epoc32/include/stdapis/boost/multi_index/ordered_index.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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)
     5  *
     6  * See http://www.boost.org/libs/multi_index for library home page.
     7  *
     8  * The internal implementation of red-black trees is based on that of SGI STL
     9  * stl_tree.h file: 
    10  *
    11  * Copyright (c) 1996,1997
    12  * Silicon Graphics Computer Systems, Inc.
    13  *
    14  * Permission to use, copy, modify, distribute and sell this software
    15  * and its documentation for any purpose is hereby granted without fee,
    16  * provided that the above copyright notice appear in all copies and
    17  * that both that copyright notice and this permission notice appear
    18  * in supporting documentation.  Silicon Graphics makes no
    19  * representations about the suitability of this software for any
    20  * purpose.  It is provided "as is" without express or implied warranty.
    21  *
    22  *
    23  * Copyright (c) 1994
    24  * Hewlett-Packard Company
    25  *
    26  * Permission to use, copy, modify, distribute and sell this software
    27  * and its documentation for any purpose is hereby granted without fee,
    28  * provided that the above copyright notice appear in all copies and
    29  * that both that copyright notice and this permission notice appear
    30  * in supporting documentation.  Hewlett-Packard Company makes no
    31  * representations about the suitability of this software for any
    32  * purpose.  It is provided "as is" without express or implied warranty.
    33  *
    34  */
    35 
    36 #ifndef BOOST_MULTI_INDEX_ORDERED_INDEX_HPP
    37 #define BOOST_MULTI_INDEX_ORDERED_INDEX_HPP
    38 
    39 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
    40 #pragma once
    41 #endif
    42 
    43 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
    44 #include <algorithm>
    45 #include <boost/call_traits.hpp>
    46 #include <boost/detail/no_exceptions_support.hpp>
    47 #include <boost/detail/workaround.hpp>
    48 #include <boost/iterator/reverse_iterator.hpp>
    49 #include <boost/mpl/push_front.hpp>
    50 #include <boost/multi_index/detail/access_specifier.hpp>
    51 #include <boost/multi_index/detail/bidir_node_iterator.hpp>
    52 #include <boost/multi_index/detail/modify_key_adaptor.hpp>
    53 #include <boost/multi_index/detail/ord_index_node.hpp>
    54 #include <boost/multi_index/detail/ord_index_ops.hpp>
    55 #include <boost/multi_index/detail/safe_ctr_proxy.hpp>
    56 #include <boost/multi_index/detail/safe_mode.hpp>
    57 #include <boost/multi_index/detail/scope_guard.hpp>
    58 #include <boost/multi_index/detail/unbounded.hpp>
    59 #include <boost/multi_index/detail/value_compare.hpp>
    60 #include <boost/multi_index/ordered_index_fwd.hpp>
    61 #include <boost/ref.hpp>
    62 #include <boost/tuple/tuple.hpp>
    63 #include <utility>
    64 
    65 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
    66 #include <boost/archive/archive_exception.hpp>
    67 #include <boost/bind.hpp>
    68 #include <boost/multi_index/detail/duplicates_iterator.hpp>
    69 #include <boost/throw_exception.hpp> 
    70 #endif
    71 
    72 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
    73 #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT                          \
    74   detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \
    75     detail::make_obj_guard(*this,&ordered_index::check_invariant_);          \
    76   BOOST_JOIN(check_invariant_,__LINE__).touch();
    77 #else
    78 #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT
    79 #endif
    80 
    81 namespace boost{
    82 
    83 namespace multi_index{
    84 
    85 namespace detail{
    86 
    87 /* ordered_index adds a layer of ordered indexing to a given Super */
    88 
    89 /* Most of the implementation of unique and non-unique indices is
    90  * shared. We tell from one another on instantiation time by using
    91  * these tags.
    92  */
    93 
    94 struct ordered_unique_tag{};
    95 struct ordered_non_unique_tag{};
    96 
    97 template<
    98   typename KeyFromValue,typename Compare,
    99   typename SuperMeta,typename TagList,typename Category
   100 >
   101 class ordered_index:
   102   BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
   103 
   104 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   105 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
   106   ,public safe_ctr_proxy_impl<
   107     bidir_node_iterator<
   108       ordered_index_node<typename SuperMeta::type::node_type> >,
   109     ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category> >
   110 #else
   111   ,public safe_mode::safe_container<
   112     ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category> >
   113 #endif
   114 #endif
   115 
   116 { 
   117 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
   118     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
   119 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
   120  * lifetime of const references bound to temporaries --precisely what
   121  * scopeguards are.
   122  */
   123 
   124 #pragma parse_mfunc_templ off
   125 #endif
   126 
   127   typedef typename SuperMeta::type                   super;
   128 
   129 protected:
   130   typedef ordered_index_node<
   131     typename super::node_type>                       node_type;
   132 
   133 public:
   134   /* types */
   135 
   136   typedef typename KeyFromValue::result_type         key_type;
   137   typedef typename node_type::value_type             value_type;
   138   typedef KeyFromValue                               key_from_value;
   139   typedef Compare                                    key_compare;
   140   typedef value_comparison<
   141     value_type,KeyFromValue,Compare>                 value_compare;
   142   typedef tuple<key_from_value,key_compare>          ctor_args;
   143   typedef typename super::final_allocator_type       allocator_type;
   144   typedef typename allocator_type::reference         reference;
   145   typedef typename allocator_type::const_reference   const_reference;
   146 
   147 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   148 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
   149   typedef safe_mode::safe_iterator<
   150     bidir_node_iterator<node_type>,
   151     safe_ctr_proxy<
   152       bidir_node_iterator<node_type> > >             iterator;
   153 #else
   154   typedef safe_mode::safe_iterator<
   155     bidir_node_iterator<node_type>,
   156     ordered_index>                                   iterator;
   157 #endif
   158 #else
   159   typedef bidir_node_iterator<node_type>             iterator;
   160 #endif
   161 
   162   typedef iterator                                   const_iterator;
   163 
   164   typedef std::size_t                                size_type;      
   165   typedef std::ptrdiff_t                             difference_type;
   166   typedef typename allocator_type::pointer           pointer;
   167   typedef typename allocator_type::const_pointer     const_pointer;
   168   typedef typename
   169     boost::reverse_iterator<iterator>                reverse_iterator;
   170   typedef typename
   171     boost::reverse_iterator<const_iterator>          const_reverse_iterator;
   172   typedef TagList                                    tag_list;
   173 
   174 protected:
   175   typedef typename super::final_node_type            final_node_type;
   176   typedef tuples::cons<
   177     ctor_args, 
   178     typename super::ctor_args_list>                  ctor_args_list;
   179   typedef typename mpl::push_front<
   180     typename super::index_type_list,
   181     ordered_index>::type                             index_type_list;
   182   typedef typename mpl::push_front<
   183     typename super::iterator_type_list,
   184     iterator>::type    iterator_type_list;
   185   typedef typename mpl::push_front<
   186     typename super::const_iterator_type_list,
   187     const_iterator>::type                            const_iterator_type_list;
   188   typedef typename super::copy_map_type              copy_map_type;
   189 
   190 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
   191   typedef typename super::index_saver_type           index_saver_type;
   192   typedef typename super::index_loader_type          index_loader_type;
   193 #endif
   194 
   195 private:
   196 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   197 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
   198   typedef safe_ctr_proxy_impl<
   199     bidir_node_iterator<node_type>,
   200     ordered_index>                                   safe_super;
   201 #else
   202   typedef safe_mode::safe_container<ordered_index>   safe_super;
   203 #endif
   204 #endif
   205 
   206   typedef typename call_traits<
   207     value_type>::param_type                          value_param_type;
   208   typedef typename call_traits<
   209     key_type>::param_type                            key_param_type;
   210 
   211 public:
   212 
   213   /* construct/copy/destroy
   214    * Default and copy ctors are in the protected section as indices are
   215    * not supposed to be created on their own. No range ctor either.
   216    */
   217 
   218   ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& operator=(
   219     const ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x)
   220   {
   221     this->final()=x.final();
   222     return *this;
   223   }
   224 
   225   allocator_type get_allocator()const
   226   {
   227     return this->final().get_allocator();
   228   }
   229 
   230   /* iterators */
   231 
   232   iterator               begin(){return make_iterator(leftmost());}
   233   const_iterator         begin()const{return make_iterator(leftmost());}
   234   iterator               end(){return make_iterator(header());}
   235   const_iterator         end()const{return make_iterator(header());}
   236   reverse_iterator       rbegin(){return make_reverse_iterator(end());}
   237   const_reverse_iterator rbegin()const{return make_reverse_iterator(end());}
   238   reverse_iterator       rend(){return make_reverse_iterator(begin());}
   239   const_reverse_iterator rend()const{return make_reverse_iterator(begin());}
   240  
   241   /* capacity */
   242 
   243   bool      empty()const{return this->final_empty_();}
   244   size_type size()const{return this->final_size_();}
   245   size_type max_size()const{return this->final_max_size_();}
   246 
   247   /* modifiers */
   248 
   249   std::pair<iterator,bool> insert(value_param_type x)
   250   {
   251     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
   252     std::pair<final_node_type*,bool> p=this->final_insert_(x);
   253     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
   254   }
   255 
   256   iterator insert(iterator position,value_param_type x)
   257   {
   258     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
   259     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
   260     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
   261     std::pair<final_node_type*,bool> p=this->final_insert_(
   262       x,static_cast<final_node_type*>(position.get_node()));
   263     return make_iterator(p.first);
   264   }
   265     
   266   template<typename InputIterator>
   267   void insert(InputIterator first,InputIterator last)
   268   {
   269     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
   270     iterator hint=end();
   271     for(;first!=last;++first)hint=insert(hint,*first);
   272   }
   273 
   274   iterator erase(iterator position)
   275   {
   276     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
   277     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
   278     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
   279     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
   280     this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
   281     return position;
   282   }
   283   
   284   size_type erase(key_param_type x)
   285   {
   286     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
   287     std::pair<iterator,iterator> p=equal_range(x);
   288     size_type s=0;
   289     while(p.first!=p.second){
   290       p.first=erase(p.first);
   291       ++s;
   292     }
   293     return s;
   294   }
   295 
   296   iterator erase(iterator first,iterator last)
   297   {
   298     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
   299     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
   300     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
   301     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
   302     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
   303     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
   304     while(first!=last){
   305       first=erase(first);
   306     }
   307     return first;
   308   }
   309 
   310   bool replace(iterator position,value_param_type x)
   311   {
   312     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
   313     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
   314     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
   315     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
   316     return this->final_replace_(
   317       x,static_cast<final_node_type*>(position.get_node()));
   318   }
   319 
   320   template<typename Modifier>
   321   bool modify(iterator position,Modifier mod)
   322   {
   323     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
   324     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
   325     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
   326     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
   327 
   328 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   329     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
   330      * this is not added. Left it for all compilers as it does no
   331      * harm.
   332      */
   333 
   334     position.detach();
   335 #endif
   336 
   337     return this->final_modify_(
   338       mod,static_cast<final_node_type*>(position.get_node()));
   339   }
   340 
   341   template<typename Modifier>
   342   bool modify_key(iterator position,Modifier mod)
   343   {
   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;
   348     return modify(
   349       position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
   350   }
   351 
   352   void swap(ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x)
   353   {
   354     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
   355     this->final_swap_(x.final());
   356   }
   357 
   358   void clear()
   359   {
   360     BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
   361     this->final_clear_();
   362   }
   363 
   364   /* observers */
   365 
   366   key_from_value key_extractor()const{return key;}
   367   key_compare    key_comp()const{return comp;}
   368   value_compare  value_comp()const{return value_compare(key,comp);}
   369 
   370   /* set operations */
   371 
   372   /* Internally, these ops rely on const_iterator being the same
   373    * type as iterator.
   374    */
   375 
   376   template<typename CompatibleKey>
   377   iterator find(const CompatibleKey& x)const
   378   {
   379     return make_iterator(ordered_index_find(header(),key,x,comp));
   380   }
   381 
   382   template<typename CompatibleKey,typename CompatibleCompare>
   383   iterator find(
   384     const CompatibleKey& x,const CompatibleCompare& comp)const
   385   {
   386     return make_iterator(ordered_index_find(header(),key,x,comp));
   387   }
   388 
   389   template<typename CompatibleKey>
   390   size_type count(const CompatibleKey& x)const
   391   {
   392     return count(x,comp);
   393   }
   394 
   395   template<typename CompatibleKey,typename CompatibleCompare>
   396   size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const
   397   {
   398     std::pair<iterator,iterator> p=equal_range(x,comp);
   399     size_type n=std::distance(p.first,p.second);
   400     return n;
   401   }
   402 
   403   template<typename CompatibleKey>
   404   iterator lower_bound(const CompatibleKey& x)const
   405   {
   406     return make_iterator(ordered_index_lower_bound(header(),key,x,comp));
   407   }
   408 
   409   template<typename CompatibleKey,typename CompatibleCompare>
   410   iterator lower_bound(
   411     const CompatibleKey& x,const CompatibleCompare& comp)const
   412   {
   413     return make_iterator(ordered_index_lower_bound(header(),key,x,comp));
   414   }
   415 
   416   template<typename CompatibleKey>
   417   iterator upper_bound(const CompatibleKey& x)const
   418   {
   419     return make_iterator(ordered_index_upper_bound(header(),key,x,comp));
   420   }
   421 
   422   template<typename CompatibleKey,typename CompatibleCompare>
   423   iterator upper_bound(
   424     const CompatibleKey& x,const CompatibleCompare& comp)const
   425   {
   426     return make_iterator(ordered_index_upper_bound(header(),key,x,comp));
   427   }
   428 
   429   template<typename CompatibleKey>
   430   std::pair<iterator,iterator> equal_range(
   431     const CompatibleKey& x)const
   432   {
   433     return equal_range(x,comp);
   434   }
   435 
   436   template<typename CompatibleKey,typename CompatibleCompare>
   437   std::pair<iterator,iterator> equal_range(
   438     const CompatibleKey& x,const CompatibleCompare& comp)const
   439   {
   440     return std::pair<iterator,iterator>(
   441       lower_bound(x,comp),upper_bound(x,comp));
   442   }
   443 
   444   /* range */
   445 
   446   template<typename LowerBounder,typename UpperBounder>
   447   std::pair<iterator,iterator>
   448   range(LowerBounder lower,UpperBounder upper)const
   449   {
   450     std::pair<iterator,iterator> p(
   451       lower_range(lower),upper_range(upper));
   452     if(p.second!=end()&&(p.first==end()||comp(key(*p.second),key(*p.first)))){
   453       p.second=p.first;
   454     }
   455     return p;
   456   }
   457 
   458 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
   459   ordered_index(const ctor_args_list& args_list,const allocator_type& al):
   460     super(args_list.get_tail(),al),
   461     key(tuples::get<0>(args_list.get_head())),
   462     comp(tuples::get<1>(args_list.get_head()))
   463   {
   464     empty_initialize();
   465   }
   466 
   467   ordered_index(
   468     const ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x):
   469     super(x),
   470 
   471 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   472     safe_super(),
   473 #endif
   474 
   475     key(x.key),
   476     comp(x.comp)
   477   {
   478     /* Copy ctor just takes the key and compare objects from x. The rest is
   479      * done in subsequent call to copy_().
   480      */
   481   }
   482 
   483   ~ordered_index()
   484   {
   485     /* the container is guaranteed to be empty by now */
   486   }
   487 
   488 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   489   iterator       make_iterator(node_type* node){return iterator(node,this);}
   490   const_iterator make_iterator(node_type* node)const
   491     {return const_iterator(node,const_cast<ordered_index*>(this));}
   492 #else
   493   iterator       make_iterator(node_type* node){return iterator(node);}
   494   const_iterator make_iterator(node_type* node)const
   495                    {return const_iterator(node);}
   496 #endif
   497 
   498   void copy_(
   499     const ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x,
   500     const copy_map_type& map)
   501   {
   502     if(!x.root()){
   503       empty_initialize();
   504     }
   505     else{
   506       header()->color()=x.header()->color();
   507 
   508       node_type* root_cpy=map.find(static_cast<final_node_type*>(x.root()));
   509       header()->parent()=root_cpy->impl();
   510 
   511       node_type* leftmost_cpy=map.find(
   512         static_cast<final_node_type*>(x.leftmost()));
   513       header()->left()=leftmost_cpy->impl();
   514 
   515       node_type* rightmost_cpy=map.find(
   516         static_cast<final_node_type*>(x.rightmost()));
   517       header()->right()=rightmost_cpy->impl();
   518 
   519       typedef typename copy_map_type::const_iterator copy_map_iterator;
   520       for(copy_map_iterator it=map.begin(),it_end=map.end();it!=it_end;++it){
   521         node_type* org=it->first;
   522         node_type* cpy=it->second;
   523 
   524         cpy->color()=org->color();
   525 
   526         ordered_index_node_impl* parent_org=org->parent();
   527         if(!parent_org)cpy->parent()=0;
   528         else{
   529           node_type* parent_cpy=map.find(
   530             static_cast<final_node_type*>(node_type::from_impl(parent_org)));
   531           cpy->parent()=parent_cpy->impl();
   532           if(parent_org->left()==org->impl()){
   533             parent_cpy->left()=cpy->impl();
   534           }
   535           else if(parent_org->right()==org->impl()){
   536             /* header() does not satisfy this nor the previous check */
   537             parent_cpy->right()=cpy->impl();
   538           }
   539         }
   540 
   541         if(!org->left())cpy->left()=0;
   542         if(!org->right())cpy->right()=0;
   543       }
   544     }
   545     
   546     super::copy_(x,map);
   547   }
   548 
   549   node_type* insert_(value_param_type v,node_type* x)
   550   {
   551     link_info inf;
   552     if(!link_point(key(v),inf,Category())){
   553       return node_type::from_impl(inf.pos);
   554     }
   555 
   556     node_type* res=static_cast<node_type*>(super::insert_(v,x));
   557     if(res==x){
   558       ordered_index_node_impl::link(
   559         x->impl(),inf.side,inf.pos,header()->impl());
   560     }
   561     return res;
   562   }
   563 
   564   node_type* insert_(value_param_type v,node_type* position,node_type* x)
   565   {
   566     link_info inf;
   567     if(!hinted_link_point(key(v),position,inf,Category())){
   568       return node_type::from_impl(inf.pos);
   569     }
   570 
   571     node_type* res=static_cast<node_type*>(super::insert_(v,position,x));
   572     if(res==x){
   573       ordered_index_node_impl::link(
   574         x->impl(),inf.side,inf.pos,header()->impl());
   575     }
   576     return res;
   577   }
   578 
   579   void erase_(node_type* x)
   580   {
   581     ordered_index_node_impl::rebalance_for_erase(
   582       x->impl(),header()->parent(),header()->left(),header()->right());
   583     super::erase_(x);
   584 
   585 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   586     detach_iterators(x);
   587 #endif
   588   }
   589 
   590   void delete_all_nodes_()
   591   {
   592     delete_all_nodes(root());
   593   }
   594 
   595   void clear_()
   596   {
   597     super::clear_();
   598     empty_initialize();
   599 
   600 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   601     safe_super::detach_dereferenceable_iterators();
   602 #endif
   603   }
   604 
   605   void swap_(ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x)
   606   {
   607     std::swap(key,x.key);
   608     std::swap(comp,x.comp);
   609 
   610 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   611     safe_super::swap(x);
   612 #endif
   613 
   614     super::swap_(x);
   615   }
   616 
   617   bool replace_(value_param_type v,node_type* x)
   618   {
   619     if(in_place(v,x,Category())){
   620       return super::replace_(v,x);
   621     }
   622 
   623     node_type* next=x;
   624     node_type::increment(next);
   625 
   626     ordered_index_node_impl::rebalance_for_erase(
   627       x->impl(),header()->parent(),header()->left(),header()->right());
   628 
   629     BOOST_TRY{
   630       link_info inf;
   631       if(link_point(key(v),inf,Category())&&super::replace_(v,x)){
   632         ordered_index_node_impl::link(
   633           x->impl(),inf.side,inf.pos,header()->impl());
   634         return true;
   635       }
   636       ordered_index_node_impl::restore(
   637         x->impl(),next->impl(),header()->impl());
   638       return false;
   639     }
   640     BOOST_CATCH(...){
   641       ordered_index_node_impl::restore(
   642         x->impl(),next->impl(),header()->impl());
   643       BOOST_RETHROW;
   644     }
   645     BOOST_CATCH_END
   646   }
   647 
   648   bool modify_(node_type* x)
   649   {
   650     bool b;
   651     BOOST_TRY{
   652       b=in_place(x->value(),x,Category());
   653     }
   654     BOOST_CATCH(...){
   655       erase_(x);
   656       BOOST_RETHROW;
   657     }
   658     BOOST_CATCH_END
   659     if(!b){
   660       ordered_index_node_impl::rebalance_for_erase(
   661         x->impl(),header()->parent(),header()->left(),header()->right());
   662       BOOST_TRY{
   663         link_info inf;
   664         if(!link_point(key(x->value()),inf,Category())){
   665           super::erase_(x);
   666 
   667 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   668           detach_iterators(x);
   669 #endif
   670           return false;
   671         }
   672         ordered_index_node_impl::link(
   673           x->impl(),inf.side,inf.pos,header()->impl());
   674       }
   675       BOOST_CATCH(...){
   676         super::erase_(x);
   677 
   678 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   679         detach_iterators(x);
   680 #endif
   681 
   682         BOOST_RETHROW;
   683       }
   684       BOOST_CATCH_END
   685     }
   686 
   687     BOOST_TRY{
   688       if(!super::modify_(x)){
   689         ordered_index_node_impl::rebalance_for_erase(
   690           x->impl(),header()->parent(),header()->left(),header()->right());
   691 
   692 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   693         detach_iterators(x);
   694 #endif
   695 
   696         return false;
   697       }
   698       else return true;
   699     }
   700     BOOST_CATCH(...){
   701       ordered_index_node_impl::rebalance_for_erase(
   702         x->impl(),header()->parent(),header()->left(),header()->right());
   703 
   704 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   705       detach_iterators(x);
   706 #endif
   707 
   708       BOOST_RETHROW;
   709     }
   710     BOOST_CATCH_END
   711   }
   712 
   713 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
   714   /* serialization */
   715 
   716   template<typename Archive>
   717   void save_(
   718     Archive& ar,const unsigned int version,const index_saver_type& sm)const
   719   {
   720     save_(ar,version,sm,Category());
   721   }
   722 
   723   template<typename Archive>
   724   void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
   725   {
   726     load_(ar,version,lm,Category());
   727   }
   728 #endif
   729 
   730 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
   731   /* invariant stuff */
   732 
   733   bool invariant_()const
   734   {
   735     if(size()==0||begin()==end()){
   736       if(size()!=0||begin()!=end()||
   737          header()->left()!=header()->impl()||
   738          header()->right()!=header()->impl())return false;
   739     }
   740     else{
   741       if((size_type)std::distance(begin(),end())!=size())return false;
   742 
   743       std::size_t len=ordered_index_node_impl::black_count(
   744         leftmost()->impl(),root()->impl());
   745       for(const_iterator it=begin(),it_end=end();it!=it_end;++it){
   746         node_type* x=it.get_node();
   747         node_type* left_x=node_type::from_impl(x->left());
   748         node_type* right_x=node_type::from_impl(x->right());
   749 
   750         if(x->color()==red){
   751           if((left_x&&left_x->color()==red)||
   752              (right_x&&right_x->color()==red))return false;
   753         }
   754         if(left_x&&comp(key(x->value()),key(left_x->value())))return false;
   755         if(right_x&&comp(key(right_x->value()),key(x->value())))return false;
   756         if(!left_x&&!right_x&&
   757            ordered_index_node_impl::black_count(
   758              x->impl(),root()->impl())!=len)
   759           return false;
   760       }
   761     
   762       if(leftmost()->impl()!=
   763          ordered_index_node_impl::minimum(root()->impl()))
   764         return false;
   765       if(rightmost()->impl()!=
   766          ordered_index_node_impl::maximum(root()->impl()))
   767         return false;
   768     }
   769 
   770     return super::invariant_();
   771   }
   772 
   773   
   774   /* This forwarding function eases things for the boost::mem_fn construct
   775    * in BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT. Actually,
   776    * final_check_invariant is already an inherited member function of
   777    * ordered_index.
   778    */
   779   void check_invariant_()const{this->final_check_invariant_();}
   780 #endif
   781 
   782 private:
   783   node_type* header()const{return this->final_header();}
   784   node_type* root()const{return node_type::from_impl(header()->parent());}
   785   node_type* leftmost()const{return node_type::from_impl(header()->left());}
   786   node_type* rightmost()const{return node_type::from_impl(header()->right());}
   787 
   788   void empty_initialize()
   789   {
   790     header()->color()=red;
   791     /* used to distinguish header() from root, in iterator.operator++ */
   792     
   793     header()->parent()=0;
   794     header()->left()=header()->impl();
   795     header()->right()=header()->impl();
   796   }
   797 
   798   struct link_info
   799   {
   800     ordered_index_side       side;
   801     ordered_index_node_impl* pos;
   802   };
   803 
   804   bool link_point(key_param_type k,link_info& inf,ordered_unique_tag)
   805   {
   806     node_type* y=header();
   807     node_type* x=root();
   808     bool c=true;
   809     while(x){
   810       y=x;
   811       c=comp(k,key(x->value()));
   812       x=node_type::from_impl(c?x->left():x->right());
   813     }
   814     node_type* yy=y;
   815     if(c){
   816       if(yy==leftmost()){
   817         inf.side=to_left;
   818         inf.pos=y->impl();
   819         return true;
   820       }
   821       else node_type::decrement(yy);
   822     }
   823 
   824     if(comp(key(yy->value()),k)){
   825       inf.side=c?to_left:to_right;
   826       inf.pos=y->impl();
   827       return true;
   828     }
   829     else{
   830       inf.pos=yy->impl();
   831       return false;
   832     }
   833   }
   834 
   835   bool link_point(key_param_type k,link_info& inf,ordered_non_unique_tag)
   836   {
   837     node_type* y=header();
   838     node_type* x=root();
   839     bool c=true;
   840     while (x){
   841      y=x;
   842      c=comp(k,key(x->value()));
   843      x=node_type::from_impl(c?x->left():x->right());
   844     }
   845     inf.side=c?to_left:to_right;
   846     inf.pos=y->impl();
   847     return true;
   848   }
   849 
   850   bool hinted_link_point(
   851     key_param_type k,node_type* position,link_info& inf,ordered_unique_tag)
   852   {
   853     if(position->impl()==header()->left()){ 
   854       if(size()>0&&comp(k,key(position->value()))){
   855         inf.side=to_left;
   856         inf.pos=position->impl();
   857         return true;
   858       }
   859       else return link_point(k,inf,ordered_unique_tag());
   860     } 
   861     else if(position==header()){ 
   862       if(comp(key(rightmost()->value()),k)){
   863         inf.side=to_right;
   864         inf.pos=rightmost()->impl();
   865         return true;
   866       }
   867       else return link_point(k,inf,ordered_unique_tag());
   868     } 
   869     else{
   870       node_type* before=position;
   871       node_type::decrement(before);
   872       if(comp(key(before->value()),k)&&comp(k,key(position->value()))){
   873         if(before->right()==0){
   874           inf.side=to_right;
   875           inf.pos=before->impl();
   876           return true;
   877         }
   878         else{
   879           inf.side=to_left;
   880           inf.pos=position->impl();
   881           return true;
   882         }
   883       } 
   884       else return link_point(k,inf,ordered_unique_tag());
   885     }
   886   }
   887 
   888   bool hinted_link_point(
   889     key_param_type k,node_type* position,link_info& inf,ordered_non_unique_tag)
   890   {
   891     if(position->impl()==header()->left()){ 
   892       if(size()>0&&!comp(key(position->value()),k)){
   893         inf.side=to_left;
   894         inf.pos=position->impl();
   895         return true;
   896       }
   897       else return link_point(k,inf,ordered_non_unique_tag());
   898     } 
   899     else if(position==header()){
   900       if(!comp(k,key(rightmost()->value()))){
   901         inf.side=to_right;
   902         inf.pos=rightmost()->impl();
   903         return true;
   904       }
   905       else return link_point(k,inf,ordered_non_unique_tag());
   906     } 
   907     else{
   908       node_type* before=position;
   909       node_type::decrement(before);
   910       if (!comp(k,key(before->value()))&&!comp(key(position->value()),k)){
   911         if(before->right()==0){
   912           inf.side=to_right;
   913           inf.pos=before->impl();
   914           return true;
   915         }
   916         else{
   917           inf.side=to_left;
   918           inf.pos=position->impl();
   919           return true;
   920         }
   921       } 
   922       else return link_point(k,inf,ordered_non_unique_tag());
   923     }
   924   }
   925 
   926   void delete_all_nodes(node_type* x)
   927   {
   928     if(!x)return;
   929 
   930     delete_all_nodes(node_type::from_impl(x->left()));
   931     delete_all_nodes(node_type::from_impl(x->right()));
   932     this->final_delete_node_(static_cast<final_node_type*>(x));
   933   }
   934 
   935   bool in_place(value_param_type v,node_type* x,ordered_unique_tag)
   936   {
   937     node_type* y;
   938     if(x!=leftmost()){
   939       y=x;
   940       node_type::decrement(y);
   941       if(!comp(key(y->value()),key(v)))return false;
   942     }
   943 
   944     y=x;
   945     node_type::increment(y);
   946     return y==header()||comp(key(v),key(y->value()));
   947   }
   948 
   949   bool in_place(value_param_type v,node_type* x,ordered_non_unique_tag)
   950   {
   951     node_type* y;
   952     if(x!=leftmost()){
   953       y=x;
   954       node_type::decrement(y);
   955       if(comp(key(v),key(y->value())))return false;
   956     }
   957 
   958     y=x;
   959     node_type::increment(y);
   960     return y==header()||!comp(key(y->value()),key(v));
   961   }
   962 
   963 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
   964   void detach_iterators(node_type* x)
   965   {
   966     iterator it=make_iterator(x);
   967     safe_mode::detach_equivalent_iterators(it);
   968   }
   969 #endif
   970 
   971   template<typename LowerBounder>
   972   iterator lower_range(LowerBounder lower)const
   973   {
   974     node_type* y=header();
   975     node_type* z=root();
   976 
   977     while(z){
   978       if(lower(key(z->value()))){
   979         y=z;
   980         z=node_type::from_impl(z->left());
   981       }
   982       else z=node_type::from_impl(z->right());
   983     }
   984 
   985     return make_iterator(y);
   986   }
   987 
   988   iterator lower_range(unbounded_type)const
   989   {
   990     return begin();
   991   }
   992 
   993   template<typename UpperBounder>
   994   iterator upper_range(UpperBounder upper)const
   995   {
   996     node_type* y=header();
   997     node_type* z=root();
   998 
   999     while(z){
  1000       if(!upper(key(z->value()))){
  1001         y=z;
  1002         z=node_type::from_impl(z->left());
  1003       }
  1004       else z=node_type::from_impl(z->right());
  1005     }
  1006 
  1007     return make_iterator(y);
  1008   }
  1009 
  1010   iterator upper_range(unbounded_type)const
  1011   {
  1012     return end();
  1013   }
  1014 
  1015 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  1016   template<typename Archive>
  1017   void save_(
  1018     Archive& ar,const unsigned int version,const index_saver_type& sm,
  1019     ordered_unique_tag)const
  1020   {
  1021     super::save_(ar,version,sm);
  1022   }
  1023 
  1024   template<typename Archive>
  1025   void load_(
  1026     Archive& ar,const unsigned int version,const index_loader_type& lm,
  1027     ordered_unique_tag)
  1028   {
  1029     super::load_(ar,version,lm);
  1030   }
  1031 
  1032   template<typename Archive>
  1033   void save_(
  1034     Archive& ar,const unsigned int version,const index_saver_type& sm,
  1035     ordered_non_unique_tag)const
  1036   {
  1037     typedef duplicates_iterator<node_type,value_compare> dup_iterator;
  1038 
  1039     sm.save(
  1040       dup_iterator(begin().get_node(),end().get_node(),value_comp()),
  1041       dup_iterator(end().get_node(),value_comp()),
  1042       ar,version);
  1043     super::save_(ar,version,sm);
  1044   }
  1045 
  1046   template<typename Archive>
  1047   void load_(
  1048     Archive& ar,const unsigned int version,const index_loader_type& lm,
  1049     ordered_non_unique_tag)
  1050   {
  1051     lm.load(
  1052       ::boost::bind(&ordered_index::rearranger,this,_1,_2),
  1053       ar,version);
  1054     super::load_(ar,version,lm);
  1055   }
  1056 
  1057   void rearranger(node_type* position,node_type *x)
  1058   {
  1059     if(!position||comp(key(position->value()),key(x->value()))){
  1060       position=lower_bound(key(x->value())).get_node();
  1061     }
  1062     else if(comp(key(x->value()),key(position->value()))){
  1063       /* inconsistent rearrangement */
  1064       throw_exception(
  1065         archive::archive_exception(
  1066           archive::archive_exception::other_exception));
  1067     }
  1068     else node_type::increment(position);
  1069 
  1070     if(position!=x){
  1071       ordered_index_node_impl::rebalance_for_erase(
  1072         x->impl(),header()->parent(),header()->left(),header()->right());
  1073       ordered_index_node_impl::restore(
  1074         x->impl(),position->impl(),header()->impl());
  1075     }
  1076   }
  1077 #endif /* serialization */
  1078 
  1079   key_from_value key;
  1080   key_compare    comp;
  1081 
  1082 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
  1083     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
  1084 #pragma parse_mfunc_templ reset
  1085 #endif
  1086 };
  1087 
  1088 /* comparison */
  1089 
  1090 template<
  1091   typename KeyFromValue1,typename Compare1,
  1092   typename SuperMeta1,typename TagList1,typename Category1,
  1093   typename KeyFromValue2,typename Compare2,
  1094   typename SuperMeta2,typename TagList2,typename Category2
  1095 >
  1096 bool operator==(
  1097   const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
  1098   const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
  1099 {
  1100   return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
  1101 }
  1102 
  1103 template<
  1104   typename KeyFromValue1,typename Compare1,
  1105   typename SuperMeta1,typename TagList1,typename Category1,
  1106   typename KeyFromValue2,typename Compare2,
  1107   typename SuperMeta2,typename TagList2,typename Category2
  1108 >
  1109 bool operator<(
  1110   const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
  1111   const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
  1112 {
  1113   return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
  1114 }
  1115 
  1116 template<
  1117   typename KeyFromValue1,typename Compare1,
  1118   typename SuperMeta1,typename TagList1,typename Category1,
  1119   typename KeyFromValue2,typename Compare2,
  1120   typename SuperMeta2,typename TagList2,typename Category2
  1121 >
  1122 bool operator!=(
  1123   const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
  1124   const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
  1125 {
  1126   return !(x==y);
  1127 }
  1128 
  1129 template<
  1130   typename KeyFromValue1,typename Compare1,
  1131   typename SuperMeta1,typename TagList1,typename Category1,
  1132   typename KeyFromValue2,typename Compare2,
  1133   typename SuperMeta2,typename TagList2,typename Category2
  1134 >
  1135 bool operator>(
  1136   const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
  1137   const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
  1138 {
  1139   return y<x;
  1140 }
  1141 
  1142 template<
  1143   typename KeyFromValue1,typename Compare1,
  1144   typename SuperMeta1,typename TagList1,typename Category1,
  1145   typename KeyFromValue2,typename Compare2,
  1146   typename SuperMeta2,typename TagList2,typename Category2
  1147 >
  1148 bool operator>=(
  1149   const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
  1150   const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
  1151 {
  1152   return !(x<y);
  1153 }
  1154 
  1155 template<
  1156   typename KeyFromValue1,typename Compare1,
  1157   typename SuperMeta1,typename TagList1,typename Category1,
  1158   typename KeyFromValue2,typename Compare2,
  1159   typename SuperMeta2,typename TagList2,typename Category2
  1160 >
  1161 bool operator<=(
  1162   const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
  1163   const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
  1164 {
  1165   return !(x>y);
  1166 }
  1167 
  1168 /*  specialized algorithms */
  1169 
  1170 template<
  1171   typename KeyFromValue,typename Compare,
  1172   typename SuperMeta,typename TagList,typename Category
  1173 >
  1174 void swap(
  1175   ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x,
  1176   ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& y)
  1177 {
  1178   x.swap(y);
  1179 }
  1180 
  1181 } /* namespace multi_index::detail */
  1182 
  1183 /* ordered_index specifiers */
  1184 
  1185 template<typename Arg1,typename Arg2,typename Arg3>
  1186 struct ordered_unique
  1187 {
  1188   typedef typename detail::ordered_index_args<
  1189     Arg1,Arg2,Arg3>                                index_args;
  1190   typedef typename index_args::tag_list_type::type tag_list_type;
  1191   typedef typename index_args::key_from_value_type key_from_value_type;
  1192   typedef typename index_args::compare_type        compare_type;
  1193 
  1194   template<typename Super>
  1195   struct node_class
  1196   {
  1197     typedef detail::ordered_index_node<Super> type;
  1198   };
  1199 
  1200   template<typename SuperMeta>
  1201   struct index_class
  1202   {
  1203     typedef detail::ordered_index<
  1204       key_from_value_type,compare_type,
  1205       SuperMeta,tag_list_type,detail::ordered_unique_tag> type;
  1206   };
  1207 };
  1208 
  1209 template<typename Arg1,typename Arg2,typename Arg3>
  1210 struct ordered_non_unique
  1211 {
  1212   typedef detail::ordered_index_args<
  1213     Arg1,Arg2,Arg3>                                index_args;
  1214   typedef typename index_args::tag_list_type::type tag_list_type;
  1215   typedef typename index_args::key_from_value_type key_from_value_type;
  1216   typedef typename index_args::compare_type        compare_type;
  1217 
  1218   template<typename Super>
  1219   struct node_class
  1220   {
  1221     typedef detail::ordered_index_node<Super> type;
  1222   };
  1223 
  1224   template<typename SuperMeta>
  1225   struct index_class
  1226   {
  1227     typedef detail::ordered_index<
  1228       key_from_value_type,compare_type,
  1229       SuperMeta,tag_list_type,detail::ordered_non_unique_tag> type;
  1230   };
  1231 };
  1232 
  1233 } /* namespace multi_index */
  1234 
  1235 } /* namespace boost */
  1236 
  1237 #undef BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT
  1238 
  1239 #endif