1 /* Copyright 2003-2007 Joaquín M López Muñoz.
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)
6 * See http://www.boost.org/libs/multi_index for library home page.
8 * The internal implementation of red-black trees is based on that of SGI STL
11 * Copyright (c) 1996,1997
12 * Silicon Graphics Computer Systems, Inc.
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.
24 * Hewlett-Packard Company
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.
36 #ifndef BOOST_MULTI_INDEX_ORDERED_INDEX_HPP
37 #define BOOST_MULTI_INDEX_ORDERED_INDEX_HPP
39 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
43 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
45 #include <boost/call_traits.hpp>
46 #include <boost/detail/no_exceptions_support.hpp>
47 #include <boost/detail/workaround.hpp>
48 #include <boost/iterator/reverse_iterator.hpp>
49 #include <boost/mpl/if.hpp>
50 #include <boost/mpl/push_front.hpp>
51 #include <boost/multi_index/detail/access_specifier.hpp>
52 #include <boost/multi_index/detail/bidir_node_iterator.hpp>
53 #include <boost/multi_index/detail/index_node_base.hpp>
54 #include <boost/multi_index/detail/modify_key_adaptor.hpp>
55 #include <boost/multi_index/detail/ord_index_node.hpp>
56 #include <boost/multi_index/detail/ord_index_ops.hpp>
57 #include <boost/multi_index/detail/safe_ctr_proxy.hpp>
58 #include <boost/multi_index/detail/safe_mode.hpp>
59 #include <boost/multi_index/detail/scope_guard.hpp>
60 #include <boost/multi_index/detail/unbounded.hpp>
61 #include <boost/multi_index/detail/value_compare.hpp>
62 #include <boost/multi_index/ordered_index_fwd.hpp>
63 #include <boost/ref.hpp>
64 #include <boost/tuple/tuple.hpp>
65 #include <boost/type_traits/is_same.hpp>
68 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
69 #include <boost/archive/archive_exception.hpp>
70 #include <boost/bind.hpp>
71 #include <boost/multi_index/detail/duplicates_iterator.hpp>
72 #include <boost/throw_exception.hpp>
75 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
76 #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT \
77 detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \
78 detail::make_obj_guard(*this,&ordered_index::check_invariant_); \
79 BOOST_JOIN(check_invariant_,__LINE__).touch();
81 #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT
86 namespace multi_index{
90 /* ordered_index adds a layer of ordered indexing to a given Super */
92 /* Most of the implementation of unique and non-unique indices is
93 * shared. We tell from one another on instantiation time by using
97 struct ordered_unique_tag{};
98 struct ordered_non_unique_tag{};
101 typename KeyFromValue,typename Compare,
102 typename SuperMeta,typename TagList,typename Category
105 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
107 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
108 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
109 ,public safe_ctr_proxy_impl<
111 ordered_index_node<typename SuperMeta::type::node_type> >,
112 ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category> >
114 ,public safe_mode::safe_container<
115 ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category> >
120 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
121 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
122 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
123 * lifetime of const references bound to temporaries --precisely what
127 #pragma parse_mfunc_templ off
130 typedef typename SuperMeta::type super;
133 typedef ordered_index_node<
134 typename super::node_type> node_type;
137 typedef typename node_type::impl_type node_impl_type;
138 typedef typename node_impl_type::pointer node_impl_pointer;
143 typedef typename KeyFromValue::result_type key_type;
144 typedef typename node_type::value_type value_type;
145 typedef KeyFromValue key_from_value;
146 typedef Compare key_compare;
147 typedef value_comparison<
148 value_type,KeyFromValue,Compare> value_compare;
149 typedef tuple<key_from_value,key_compare> ctor_args;
150 typedef typename super::final_allocator_type allocator_type;
151 typedef typename allocator_type::reference reference;
152 typedef typename allocator_type::const_reference const_reference;
154 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
155 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
156 typedef safe_mode::safe_iterator<
157 bidir_node_iterator<node_type>,
159 bidir_node_iterator<node_type> > > iterator;
161 typedef safe_mode::safe_iterator<
162 bidir_node_iterator<node_type>,
163 ordered_index> iterator;
166 typedef bidir_node_iterator<node_type> iterator;
169 typedef iterator const_iterator;
171 typedef std::size_t size_type;
172 typedef std::ptrdiff_t difference_type;
173 typedef typename allocator_type::pointer pointer;
174 typedef typename allocator_type::const_pointer const_pointer;
176 boost::reverse_iterator<iterator> reverse_iterator;
178 boost::reverse_iterator<const_iterator> const_reverse_iterator;
179 typedef TagList tag_list;
182 typedef typename super::final_node_type final_node_type;
183 typedef tuples::cons<
185 typename super::ctor_args_list> ctor_args_list;
186 typedef typename mpl::push_front<
187 typename super::index_type_list,
188 ordered_index>::type index_type_list;
189 typedef typename mpl::push_front<
190 typename super::iterator_type_list,
191 iterator>::type iterator_type_list;
192 typedef typename mpl::push_front<
193 typename super::const_iterator_type_list,
194 const_iterator>::type const_iterator_type_list;
195 typedef typename super::copy_map_type copy_map_type;
197 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
198 typedef typename super::index_saver_type index_saver_type;
199 typedef typename super::index_loader_type index_loader_type;
203 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
204 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
205 typedef safe_ctr_proxy_impl<
206 bidir_node_iterator<node_type>,
207 ordered_index> safe_super;
209 typedef safe_mode::safe_container<ordered_index> safe_super;
213 typedef typename call_traits<
214 value_type>::param_type value_param_type;
215 typedef typename call_traits<
216 key_type>::param_type key_param_type;
220 /* construct/copy/destroy
221 * Default and copy ctors are in the protected section as indices are
222 * not supposed to be created on their own. No range ctor either.
225 ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& operator=(
226 const ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x)
228 this->final()=x.final();
232 allocator_type get_allocator()const
234 return this->final().get_allocator();
239 iterator begin(){return make_iterator(leftmost());}
240 const_iterator begin()const{return make_iterator(leftmost());}
241 iterator end(){return make_iterator(header());}
242 const_iterator end()const{return make_iterator(header());}
243 reverse_iterator rbegin(){return make_reverse_iterator(end());}
244 const_reverse_iterator rbegin()const{return make_reverse_iterator(end());}
245 reverse_iterator rend(){return make_reverse_iterator(begin());}
246 const_reverse_iterator rend()const{return make_reverse_iterator(begin());}
247 const_iterator cbegin()const{return begin();}
248 const_iterator cend()const{return end();}
249 const_reverse_iterator crbegin()const{return rbegin();}
250 const_reverse_iterator crend()const{return rend();}
252 iterator iterator_to(const value_type& x)
254 return make_iterator(node_from_value<node_type>(&x));
257 const_iterator iterator_to(const value_type& x)const
259 return make_iterator(node_from_value<node_type>(&x));
264 bool empty()const{return this->final_empty_();}
265 size_type size()const{return this->final_size_();}
266 size_type max_size()const{return this->final_max_size_();}
270 std::pair<iterator,bool> insert(value_param_type x)
272 BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
273 std::pair<final_node_type*,bool> p=this->final_insert_(x);
274 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
277 iterator insert(iterator position,value_param_type x)
279 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
280 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
281 BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
282 std::pair<final_node_type*,bool> p=this->final_insert_(
283 x,static_cast<final_node_type*>(position.get_node()));
284 return make_iterator(p.first);
287 template<typename InputIterator>
288 void insert(InputIterator first,InputIterator last)
290 BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
292 for(;first!=last;++first)hint=insert(hint,*first);
295 iterator erase(iterator position)
297 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
298 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
299 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
300 BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
301 this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
305 size_type erase(key_param_type x)
307 BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
308 std::pair<iterator,iterator> p=equal_range(x);
310 while(p.first!=p.second){
311 p.first=erase(p.first);
317 iterator erase(iterator first,iterator last)
319 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
320 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
321 BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
322 BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
323 BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
324 BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
331 bool replace(iterator position,value_param_type x)
333 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
334 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
335 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
336 BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
337 return this->final_replace_(
338 x,static_cast<final_node_type*>(position.get_node()));
341 template<typename Modifier>
342 bool modify(iterator position,Modifier mod)
344 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
345 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
346 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
347 BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
349 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
350 /* MSVC++ 6.0 optimizer on safe mode code chokes if this
351 * this is not added. Left it for all compilers as it does no
358 return this->final_modify_(
359 mod,static_cast<final_node_type*>(position.get_node()));
362 template<typename Modifier,typename Rollback>
363 bool modify(iterator position,Modifier mod,Rollback back)
365 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
366 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
367 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
368 BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
370 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
371 /* MSVC++ 6.0 optimizer on safe mode code chokes if this
372 * this is not added. Left it for all compilers as it does no
379 return this->final_modify_(
380 mod,back,static_cast<final_node_type*>(position.get_node()));
383 template<typename Modifier>
384 bool modify_key(iterator position,Modifier mod)
386 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
387 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
388 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
389 BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
391 position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
394 template<typename Modifier,typename Rollback>
395 bool modify_key(iterator position,Modifier mod,Rollback back)
397 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
398 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
399 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
400 BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
403 modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key),
404 modify_key_adaptor<Modifier,value_type,KeyFromValue>(back,key));
407 void swap(ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x)
409 BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
410 this->final_swap_(x.final());
415 BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
416 this->final_clear_();
421 key_from_value key_extractor()const{return key;}
422 key_compare key_comp()const{return comp;}
423 value_compare value_comp()const{return value_compare(key,comp);}
427 /* Internally, these ops rely on const_iterator being the same
431 template<typename CompatibleKey>
432 iterator find(const CompatibleKey& x)const
434 return make_iterator(ordered_index_find(root(),header(),key,x,comp));
437 template<typename CompatibleKey,typename CompatibleCompare>
439 const CompatibleKey& x,const CompatibleCompare& comp)const
441 return make_iterator(ordered_index_find(root(),header(),key,x,comp));
444 template<typename CompatibleKey>
445 size_type count(const CompatibleKey& x)const
447 return count(x,comp);
450 template<typename CompatibleKey,typename CompatibleCompare>
451 size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const
453 std::pair<iterator,iterator> p=equal_range(x,comp);
454 size_type n=std::distance(p.first,p.second);
458 template<typename CompatibleKey>
459 iterator lower_bound(const CompatibleKey& x)const
461 return make_iterator(
462 ordered_index_lower_bound(root(),header(),key,x,comp));
465 template<typename CompatibleKey,typename CompatibleCompare>
466 iterator lower_bound(
467 const CompatibleKey& x,const CompatibleCompare& comp)const
469 return make_iterator(
470 ordered_index_lower_bound(root(),header(),key,x,comp));
473 template<typename CompatibleKey>
474 iterator upper_bound(const CompatibleKey& x)const
476 return make_iterator(
477 ordered_index_upper_bound(root(),header(),key,x,comp));
480 template<typename CompatibleKey,typename CompatibleCompare>
481 iterator upper_bound(
482 const CompatibleKey& x,const CompatibleCompare& comp)const
484 return make_iterator(
485 ordered_index_upper_bound(root(),header(),key,x,comp));
488 template<typename CompatibleKey>
489 std::pair<iterator,iterator> equal_range(
490 const CompatibleKey& x)const
492 std::pair<node_type*,node_type*> p=
493 ordered_index_equal_range(root(),header(),key,x,comp);
494 return std::pair<iterator,iterator>(
495 make_iterator(p.first),make_iterator(p.second));
498 template<typename CompatibleKey,typename CompatibleCompare>
499 std::pair<iterator,iterator> equal_range(
500 const CompatibleKey& x,const CompatibleCompare& comp)const
502 std::pair<node_type*,node_type*> p=
503 ordered_index_equal_range(root(),header(),key,x,comp);
504 return std::pair<iterator,iterator>(
505 make_iterator(p.first),make_iterator(p.second));
510 template<typename LowerBounder,typename UpperBounder>
511 std::pair<iterator,iterator>
512 range(LowerBounder lower,UpperBounder upper)const
514 typedef typename mpl::if_<
515 is_same<LowerBounder,unbounded_type>,
516 BOOST_DEDUCED_TYPENAME mpl::if_<
517 is_same<UpperBounder,unbounded_type>,
521 BOOST_DEDUCED_TYPENAME mpl::if_<
522 is_same<UpperBounder,unbounded_type>,
528 return range(lower,upper,dispatch());
531 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
532 ordered_index(const ctor_args_list& args_list,const allocator_type& al):
533 super(args_list.get_tail(),al),
534 key(tuples::get<0>(args_list.get_head())),
535 comp(tuples::get<1>(args_list.get_head()))
541 const ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x):
544 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
551 /* Copy ctor just takes the key and compare objects from x. The rest is
552 * done in subsequent call to copy_().
558 /* the container is guaranteed to be empty by now */
561 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
562 iterator make_iterator(node_type* node){return iterator(node,this);}
563 const_iterator make_iterator(node_type* node)const
564 {return const_iterator(node,const_cast<ordered_index*>(this));}
566 iterator make_iterator(node_type* node){return iterator(node);}
567 const_iterator make_iterator(node_type* node)const
568 {return const_iterator(node);}
572 const ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x,
573 const copy_map_type& map)
579 header()->color()=x.header()->color();
581 node_type* root_cpy=map.find(static_cast<final_node_type*>(x.root()));
582 header()->parent()=root_cpy->impl();
584 node_type* leftmost_cpy=map.find(
585 static_cast<final_node_type*>(x.leftmost()));
586 header()->left()=leftmost_cpy->impl();
588 node_type* rightmost_cpy=map.find(
589 static_cast<final_node_type*>(x.rightmost()));
590 header()->right()=rightmost_cpy->impl();
592 typedef typename copy_map_type::const_iterator copy_map_iterator;
593 for(copy_map_iterator it=map.begin(),it_end=map.end();it!=it_end;++it){
594 node_type* org=it->first;
595 node_type* cpy=it->second;
597 cpy->color()=org->color();
599 node_impl_pointer parent_org=org->parent();
600 if(parent_org==node_impl_pointer(0))cpy->parent()=node_impl_pointer(0);
602 node_type* parent_cpy=map.find(
603 static_cast<final_node_type*>(node_type::from_impl(parent_org)));
604 cpy->parent()=parent_cpy->impl();
605 if(parent_org->left()==org->impl()){
606 parent_cpy->left()=cpy->impl();
608 else if(parent_org->right()==org->impl()){
609 /* header() does not satisfy this nor the previous check */
610 parent_cpy->right()=cpy->impl();
614 if(org->left()==node_impl_pointer(0))
615 cpy->left()=node_impl_pointer(0);
616 if(org->right()==node_impl_pointer(0))
617 cpy->right()=node_impl_pointer(0);
624 node_type* insert_(value_param_type v,node_type* x)
627 if(!link_point(key(v),inf,Category())){
628 return node_type::from_impl(inf.pos);
631 node_type* res=static_cast<node_type*>(super::insert_(v,x));
633 node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
638 node_type* insert_(value_param_type v,node_type* position,node_type* x)
641 if(!hinted_link_point(key(v),position,inf,Category())){
642 return node_type::from_impl(inf.pos);
645 node_type* res=static_cast<node_type*>(super::insert_(v,position,x));
647 node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
652 void erase_(node_type* x)
654 node_impl_type::rebalance_for_erase(
655 x->impl(),header()->parent(),header()->left(),header()->right());
658 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
663 void delete_all_nodes_()
665 delete_all_nodes(root());
673 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
674 safe_super::detach_dereferenceable_iterators();
678 void swap_(ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x)
680 std::swap(key,x.key);
681 std::swap(comp,x.comp);
683 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
690 bool replace_(value_param_type v,node_type* x)
692 if(in_place(v,x,Category())){
693 return super::replace_(v,x);
697 node_type::increment(next);
699 node_impl_type::rebalance_for_erase(
700 x->impl(),header()->parent(),header()->left(),header()->right());
704 if(link_point(key(v),inf,Category())&&super::replace_(v,x)){
705 node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
708 node_impl_type::restore(x->impl(),next->impl(),header()->impl());
712 node_impl_type::restore(x->impl(),next->impl(),header()->impl());
718 bool modify_(node_type* x)
722 b=in_place(x->value(),x,Category());
730 node_impl_type::rebalance_for_erase(
731 x->impl(),header()->parent(),header()->left(),header()->right());
734 if(!link_point(key(x->value()),inf,Category())){
737 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
742 node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
747 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
757 if(!super::modify_(x)){
758 node_impl_type::rebalance_for_erase(
759 x->impl(),header()->parent(),header()->left(),header()->right());
761 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
770 node_impl_type::rebalance_for_erase(
771 x->impl(),header()->parent(),header()->left(),header()->right());
773 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
782 bool modify_rollback_(node_type* x)
784 if(in_place(x->value(),x,Category())){
785 return super::modify_rollback_(x);
789 node_type::increment(next);
791 node_impl_type::rebalance_for_erase(
792 x->impl(),header()->parent(),header()->left(),header()->right());
796 if(link_point(key(x->value()),inf,Category())&&
797 super::modify_rollback_(x)){
798 node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
801 node_impl_type::restore(x->impl(),next->impl(),header()->impl());
805 node_impl_type::restore(x->impl(),next->impl(),header()->impl());
811 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
814 template<typename Archive>
816 Archive& ar,const unsigned int version,const index_saver_type& sm)const
818 save_(ar,version,sm,Category());
821 template<typename Archive>
822 void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
824 load_(ar,version,lm,Category());
828 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
829 /* invariant stuff */
831 bool invariant_()const
833 if(size()==0||begin()==end()){
834 if(size()!=0||begin()!=end()||
835 header()->left()!=header()->impl()||
836 header()->right()!=header()->impl())return false;
839 if((size_type)std::distance(begin(),end())!=size())return false;
841 std::size_t len=node_impl_type::black_count(
842 leftmost()->impl(),root()->impl());
843 for(const_iterator it=begin(),it_end=end();it!=it_end;++it){
844 node_type* x=it.get_node();
845 node_type* left_x=node_type::from_impl(x->left());
846 node_type* right_x=node_type::from_impl(x->right());
849 if((left_x&&left_x->color()==red)||
850 (right_x&&right_x->color()==red))return false;
852 if(left_x&&comp(key(x->value()),key(left_x->value())))return false;
853 if(right_x&&comp(key(right_x->value()),key(x->value())))return false;
854 if(!left_x&&!right_x&&
855 node_impl_type::black_count(x->impl(),root()->impl())!=len)
859 if(leftmost()->impl()!=node_impl_type::minimum(root()->impl()))
861 if(rightmost()->impl()!=node_impl_type::maximum(root()->impl()))
865 return super::invariant_();
869 /* This forwarding function eases things for the boost::mem_fn construct
870 * in BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT. Actually,
871 * final_check_invariant is already an inherited member function of
874 void check_invariant_()const{this->final_check_invariant_();}
878 node_type* header()const{return this->final_header();}
879 node_type* root()const{return node_type::from_impl(header()->parent());}
880 node_type* leftmost()const{return node_type::from_impl(header()->left());}
881 node_type* rightmost()const{return node_type::from_impl(header()->right());}
883 void empty_initialize()
885 header()->color()=red;
886 /* used to distinguish header() from root, in iterator.operator++ */
888 header()->parent()=node_impl_pointer(0);
889 header()->left()=header()->impl();
890 header()->right()=header()->impl();
895 link_info():side(to_left){}
897 ordered_index_side side;
898 node_impl_pointer pos;
901 bool link_point(key_param_type k,link_info& inf,ordered_unique_tag)
903 node_type* y=header();
908 c=comp(k,key(x->value()));
909 x=node_type::from_impl(c?x->left():x->right());
918 else node_type::decrement(yy);
921 if(comp(key(yy->value()),k)){
922 inf.side=c?to_left:to_right;
932 bool link_point(key_param_type k,link_info& inf,ordered_non_unique_tag)
934 node_type* y=header();
939 c=comp(k,key(x->value()));
940 x=node_type::from_impl(c?x->left():x->right());
942 inf.side=c?to_left:to_right;
947 bool lower_link_point(key_param_type k,link_info& inf,ordered_non_unique_tag)
949 node_type* y=header();
954 c=comp(key(x->value()),k);
955 x=node_type::from_impl(c?x->right():x->left());
957 inf.side=c?to_right:to_left;
962 bool hinted_link_point(
963 key_param_type k,node_type* position,link_info& inf,ordered_unique_tag)
965 if(position->impl()==header()->left()){
966 if(size()>0&&comp(k,key(position->value()))){
968 inf.pos=position->impl();
971 else return link_point(k,inf,ordered_unique_tag());
973 else if(position==header()){
974 if(comp(key(rightmost()->value()),k)){
976 inf.pos=rightmost()->impl();
979 else return link_point(k,inf,ordered_unique_tag());
982 node_type* before=position;
983 node_type::decrement(before);
984 if(comp(key(before->value()),k)&&comp(k,key(position->value()))){
985 if(before->right()==node_impl_pointer(0)){
987 inf.pos=before->impl();
992 inf.pos=position->impl();
996 else return link_point(k,inf,ordered_unique_tag());
1000 bool hinted_link_point(
1001 key_param_type k,node_type* position,link_info& inf,ordered_non_unique_tag)
1003 if(position->impl()==header()->left()){
1004 if(size()>0&&!comp(key(position->value()),k)){
1006 inf.pos=position->impl();
1009 else return lower_link_point(k,inf,ordered_non_unique_tag());
1011 else if(position==header()){
1012 if(!comp(k,key(rightmost()->value()))){
1014 inf.pos=rightmost()->impl();
1017 else return link_point(k,inf,ordered_non_unique_tag());
1020 node_type* before=position;
1021 node_type::decrement(before);
1022 if(!comp(k,key(before->value()))){
1023 if(!comp(key(position->value()),k)){
1024 if(before->right()==node_impl_pointer(0)){
1026 inf.pos=before->impl();
1031 inf.pos=position->impl();
1035 else return lower_link_point(k,inf,ordered_non_unique_tag());
1037 else return link_point(k,inf,ordered_non_unique_tag());
1041 void delete_all_nodes(node_type* x)
1045 delete_all_nodes(node_type::from_impl(x->left()));
1046 delete_all_nodes(node_type::from_impl(x->right()));
1047 this->final_delete_node_(static_cast<final_node_type*>(x));
1050 bool in_place(value_param_type v,node_type* x,ordered_unique_tag)
1055 node_type::decrement(y);
1056 if(!comp(key(y->value()),key(v)))return false;
1060 node_type::increment(y);
1061 return y==header()||comp(key(v),key(y->value()));
1064 bool in_place(value_param_type v,node_type* x,ordered_non_unique_tag)
1069 node_type::decrement(y);
1070 if(comp(key(v),key(y->value())))return false;
1074 node_type::increment(y);
1075 return y==header()||!comp(key(y->value()),key(v));
1078 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1079 void detach_iterators(node_type* x)
1081 iterator it=make_iterator(x);
1082 safe_mode::detach_equivalent_iterators(it);
1086 template<typename LowerBounder,typename UpperBounder>
1087 std::pair<iterator,iterator>
1088 range(LowerBounder lower,UpperBounder upper,none_unbounded_tag)const
1090 node_type* y=header();
1091 node_type* z=root();
1094 if(!lower(key(z->value()))){
1095 z=node_type::from_impl(z->right());
1097 else if(!upper(key(z->value()))){
1099 z=node_type::from_impl(z->left());
1102 return std::pair<iterator,iterator>(
1104 lower_range(node_type::from_impl(z->left()),z,lower)),
1106 upper_range(node_type::from_impl(z->right()),y,upper)));
1110 return std::pair<iterator,iterator>(make_iterator(y),make_iterator(y));
1113 template<typename LowerBounder,typename UpperBounder>
1114 std::pair<iterator,iterator>
1115 range(LowerBounder,UpperBounder upper,lower_unbounded_tag)const
1117 return std::pair<iterator,iterator>(
1119 make_iterator(upper_range(root(),header(),upper)));
1122 template<typename LowerBounder,typename UpperBounder>
1123 std::pair<iterator,iterator>
1124 range(LowerBounder lower,UpperBounder,upper_unbounded_tag)const
1126 return std::pair<iterator,iterator>(
1127 make_iterator(lower_range(root(),header(),lower)),
1131 template<typename LowerBounder,typename UpperBounder>
1132 std::pair<iterator,iterator>
1133 range(LowerBounder,UpperBounder,both_unbounded_tag)const
1135 return std::pair<iterator,iterator>(begin(),end());
1138 template<typename LowerBounder>
1139 node_type * lower_range(node_type* top,node_type* y,LowerBounder lower)const
1142 if(lower(key(top->value()))){
1144 top=node_type::from_impl(top->left());
1146 else top=node_type::from_impl(top->right());
1152 template<typename UpperBounder>
1153 node_type * upper_range(node_type* top,node_type* y,UpperBounder upper)const
1156 if(!upper(key(top->value()))){
1158 top=node_type::from_impl(top->left());
1160 else top=node_type::from_impl(top->right());
1166 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1167 template<typename Archive>
1169 Archive& ar,const unsigned int version,const index_saver_type& sm,
1170 ordered_unique_tag)const
1172 super::save_(ar,version,sm);
1175 template<typename Archive>
1177 Archive& ar,const unsigned int version,const index_loader_type& lm,
1180 super::load_(ar,version,lm);
1183 template<typename Archive>
1185 Archive& ar,const unsigned int version,const index_saver_type& sm,
1186 ordered_non_unique_tag)const
1188 typedef duplicates_iterator<node_type,value_compare> dup_iterator;
1191 dup_iterator(begin().get_node(),end().get_node(),value_comp()),
1192 dup_iterator(end().get_node(),value_comp()),
1194 super::save_(ar,version,sm);
1197 template<typename Archive>
1199 Archive& ar,const unsigned int version,const index_loader_type& lm,
1200 ordered_non_unique_tag)
1203 ::boost::bind(&ordered_index::rearranger,this,_1,_2),
1205 super::load_(ar,version,lm);
1208 void rearranger(node_type* position,node_type *x)
1210 if(!position||comp(key(position->value()),key(x->value()))){
1211 position=lower_bound(key(x->value())).get_node();
1213 else if(comp(key(x->value()),key(position->value()))){
1214 /* inconsistent rearrangement */
1216 archive::archive_exception(
1217 archive::archive_exception::other_exception));
1219 else node_type::increment(position);
1222 node_impl_type::rebalance_for_erase(
1223 x->impl(),header()->parent(),header()->left(),header()->right());
1224 node_impl_type::restore(
1225 x->impl(),position->impl(),header()->impl());
1228 #endif /* serialization */
1233 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1234 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1235 #pragma parse_mfunc_templ reset
1242 typename KeyFromValue1,typename Compare1,
1243 typename SuperMeta1,typename TagList1,typename Category1,
1244 typename KeyFromValue2,typename Compare2,
1245 typename SuperMeta2,typename TagList2,typename Category2
1248 const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
1249 const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
1251 return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
1255 typename KeyFromValue1,typename Compare1,
1256 typename SuperMeta1,typename TagList1,typename Category1,
1257 typename KeyFromValue2,typename Compare2,
1258 typename SuperMeta2,typename TagList2,typename Category2
1261 const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
1262 const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
1264 return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
1268 typename KeyFromValue1,typename Compare1,
1269 typename SuperMeta1,typename TagList1,typename Category1,
1270 typename KeyFromValue2,typename Compare2,
1271 typename SuperMeta2,typename TagList2,typename Category2
1274 const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
1275 const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
1281 typename KeyFromValue1,typename Compare1,
1282 typename SuperMeta1,typename TagList1,typename Category1,
1283 typename KeyFromValue2,typename Compare2,
1284 typename SuperMeta2,typename TagList2,typename Category2
1287 const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
1288 const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
1294 typename KeyFromValue1,typename Compare1,
1295 typename SuperMeta1,typename TagList1,typename Category1,
1296 typename KeyFromValue2,typename Compare2,
1297 typename SuperMeta2,typename TagList2,typename Category2
1300 const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
1301 const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
1307 typename KeyFromValue1,typename Compare1,
1308 typename SuperMeta1,typename TagList1,typename Category1,
1309 typename KeyFromValue2,typename Compare2,
1310 typename SuperMeta2,typename TagList2,typename Category2
1313 const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
1314 const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
1319 /* specialized algorithms */
1322 typename KeyFromValue,typename Compare,
1323 typename SuperMeta,typename TagList,typename Category
1326 ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x,
1327 ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& y)
1332 } /* namespace multi_index::detail */
1334 /* ordered_index specifiers */
1336 template<typename Arg1,typename Arg2,typename Arg3>
1337 struct ordered_unique
1339 typedef typename detail::ordered_index_args<
1340 Arg1,Arg2,Arg3> index_args;
1341 typedef typename index_args::tag_list_type::type tag_list_type;
1342 typedef typename index_args::key_from_value_type key_from_value_type;
1343 typedef typename index_args::compare_type compare_type;
1345 template<typename Super>
1348 typedef detail::ordered_index_node<Super> type;
1351 template<typename SuperMeta>
1354 typedef detail::ordered_index<
1355 key_from_value_type,compare_type,
1356 SuperMeta,tag_list_type,detail::ordered_unique_tag> type;
1360 template<typename Arg1,typename Arg2,typename Arg3>
1361 struct ordered_non_unique
1363 typedef detail::ordered_index_args<
1364 Arg1,Arg2,Arg3> index_args;
1365 typedef typename index_args::tag_list_type::type tag_list_type;
1366 typedef typename index_args::key_from_value_type key_from_value_type;
1367 typedef typename index_args::compare_type compare_type;
1369 template<typename Super>
1372 typedef detail::ordered_index_node<Super> type;
1375 template<typename SuperMeta>
1378 typedef detail::ordered_index<
1379 key_from_value_type,compare_type,
1380 SuperMeta,tag_list_type,detail::ordered_non_unique_tag> type;
1384 } /* namespace multi_index */
1386 } /* namespace boost */
1388 #undef BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT