//=======================================================================

// Copyright 2002 Indiana University.

// 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_ARCHETYPES_HPP

#define BOOST_GRAPH_ARCHETYPES_HPP

#include <boost/property_map.hpp>

#include <boost/concept_archetype.hpp>

namespace boost { // should use a different namespace for this

  namespace detail {

    struct null_graph_archetype : public null_archetype<> {

      struct traversal_category { }; 

    };

  }

  //===========================================================================

  template <typename Vertex, typename Directed, typename ParallelCategory,

    typename Base = detail::null_graph_archetype >

  struct incidence_graph_archetype : public Base

  {

    typedef typename Base::traversal_category base_trav_cat;

    struct traversal_category

      : public incidence_graph_tag, public base_trav_cat { };

#if 0

    typedef immutable_graph_tag mutability_category;

#endif

    typedef Vertex vertex_descriptor;

    typedef unsigned int degree_size_type;

    typedef unsigned int vertices_size_type;

    typedef unsigned int edges_size_type;

    struct edge_descriptor {

      edge_descriptor() { }

      edge_descriptor(const detail::dummy_constructor&) { }

      bool operator==(const edge_descriptor&) const { return false; }

      bool operator!=(const edge_descriptor&) const { return false; }

    };

    typedef input_iterator_archetype<edge_descriptor> out_edge_iterator;

    typedef Directed directed_category;

    typedef ParallelCategory edge_parallel_category;

    typedef void adjacency_iterator;

    typedef void in_edge_iterator;

    typedef void vertex_iterator;

    typedef void edge_iterator;

  };

  template <typename V, typename D, typename P, typename B>

  V source(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&,

           const incidence_graph_archetype<V,D,P,B>& )

  {

    return V(static_object<detail::dummy_constructor>::get());

  }

  template <typename V, typename D, typename P, typename B>

  V target(const typename incidence_graph_archetype<V,D,P,B>::edge_descriptor&,

           const incidence_graph_archetype<V,D,P,B>& )

  {

    return V(static_object<detail::dummy_constructor>::get());

  }

  template <typename V, typename D, typename P, typename B>

  std::pair<typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator,

            typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator>

  out_edges(const V&, const incidence_graph_archetype<V,D,P,B>& )

  {

    typedef typename incidence_graph_archetype<V,D,P,B>::out_edge_iterator Iter;

    return std::make_pair(Iter(), Iter());

  }

  template <typename V, typename D, typename P, typename B>

  typename incidence_graph_archetype<V,D,P,B>::degree_size_type

  out_degree(const V&, const incidence_graph_archetype<V,D,P,B>& )

  {

    return 0;

  }

  //===========================================================================

  template <typename Vertex, typename Directed, typename ParallelCategory,

    typename Base = detail::null_graph_archetype >

  struct adjacency_graph_archetype : public Base

  {

    typedef typename Base::traversal_category base_trav_cat;

    struct traversal_category

      : public adjacency_graph_tag, public base_trav_cat { };

    typedef Vertex vertex_descriptor;

    typedef unsigned int degree_size_type;

    typedef unsigned int vertices_size_type;

    typedef unsigned int edges_size_type;

    typedef void edge_descriptor;

    typedef input_iterator_archetype<Vertex> adjacency_iterator;

    typedef Directed directed_category;

    typedef ParallelCategory edge_parallel_category;

    typedef void in_edge_iterator;

    typedef void out_edge_iterator;

    typedef void vertex_iterator;

    typedef void edge_iterator;

  };

  template <typename V, typename D, typename P, typename B>

  std::pair<typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator,

            typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator>

  adjacent_vertices(const V&, const adjacency_graph_archetype<V,D,P,B>& )

  {

    typedef typename adjacency_graph_archetype<V,D,P,B>::adjacency_iterator Iter;

    return std::make_pair(Iter(), Iter());

  }

  template <typename V, typename D, typename P, typename B>

  typename adjacency_graph_archetype<V,D,P,B>::degree_size_type

  out_degree(const V&, const adjacency_graph_archetype<V,D,P,B>& )

  {

    return 0;

  }

  //===========================================================================

  template <typename Vertex, typename Directed, typename ParallelCategory,

    typename Base = detail::null_graph_archetype >

  struct vertex_list_graph_archetype : public Base

  {

    typedef incidence_graph_archetype<Vertex, Directed, ParallelCategory> 

      Incidence;

    typedef adjacency_graph_archetype<Vertex, Directed, ParallelCategory> 

      Adjacency;

    typedef typename Base::traversal_category base_trav_cat;

    struct traversal_category

      : public vertex_list_graph_tag, public base_trav_cat { };

#if 0

    typedef immutable_graph_tag mutability_category;

#endif

    typedef Vertex vertex_descriptor;

    typedef unsigned int degree_size_type;

    typedef typename Incidence::edge_descriptor edge_descriptor;

    typedef typename Incidence::out_edge_iterator out_edge_iterator;

    typedef typename Adjacency::adjacency_iterator adjacency_iterator;

    typedef input_iterator_archetype<Vertex> vertex_iterator;

    typedef unsigned int vertices_size_type;

    typedef unsigned int edges_size_type;

    typedef Directed directed_category;

    typedef ParallelCategory edge_parallel_category;

    typedef void in_edge_iterator;

    typedef void edge_iterator;

  };

  template <typename V, typename D, typename P, typename B>

  std::pair<typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator,

            typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator>

  vertices(const vertex_list_graph_archetype<V,D,P,B>& )

  {

    typedef typename vertex_list_graph_archetype<V,D,P,B>::vertex_iterator Iter;

    return std::make_pair(Iter(), Iter());

  }

  template <typename V, typename D, typename P, typename B>

  typename vertex_list_graph_archetype<V,D,P,B>::vertices_size_type

  num_vertices(const vertex_list_graph_archetype<V,D,P,B>& )

  {

    return 0;

  }

  // ambiguously inherited from incidence graph and adjacency graph

  template <typename V, typename D, typename P, typename B>

  typename vertex_list_graph_archetype<V,D,P,B>::degree_size_type

  out_degree(const V&, const vertex_list_graph_archetype<V,D,P,B>& )

  {

    return 0;

  }

  //===========================================================================

  struct property_graph_archetype_tag { };

  template <typename GraphArchetype, typename Property, typename ValueArch>

  struct property_graph_archetype : public GraphArchetype

  {

    typedef property_graph_archetype_tag graph_tag;

    typedef ValueArch vertex_property_type;

    typedef ValueArch edge_property_type;

  };

  struct choose_edge_property_map_archetype {

    template <typename Graph, typename Property, typename Tag>

    struct bind_ {

      typedef mutable_lvalue_property_map_archetype

        <typename Graph::edge_descriptor, Property> type;

      typedef lvalue_property_map_archetype

        <typename Graph::edge_descriptor, Property> const_type;

    };

  };

  template <>

  struct edge_property_selector<property_graph_archetype_tag> {

    typedef choose_edge_property_map_archetype type;

  };

  struct choose_vertex_property_map_archetype {

    template <typename Graph, typename Property, typename Tag>

    struct bind_ {

      typedef mutable_lvalue_property_map_archetype

        <typename Graph::vertex_descriptor, Property> type;

      typedef lvalue_property_map_archetype

        <typename Graph::vertex_descriptor, Property> const_type;

    };

  };

  template <>

  struct vertex_property_selector<property_graph_archetype_tag> {

    typedef choose_vertex_property_map_archetype type;

  };

  template <typename G, typename P, typename V>

  typename property_map<property_graph_archetype<G, P, V>, P>::type

  get(P, property_graph_archetype<G, P, V>&) {

    typename property_map<property_graph_archetype<G, P, V>, P>::type pmap;

    return pmap;

  }

  template <typename G, typename P, typename V>

  typename property_map<property_graph_archetype<G, P, V>, P>::const_type

  get(P, const property_graph_archetype<G, P, V>&) {

    typename property_map<property_graph_archetype<G, P, V>, P>::const_type pmap;

    return pmap;

  }

  template <typename G, typename P, typename K, typename V>

  typename property_traits<typename property_map<property_graph_archetype<G, P, V>, P>::const_type>::value_type

  get(P p, const property_graph_archetype<G, P, V>& g, K k) {

    return get( get(p, g), k);

  }

  template <typename G, typename P, typename V, typename Key>

  void

  put(P p, property_graph_archetype<G, P, V>& g, 

      const Key& key, const V& value)

  {

    typedef typename boost::property_map<property_graph_archetype<G, P, V>, P>::type Map;

    Map pmap = get(p, g);

    put(pmap, key, value);

  }

  struct color_value_archetype {

    color_value_archetype() { }

    color_value_archetype(detail::dummy_constructor) { }

    bool operator==(const color_value_archetype& ) const { return true; }

    bool operator!=(const color_value_archetype& ) const { return true; }

  };

  template <>

  struct color_traits<color_value_archetype> {

    static color_value_archetype white()

    { 

      return color_value_archetype

        (static_object<detail::dummy_constructor>::get()); 

    }

    static color_value_archetype gray()

    {

      return color_value_archetype

        (static_object<detail::dummy_constructor>::get()); 

    }

    static color_value_archetype black()

    {

      return color_value_archetype

        (static_object<detail::dummy_constructor>::get()); 

    }

  };

  template <typename T>

  class buffer_archetype {

  public:

    void push(const T&) {}

    void pop() {}

    T& top() { return static_object<T>::get(); }

    const T& top() const { return static_object<T>::get(); }

    bool empty() const { return true; }

  };

} // namespace boost

#endif // BOOST_GRAPH_ARCHETYPES_HPP