multi_index/detail/ord_index_impl.hpp

0001 /* Copyright 2003-2023 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/multi_index for library home page.
0007  *
0008  * The internal implementation of red-black trees is based on that of SGI STL
0009  * stl_tree.h file:
0010  *
0011  * Copyright (c) 1996,1997
0012  * Silicon Graphics Computer Systems, Inc.
0013  *
0014  * Permission to use, copy, modify, distribute and sell this software
0015  * and its documentation for any purpose is hereby granted without fee,
0016  * provided that the above copyright notice appear in all copies and
0017  * that both that copyright notice and this permission notice appear
0018  * in supporting documentation.  Silicon Graphics makes no
0019  * representations about the suitability of this software for any
0020  * purpose.  It is provided "as is" without express or implied warranty.
0021  *
0022  *
0023  * Copyright (c) 1994
0024  * Hewlett-Packard Company
0025  *
0026  * Permission to use, copy, modify, distribute and sell this software
0027  * and its documentation for any purpose is hereby granted without fee,
0028  * provided that the above copyright notice appear in all copies and
0029  * that both that copyright notice and this permission notice appear
0030  * in supporting documentation.  Hewlett-Packard Company makes no
0031  * representations about the suitability of this software for any
0032  * purpose.  It is provided "as is" without express or implied warranty.
0033  *
0034  */
0035
0036 #ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_IMPL_HPP
0037 #define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_IMPL_HPP
0038
0039 #if defined(_MSC_VER)
0040 #pragma once
0041 #endif
0042
0043 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
0044 #include <algorithm>
0045 #include <boost/call_traits.hpp>
0046 #include <boost/core/addressof.hpp>
0047 #include <boost/core/no_exceptions_support.hpp>
0048 #include <boost/core/ref.hpp>
0049 #include <boost/detail/workaround.hpp>
0050 #include <boost/iterator/reverse_iterator.hpp>
0051 #include <boost/move/core.hpp>
0052 #include <boost/move/utility_core.hpp>
0053 #include <boost/mpl/bool.hpp>
0054 #include <boost/mpl/if.hpp>
0055 #include <boost/mpl/push_front.hpp>
0056 #include <boost/multi_index/detail/access_specifier.hpp>
0057 #include <boost/multi_index/detail/adl_swap.hpp>
0058 #include <boost/multi_index/detail/allocator_traits.hpp>
0059 #include <boost/multi_index/detail/bidir_node_iterator.hpp>
0060 #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
0061 #include <boost/multi_index/detail/index_node_base.hpp>
0062 #include <boost/multi_index/detail/invalidate_iterators.hpp>
0063 #include <boost/multi_index/detail/modify_key_adaptor.hpp>
0064 #include <boost/multi_index/detail/node_handle.hpp>
0065 #include <boost/multi_index/detail/ord_index_node.hpp>
0066 #include <boost/multi_index/detail/ord_index_ops.hpp>
0067 #include <boost/multi_index/detail/safe_mode.hpp>
0068 #include <boost/multi_index/detail/scope_guard.hpp>
0069 #include <boost/multi_index/detail/unbounded.hpp>
0070 #include <boost/multi_index/detail/value_compare.hpp>
0071 #include <boost/multi_index/detail/vartempl_support.hpp>
0072 #include <boost/multi_index/detail/ord_index_impl_fwd.hpp>
0073 #include <boost/tuple/tuple.hpp>
0074 #include <boost/type_traits/is_same.hpp>
0075 #include <utility>
0076
0077 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0078 #include <initializer_list>
0079 #endif
0080
0081 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
0082 #include <boost/bind/bind.hpp>
0083 #include <boost/multi_index/detail/bad_archive_exception.hpp>
0084 #include <boost/multi_index/detail/duplicates_iterator.hpp>
0085 #include <boost/throw_exception.hpp>
0086 #endif
0087
0088 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
0089 #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(x)                    \
0090   detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \
0091     detail::make_obj_guard(x,&ordered_index_impl::check_invariant_);         \
0092   BOOST_JOIN(check_invariant_,__LINE__).touch();
0093 #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT                          \
0094   BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(*this)
0095 #else
0096 #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(x)
0097 #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT
0098 #endif
0099
0100 namespace boost{
0101
0102 namespace multi_index{
0103
0104 namespace detail{
0105
0106 /* ordered_index adds a layer of ordered indexing to a given Super and accepts
0107  * an augmenting policy for optional addition of order statistics.
0108  */
0109
0110 /* Most of the implementation of unique and non-unique indices is
0111  * shared. We tell from one another on instantiation time by using
0112  * these tags.
0113  */
0114
0115 struct ordered_unique_tag{};
0116 struct ordered_non_unique_tag{};
0117
0118 #if defined(BOOST_MSVC)
0119 #pragma warning(push)
0120 #pragma warning(disable:4355) /* this used in base member initializer list */
0121 #endif
0122
0123 template<
0124   typename KeyFromValue,typename Compare,
0125   typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
0126 >
0127 class ordered_index;
0128
0129 template<
0130   typename KeyFromValue,typename Compare,
0131   typename SuperMeta,typename TagList,typename Category,typename AugmentPolicy
0132 >
0133 class ordered_index_impl:
0134   BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
0135 {
0136 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
0137     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
0138 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
0139  * lifetime of const references bound to temporaries --precisely what
0140  * scopeguards are.
0141  */
0142
0143 #pragma parse_mfunc_templ off
0144 #endif
0145
0146 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
0147   /* cross-index access */
0148
0149   template <typename,typename,typename> friend class index_base;
0150 #endif
0151
0152   typedef typename SuperMeta::type                   super;
0153
0154 protected:
0155   typedef ordered_index_node<
0156     AugmentPolicy,typename super::index_node_type>   index_node_type;
0157
0158 protected: /* for the benefit of AugmentPolicy::augmented_interface */
0159   typedef typename index_node_type::impl_type        node_impl_type;
0160   typedef typename node_impl_type::pointer           node_impl_pointer;
0161
0162 public:
0163   /* types */
0164
0165   typedef typename KeyFromValue::result_type         key_type;
0166   typedef typename index_node_type::value_type       value_type;
0167   typedef KeyFromValue                               key_from_value;
0168   typedef Compare                                    key_compare;
0169   typedef value_comparison<
0170     value_type,KeyFromValue,Compare>                 value_compare;
0171   typedef tuple<key_from_value,key_compare>          ctor_args;
0172   typedef typename super::final_allocator_type       allocator_type;
0173   typedef value_type&                                reference;
0174   typedef const value_type&                          const_reference;
0175
0176 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0177   typedef safe_mode::safe_iterator<
0178     bidir_node_iterator<index_node_type> >           iterator;
0179 #else
0180   typedef bidir_node_iterator<index_node_type>       iterator;
0181 #endif
0182
0183   typedef iterator                                   const_iterator;
0184
0185 private:
0186   typedef allocator_traits<allocator_type>           alloc_traits;
0187
0188 public:
0189   typedef typename alloc_traits::size_type           size_type;
0190   typedef typename alloc_traits::difference_type     difference_type;
0191   typedef typename alloc_traits::pointer             pointer;
0192   typedef typename alloc_traits::const_pointer       const_pointer;
0193   typedef typename
0194     boost::reverse_iterator<iterator>                reverse_iterator;
0195   typedef typename
0196     boost::reverse_iterator<const_iterator>          const_reverse_iterator;
0197   typedef typename super::final_node_handle_type     node_type;
0198   typedef detail::insert_return_type<
0199     iterator,node_type>                              insert_return_type;
0200   typedef TagList                                    tag_list;
0201
0202 protected:
0203   typedef typename super::final_node_type            final_node_type;
0204   typedef tuples::cons<
0205     ctor_args,
0206     typename super::ctor_args_list>                  ctor_args_list;
0207   typedef typename mpl::push_front<
0208     typename super::index_type_list,
0209     ordered_index<
0210       KeyFromValue,Compare,
0211       SuperMeta,TagList,Category,AugmentPolicy
0212     > >::type                                        index_type_list;
0213   typedef typename mpl::push_front<
0214     typename super::iterator_type_list,
0215     iterator>::type    iterator_type_list;
0216   typedef typename mpl::push_front<
0217     typename super::const_iterator_type_list,
0218     const_iterator>::type                            const_iterator_type_list;
0219   typedef typename super::copy_map_type              copy_map_type;
0220
0221 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
0222   typedef typename super::index_saver_type           index_saver_type;
0223   typedef typename super::index_loader_type          index_loader_type;
0224 #endif
0225
0226 protected:
0227 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0228   typedef safe_mode::safe_container<iterator>        safe_container;
0229 #endif
0230
0231   typedef typename call_traits<
0232     value_type>::param_type                          value_param_type;
0233   typedef typename call_traits<
0234     key_type>::param_type                            key_param_type;
0235
0236   /* needed to avoid commas in some macros */
0237
0238   typedef std::pair<iterator,bool>                   pair_return_type;
0239
0240 public:
0241
0242   /* construct/copy/destroy
0243    * Default and copy ctors are in the protected section as indices are
0244    * not supposed to be created on their own. No range ctor either.
0245    * Assignment operators defined at ordered_index rather than here.
0246    */
0247
0248   allocator_type get_allocator()const BOOST_NOEXCEPT
0249   {
0250     return this->final().get_allocator();
0251   }
0252
0253   /* iterators */
0254
0255   iterator
0256     begin()BOOST_NOEXCEPT{return make_iterator(leftmost());}
0257   const_iterator
0258     begin()const BOOST_NOEXCEPT{return make_iterator(leftmost());}
0259   iterator
0260     end()BOOST_NOEXCEPT{return make_iterator(header());}
0261   const_iterator
0262     end()const BOOST_NOEXCEPT{return make_iterator(header());}
0263   reverse_iterator
0264     rbegin()BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
0265   const_reverse_iterator
0266     rbegin()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
0267   reverse_iterator
0268     rend()BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
0269   const_reverse_iterator
0270     rend()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
0271   const_iterator
0272     cbegin()const BOOST_NOEXCEPT{return begin();}
0273   const_iterator
0274     cend()const BOOST_NOEXCEPT{return end();}
0275   const_reverse_iterator
0276     crbegin()const BOOST_NOEXCEPT{return rbegin();}
0277   const_reverse_iterator
0278     crend()const BOOST_NOEXCEPT{return rend();}
0279
0280   iterator iterator_to(const value_type& x)
0281   {
0282     return make_iterator(
0283       node_from_value<index_node_type>(boost::addressof(x)));
0284   }
0285
0286   const_iterator iterator_to(const value_type& x)const
0287   {
0288     return make_iterator(
0289       node_from_value<index_node_type>(boost::addressof(x)));
0290   }
0291
0292   /* capacity */
0293
0294   bool      empty()const BOOST_NOEXCEPT{return this->final_empty_();}
0295   size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
0296   size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
0297
0298   /* modifiers */
0299
0300   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
0301     pair_return_type,emplace,emplace_impl)
0302
0303   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
0304     iterator,emplace_hint,emplace_hint_impl,iterator,position)
0305
0306   std::pair<iterator,bool> insert(const value_type& x)
0307   {
0308     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0309     std::pair<final_node_type*,bool> p=this->final_insert_(x);
0310     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
0311   }
0312
0313   std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
0314   {
0315     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0316     std::pair<final_node_type*,bool> p=this->final_insert_rv_(x);
0317     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
0318   }
0319
0320   iterator insert(iterator position,const value_type& x)
0321   {
0322     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0323     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0324     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0325     std::pair<final_node_type*,bool> p=this->final_insert_(
0326       x,static_cast<final_node_type*>(position.get_node()));
0327     return make_iterator(p.first);
0328   }
0329
0330   iterator insert(iterator position,BOOST_RV_REF(value_type) x)
0331   {
0332     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0333     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0334     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0335     std::pair<final_node_type*,bool> p=this->final_insert_rv_(
0336       x,static_cast<final_node_type*>(position.get_node()));
0337     return make_iterator(p.first);
0338   }
0339
0340   template<typename InputIterator>
0341   void insert(InputIterator first,InputIterator last)
0342   {
0343     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0344     for(;first!=last;++first)this->final_insert_ref_(*first);
0345   }
0346
0347 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0348   void insert(std::initializer_list<value_type> list)
0349   {
0350     insert(list.begin(),list.end());
0351   }
0352 #endif
0353
0354   insert_return_type insert(BOOST_RV_REF(node_type) nh)
0355   {
0356     if(nh)BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,nh);
0357     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0358     std::pair<final_node_type*,bool> p=this->final_insert_nh_(nh);
0359     return insert_return_type(make_iterator(p.first),p.second,boost::move(nh));
0360   }
0361
0362   iterator insert(const_iterator position,BOOST_RV_REF(node_type) nh)
0363   {
0364     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0365     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0366     if(nh)BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,nh);
0367     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0368     std::pair<final_node_type*,bool> p=this->final_insert_nh_(
0369       nh,static_cast<final_node_type*>(position.get_node()));
0370     return make_iterator(p.first);
0371   }
0372
0373   node_type extract(const_iterator position)
0374   {
0375     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0376     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
0377     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0378     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0379     return this->final_extract_(
0380       static_cast<final_node_type*>(position.get_node()));
0381   }
0382
0383   node_type extract(key_param_type x)
0384   {
0385     iterator position=lower_bound(x);
0386     if(position==end()||comp_(x,key(*position)))return node_type();
0387     else return extract(position);
0388   }
0389
0390   iterator erase(iterator position)
0391   {
0392     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0393     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
0394     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0395     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0396     this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
0397     return position;
0398   }
0399
0400   size_type erase(key_param_type x)
0401   {
0402     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0403     std::pair<iterator,iterator> p=equal_range(x);
0404     size_type s=0;
0405     while(p.first!=p.second){
0406       p.first=erase(p.first);
0407       ++s;
0408     }
0409     return s;
0410   }
0411
0412   iterator erase(iterator first,iterator last)
0413   {
0414     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
0415     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
0416     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
0417     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
0418     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
0419     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0420     while(first!=last){
0421       first=erase(first);
0422     }
0423     return first;
0424   }
0425
0426   bool replace(iterator position,const value_type& x)
0427   {
0428     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0429     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
0430     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0431     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0432     return this->final_replace_(
0433       x,static_cast<final_node_type*>(position.get_node()));
0434   }
0435
0436   bool replace(iterator position,BOOST_RV_REF(value_type) x)
0437   {
0438     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0439     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
0440     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0441     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0442     return this->final_replace_rv_(
0443       x,static_cast<final_node_type*>(position.get_node()));
0444   }
0445
0446   template<typename Modifier>
0447   bool modify(iterator position,Modifier mod)
0448   {
0449     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0450     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
0451     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0452     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0453
0454 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0455     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
0456      * this is not added. Left it for all compilers as it does no
0457      * harm.
0458      */
0459
0460     position.detach();
0461 #endif
0462
0463     return this->final_modify_(
0464       mod,static_cast<final_node_type*>(position.get_node()));
0465   }
0466
0467   template<typename Modifier,typename Rollback>
0468   bool modify(iterator position,Modifier mod,Rollback back_)
0469   {
0470     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0471     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
0472     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0473     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0474
0475 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0476     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
0477      * this is not added. Left it for all compilers as it does no
0478      * harm.
0479      */
0480
0481     position.detach();
0482 #endif
0483
0484     return this->final_modify_(
0485       mod,back_,static_cast<final_node_type*>(position.get_node()));
0486   }
0487
0488   template<typename Modifier>
0489   bool modify_key(iterator position,Modifier mod)
0490   {
0491     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0492     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
0493     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0494     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0495     return modify(
0496       position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
0497   }
0498
0499   template<typename Modifier,typename Rollback>
0500   bool modify_key(iterator position,Modifier mod,Rollback back_)
0501   {
0502     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0503     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
0504     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0505     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0506     return modify(
0507       position,
0508       modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key),
0509       modify_key_adaptor<Rollback,value_type,KeyFromValue>(back_,key));
0510   }
0511
0512   void swap(
0513     ordered_index<
0514       KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x)
0515   {
0516     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0517     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT_OF(x);
0518     this->final_swap_(x.final());
0519   }
0520
0521   void clear()BOOST_NOEXCEPT
0522   {
0523     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0524     this->final_clear_();
0525   }
0526
0527   template<typename Index>
0528   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(ordered_index_impl,Index,void)
0529   merge(Index& x)
0530   {
0531     merge(x,x.begin(),x.end());
0532   }
0533
0534   template<typename Index>
0535   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(ordered_index_impl,Index,void)
0536   merge(BOOST_RV_REF(Index) x){merge(static_cast<Index&>(x));}
0537
0538   template<typename Index>
0539   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(
0540     ordered_index_impl,Index,pair_return_type)
0541   merge(Index& x,BOOST_DEDUCED_TYPENAME Index::iterator i)
0542   {
0543     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
0544     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
0545     BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x);
0546     BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,x);
0547     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0548     if(x.end().get_node()==this->header()){ /* same container */
0549       return std::pair<iterator,bool>(
0550         make_iterator(static_cast<final_node_type*>(i.get_node())),true);
0551     }
0552     else{
0553       std::pair<final_node_type*,bool> p=this->final_transfer_(
0554         x,static_cast<final_node_type*>(i.get_node()));
0555       return std::pair<iterator,bool>(make_iterator(p.first),p.second);
0556     }
0557   }
0558
0559   template<typename Index>
0560   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(
0561     ordered_index_impl,Index,pair_return_type)
0562   merge(BOOST_RV_REF(Index) x,BOOST_DEDUCED_TYPENAME Index::iterator i)
0563   {
0564     return merge(static_cast<Index&>(x),i);
0565   }
0566
0567   template<typename Index>
0568   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(ordered_index_impl,Index,void)
0569   merge(
0570     Index& x,
0571     BOOST_DEDUCED_TYPENAME Index::iterator first,
0572     BOOST_DEDUCED_TYPENAME Index::iterator last)
0573   {
0574     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
0575     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
0576     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x);
0577     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x);
0578     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
0579     BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,x);
0580     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
0581     if(x.end().get_node()!=this->header()){ /* different containers */
0582       this->final_transfer_range_(x,first,last);
0583     }
0584   }
0585
0586   template<typename Index>
0587   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(ordered_index_impl,Index,void)
0588   merge(
0589     BOOST_RV_REF(Index) x,
0590     BOOST_DEDUCED_TYPENAME Index::iterator first,
0591     BOOST_DEDUCED_TYPENAME Index::iterator last)
0592   {
0593     merge(static_cast<Index&>(x),first,last);
0594   }
0595
0596   /* observers */
0597
0598   key_from_value key_extractor()const{return key;}
0599   key_compare    key_comp()const{return comp_;}
0600   value_compare  value_comp()const{return value_compare(key,comp_);}
0601
0602   /* set operations */
0603
0604   /* Internally, these ops rely on const_iterator being the same
0605    * type as iterator.
0606    */
0607
0608   template<typename CompatibleKey>
0609   iterator find(const CompatibleKey& x)const
0610   {
0611     return make_iterator(ordered_index_find(root(),header(),key,x,comp_));
0612   }
0613
0614   template<typename CompatibleKey,typename CompatibleCompare>
0615   iterator find(
0616     const CompatibleKey& x,const CompatibleCompare& comp)const
0617   {
0618     return make_iterator(ordered_index_find(root(),header(),key,x,comp));
0619   }
0620
0621   template<typename CompatibleKey>
0622   size_type count(const CompatibleKey& x)const
0623   {
0624     return count(x,comp_);
0625   }
0626
0627   template<typename CompatibleKey,typename CompatibleCompare>
0628   size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const
0629   {
0630     std::pair<iterator,iterator> p=equal_range(x,comp);
0631     size_type n=static_cast<size_type>(std::distance(p.first,p.second));
0632     return n;
0633   }
0634
0635   template<typename CompatibleKey>
0636   bool contains(const CompatibleKey& x)const
0637   {
0638     return contains(x,comp_);
0639   }
0640
0641   template<typename CompatibleKey,typename CompatibleCompare>
0642   bool contains(
0643     const CompatibleKey& x,const CompatibleCompare& comp)const
0644   {
0645     return find(x,comp)!=end();
0646   }
0647
0648   template<typename CompatibleKey>
0649   iterator lower_bound(const CompatibleKey& x)const
0650   {
0651     return make_iterator(
0652       ordered_index_lower_bound(root(),header(),key,x,comp_));
0653   }
0654
0655   template<typename CompatibleKey,typename CompatibleCompare>
0656   iterator lower_bound(
0657     const CompatibleKey& x,const CompatibleCompare& comp)const
0658   {
0659     return make_iterator(
0660       ordered_index_lower_bound(root(),header(),key,x,comp));
0661   }
0662
0663   template<typename CompatibleKey>
0664   iterator upper_bound(const CompatibleKey& x)const
0665   {
0666     return make_iterator(
0667       ordered_index_upper_bound(root(),header(),key,x,comp_));
0668   }
0669
0670   template<typename CompatibleKey,typename CompatibleCompare>
0671   iterator upper_bound(
0672     const CompatibleKey& x,const CompatibleCompare& comp)const
0673   {
0674     return make_iterator(
0675       ordered_index_upper_bound(root(),header(),key,x,comp));
0676   }
0677
0678   template<typename CompatibleKey>
0679   std::pair<iterator,iterator> equal_range(
0680     const CompatibleKey& x)const
0681   {
0682     std::pair<index_node_type*,index_node_type*> p=
0683       ordered_index_equal_range(root(),header(),key,x,comp_);
0684     return std::pair<iterator,iterator>(
0685       make_iterator(p.first),make_iterator(p.second));
0686   }
0687
0688   template<typename CompatibleKey,typename CompatibleCompare>
0689   std::pair<iterator,iterator> equal_range(
0690     const CompatibleKey& x,const CompatibleCompare& comp)const
0691   {
0692     std::pair<index_node_type*,index_node_type*> p=
0693       ordered_index_equal_range(root(),header(),key,x,comp);
0694     return std::pair<iterator,iterator>(
0695       make_iterator(p.first),make_iterator(p.second));
0696   }
0697
0698   /* range */
0699
0700   template<typename LowerBounder,typename UpperBounder>
0701   std::pair<iterator,iterator>
0702   range(LowerBounder lower,UpperBounder upper)const
0703   {
0704     typedef typename mpl::if_<
0705       is_same<LowerBounder,unbounded_type>,
0706       BOOST_DEDUCED_TYPENAME mpl::if_<
0707         is_same<UpperBounder,unbounded_type>,
0708         both_unbounded_tag,
0709         lower_unbounded_tag
0710       >::type,
0711       BOOST_DEDUCED_TYPENAME mpl::if_<
0712         is_same<UpperBounder,unbounded_type>,
0713         upper_unbounded_tag,
0714         none_unbounded_tag
0715       >::type
0716     >::type dispatch;
0717
0718     return range(lower,upper,dispatch());
0719   }
0720
0721 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
0722   ordered_index_impl(const ctor_args_list& args_list,const allocator_type& al):
0723     super(args_list.get_tail(),al),
0724     key(tuples::get<0>(args_list.get_head())),
0725     comp_(tuples::get<1>(args_list.get_head()))
0726
0727 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0728     ,safe(*this)
0729 #endif
0730
0731   {
0732     empty_initialize();
0733   }
0734
0735   ordered_index_impl(
0736     const ordered_index_impl<
0737       KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x):
0738     super(x),
0739     key(x.key),
0740     comp_(x.comp_)
0741
0742 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0743     ,safe(*this)
0744 #endif
0745
0746   {
0747     /* Copy ctor just takes the key and compare objects from x. The rest is
0748      * done in a subsequent call to copy_().
0749      */
0750   }
0751
0752   ordered_index_impl(
0753      const ordered_index_impl<
0754        KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x,
0755      do_not_copy_elements_tag):
0756     super(x,do_not_copy_elements_tag()),
0757     key(x.key),
0758     comp_(x.comp_)
0759
0760 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0761     ,safe(*this)
0762 #endif
0763
0764   {
0765     empty_initialize();
0766   }
0767
0768   ~ordered_index_impl()
0769   {
0770     /* the container is guaranteed to be empty by now */
0771   }
0772
0773 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0774   iterator       make_iterator(index_node_type* node)
0775     {return iterator(node,&safe);}
0776   const_iterator make_iterator(index_node_type* node)const
0777     {return const_iterator(node,const_cast<safe_container*>(&safe));}
0778 #else
0779   iterator       make_iterator(index_node_type* node){return iterator(node);}
0780   const_iterator make_iterator(index_node_type* node)const
0781                    {return const_iterator(node);}
0782 #endif
0783
0784   void copy_(
0785     const ordered_index_impl<
0786       KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x,
0787     const copy_map_type& map)
0788   {
0789     if(!x.root()){
0790       empty_initialize();
0791     }
0792     else{
0793       header()->color()=x.header()->color();
0794       AugmentPolicy::copy(x.header()->impl(),header()->impl());
0795
0796       index_node_type* root_cpy=map.find(
0797         static_cast<final_node_type*>(x.root()));
0798       header()->parent()=root_cpy->impl();
0799
0800       index_node_type* leftmost_cpy=map.find(
0801         static_cast<final_node_type*>(x.leftmost()));
0802       header()->left()=leftmost_cpy->impl();
0803
0804       index_node_type* rightmost_cpy=map.find(
0805         static_cast<final_node_type*>(x.rightmost()));
0806       header()->right()=rightmost_cpy->impl();
0807
0808       typedef typename copy_map_type::const_iterator copy_map_iterator;
0809       for(copy_map_iterator it=map.begin(),it_end=map.end();it!=it_end;++it){
0810         index_node_type* org=it->first;
0811         index_node_type* cpy=it->second;
0812
0813         cpy->color()=org->color();
0814         AugmentPolicy::copy(org->impl(),cpy->impl());
0815
0816         node_impl_pointer parent_org=org->parent();
0817         if(parent_org==node_impl_pointer(0))cpy->parent()=node_impl_pointer(0);
0818         else{
0819           index_node_type* parent_cpy=map.find(
0820             static_cast<final_node_type*>(
0821               index_node_type::from_impl(parent_org)));
0822           cpy->parent()=parent_cpy->impl();
0823           if(parent_org->left()==org->impl()){
0824             parent_cpy->left()=cpy->impl();
0825           }
0826           else if(parent_org->right()==org->impl()){
0827             /* header() does not satisfy this nor the previous check */
0828             parent_cpy->right()=cpy->impl();
0829           }
0830         }
0831
0832         if(org->left()==node_impl_pointer(0))
0833           cpy->left()=node_impl_pointer(0);
0834         if(org->right()==node_impl_pointer(0))
0835           cpy->right()=node_impl_pointer(0);
0836       }
0837     }
0838
0839     super::copy_(x,map);
0840   }
0841
0842   template<typename Variant>
0843   final_node_type* insert_(
0844     value_param_type v,final_node_type*& x,Variant variant)
0845   {
0846     link_info inf;
0847     if(!link_point(key(v),inf,Category())){
0848       return static_cast<final_node_type*>(
0849         index_node_type::from_impl(inf.pos));
0850     }
0851
0852     final_node_type* res=super::insert_(v,x,variant);
0853     if(res==x){
0854       node_impl_type::link(
0855         static_cast<index_node_type*>(x)->impl(),
0856         inf.side,inf.pos,header()->impl());
0857     }
0858     return res;
0859   }
0860
0861   template<typename Variant>
0862   final_node_type* insert_(
0863     value_param_type v,index_node_type* position,
0864     final_node_type*& x,Variant variant)
0865   {
0866     link_info inf;
0867     if(!hinted_link_point(key(v),position,inf,Category())){
0868       return static_cast<final_node_type*>(
0869         index_node_type::from_impl(inf.pos));
0870     }
0871
0872     final_node_type* res=super::insert_(v,position,x,variant);
0873     if(res==x){
0874       node_impl_type::link(
0875         static_cast<index_node_type*>(x)->impl(),
0876         inf.side,inf.pos,header()->impl());
0877     }
0878     return res;
0879   }
0880
0881   template<typename Dst>
0882   void extract_(index_node_type* x,Dst dst)
0883   {
0884     node_impl_type::rebalance_for_extract(
0885       x->impl(),header()->parent(),header()->left(),header()->right());
0886     super::extract_(x,dst.next());
0887
0888 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0889     transfer_iterators(dst.get(),x);
0890 #endif
0891   }
0892
0893   void delete_all_nodes_()
0894   {
0895     delete_all_nodes(root());
0896   }
0897
0898   void clear_()
0899   {
0900     super::clear_();
0901     empty_initialize();
0902
0903 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0904     safe.detach_dereferenceable_iterators();
0905 #endif
0906   }
0907
0908   template<typename BoolConstant>
0909   void swap_(
0910     ordered_index_impl<
0911       KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x,
0912     BoolConstant swap_allocators)
0913   {
0914     adl_swap(key,x.key);
0915     adl_swap(comp_,x.comp_);
0916
0917 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0918     safe.swap(x.safe);
0919 #endif
0920
0921     super::swap_(x,swap_allocators);
0922   }
0923
0924   void swap_elements_(
0925     ordered_index_impl<
0926       KeyFromValue,Compare,SuperMeta,TagList,Category,AugmentPolicy>& x)
0927   {
0928 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0929     safe.swap(x.safe);
0930 #endif
0931
0932     super::swap_elements_(x);
0933   }
0934
0935   template<typename Variant>
0936   bool replace_(value_param_type v,index_node_type* x,Variant variant)
0937   {
0938     if(in_place(v,x,Category())){
0939       return super::replace_(v,x,variant);
0940     }
0941
0942     index_node_type* next=x;
0943     index_node_type::increment(next);
0944
0945     node_impl_type::rebalance_for_extract(
0946       x->impl(),header()->parent(),header()->left(),header()->right());
0947
0948     BOOST_TRY{
0949       link_info inf;
0950       if(link_point(key(v),inf,Category())&&super::replace_(v,x,variant)){
0951         node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
0952         return true;
0953       }
0954       node_impl_type::restore(x->impl(),next->impl(),header()->impl());
0955       return false;
0956     }
0957     BOOST_CATCH(...){
0958       node_impl_type::restore(x->impl(),next->impl(),header()->impl());
0959       BOOST_RETHROW;
0960     }
0961     BOOST_CATCH_END
0962   }
0963
0964   bool modify_(index_node_type* x)
0965   {
0966     bool b;
0967     BOOST_TRY{
0968       b=in_place(x->value(),x,Category());
0969     }
0970     BOOST_CATCH(...){
0971       extract_(x,invalidate_iterators());
0972       BOOST_RETHROW;
0973     }
0974     BOOST_CATCH_END
0975     if(!b){
0976       node_impl_type::rebalance_for_extract(
0977         x->impl(),header()->parent(),header()->left(),header()->right());
0978       BOOST_TRY{
0979         link_info inf;
0980         if(!link_point(key(x->value()),inf,Category())){
0981           super::extract_(x,invalidate_iterators());
0982
0983 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0984           detach_iterators(x);
0985 #endif
0986           return false;
0987         }
0988         node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
0989       }
0990       BOOST_CATCH(...){
0991         super::extract_(x,invalidate_iterators());
0992
0993 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
0994         detach_iterators(x);
0995 #endif
0996
0997         BOOST_RETHROW;
0998       }
0999       BOOST_CATCH_END
1000     }
1001
1002     BOOST_TRY{
1003       if(!super::modify_(x)){
1004         node_impl_type::rebalance_for_extract(
1005           x->impl(),header()->parent(),header()->left(),header()->right());
1006
1007 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1008         detach_iterators(x);
1009 #endif
1010
1011         return false;
1012       }
1013       else return true;
1014     }
1015     BOOST_CATCH(...){
1016       node_impl_type::rebalance_for_extract(
1017         x->impl(),header()->parent(),header()->left(),header()->right());
1018
1019 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1020       detach_iterators(x);
1021 #endif
1022
1023       BOOST_RETHROW;
1024     }
1025     BOOST_CATCH_END
1026   }
1027
1028   bool modify_rollback_(index_node_type* x)
1029   {
1030     if(in_place(x->value(),x,Category())){
1031       return super::modify_rollback_(x);
1032     }
1033
1034     index_node_type* next=x;
1035     index_node_type::increment(next);
1036
1037     node_impl_type::rebalance_for_extract(
1038       x->impl(),header()->parent(),header()->left(),header()->right());
1039
1040     BOOST_TRY{
1041       link_info inf;
1042       if(link_point(key(x->value()),inf,Category())&&
1043          super::modify_rollback_(x)){
1044         node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
1045         return true;
1046       }
1047       node_impl_type::restore(x->impl(),next->impl(),header()->impl());
1048       return false;
1049     }
1050     BOOST_CATCH(...){
1051       node_impl_type::restore(x->impl(),next->impl(),header()->impl());
1052       BOOST_RETHROW;
1053     }
1054     BOOST_CATCH_END
1055   }
1056
1057   bool check_rollback_(index_node_type* x)const
1058   {
1059     return in_place(x->value(),x,Category())&&super::check_rollback_(x);
1060   }
1061
1062 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1063   /* serialization */
1064
1065   template<typename Archive>
1066   void save_(
1067     Archive& ar,const unsigned int version,const index_saver_type& sm)const
1068   {
1069     save_(ar,version,sm,Category());
1070   }
1071
1072   template<typename Archive>
1073   void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
1074   {
1075     load_(ar,version,lm,Category());
1076   }
1077 #endif
1078
1079 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
1080   /* invariant stuff */
1081
1082   bool invariant_()const
1083   {
1084     if(size()==0||begin()==end()){
1085       if(size()!=0||begin()!=end()||
1086          header()->left()!=header()->impl()||
1087          header()->right()!=header()->impl())return false;
1088     }
1089     else{
1090       if((size_type)std::distance(begin(),end())!=size())return false;
1091
1092       std::size_t len=node_impl_type::black_count(
1093         leftmost()->impl(),root()->impl());
1094       for(const_iterator it=begin(),it_end=end();it!=it_end;++it){
1095         index_node_type* x=it.get_node();
1096         index_node_type* left_x=index_node_type::from_impl(x->left());
1097         index_node_type* right_x=index_node_type::from_impl(x->right());
1098
1099         if(x->color()==red){
1100           if((left_x&&left_x->color()==red)||
1101              (right_x&&right_x->color()==red))return false;
1102         }
1103         if(left_x&&comp_(key(x->value()),key(left_x->value())))return false;
1104         if(right_x&&comp_(key(right_x->value()),key(x->value())))return false;
1105         if(!left_x&&!right_x&&
1106            node_impl_type::black_count(x->impl(),root()->impl())!=len)
1107           return false;
1108         if(!AugmentPolicy::invariant(x->impl()))return false;
1109       }
1110
1111       if(leftmost()->impl()!=node_impl_type::minimum(root()->impl()))
1112         return false;
1113       if(rightmost()->impl()!=node_impl_type::maximum(root()->impl()))
1114         return false;
1115     }
1116
1117     return super::invariant_();
1118   }
1119
1120
1121   /* This forwarding function eases things for the boost::mem_fn construct
1122    * in BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT. Actually,
1123    * final_check_invariant is already an inherited member function of
1124    * ordered_index_impl.
1125    */
1126   void check_invariant_()const{this->final_check_invariant_();}
1127 #endif
1128
1129 protected: /* for the benefit of AugmentPolicy::augmented_interface */
1130   index_node_type* header()const
1131     {return this->final_header();}
1132   index_node_type* root()const
1133     {return index_node_type::from_impl(header()->parent());}
1134   index_node_type* leftmost()const
1135     {return index_node_type::from_impl(header()->left());}
1136   index_node_type* rightmost()const
1137     {return index_node_type::from_impl(header()->right());}
1138
1139 private:
1140   void empty_initialize()
1141   {
1142     header()->color()=red;
1143     /* used to distinguish header() from root, in iterator.operator++ */
1144
1145     header()->parent()=node_impl_pointer(0);
1146     header()->left()=header()->impl();
1147     header()->right()=header()->impl();
1148   }
1149
1150   struct link_info
1151   {
1152     /* coverity[uninit_ctor]: suppress warning */
1153     link_info():side(to_left){}
1154
1155     ordered_index_side side;
1156     node_impl_pointer  pos;
1157   };
1158
1159   bool link_point(key_param_type k,link_info& inf,ordered_unique_tag)
1160   {
1161     index_node_type* y=header();
1162     index_node_type* x=root();
1163     bool c=true;
1164     while(x){
1165       y=x;
1166       c=comp_(k,key(x->value()));
1167       x=index_node_type::from_impl(c?x->left():x->right());
1168     }
1169     index_node_type* yy=y;
1170     if(c){
1171       if(yy==leftmost()){
1172         inf.side=to_left;
1173         inf.pos=y->impl();
1174         return true;
1175       }
1176       else index_node_type::decrement(yy);
1177     }
1178
1179     if(comp_(key(yy->value()),k)){
1180       inf.side=c?to_left:to_right;
1181       inf.pos=y->impl();
1182       return true;
1183     }
1184     else{
1185       inf.pos=yy->impl();
1186       return false;
1187     }
1188   }
1189
1190   bool link_point(key_param_type k,link_info& inf,ordered_non_unique_tag)
1191   {
1192     index_node_type* y=header();
1193     index_node_type* x=root();
1194     bool c=true;
1195     while (x){
1196      y=x;
1197      c=comp_(k,key(x->value()));
1198      x=index_node_type::from_impl(c?x->left():x->right());
1199     }
1200     inf.side=c?to_left:to_right;
1201     inf.pos=y->impl();
1202     return true;
1203   }
1204
1205   bool lower_link_point(key_param_type k,link_info& inf,ordered_non_unique_tag)
1206   {
1207     index_node_type* y=header();
1208     index_node_type* x=root();
1209     bool c=false;
1210     while (x){
1211      y=x;
1212      c=comp_(key(x->value()),k);
1213      x=index_node_type::from_impl(c?x->right():x->left());
1214     }
1215     inf.side=c?to_right:to_left;
1216     inf.pos=y->impl();
1217     return true;
1218   }
1219
1220   bool hinted_link_point(
1221     key_param_type k,index_node_type* position,
1222     link_info& inf,ordered_unique_tag)
1223   {
1224     if(position->impl()==header()->left()){
1225       if(size()>0&&comp_(k,key(position->value()))){
1226         inf.side=to_left;
1227         inf.pos=position->impl();
1228         return true;
1229       }
1230       else return link_point(k,inf,ordered_unique_tag());
1231     }
1232     else if(position==header()){
1233       if(comp_(key(rightmost()->value()),k)){
1234         inf.side=to_right;
1235         inf.pos=rightmost()->impl();
1236         return true;
1237       }
1238       else return link_point(k,inf,ordered_unique_tag());
1239     }
1240     else{
1241       index_node_type* before=position;
1242       index_node_type::decrement(before);
1243       if(comp_(key(before->value()),k)&&comp_(k,key(position->value()))){
1244         if(before->right()==node_impl_pointer(0)){
1245           inf.side=to_right;
1246           inf.pos=before->impl();
1247           return true;
1248         }
1249         else{
1250           inf.side=to_left;
1251           inf.pos=position->impl();
1252           return true;
1253         }
1254       }
1255       else return link_point(k,inf,ordered_unique_tag());
1256     }
1257   }
1258
1259   bool hinted_link_point(
1260     key_param_type k,index_node_type* position,
1261     link_info& inf,ordered_non_unique_tag)
1262   {
1263     if(position->impl()==header()->left()){
1264       if(size()>0&&!comp_(key(position->value()),k)){
1265         inf.side=to_left;
1266         inf.pos=position->impl();
1267         return true;
1268       }
1269       else return lower_link_point(k,inf,ordered_non_unique_tag());
1270     }
1271     else if(position==header()){
1272       if(!comp_(k,key(rightmost()->value()))){
1273         inf.side=to_right;
1274         inf.pos=rightmost()->impl();
1275         return true;
1276       }
1277       else return link_point(k,inf,ordered_non_unique_tag());
1278     }
1279     else{
1280       index_node_type* before=position;
1281       index_node_type::decrement(before);
1282       if(!comp_(k,key(before->value()))){
1283         if(!comp_(key(position->value()),k)){
1284           if(before->right()==node_impl_pointer(0)){
1285             inf.side=to_right;
1286             inf.pos=before->impl();
1287             return true;
1288           }
1289           else{
1290             inf.side=to_left;
1291             inf.pos=position->impl();
1292             return true;
1293           }
1294         }
1295         else return lower_link_point(k,inf,ordered_non_unique_tag());
1296       }
1297       else return link_point(k,inf,ordered_non_unique_tag());
1298     }
1299   }
1300
1301   void delete_all_nodes(index_node_type* x)
1302   {
1303     if(!x)return;
1304
1305     delete_all_nodes(index_node_type::from_impl(x->left()));
1306     delete_all_nodes(index_node_type::from_impl(x->right()));
1307     this->final_delete_node_(static_cast<final_node_type*>(x));
1308   }
1309
1310   bool in_place(value_param_type v,index_node_type* x,ordered_unique_tag)const
1311   {
1312     index_node_type* y;
1313     if(x!=leftmost()){
1314       y=x;
1315       index_node_type::decrement(y);
1316       if(!comp_(key(y->value()),key(v)))return false;
1317     }
1318
1319     y=x;
1320     index_node_type::increment(y);
1321     return y==header()||comp_(key(v),key(y->value()));
1322   }
1323
1324   bool in_place(
1325     value_param_type v,index_node_type* x,ordered_non_unique_tag)const
1326   {
1327     index_node_type* y;
1328     if(x!=leftmost()){
1329       y=x;
1330       index_node_type::decrement(y);
1331       if(comp_(key(v),key(y->value())))return false;
1332     }
1333
1334     y=x;
1335     index_node_type::increment(y);
1336     return y==header()||!comp_(key(y->value()),key(v));
1337   }
1338
1339 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1340   void detach_iterators(index_node_type* x)
1341   {
1342     iterator it=make_iterator(x);
1343     safe_mode::detach_equivalent_iterators(it);
1344   }
1345
1346   template<typename Dst>
1347   void transfer_iterators(Dst& dst,index_node_type* x)
1348   {
1349     iterator it=make_iterator(x);
1350     safe_mode::transfer_equivalent_iterators(dst,it);
1351   }
1352 #endif
1353
1354   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1355   std::pair<iterator,bool> emplace_impl(BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1356   {
1357     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1358     std::pair<final_node_type*,bool>p=
1359       this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1360     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
1361   }
1362
1363   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1364   iterator emplace_hint_impl(
1365     iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1366   {
1367     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1368     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1369     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1370     std::pair<final_node_type*,bool>p=
1371       this->final_emplace_hint_(
1372         static_cast<final_node_type*>(position.get_node()),
1373         BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1374     return make_iterator(p.first);
1375   }
1376
1377   template<typename LowerBounder,typename UpperBounder>
1378   std::pair<iterator,iterator>
1379   range(LowerBounder lower,UpperBounder upper,none_unbounded_tag)const
1380   {
1381     index_node_type* y=header();
1382     index_node_type* z=root();
1383
1384     while(z){
1385       if(!lower(key(z->value()))){
1386         z=index_node_type::from_impl(z->right());
1387       }
1388       else if(!upper(key(z->value()))){
1389         y=z;
1390         z=index_node_type::from_impl(z->left());
1391       }
1392       else{
1393         return std::pair<iterator,iterator>(
1394           make_iterator(
1395             lower_range(index_node_type::from_impl(z->left()),z,lower)),
1396           make_iterator(
1397             upper_range(index_node_type::from_impl(z->right()),y,upper)));
1398       }
1399     }
1400
1401     return std::pair<iterator,iterator>(make_iterator(y),make_iterator(y));
1402   }
1403
1404   template<typename LowerBounder,typename UpperBounder>
1405   std::pair<iterator,iterator>
1406   range(LowerBounder,UpperBounder upper,lower_unbounded_tag)const
1407   {
1408     return std::pair<iterator,iterator>(
1409       begin(),
1410       make_iterator(upper_range(root(),header(),upper)));
1411   }
1412
1413   template<typename LowerBounder,typename UpperBounder>
1414   std::pair<iterator,iterator>
1415   range(LowerBounder lower,UpperBounder,upper_unbounded_tag)const
1416   {
1417     return std::pair<iterator,iterator>(
1418       make_iterator(lower_range(root(),header(),lower)),
1419       end());
1420   }
1421
1422   template<typename LowerBounder,typename UpperBounder>
1423   std::pair<iterator,iterator>
1424   range(LowerBounder,UpperBounder,both_unbounded_tag)const
1425   {
1426     return std::pair<iterator,iterator>(begin(),end());
1427   }
1428
1429   template<typename LowerBounder>
1430   index_node_type * lower_range(
1431     index_node_type* top,index_node_type* y,LowerBounder lower)const
1432   {
1433     while(top){
1434       if(lower(key(top->value()))){
1435         y=top;
1436         top=index_node_type::from_impl(top->left());
1437       }
1438       else top=index_node_type::from_impl(top->right());
1439     }
1440
1441     return y;
1442   }
1443
1444   template<typename UpperBounder>
1445   index_node_type * upper_range(
1446     index_node_type* top,index_node_type* y,UpperBounder upper)const
1447   {
1448     while(top){
1449       if(!upper(key(top->value()))){
1450         y=top;
1451         top=index_node_type::from_impl(top->left());
1452       }
1453       else top=index_node_type::from_impl(top->right());
1454     }
1455
1456     return y;
1457   }
1458
1459 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1460   template<typename Archive>
1461   void save_(
1462     Archive& ar,const unsigned int version,const index_saver_type& sm,
1463     ordered_unique_tag)const
1464   {
1465     super::save_(ar,version,sm);
1466   }
1467
1468   template<typename Archive>
1469   void load_(
1470     Archive& ar,const unsigned int version,const index_loader_type& lm,
1471     ordered_unique_tag)
1472   {
1473     super::load_(ar,version,lm);
1474   }
1475
1476   template<typename Archive>
1477   void save_(
1478     Archive& ar,const unsigned int version,const index_saver_type& sm,
1479     ordered_non_unique_tag)const
1480   {
1481     typedef duplicates_iterator<index_node_type,value_compare> dup_iterator;
1482
1483     sm.save(
1484       dup_iterator(begin().get_node(),end().get_node(),value_comp()),
1485       dup_iterator(end().get_node(),value_comp()),
1486       ar,version);
1487     super::save_(ar,version,sm);
1488   }
1489
1490   template<typename Archive>
1491   void load_(
1492     Archive& ar,const unsigned int version,const index_loader_type& lm,
1493     ordered_non_unique_tag)
1494   {
1495     lm.load(
1496       ::boost::bind(
1497         &ordered_index_impl::rearranger,this,
1498         ::boost::arg<1>(),::boost::arg<2>()),
1499       ar,version);
1500     super::load_(ar,version,lm);
1501   }
1502
1503   void rearranger(index_node_type* position,index_node_type *x)
1504   {
1505     if(!position||comp_(key(position->value()),key(x->value()))){
1506       position=lower_bound(key(x->value())).get_node();
1507     }
1508     else if(comp_(key(x->value()),key(position->value()))){
1509       /* inconsistent rearrangement */
1510       throw_exception(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   ordered_index(
1582     const ctor_args_list& args_list,const allocator_type& al):
1583     super(args_list,al){}
1584
1585   ordered_index(const ordered_index& x):super(x){}
1586
1587   ordered_index(const ordered_index& x,do_not_copy_elements_tag):
1588     super(x,do_not_copy_elements_tag()){}
1589 };
1590
1591 #if defined(BOOST_MSVC)
1592 #pragma warning(pop) /* C4355 */
1593 #endif
1594
1595 /* comparison */
1596
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