Chris@16: //  (C) Copyright Jeremy Siek 2004 
Chris@16: //  (C) Copyright Thomas Claveirole 2010
Chris@16: //  (C) Copyright Ignacy Gawedzki 2010
Chris@16: //  Distributed under the Boost Software License, Version 1.0. (See
Chris@16: //  accompanying file LICENSE_1_0.txt or copy at
Chris@16: //  http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H
Chris@16: #define BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H
Chris@16: 
Chris@16: // Sure would be nice to be able to forward declare these
Chris@16: // instead of pulling in all the headers. Too bad that
Chris@16: // is not legal. There ought to be a standard <stlfwd> header. -JGS 
Chris@16: 
Chris@16: #include <boost/next_prior.hpp>
Chris@16: 
Chris@16: #include <algorithm>   // for std::remove
Chris@101: #include <utility>
Chris@16: #include <vector>
Chris@16: #include <list>
Chris@16: #include <map>
Chris@16: #include <set>
Chris@16: #include <boost/unordered_set.hpp>
Chris@16: #include <boost/unordered_map.hpp>
Chris@16: 
Chris@16: #if !defined BOOST_NO_SLIST
Chris@16: #  ifdef BOOST_SLIST_HEADER
Chris@16: #    include BOOST_SLIST_HEADER
Chris@16: #  else
Chris@16: #    include <slist>
Chris@16: #  endif
Chris@16: #endif
Chris@16: 
Chris@101: #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
Chris@101: #include <unordered_set>
Chris@101: #endif
Chris@101: 
Chris@101: #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
Chris@101: #include <unordered_map>
Chris@101: #endif
Chris@101: 
Chris@101: #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@101: #define BOOST_PENDING_FWD_TYPE(type) const type&
Chris@101: #define BOOST_PENDING_FWD_VALUE(type, var) (var)
Chris@101: #else
Chris@101: #define BOOST_PENDING_FWD_TYPE(type) type&&
Chris@101: #define BOOST_PENDING_FWD_VALUE(type, var) (std::forward<type>((var)))
Chris@16: #endif
Chris@16: 
Chris@16: // The content of this file is in 'graph_detail' because otherwise
Chris@16: // there will be name clashes with 
Chris@16: // sandbox/boost/sequence_algo/container_traits.hpp
Chris@16: // The 'detail' subnamespace will still cause problems.
Chris@16: namespace boost { namespace graph_detail {
Chris@16: 
Chris@16:   //======================================================================
Chris@16:   // Container Category Tags
Chris@16:   //
Chris@16:   //   They use virtual inheritance because there are lots of
Chris@16:   //   inheritance diamonds.
Chris@16: 
Chris@16:   struct container_tag { };
Chris@16:   struct forward_container_tag : virtual public container_tag { };
Chris@16:   struct reversible_container_tag : virtual public forward_container_tag { };
Chris@16:   struct random_access_container_tag
Chris@16:     : virtual public reversible_container_tag { };
Chris@16:   
Chris@16:   struct sequence_tag : virtual public forward_container_tag { };
Chris@16: 
Chris@16:   struct associative_container_tag : virtual public forward_container_tag { };
Chris@16: 
Chris@16:   struct sorted_associative_container_tag 
Chris@16:     : virtual public associative_container_tag,
Chris@16:       virtual public reversible_container_tag { };
Chris@16: 
Chris@16:   struct front_insertion_sequence_tag : virtual public sequence_tag { };
Chris@16:   struct back_insertion_sequence_tag : virtual public sequence_tag { };
Chris@16: 
Chris@16:   struct unique_associative_container_tag 
Chris@16:     : virtual public associative_container_tag { };
Chris@16:   struct multiple_associative_container_tag 
Chris@16:     : virtual public associative_container_tag { };
Chris@16:   struct simple_associative_container_tag 
Chris@16:     : virtual public associative_container_tag { };
Chris@16:   struct pair_associative_container_tag 
Chris@16:     : virtual public associative_container_tag { };
Chris@16: 
Chris@16: 
Chris@16:   //======================================================================
Chris@16:   // Iterator Stability Tags
Chris@16:   //
Chris@16:   // Do mutating operations such as insert/erase/resize invalidate all
Chris@16:   // outstanding iterators?
Chris@16: 
Chris@16:   struct stable_tag { };
Chris@16:   struct unstable_tag { };
Chris@16: 
Chris@16:   //======================================================================
Chris@16:   // Container Traits Class and container_category() function
Chris@16: 
Chris@16:   // don't use this unless there is partial specialization 
Chris@16:   template <class Container>
Chris@16:   struct container_traits {
Chris@16:     typedef typename Container::category category;
Chris@16:     typedef typename Container::iterator_stability iterator_stability;
Chris@16:   };
Chris@16: 
Chris@16:   // Use this as a compile-time assertion that X is stable
Chris@16:   inline void require_stable(stable_tag) { }
Chris@16: 
Chris@16:   // std::vector
Chris@16:   struct vector_tag :
Chris@16:     virtual public random_access_container_tag,
Chris@16:     virtual public back_insertion_sequence_tag { };
Chris@16: 
Chris@16:   template <class T, class Alloc>
Chris@16:   vector_tag container_category(const std::vector<T,Alloc>&)
Chris@16:     { return vector_tag(); }
Chris@16: 
Chris@16:   template <class T, class Alloc>
Chris@16:   unstable_tag iterator_stability(const std::vector<T,Alloc>&)
Chris@16:     { return unstable_tag(); }
Chris@16: 
Chris@16:   template <class T, class Alloc>
Chris@16:   struct container_traits< std::vector<T,Alloc> > {
Chris@16:     typedef vector_tag category;
Chris@16:     typedef unstable_tag iterator_stability;
Chris@16:   };
Chris@16: 
Chris@16:   // std::list
Chris@16:   struct list_tag :
Chris@16:     virtual public reversible_container_tag,
Chris@16:     virtual public back_insertion_sequence_tag
Chris@16:     // this causes problems for push_dispatch...
Chris@16:     //    virtual public front_insertion_sequence_tag
Chris@16:     { };
Chris@16: 
Chris@16:   template <class T, class Alloc>
Chris@16:   list_tag container_category(const std::list<T,Alloc>&)
Chris@16:     { return list_tag(); }
Chris@16: 
Chris@16:   template <class T, class Alloc>
Chris@16:   stable_tag iterator_stability(const std::list<T,Alloc>&)
Chris@16:     { return stable_tag(); }
Chris@16: 
Chris@16:   template <class T, class Alloc>
Chris@16:   struct container_traits< std::list<T,Alloc> > {
Chris@16:     typedef list_tag category;
Chris@16:     typedef stable_tag iterator_stability;
Chris@16:   };
Chris@16: 
Chris@16: 
Chris@16:   // std::slist
Chris@16: #ifndef BOOST_NO_SLIST
Chris@16:   template <class T, class Alloc>
Chris@16:   struct container_traits<BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc> > {
Chris@16:     typedef front_insertion_sequence_tag category;
Chris@16:     typedef stable_tag iterator_stability;
Chris@16:   };
Chris@16:   template <class T, class Alloc>
Chris@16:   front_insertion_sequence_tag container_category(
Chris@16:   const BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc>&
Chris@16:   )
Chris@16:     { return front_insertion_sequence_tag(); }
Chris@16: 
Chris@16:   template <class T, class Alloc>
Chris@16:   stable_tag iterator_stability(
Chris@16:   const BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc>&)
Chris@16:     { return stable_tag(); }
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16:   // std::set
Chris@16:   struct set_tag :
Chris@16:     virtual public sorted_associative_container_tag,
Chris@16:     virtual public simple_associative_container_tag,
Chris@16:     virtual public unique_associative_container_tag 
Chris@16:     { };
Chris@16: 
Chris@16:   template <class Key, class Cmp, class Alloc> 
Chris@16:   set_tag container_category(const std::set<Key,Cmp,Alloc>&)
Chris@16:   { return set_tag(); }
Chris@16: 
Chris@16:   template <class Key, class Cmp, class Alloc> 
Chris@16:   stable_tag iterator_stability(const std::set<Key,Cmp,Alloc>&)
Chris@16:   { return stable_tag(); }
Chris@16: 
Chris@16:   template <class Key, class Cmp, class Alloc> 
Chris@16:   struct container_traits< std::set<Key,Cmp,Alloc> > {
Chris@16:     typedef set_tag category;
Chris@16:     typedef stable_tag iterator_stability;
Chris@16:   };
Chris@16: 
Chris@16:   // std::multiset
Chris@16:   struct multiset_tag :
Chris@16:     virtual public sorted_associative_container_tag,
Chris@16:     virtual public simple_associative_container_tag,
Chris@16:     virtual public multiple_associative_container_tag 
Chris@16:     { };
Chris@16: 
Chris@16:   template <class Key, class Cmp, class Alloc> 
Chris@16:   multiset_tag container_category(const std::multiset<Key,Cmp,Alloc>&)
Chris@16:   { return multiset_tag(); }
Chris@16: 
Chris@16:   template <class Key, class Cmp, class Alloc> 
Chris@16:   stable_tag iterator_stability(const std::multiset<Key,Cmp,Alloc>&)
Chris@16:   { return stable_tag(); }
Chris@16: 
Chris@16:   template <class Key, class Cmp, class Alloc> 
Chris@16:   struct container_traits< std::multiset<Key,Cmp,Alloc> > {
Chris@16:     typedef multiset_tag category;
Chris@16:     typedef stable_tag iterator_stability;
Chris@16:   };
Chris@16: 
Chris@16:   // deque
Chris@16: 
Chris@16:   // std::map
Chris@16:   struct map_tag :
Chris@16:     virtual public sorted_associative_container_tag,
Chris@16:     virtual public pair_associative_container_tag,
Chris@16:     virtual public unique_associative_container_tag 
Chris@16:     { };
Chris@16: 
Chris@16:   template <class Key, class T, class Cmp, class Alloc> 
Chris@16:   struct container_traits< std::map<Key,T,Cmp,Alloc> > {
Chris@16:     typedef map_tag category;
Chris@16:     typedef stable_tag iterator_stability;
Chris@16:   };
Chris@16: 
Chris@16:   template <class Key, class T, class Cmp, class Alloc> 
Chris@16:   map_tag container_category(const std::map<Key,T,Cmp,Alloc>&)
Chris@16:   { return map_tag(); }
Chris@16: 
Chris@16:   template <class Key, class T, class Cmp, class Alloc> 
Chris@16:   stable_tag iterator_stability(const std::map<Key,T,Cmp,Alloc>&)
Chris@16:   { return stable_tag(); }
Chris@16: 
Chris@16:   // std::multimap
Chris@16:   struct multimap_tag :
Chris@16:     virtual public sorted_associative_container_tag,
Chris@16:     virtual public pair_associative_container_tag,
Chris@16:     virtual public multiple_associative_container_tag 
Chris@16:     { };
Chris@16: 
Chris@16:   template <class Key, class T, class Cmp, class Alloc> 
Chris@16:   struct container_traits< std::multimap<Key,T,Cmp,Alloc> > {
Chris@16:     typedef multimap_tag category;
Chris@16:     typedef stable_tag iterator_stability;
Chris@16:   };
Chris@16: 
Chris@16:   template <class Key, class T, class Cmp, class Alloc> 
Chris@16:   multimap_tag container_category(const std::multimap<Key,T,Cmp,Alloc>&)
Chris@16:   { return multimap_tag(); }
Chris@16: 
Chris@16:   template <class Key, class T, class Cmp, class Alloc> 
Chris@16:   stable_tag iterator_stability(const std::multimap<Key,T,Cmp,Alloc>&)
Chris@16:   { return stable_tag(); }
Chris@16: 
Chris@16: 
Chris@16:  // hash_set, hash_map
Chris@16: 
Chris@16:   struct unordered_set_tag :
Chris@16:     virtual public simple_associative_container_tag,
Chris@16:     virtual public unique_associative_container_tag
Chris@16:     { };
Chris@16: 
Chris@16:   struct unordered_multiset_tag :
Chris@16:     virtual public simple_associative_container_tag,
Chris@16:     virtual public multiple_associative_container_tag
Chris@16:     { };
Chris@16: 
Chris@16: 
Chris@16:   struct unordered_map_tag :
Chris@16:     virtual public pair_associative_container_tag,
Chris@16:     virtual public unique_associative_container_tag
Chris@16:     { };
Chris@16: 
Chris@16:   struct unordered_multimap_tag :
Chris@16:     virtual public pair_associative_container_tag,
Chris@16:     virtual public multiple_associative_container_tag
Chris@16:     { };
Chris@16: 
Chris@16: 
Chris@16:   template <class Key, class Eq, class Hash, class Alloc> 
Chris@16:   struct container_traits< boost::unordered_set<Key,Eq,Hash,Alloc> > {
Chris@16:     typedef unordered_set_tag category;
Chris@16:     typedef unstable_tag iterator_stability;
Chris@16:   };
Chris@16:   template <class Key, class T, class Eq, class Hash, class Alloc>
Chris@16:   struct container_traits< boost::unordered_map<Key,T,Eq,Hash,Alloc> > {
Chris@16:     typedef unordered_map_tag category;
Chris@16:     typedef unstable_tag iterator_stability;
Chris@16:   };
Chris@16:   template <class Key, class Eq, class Hash, class Alloc>
Chris@16:   struct container_traits< boost::unordered_multiset<Key,Eq,Hash,Alloc> > {
Chris@16:     typedef unordered_multiset_tag category;
Chris@16:     typedef unstable_tag iterator_stability;
Chris@16:   };
Chris@16:   template <class Key, class T, class Eq, class Hash, class Alloc>
Chris@16:   struct container_traits< boost::unordered_multimap<Key,T,Eq,Hash,Alloc> > {
Chris@16:     typedef unordered_multimap_tag category;
Chris@16:     typedef unstable_tag iterator_stability;
Chris@16:   };
Chris@101: 
Chris@16:   template <class Key, class Eq, class Hash, class Alloc>
Chris@16:   unordered_set_tag
Chris@16:   container_category(const boost::unordered_set<Key,Eq,Hash,Alloc>&)
Chris@16:   { return unordered_set_tag(); }
Chris@16: 
Chris@16:   template <class Key, class T, class Eq, class Hash, class Alloc>
Chris@16:   unordered_map_tag
Chris@16:   container_category(const boost::unordered_map<Key,T,Eq,Hash,Alloc>&)
Chris@16:   { return unordered_map_tag(); }
Chris@16: 
Chris@16:   template <class Key, class Eq, class Hash, class Alloc>
Chris@16:   unstable_tag iterator_stability(const boost::unordered_set<Key,Eq,Hash,Alloc>&)
Chris@16:   { return unstable_tag(); }
Chris@16: 
Chris@16:   template <class Key, class T, class Eq, class Hash, class Alloc>
Chris@16:   unstable_tag iterator_stability(const boost::unordered_map<Key,T,Eq,Hash,Alloc>&)
Chris@16:   { return unstable_tag(); }
Chris@16:   template <class Key, class Eq, class Hash, class Alloc>
Chris@16:   unordered_multiset_tag
Chris@16:   container_category(const boost::unordered_multiset<Key,Eq,Hash,Alloc>&)
Chris@16:   { return unordered_multiset_tag(); }
Chris@16: 
Chris@16:   template <class Key, class T, class Eq, class Hash, class Alloc>
Chris@16:   unordered_multimap_tag
Chris@16:   container_category(const boost::unordered_multimap<Key,T,Eq,Hash,Alloc>&)
Chris@16:   { return unordered_multimap_tag(); }
Chris@16: 
Chris@16:   template <class Key, class Eq, class Hash, class Alloc>
Chris@16:   unstable_tag
Chris@16:   iterator_stability(const boost::unordered_multiset<Key,Eq,Hash,Alloc>&)
Chris@16:   { return unstable_tag(); }
Chris@16: 
Chris@16:   template <class Key, class T, class Eq, class Hash, class Alloc>
Chris@16:   unstable_tag
Chris@16:   iterator_stability(const boost::unordered_multimap<Key,T,Eq,Hash,Alloc>&)
Chris@16:   { return unstable_tag(); }
Chris@101: 
Chris@101: #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
Chris@101:   template <class Key, class Eq, class Hash, class Alloc> 
Chris@101:   struct container_traits< std::unordered_set<Key,Eq,Hash,Alloc> > {
Chris@101:     typedef unordered_set_tag category;
Chris@101:     typedef unstable_tag iterator_stability;
Chris@101:   };
Chris@101: #endif
Chris@101: #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
Chris@101:   template <class Key, class T, class Eq, class Hash, class Alloc>
Chris@101:   struct container_traits< std::unordered_map<Key,T,Eq,Hash,Alloc> > {
Chris@101:     typedef unordered_map_tag category;
Chris@101:     typedef unstable_tag iterator_stability;
Chris@101:   };
Chris@101: #endif
Chris@101: #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
Chris@101:   template <class Key, class Eq, class Hash, class Alloc>
Chris@101:   struct container_traits< std::unordered_multiset<Key,Eq,Hash,Alloc> > {
Chris@101:     typedef unordered_multiset_tag category;
Chris@101:     typedef unstable_tag iterator_stability;
Chris@101:   };
Chris@101: #endif
Chris@101: #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
Chris@101:   template <class Key, class T, class Eq, class Hash, class Alloc>
Chris@101:   struct container_traits< std::unordered_multimap<Key,T,Eq,Hash,Alloc> > {
Chris@101:     typedef unordered_multimap_tag category;
Chris@101:     typedef unstable_tag iterator_stability;
Chris@101:   };
Chris@101: #endif
Chris@101: #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
Chris@101:   template <class Key, class Eq, class Hash, class Alloc>
Chris@101:   unordered_set_tag
Chris@101:   container_category(const std::unordered_set<Key,Eq,Hash,Alloc>&)
Chris@101:   { return unordered_set_tag(); }
Chris@16: #endif
Chris@16: 
Chris@101: #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
Chris@101:   template <class Key, class T, class Eq, class Hash, class Alloc>
Chris@101:   unordered_map_tag
Chris@101:   container_category(const std::unordered_map<Key,T,Eq,Hash,Alloc>&)
Chris@101:   { return unordered_map_tag(); }
Chris@101: #endif
Chris@101: 
Chris@101: #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
Chris@101:   template <class Key, class Eq, class Hash, class Alloc>
Chris@101:   unstable_tag iterator_stability(const std::unordered_set<Key,Eq,Hash,Alloc>&)
Chris@101:   { return unstable_tag(); }
Chris@101: #endif
Chris@101: 
Chris@101: #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
Chris@101:   template <class Key, class T, class Eq, class Hash, class Alloc>
Chris@101:   unstable_tag iterator_stability(const std::unordered_map<Key,T,Eq,Hash,Alloc>&)
Chris@101:   { return unstable_tag(); }
Chris@101: #endif
Chris@101: #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
Chris@101:   template <class Key, class Eq, class Hash, class Alloc>
Chris@101:   unordered_multiset_tag
Chris@101:   container_category(const std::unordered_multiset<Key,Eq,Hash,Alloc>&)
Chris@101:   { return unordered_multiset_tag(); }
Chris@101: #endif
Chris@101: 
Chris@101: #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
Chris@101:   template <class Key, class T, class Eq, class Hash, class Alloc>
Chris@101:   unordered_multimap_tag
Chris@101:   container_category(const std::unordered_multimap<Key,T,Eq,Hash,Alloc>&)
Chris@101:   { return unordered_multimap_tag(); }
Chris@101: #endif
Chris@101: 
Chris@101: #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
Chris@101:   template <class Key, class Eq, class Hash, class Alloc>
Chris@101:   unstable_tag
Chris@101:   iterator_stability(const std::unordered_multiset<Key,Eq,Hash,Alloc>&)
Chris@101:   { return unstable_tag(); }
Chris@101: #endif
Chris@101: 
Chris@101: #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
Chris@101:   template <class Key, class T, class Eq, class Hash, class Alloc>
Chris@101:   unstable_tag
Chris@101:   iterator_stability(const std::unordered_multimap<Key,T,Eq,Hash,Alloc>&)
Chris@101:   { return unstable_tag(); }
Chris@101: #endif
Chris@16: 
Chris@16: 
Chris@16:   //===========================================================================
Chris@16:   // Generalized Container Functions
Chris@16: 
Chris@16: 
Chris@16:   // Erase
Chris@16:   template <class Sequence, class T>
Chris@16:   void erase_dispatch(Sequence& c, const T& x, 
Chris@16:                       sequence_tag)
Chris@16:   {
Chris@16:     c.erase(std::remove(c.begin(), c.end(), x), c.end());
Chris@16:   }
Chris@16: 
Chris@16:   template <class AssociativeContainer, class T>
Chris@16:   void erase_dispatch(AssociativeContainer& c, const T& x, 
Chris@16:                       associative_container_tag)
Chris@16:   {
Chris@16:     c.erase(x);
Chris@16:   }
Chris@16:   template <class Container, class T>
Chris@16:   void erase(Container& c, const T& x)
Chris@16:   {
Chris@16:     erase_dispatch(c, x, container_category(c));
Chris@16:   }
Chris@16: 
Chris@16:   // Erase If
Chris@16:   template <class Sequence, class Predicate, class IteratorStability>
Chris@16:   void erase_if_dispatch(Sequence& c, Predicate p,
Chris@16:                          sequence_tag, IteratorStability)
Chris@16:   {
Chris@16: #if 0
Chris@16:     c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
Chris@16: #else
Chris@16:     if (! c.empty())
Chris@16:       c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
Chris@16: #endif
Chris@16:   }
Chris@16:   template <class AssociativeContainer, class Predicate>
Chris@16:   void erase_if_dispatch(AssociativeContainer& c, Predicate p,
Chris@16:                          associative_container_tag, stable_tag)
Chris@16:   {
Chris@16:     typename AssociativeContainer::iterator i, next;
Chris@16:     for (i = next = c.begin(); next != c.end(); i = next) {
Chris@16:       ++next;
Chris@16:       if (p(*i))
Chris@16:         c.erase(i);
Chris@16:     }
Chris@16:   }
Chris@16:   template <class AssociativeContainer, class Predicate>
Chris@16:   void erase_if_dispatch(AssociativeContainer& c, Predicate p,
Chris@16:                          associative_container_tag, unstable_tag)
Chris@16:   {
Chris@16:     // This method is really slow, so hopefully we won't have any
Chris@16:     // associative containers with unstable iterators!
Chris@16:     // Is there a better way to do this?
Chris@16:     typename AssociativeContainer::iterator i;
Chris@16:     typename AssociativeContainer::size_type n = c.size();
Chris@16:     while (n--)
Chris@16:       for (i = c.begin(); i != c.end(); ++i)
Chris@16:         if (p(*i)) {
Chris@16:           c.erase(i);
Chris@16:           break;
Chris@16:         }
Chris@16:   }
Chris@16:   template <class Container, class Predicate>
Chris@16:   void erase_if(Container& c, Predicate p)
Chris@16:   {
Chris@16:     erase_if_dispatch(c, p, container_category(c), iterator_stability(c));
Chris@16:   }
Chris@16: 
Chris@16:   // Push
Chris@16:   template <class Container, class T>
Chris@16:   std::pair<typename Container::iterator, bool>
Chris@101:   push_dispatch(Container& c, BOOST_PENDING_FWD_TYPE(T) v, back_insertion_sequence_tag)
Chris@16:   {
Chris@101:     c.push_back(BOOST_PENDING_FWD_VALUE(T, v));
Chris@16:     return std::make_pair(boost::prior(c.end()), true);
Chris@16:   }
Chris@16: 
Chris@16:   template <class Container, class T>
Chris@16:   std::pair<typename Container::iterator, bool>
Chris@101:   push_dispatch(Container& c, BOOST_PENDING_FWD_TYPE(T) v, front_insertion_sequence_tag)
Chris@16:   {
Chris@101:     c.push_front(BOOST_PENDING_FWD_VALUE(T, v));
Chris@16:     return std::make_pair(c.begin(), true);
Chris@16:   }
Chris@16: 
Chris@16:   template <class AssociativeContainer, class T>
Chris@16:   std::pair<typename AssociativeContainer::iterator, bool>
Chris@101:   push_dispatch(AssociativeContainer& c, BOOST_PENDING_FWD_TYPE(T) v, 
Chris@16:                 unique_associative_container_tag)
Chris@16:   {
Chris@101:     return c.insert(BOOST_PENDING_FWD_VALUE(T, v));
Chris@16:   }
Chris@16: 
Chris@16:   template <class AssociativeContainer, class T>
Chris@16:   std::pair<typename AssociativeContainer::iterator, bool>
Chris@101:   push_dispatch(AssociativeContainer& c, BOOST_PENDING_FWD_TYPE(T) v,
Chris@16:                 multiple_associative_container_tag)
Chris@16:   {
Chris@101:     return std::make_pair(c.insert(BOOST_PENDING_FWD_VALUE(T, v)), true);
Chris@16:   }
Chris@16: 
Chris@16:   template <class Container, class T>
Chris@16:   std::pair<typename Container::iterator,bool>
Chris@101:   push(Container& c, BOOST_PENDING_FWD_TYPE(T) v)
Chris@16:   {
Chris@101:     return push_dispatch(c, BOOST_PENDING_FWD_VALUE(T, v), container_category(c));
Chris@16:   }
Chris@16: 
Chris@16:   // Find
Chris@16:   template <class Container, class Value>
Chris@16:   typename Container::iterator
Chris@16:   find_dispatch(Container& c,
Chris@16:                 const Value& value,
Chris@16:                 container_tag)
Chris@16:   {
Chris@16:     return std::find(c.begin(), c.end(), value);
Chris@16:   }
Chris@16: 
Chris@16:   template <class AssociativeContainer, class Value>
Chris@16:   typename AssociativeContainer::iterator
Chris@16:   find_dispatch(AssociativeContainer& c,
Chris@16:                 const Value& value,
Chris@16:                 associative_container_tag)
Chris@16:   {
Chris@16:     return c.find(value);
Chris@16:   }
Chris@16: 
Chris@16:   template <class Container, class Value>
Chris@16:   typename Container::iterator
Chris@16:   find(Container& c,
Chris@16:        const Value& value)
Chris@16:   {
Chris@16:     return find_dispatch(c, value,
Chris@16:                          graph_detail::container_category(c));
Chris@16:   }
Chris@16: 
Chris@16:   // Find (const versions)
Chris@16:   template <class Container, class Value>
Chris@16:   typename Container::const_iterator
Chris@16:   find_dispatch(const Container& c,
Chris@16:                 const Value& value,
Chris@16:                 container_tag)
Chris@16:   {
Chris@16:     return std::find(c.begin(), c.end(), value);
Chris@16:   }
Chris@16: 
Chris@16:   template <class AssociativeContainer, class Value>
Chris@16:   typename AssociativeContainer::const_iterator
Chris@16:   find_dispatch(const AssociativeContainer& c,
Chris@16:                 const Value& value,
Chris@16:                 associative_container_tag)
Chris@16:   {
Chris@16:     return c.find(value);
Chris@16:   }
Chris@16: 
Chris@16:   template <class Container, class Value>
Chris@16:   typename Container::const_iterator
Chris@16:   find(const Container& c,
Chris@16:        const Value& value)
Chris@16:   {
Chris@16:     return find_dispatch(c, value,
Chris@16:                          graph_detail::container_category(c));
Chris@16:   }
Chris@16: 
Chris@16:   // Equal range
Chris@16: #if 0
Chris@16:   // Make the dispatch fail if c is not an Associative Container (and thus
Chris@16:   // doesn't have equal_range unless it is sorted, which we cannot check
Chris@16:   // statically and is not typically true for BGL's uses of this function).
Chris@16:   template <class Container,
Chris@16:             class LessThanComparable>
Chris@16:   std::pair<typename Container::iterator, typename Container::iterator>
Chris@16:   equal_range_dispatch(Container& c,
Chris@16:                        const LessThanComparable& value,
Chris@16:                        container_tag)
Chris@16:   {
Chris@16:     // c must be sorted for std::equal_range to behave properly.
Chris@16:     return std::equal_range(c.begin(), c.end(), value);
Chris@16:   }
Chris@16: #endif
Chris@16: 
Chris@16:   template <class AssociativeContainer, class Value>
Chris@16:   std::pair<typename AssociativeContainer::iterator,
Chris@16:             typename AssociativeContainer::iterator>
Chris@16:   equal_range_dispatch(AssociativeContainer& c,
Chris@16:                        const Value& value,
Chris@16:                        associative_container_tag)
Chris@16:   {
Chris@16:     return c.equal_range(value);
Chris@16:   }
Chris@16: 
Chris@16:   template <class Container, class Value>
Chris@16:   std::pair<typename Container::iterator, typename Container::iterator>
Chris@16:   equal_range(Container& c,
Chris@16:               const Value& value)
Chris@16:   {
Chris@16:     return equal_range_dispatch(c, value,
Chris@16:                                 graph_detail::container_category(c));
Chris@16:   }
Chris@16: 
Chris@16: }} // namespace boost::graph_detail
Chris@16: 
Chris@101: #undef BOOST_PENDING_FWD_TYPE
Chris@101: #undef BOOST_PENDING_FWD_VALUE
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H