#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>


class Op
{
	const char *mName;
public:
	Op( const char *s ) : mName(s) {}
	const char* name() const { return mName; }
};

struct OpMapper
{
	Op *op;
	OpMapper( Op *o = NULL ) : op(o) {}
};

namespace boost { namespace graph {

	template <typename T>
	struct vertex_name_extractor
	{
		typedef T   type;
		typedef Op* result_type;
		const result_type operator() ( const T& v ) const
		{
			return v.me;
		}
	};

	template<typename VertexProperty>                                                         
	struct vertex_info_constructor
	{
		typedef VertexProperty return_type;                                                     
		typedef typename vertex_name_extractor<VertexProperty>::result_type argument_type;      
		return_type operator()( argument_type n )
		{                                                                                       
			return VertexProperty(n);
		}                                                                                       
	};

	template<> struct internal_vertex_name<OpMapper>
	{ typedef multi_index::member<OpMapper, Op*, &OpMapper::op> type; };

	template<> struct internal_vertex_constructor<OpMapper>
	{ typedef vertex_info_constructor<OpMapper> type; };

} }


class BoostGraph
{
	typedef boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, OpMapper> graph_t;
	typedef boost::graph_traits<graph_t>::vertex_descriptor Vertex;
	typedef boost::graph_traits<graph_t>::edge_descriptor   Edge;
	typedef boost::graph_traits<graph_t>::in_edge_iterator  Iterator;

	graph_t mGraph;

	bool removeVertexIfEmpty( const Vertex &v )
	{
		if ( boost::degree(v, mGraph)==0 && boost::out_degree(v, mGraph)==0 )
		{
			OpMapper &op = mGraph[v];
			printf("removeVert: %s (%p,%lu)\n", op.op->name(), op.op, v);
			boost::clear_vertex(v, mGraph);
			boost::remove_vertex(v, mGraph);
			return true;
		}
		return false;
	}

	void _printInputs( const Vertex &v )
	{
		Op *dst = mGraph[v].op;
		Iterator vi, ve;
		for ( boost::tie(vi,ve) = boost::in_edges(v, mGraph); vi != ve; ++vi )
		{
			const Vertex dv = source(*vi, mGraph);
			Op *src = mGraph[dv].op;
			printf("inedge: %s (%p,%lu) -> %s (%p,%lu)\n", src->name(), src, size_t(v), dst?dst->name():"!NULL!", dst, size_t(dv));
		}
	}

	void printInputs( const Vertex &v )
	{
		_printInputs(v);
		printf("---------------------------------\n");
	}

public:
	void connect( Op &from, Op &to )
	{
		const Vertex u = boost::graph::add_vertex(&from, mGraph), v = boost::graph::add_vertex(&to, mGraph);
		if ( boost::edge(u, v, mGraph).second==false )
		{
			boost::add_edge(u, v, mGraph);
			printInputs(v);
		}
	}

	void disconnect( Op &from, Op &to )
	{
		boost::optional<Vertex> fv = boost::graph::find_vertex(&from, mGraph);
		if ( fv )
		{
			const boost::optional<Vertex> tv = boost::graph::find_vertex(&to, mGraph);
			if ( tv )
			{
				printf("disconnect: %s (%p,%lu) -> %s (%p,%lu)\n", from.name(), &from, *fv, to.name(), &to, *tv);
				boost::remove_edge(*fv, *tv, mGraph);
				if ( removeVertexIfEmpty(*tv) )
				{
					// fv invalid now ?
					fv = boost::graph::find_vertex(&from, mGraph);
					if ( fv ) removeVertexIfEmpty(*fv);

					printInputs(*tv);
					return;
				}
				printInputs(*tv);
			}
			removeVertexIfEmpty(*fv);
		}
	}

	void dumpInputs( const Vertex &v )
	{
		Iterator vi, ve;
		for ( boost::tie(vi,ve) = boost::in_edges(v, mGraph); vi != ve; ++vi )
			dumpInputs( source(*vi, mGraph) );

		_printInputs(v);
	}

	void printInputs( Op &op )
	{
		printf("-------------- tree -------------------\n");
		dumpInputs( *boost::graph::find_vertex(&op, mGraph) );
	}
};

extern "C" int main( int argc, const char **argv )
{
	Op a("a"), b("b"), c("c"), d("d");
	BoostGraph bg;
	
	bg.connect(c, d);

	// Swapping these two lines should have no affect...but it does
	// BoostGraph::connect calling boost::graph::add_vertex is giving bad vertex ids
	bg.connect(a, b);
	bg.disconnect(c, d);

	bg.connect(c, b);	
	bg.connect(b, d);

	bg.printInputs(d);

	return 0;
}