boost/multi_index/sequenced_index.hpp

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