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

source code of boost/libs/multi_index/include/boost/multi_index/detail/ord_index_impl.hpp