1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/pending/container_traits.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,413 @@
1.4 +// (C) Copyright Jeremy Siek 2004
1.5 +// Distributed under the Boost Software License, Version 1.0. (See
1.6 +// accompanying file LICENSE_1_0.txt or copy at
1.7 +// http://www.boost.org/LICENSE_1_0.txt)
1.8 +
1.9 +#ifndef BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H
1.10 +#define BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H
1.11 +
1.12 +// Sure would be nice to be able to forward declare these
1.13 +// instead of pulling in all the headers. Too bad that
1.14 +// is not legal. There ought to be a standard <stlfwd> header. -JGS
1.15 +
1.16 +#include <boost/next_prior.hpp>
1.17 +
1.18 +#include <algorithm> // for std::remove
1.19 +#include <vector>
1.20 +#include <list>
1.21 +#include <map>
1.22 +#include <set>
1.23 +
1.24 +#if !defined BOOST_NO_HASH
1.25 +# ifdef BOOST_HASH_SET_HEADER
1.26 +# include BOOST_HASH_SET_HEADER
1.27 +# else
1.28 +# include <hash_set>
1.29 +# endif
1.30 +# ifdef BOOST_HASH_MAP_HEADER
1.31 +# include BOOST_HASH_MAP_HEADER
1.32 +# else
1.33 +# include <hash_map>
1.34 +# endif
1.35 +#endif
1.36 +
1.37 +#if !defined BOOST_NO_SLIST
1.38 +# ifdef BOOST_SLIST_HEADER
1.39 +# include BOOST_SLIST_HEADER
1.40 +# else
1.41 +# include <slist>
1.42 +# endif
1.43 +#endif
1.44 +
1.45 +// The content of this file is in 'graph_detail' because otherwise
1.46 +// there will be name clashes with
1.47 +// sandbox/boost/sequence_algo/container_traits.hpp
1.48 +// The 'detail' subnamespace will still cause problems.
1.49 +namespace boost { namespace graph_detail {
1.50 +
1.51 + //======================================================================
1.52 + // Container Category Tags
1.53 + //
1.54 + // They use virtual inheritance because there are lots of
1.55 + // inheritance diamonds.
1.56 +
1.57 + struct container_tag { };
1.58 + struct forward_container_tag : virtual public container_tag { };
1.59 + struct reversible_container_tag : virtual public forward_container_tag { };
1.60 + struct random_access_container_tag
1.61 + : virtual public reversible_container_tag { };
1.62 +
1.63 + struct sequence_tag : virtual public forward_container_tag { };
1.64 +
1.65 + struct associative_container_tag : virtual public forward_container_tag { };
1.66 +
1.67 + struct sorted_associative_container_tag
1.68 + : virtual public associative_container_tag,
1.69 + virtual public reversible_container_tag { };
1.70 +
1.71 + struct front_insertion_sequence_tag : virtual public sequence_tag { };
1.72 + struct back_insertion_sequence_tag : virtual public sequence_tag { };
1.73 +
1.74 + struct unique_associative_container_tag
1.75 + : virtual public associative_container_tag { };
1.76 + struct multiple_associative_container_tag
1.77 + : virtual public associative_container_tag { };
1.78 + struct simple_associative_container_tag
1.79 + : virtual public associative_container_tag { };
1.80 + struct pair_associative_container_tag
1.81 + : virtual public associative_container_tag { };
1.82 +
1.83 +
1.84 + //======================================================================
1.85 + // Iterator Stability Tags
1.86 + //
1.87 + // Do mutating operations such as insert/erase/resize invalidate all
1.88 + // outstanding iterators?
1.89 +
1.90 + struct stable_tag { };
1.91 + struct unstable_tag { };
1.92 +
1.93 + //======================================================================
1.94 + // Container Traits Class and container_category() function
1.95 +
1.96 +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.97 + // don't use this unless there is partial specialization
1.98 + template <class Container>
1.99 + struct container_traits {
1.100 + typedef typename Container::category category;
1.101 + typedef typename Container::iterator_stability iterator_stability;
1.102 + };
1.103 +#endif
1.104 +
1.105 + // Use this as a compile-time assertion that X is stable
1.106 + inline void require_stable(stable_tag) { }
1.107 +
1.108 + // std::vector
1.109 + struct vector_tag :
1.110 + virtual public random_access_container_tag,
1.111 + virtual public back_insertion_sequence_tag { };
1.112 +
1.113 + template <class T, class Alloc>
1.114 + vector_tag container_category(const std::vector<T,Alloc>&)
1.115 + { return vector_tag(); }
1.116 +
1.117 + template <class T, class Alloc>
1.118 + unstable_tag iterator_stability(const std::vector<T,Alloc>&)
1.119 + { return unstable_tag(); }
1.120 +
1.121 +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.122 + template <class T, class Alloc>
1.123 + struct container_traits< std::vector<T,Alloc> > {
1.124 + typedef vector_tag category;
1.125 + typedef unstable_tag iterator_stability;
1.126 + };
1.127 +#endif
1.128 +
1.129 + // std::list
1.130 + struct list_tag :
1.131 + virtual public reversible_container_tag,
1.132 + virtual public back_insertion_sequence_tag
1.133 + // this causes problems for push_dispatch...
1.134 + // virtual public front_insertion_sequence_tag
1.135 + { };
1.136 +
1.137 + template <class T, class Alloc>
1.138 + list_tag container_category(const std::list<T,Alloc>&)
1.139 + { return list_tag(); }
1.140 +
1.141 + template <class T, class Alloc>
1.142 + stable_tag iterator_stability(const std::list<T,Alloc>&)
1.143 + { return stable_tag(); }
1.144 +
1.145 +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.146 + template <class T, class Alloc>
1.147 + struct container_traits< std::list<T,Alloc> > {
1.148 + typedef list_tag category;
1.149 + typedef stable_tag iterator_stability;
1.150 + };
1.151 +#endif
1.152 +
1.153 +
1.154 + // std::slist
1.155 +#ifndef BOOST_NO_SLIST
1.156 +# ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.157 + template <class T, class Alloc>
1.158 + struct container_traits<BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc> > {
1.159 + typedef front_insertion_sequence_tag category;
1.160 + typedef stable_tag iterator_stability;
1.161 + };
1.162 +#endif
1.163 + template <class T, class Alloc>
1.164 + front_insertion_sequence_tag container_category(
1.165 + const BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc>&
1.166 + )
1.167 + { return front_insertion_sequence_tag(); }
1.168 +
1.169 + template <class T, class Alloc>
1.170 + stable_tag iterator_stability(
1.171 + const BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc>&)
1.172 + { return stable_tag(); }
1.173 +#endif
1.174 +
1.175 +
1.176 + // std::set
1.177 + struct set_tag :
1.178 + virtual public sorted_associative_container_tag,
1.179 + virtual public simple_associative_container_tag,
1.180 + virtual public unique_associative_container_tag
1.181 + { };
1.182 +
1.183 + template <class Key, class Cmp, class Alloc>
1.184 + set_tag container_category(const std::set<Key,Cmp,Alloc>&)
1.185 + { return set_tag(); }
1.186 +
1.187 + template <class Key, class Cmp, class Alloc>
1.188 + stable_tag iterator_stability(const std::set<Key,Cmp,Alloc>&)
1.189 + { return stable_tag(); }
1.190 +
1.191 +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.192 + template <class Key, class Cmp, class Alloc>
1.193 + struct container_traits< std::set<Key,Cmp,Alloc> > {
1.194 + typedef set_tag category;
1.195 + typedef stable_tag iterator_stability;
1.196 + };
1.197 +#endif
1.198 +
1.199 + // std::multiset
1.200 + struct multiset_tag :
1.201 + virtual public sorted_associative_container_tag,
1.202 + virtual public simple_associative_container_tag,
1.203 + virtual public multiple_associative_container_tag
1.204 + { };
1.205 +
1.206 + template <class Key, class Cmp, class Alloc>
1.207 + multiset_tag container_category(const std::multiset<Key,Cmp,Alloc>&)
1.208 + { return multiset_tag(); }
1.209 +
1.210 + template <class Key, class Cmp, class Alloc>
1.211 + stable_tag iterator_stability(const std::multiset<Key,Cmp,Alloc>&)
1.212 + { return stable_tag(); }
1.213 +
1.214 +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.215 + template <class Key, class Cmp, class Alloc>
1.216 + struct container_traits< std::multiset<Key,Cmp,Alloc> > {
1.217 + typedef multiset_tag category;
1.218 + typedef stable_tag iterator_stability;
1.219 + };
1.220 +#endif
1.221 +
1.222 + // deque
1.223 +
1.224 + // std::map
1.225 + struct map_tag :
1.226 + virtual public sorted_associative_container_tag,
1.227 + virtual public pair_associative_container_tag,
1.228 + virtual public unique_associative_container_tag
1.229 + { };
1.230 +
1.231 +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.232 + template <class Key, class T, class Cmp, class Alloc>
1.233 + struct container_traits< std::map<Key,T,Cmp,Alloc> > {
1.234 + typedef map_tag category;
1.235 + typedef stable_tag iterator_stability;
1.236 + };
1.237 +#endif
1.238 +
1.239 + template <class Key, class T, class Cmp, class Alloc>
1.240 + map_tag container_category(const std::map<Key,T,Cmp,Alloc>&)
1.241 + { return map_tag(); }
1.242 +
1.243 + template <class Key, class T, class Cmp, class Alloc>
1.244 + stable_tag iterator_stability(const std::map<Key,T,Cmp,Alloc>&)
1.245 + { return stable_tag(); }
1.246 +
1.247 + // std::multimap
1.248 + struct multimap_tag :
1.249 + virtual public sorted_associative_container_tag,
1.250 + virtual public pair_associative_container_tag,
1.251 + virtual public multiple_associative_container_tag
1.252 + { };
1.253 +
1.254 +#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.255 + template <class Key, class T, class Cmp, class Alloc>
1.256 + struct container_traits< std::multimap<Key,T,Cmp,Alloc> > {
1.257 + typedef multimap_tag category;
1.258 + typedef stable_tag iterator_stability;
1.259 + };
1.260 +#endif
1.261 +
1.262 + template <class Key, class T, class Cmp, class Alloc>
1.263 + multimap_tag container_category(const std::multimap<Key,T,Cmp,Alloc>&)
1.264 + { return multimap_tag(); }
1.265 +
1.266 + template <class Key, class T, class Cmp, class Alloc>
1.267 + stable_tag iterator_stability(const std::multimap<Key,T,Cmp,Alloc>&)
1.268 + { return stable_tag(); }
1.269 +
1.270 +
1.271 + // hash_set, hash_map
1.272 +
1.273 +#ifndef BOOST_NO_HASH
1.274 +#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
1.275 + template <class Key, class Eq, class Hash, class Alloc>
1.276 + struct container_traits< BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc> > {
1.277 + typedef set_tag category;
1.278 + typedef stable_tag iterator_stability; // is this right?
1.279 + };
1.280 + template <class Key, class T, class Eq, class Hash, class Alloc>
1.281 + struct container_traits< BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc> > {
1.282 + typedef map_tag category;
1.283 + typedef stable_tag iterator_stability; // is this right?
1.284 + };
1.285 +#endif
1.286 + template <class Key, class Eq, class Hash, class Alloc>
1.287 + set_tag container_category(const BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc>&)
1.288 + { return set_tag(); }
1.289 +
1.290 + template <class Key, class T, class Eq, class Hash, class Alloc>
1.291 + map_tag container_category(const BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc>&)
1.292 + { return map_tag(); }
1.293 +
1.294 + template <class Key, class Eq, class Hash, class Alloc>
1.295 + stable_tag iterator_stability(const BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc>&)
1.296 + { return stable_tag(); }
1.297 +
1.298 + template <class Key, class T, class Eq, class Hash, class Alloc>
1.299 + stable_tag iterator_stability(const BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc>&)
1.300 + { return stable_tag(); }
1.301 +#endif
1.302 +
1.303 +
1.304 +
1.305 + //===========================================================================
1.306 + // Generalized Container Functions
1.307 +
1.308 +
1.309 + // Erase
1.310 + template <class Sequence, class T>
1.311 + void erase_dispatch(Sequence& c, const T& x,
1.312 + sequence_tag)
1.313 + {
1.314 + c.erase(std::remove(c.begin(), c.end(), x), c.end());
1.315 + }
1.316 +
1.317 + template <class AssociativeContainer, class T>
1.318 + void erase_dispatch(AssociativeContainer& c, const T& x,
1.319 + associative_container_tag)
1.320 + {
1.321 + c.erase(x);
1.322 + }
1.323 + template <class Container, class T>
1.324 + void erase(Container& c, const T& x)
1.325 + {
1.326 + erase_dispatch(c, x, container_category(c));
1.327 + }
1.328 +
1.329 + // Erase If
1.330 + template <class Sequence, class Predicate, class IteratorStability>
1.331 + void erase_if_dispatch(Sequence& c, Predicate p,
1.332 + sequence_tag, IteratorStability)
1.333 + {
1.334 +#if 0
1.335 + c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
1.336 +#else
1.337 + if (! c.empty())
1.338 + c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
1.339 +#endif
1.340 + }
1.341 + template <class AssociativeContainer, class Predicate>
1.342 + void erase_if_dispatch(AssociativeContainer& c, Predicate p,
1.343 + associative_container_tag, stable_tag)
1.344 + {
1.345 + typename AssociativeContainer::iterator i, next;
1.346 + for (i = next = c.begin(); next != c.end(); i = next) {
1.347 + ++next;
1.348 + if (p(*i))
1.349 + c.erase(i);
1.350 + }
1.351 + }
1.352 + template <class AssociativeContainer, class Predicate>
1.353 + void erase_if_dispatch(AssociativeContainer& c, Predicate p,
1.354 + associative_container_tag, unstable_tag)
1.355 + {
1.356 + // This method is really slow, so hopefully we won't have any
1.357 + // associative containers with unstable iterators!
1.358 + // Is there a better way to do this?
1.359 + typename AssociativeContainer::iterator i;
1.360 + typename AssociativeContainer::size_type n = c.size();
1.361 + while (n--)
1.362 + for (i = c.begin(); i != c.end(); ++i)
1.363 + if (p(*i)) {
1.364 + c.erase(i);
1.365 + break;
1.366 + }
1.367 + }
1.368 + template <class Container, class Predicate>
1.369 + void erase_if(Container& c, Predicate p)
1.370 + {
1.371 + erase_if_dispatch(c, p, container_category(c), iterator_stability(c));
1.372 + }
1.373 +
1.374 + // Push
1.375 + template <class Container, class T>
1.376 + std::pair<typename Container::iterator, bool>
1.377 + push_dispatch(Container& c, const T& v, back_insertion_sequence_tag)
1.378 + {
1.379 + c.push_back(v);
1.380 + return std::make_pair(boost::prior(c.end()), true);
1.381 + }
1.382 +
1.383 + template <class Container, class T>
1.384 + std::pair<typename Container::iterator, bool>
1.385 + push_dispatch(Container& c, const T& v, front_insertion_sequence_tag)
1.386 + {
1.387 + c.push_front(v);
1.388 + return std::make_pair(c.begin(), true);
1.389 + }
1.390 +
1.391 + template <class AssociativeContainer, class T>
1.392 + std::pair<typename AssociativeContainer::iterator, bool>
1.393 + push_dispatch(AssociativeContainer& c, const T& v,
1.394 + unique_associative_container_tag)
1.395 + {
1.396 + return c.insert(v);
1.397 + }
1.398 +
1.399 + template <class AssociativeContainer, class T>
1.400 + std::pair<typename AssociativeContainer::iterator, bool>
1.401 + push_dispatch(AssociativeContainer& c, const T& v,
1.402 + multiple_associative_container_tag)
1.403 + {
1.404 + return std::make_pair(c.insert(v), true);
1.405 + }
1.406 +
1.407 + template <class Container, class T>
1.408 + std::pair<typename Container::iterator,bool>
1.409 + push(Container& c, const T& v)
1.410 + {
1.411 + return push_dispatch(c, v, container_category(c));
1.412 + }
1.413 +
1.414 +}} // namespace boost::graph_detail
1.415 +
1.416 +#endif // BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H