source: NonGTP/Boost/boost/multi_index/sequenced_index.hpp @ 857

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