comparison DEPENDENCIES/generic/include/boost/pending/container_traits.hpp @ 16:2665513ce2d3

Add boost headers

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