//
//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// 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)
//=======================================================================
//
#ifndef BOOST_GRAPH_GRAPH_AS_TREE_HPP
#define BOOST_GRAPH_GRAPH_AS_TREE_HPP

#include <vector>
#include <boost/config.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/tree_traits.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/visitors.hpp>

namespace boost {

  template <class Graph, class Node, class ChIt, class Derived>
  class graph_as_tree_base
  {
    typedef Derived Tree;
  public:
    typedef Node node_descriptor;
    typedef ChIt children_iterator;
    
    graph_as_tree_base(Graph& g, Node root) : _g(g), _root(root) { }
    
    friend Node root(const Tree& t) { return t._root; }
    
    template <class N>
    friend std::pair<ChIt,ChIt>
    children(N n, const Tree& t) { return adjacent_vertices(n, t._g);  }
    
    template<class N>
    friend Node parent(N n, const Tree& t) { 
      return boost::get(t.parent_pa(), n); 
    }
    
    Graph& _g;
    Node _root;
  };
  
  struct graph_as_tree_tag { };
  
  template <class Graph, class ParentMap
          , class Node 
#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
             = typename graph_traits<Graph>::vertex_descriptor
#endif
          , class ChIt
#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
              = typename graph_traits<Graph>::adjacency_iterator
#endif
           >
  class graph_as_tree
    : public graph_as_tree_base<Graph, Node, ChIt, 
            graph_as_tree<Graph,ParentMap,Node,ChIt> >
  {
    typedef graph_as_tree self;
    typedef graph_as_tree_base<Graph, Node, ChIt, self> super;
  public:
    graph_as_tree(Graph& g, Node root) : super(g, root) {  }
    
    graph_as_tree(Graph& g, Node root, ParentMap p) : super(g, root), _p(p) { 
      breadth_first_search(g, root, 
                           visitor(make_bfs_visitor
                   (record_predecessors(p, boost::on_tree_edge()))));
    }
    ParentMap parent_pa() const { return _p; }
    typedef graph_as_tree_tag graph_tag; // for property_map
  protected:
    ParentMap _p;
  };
  

  namespace detail {

    struct graph_as_tree_vertex_property_selector {
      template <typename GraphAsTree, typename Property, typename Tag>
      struct bind_ {
        typedef typename GraphAsTree::base_type Graph;
        typedef property_map<Graph, Tag> PMap;
        typedef typename PMap::type type;
        typedef typename PMap::const_type const_type;
      };
    };

    struct graph_as_tree_edge_property_selector {
      template <typename GraphAsTree, typename Property, typename Tag>
      struct bind_ {
        typedef typename GraphAsTree::base_type Graph;
        typedef property_map<Graph, Tag> PMap;
        typedef typename PMap::type type;
        typedef typename PMap::const_type const_type;
      };
    };

  } // namespace detail

  template <>
  struct vertex_property_selector<graph_as_tree_tag> {
    typedef detail::graph_as_tree_vertex_property_selector type;
  };

  template <>
  struct edge_property_selector<graph_as_tree_tag> {
    typedef detail::graph_as_tree_edge_property_selector type;
  };

  template <typename Graph, typename P, typename N, typename C, 
            typename Property>
  typename property_map<Graph, Property>::type
  get(Property p, graph_as_tree<Graph,P,N,C>& g)
  {
    return get(p, g._g);
  }

  template <typename Graph, typename P, typename N, typename C, 
            typename Property>
  typename property_map<Graph, Property>::const_type
  get(Property p, const graph_as_tree<Graph,P,N,C>& g)
  {
    const Graph& gref = g._g; // in case GRef is non-const
    return get(p, gref);
  }

  template <typename Graph, typename P, typename N, typename C, 
            typename Property, typename Key>
  typename property_traits<
    typename property_map<Graph, Property>::const_type
  >::value_type
  get(Property p, const graph_as_tree<Graph,P,N,C>& g, const Key& k)
  {
    return get(p, g._g, k);
  }

  template <typename Graph, typename P, typename N, typename C, 
            typename Property, typename Key, typename Value>
  void
  put(Property p, const graph_as_tree<Graph,P,N,C>& g, const Key& k,
      const Value& val)
  {
    put(p, g._g, k, val);
  }

} // namespace boost

#endif //  BOOST_GRAPH_GRAPH_AS_TREE_HPP