epoc32/include/stdapis/boost/pending/container_traits.hpp
author William Roberts <williamr@symbian.org>
Tue, 16 Mar 2010 16:12:26 +0000
branchSymbian2
changeset 2 2fe1408b6811
permissions -rw-r--r--
Final list of Symbian^2 public API header files
     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