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