1 //  (C) Copyright Jeremy Siek 2004 

     2 //  Distributed under the Boost Software License, Version 1.0. (See

     3 //  accompanying file LICENSE_1_0.txt or copy at

     4 //  http://www.boost.org/LICENSE_1_0.txt)

     5 

     6 #ifndef BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H

     7 #define BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H

     8 

     9 // Sure would be nice to be able to forward declare these

    10 // instead of pulling in all the headers. Too bad that

    11 // is not legal. There ought to be a standard <stlfwd> header. -JGS 

    12 

    13 #include <boost/next_prior.hpp>

    14 

    15 #include <algorithm>   // for std::remove

    16 #include <vector>

    17 #include <list>

    18 #include <map>

    19 #include <set>

    20 

    21 #if !defined BOOST_NO_HASH

    22 #  ifdef BOOST_HASH_SET_HEADER

    23 #    include BOOST_HASH_SET_HEADER

    24 #  else

    25 #    include <hash_set>

    26 #  endif

    27 #  ifdef BOOST_HASH_MAP_HEADER

    28 #    include BOOST_HASH_MAP_HEADER

    29 #  else

    30 #    include <hash_map>

    31 #  endif

    32 #endif

    33 

    34 #if !defined BOOST_NO_SLIST

    35 #  ifdef BOOST_SLIST_HEADER

    36 #    include BOOST_SLIST_HEADER

    37 #  else

    38 #    include <slist>

    39 #  endif

    40 #endif

    41 

    42 // The content of this file is in 'graph_detail' because otherwise

    43 // there will be name clashes with 

    44 // sandbox/boost/sequence_algo/container_traits.hpp

    45 // The 'detail' subnamespace will still cause problems.

    46 namespace boost { namespace graph_detail {

    47 

    48   //======================================================================

    49   // Container Category Tags

    50   //

    51   //   They use virtual inheritance because there are lots of

    52   //   inheritance diamonds.

    53 

    54   struct container_tag { };

    55   struct forward_container_tag : virtual public container_tag { };

    56   struct reversible_container_tag : virtual public forward_container_tag { };

    57   struct random_access_container_tag

    58     : virtual public reversible_container_tag { };

    59   

    60   struct sequence_tag : virtual public forward_container_tag { };

    61 

    62   struct associative_container_tag : virtual public forward_container_tag { };

    63 

    64   struct sorted_associative_container_tag 

    65     : virtual public associative_container_tag,

    66       virtual public reversible_container_tag { };

    67 

    68   struct front_insertion_sequence_tag : virtual public sequence_tag { };

    69   struct back_insertion_sequence_tag : virtual public sequence_tag { };

    70 

    71   struct unique_associative_container_tag 

    72     : virtual public associative_container_tag { };

    73   struct multiple_associative_container_tag 

    74     : virtual public associative_container_tag { };

    75   struct simple_associative_container_tag 

    76     : virtual public associative_container_tag { };

    77   struct pair_associative_container_tag 

    78     : virtual public associative_container_tag { };

    79 

    80 

    81   //======================================================================

    82   // Iterator Stability Tags

    83   //

    84   // Do mutating operations such as insert/erase/resize invalidate all

    85   // outstanding iterators?

    86 

    87   struct stable_tag { };

    88   struct unstable_tag { };

    89 

    90   //======================================================================

    91   // Container Traits Class and container_category() function

    92 

    93 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

    94   // don't use this unless there is partial specialization 

    95   template <class Container>

    96   struct container_traits {

    97     typedef typename Container::category category;

    98     typedef typename Container::iterator_stability iterator_stability;

    99   };

   100 #endif

   101 

   102   // Use this as a compile-time assertion that X is stable

   103   inline void require_stable(stable_tag) { }

   104 

   105   // std::vector

   106   struct vector_tag :

   107     virtual public random_access_container_tag,

   108     virtual public back_insertion_sequence_tag { };

   109 

   110   template <class T, class Alloc>

   111   vector_tag container_category(const std::vector<T,Alloc>&)

   112     { return vector_tag(); }

   113 

   114   template <class T, class Alloc>

   115   unstable_tag iterator_stability(const std::vector<T,Alloc>&)

   116     { return unstable_tag(); }

   117 

   118 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

   119   template <class T, class Alloc>

   120   struct container_traits< std::vector<T,Alloc> > {

   121     typedef vector_tag category;

   122     typedef unstable_tag iterator_stability;

   123   };

   124 #endif

   125 

   126   // std::list

   127   struct list_tag :

   128     virtual public reversible_container_tag,

   129     virtual public back_insertion_sequence_tag

   130     // this causes problems for push_dispatch...

   131     //    virtual public front_insertion_sequence_tag

   132     { };

   133 

   134   template <class T, class Alloc>

   135   list_tag container_category(const std::list<T,Alloc>&)

   136     { return list_tag(); }

   137 

   138   template <class T, class Alloc>

   139   stable_tag iterator_stability(const std::list<T,Alloc>&)

   140     { return stable_tag(); }

   141 

   142 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

   143   template <class T, class Alloc>

   144   struct container_traits< std::list<T,Alloc> > {

   145     typedef list_tag category;

   146     typedef stable_tag iterator_stability;

   147   };

   148 #endif

   149 

   150 

   151   // std::slist

   152 #ifndef BOOST_NO_SLIST

   153 # ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

   154   template <class T, class Alloc>

   155   struct container_traits<BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc> > {

   156     typedef front_insertion_sequence_tag category;

   157     typedef stable_tag iterator_stability;

   158   };

   159 #endif

   160   template <class T, class Alloc>

   161   front_insertion_sequence_tag container_category(

   162   const BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc>&

   163   )

   164     { return front_insertion_sequence_tag(); }

   165 

   166   template <class T, class Alloc>

   167   stable_tag iterator_stability(

   168   const BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc>&)

   169     { return stable_tag(); }

   170 #endif

   171 

   172 

   173   // std::set

   174   struct set_tag :

   175     virtual public sorted_associative_container_tag,

   176     virtual public simple_associative_container_tag,

   177     virtual public unique_associative_container_tag 

   178     { };

   179 

   180   template <class Key, class Cmp, class Alloc> 

   181   set_tag container_category(const std::set<Key,Cmp,Alloc>&)

   182   { return set_tag(); }

   183 

   184   template <class Key, class Cmp, class Alloc> 

   185   stable_tag iterator_stability(const std::set<Key,Cmp,Alloc>&)

   186   { return stable_tag(); }

   187 

   188 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

   189   template <class Key, class Cmp, class Alloc> 

   190   struct container_traits< std::set<Key,Cmp,Alloc> > {

   191     typedef set_tag category;

   192     typedef stable_tag iterator_stability;

   193   };

   194 #endif

   195 

   196   // std::multiset

   197   struct multiset_tag :

   198     virtual public sorted_associative_container_tag,

   199     virtual public simple_associative_container_tag,

   200     virtual public multiple_associative_container_tag 

   201     { };

   202 

   203   template <class Key, class Cmp, class Alloc> 

   204   multiset_tag container_category(const std::multiset<Key,Cmp,Alloc>&)

   205   { return multiset_tag(); }

   206 

   207   template <class Key, class Cmp, class Alloc> 

   208   stable_tag iterator_stability(const std::multiset<Key,Cmp,Alloc>&)

   209   { return stable_tag(); }

   210 

   211 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

   212   template <class Key, class Cmp, class Alloc> 

   213   struct container_traits< std::multiset<Key,Cmp,Alloc> > {

   214     typedef multiset_tag category;

   215     typedef stable_tag iterator_stability;

   216   };

   217 #endif

   218 

   219   // deque

   220 

   221   // std::map

   222   struct map_tag :

   223     virtual public sorted_associative_container_tag,

   224     virtual public pair_associative_container_tag,

   225     virtual public unique_associative_container_tag 

   226     { };

   227 

   228 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

   229   template <class Key, class T, class Cmp, class Alloc> 

   230   struct container_traits< std::map<Key,T,Cmp,Alloc> > {

   231     typedef map_tag category;

   232     typedef stable_tag iterator_stability;

   233   };

   234 #endif

   235 

   236   template <class Key, class T, class Cmp, class Alloc> 

   237   map_tag container_category(const std::map<Key,T,Cmp,Alloc>&)

   238   { return map_tag(); }

   239 

   240   template <class Key, class T, class Cmp, class Alloc> 

   241   stable_tag iterator_stability(const std::map<Key,T,Cmp,Alloc>&)

   242   { return stable_tag(); }

   243 

   244   // std::multimap

   245   struct multimap_tag :

   246     virtual public sorted_associative_container_tag,

   247     virtual public pair_associative_container_tag,

   248     virtual public multiple_associative_container_tag 

   249     { };

   250 

   251 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

   252   template <class Key, class T, class Cmp, class Alloc> 

   253   struct container_traits< std::multimap<Key,T,Cmp,Alloc> > {

   254     typedef multimap_tag category;

   255     typedef stable_tag iterator_stability;

   256   };

   257 #endif

   258 

   259   template <class Key, class T, class Cmp, class Alloc> 

   260   multimap_tag container_category(const std::multimap<Key,T,Cmp,Alloc>&)

   261   { return multimap_tag(); }

   262 

   263   template <class Key, class T, class Cmp, class Alloc> 

   264   stable_tag iterator_stability(const std::multimap<Key,T,Cmp,Alloc>&)

   265   { return stable_tag(); }

   266 

   267 

   268  // hash_set, hash_map

   269 

   270 #ifndef BOOST_NO_HASH

   271 #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

   272   template <class Key, class Eq, class Hash, class Alloc> 

   273   struct container_traits< BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc> > {

   274     typedef set_tag category;

   275     typedef stable_tag iterator_stability; // is this right?

   276   };

   277   template <class Key, class T, class Eq, class Hash, class Alloc>

   278   struct container_traits< BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc> > {

   279     typedef map_tag category;

   280     typedef stable_tag iterator_stability; // is this right?

   281   };

   282 #endif

   283   template <class Key, class Eq, class Hash, class Alloc>

   284   set_tag container_category(const BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc>&)

   285   { return set_tag(); }

   286 

   287   template <class Key, class T, class Eq, class Hash, class Alloc>

   288   map_tag container_category(const BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc>&)

   289   { return map_tag(); }

   290 

   291   template <class Key, class Eq, class Hash, class Alloc>

   292   stable_tag iterator_stability(const BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc>&)

   293   { return stable_tag(); }

   294 

   295   template <class Key, class T, class Eq, class Hash, class Alloc>

   296   stable_tag iterator_stability(const BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc>&)

   297   { return stable_tag(); }

   298 #endif

   299 

   300 

   301 

   302   //===========================================================================

   303   // Generalized Container Functions

   304 

   305 

   306   // Erase

   307   template <class Sequence, class T>

   308   void erase_dispatch(Sequence& c, const T& x, 

   309                       sequence_tag)

   310   {

   311     c.erase(std::remove(c.begin(), c.end(), x), c.end());

   312   }

   313 

   314   template <class AssociativeContainer, class T>

   315   void erase_dispatch(AssociativeContainer& c, const T& x, 

   316                       associative_container_tag)

   317   {

   318     c.erase(x);

   319   }

   320   template <class Container, class T>

   321   void erase(Container& c, const T& x)

   322   {

   323     erase_dispatch(c, x, container_category(c));

   324   }

   325 

   326   // Erase If

   327   template <class Sequence, class Predicate, class IteratorStability>

   328   void erase_if_dispatch(Sequence& c, Predicate p,

   329                          sequence_tag, IteratorStability)

   330   {

   331 #if 0

   332     c.erase(std::remove_if(c.begin(), c.end(), p), c.end());

   333 #else

   334     if (! c.empty())

   335       c.erase(std::remove_if(c.begin(), c.end(), p), c.end());

   336 #endif

   337   }

   338   template <class AssociativeContainer, class Predicate>

   339   void erase_if_dispatch(AssociativeContainer& c, Predicate p,

   340                          associative_container_tag, stable_tag)

   341   {

   342     typename AssociativeContainer::iterator i, next;

   343     for (i = next = c.begin(); next != c.end(); i = next) {

   344       ++next;

   345       if (p(*i))

   346         c.erase(i);

   347     }

   348   }

   349   template <class AssociativeContainer, class Predicate>

   350   void erase_if_dispatch(AssociativeContainer& c, Predicate p,

   351                          associative_container_tag, unstable_tag)

   352   {

   353     // This method is really slow, so hopefully we won't have any

   354     // associative containers with unstable iterators!

   355     // Is there a better way to do this?

   356     typename AssociativeContainer::iterator i;

   357     typename AssociativeContainer::size_type n = c.size();

   358     while (n--)

   359       for (i = c.begin(); i != c.end(); ++i)

   360         if (p(*i)) {

   361           c.erase(i);

   362           break;

   363         }

   364   }

   365   template <class Container, class Predicate>

   366   void erase_if(Container& c, Predicate p)

   367   {

   368     erase_if_dispatch(c, p, container_category(c), iterator_stability(c));

   369   }

   370 

   371   // Push

   372   template <class Container, class T>

   373   std::pair<typename Container::iterator, bool>

   374   push_dispatch(Container& c, const T& v, back_insertion_sequence_tag)

   375   {

   376     c.push_back(v);

   377     return std::make_pair(boost::prior(c.end()), true);

   378   }

   379 

   380   template <class Container, class T>

   381   std::pair<typename Container::iterator, bool>

   382   push_dispatch(Container& c, const T& v, front_insertion_sequence_tag)

   383   {

   384     c.push_front(v);

   385     return std::make_pair(c.begin(), true);

   386   }

   387 

   388   template <class AssociativeContainer, class T>

   389   std::pair<typename AssociativeContainer::iterator, bool>

   390   push_dispatch(AssociativeContainer& c, const T& v, 

   391                 unique_associative_container_tag)

   392   {

   393     return c.insert(v);

   394   }

   395 

   396   template <class AssociativeContainer, class T>

   397   std::pair<typename AssociativeContainer::iterator, bool>

   398   push_dispatch(AssociativeContainer& c, const T& v,

   399                 multiple_associative_container_tag)

   400   {

   401     return std::make_pair(c.insert(v), true);

   402   }

   403 

   404   template <class Container, class T>

   405   std::pair<typename Container::iterator,bool>

   406   push(Container& c, const T& v)

   407   {

   408     return push_dispatch(c, v, container_category(c));

   409   }

   410 

   411 }} // namespace boost::graph_detail

   412 

   413 #endif // BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H