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

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