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