#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/astar_search.hpp>

using namespace std;


template <typename Functor, typename Arg>
struct function_property_map {
private:
  Functor f;

public:
  typedef typename boost::property_traits<
    function_property_map<Functor, Arg>
  >::value_type
  value_type; 

  explicit function_property_map(const Functor& f): f(f) {}

  friend value_type get(const function_property_map& pm, const Arg& x) {
    return pm.f(x);
  }
};

namespace boost {
  template <typename Functor, typename Arg>
  struct property_traits<function_property_map<Functor, Arg> > {
    typedef typename boost::result_of<Functor(Arg)>::type value_type;
    typedef value_type reference;
    typedef Arg key_type;
    typedef boost::readable_property_map_tag category;
  };
}

template <typename Arg, typename Functor>
function_property_map<Functor, Arg>
make_function_property_map(const Functor& f) {
  return function_property_map<Functor, Arg>(f);
}

struct Hex
{
  size_t id;
};

struct Unit
{
  Hex* hex;

  virtual int moveCost(Hex& hex)
  {
    return 1;
  }
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Hex*> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef boost::graph_traits<Graph>::edge_descriptor   Edge;

struct GoalDistanceHeuristic : public boost::astar_heuristic<Graph, int>
{
  GoalDistanceHeuristic(Graph& g, Vertex goal) : g_(g), goal_(goal)
  {

  }

  int operator() (Vertex v)
  {
    return 1;
  }

  Graph& g_;
  Vertex goal_;
};

struct AStarVisitor : public boost::default_astar_visitor
{
  AStarVisitor(Graph& graph, Vertex goal, int maxDist)
    : graph_(graph), goal_(goal), maxDist_(maxDist)
  {

  }

  void examine_vertex(Vertex u, const Graph& g)
  {
    /*
    if (graph_.distances_[u] > maxDist_)
    {
      throw MaxDepthReached();
    }

    if (u == goal_)
    {
      throw GoalFound();
    }
    */
  }

  Graph& graph_;
  Vertex goal_;
  int maxDist_;
};

struct EdgeWeight
{
  typedef int result_type;

  EdgeWeight(Graph& g, Unit& unit) : g_(g), unit_(unit)
  {

  }

  result_type operator()(Edge e) const
  {
    Vertex v = target(e, g_);

    return unit_.moveCost(*g_[v]);
  }

  Graph& g_;
  Unit& unit_;
};

int main()
{
  Graph graph;

  std::vector<Vertex> predecessors;

  std::vector<int> distances;

  Unit unit;
  Hex start, goal;

  boost::astar_search(graph, start.id, 
    GoalDistanceHeuristic(graph, goal.id),
    boost::visitor(AStarVisitor(graph, goal.id, 5))
    .predecessor_map(&predecessors[0])
    .distance_map(&distances[0])
    .weight_map(make_function_property_map<Edge>(EdgeWeight(graph, unit))));
}