Line data Source code
1 : /* Copyright 2003-2019 Joaquin M Lopez Munoz.
2 : * Distributed under the Boost Software License, Version 1.0.
3 : * (See accompanying file LICENSE_1_0.txt or copy at
4 : * http://www.boost.org/LICENSE_1_0.txt)
5 : *
6 : * See http://www.boost.org/libs/multi_index for library home page.
7 : *
8 : * The internal implementation of red-black trees is based on that of SGI STL
9 : * stl_tree.h file:
10 : *
11 : * Copyright (c) 1996,1997
12 : * Silicon Graphics Computer Systems, Inc.
13 : *
14 : * Permission to use, copy, modify, distribute and sell this software
15 : * and its documentation for any purpose is hereby granted without fee,
16 : * provided that the above copyright notice appear in all copies and
17 : * that both that copyright notice and this permission notice appear
18 : * in supporting documentation. Silicon Graphics makes no
19 : * representations about the suitability of this software for any
20 : * purpose. It is provided "as is" without express or implied warranty.
21 : *
22 : *
23 : * Copyright (c) 1994
24 : * Hewlett-Packard Company
25 : *
26 : * Permission to use, copy, modify, distribute and sell this software
27 : * and its documentation for any purpose is hereby granted without fee,
28 : * provided that the above copyright notice appear in all copies and
29 : * that both that copyright notice and this permission notice appear
30 : * in supporting documentation. Hewlett-Packard Company makes no
31 : * representations about the suitability of this software for any
32 : * purpose. It is provided "as is" without express or implied warranty.
33 : *
34 : */
35 :
36 : #ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_IMPL_HPP
37 : #define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_IMPL_HPP
38 :
39 : #if defined(_MSC_VER)
40 : #pragma once
41 : #endif
42 :
43 : #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
44 : #include <algorithm>
45 : #include <boost/call_traits.hpp>
46 : #include <boost/core/addressof.hpp>
47 : #include <boost/detail/no_exceptions_support.hpp>
48 : #include <boost/detail/workaround.hpp>
49 : #include <boost/foreach_fwd.hpp>
50 : #include <boost/iterator/reverse_iterator.hpp>
51 : #include <boost/move/core.hpp>
52 : #include <boost/mpl/bool.hpp>
53 : #include <boost/mpl/if.hpp>
54 : #include <boost/mpl/push_front.hpp>
55 : #include <boost/multi_index/detail/access_specifier.hpp>
56 : #include <boost/multi_index/detail/allocator_traits.hpp>
57 : #include <boost/multi_index/detail/bidir_node_iterator.hpp>
58 : #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
59 : #include <boost/multi_index/detail/index_node_base.hpp>
60 : #include <boost/multi_index/detail/modify_key_adaptor.hpp>
61 : #include <boost/multi_index/detail/ord_index_node.hpp>
62 : #include <boost/multi_index/detail/ord_index_ops.hpp>
63 : #include <boost/multi_index/detail/safe_mode.hpp>
64 : #include <boost/multi_index/detail/scope_guard.hpp>
65 : #include <boost/multi_index/detail/unbounded.hpp>
66 : #include <boost/multi_index/detail/value_compare.hpp>
67 : #include <boost/multi_index/detail/vartempl_support.hpp>
68 : #include <boost/multi_index/detail/ord_index_impl_fwd.hpp>
69 : #include <boost/ref.hpp>
70 : #include <boost/tuple/tuple.hpp>
71 : #include <boost/type_traits/is_same.hpp>
72 : #include <utility>
73 :
74 : #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
75 : #include <initializer_list>
76 : #endif
77 :
78 : #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
79 : #include <boost/archive/archive_exception.hpp>
80 : #include <boost/bind.hpp>
81 : #include <boost/multi_index/detail/duplicates_iterator.hpp>
82 : #include <boost/throw_exception.hpp>
83 : #endif
84 :
85 : #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
86 : #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(x) \
87 : detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \
88 : detail::make_obj_guard(x,&ordered_index_impl::check_invariant_); \
89 : BOOST_JOIN(check_invariant_,__LINE__).touch();
90 : #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT \
91 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(*this)
92 : #else
93 : #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(x)
94 : #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT
95 : #endif
96 :
97 : namespace boost{
98 :
99 : namespace multi_index{
100 :
101 : namespace detail{
102 :
103 : /* ordered_index adds a layer of ordered indexing to a given Super and accepts
104 : * an augmenting policy for optional addition of order statistics.
105 : */
106 :
107 : /* Most of the implementation of unique and non-unique indices is
108 : * shared. We tell from one another on instantiation time by using
109 : * these tags.
110 : */
111 :
112 : struct ordered_unique_tag{};
113 : struct ordered_non_unique_tag{};
114 :
115 : template<
116 : typename KeyFromValue,typename Compare,
117 : typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
118 : >
119 : class ordered_index;
120 :
121 : template<
122 : typename KeyFromValue,typename Compare,
123 : typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
124 : >
125 : class ordered_index_impl:
126 : BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
127 :
128 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
129 : ,public safe_mode::safe_container<
130 : ordered_index_impl<
131 : KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy> >
132 : #endif
133 :
134 : {
135 : #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
136 : BOOST_WORKAROUND(__MWERKS__,<=0x3003)
137 : /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
138 : * lifetime of const references bound to temporaries --precisely what
139 : * scopeguards are.
140 : */
141 :
142 : #pragma parse_mfunc_templ off
143 : #endif
144 :
145 : typedef typename SuperMeta::type super;
146 :
147 : protected:
148 : typedef ordered_index_node<
149 : AugmentPolicy,typename super::node_type> node_type;
150 :
151 : protected: /* for the benefit of AugmentPolicy::augmented_interface */
152 : typedef typename node_type::impl_type node_impl_type;
153 : typedef typename node_impl_type::pointer node_impl_pointer;
154 :
155 : public:
156 : /* types */
157 :
158 : typedef typename KeyFromValue::result_type key_type;
159 : typedef typename node_type::value_type value_type;
160 : typedef KeyFromValue key_from_value;
161 : typedef Compare key_compare;
162 : typedef value_comparison<
163 : value_type,KeyFromValue,Compare> value_compare;
164 : typedef tuple<key_from_value,key_compare> ctor_args;
165 : typedef typename super::final_allocator_type allocator_type;
166 : typedef value_type& reference;
167 : typedef const value_type& const_reference;
168 :
169 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
170 : typedef safe_mode::safe_iterator<
171 : bidir_node_iterator<node_type>,
172 : ordered_index_impl> iterator;
173 : #else
174 : typedef bidir_node_iterator<node_type> iterator;
175 : #endif
176 :
177 : typedef iterator const_iterator;
178 :
179 : private:
180 : typedef allocator_traits<allocator_type> alloc_traits;
181 :
182 : public:
183 : typedef typename alloc_traits::size_type size_type;
184 : typedef typename alloc_traits::difference_type difference_type;
185 : typedef typename alloc_traits::pointer pointer;
186 : typedef typename alloc_traits::const_pointer const_pointer;
187 : typedef typename
188 : boost::reverse_iterator<iterator> reverse_iterator;
189 : typedef typename
190 : boost::reverse_iterator<const_iterator> const_reverse_iterator;
191 : typedef TagList tag_list;
192 :
193 : protected:
194 : typedef typename super::final_node_type final_node_type;
195 : typedef tuples::cons<
196 : ctor_args,
197 : typename super::ctor_args_list> ctor_args_list;
198 : typedef typename mpl::push_front<
199 : typename super::index_type_list,
200 : ordered_index<
201 : KeyFromValue,Compare,
202 : SuperMeta,TagList,Category,AugmentPolicy
203 : > >::type index_type_list;
204 : typedef typename mpl::push_front<
205 : typename super::iterator_type_list,
206 : iterator>::type iterator_type_list;
207 : typedef typename mpl::push_front<
208 : typename super::const_iterator_type_list,
209 : const_iterator>::type const_iterator_type_list;
210 : typedef typename super::copy_map_type copy_map_type;
211 :
212 : #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
213 : typedef typename super::index_saver_type index_saver_type;
214 : typedef typename super::index_loader_type index_loader_type;
215 : #endif
216 :
217 : protected:
218 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
219 : typedef safe_mode::safe_container<
220 : ordered_index_impl> safe_super;
221 : #endif
222 :
223 : typedef typename call_traits<
224 : value_type>::param_type value_param_type;
225 : typedef typename call_traits<
226 : key_type>::param_type key_param_type;
227 :
228 : /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL
229 : * expansion.
230 : */
231 :
232 : typedef std::pair<iterator,bool> emplace_return_type;
233 :
234 : public:
235 :
236 : /* construct/copy/destroy
237 : * Default and copy ctors are in the protected section as indices are
238 : * not supposed to be created on their own. No range ctor either.
239 : * Assignment operators defined at ordered_index rather than here.
240 : */
241 :
242 : allocator_type get_allocator()const BOOST_NOEXCEPT
243 : {
244 : return this->final().get_allocator();
245 : }
246 :
247 : /* iterators */
248 :
249 : iterator
250 : begin()BOOST_NOEXCEPT{return make_iterator(leftmost());}
251 : const_iterator
252 : begin()const BOOST_NOEXCEPT{return make_iterator(leftmost());}
253 : iterator
254 0 : end()BOOST_NOEXCEPT{return make_iterator(header());}
255 : const_iterator
256 : end()const BOOST_NOEXCEPT{return make_iterator(header());}
257 : reverse_iterator
258 : rbegin()BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
259 : const_reverse_iterator
260 : rbegin()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
261 : reverse_iterator
262 : rend()BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
263 : const_reverse_iterator
264 : rend()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
265 : const_iterator
266 : cbegin()const BOOST_NOEXCEPT{return begin();}
267 : const_iterator
268 : cend()const BOOST_NOEXCEPT{return end();}
269 : const_reverse_iterator
270 : crbegin()const BOOST_NOEXCEPT{return rbegin();}
271 : const_reverse_iterator
272 : crend()const BOOST_NOEXCEPT{return rend();}
273 :
274 : iterator iterator_to(const value_type& x)
275 : {
276 : return make_iterator(node_from_value<node_type>(boost::addressof(x)));
277 : }
278 :
279 : const_iterator iterator_to(const value_type& x)const
280 : {
281 : return make_iterator(node_from_value<node_type>(boost::addressof(x)));
282 : }
283 :
284 : /* capacity */
285 :
286 : bool empty()const BOOST_NOEXCEPT{return this->final_empty_();}
287 : size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
288 : size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
289 :
290 : /* modifiers */
291 :
292 : BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
293 : emplace_return_type,emplace,emplace_impl)
294 :
295 : BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
296 : iterator,emplace_hint,emplace_hint_impl,iterator,position)
297 :
298 : std::pair<iterator,bool> insert(const value_type& x)
299 : {
300 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
301 : std::pair<final_node_type*,bool> p=this->final_insert_(x);
302 : return std::pair<iterator,bool>(make_iterator(p.first),p.second);
303 : }
304 :
305 0 : std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
306 : {
307 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
308 0 : std::pair<final_node_type*,bool> p=this->final_insert_rv_(x);
309 0 : return std::pair<iterator,bool>(make_iterator(p.first),p.second);
310 : }
311 :
312 : iterator insert(iterator position,const value_type& x)
313 : {
314 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
315 : BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
316 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
317 : std::pair<final_node_type*,bool> p=this->final_insert_(
318 : x,static_cast<final_node_type*>(position.get_node()));
319 : return make_iterator(p.first);
320 : }
321 :
322 : iterator insert(iterator position,BOOST_RV_REF(value_type) x)
323 : {
324 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
325 : BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
326 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
327 : std::pair<final_node_type*,bool> p=this->final_insert_rv_(
328 : x,static_cast<final_node_type*>(position.get_node()));
329 : return make_iterator(p.first);
330 : }
331 :
332 : template<typename InputIterator>
333 : void insert(InputIterator first,InputIterator last)
334 : {
335 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
336 : node_type* hint=header(); /* end() */
337 : for(;first!=last;++first){
338 : hint=this->final_insert_ref_(
339 : *first,static_cast<final_node_type*>(hint)).first;
340 : node_type::increment(hint);
341 : }
342 : }
343 :
344 : #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
345 : void insert(std::initializer_list<value_type> list)
346 : {
347 : insert(list.begin(),list.end());
348 : }
349 : #endif
350 :
351 0 : iterator erase(iterator position)
352 : {
353 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
354 : BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
355 : BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
356 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
357 0 : this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
358 0 : return position;
359 : }
360 :
361 : size_type erase(key_param_type x)
362 : {
363 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
364 : std::pair<iterator,iterator> p=equal_range(x);
365 : size_type s=0;
366 : while(p.first!=p.second){
367 : p.first=erase(p.first);
368 : ++s;
369 : }
370 : return s;
371 : }
372 :
373 : iterator erase(iterator first,iterator last)
374 : {
375 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
376 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
377 : BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
378 : BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
379 : BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
380 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
381 0 : while(first!=last){
382 0 : first=erase(first);
383 : }
384 : return first;
385 : }
386 :
387 : bool replace(iterator position,const value_type& x)
388 : {
389 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
390 : BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
391 : BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
392 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
393 : return this->final_replace_(
394 : x,static_cast<final_node_type*>(position.get_node()));
395 : }
396 :
397 : bool replace(iterator position,BOOST_RV_REF(value_type) x)
398 : {
399 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
400 : BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
401 : BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
402 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
403 : return this->final_replace_rv_(
404 : x,static_cast<final_node_type*>(position.get_node()));
405 : }
406 :
407 : template<typename Modifier>
408 : bool modify(iterator position,Modifier mod)
409 : {
410 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
411 : BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
412 : BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
413 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
414 :
415 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
416 : /* MSVC++ 6.0 optimizer on safe mode code chokes if this
417 : * this is not added. Left it for all compilers as it does no
418 : * harm.
419 : */
420 :
421 : position.detach();
422 : #endif
423 :
424 : return this->final_modify_(
425 : mod,static_cast<final_node_type*>(position.get_node()));
426 : }
427 :
428 : template<typename Modifier,typename Rollback>
429 : bool modify(iterator position,Modifier mod,Rollback back_)
430 : {
431 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
432 : BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
433 : BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
434 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
435 :
436 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
437 : /* MSVC++ 6.0 optimizer on safe mode code chokes if this
438 : * this is not added. Left it for all compilers as it does no
439 : * harm.
440 : */
441 :
442 : position.detach();
443 : #endif
444 :
445 : return this->final_modify_(
446 : mod,back_,static_cast<final_node_type*>(position.get_node()));
447 : }
448 :
449 : template<typename Modifier>
450 : bool modify_key(iterator position,Modifier mod)
451 : {
452 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
453 : BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
454 : BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
455 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
456 : return modify(
457 : position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
458 : }
459 :
460 : template<typename Modifier,typename Rollback>
461 : bool modify_key(iterator position,Modifier mod,Rollback back_)
462 : {
463 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
464 : BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
465 : BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
466 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
467 : return modify(
468 : position,
469 : modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key),
470 : modify_key_adaptor<Rollback,value_type,KeyFromValue>(back_,key));
471 : }
472 :
473 : void swap(
474 : ordered_index<
475 : KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x)
476 : {
477 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
478 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(x);
479 : this->final_swap_(x.final());
480 : }
481 :
482 : void clear()BOOST_NOEXCEPT
483 : {
484 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
485 : this->final_clear_();
486 : }
487 :
488 : /* observers */
489 :
490 : key_from_value key_extractor()const{return key;}
491 : key_compare key_comp()const{return comp_;}
492 : value_compare value_comp()const{return value_compare(key,comp_);}
493 :
494 : /* set operations */
495 :
496 : /* Internally, these ops rely on const_iterator being the same
497 : * type as iterator.
498 : */
499 :
500 : template<typename CompatibleKey>
501 0 : iterator find(const CompatibleKey& x)const
502 : {
503 0 : return make_iterator(ordered_index_find(root(),header(),key,x,comp_));
504 : }
505 :
506 : template<typename CompatibleKey,typename CompatibleCompare>
507 : iterator find(
508 : const CompatibleKey& x,const CompatibleCompare& comp)const
509 : {
510 : return make_iterator(ordered_index_find(root(),header(),key,x,comp));
511 : }
512 :
513 : template<typename CompatibleKey>
514 : size_type count(const CompatibleKey& x)const
515 : {
516 : return count(x,comp_);
517 : }
518 :
519 : template<typename CompatibleKey,typename CompatibleCompare>
520 : size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const
521 : {
522 : std::pair<iterator,iterator> p=equal_range(x,comp);
523 : size_type n=static_cast<size_type>(std::distance(p.first,p.second));
524 : return n;
525 : }
526 :
527 : template<typename CompatibleKey>
528 : iterator lower_bound(const CompatibleKey& x)const
529 : {
530 : return make_iterator(
531 : ordered_index_lower_bound(root(),header(),key,x,comp_));
532 : }
533 :
534 : template<typename CompatibleKey,typename CompatibleCompare>
535 : iterator lower_bound(
536 : const CompatibleKey& x,const CompatibleCompare& comp)const
537 : {
538 : return make_iterator(
539 : ordered_index_lower_bound(root(),header(),key,x,comp));
540 : }
541 :
542 : template<typename CompatibleKey>
543 : iterator upper_bound(const CompatibleKey& x)const
544 : {
545 : return make_iterator(
546 : ordered_index_upper_bound(root(),header(),key,x,comp_));
547 : }
548 :
549 : template<typename CompatibleKey,typename CompatibleCompare>
550 : iterator upper_bound(
551 : const CompatibleKey& x,const CompatibleCompare& comp)const
552 : {
553 : return make_iterator(
554 : ordered_index_upper_bound(root(),header(),key,x,comp));
555 : }
556 :
557 : template<typename CompatibleKey>
558 0 : std::pair<iterator,iterator> equal_range(
559 : const CompatibleKey& x)const
560 : {
561 : std::pair<node_type*,node_type*> p=
562 0 : ordered_index_equal_range(root(),header(),key,x,comp_);
563 0 : return std::pair<iterator,iterator>(
564 0 : make_iterator(p.first),make_iterator(p.second));
565 : }
566 :
567 : template<typename CompatibleKey,typename CompatibleCompare>
568 : std::pair<iterator,iterator> equal_range(
569 : const CompatibleKey& x,const CompatibleCompare& comp)const
570 : {
571 : std::pair<node_type*,node_type*> p=
572 : ordered_index_equal_range(root(),header(),key,x,comp);
573 : return std::pair<iterator,iterator>(
574 : make_iterator(p.first),make_iterator(p.second));
575 : }
576 :
577 : /* range */
578 :
579 : template<typename LowerBounder,typename UpperBounder>
580 : std::pair<iterator,iterator>
581 : range(LowerBounder lower,UpperBounder upper)const
582 : {
583 : typedef typename mpl::if_<
584 : is_same<LowerBounder,unbounded_type>,
585 : BOOST_DEDUCED_TYPENAME mpl::if_<
586 : is_same<UpperBounder,unbounded_type>,
587 : both_unbounded_tag,
588 : lower_unbounded_tag
589 : >::type,
590 : BOOST_DEDUCED_TYPENAME mpl::if_<
591 : is_same<UpperBounder,unbounded_type>,
592 : upper_unbounded_tag,
593 : none_unbounded_tag
594 : >::type
595 : >::type dispatch;
596 :
597 : return range(lower,upper,dispatch());
598 : }
599 :
600 : BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
601 0 : ordered_index_impl(const ctor_args_list& args_list,const allocator_type& al):
602 : super(args_list.get_tail(),al),
603 0 : key(tuples::get<0>(args_list.get_head())),
604 0 : comp_(tuples::get<1>(args_list.get_head()))
605 : {
606 0 : empty_initialize();
607 : }
608 :
609 : ordered_index_impl(
610 : const ordered_index_impl<
611 : KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x):
612 : super(x),
613 :
614 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
615 : safe_super(),
616 : #endif
617 :
618 : key(x.key),
619 : comp_(x.comp_)
620 : {
621 : /* Copy ctor just takes the key and compare objects from x. The rest is
622 : * done in a subsequent call to copy_().
623 : */
624 : }
625 :
626 : ordered_index_impl(
627 : const ordered_index_impl<
628 : KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x,
629 : do_not_copy_elements_tag):
630 : super(x,do_not_copy_elements_tag()),
631 :
632 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
633 : safe_super(),
634 : #endif
635 :
636 : key(x.key),
637 : comp_(x.comp_)
638 : {
639 : empty_initialize();
640 : }
641 :
642 0 : ~ordered_index_impl()
643 : {
644 : /* the container is guaranteed to be empty by now */
645 0 : }
646 :
647 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
648 : iterator make_iterator(node_type* node){return iterator(node,this);}
649 : const_iterator make_iterator(node_type* node)const
650 : {return const_iterator(node,const_cast<ordered_index_impl*>(this));}
651 : #else
652 0 : iterator make_iterator(node_type* node){return iterator(node);}
653 0 : const_iterator make_iterator(node_type* node)const
654 0 : {return const_iterator(node);}
655 : #endif
656 :
657 : void copy_(
658 : const ordered_index_impl<
659 : KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x,
660 : const copy_map_type& map)
661 : {
662 : if(!x.root()){
663 : empty_initialize();
664 : }
665 : else{
666 : header()->color()=x.header()->color();
667 : AugmentPolicy::copy(x.header()->impl(),header()->impl());
668 :
669 : node_type* root_cpy=map.find(static_cast<final_node_type*>(x.root()));
670 : header()->parent()=root_cpy->impl();
671 :
672 : node_type* leftmost_cpy=map.find(
673 : static_cast<final_node_type*>(x.leftmost()));
674 : header()->left()=leftmost_cpy->impl();
675 :
676 : node_type* rightmost_cpy=map.find(
677 : static_cast<final_node_type*>(x.rightmost()));
678 : header()->right()=rightmost_cpy->impl();
679 :
680 : typedef typename copy_map_type::const_iterator copy_map_iterator;
681 : for(copy_map_iterator it=map.begin(),it_end=map.end();it!=it_end;++it){
682 : node_type* org=it->first;
683 : node_type* cpy=it->second;
684 :
685 : cpy->color()=org->color();
686 : AugmentPolicy::copy(org->impl(),cpy->impl());
687 :
688 : node_impl_pointer parent_org=org->parent();
689 : if(parent_org==node_impl_pointer(0))cpy->parent()=node_impl_pointer(0);
690 : else{
691 : node_type* parent_cpy=map.find(
692 : static_cast<final_node_type*>(node_type::from_impl(parent_org)));
693 : cpy->parent()=parent_cpy->impl();
694 : if(parent_org->left()==org->impl()){
695 : parent_cpy->left()=cpy->impl();
696 : }
697 : else if(parent_org->right()==org->impl()){
698 : /* header() does not satisfy this nor the previous check */
699 : parent_cpy->right()=cpy->impl();
700 : }
701 : }
702 :
703 : if(org->left()==node_impl_pointer(0))
704 : cpy->left()=node_impl_pointer(0);
705 : if(org->right()==node_impl_pointer(0))
706 : cpy->right()=node_impl_pointer(0);
707 : }
708 : }
709 :
710 : super::copy_(x,map);
711 : }
712 :
713 : template<typename Variant>
714 0 : final_node_type* insert_(
715 : value_param_type v,final_node_type*& x,Variant variant)
716 : {
717 0 : link_info inf;
718 0 : if(!link_point(key(v),inf,Category())){
719 0 : return static_cast<final_node_type*>(node_type::from_impl(inf.pos));
720 : }
721 :
722 0 : final_node_type* res=super::insert_(v,x,variant);
723 0 : if(res==x){
724 0 : node_impl_type::link(
725 : static_cast<node_type*>(x)->impl(),inf.side,inf.pos,header()->impl());
726 : }
727 : return res;
728 : }
729 :
730 : template<typename Variant>
731 : final_node_type* insert_(
732 : value_param_type v,node_type* position,final_node_type*& x,Variant variant)
733 : {
734 : link_info inf;
735 : if(!hinted_link_point(key(v),position,inf,Category())){
736 : return static_cast<final_node_type*>(node_type::from_impl(inf.pos));
737 : }
738 :
739 : final_node_type* res=super::insert_(v,position,x,variant);
740 : if(res==x){
741 : node_impl_type::link(
742 : static_cast<node_type*>(x)->impl(),inf.side,inf.pos,header()->impl());
743 : }
744 : return res;
745 : }
746 :
747 0 : void erase_(node_type* x)
748 : {
749 0 : node_impl_type::rebalance_for_erase(
750 : x->impl(),header()->parent(),header()->left(),header()->right());
751 0 : super::erase_(x);
752 :
753 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
754 : detach_iterators(x);
755 : #endif
756 0 : }
757 :
758 0 : void delete_all_nodes_()
759 : {
760 0 : delete_all_nodes(root());
761 : }
762 :
763 : void clear_()
764 : {
765 : super::clear_();
766 : empty_initialize();
767 :
768 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
769 : safe_super::detach_dereferenceable_iterators();
770 : #endif
771 : }
772 :
773 : void swap_(
774 : ordered_index_impl<
775 : KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x)
776 : {
777 : std::swap(key,x.key);
778 : std::swap(comp_,x.comp_);
779 :
780 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
781 : safe_super::swap(x);
782 : #endif
783 :
784 : super::swap_(x);
785 : }
786 :
787 : void swap_elements_(
788 : ordered_index_impl<
789 : KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x)
790 : {
791 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
792 : safe_super::swap(x);
793 : #endif
794 :
795 : super::swap_elements_(x);
796 : }
797 :
798 : template<typename Variant>
799 : bool replace_(value_param_type v,node_type* x,Variant variant)
800 : {
801 : if(in_place(v,x,Category())){
802 : return super::replace_(v,x,variant);
803 : }
804 :
805 : node_type* next=x;
806 : node_type::increment(next);
807 :
808 : node_impl_type::rebalance_for_erase(
809 : x->impl(),header()->parent(),header()->left(),header()->right());
810 :
811 : BOOST_TRY{
812 : link_info inf;
813 : if(link_point(key(v),inf,Category())&&super::replace_(v,x,variant)){
814 : node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
815 : return true;
816 : }
817 : node_impl_type::restore(x->impl(),next->impl(),header()->impl());
818 : return false;
819 : }
820 : BOOST_CATCH(...){
821 : node_impl_type::restore(x->impl(),next->impl(),header()->impl());
822 : BOOST_RETHROW;
823 : }
824 : BOOST_CATCH_END
825 : }
826 :
827 : bool modify_(node_type* x)
828 : {
829 : bool b;
830 : BOOST_TRY{
831 : b=in_place(x->value(),x,Category());
832 : }
833 : BOOST_CATCH(...){
834 : erase_(x);
835 : BOOST_RETHROW;
836 : }
837 : BOOST_CATCH_END
838 : if(!b){
839 : node_impl_type::rebalance_for_erase(
840 : x->impl(),header()->parent(),header()->left(),header()->right());
841 : BOOST_TRY{
842 : link_info inf;
843 : if(!link_point(key(x->value()),inf,Category())){
844 : super::erase_(x);
845 :
846 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
847 : detach_iterators(x);
848 : #endif
849 : return false;
850 : }
851 : node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
852 : }
853 : BOOST_CATCH(...){
854 : super::erase_(x);
855 :
856 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
857 : detach_iterators(x);
858 : #endif
859 :
860 : BOOST_RETHROW;
861 : }
862 : BOOST_CATCH_END
863 : }
864 :
865 : BOOST_TRY{
866 : if(!super::modify_(x)){
867 : node_impl_type::rebalance_for_erase(
868 : x->impl(),header()->parent(),header()->left(),header()->right());
869 :
870 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
871 : detach_iterators(x);
872 : #endif
873 :
874 : return false;
875 : }
876 : else return true;
877 : }
878 : BOOST_CATCH(...){
879 : node_impl_type::rebalance_for_erase(
880 : x->impl(),header()->parent(),header()->left(),header()->right());
881 :
882 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
883 : detach_iterators(x);
884 : #endif
885 :
886 : BOOST_RETHROW;
887 : }
888 : BOOST_CATCH_END
889 : }
890 :
891 : bool modify_rollback_(node_type* x)
892 : {
893 : if(in_place(x->value(),x,Category())){
894 : return super::modify_rollback_(x);
895 : }
896 :
897 : node_type* next=x;
898 : node_type::increment(next);
899 :
900 : node_impl_type::rebalance_for_erase(
901 : x->impl(),header()->parent(),header()->left(),header()->right());
902 :
903 : BOOST_TRY{
904 : link_info inf;
905 : if(link_point(key(x->value()),inf,Category())&&
906 : super::modify_rollback_(x)){
907 : node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
908 : return true;
909 : }
910 : node_impl_type::restore(x->impl(),next->impl(),header()->impl());
911 : return false;
912 : }
913 : BOOST_CATCH(...){
914 : node_impl_type::restore(x->impl(),next->impl(),header()->impl());
915 : BOOST_RETHROW;
916 : }
917 : BOOST_CATCH_END
918 : }
919 :
920 : bool check_rollback_(node_type* x)const
921 : {
922 : return in_place(x->value(),x,Category())&&super::check_rollback_(x);
923 : }
924 :
925 : #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
926 : /* serialization */
927 :
928 : template<typename Archive>
929 : void save_(
930 : Archive& ar,const unsigned int version,const index_saver_type& sm)const
931 : {
932 : save_(ar,version,sm,Category());
933 : }
934 :
935 : template<typename Archive>
936 : void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
937 : {
938 : load_(ar,version,lm,Category());
939 : }
940 : #endif
941 :
942 : #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
943 : /* invariant stuff */
944 :
945 : bool invariant_()const
946 : {
947 : if(size()==0||begin()==end()){
948 : if(size()!=0||begin()!=end()||
949 : header()->left()!=header()->impl()||
950 : header()->right()!=header()->impl())return false;
951 : }
952 : else{
953 : if((size_type)std::distance(begin(),end())!=size())return false;
954 :
955 : std::size_t len=node_impl_type::black_count(
956 : leftmost()->impl(),root()->impl());
957 : for(const_iterator it=begin(),it_end=end();it!=it_end;++it){
958 : node_type* x=it.get_node();
959 : node_type* left_x=node_type::from_impl(x->left());
960 : node_type* right_x=node_type::from_impl(x->right());
961 :
962 : if(x->color()==red){
963 : if((left_x&&left_x->color()==red)||
964 : (right_x&&right_x->color()==red))return false;
965 : }
966 : if(left_x&&comp_(key(x->value()),key(left_x->value())))return false;
967 : if(right_x&&comp_(key(right_x->value()),key(x->value())))return false;
968 : if(!left_x&&!right_x&&
969 : node_impl_type::black_count(x->impl(),root()->impl())!=len)
970 : return false;
971 : if(!AugmentPolicy::invariant(x->impl()))return false;
972 : }
973 :
974 : if(leftmost()->impl()!=node_impl_type::minimum(root()->impl()))
975 : return false;
976 : if(rightmost()->impl()!=node_impl_type::maximum(root()->impl()))
977 : return false;
978 : }
979 :
980 : return super::invariant_();
981 : }
982 :
983 :
984 : /* This forwarding function eases things for the boost::mem_fn construct
985 : * in BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT. Actually,
986 : * final_check_invariant is already an inherited member function of
987 : * ordered_index_impl.
988 : */
989 : void check_invariant_()const{this->final_check_invariant_();}
990 : #endif
991 :
992 : protected: /* for the benefit of AugmentPolicy::augmented_interface */
993 0 : node_type* header()const{return this->final_header();}
994 0 : node_type* root()const{return node_type::from_impl(header()->parent());}
995 0 : node_type* leftmost()const{return node_type::from_impl(header()->left());}
996 : node_type* rightmost()const{return node_type::from_impl(header()->right());}
997 :
998 : private:
999 0 : void empty_initialize()
1000 : {
1001 0 : header()->color()=red;
1002 : /* used to distinguish header() from root, in iterator.operator++ */
1003 :
1004 0 : header()->parent()=node_impl_pointer(0);
1005 0 : header()->left()=header()->impl();
1006 0 : header()->right()=header()->impl();
1007 : }
1008 :
1009 : struct link_info
1010 : {
1011 : /* coverity[uninit_ctor]: suppress warning */
1012 0 : link_info():side(to_left){}
1013 :
1014 : ordered_index_side side;
1015 : node_impl_pointer pos;
1016 : };
1017 :
1018 0 : bool link_point(key_param_type k,link_info& inf,ordered_unique_tag)
1019 : {
1020 0 : node_type* y=header();
1021 0 : node_type* x=root();
1022 : bool c=true;
1023 0 : while(x){
1024 0 : y=x;
1025 0 : c=comp_(k,key(x->value()));
1026 0 : x=node_type::from_impl(c?x->left():x->right());
1027 : }
1028 0 : node_type* yy=y;
1029 0 : if(c){
1030 0 : if(yy==leftmost()){
1031 0 : inf.side=to_left;
1032 0 : inf.pos=y->impl();
1033 0 : return true;
1034 : }
1035 0 : else node_type::decrement(yy);
1036 : }
1037 :
1038 0 : if(comp_(key(yy->value()),k)){
1039 0 : inf.side=c?to_left:to_right;
1040 0 : inf.pos=y->impl();
1041 0 : return true;
1042 : }
1043 : else{
1044 0 : inf.pos=yy->impl();
1045 0 : return false;
1046 : }
1047 : }
1048 :
1049 : bool link_point(key_param_type k,link_info& inf,ordered_non_unique_tag)
1050 : {
1051 : node_type* y=header();
1052 : node_type* x=root();
1053 : bool c=true;
1054 : while (x){
1055 : y=x;
1056 : c=comp_(k,key(x->value()));
1057 : x=node_type::from_impl(c?x->left():x->right());
1058 : }
1059 : inf.side=c?to_left:to_right;
1060 : inf.pos=y->impl();
1061 : return true;
1062 : }
1063 :
1064 : bool lower_link_point(key_param_type k,link_info& inf,ordered_non_unique_tag)
1065 : {
1066 : node_type* y=header();
1067 : node_type* x=root();
1068 : bool c=false;
1069 : while (x){
1070 : y=x;
1071 : c=comp_(key(x->value()),k);
1072 : x=node_type::from_impl(c?x->right():x->left());
1073 : }
1074 : inf.side=c?to_right:to_left;
1075 : inf.pos=y->impl();
1076 : return true;
1077 : }
1078 :
1079 : bool hinted_link_point(
1080 : key_param_type k,node_type* position,link_info& inf,ordered_unique_tag)
1081 : {
1082 : if(position->impl()==header()->left()){
1083 : if(size()>0&&comp_(k,key(position->value()))){
1084 : inf.side=to_left;
1085 : inf.pos=position->impl();
1086 : return true;
1087 : }
1088 : else return link_point(k,inf,ordered_unique_tag());
1089 : }
1090 : else if(position==header()){
1091 : if(comp_(key(rightmost()->value()),k)){
1092 : inf.side=to_right;
1093 : inf.pos=rightmost()->impl();
1094 : return true;
1095 : }
1096 : else return link_point(k,inf,ordered_unique_tag());
1097 : }
1098 : else{
1099 : node_type* before=position;
1100 : node_type::decrement(before);
1101 : if(comp_(key(before->value()),k)&&comp_(k,key(position->value()))){
1102 : if(before->right()==node_impl_pointer(0)){
1103 : inf.side=to_right;
1104 : inf.pos=before->impl();
1105 : return true;
1106 : }
1107 : else{
1108 : inf.side=to_left;
1109 : inf.pos=position->impl();
1110 : return true;
1111 : }
1112 : }
1113 : else return link_point(k,inf,ordered_unique_tag());
1114 : }
1115 : }
1116 :
1117 : bool hinted_link_point(
1118 : key_param_type k,node_type* position,link_info& inf,ordered_non_unique_tag)
1119 : {
1120 : if(position->impl()==header()->left()){
1121 : if(size()>0&&!comp_(key(position->value()),k)){
1122 : inf.side=to_left;
1123 : inf.pos=position->impl();
1124 : return true;
1125 : }
1126 : else return lower_link_point(k,inf,ordered_non_unique_tag());
1127 : }
1128 : else if(position==header()){
1129 : if(!comp_(k,key(rightmost()->value()))){
1130 : inf.side=to_right;
1131 : inf.pos=rightmost()->impl();
1132 : return true;
1133 : }
1134 : else return link_point(k,inf,ordered_non_unique_tag());
1135 : }
1136 : else{
1137 : node_type* before=position;
1138 : node_type::decrement(before);
1139 : if(!comp_(k,key(before->value()))){
1140 : if(!comp_(key(position->value()),k)){
1141 : if(before->right()==node_impl_pointer(0)){
1142 : inf.side=to_right;
1143 : inf.pos=before->impl();
1144 : return true;
1145 : }
1146 : else{
1147 : inf.side=to_left;
1148 : inf.pos=position->impl();
1149 : return true;
1150 : }
1151 : }
1152 : else return lower_link_point(k,inf,ordered_non_unique_tag());
1153 : }
1154 : else return link_point(k,inf,ordered_non_unique_tag());
1155 : }
1156 : }
1157 :
1158 0 : void delete_all_nodes(node_type* x)
1159 : {
1160 0 : if(!x)return;
1161 :
1162 0 : delete_all_nodes(node_type::from_impl(x->left()));
1163 0 : delete_all_nodes(node_type::from_impl(x->right()));
1164 0 : this->final_delete_node_(static_cast<final_node_type*>(x));
1165 : }
1166 :
1167 : bool in_place(value_param_type v,node_type* x,ordered_unique_tag)const
1168 : {
1169 : node_type* y;
1170 : if(x!=leftmost()){
1171 : y=x;
1172 : node_type::decrement(y);
1173 : if(!comp_(key(y->value()),key(v)))return false;
1174 : }
1175 :
1176 : y=x;
1177 : node_type::increment(y);
1178 : return y==header()||comp_(key(v),key(y->value()));
1179 : }
1180 :
1181 : bool in_place(value_param_type v,node_type* x,ordered_non_unique_tag)const
1182 : {
1183 : node_type* y;
1184 : if(x!=leftmost()){
1185 : y=x;
1186 : node_type::decrement(y);
1187 : if(comp_(key(v),key(y->value())))return false;
1188 : }
1189 :
1190 : y=x;
1191 : node_type::increment(y);
1192 : return y==header()||!comp_(key(y->value()),key(v));
1193 : }
1194 :
1195 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1196 : void detach_iterators(node_type* x)
1197 : {
1198 : iterator it=make_iterator(x);
1199 : safe_mode::detach_equivalent_iterators(it);
1200 : }
1201 : #endif
1202 :
1203 : template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1204 : std::pair<iterator,bool> emplace_impl(BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1205 : {
1206 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1207 : std::pair<final_node_type*,bool>p=
1208 : this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1209 : return std::pair<iterator,bool>(make_iterator(p.first),p.second);
1210 : }
1211 :
1212 : template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1213 : iterator emplace_hint_impl(
1214 : iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1215 : {
1216 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1217 : BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1218 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1219 : std::pair<final_node_type*,bool>p=
1220 : this->final_emplace_hint_(
1221 : static_cast<final_node_type*>(position.get_node()),
1222 : BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1223 : return make_iterator(p.first);
1224 : }
1225 :
1226 : template<typename LowerBounder,typename UpperBounder>
1227 : std::pair<iterator,iterator>
1228 : range(LowerBounder lower,UpperBounder upper,none_unbounded_tag)const
1229 : {
1230 : node_type* y=header();
1231 : node_type* z=root();
1232 :
1233 : while(z){
1234 : if(!lower(key(z->value()))){
1235 : z=node_type::from_impl(z->right());
1236 : }
1237 : else if(!upper(key(z->value()))){
1238 : y=z;
1239 : z=node_type::from_impl(z->left());
1240 : }
1241 : else{
1242 : return std::pair<iterator,iterator>(
1243 : make_iterator(
1244 : lower_range(node_type::from_impl(z->left()),z,lower)),
1245 : make_iterator(
1246 : upper_range(node_type::from_impl(z->right()),y,upper)));
1247 : }
1248 : }
1249 :
1250 : return std::pair<iterator,iterator>(make_iterator(y),make_iterator(y));
1251 : }
1252 :
1253 : template<typename LowerBounder,typename UpperBounder>
1254 : std::pair<iterator,iterator>
1255 : range(LowerBounder,UpperBounder upper,lower_unbounded_tag)const
1256 : {
1257 : return std::pair<iterator,iterator>(
1258 : begin(),
1259 : make_iterator(upper_range(root(),header(),upper)));
1260 : }
1261 :
1262 : template<typename LowerBounder,typename UpperBounder>
1263 : std::pair<iterator,iterator>
1264 : range(LowerBounder lower,UpperBounder,upper_unbounded_tag)const
1265 : {
1266 : return std::pair<iterator,iterator>(
1267 : make_iterator(lower_range(root(),header(),lower)),
1268 : end());
1269 : }
1270 :
1271 : template<typename LowerBounder,typename UpperBounder>
1272 : std::pair<iterator,iterator>
1273 : range(LowerBounder,UpperBounder,both_unbounded_tag)const
1274 : {
1275 : return std::pair<iterator,iterator>(begin(),end());
1276 : }
1277 :
1278 : template<typename LowerBounder>
1279 : node_type * lower_range(node_type* top,node_type* y,LowerBounder lower)const
1280 : {
1281 : while(top){
1282 : if(lower(key(top->value()))){
1283 : y=top;
1284 : top=node_type::from_impl(top->left());
1285 : }
1286 : else top=node_type::from_impl(top->right());
1287 : }
1288 :
1289 : return y;
1290 : }
1291 :
1292 : template<typename UpperBounder>
1293 : node_type * upper_range(node_type* top,node_type* y,UpperBounder upper)const
1294 : {
1295 : while(top){
1296 : if(!upper(key(top->value()))){
1297 : y=top;
1298 : top=node_type::from_impl(top->left());
1299 : }
1300 : else top=node_type::from_impl(top->right());
1301 : }
1302 :
1303 : return y;
1304 : }
1305 :
1306 : #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1307 : template<typename Archive>
1308 : void save_(
1309 : Archive& ar,const unsigned int version,const index_saver_type& sm,
1310 : ordered_unique_tag)const
1311 : {
1312 : super::save_(ar,version,sm);
1313 : }
1314 :
1315 : template<typename Archive>
1316 : void load_(
1317 : Archive& ar,const unsigned int version,const index_loader_type& lm,
1318 : ordered_unique_tag)
1319 : {
1320 : super::load_(ar,version,lm);
1321 : }
1322 :
1323 : template<typename Archive>
1324 : void save_(
1325 : Archive& ar,const unsigned int version,const index_saver_type& sm,
1326 : ordered_non_unique_tag)const
1327 : {
1328 : typedef duplicates_iterator<node_type,value_compare> dup_iterator;
1329 :
1330 : sm.save(
1331 : dup_iterator(begin().get_node(),end().get_node(),value_comp()),
1332 : dup_iterator(end().get_node(),value_comp()),
1333 : ar,version);
1334 : super::save_(ar,version,sm);
1335 : }
1336 :
1337 : template<typename Archive>
1338 : void load_(
1339 : Archive& ar,const unsigned int version,const index_loader_type& lm,
1340 : ordered_non_unique_tag)
1341 : {
1342 : lm.load(
1343 : ::boost::bind(
1344 : &ordered_index_impl::rearranger,this,
1345 : ::boost::arg<1>(),::boost::arg<2>()),
1346 : ar,version);
1347 : super::load_(ar,version,lm);
1348 : }
1349 :
1350 : void rearranger(node_type* position,node_type *x)
1351 : {
1352 : if(!position||comp_(key(position->value()),key(x->value()))){
1353 : position=lower_bound(key(x->value())).get_node();
1354 : }
1355 : else if(comp_(key(x->value()),key(position->value()))){
1356 : /* inconsistent rearrangement */
1357 : throw_exception(
1358 : archive::archive_exception(
1359 : archive::archive_exception::other_exception));
1360 : }
1361 : else node_type::increment(position);
1362 :
1363 : if(position!=x){
1364 : node_impl_type::rebalance_for_erase(
1365 : x->impl(),header()->parent(),header()->left(),header()->right());
1366 : node_impl_type::restore(
1367 : x->impl(),position->impl(),header()->impl());
1368 : }
1369 : }
1370 : #endif /* serialization */
1371 :
1372 : protected: /* for the benefit of AugmentPolicy::augmented_interface */
1373 : key_from_value key;
1374 : key_compare comp_;
1375 :
1376 : #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1377 : BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1378 : #pragma parse_mfunc_templ reset
1379 : #endif
1380 : };
1381 :
1382 : template<
1383 : typename KeyFromValue,typename Compare,
1384 : typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
1385 : >
1386 0 : class ordered_index:
1387 : public AugmentPolicy::template augmented_interface<
1388 : ordered_index_impl<
1389 : KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy
1390 : >
1391 : >::type
1392 : {
1393 : typedef typename AugmentPolicy::template
1394 : augmented_interface<
1395 : ordered_index_impl<
1396 : KeyFromValue,Compare,
1397 : SuperMeta,TagList,Category,AugmentPolicy
1398 : >
1399 : >::type super;
1400 : public:
1401 : typedef typename super::ctor_args_list ctor_args_list;
1402 : typedef typename super::allocator_type allocator_type;
1403 : typedef typename super::iterator iterator;
1404 :
1405 : /* construct/copy/destroy
1406 : * Default and copy ctors are in the protected section as indices are
1407 : * not supposed to be created on their own. No range ctor either.
1408 : */
1409 :
1410 : ordered_index& operator=(const ordered_index& x)
1411 : {
1412 : this->final()=x.final();
1413 : return *this;
1414 : }
1415 :
1416 : #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1417 : ordered_index& operator=(
1418 : std::initializer_list<BOOST_DEDUCED_TYPENAME super::value_type> list)
1419 : {
1420 : this->final()=list;
1421 : return *this;
1422 : }
1423 : #endif
1424 :
1425 : protected:
1426 0 : ordered_index(
1427 : const ctor_args_list& args_list,const allocator_type& al):
1428 0 : super(args_list,al){}
1429 :
1430 : ordered_index(const ordered_index& x):super(x){}
1431 :
1432 : ordered_index(const ordered_index& x,do_not_copy_elements_tag):
1433 : super(x,do_not_copy_elements_tag()){}
1434 : };
1435 :
1436 : /* comparison */
1437 :
1438 : template<
1439 : typename KeyFromValue1,typename Compare1,
1440 : typename SuperMeta1,typename TagList1,typename Category1,
1441 : typename AugmentPolicy1,
1442 : typename KeyFromValue2,typename Compare2,
1443 : typename SuperMeta2,typename TagList2,typename Category2,
1444 : typename AugmentPolicy2
1445 : >
1446 : bool operator==(
1447 : const ordered_index<
1448 : KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x,
1449 : const ordered_index<
1450 : KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y)
1451 : {
1452 : return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
1453 : }
1454 :
1455 : template<
1456 : typename KeyFromValue1,typename Compare1,
1457 : typename SuperMeta1,typename TagList1,typename Category1,
1458 : typename AugmentPolicy1,
1459 : typename KeyFromValue2,typename Compare2,
1460 : typename SuperMeta2,typename TagList2,typename Category2,
1461 : typename AugmentPolicy2
1462 : >
1463 : bool operator<(
1464 : const ordered_index<
1465 : KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x,
1466 : const ordered_index<
1467 : KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y)
1468 : {
1469 : return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
1470 : }
1471 :
1472 : template<
1473 : typename KeyFromValue1,typename Compare1,
1474 : typename SuperMeta1,typename TagList1,typename Category1,
1475 : typename AugmentPolicy1,
1476 : typename KeyFromValue2,typename Compare2,
1477 : typename SuperMeta2,typename TagList2,typename Category2,
1478 : typename AugmentPolicy2
1479 : >
1480 : bool operator!=(
1481 : const ordered_index<
1482 : KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x,
1483 : const ordered_index<
1484 : KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y)
1485 : {
1486 : return !(x==y);
1487 : }
1488 :
1489 : template<
1490 : typename KeyFromValue1,typename Compare1,
1491 : typename SuperMeta1,typename TagList1,typename Category1,
1492 : typename AugmentPolicy1,
1493 : typename KeyFromValue2,typename Compare2,
1494 : typename SuperMeta2,typename TagList2,typename Category2,
1495 : typename AugmentPolicy2
1496 : >
1497 : bool operator>(
1498 : const ordered_index<
1499 : KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x,
1500 : const ordered_index<
1501 : KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y)
1502 : {
1503 : return y<x;
1504 : }
1505 :
1506 : template<
1507 : typename KeyFromValue1,typename Compare1,
1508 : typename SuperMeta1,typename TagList1,typename Category1,
1509 : typename AugmentPolicy1,
1510 : typename KeyFromValue2,typename Compare2,
1511 : typename SuperMeta2,typename TagList2,typename Category2,
1512 : typename AugmentPolicy2
1513 : >
1514 : bool operator>=(
1515 : const ordered_index<
1516 : KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x,
1517 : const ordered_index<
1518 : KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y)
1519 : {
1520 : return !(x<y);
1521 : }
1522 :
1523 : template<
1524 : typename KeyFromValue1,typename Compare1,
1525 : typename SuperMeta1,typename TagList1,typename Category1,
1526 : typename AugmentPolicy1,
1527 : typename KeyFromValue2,typename Compare2,
1528 : typename SuperMeta2,typename TagList2,typename Category2,
1529 : typename AugmentPolicy2
1530 : >
1531 : bool operator<=(
1532 : const ordered_index<
1533 : KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1,AugmentPolicy1>& x,
1534 : const ordered_index<
1535 : KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2,AugmentPolicy2>& y)
1536 : {
1537 : return !(x>y);
1538 : }
1539 :
1540 : /* specialized algorithms */
1541 :
1542 : template<
1543 : typename KeyFromValue,typename Compare,
1544 : typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
1545 : >
1546 : void swap(
1547 : ordered_index<
1548 : KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x,
1549 : ordered_index<
1550 : KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& y)
1551 : {
1552 : x.swap(y);
1553 : }
1554 :
1555 : } /* namespace multi_index::detail */
1556 :
1557 : } /* namespace multi_index */
1558 :
1559 : } /* namespace boost */
1560 :
1561 : /* Boost.Foreach compatibility */
1562 :
1563 : template<
1564 : typename KeyFromValue,typename Compare,
1565 : typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
1566 : >
1567 : inline boost::mpl::true_* boost_foreach_is_noncopyable(
1568 : boost::multi_index::detail::ordered_index<
1569 : KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>*&,
1570 : boost_foreach_argument_dependent_lookup_hack)
1571 : {
1572 : return 0;
1573 : }
1574 :
1575 : #undef BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT
1576 : #undef BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF
1577 :
1578 : #endif
|
