// copied and modified from boost/libs/graph/example/knights-tour.cpp

//=======================================================================
// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, 
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#include <boost/config.hpp>
#include <stdlib.h>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <boost/operators.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/astar_search.hpp>
#include <boost/shared_container_iterator.hpp>

using namespace std;
using namespace boost;

struct vertex_t
{
	vertex_t() : i(0) {}
	explicit vertex_t(int i) : i(i) {}
	vertex_t(vertex_t const& rhs) : i(rhs.i) {}

	bool operator==(vertex_t const& rhs) const {
		return i == rhs.i;
	}
	bool operator!=(vertex_t const& rhs) const {
		return !operator==(rhs);
	}

	int i;
};

struct edge_t
{
	edge_t() {}
	edge_t(vertex_t const& u, vertex_t const& v) : u(u), v(v) {}
	edge_t(edge_t const& rhs) : u(rhs.u), v(rhs.v) {}

	bool operator==(edge_t const& rhs) const {
		return u == rhs.u && v == rhs.v;
	}
	bool operator!=(edge_t const& rhs) const {
		return !operator==(rhs);
	}

	vertex_t u;
	vertex_t v;
};

struct graph_t
{
	typedef std::vector<vertex_t>::iterator vertex_iterator;
	typedef std::vector<vertex_t>::size_type vertices_size_type;
	typedef vertex_t vertex_descriptor;
	typedef edge_t edge_descriptor;
	typedef directed_tag directed_category;
	typedef disallow_parallel_edge_tag edge_parallel_category;

	struct category_t : public incidence_graph_tag, public vertex_list_graph_tag {};
	typedef category_t traversal_category;

	typedef shared_container_iterator<vector<edge_t> > out_edge_iterator;
	typedef size_t degree_size_type;

	typedef void adjacency_iterator;
	typedef void in_edge_iterator;
	typedef void edge_iterator;
	typedef void edges_size_type;

	explicit graph_t(int size)
	{
        for (int i=0; i<size; i++) {
			m_vertices.push_back(vertex_t(i));
		}
	}

public:
	std::vector<vertex_t> m_vertices;
};

vertex_t source(edge_t const& e, graph_t const&)
{
	return e.u;
}

vertex_t target(edge_t const& e, graph_t const&)
{
	return e.v;
}

std::pair<graph_t::out_edge_iterator, graph_t::out_edge_iterator>
out_edges(vertex_t const& v, graph_t const& g)
{
	boost::shared_ptr<vector<edge_t> > c(new vector<edge_t> );
	if (v.i > 0) {
		c->push_back(edge_t(vertex_t(v.i-1), v));
	}
	if (static_cast<size_t>(v.i) < g.m_vertices.size()-1) {
		c->push_back(edge_t(v, vertex_t(v.i+1)));
	}
	
	return make_shared_container_range(c);
}

size_t out_degree(vertex_t const& v, graph_t const& g)
{
	std::pair<graph_t::out_edge_iterator, graph_t::out_edge_iterator> eis = out_edges(v, g);
	return std::distance(eis.first, eis.second);

}

std::pair<graph_t::vertex_iterator, graph_t::vertex_iterator>
vertices(graph_t& g) {
	return make_pair(g.m_vertices.begin(), g.m_vertices.end());
}

graph_t::vertices_size_type num_vertices(graph_t const& g) {
	return g.m_vertices.size();
}

struct vertex_index_map_t
{
	typedef int value_type;
	typedef int reference;
	typedef vertex_t key_type;
	typedef readable_property_map_tag category;
};
int get(vertex_index_map_t, vertex_t const& v) {
	return v.i;
}

struct edge_weight_map_t
{
	typedef double value_type;
	typedef double reference;
	typedef edge_t key_type;
	typedef readable_property_map_tag category;
};
double get(edge_weight_map_t, edge_t const& e) {
	return abs(e.u.i - e.u.i);
}
///////////////////////////////////////////////////////////////////////////////

struct h : public astar_heuristic<graph_t, double>
{
    double operator()(vertex_t const& v) const
	{
		return 0.0;
	}
};

int main(int argc, char *argv[])
{
	graph_t g(10);

	astar_search
		( g
		, vertex_t(0)
		, h()
		, weight_map(edge_weight_map_t())
		  .vertex_index_map(vertex_index_map_t())
		);

	return 0;
}