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