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