Mercurial > hg > vamp-build-and-test

comparison DEPENDENCIES/generic/include/boost/intrusive/rbtree.hpp @ 16:2665513ce2d3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add boost headers
author Chris Cannam
date Tue, 05 Aug 2014 11:11:38 +0100
parents
children c530137014c0
comparison
equal deleted inserted replaced
15:663ca0da4350 16:2665513ce2d3
1 /////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2006-2013
4 //
5 // Distributed under the Boost Software License, Version 1.0.
6 // (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //
9 // See http://www.boost.org/libs/intrusive for documentation.
10 //
11 /////////////////////////////////////////////////////////////////////////////
12 #ifndef BOOST_INTRUSIVE_RBTREE_HPP
13 #define BOOST_INTRUSIVE_RBTREE_HPP
14
15 #include <boost/intrusive/detail/config_begin.hpp>
16 #include <cstddef>
17 #include <functional>
18 #include <utility>
19
20 #include <boost/intrusive/detail/assert.hpp>
21 #include <boost/static_assert.hpp>
22 #include <boost/intrusive/intrusive_fwd.hpp>
23 #include <boost/intrusive/set_hook.hpp>
24 #include <boost/intrusive/detail/rbtree_node.hpp>
25 #include <boost/intrusive/bstree.hpp>
26 #include <boost/intrusive/detail/tree_node.hpp>
27 #include <boost/intrusive/detail/ebo_functor_holder.hpp>
28 #include <boost/intrusive/detail/mpl.hpp>
29 #include <boost/intrusive/pointer_traits.hpp>
30 #include <boost/intrusive/detail/function_detector.hpp>
31 #include <boost/intrusive/detail/utilities.hpp>
32 #include <boost/intrusive/options.hpp>
33 #include <boost/intrusive/rbtree_algorithms.hpp>
34 #include <boost/intrusive/link_mode.hpp>
35 #include <boost/move/move.hpp>
36
37 namespace boost {
38 namespace intrusive {
39
40 /// @cond
41
42 struct rbtree_defaults
43 {
44 typedef detail::default_rbtree_hook proto_value_traits;
45 static const bool constant_time_size = true;
46 typedef std::size_t size_type;
47 typedef void compare;
48 };
49
50 /// @endcond
51
52 //! The class template rbtree is an intrusive red-black tree container, that
53 //! is used to construct intrusive set and multiset containers. The no-throw
54 //! guarantee holds only, if the value_compare object
55 //! doesn't throw.
56 //!
57 //! The template parameter \c T is the type to be managed by the container.
58 //! The user can specify additional options and if no options are provided
59 //! default options are used.
60 //!
61 //! The container supports the following options:
62 //! \c base_hook<>/member_hook<>/value_traits<>,
63 //! \c constant_time_size<>, \c size_type<> and
64 //! \c compare<>.
65 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
66 template<class T, class ...Options>
67 #else
68 template<class ValueTraits, class VoidOrKeyComp, class SizeType, bool ConstantTimeSize>
69 #endif
70 class rbtree_impl
71 /// @cond
72 : public bstree_impl<ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, RbTreeAlgorithms>
73 /// @endcond
74 {
75 public:
76 typedef ValueTraits value_traits;
77 /// @cond
78 typedef bstree_impl< ValueTraits, VoidOrKeyComp, SizeType
79 , ConstantTimeSize, RbTreeAlgorithms> tree_type;
80 typedef tree_type implementation_defined;
81 /// @endcond
82
83 typedef typename implementation_defined::pointer pointer;
84 typedef typename implementation_defined::const_pointer const_pointer;
85 typedef typename implementation_defined::value_type value_type;
86 typedef typename implementation_defined::key_type key_type;
87 typedef typename implementation_defined::reference reference;
88 typedef typename implementation_defined::const_reference const_reference;
89 typedef typename implementation_defined::difference_type difference_type;
90 typedef typename implementation_defined::size_type size_type;
91 typedef typename implementation_defined::value_compare value_compare;
92 typedef typename implementation_defined::key_compare key_compare;
93 typedef typename implementation_defined::iterator iterator;
94 typedef typename implementation_defined::const_iterator const_iterator;
95 typedef typename implementation_defined::reverse_iterator reverse_iterator;
96 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator;
97 typedef typename implementation_defined::node_traits node_traits;
98 typedef typename implementation_defined::node node;
99 typedef typename implementation_defined::node_ptr node_ptr;
100 typedef typename implementation_defined::const_node_ptr const_node_ptr;
101 typedef typename implementation_defined::node_algorithms node_algorithms;
102
103 static const bool constant_time_size = implementation_defined::constant_time_size;
104 /// @cond
105 private:
106
107 //noncopyable
108 BOOST_MOVABLE_BUT_NOT_COPYABLE(rbtree_impl)
109
110 /// @endcond
111
112 public:
113
114 typedef typename implementation_defined::insert_commit_data insert_commit_data;
115
116 //! @copydoc ::boost::intrusive::bstree::bstree(const value_compare &,const value_traits &)
117 explicit rbtree_impl( const value_compare &cmp = value_compare()
118 , const value_traits &v_traits = value_traits())
119 : tree_type(cmp, v_traits)
120 {}
121
122 //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const value_compare &,const value_traits &)
123 template<class Iterator>
124 rbtree_impl( bool unique, Iterator b, Iterator e
125 , const value_compare &cmp = value_compare()
126 , const value_traits &v_traits = value_traits())
127 : tree_type(unique, b, e, cmp, v_traits)
128 {}
129
130 //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&)
131 rbtree_impl(BOOST_RV_REF(rbtree_impl) x)
132 : tree_type(::boost::move(static_cast<tree_type&>(x)))
133 {}
134
135 //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&)
136 rbtree_impl& operator=(BOOST_RV_REF(rbtree_impl) x)
137 { return static_cast<rbtree_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); }
138
139 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
140 //! @copydoc ::boost::intrusive::bstree::~bstree()
141 ~rbtree_impl();
142
143 //! @copydoc ::boost::intrusive::bstree::begin()
144 iterator begin();
145
146 //! @copydoc ::boost::intrusive::bstree::begin()const
147 const_iterator begin() const;
148
149 //! @copydoc ::boost::intrusive::bstree::cbegin()const
150 const_iterator cbegin() const;
151
152 //! @copydoc ::boost::intrusive::bstree::end()
153 iterator end();
154
155 //! @copydoc ::boost::intrusive::bstree::end()const
156 const_iterator end() const;
157
158 //! @copydoc ::boost::intrusive::bstree::cend()const
159 const_iterator cend() const;
160
161 //! @copydoc ::boost::intrusive::bstree::rbegin()
162 reverse_iterator rbegin();
163
164 //! @copydoc ::boost::intrusive::bstree::rbegin()const
165 const_reverse_iterator rbegin() const;
166
167 //! @copydoc ::boost::intrusive::bstree::crbegin()const
168 const_reverse_iterator crbegin() const;
169
170 //! @copydoc ::boost::intrusive::bstree::rend()
171 reverse_iterator rend();
172
173 //! @copydoc ::boost::intrusive::bstree::rend()const
174 const_reverse_iterator rend() const;
175
176 //! @copydoc ::boost::intrusive::bstree::crend()const
177 const_reverse_iterator crend() const;
178
179 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
180 static rbtree_impl &container_from_end_iterator(iterator end_iterator);
181
182 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator)
183 static const rbtree_impl &container_from_end_iterator(const_iterator end_iterator);
184
185 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator)
186 static rbtree_impl &container_from_iterator(iterator it);
187
188 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator)
189 static const rbtree_impl &container_from_iterator(const_iterator it);
190
191 //! @copydoc ::boost::intrusive::bstree::key_comp()const
192 key_compare key_comp() const;
193
194 //! @copydoc ::boost::intrusive::bstree::value_comp()const
195 value_compare value_comp() const;
196
197 //! @copydoc ::boost::intrusive::bstree::empty()const
198 bool empty() const;
199
200 //! @copydoc ::boost::intrusive::bstree::size()const
201 size_type size() const;
202
203 //! @copydoc ::boost::intrusive::bstree::swap
204 void swap(rbtree_impl& other);
205
206 //! @copydoc ::boost::intrusive::bstree::clone_from
207 template <class Cloner, class Disposer>
208 void clone_from(const rbtree_impl &src, Cloner cloner, Disposer disposer);
209
210 //! @copydoc ::boost::intrusive::bstree::insert_equal(reference)
211 iterator insert_equal(reference value);
212
213 //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference)
214 iterator insert_equal(const_iterator hint, reference value);
215
216 //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator)
217 template<class Iterator>
218 void insert_equal(Iterator b, Iterator e);
219
220 //! @copydoc ::boost::intrusive::bstree::insert_unique(reference)
221 std::pair<iterator, bool> insert_unique(reference value);
222
223 //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference)
224 iterator insert_unique(const_iterator hint, reference value);
225
226 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyValueCompare,insert_commit_data&)
227 template<class KeyType, class KeyValueCompare>
228 std::pair<iterator, bool> insert_unique_check
229 (const KeyType &key, KeyValueCompare key_value_comp, insert_commit_data &commit_data);
230
231 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyValueCompare,insert_commit_data&)
232 template<class KeyType, class KeyValueCompare>
233 std::pair<iterator, bool> insert_unique_check
234 (const_iterator hint, const KeyType &key
235 ,KeyValueCompare key_value_comp, insert_commit_data &commit_data);
236
237 //! @copydoc ::boost::intrusive::bstree::insert_unique_commit
238 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data);
239
240 //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator)
241 template<class Iterator>
242 void insert_unique(Iterator b, Iterator e);
243
244 //! @copydoc ::boost::intrusive::bstree::insert_before
245 iterator insert_before(const_iterator pos, reference value);
246
247 //! @copydoc ::boost::intrusive::bstree::push_back
248 void push_back(reference value);
249
250 //! @copydoc ::boost::intrusive::bstree::push_front
251 void push_front(reference value);
252
253 //! @copydoc ::boost::intrusive::bstree::erase(const_iterator)
254 iterator erase(const_iterator i);
255
256 //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator)
257 iterator erase(const_iterator b, const_iterator e);
258
259 //! @copydoc ::boost::intrusive::bstree::erase(const_reference)
260 size_type erase(const_reference value);
261
262 //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyValueCompare)
263 template<class KeyType, class KeyValueCompare>
264 size_type erase(const KeyType& key, KeyValueCompare comp);
265
266 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer)
267 template<class Disposer>
268 iterator erase_and_dispose(const_iterator i, Disposer disposer);
269
270 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer)
271 template<class Disposer>
272 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer);
273
274 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_reference, Disposer)
275 template<class Disposer>
276 size_type erase_and_dispose(const_reference value, Disposer disposer);
277
278 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyValueCompare,Disposer)
279 template<class KeyType, class KeyValueCompare, class Disposer>
280 size_type erase_and_dispose(const KeyType& key, KeyValueCompare comp, Disposer disposer);
281
282 //! @copydoc ::boost::intrusive::bstree::clear
283 void clear();
284
285 //! @copydoc ::boost::intrusive::bstree::clear_and_dispose
286 template<class Disposer>
287 void clear_and_dispose(Disposer disposer);
288
289 //! @copydoc ::boost::intrusive::bstree::count(const_reference)const
290 size_type count(const_reference value) const;
291
292 //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyValueCompare)const
293 template<class KeyType, class KeyValueCompare>
294 size_type count(const KeyType& key, KeyValueCompare comp) const;
295
296 //! @copydoc ::boost::intrusive::bstree::lower_bound(const_reference)
297 iterator lower_bound(const_reference value);
298
299 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyValueCompare)
300 template<class KeyType, class KeyValueCompare>
301 iterator lower_bound(const KeyType& key, KeyValueCompare comp);
302
303 //! @copydoc ::boost::intrusive::bstree::lower_bound(const_reference)const
304 const_iterator lower_bound(const_reference value) const;
305
306 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyValueCompare)const
307 template<class KeyType, class KeyValueCompare>
308 const_iterator lower_bound(const KeyType& key, KeyValueCompare comp) const;
309
310 //! @copydoc ::boost::intrusive::bstree::upper_bound(const_reference)
311 iterator upper_bound(const_reference value);
312
313 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyValueCompare)
314 template<class KeyType, class KeyValueCompare>
315 iterator upper_bound(const KeyType& key, KeyValueCompare comp);
316
317 //! @copydoc ::boost::intrusive::bstree::upper_bound(const_reference)const
318 const_iterator upper_bound(const_reference value) const;
319
320 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyValueCompare)const
321 template<class KeyType, class KeyValueCompare>
322 const_iterator upper_bound(const KeyType& key, KeyValueCompare comp) const;
323
324 //! @copydoc ::boost::intrusive::bstree::find(const_reference)
325 iterator find(const_reference value);
326
327 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyValueCompare)
328 template<class KeyType, class KeyValueCompare>
329 iterator find(const KeyType& key, KeyValueCompare comp);
330
331 //! @copydoc ::boost::intrusive::bstree::find(const_reference)const
332 const_iterator find(const_reference value) const;
333
334 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyValueCompare)const
335 template<class KeyType, class KeyValueCompare>
336 const_iterator find(const KeyType& key, KeyValueCompare comp) const;
337
338 //! @copydoc ::boost::intrusive::bstree::equal_range(const_reference)
339 std::pair<iterator,iterator> equal_range(const_reference value);
340
341 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyValueCompare)
342 template<class KeyType, class KeyValueCompare>
343 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyValueCompare comp);
344
345 //! @copydoc ::boost::intrusive::bstree::equal_range(const_reference)const
346 std::pair<const_iterator, const_iterator>
347 equal_range(const_reference value) const;
348
349 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyValueCompare)const
350 template<class KeyType, class KeyValueCompare>
351 std::pair<const_iterator, const_iterator>
352 equal_range(const KeyType& key, KeyValueCompare comp) const;
353
354 //! @copydoc ::boost::intrusive::bstree::bounded_range(const_reference,const_reference,bool,bool)
355 std::pair<iterator,iterator> bounded_range
356 (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed);
357
358 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyValueCompare,bool,bool)
359 template<class KeyType, class KeyValueCompare>
360 std::pair<iterator,iterator> bounded_range
361 (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed);
362
363 //! @copydoc ::boost::intrusive::bstree::bounded_range(const_reference,const_reference,bool,bool)const
364 std::pair<const_iterator, const_iterator>
365 bounded_range(const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const;
366
367 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyValueCompare,bool,bool)const
368 template<class KeyType, class KeyValueCompare>
369 std::pair<const_iterator, const_iterator> bounded_range
370 (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const;
371
372 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference)
373 static iterator s_iterator_to(reference value);
374
375 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference)
376 static const_iterator s_iterator_to(const_reference value);
377
378 //! @copydoc ::boost::intrusive::bstree::iterator_to(reference)
379 iterator iterator_to(reference value);
380
381 //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const
382 const_iterator iterator_to(const_reference value) const;
383
384 //! @copydoc ::boost::intrusive::bstree::init_node(reference)
385 static void init_node(reference value);
386
387 //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance
388 pointer unlink_leftmost_without_rebalance();
389
390 //! @copydoc ::boost::intrusive::bstree::replace_node
391 void replace_node(iterator replace_this, reference with_this);
392
393 //! @copydoc ::boost::intrusive::bstree::remove_node
394 void remove_node(reference value);
395 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
396 };
397
398 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
399
400 template<class T, class ...Options>
401 bool operator< (const rbtree_impl<T, Options...> &x, const rbtree_impl<T, Options...> &y);
402
403 template<class T, class ...Options>
404 bool operator==(const rbtree_impl<T, Options...> &x, const rbtree_impl<T, Options...> &y);
405
406 template<class T, class ...Options>
407 bool operator!= (const rbtree_impl<T, Options...> &x, const rbtree_impl<T, Options...> &y);
408
409 template<class T, class ...Options>
410 bool operator>(const rbtree_impl<T, Options...> &x, const rbtree_impl<T, Options...> &y);
411
412 template<class T, class ...Options>
413 bool operator<=(const rbtree_impl<T, Options...> &x, const rbtree_impl<T, Options...> &y);
414
415 template<class T, class ...Options>
416 bool operator>=(const rbtree_impl<T, Options...> &x, const rbtree_impl<T, Options...> &y);
417
418 template<class T, class ...Options>
419 void swap(rbtree_impl<T, Options...> &x, rbtree_impl<T, Options...> &y);
420
421 #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
422
423 //! Helper metafunction to define a \c rbtree that yields to the same type when the
424 //! same options (either explicitly or implicitly) are used.
425 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
426 template<class T, class ...Options>
427 #else
428 template<class T, class O1 = void, class O2 = void
429 , class O3 = void, class O4 = void>
430 #endif
431 struct make_rbtree
432 {
433 /// @cond
434 typedef typename pack_options
435 < rbtree_defaults,
436 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
437 O1, O2, O3, O4
438 #else
439 Options...
440 #endif
441 >::type packed_options;
442
443 typedef typename detail::get_value_traits
444 <T, typename packed_options::proto_value_traits>::type value_traits;
445
446 typedef rbtree_impl
447 < value_traits
448 , typename packed_options::compare
449 , typename packed_options::size_type
450 , packed_options::constant_time_size
451 > implementation_defined;
452 /// @endcond
453 typedef implementation_defined type;
454 };
455
456
457 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
458
459 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
460 template<class T, class O1, class O2, class O3, class O4>
461 #else
462 template<class T, class ...Options>
463 #endif
464 class rbtree
465 : public make_rbtree<T,
466 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
467 O1, O2, O3, O4
468 #else
469 Options...
470 #endif
471 >::type
472 {
473 typedef typename make_rbtree
474 <T,
475 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
476 O1, O2, O3, O4
477 #else
478 Options...
479 #endif
480 >::type Base;
481 BOOST_MOVABLE_BUT_NOT_COPYABLE(rbtree)
482
483 public:
484 typedef typename Base::value_compare value_compare;
485 typedef typename Base::value_traits value_traits;
486 typedef typename Base::real_value_traits real_value_traits;
487 typedef typename Base::iterator iterator;
488 typedef typename Base::const_iterator const_iterator;
489 typedef typename Base::reverse_iterator reverse_iterator;
490 typedef typename Base::const_reverse_iterator const_reverse_iterator;
491
492 //Assert if passed value traits are compatible with the type
493 BOOST_STATIC_ASSERT((detail::is_same<typename real_value_traits::value_type, T>::value));
494
495 explicit rbtree( const value_compare &cmp = value_compare()
496 , const value_traits &v_traits = value_traits())
497 : Base(cmp, v_traits)
498 {}
499
500 template<class Iterator>
501 rbtree( bool unique, Iterator b, Iterator e
502 , const value_compare &cmp = value_compare()
503 , const value_traits &v_traits = value_traits())
504 : Base(unique, b, e, cmp, v_traits)
505 {}
506
507 rbtree(BOOST_RV_REF(rbtree) x)
508 : Base(::boost::move(static_cast<Base&>(x)))
509 {}
510
511 rbtree& operator=(BOOST_RV_REF(rbtree) x)
512 { return static_cast<rbtree &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); }
513
514 static rbtree &container_from_end_iterator(iterator end_iterator)
515 { return static_cast<rbtree &>(Base::container_from_end_iterator(end_iterator)); }
516
517 static const rbtree &container_from_end_iterator(const_iterator end_iterator)
518 { return static_cast<const rbtree &>(Base::container_from_end_iterator(end_iterator)); }
519
520 static rbtree &container_from_iterator(iterator it)
521 { return static_cast<rbtree &>(Base::container_from_iterator(it)); }
522
523 static const rbtree &container_from_iterator(const_iterator it)
524 { return static_cast<const rbtree &>(Base::container_from_iterator(it)); }
525 };
526
527 #endif
528
529 } //namespace intrusive
530 } //namespace boost
531
532 #include <boost/intrusive/detail/config_end.hpp>
533
534 #endif //BOOST_INTRUSIVE_RBTREE_HPP