boost/multi_index/ordered_index.hpp

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