source: NonGTP/Boost/boost/pending/container_traits.hpp @ 857

Revision 857, 13.0 KB checked in by igarcia, 19 years ago (diff)
RevLine 
[857]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#ifndef BOOST_NO_SLIST
21#  include <slist>
22#endif
23#ifndef BOOST_NO_HASH
24#  include <hash_map>
25#  include <hash_set>
26#endif
27
28// The content of this file is in 'graph_detail' because otherwise
29// there will be name clashes with
30// sandbox/boost/sequence_algo/container_traits.hpp
31// The 'detail' subnamespace will still cause problems.
32namespace boost { namespace graph_detail {
33
34  //======================================================================
35  // Container Category Tags
36  //
37  //   They use virtual inheritance because there are lots of
38  //   inheritance diamonds.
39
40  struct container_tag { };
41  struct forward_container_tag : virtual public container_tag { };
42  struct reversible_container_tag : virtual public forward_container_tag { };
43  struct random_access_container_tag
44    : virtual public reversible_container_tag { };
45 
46  struct sequence_tag : virtual public forward_container_tag { };
47
48  struct associative_container_tag : virtual public forward_container_tag { };
49
50  struct sorted_associative_container_tag
51    : virtual public associative_container_tag,
52      virtual public reversible_container_tag { };
53
54  struct front_insertion_sequence_tag : virtual public sequence_tag { };
55  struct back_insertion_sequence_tag : virtual public sequence_tag { };
56
57  struct unique_associative_container_tag
58    : virtual public associative_container_tag { };
59  struct multiple_associative_container_tag
60    : virtual public associative_container_tag { };
61  struct simple_associative_container_tag
62    : virtual public associative_container_tag { };
63  struct pair_associative_container_tag
64    : virtual public associative_container_tag { };
65
66
67  //======================================================================
68  // Iterator Stability Tags
69  //
70  // Do mutating operations such as insert/erase/resize invalidate all
71  // outstanding iterators?
72
73  struct stable_tag { };
74  struct unstable_tag { };
75
76  //======================================================================
77  // Container Traits Class and container_category() function
78
79#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
80  // don't use this unless there is partial specialization
81  template <class Container>
82  struct container_traits {
83    typedef typename Container::category category;
84    typedef typename Container::iterator_stability iterator_stability;
85  };
86#endif
87
88  // Use this as a compile-time assertion that X is stable
89  inline void require_stable(stable_tag) { }
90
91  // std::vector
92  struct vector_tag :
93    virtual public random_access_container_tag,
94    virtual public back_insertion_sequence_tag { };
95
96  template <class T, class Alloc>
97  vector_tag container_category(const std::vector<T,Alloc>&)
98    { return vector_tag(); }
99
100  template <class T, class Alloc>
101  unstable_tag iterator_stability(const std::vector<T,Alloc>&)
102    { return unstable_tag(); }
103
104#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
105  template <class T, class Alloc>
106  struct container_traits< std::vector<T,Alloc> > {
107    typedef vector_tag category;
108    typedef unstable_tag iterator_stability;
109  };
110#endif
111
112  // std::list
113  struct list_tag :
114    virtual public reversible_container_tag,
115    virtual public back_insertion_sequence_tag
116    // this causes problems for push_dispatch...
117    //    virtual public front_insertion_sequence_tag
118    { };
119
120  template <class T, class Alloc>
121  list_tag container_category(const std::list<T,Alloc>&)
122    { return list_tag(); }
123
124  template <class T, class Alloc>
125  stable_tag iterator_stability(const std::list<T,Alloc>&)
126    { return stable_tag(); }
127
128#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
129  template <class T, class Alloc>
130  struct container_traits< std::list<T,Alloc> > {
131    typedef list_tag category;
132    typedef stable_tag iterator_stability;
133  };
134#endif
135
136
137  // std::slist
138#ifndef BOOST_NO_SLIST
139# ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
140  template <class T, class Alloc>
141  struct container_traits<BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc> > {
142    typedef front_insertion_sequence_tag category;
143    typedef stable_tag iterator_stability;
144  };
145#endif
146  template <class T, class Alloc>
147  front_insertion_sequence_tag container_category(
148  const BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc>&
149  )
150    { return front_insertion_sequence_tag(); }
151
152  template <class T, class Alloc>
153  stable_tag iterator_stability(
154  const BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc>&)
155    { return stable_tag(); }
156#endif
157
158
159  // std::set
160  struct set_tag :
161    virtual public sorted_associative_container_tag,
162    virtual public simple_associative_container_tag,
163    virtual public unique_associative_container_tag
164    { };
165
166  template <class Key, class Cmp, class Alloc>
167  set_tag container_category(const std::set<Key,Cmp,Alloc>&)
168  { return set_tag(); }
169
170  template <class Key, class Cmp, class Alloc>
171  stable_tag iterator_stability(const std::set<Key,Cmp,Alloc>&)
172  { return stable_tag(); }
173
174#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
175  template <class Key, class Cmp, class Alloc>
176  struct container_traits< std::set<Key,Cmp,Alloc> > {
177    typedef set_tag category;
178    typedef stable_tag iterator_stability;
179  };
180#endif
181
182  // std::multiset
183  struct multiset_tag :
184    virtual public sorted_associative_container_tag,
185    virtual public simple_associative_container_tag,
186    virtual public multiple_associative_container_tag
187    { };
188
189  template <class Key, class Cmp, class Alloc>
190  multiset_tag container_category(const std::multiset<Key,Cmp,Alloc>&)
191  { return multiset_tag(); }
192
193  template <class Key, class Cmp, class Alloc>
194  stable_tag iterator_stability(const std::multiset<Key,Cmp,Alloc>&)
195  { return stable_tag(); }
196
197#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
198  template <class Key, class Cmp, class Alloc>
199  struct container_traits< std::multiset<Key,Cmp,Alloc> > {
200    typedef multiset_tag category;
201    typedef stable_tag iterator_stability;
202  };
203#endif
204
205  // deque
206
207  // std::map
208  struct map_tag :
209    virtual public sorted_associative_container_tag,
210    virtual public pair_associative_container_tag,
211    virtual public unique_associative_container_tag
212    { };
213
214#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
215  template <class Key, class T, class Cmp, class Alloc>
216  struct container_traits< std::map<Key,T,Cmp,Alloc> > {
217    typedef map_tag category;
218    typedef stable_tag iterator_stability;
219  };
220#endif
221
222  template <class Key, class T, class Cmp, class Alloc>
223  map_tag container_category(const std::map<Key,T,Cmp,Alloc>&)
224  { return map_tag(); }
225
226  template <class Key, class T, class Cmp, class Alloc>
227  stable_tag iterator_stability(const std::map<Key,T,Cmp,Alloc>&)
228  { return stable_tag(); }
229
230  // std::multimap
231  struct multimap_tag :
232    virtual public sorted_associative_container_tag,
233    virtual public pair_associative_container_tag,
234    virtual public multiple_associative_container_tag
235    { };
236
237#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
238  template <class Key, class T, class Cmp, class Alloc>
239  struct container_traits< std::multimap<Key,T,Cmp,Alloc> > {
240    typedef multimap_tag category;
241    typedef stable_tag iterator_stability;
242  };
243#endif
244
245  template <class Key, class T, class Cmp, class Alloc>
246  multimap_tag container_category(const std::multimap<Key,T,Cmp,Alloc>&)
247  { return multimap_tag(); }
248
249  template <class Key, class T, class Cmp, class Alloc>
250  stable_tag iterator_stability(const std::multimap<Key,T,Cmp,Alloc>&)
251  { return stable_tag(); }
252
253
254 // hash_set, hash_map
255
256#ifndef BOOST_NO_HASH
257#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
258  template <class Key, class Eq, class Hash, class Alloc>
259  struct container_traits< BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc> > {
260    typedef set_tag category;
261    typedef stable_tag iterator_stability; // is this right?
262  };
263  template <class Key, class T, class Eq, class Hash, class Alloc>
264  struct container_traits< BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc> > {
265    typedef map_tag category;
266    typedef stable_tag iterator_stability; // is this right?
267  };
268#endif
269  template <class Key, class Eq, class Hash, class Alloc>
270  set_tag container_category(const BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc>&)
271  { return set_tag(); }
272
273  template <class Key, class T, class Eq, class Hash, class Alloc>
274  map_tag container_category(const BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc>&)
275  { return map_tag(); }
276
277  template <class Key, class Eq, class Hash, class Alloc>
278  stable_tag iterator_stability(const BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc>&)
279  { return stable_tag(); }
280
281  template <class Key, class T, class Eq, class Hash, class Alloc>
282  stable_tag iterator_stability(const BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc>&)
283  { return stable_tag(); }
284#endif
285
286
287
288  //===========================================================================
289  // Generalized Container Functions
290
291
292  // Erase
293  template <class Sequence, class T>
294  void erase_dispatch(Sequence& c, const T& x,
295                      sequence_tag)
296  {
297    c.erase(std::remove(c.begin(), c.end(), x), c.end());
298  }
299
300  template <class AssociativeContainer, class T>
301  void erase_dispatch(AssociativeContainer& c, const T& x,
302                      associative_container_tag)
303  {
304    c.erase(x);
305  }
306  template <class Container, class T>
307  void erase(Container& c, const T& x)
308  {
309    erase_dispatch(c, x, container_category(c));
310  }
311
312  // Erase If
313  template <class Sequence, class Predicate, class IteratorStability>
314  void erase_if_dispatch(Sequence& c, Predicate p,
315                         sequence_tag, IteratorStability)
316  {
317#if 0
318    c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
319#else
320    if (! c.empty())
321      c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
322#endif
323  }
324  template <class AssociativeContainer, class Predicate>
325  void erase_if_dispatch(AssociativeContainer& c, Predicate p,
326                         associative_container_tag, stable_tag)
327  {
328    typename AssociativeContainer::iterator i, next;
329    for (i = next = c.begin(); next != c.end(); i = next) {
330      ++next;
331      if (p(*i))
332        c.erase(i);
333    }
334  }
335  template <class AssociativeContainer, class Predicate>
336  void erase_if_dispatch(AssociativeContainer& c, Predicate p,
337                         associative_container_tag, unstable_tag)
338  {
339    // This method is really slow, so hopefully we won't have any
340    // associative containers with unstable iterators!
341    // Is there a better way to do this?
342    typename AssociativeContainer::iterator i;
343    typename AssociativeContainer::size_type n = c.size();
344    while (n--)
345      for (i = c.begin(); i != c.end(); ++i)
346        if (p(*i)) {
347          c.erase(i);
348          break;
349        }
350  }
351  template <class Container, class Predicate>
352  void erase_if(Container& c, Predicate p)
353  {
354    erase_if_dispatch(c, p, container_category(c), iterator_stability(c));
355  }
356
357  // Push
358  template <class Container, class T>
359  std::pair<typename Container::iterator, bool>
360  push_dispatch(Container& c, const T& v, back_insertion_sequence_tag)
361  {
362    c.push_back(v);
363    return std::make_pair(boost::prior(c.end()), true);
364  }
365
366  template <class Container, class T>
367  std::pair<typename Container::iterator, bool>
368  push_dispatch(Container& c, const T& v, front_insertion_sequence_tag)
369  {
370    c.push_front(v);
371    return std::make_pair(c.begin(), true);
372  }
373
374  template <class AssociativeContainer, class T>
375  std::pair<typename AssociativeContainer::iterator, bool>
376  push_dispatch(AssociativeContainer& c, const T& v,
377                unique_associative_container_tag)
378  {
379    return c.insert(v);
380  }
381
382  template <class AssociativeContainer, class T>
383  std::pair<typename AssociativeContainer::iterator, bool>
384  push_dispatch(AssociativeContainer& c, const T& v,
385                multiple_associative_container_tag)
386  {
387    return std::make_pair(c.insert(v), true);
388  }
389
390  template <class Container, class T>
391  std::pair<typename Container::iterator,bool>
392  push(Container& c, const T& v)
393  {
394    return push_dispatch(c, v, container_category(c));
395  }
396
397}} // namespace boost::graph_detail
398
399#endif // BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H
Note: See TracBrowser for help on using the repository browser.