boost/multi_index/sequenced_index.hpp

   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
   9 #ifndef BOOST_MULTI_INDEX_SEQUENCED_INDEX_HPP
  10 #define BOOST_MULTI_INDEX_SEQUENCED_INDEX_HPP
  11
  12 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
  13 #pragma once
  14 #endif
  15
  16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  17 #include <boost/call_traits.hpp>
  18 #include <boost/detail/allocator_utilities.hpp>
  19 #include <boost/detail/no_exceptions_support.hpp>
  20 #include <boost/detail/workaround.hpp>
  21 #include <boost/iterator/reverse_iterator.hpp>
  22 #include <boost/mpl/bool.hpp>
  23 #include <boost/mpl/not.hpp>
  24 #include <boost/mpl/push_front.hpp>
  25 #include <boost/multi_index/detail/access_specifier.hpp>
  26 #include <boost/multi_index/detail/bidir_node_iterator.hpp>
  27 #include <boost/multi_index/detail/index_node_base.hpp>
  28 #include <boost/multi_index/detail/safe_ctr_proxy.hpp>
  29 #include <boost/multi_index/detail/safe_mode.hpp>
  30 #include <boost/multi_index/detail/scope_guard.hpp>
  31 #include <boost/multi_index/detail/seq_index_node.hpp>
  32 #include <boost/multi_index/detail/seq_index_ops.hpp>
  33 #include <boost/multi_index/sequenced_index_fwd.hpp>
  34 #include <boost/tuple/tuple.hpp>
  35 #include <boost/type_traits/is_integral.hpp>
  36 #include <cstddef>
  37 #include <functional>
  38 #include <utility>
  39
  40 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  41 #include <boost/bind.hpp>
  42 #endif
  43
  44 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
  45 #define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT                          \
  46   detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \
  47     detail::make_obj_guard(*this,&sequenced_index::check_invariant_);        \
  48   BOOST_JOIN(check_invariant_,__LINE__).touch();
  49 #else
  50 #define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT
  51 #endif
  52
  53 namespace boost{
  54
  55 namespace multi_index{
  56
  57 namespace detail{
  58
  59 /* sequenced_index adds a layer of sequenced indexing to a given Super */
  60
  61 template<typename SuperMeta,typename TagList>
  62 class sequenced_index:
  63   BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
  64
  65 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  66 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
  67   ,public safe_ctr_proxy_impl<
  68     bidir_node_iterator<
  69       sequenced_index_node<typename SuperMeta::type::node_type> >,
  70     sequenced_index<SuperMeta,TagList> >
  71 #else
  72   ,public safe_mode::safe_container<
  73     sequenced_index<SuperMeta,TagList> >
  74 #endif
  75 #endif
  76
  77 {
  78 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
  79     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
  80 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
  81  * lifetime of const references bound to temporaries --precisely what
  82  * scopeguards are.
  83  */
  84
  85 #pragma parse_mfunc_templ off
  86 #endif
  87
  88   typedef typename SuperMeta::type                    super;
  89
  90 protected:
  91   typedef sequenced_index_node<
  92     typename super::node_type>                        node_type;
  93
  94 private:
  95   typedef typename node_type::impl_type               node_impl_type;
  96
  97 public:
  98   /* types */
  99
 100   typedef typename node_type::value_type              value_type;
 101   typedef tuples::null_type                           ctor_args;
 102   typedef typename super::final_allocator_type        allocator_type;
 103   typedef typename allocator_type::reference          reference;
 104   typedef typename allocator_type::const_reference    const_reference;
 105
 106 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 107 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
 108   typedef safe_mode::safe_iterator<
 109     bidir_node_iterator<node_type>,
 110     safe_ctr_proxy<
 111       bidir_node_iterator<node_type> > >              iterator;
 112 #else
 113   typedef safe_mode::safe_iterator<
 114     bidir_node_iterator<node_type>,
 115     sequenced_index>                                  iterator;
 116 #endif
 117 #else
 118   typedef bidir_node_iterator<node_type>              iterator;
 119 #endif
 120
 121   typedef iterator                                    const_iterator;
 122
 123   typedef std::size_t                                 size_type;
 124   typedef std::ptrdiff_t                              difference_type;
 125   typedef typename allocator_type::pointer            pointer;
 126   typedef typename allocator_type::const_pointer      const_pointer;
 127   typedef typename
 128     boost::reverse_iterator<iterator>                 reverse_iterator;
 129   typedef typename
 130     boost::reverse_iterator<const_iterator>           const_reverse_iterator;
 131   typedef TagList                                     tag_list;
 132
 133 protected:
 134   typedef typename super::final_node_type     final_node_type;
 135   typedef tuples::cons<
 136     ctor_args,
 137     typename super::ctor_args_list>           ctor_args_list;
 138   typedef typename mpl::push_front<
 139     typename super::index_type_list,
 140     sequenced_index>::type                    index_type_list;
 141   typedef typename mpl::push_front<
 142     typename super::iterator_type_list,
 143     iterator>::type                           iterator_type_list;
 144   typedef typename mpl::push_front<
 145     typename super::const_iterator_type_list,
 146     const_iterator>::type                     const_iterator_type_list;
 147   typedef typename super::copy_map_type       copy_map_type;
 148
 149 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 150   typedef typename super::index_saver_type    index_saver_type;
 151   typedef typename super::index_loader_type   index_loader_type;
 152 #endif
 153
 154 private:
 155 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 156 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
 157   typedef safe_ctr_proxy_impl<
 158     bidir_node_iterator<node_type>,
 159     sequenced_index>                          safe_super;
 160 #else
 161   typedef safe_mode::safe_container<
 162     sequenced_index>                          safe_super;
 163 #endif
 164 #endif
 165
 166   typedef typename call_traits<value_type>::param_type value_param_type;
 167
 168 public:
 169
 170   /* construct/copy/destroy
 171    * Default and copy ctors are in the protected section as indices are
 172    * not supposed to be created on their own. No range ctor either.
 173    */
 174
 175   sequenced_index<SuperMeta,TagList>& operator=(
 176     const sequenced_index<SuperMeta,TagList>& x)
 177   {
 178     this->final()=x.final();
 179     return *this;
 180   }
 181
 182   template <class InputIterator>
 183   void assign(InputIterator first,InputIterator last)
 184   {
 185     assign_iter(first,last,mpl::not_<is_integral<InputIterator> >());
 186   }
 187
 188   void assign(size_type n,value_param_type value)
 189   {
 190     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 191     clear();
 192     for(size_type i=0;i<n;++i)push_back(value);
 193   }
 194
 195   allocator_type get_allocator()const
 196   {
 197     return this->final().get_allocator();
 198   }
 199
 200   /* iterators */
 201
 202   iterator               begin()
 203     {return make_iterator(node_type::from_impl(header()->next()));}
 204   const_iterator         begin()const
 205     {return make_iterator(node_type::from_impl(header()->next()));}
 206   iterator               end(){return make_iterator(header());}
 207   const_iterator         end()const{return make_iterator(header());}
 208   reverse_iterator       rbegin(){return make_reverse_iterator(end());}
 209   const_reverse_iterator rbegin()const{return make_reverse_iterator(end());}
 210   reverse_iterator       rend(){return make_reverse_iterator(begin());}
 211   const_reverse_iterator rend()const{return make_reverse_iterator(begin());}
 212   const_iterator         cbegin()const{return begin();}
 213   const_iterator         cend()const{return end();}
 214   const_reverse_iterator crbegin()const{return rbegin();}
 215   const_reverse_iterator crend()const{return rend();}
 216
 217   iterator iterator_to(const value_type& x)
 218   {
 219     return make_iterator(node_from_value<node_type>(&x));
 220   }
 221
 222   const_iterator iterator_to(const value_type& x)const
 223   {
 224     return make_iterator(node_from_value<node_type>(&x));
 225   }
 226
 227   /* capacity */
 228
 229   bool      empty()const{return this->final_empty_();}
 230   size_type size()const{return this->final_size_();}
 231   size_type max_size()const{return this->final_max_size_();}
 232
 233   void resize(size_type n,value_param_type x=value_type())
 234   {
 235     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 236     if(n>size())insert(end(),n-size(),x);
 237     else if(n<size()){
 238       iterator it;
 239       if(n<=size()/2){
 240         it=begin();
 241         std::advance(it,n);
 242       }
 243       else{
 244         it=end();
 245         for(size_type m=size()-n;m--;--it){}
 246       }
 247       erase(it,end());
 248     }
 249   }
 250
 251   /* access: no non-const versions provided as sequenced_index
 252    * handles const elements.
 253    */
 254
 255   const_reference front()const{return *begin();}
 256   const_reference back()const{return *--end();}
 257
 258   /* modifiers */
 259
 260   std::pair<iterator,bool> push_front(value_param_type x)
 261                              {return insert(begin(),x);}
 262   void                     pop_front(){erase(begin());}
 263   std::pair<iterator,bool> push_back(value_param_type x)
 264                              {return insert(end(),x);}
 265   void                     pop_back(){erase(--end());}
 266
 267   std::pair<iterator,bool> insert(iterator position,value_param_type x)
 268   {
 269     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 270     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 271     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 272     std::pair<final_node_type*,bool> p=this->final_insert_(x);
 273     if(p.second&&position.get_node()!=header()){
 274       relink(position.get_node(),p.first);
 275     }
 276     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
 277   }
 278
 279   void insert(iterator position,size_type n,value_param_type x)
 280   {
 281     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 282     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 283     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 284     for(size_type i=0;i<n;++i)insert(position,x);
 285   }
 286
 287   template<typename InputIterator>
 288   void insert(iterator position,InputIterator first,InputIterator last)
 289   {
 290     insert_iter(position,first,last,mpl::not_<is_integral<InputIterator> >());
 291   }
 292
 293   iterator erase(iterator position)
 294   {
 295     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 296     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 297     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 298     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 299     this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
 300     return position;
 301   }
 302
 303   iterator erase(iterator first,iterator last)
 304   {
 305     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
 306     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
 307     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
 308     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
 309     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
 310     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 311     while(first!=last){
 312       first=erase(first);
 313     }
 314     return first;
 315   }
 316
 317   bool replace(iterator position,value_param_type x)
 318   {
 319     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 320     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 321     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 322     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 323     return this->final_replace_(
 324       x,static_cast<final_node_type*>(position.get_node()));
 325   }
 326
 327   template<typename Modifier>
 328   bool modify(iterator position,Modifier mod)
 329   {
 330     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 331     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 332     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 333     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 334
 335 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 336     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
 337      * this is not added. Left it for all compilers as it does no
 338      * harm.
 339      */
 340
 341     position.detach();
 342 #endif
 343
 344     return this->final_modify_(
 345       mod,static_cast<final_node_type*>(position.get_node()));
 346   }
 347
 348   template<typename Modifier,typename Rollback>
 349   bool modify(iterator position,Modifier mod,Rollback back)
 350   {
 351     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 352     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 353     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 354     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 355
 356 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 357     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
 358      * this is not added. Left it for all compilers as it does no
 359      * harm.
 360      */
 361
 362     position.detach();
 363 #endif
 364
 365     return this->final_modify_(
 366       mod,back,static_cast<final_node_type*>(position.get_node()));
 367   }
 368
 369   void swap(sequenced_index<SuperMeta,TagList>& x)
 370   {
 371     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 372     this->final_swap_(x.final());
 373   }
 374
 375   void clear()
 376   {
 377     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 378     this->final_clear_();
 379   }
 380
 381   /* list operations */
 382
 383   void splice(iterator position,sequenced_index<SuperMeta,TagList>& x)
 384   {
 385     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 386     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 387     BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(*this,x);
 388     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 389     iterator first=x.begin(),last=x.end();
 390     while(first!=last){
 391       if(insert(position,*first).second)first=x.erase(first);
 392       else ++first;
 393     }
 394   }
 395
 396   void splice(iterator position,sequenced_index<SuperMeta,TagList>& x,iterator i)
 397   {
 398     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 399     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 400     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
 401     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
 402     BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x);
 403     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 404     if(&x==this){
 405       if(position!=i)relink(position.get_node(),i.get_node());
 406     }
 407     else{
 408       if(insert(position,*i).second){
 409
 410 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 411     /* MSVC++ 6.0 optimizer has a hard time with safe mode, and the following
 412      * workaround is needed. Left it for all compilers as it does no
 413      * harm.
 414      */
 415         i.detach();
 416         x.erase(x.make_iterator(i.get_node()));
 417 #else
 418         x.erase(i);
 419 #endif
 420
 421       }
 422     }
 423   }
 424
 425   void splice(
 426     iterator position,sequenced_index<SuperMeta,TagList>& x,
 427     iterator first,iterator last)
 428   {
 429     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 430     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 431     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
 432     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
 433     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x);
 434     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x);
 435     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
 436     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 437     if(&x==this){
 438       BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last);
 439       if(position!=last)relink(
 440         position.get_node(),first.get_node(),last.get_node());
 441     }
 442     else{
 443       while(first!=last){
 444         if(insert(position,*first).second)first=x.erase(first);
 445         else ++first;
 446       }
 447     }
 448   }
 449
 450   void remove(value_param_type value)
 451   {
 452     sequenced_index_remove(
 453       *this,std::bind2nd(std::equal_to<value_type>(),value));
 454   }
 455
 456   template<typename Predicate>
 457   void remove_if(Predicate pred)
 458   {
 459     sequenced_index_remove(*this,pred);
 460   }
 461
 462   void unique()
 463   {
 464     sequenced_index_unique(*this,std::equal_to<value_type>());
 465   }
 466
 467   template <class BinaryPredicate>
 468   void unique(BinaryPredicate binary_pred)
 469   {
 470     sequenced_index_unique(*this,binary_pred);
 471   }
 472
 473   void merge(sequenced_index<SuperMeta,TagList>& x)
 474   {
 475     sequenced_index_merge(*this,x,std::less<value_type>());
 476   }
 477
 478   template <typename Compare>
 479   void merge(sequenced_index<SuperMeta,TagList>& x,Compare comp)
 480   {
 481     sequenced_index_merge(*this,x,comp);
 482   }
 483
 484   void sort()
 485   {
 486     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 487     sequenced_index_sort(header(),std::less<value_type>());
 488   }
 489
 490   template <typename Compare>
 491   void sort(Compare comp)
 492   {
 493     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 494     sequenced_index_sort(header(),comp);
 495   }
 496
 497   void reverse()
 498   {
 499     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 500     node_impl_type::reverse(header()->impl());
 501   }
 502
 503   /* rearrange operations */
 504
 505   void relocate(iterator position,iterator i)
 506   {
 507     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 508     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 509     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
 510     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
 511     BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,*this);
 512     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 513     if(position!=i)relink(position.get_node(),i.get_node());
 514   }
 515
 516   void relocate(iterator position,iterator first,iterator last)
 517   {
 518     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 519     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 520     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
 521     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
 522     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
 523     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
 524     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
 525     BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last);
 526     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 527     if(position!=last)relink(
 528       position.get_node(),first.get_node(),last.get_node());
 529   }
 530
 531   template<typename InputIterator>
 532   void rearrange(InputIterator first)
 533   {
 534     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 535     node_type* pos=header();
 536     for(size_type s=size();s--;){
 537       const value_type& v=*first++;
 538       relink(pos,node_from_value<node_type>(&v));
 539     }
 540   }
 541
 542 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
 543   sequenced_index(const ctor_args_list& args_list,const allocator_type& al):
 544     super(args_list.get_tail(),al)
 545   {
 546     empty_initialize();
 547   }
 548
 549   sequenced_index(const sequenced_index<SuperMeta,TagList>& x):
 550     super(x)
 551
 552 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 553     ,safe_super()
 554 #endif
 555
 556   {
 557     /* The actual copying takes place in subsequent call to copy_().
 558      */
 559   }
 560
 561   ~sequenced_index()
 562   {
 563     /* the container is guaranteed to be empty by now */
 564   }
 565
 566 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 567   iterator       make_iterator(node_type* node){return iterator(node,this);}
 568   const_iterator make_iterator(node_type* node)const
 569     {return const_iterator(node,const_cast<sequenced_index*>(this));}
 570 #else
 571   iterator       make_iterator(node_type* node){return iterator(node);}
 572   const_iterator make_iterator(node_type* node)const
 573                    {return const_iterator(node);}
 574 #endif
 575
 576   void copy_(
 577     const sequenced_index<SuperMeta,TagList>& x,const copy_map_type& map)
 578   {
 579     node_type* org=x.header();
 580     node_type* cpy=header();
 581     do{
 582       node_type* next_org=node_type::from_impl(org->next());
 583       node_type* next_cpy=map.find(static_cast<final_node_type*>(next_org));
 584       cpy->next()=next_cpy->impl();
 585       next_cpy->prior()=cpy->impl();
 586       org=next_org;
 587       cpy=next_cpy;
 588     }while(org!=x.header());
 589
 590     super::copy_(x,map);
 591   }
 592
 593   node_type* insert_(value_param_type v,node_type* x)
 594   {
 595     node_type* res=static_cast<node_type*>(super::insert_(v,x));
 596     if(res==x)link(x);
 597     return res;
 598   }
 599
 600   node_type* insert_(value_param_type v,node_type* position,node_type* x)
 601   {
 602     node_type* res=static_cast<node_type*>(super::insert_(v,position,x));
 603     if(res==x)link(x);
 604     return res;
 605   }
 606
 607   void erase_(node_type* x)
 608   {
 609     unlink(x);
 610     super::erase_(x);
 611
 612 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 613     detach_iterators(x);
 614 #endif
 615   }
 616
 617   void delete_all_nodes_()
 618   {
 619     for(node_type* x=node_type::from_impl(header()->next());x!=header();){
 620       node_type* y=node_type::from_impl(x->next());
 621       this->final_delete_node_(static_cast<final_node_type*>(x));
 622       x=y;
 623     }
 624   }
 625
 626   void clear_()
 627   {
 628     super::clear_();
 629     empty_initialize();
 630
 631 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 632     safe_super::detach_dereferenceable_iterators();
 633 #endif
 634   }
 635
 636   void swap_(sequenced_index<SuperMeta,TagList>& x)
 637   {
 638 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 639     safe_super::swap(x);
 640 #endif
 641
 642     super::swap_(x);
 643   }
 644
 645   bool replace_(value_param_type v,node_type* x)
 646   {
 647     return super::replace_(v,x);
 648   }
 649
 650   bool modify_(node_type* x)
 651   {
 652     BOOST_TRY{
 653       if(!super::modify_(x)){
 654         unlink(x);
 655
 656 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 657         detach_iterators(x);
 658 #endif
 659
 660         return false;
 661       }
 662       else return true;
 663     }
 664     BOOST_CATCH(...){
 665       unlink(x);
 666
 667 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 668       detach_iterators(x);
 669 #endif
 670
 671       BOOST_RETHROW;
 672     }
 673     BOOST_CATCH_END
 674   }
 675
 676   bool modify_rollback_(node_type* x)
 677   {
 678     return super::modify_rollback_(x);
 679   }
 680
 681 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 682   /* serialization */
 683
 684   template<typename Archive>
 685   void save_(
 686     Archive& ar,const unsigned int version,const index_saver_type& sm)const
 687   {
 688     sm.save(begin(),end(),ar,version);
 689     super::save_(ar,version,sm);
 690   }
 691
 692   template<typename Archive>
 693   void load_(
 694     Archive& ar,const unsigned int version,const index_loader_type& lm)
 695   {
 696     lm.load(
 697       ::boost::bind(&sequenced_index::rearranger,this,_1,_2),
 698       ar,version);
 699     super::load_(ar,version,lm);
 700   }
 701 #endif
 702
 703 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
 704   /* invariant stuff */
 705
 706   bool invariant_()const
 707   {
 708     if(size()==0||begin()==end()){
 709       if(size()!=0||begin()!=end()||
 710          header()->next()!=header()->impl()||
 711          header()->prior()!=header()->impl())return false;
 712     }
 713     else{
 714       size_type s=0;
 715       for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s){
 716         if(it.get_node()->next()->prior()!=it.get_node()->impl())return false;
 717         if(it.get_node()->prior()->next()!=it.get_node()->impl())return false;
 718       }
 719       if(s!=size())return false;
 720     }
 721
 722     return super::invariant_();
 723   }
 724
 725   /* This forwarding function eases things for the boost::mem_fn construct
 726    * in BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT. Actually,
 727    * final_check_invariant is already an inherited member function of index.
 728    */
 729   void check_invariant_()const{this->final_check_invariant_();}
 730 #endif
 731
 732 private:
 733   node_type* header()const{return this->final_header();}
 734
 735   void empty_initialize()
 736   {
 737     header()->prior()=header()->next()=header()->impl();
 738   }
 739
 740   void link(node_type* x)
 741   {
 742     node_impl_type::link(x->impl(),header()->impl());
 743   };
 744
 745   static void unlink(node_type* x)
 746   {
 747     node_impl_type::unlink(x->impl());
 748   }
 749
 750   static void relink(node_type* position,node_type* x)
 751   {
 752     node_impl_type::relink(position->impl(),x->impl());
 753   }
 754
 755   static void relink(node_type* position,node_type* first,node_type* last)
 756   {
 757     node_impl_type::relink(
 758       position->impl(),first->impl(),last->impl());
 759   }
 760
 761 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 762   void rearranger(node_type* position,node_type *x)
 763   {
 764     if(!position)position=header();
 765     node_type::increment(position);
 766     if(position!=x)relink(position,x);
 767   }
 768 #endif
 769
 770 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 771   void detach_iterators(node_type* x)
 772   {
 773     iterator it=make_iterator(x);
 774     safe_mode::detach_equivalent_iterators(it);
 775   }
 776 #endif
 777
 778   template <class InputIterator>
 779   void assign_iter(InputIterator first,InputIterator last,mpl::true_)
 780   {
 781     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 782     clear();
 783     for(;first!=last;++first)push_back(*first);
 784   }
 785
 786   void assign_iter(size_type n,value_param_type value,mpl::false_)
 787   {
 788     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 789     clear();
 790     for(size_type i=0;i<n;++i)push_back(value);
 791   }
 792
 793   template<typename InputIterator>
 794   void insert_iter(
 795     iterator position,InputIterator first,InputIterator last,mpl::true_)
 796   {
 797     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 798     for(;first!=last;++first)insert(position,*first);
 799   }
 800
 801   void insert_iter(
 802     iterator position,size_type n,value_param_type x,mpl::false_)
 803   {
 804     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 805     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 806     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 807     for(size_type i=0;i<n;++i)insert(position,x);
 808   }
 809
 810 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
 811     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
 812 #pragma parse_mfunc_templ reset
 813 #endif
 814 };
 815
 816 /* comparison */
 817
 818 template<
 819   typename SuperMeta1,typename TagList1,
 820   typename SuperMeta2,typename TagList2
 821 >
 822 bool operator==(
 823   const sequenced_index<SuperMeta1,TagList1>& x,
 824   const sequenced_index<SuperMeta2,TagList2>& y)
 825 {
 826   return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
 827 }
 828
 829 template<
 830   typename SuperMeta1,typename TagList1,
 831   typename SuperMeta2,typename TagList2
 832 >
 833 bool operator<(
 834   const sequenced_index<SuperMeta1,TagList1>& x,
 835   const sequenced_index<SuperMeta2,TagList2>& y)
 836 {
 837   return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
 838 }
 839
 840 template<
 841   typename SuperMeta1,typename TagList1,
 842   typename SuperMeta2,typename TagList2
 843 >
 844 bool operator!=(
 845   const sequenced_index<SuperMeta1,TagList1>& x,
 846   const sequenced_index<SuperMeta2,TagList2>& y)
 847 {
 848   return !(x==y);
 849 }
 850
 851 template<
 852   typename SuperMeta1,typename TagList1,
 853   typename SuperMeta2,typename TagList2
 854 >
 855 bool operator>(
 856   const sequenced_index<SuperMeta1,TagList1>& x,
 857   const sequenced_index<SuperMeta2,TagList2>& y)
 858 {
 859   return y<x;
 860 }
 861
 862 template<
 863   typename SuperMeta1,typename TagList1,
 864   typename SuperMeta2,typename TagList2
 865 >
 866 bool operator>=(
 867   const sequenced_index<SuperMeta1,TagList1>& x,
 868   const sequenced_index<SuperMeta2,TagList2>& y)
 869 {
 870   return !(x<y);
 871 }
 872
 873 template<
 874   typename SuperMeta1,typename TagList1,
 875   typename SuperMeta2,typename TagList2
 876 >
 877 bool operator<=(
 878   const sequenced_index<SuperMeta1,TagList1>& x,
 879   const sequenced_index<SuperMeta2,TagList2>& y)
 880 {
 881   return !(x>y);
 882 }
 883
 884 /*  specialized algorithms */
 885
 886 template<typename SuperMeta,typename TagList>
 887 void swap(
 888   sequenced_index<SuperMeta,TagList>& x,
 889   sequenced_index<SuperMeta,TagList>& y)
 890 {
 891   x.swap(y);
 892 }
 893
 894 } /* namespace multi_index::detail */
 895
 896 /* sequenced index specifier */
 897
 898 template <typename TagList>
 899 struct sequenced
 900 {
 901   BOOST_STATIC_ASSERT(detail::is_tag<TagList>::value);
 902
 903   template<typename Super>
 904   struct node_class
 905   {
 906     typedef detail::sequenced_index_node<Super> type;
 907   };
 908
 909   template<typename SuperMeta>
 910   struct index_class
 911   {
 912     typedef detail::sequenced_index<SuperMeta,typename TagList::type> type;
 913   };
 914 };
 915
 916 } /* namespace multi_index */
 917
 918 } /* namespace boost */
 919
 920 #undef BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT
 921
 922 #endif