// Copyright David Abrahams 2002. Permission to copy, use,
// modify, sell and distribute this software is granted provided this
// copyright notice appears in all copies. This software is provided
// "as is" without express or implied warranty, and with no claim as
// to its suitability for any purpose.

//#include <boost/python/converter/type_id.hpp>
#include <boost/iterator_adaptors.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_iterator.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <vector>
#include <set>

namespace boost {

namespace
{

  //
  // Here we put together the low-level data structures of the
  // inheritance graph representation.
  //
  //typedef python::converter::undecorated_type_id_t class_id;
  //llee boost/mpl/select_type.hpp is not in the cvs yet :-(
  typedef int class_id;

  struct vertex;

  enum direction_t { up, down };
  
  struct edge
  {
      edge(direction_t direction, vertex const* target, void*(*cast)(void*))
          : direction(direction)
            , target(target)
            , cast(cast)
      {}
      
      direction_t direction;
      vertex const* target;
      void* (*cast)(void*);
  };

  typedef std::vector<edge> edge_list_t;
  
  struct vertex : std::vector<edge>
  {
      vertex(class_id source)
          : source(source)
      {}

      bool operator<(vertex const& rhs) const
      {
          return this->source < rhs.source;
      }
      
      class_id source;
      edge_list_t edges;
      int color;
  };

  
  //llee:
  struct my_color_map {
    typedef vertex const* key_type;
    typedef int value_type;
    typedef int&  reference;
    typedef read_write_property_map_tag category;
  };

  //llee
  int get(my_color_map, const vertex const* v) {
    return v->color;
  }

  //llee
  void put(my_color_map, vertex const* vv, int i) {
    vertex * v = const_cast<vertex *>(vv);
    v->color = i;
  }
  

  typedef std::set<vertex> vertex_set;
  
  vertex_set&
  vertices()
  {
      static vertex_set v;
      return v;
  }

  //
  // Now we build two different BGL graphs on top of the vertex_set:
  // full_graph is a BGL representation of the entire graph, and
  // up_graph is a filtered view of just the up-edges.
  //
  // Why do we have to do this at all? It should be trivial to
  // redefine adjacency_list so that it can use a set<> as its
  // backbone, if it already works with list<>.

  // This is the base for both views of the graph
  struct graph_base
  {
      graph_base() : m_vertices(vertices()) {}
      
      typedef graph_base self;

      //
      // Graph requirements
      //
      typedef vertex const* vertex_descriptor;
      typedef std::pair<vertex_descriptor,edge const*> edge_descriptor;
      typedef directed_tag directed_category;
      typedef disallow_parallel_edge_tag edge_parallel_category;
      
      struct traversal_category : 
          public virtual vertex_list_graph_tag,
          public virtual incidence_graph_tag,
          public virtual adjacency_graph_tag
      { };

      //
      // IncidenceGraph requirements
      //
      
      // A function object which builds an edge_descriptor from a
      // vertex_descriptor and an edge.
      //
      // We have to do this because the graph library requires that
      // every IncidenceGraph support source(e), returning the source
      // vertex of an arbitrary edge. Our graph doesn't store the
      // source vertex in the edge structure, so we need to cobble
      // together a pair which can supply the needed information.
      //
      // I think this is much less-efficient than it has to be for
      // most graph algorithms. Probably a new concept is needed to
      // distinguish a graph that doesn't support source(e).
      struct build_edge_descriptor
      {
          typedef edge_descriptor result_type;
	build_edge_descriptor() {} //llee: required by transform_iterator_policies
          build_edge_descriptor(vertex_descriptor source) : source(source) {}
          
	result_type operator()(edge const& e) const //llee: add const
          {
              return result_type(source, &e);
          }
          
          vertex_descriptor source;
      };

      typedef edge_list_t::size_type degree_size_type;

      friend vertex_descriptor
      source(edge_descriptor const& e, self const&)
      {
          return e.first;
      }

      friend vertex_descriptor
      target(edge_descriptor const& e, self const&)
      {
          return e.second->target;
      }

      friend degree_size_type
      inline out_degree(vertex_descriptor v, self const&)
      {
          return v->edges.size();
      }

      //
      // VertexListGraph requirements
      //
      typedef vertex_set::const_iterator vertex_iterator;
      typedef vertex_set::size_type vertices_size_type;

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

      friend vertices_size_type
      num_vertices(self const& g)
      {
          return g.m_vertices.size();
      }

      // Garbage for graph_traits<>: what causes the library to require these?
      typedef void in_edge_iterator;
      typedef void edge_iterator;
      typedef void edges_size_type;
   protected:
      vertex_set const& m_vertices;
  };

  // This intermediate class is used to generate the information
  // specific to the view. The EdgeIterator type determines whether
  // we're looking at all edges or just the up-edges.
  template <class Graph, class EdgeIterator>
  struct inheritance_graph : graph_base
  {
      typedef Graph self;

      //
      // IncidenceGraph requirements
      //
      
      // Construct the outgoing edge iterator type.  See the
      // description of build_edge_descriptor from graph_base, above,
      // for an explanation.
      typedef boost::transform_iterator_generator<
            build_edge_descriptor,EdgeIterator
          >::type out_edge_iterator;

      friend std::pair<out_edge_iterator, out_edge_iterator>
      out_edges(vertex_descriptor v, self const&)
      {
          return std::pair<out_edge_iterator, out_edge_iterator>(
              out_edge_iterator(
                  EdgeIterator(v->edges.begin())
                  , out_edge_iterator::policies_type(v))
              
              , out_edge_iterator(
                  EdgeIterator(v->edges.end())
                  , out_edge_iterator::policies_type(v))
              );
      }

      //
      // AdjacencyGraph requirements
      //

      // This is just boilerplate that makes an IncidenceGraph into an
      // AdjacencyGraph. Probably the BGL ought to have a graph
      // adaptor for this purpose.
      typedef boost::adjacency_iterator_generator<
          self, vertex_descriptor, out_edge_iterator
          >::type adjacency_iterator;

      friend std::pair<adjacency_iterator, adjacency_iterator>
      adjacent_vertices(vertex_descriptor v, self const& g)
      {
          return out_edges(v, g);
      }
  };

  // The unfiltered graph type
  struct full_graph : inheritance_graph<full_graph,edge_list_t::const_iterator>
  {
  };

  //
  // Define the filtered graph type
  //

  // First build the filtered edge iterator
  struct is_up
  {
      bool operator()(edge const& e) { return e.direction == up; }
  };

  typedef boost::filter_iterator_generator<
      is_up
      , edge_list_t::const_iterator
      , edge
      , edge const&
      , edge const
      >::type up_edge_iterator;

  // Then use it to define the up_graph
  struct up_graph : inheritance_graph<up_graph,up_edge_iterator>
  {
  };

  // A utility function for graph building
  void add_cast(class_id source, class_id target, void*(*cast)(void*), direction_t direction)
  {
      vertex_set& g = vertices();
      std::pair<vertex_set::iterator,bool> s = g.insert(source);
      std::pair<vertex_set::iterator,bool> t = g.insert(target);
      
      const_cast<vertex&>(*s.first).push_back(
          edge(direction, &*t.first, cast));
  }
}

namespace python { namespace object {

BOOST_DECL void add_upcast(class_id source, class_id target, void*(*cast)(void*))
{
    add_cast(source, target, cast, up);

    // Just test the graph to see if we've met requirements.
    up_graph g;
    
    boost::my_color_map color; //llee

    breadth_first_visit(
#if 0   //llee
        g, &*vertices().find(source),
        visitor(bfs_visitor<null_visitor>())
#else   //llee
	//g, &*vertices().find(source), q, default_bfs_visitor(), color
	//or
	g, &*vertices().find(source), color_map(color).visitor(default_bfs_visitor())
#endif
        );
}

BOOST_DECL void add_downcast(class_id source, class_id target, void*(*cast)(void*))
{
    add_cast(source, target, cast, down);
}

}}} // namespace boost::python::object