Line data Source code
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 :
100 : namespace boost{
101 :
102 : namespace multi_index{
103 :
104 : namespace 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 :
115 : struct ordered_unique_tag{};
116 : struct 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 :
123 : template<
124 : typename KeyFromValue,typename Compare,
125 : typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
126 : >
127 : class ordered_index;
128 :
129 : template<
130 : typename KeyFromValue,typename Compare,
131 : typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
132 : >
133 : class 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 :
154 : protected:
155 : typedef ordered_index_node<
156 : AugmentPolicy,typename super::index_node_type> index_node_type;
157 :
158 : protected: /* 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 :
162 : public:
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 :
185 : private:
186 : typedef allocator_traits<allocator_type> alloc_traits;
187 :
188 : public:
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 :
202 : protected:
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 :
226 : protected:
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 :
240 : public:
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 298 : begin()BOOST_NOEXCEPT{return make_iterator(leftmost());}
257 : const_iterator
258 24517 : begin()const BOOST_NOEXCEPT{return make_iterator(leftmost());}
259 : iterator
260 731670 : end()BOOST_NOEXCEPT{return make_iterator(header());}
261 : const_iterator
262 29111 : 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 24538 : 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 1162 : std::pair<iterator,bool> insert(const value_type& x)
307 : {
308 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
309 1162 : std::pair<final_node_type*,bool> p=this->final_insert_(x);
310 1162 : 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 1159 : 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 1159 : this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
397 1159 : return position;
398 : }
399 :
400 2035 : size_type erase(key_param_type x)
401 : {
402 : BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
403 2035 : std::pair<iterator,iterator> p=equal_range(x);
404 2035 : size_type s=0;
405 3186 : while(p.first!=p.second){
406 1151 : p.first=erase(p.first);
407 1151 : ++s;
408 : }
409 2035 : 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 731317 : 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 731317 : return this->final_modify_(
464 731317 : 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 731317 : iterator find(const CompatibleKey& x)const
610 : {
611 731317 : 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 2181 : size_type count(const CompatibleKey& x)const
623 : {
624 2181 : return count(x,comp_);
625 : }
626 :
627 : template<typename CompatibleKey,typename CompatibleCompare>
628 2181 : size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const
629 : {
630 2181 : std::pair<iterator,iterator> p=equal_range(x,comp);
631 2181 : size_type n=static_cast<size_type>(std::distance(p.first,p.second));
632 2181 : 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 2035 : std::pair<iterator,iterator> equal_range(
680 : const CompatibleKey& x)const
681 : {
682 : std::pair<index_node_type*,index_node_type*> p=
683 2035 : ordered_index_equal_range(root(),header(),key,x,comp_);
684 2035 : return std::pair<iterator,iterator>(
685 2035 : make_iterator(p.first),make_iterator(p.second));
686 : }
687 :
688 : template<typename CompatibleKey,typename CompatibleCompare>
689 2181 : 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 2181 : ordered_index_equal_range(root(),header(),key,x,comp);
694 2181 : return std::pair<iterator,iterator>(
695 2181 : 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 :
721 : BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
722 120371 : ordered_index_impl(const ctor_args_list& args_list,const allocator_type& al):
723 120371 : super(args_list.get_tail(),al),
724 120371 : key(tuples::get<0>(args_list.get_head())),
725 120371 : 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 120371 : empty_initialize();
733 120371 : }
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 120371 : ~ordered_index_impl()
769 : {
770 : /* the container is guaranteed to be empty by now */
771 120371 : }
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 733130 : iterator make_iterator(index_node_type* node){return iterator(node);}
780 793377 : const_iterator make_iterator(index_node_type* node)const
781 793377 : {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 83036 : final_node_type* insert_(
844 : value_param_type v,final_node_type*& x,Variant variant)
845 : {
846 83036 : link_info inf;
847 83036 : if(!link_point(key(v),inf,Category())){
848 0 : return static_cast<final_node_type*>(
849 0 : index_node_type::from_impl(inf.pos));
850 : }
851 :
852 83036 : final_node_type* res=super::insert_(v,x,variant);
853 83036 : if(res==x){
854 83036 : node_impl_type::link(
855 83036 : static_cast<index_node_type*>(x)->impl(),
856 83036 : inf.side,inf.pos,header()->impl());
857 83036 : }
858 83036 : return res;
859 83036 : }
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 76421 : void extract_(index_node_type* x,Dst dst)
883 : {
884 76421 : node_impl_type::rebalance_for_extract(
885 76421 : x->impl(),header()->parent(),header()->left(),header()->right());
886 76421 : super::extract_(x,dst.next());
887 :
888 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
889 : transfer_iterators(dst.get(),x);
890 : #endif
891 76421 : }
892 :
893 24517 : void delete_all_nodes_()
894 : {
895 24517 : delete_all_nodes(root());
896 24517 : }
897 :
898 71373 : void clear_()
899 : {
900 71373 : super::clear_();
901 71373 : empty_initialize();
902 :
903 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
904 : safe.detach_dereferenceable_iterators();
905 : #endif
906 71373 : }
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 4571111 : bool modify_(index_node_type* x)
965 : {
966 : bool b;
967 : BOOST_TRY{
968 4571111 : b=in_place(x->value(),x,Category());
969 4571111 : }
970 : BOOST_CATCH(...){
971 0 : extract_(x,invalidate_iterators());
972 0 : BOOST_RETHROW;
973 0 : }
974 : BOOST_CATCH_END
975 4571111 : if(!b){
976 1030905 : node_impl_type::rebalance_for_extract(
977 1030905 : x->impl(),header()->parent(),header()->left(),header()->right());
978 : BOOST_TRY{
979 1030905 : link_info inf;
980 1030905 : if(!link_point(key(x->value()),inf,Category())){
981 0 : super::extract_(x,invalidate_iterators());
982 :
983 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
984 : detach_iterators(x);
985 : #endif
986 0 : return false;
987 : }
988 1030905 : node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
989 1030905 : }
990 : BOOST_CATCH(...){
991 0 : super::extract_(x,invalidate_iterators());
992 :
993 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
994 : detach_iterators(x);
995 : #endif
996 :
997 0 : BOOST_RETHROW;
998 0 : }
999 : BOOST_CATCH_END
1000 1030905 : }
1001 :
1002 : BOOST_TRY{
1003 4571111 : if(!super::modify_(x)){
1004 0 : node_impl_type::rebalance_for_extract(
1005 0 : 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 0 : return false;
1012 : }
1013 4571111 : else return true;
1014 0 : }
1015 : BOOST_CATCH(...){
1016 0 : node_impl_type::rebalance_for_extract(
1017 0 : 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 0 : BOOST_RETHROW;
1024 0 : }
1025 : BOOST_CATCH_END
1026 4571111 : }
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 :
1129 : protected: /* for the benefit of AugmentPolicy::augmented_interface */
1130 18226944 : index_node_type* header()const
1131 18226944 : {return this->final_header();}
1132 1873991 : index_node_type* root()const
1133 1873991 : {return index_node_type::from_impl(header()->parent());}
1134 4596513 : index_node_type* leftmost()const
1135 4596513 : {return index_node_type::from_impl(header()->left());}
1136 : index_node_type* rightmost()const
1137 : {return index_node_type::from_impl(header()->right());}
1138 :
1139 : private:
1140 191744 : void empty_initialize()
1141 : {
1142 191744 : header()->color()=red;
1143 : /* used to distinguish header() from root, in iterator.operator++ */
1144 :
1145 191744 : header()->parent()=node_impl_pointer(0);
1146 191744 : header()->left()=header()->impl();
1147 191744 : header()->right()=header()->impl();
1148 191744 : }
1149 :
1150 : struct link_info
1151 : {
1152 : /* coverity[uninit_ctor]: suppress warning */
1153 2227882 : link_info():side(to_left){}
1154 :
1155 : ordered_index_side side;
1156 : node_impl_pointer pos;
1157 : };
1158 :
1159 1162 : bool link_point(key_param_type k,link_info& inf,ordered_unique_tag)
1160 : {
1161 1162 : index_node_type* y=header();
1162 1162 : index_node_type* x=root();
1163 1162 : bool c=true;
1164 10261 : while(x){
1165 9099 : y=x;
1166 9099 : c=comp_(k,key(x->value()));
1167 9099 : x=index_node_type::from_impl(c?x->left():x->right());
1168 : }
1169 1162 : index_node_type* yy=y;
1170 1162 : if(c){
1171 587 : if(yy==leftmost()){
1172 19 : inf.side=to_left;
1173 19 : inf.pos=y->impl();
1174 19 : return true;
1175 : }
1176 568 : else index_node_type::decrement(yy);
1177 568 : }
1178 :
1179 1143 : if(comp_(key(yy->value()),k)){
1180 1143 : inf.side=c?to_left:to_right;
1181 1143 : inf.pos=y->impl();
1182 1143 : return true;
1183 : }
1184 : else{
1185 0 : inf.pos=yy->impl();
1186 0 : return false;
1187 : }
1188 1162 : }
1189 :
1190 1112779 : bool link_point(key_param_type k,link_info& inf,ordered_non_unique_tag)
1191 : {
1192 1112779 : index_node_type* y=header();
1193 1112779 : index_node_type* x=root();
1194 1112779 : bool c=true;
1195 13728281 : while (x){
1196 12615502 : y=x;
1197 12615502 : c=comp_(k,key(x->value()));
1198 12615502 : x=index_node_type::from_impl(c?x->left():x->right());
1199 : }
1200 1112779 : inf.side=c?to_left:to_right;
1201 1112779 : inf.pos=y->impl();
1202 1112779 : 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 24523 : void delete_all_nodes(index_node_type* x)
1302 : {
1303 24523 : if(!x)return;
1304 :
1305 3 : delete_all_nodes(index_node_type::from_impl(x->left()));
1306 3 : delete_all_nodes(index_node_type::from_impl(x->right()));
1307 3 : this->final_delete_node_(static_cast<final_node_type*>(x));
1308 24523 : }
1309 :
1310 731317 : bool in_place(value_param_type v,index_node_type* x,ordered_unique_tag)const
1311 : {
1312 : index_node_type* y;
1313 731317 : if(x!=leftmost()){
1314 729301 : y=x;
1315 729301 : index_node_type::decrement(y);
1316 729301 : if(!comp_(key(y->value()),key(v)))return false;
1317 729301 : }
1318 :
1319 731317 : y=x;
1320 731317 : index_node_type::increment(y);
1321 731317 : return y==header()||comp_(key(v),key(y->value()));
1322 731317 : }
1323 :
1324 3839794 : bool in_place(
1325 : value_param_type v,index_node_type* x,ordered_non_unique_tag)const
1326 : {
1327 : index_node_type* y;
1328 3839794 : if(x!=leftmost()){
1329 3819630 : y=x;
1330 3819630 : index_node_type::decrement(y);
1331 3819630 : if(comp_(key(v),key(y->value())))return false;
1332 2808321 : }
1333 :
1334 2828485 : y=x;
1335 2828485 : index_node_type::increment(y);
1336 2828485 : return y==header()||!comp_(key(y->value()),key(v));
1337 3839794 : }
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(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 :
1523 : protected: /* 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 :
1537 : template<
1538 : typename KeyFromValue,typename Compare,
1539 : typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
1540 : >
1541 : class 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;
1555 : public:
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 :
1580 : protected:
1581 120371 : ordered_index(
1582 : const ctor_args_list& args_list,const allocator_type& al):
1583 120371 : 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 :
1597 : template<
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 : >
1605 : bool 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 :
1614 : template<
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 : >
1622 : bool 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 :
1631 : template<
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 : >
1639 : bool 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 :
1648 : template<
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 : >
1656 : bool 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 :
1665 : template<
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 : >
1673 : bool 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 :
1682 : template<
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 : >
1690 : bool 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 :
1701 : template<
1702 : typename KeyFromValue,typename Compare,
1703 : typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
1704 : >
1705 : void 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 :
1722 : namespace boost{
1723 : namespace foreach{
1724 :
1725 : template<typename>
1726 : struct is_noncopyable;
1727 :
1728 : template<
1729 : typename KeyFromValue,typename Compare,
1730 : typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
1731 : >
1732 : struct 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
|
