test: epoc32/include/stdapis/boost/multi_index/random_access

     1 /* Copyright 2003-2007 Joaquín M López Muñoz.

     2  * Distributed under the Boost Software License, Version 1.0.

     3  * (See accompanying file LICENSE_1_0.txt or copy at

     4  * http://www.boost.org/LICENSE_1_0.txt)

     5  *

     6  * See http://www.boost.org/libs/multi_index for library home page.

     7  */

     9 #ifndef BOOST_MULTI_INDEX_RANDOM_ACCESS_INDEX_HPP

    10 #define BOOST_MULTI_INDEX_RANDOM_ACCESS_INDEX_HPP

    12 #if defined(_MSC_VER)&&(_MSC_VER>=1200)

    13 #pragma once

    14 #endif

    16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */

    17 #include <algorithm>

    18 #include <boost/call_traits.hpp>

    19 #include <boost/detail/no_exceptions_support.hpp>

    20 #include <boost/detail/workaround.hpp>

    21 #include <boost/iterator/reverse_iterator.hpp>

    22 #include <boost/mpl/push_front.hpp>

    23 #include <boost/multi_index/detail/access_specifier.hpp>

    24 #include <boost/multi_index/detail/index_node_base.hpp>

    25 #include <boost/multi_index/detail/rnd_node_iterator.hpp>

    26 #include <boost/multi_index/detail/rnd_index_node.hpp>

    27 #include <boost/multi_index/detail/rnd_index_ops.hpp>

    28 #include <boost/multi_index/detail/rnd_index_ptr_array.hpp>

    29 #include <boost/multi_index/detail/safe_ctr_proxy.hpp>

    30 #include <boost/multi_index/detail/safe_mode.hpp>

    31 #include <boost/multi_index/detail/scope_guard.hpp>

    32 #include <boost/multi_index/random_access_index_fwd.hpp>

    33 #include <boost/throw_exception.hpp>

    34 #include <boost/tuple/tuple.hpp>

    35 #include <cstddef>

    36 #include <functional>

    37 #include <stdexcept>

    38 #include <utility>

    40 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)

    41 #include <boost/bind.hpp>

    42 #include <boost/multi_index/detail/rnd_index_loader.hpp>

    43 #endif

    45 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)

    46 #define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT                          \

    47   detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \

    48     detail::make_obj_guard(*this,&random_access_index::check_invariant_);    \

    49   BOOST_JOIN(check_invariant_,__LINE__).touch();

    50 #else

    51 #define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT

    52 #endif

    54 namespace boost{

    56 namespace multi_index{

    58 namespace detail{

    60 /* random_access_index adds a layer of random access indexing

    61  * to a given Super

    62  */

    64 template<typename SuperMeta,typename TagList>

    65 class random_access_index:

    66   BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type

    68 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

    69 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)

    70   ,public safe_ctr_proxy_impl<

    71     rnd_node_iterator<

    72       random_access_index_node<typename SuperMeta::type::node_type> >,

    73     random_access_index<SuperMeta,TagList> >

    74 #else

    75   ,public safe_mode::safe_container<

    76     random_access_index<SuperMeta,TagList> >

    77 #endif

    78 #endif

    80 {

    81 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\

    82     BOOST_WORKAROUND(__MWERKS__,<=0x3003)

    83 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the

    84  * lifetime of const references bound to temporaries --precisely what

    85  * scopeguards are.

    86  */

    88 #pragma parse_mfunc_templ off

    89 #endif

    91   typedef typename SuperMeta::type                 super;

    93 protected:

    94   typedef random_access_index_node<

    95     typename super::node_type>                     node_type;

    97 public:

    98   /* types */

   100   typedef typename node_type::value_type           value_type;

   101   typedef tuples::null_type                        ctor_args;

   102   typedef typename super::final_allocator_type     allocator_type;

   103   typedef typename allocator_type::reference       reference;

   104   typedef typename allocator_type::const_reference const_reference;

   106 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

   107 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)

   108   typedef safe_mode::safe_iterator<

   109     rnd_node_iterator<node_type>,

   110     safe_ctr_proxy<

   111       rnd_node_iterator<node_type> > >             iterator;

   112 #else

   113   typedef safe_mode::safe_iterator<

   114     rnd_node_iterator<node_type>,

   115     random_access_index>                           iterator;

   116 #endif

   117 #else

   118   typedef rnd_node_iterator<node_type>             iterator;

   119 #endif

   121   typedef iterator                                 const_iterator;

   123   typedef std::size_t                              size_type;

   124   typedef std::ptrdiff_t                           difference_type;

   125   typedef typename allocator_type::pointer         pointer;

   126   typedef typename allocator_type::const_pointer   const_pointer;

   127   typedef typename

   128     boost::reverse_iterator<iterator>              reverse_iterator;

   129   typedef typename

   130     boost::reverse_iterator<const_iterator>        const_reverse_iterator;

   131   typedef TagList                                  tag_list;

   133 protected:

   134   typedef typename super::final_node_type     final_node_type;

   135   typedef tuples::cons<

   136     ctor_args,

   137     typename super::ctor_args_list>           ctor_args_list;

   138   typedef typename mpl::push_front<

   139     typename super::index_type_list,

   140     random_access_index>::type                index_type_list;

   141   typedef typename mpl::push_front<

   142     typename super::iterator_type_list,

   143     iterator>::type                           iterator_type_list;

   144   typedef typename mpl::push_front<

   145     typename super::const_iterator_type_list,

   146     const_iterator>::type                     const_iterator_type_list;

   147   typedef typename super::copy_map_type       copy_map_type;

   149 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)

   150   typedef typename super::index_saver_type    index_saver_type;

   151   typedef typename super::index_loader_type   index_loader_type;

   152 #endif

   154 private:

   155 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

   156 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)

   157   typedef safe_ctr_proxy_impl<

   158     rnd_node_iterator<node_type>,

   159     random_access_index>                      safe_super;

   160 #else

   161   typedef safe_mode::safe_container<

   162     random_access_index>                      safe_super;

   163 #endif

   164 #endif

   166   typedef typename call_traits<

   167     value_type>::param_type                   value_param_type;

   169 public:

   171   /* construct/copy/destroy

   172    * Default and copy ctors are in the protected section as indices are

   173    * not supposed to be created on their own. No range ctor either.

   174    */

   176   random_access_index<SuperMeta,TagList>& operator=(

   177     const random_access_index<SuperMeta,TagList>& x)

   178   {

   179     this->final()=x.final();

   180     return *this;

   181   }

   183   template <class InputIterator>

   184   void assign(InputIterator first,InputIterator last)

   185   {

   186     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   187     clear();

   188     for(;first!=last;++first)push_back(*first);

   189   }

   191   void assign(size_type n,value_param_type value)

   192   {

   193     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   194     clear();

   195     for(size_type i=0;i<n;++i)push_back(value);

   196   }

   198   allocator_type get_allocator()const

   199   {

   200     return this->final().get_allocator();

   201   }

   203   /* iterators */

   205   iterator               begin()

   206     {return make_iterator(node_type::from_impl(*ptrs.begin()));}

   207   const_iterator         begin()const

   208     {return make_iterator(node_type::from_impl(*ptrs.begin()));}

   209   iterator               end(){return make_iterator(header());}

   210   const_iterator         end()const{return make_iterator(header());}

   211   reverse_iterator       rbegin(){return make_reverse_iterator(end());}

   212   const_reverse_iterator rbegin()const{return make_reverse_iterator(end());}

   213   reverse_iterator       rend(){return make_reverse_iterator(begin());}

   214   const_reverse_iterator rend()const{return make_reverse_iterator(begin());}

   216   /* capacity */

   218   bool      empty()const{return this->final_empty_();}

   219   size_type size()const{return this->final_size_();}

   220   size_type max_size()const{return this->final_max_size_();}

   221   size_type capacity()const{return ptrs.capacity();}

   222   void      reserve(size_type n){ptrs.reserve(n);}

   224   void resize(size_type n,value_param_type x=value_type())

   225   {

   226     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   227     if(n>size())insert(end(),n-size(),x);

   228     else if(n<size())erase(begin()+n,end());

   229   }

   231   /* access: no non-const versions provided as random_access_index

   232    * handles const elements.

   233    */

   235   const_reference operator[](size_type n)const

   236   {

   237     BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(n<size(),safe_mode::out_of_bounds);

   238     return node_type::from_impl(*ptrs.at(n))->value();

   239   }

   241   const_reference at(size_type n)const

   242   {

   243     if(n>=size())throw_exception(std::out_of_range("random access index"));

   244     return node_type::from_impl(*ptrs.at(n))->value();

   245   }

   247   const_reference front()const{return operator[](0);}

   248   const_reference back()const{return operator[](size()-1);}

   250   /* modifiers */

   252   std::pair<iterator,bool> push_front(value_param_type x)

   253                              {return insert(begin(),x);}

   254   void                     pop_front(){erase(begin());}

   255   std::pair<iterator,bool> push_back(value_param_type x)

   256                              {return insert(end(),x);}

   257   void                     pop_back(){erase(--end());}

   259   std::pair<iterator,bool> insert(iterator position,value_param_type x)

   260   {

   261     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

   262     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

   263     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   264     std::pair<final_node_type*,bool> p=this->final_insert_(x);

   265     if(p.second&&position.get_node()!=header()){

   266       relocate(position.get_node(),p.first);

   267     }

   268     return std::pair<iterator,bool>(make_iterator(p.first),p.second);

   269   }

   271   void insert(iterator position,size_type n,value_param_type x)

   272   {

   273     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

   274     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

   275     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   276     size_type s=0;

   277     BOOST_TRY{

   278       while(n--){

   279         if(push_back(x).second)++s;

   280       }

   281     }

   282     BOOST_CATCH(...){

   283       relocate(position,end()-s,end());

   284       BOOST_RETHROW;

   285     }

   286     BOOST_CATCH_END

   287     relocate(position,end()-s,end());

   288   }

   290   template<typename InputIterator>

   291   void insert(iterator position,InputIterator first,InputIterator last)

   292   {

   293     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   294     size_type s=0;

   295     BOOST_TRY{

   296       for(;first!=last;++first){

   297         if(push_back(*first).second)++s;

   298       }

   299     }

   300     BOOST_CATCH(...){

   301       relocate(position,end()-s,end());

   302       BOOST_RETHROW;

   303     }

   304     BOOST_CATCH_END

   305     relocate(position,end()-s,end());

   306   }

   308   iterator erase(iterator position)

   309   {

   310     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

   311     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);

   312     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

   313     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   314     this->final_erase_(static_cast<final_node_type*>(position++.get_node()));

   315     return position;

   316   }

   318   iterator erase(iterator first,iterator last)

   319   {

   320     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);

   321     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);

   322     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);

   323     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);

   324     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);

   325     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   326     difference_type n=last-first;

   327     relocate(end(),first,last);

   328     while(n--)pop_back();

   329     return last;

   330   }

   332   bool replace(iterator position,value_param_type x)

   333   {

   334     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

   335     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);

   336     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

   337     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   338     return this->final_replace_(

   339       x,static_cast<final_node_type*>(position.get_node()));

   340   }

   342   template<typename Modifier>

   343   bool modify(iterator position,Modifier mod)

   344   {

   345     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

   346     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);

   347     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

   348     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   350 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

   351     /* MSVC++ 6.0 optimizer on safe mode code chokes if this

   352      * this is not added. Left it for all compilers as it does no

   353      * harm.

   354      */

   356     position.detach();

   357 #endif

   359     return this->final_modify_(

   360       mod,static_cast<final_node_type*>(position.get_node()));

   361   }

   363   void swap(random_access_index<SuperMeta,TagList>& x)

   364   {

   365     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   366     this->final_swap_(x.final());

   367   }

   369   void clear()

   370   {

   371     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   372     this->final_clear_();

   373   }

   375   /* list operations */

   377   void splice(iterator position,random_access_index<SuperMeta,TagList>& x)

   378   {

   379     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

   380     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

   381     BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(*this,x);

   382     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   383     iterator  first=x.begin(),last=x.end();

   384     size_type n=0;

   385     BOOST_TRY{

   386       while(first!=last){

   387         if(push_back(*first).second){

   388           first=x.erase(first);

   389           ++n;

   390         }

   391         else ++first;

   392       }

   393     }

   394     BOOST_CATCH(...){

   395       relocate(position,end()-n,end());

   396       BOOST_RETHROW;

   397     }

   398     BOOST_CATCH_END

   399     relocate(position,end()-n,end());

   400   }

   402   void splice(

   403     iterator position,random_access_index<SuperMeta,TagList>& x,iterator i)

   404   {

   405     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

   406     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

   407     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);

   408     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);

   409     BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x);

   410     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   411     if(&x==this)relocate(position,i);

   412     else{

   413       if(insert(position,*i).second){

   415 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

   416     /* MSVC++ 6.0 optimizer has a hard time with safe mode, and the following

   417      * workaround is needed. Left it for all compilers as it does no

   418      * harm.

   419      */

   420         i.detach();

   421         x.erase(x.make_iterator(i.get_node()));

   422 #else

   423         x.erase(i);

   424 #endif

   426       }

   427     }

   428   }

   430   void splice(

   431     iterator position,random_access_index<SuperMeta,TagList>& x,

   432     iterator first,iterator last)

   433   {

   434     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

   435     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

   436     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);

   437     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);

   438     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x);

   439     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x);

   440     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);

   441     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   442     if(&x==this)relocate(position,first,last);

   443     else{

   444       size_type n=0;

   445       BOOST_TRY{

   446         while(first!=last){

   447           if(push_back(*first).second){

   448             first=x.erase(first);

   449             ++n;

   450           }

   451           else ++first;

   452         }

   453       }

   454       BOOST_CATCH(...){

   455         relocate(position,end()-n,end());

   456         BOOST_RETHROW;

   457       }

   458       BOOST_CATCH_END

   459       relocate(position,end()-n,end());

   460     }

   461   }

   463   void remove(value_param_type value)

   464   {

   465     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   466     difference_type n=

   467       end()-make_iterator(

   468         random_access_index_remove<node_type>(

   469           ptrs,std::bind2nd(std::equal_to<value_type>(),value)));

   470     while(n--)pop_back();

   471   }

   473   template<typename Predicate>

   474   void remove_if(Predicate pred)

   475   {

   476     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   477     difference_type n=

   478       end()-make_iterator(random_access_index_remove<node_type>(ptrs,pred));

   479     while(n--)pop_back();

   480   }

   482   void unique()

   483   {

   484     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   485     difference_type n=

   486       end()-make_iterator(

   487         random_access_index_unique<node_type>(

   488           ptrs,std::equal_to<value_type>()));

   489     while(n--)pop_back();

   490   }

   492   template <class BinaryPredicate>

   493   void unique(BinaryPredicate binary_pred)

   494   {

   495     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   496     difference_type n=

   497       end()-make_iterator(

   498         random_access_index_unique<node_type>(ptrs,binary_pred));

   499     while(n--)pop_back();

   500   }

   502   void merge(random_access_index<SuperMeta,TagList>& x)

   503   {

   504     if(this!=&x){

   505       BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   506       size_type s=size();

   507       splice(end(),x);

   508       random_access_index_inplace_merge<node_type>(

   509         get_allocator(),ptrs,ptrs.at(s),std::less<value_type>());

   510     }

   511   }

   513   template <typename Compare>

   514   void merge(random_access_index<SuperMeta,TagList>& x,Compare comp)

   515   {

   516     if(this!=&x){

   517       BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   518       size_type s=size();

   519       splice(end(),x);

   520       random_access_index_inplace_merge<node_type>(

   521         get_allocator(),ptrs,ptrs.at(s),comp);

   522     }

   523   }

   525   void sort()

   526   {

   527     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   528     random_access_index_sort<node_type>(

   529       get_allocator(),ptrs,std::less<value_type>());

   530   }

   532   template <typename Compare>

   533   void sort(Compare comp)

   534   {

   535     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   536     random_access_index_sort<node_type>(

   537       get_allocator(),ptrs,comp);

   538   }

   540   void reverse()

   541   {

   542     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   543     random_access_index_node_impl::reverse(ptrs.begin(),ptrs.end());

   544   }

   546   /* rearrange operations */

   548   void relocate(iterator position,iterator i)

   549   {

   550     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

   551     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

   552     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);

   553     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);

   554     BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,*this);

   555     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   556     if(position!=i)relocate(position.get_node(),i.get_node());

   557   }

   559   void relocate(iterator position,iterator first,iterator last)

   560   {

   561     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

   562     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

   563     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);

   564     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);

   565     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);

   566     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);

   567     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);

   568     BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last);

   569     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   570     if(position!=last)relocate(

   571       position.get_node(),first.get_node(),last.get_node());

   572   }

   574   template<typename InputIterator>

   575   void rearrange(InputIterator first)

   576   {

   577     BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;

   578     for(random_access_index_node_impl** p0=ptrs.begin(),** p0_end=ptrs.end();

   579         p0!=p0_end;++first,++p0){

   580       const value_type&               v1=*first;

   581       random_access_index_node_impl** p1=node_from_value<node_type>(&v1)->up();

   583       std::swap(*p0,*p1);

   584       (*p0)->up()=p0;

   585       (*p1)->up()=p1;

   586     }

   587   }

   589 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:

   590   random_access_index(

   591     const ctor_args_list& args_list,const allocator_type& al):

   592     super(args_list.get_tail(),al),

   593     ptrs(al,header()->impl(),0)

   594   {

   595   }

   597   random_access_index(const random_access_index<SuperMeta,TagList>& x):

   598     super(x),

   600 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

   601     safe_super(),

   602 #endif

   604     ptrs(x.get_allocator(),header()->impl(),x.size())

   605   {

   606     /* The actual copying takes place in subsequent call to copy_().

   607      */

   608   }

   610   ~random_access_index()

   611   {

   612     /* the container is guaranteed to be empty by now */

   613   }

   615 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

   616   iterator       make_iterator(node_type* node){return iterator(node,this);}

   617   const_iterator make_iterator(node_type* node)const

   618     {return const_iterator(node,const_cast<random_access_index*>(this));}

   619 #else

   620   iterator       make_iterator(node_type* node){return iterator(node);}

   621   const_iterator make_iterator(node_type* node)const

   622                    {return const_iterator(node);}

   623 #endif

   625   void copy_(

   626     const random_access_index<SuperMeta,TagList>& x,const copy_map_type& map)

   627   {

   628     for(random_access_index_node_impl** begin_org=x.ptrs.begin(),

   629                                      ** begin_cpy=ptrs.begin(),

   630                                      ** end_org=x.ptrs.end();

   631         begin_org!=end_org;++begin_org,++begin_cpy){

   632       *begin_cpy=

   633          static_cast<node_type*>(

   634            map.find(

   635              static_cast<final_node_type*>(

   636                node_type::from_impl(*begin_org))))->impl();

   637       (*begin_cpy)->up()=begin_cpy;

   638     }

   640     super::copy_(x,map);

   641   }

   643   node_type* insert_(value_param_type v,node_type* x)

   644   {

   645     ptrs.room_for_one();

   646     node_type* res=static_cast<node_type*>(super::insert_(v,x));

   647     if(res==x)ptrs.push_back(x->impl());

   648     return res;

   649   }

   651   node_type* insert_(value_param_type v,node_type* position,node_type* x)

   652   {

   653     ptrs.room_for_one();

   654     node_type* res=static_cast<node_type*>(super::insert_(v,position,x));

   655     if(res==x)ptrs.push_back(x->impl());

   656     return res;

   657   }

   659   void erase_(node_type* x)

   660   {

   661     ptrs.erase(x->impl());

   662     super::erase_(x);

   664 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

   665     detach_iterators(x);

   666 #endif

   667   }

   669   void delete_all_nodes_()

   670   {

   671     for(random_access_index_node_impl** x=ptrs.begin(),**x_end=ptrs.end();

   672         x!=x_end;++x){

   673       this->final_delete_node_(

   674         static_cast<final_node_type*>(node_type::from_impl(*x)));

   675     }

   676   }

   678   void clear_()

   679   {

   680     super::clear_();

   681     ptrs.clear();

   683 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

   684     safe_super::detach_dereferenceable_iterators();

   685 #endif

   686   }

   688   void swap_(random_access_index<SuperMeta,TagList>& x)

   689   {

   690     ptrs.swap(x.ptrs);

   692 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

   693     safe_super::swap(x);

   694 #endif

   696     super::swap_(x);

   697   }

   699   bool replace_(value_param_type v,node_type* x)

   700   {

   701     return super::replace_(v,x);

   702   }

   704   bool modify_(node_type* x)

   705   {

   706     BOOST_TRY{

   707       if(!super::modify_(x)){

   708         ptrs.erase(x->impl());

   710 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

   711         detach_iterators(x);

   712 #endif

   714         return false;

   715       }

   716       else return true;

   717     }

   718     BOOST_CATCH(...){

   719       ptrs.erase(x->impl());

   721 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

   722       detach_iterators(x);

   723 #endif

   725       BOOST_RETHROW;

   726     }

   727     BOOST_CATCH_END

   728   }

   730 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)

   731   /* serialization */

   733   template<typename Archive>

   734   void save_(

   735     Archive& ar,const unsigned int version,const index_saver_type& sm)const

   736   {

   737     sm.save(begin(),end(),ar,version);

   738     super::save_(ar,version,sm);

   739   }

   741   template<typename Archive>

   742   void load_(

   743     Archive& ar,const unsigned int version,const index_loader_type& lm)

   744   {

   745     {

   746       typedef random_access_index_loader<node_type,allocator_type> loader;

   748       loader ld(get_allocator(),ptrs);

   749       lm.load(::boost::bind(&loader::rearrange,&ld,_1,_2),ar,version);

   750     } /* exit scope so that ld frees its resources */

   751     super::load_(ar,version,lm);

   752   }

   753 #endif

   755 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)

   756   /* invariant stuff */

   758   bool invariant_()const

   759   {

   760     if(size()>capacity())return false;

   761     if(size()==0||begin()==end()){

   762       if(size()!=0||begin()!=end())return false;

   763     }

   764     else{

   765       size_type s=0;

   766       for(const_iterator it=begin(),it_end=end();;++it,++s){

   767         if(*(it.get_node()->up())!=it.get_node()->impl())return false;

   768         if(it==it_end)break;

   769       }

   770       if(s!=size())return false;

   771     }

   773     return super::invariant_();

   774   }

   776   /* This forwarding function eases things for the boost::mem_fn construct

   777    * in BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT. Actually,

   778    * final_check_invariant is already an inherited member function of index.

   779    */

   780   void check_invariant_()const{this->final_check_invariant_();}

   781 #endif

   783 private:

   784   node_type* header()const{return this->final_header();}

   786   static void relocate(node_type* position,node_type* x)

   787   {

   788     random_access_index_node_impl::relocate(position->up(),x->up());

   789   }

   791   static void relocate(node_type* position,node_type* first,node_type* last)

   792   {

   793     random_access_index_node_impl::relocate(

   794       position->up(),first->up(),last->up());

   795   }

   797 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

   798   void detach_iterators(node_type* x)

   799   {

   800     iterator it=make_iterator(x);

   801     safe_mode::detach_equivalent_iterators(it);

   802   }

   803 #endif

   805   random_access_index_ptr_array<typename super::final_allocator_type> ptrs;

   807 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\

   808     BOOST_WORKAROUND(__MWERKS__,<=0x3003)

   809 #pragma parse_mfunc_templ reset

   810 #endif

   811 };

   813 /* comparison */

   815 template<

   816   typename SuperMeta1,typename TagList1,

   817   typename SuperMeta2,typename TagList2

   818 >

   819 bool operator==(

   820   const random_access_index<SuperMeta1,TagList1>& x,

   821   const random_access_index<SuperMeta2,TagList2>& y)

   822 {

   823   return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());

   824 }

   826 template<

   827   typename SuperMeta1,typename TagList1,

   828   typename SuperMeta2,typename TagList2

   829 >

   830 bool operator<(

   831   const random_access_index<SuperMeta1,TagList1>& x,

   832   const random_access_index<SuperMeta2,TagList2>& y)

   833 {

   834   return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());

   835 }

   837 template<

   838   typename SuperMeta1,typename TagList1,

   839   typename SuperMeta2,typename TagList2

   840 >

   841 bool operator!=(

   842   const random_access_index<SuperMeta1,TagList1>& x,

   843   const random_access_index<SuperMeta2,TagList2>& y)

   844 {

   845   return !(x==y);

   846 }

   848 template<

   849   typename SuperMeta1,typename TagList1,

   850   typename SuperMeta2,typename TagList2

   851 >

   852 bool operator>(

   853   const random_access_index<SuperMeta1,TagList1>& x,

   854   const random_access_index<SuperMeta2,TagList2>& y)

   855 {

   856   return y<x;

   857 }

   859 template<

   860   typename SuperMeta1,typename TagList1,

   861   typename SuperMeta2,typename TagList2

   862 >

   863 bool operator>=(

   864   const random_access_index<SuperMeta1,TagList1>& x,

   865   const random_access_index<SuperMeta2,TagList2>& y)

   866 {

   867   return !(x<y);

   868 }

   870 template<

   871   typename SuperMeta1,typename TagList1,

   872   typename SuperMeta2,typename TagList2

   873 >

   874 bool operator<=(

   875   const random_access_index<SuperMeta1,TagList1>& x,

   876   const random_access_index<SuperMeta2,TagList2>& y)

   877 {

   878   return !(x>y);

   879 }

   881 /*  specialized algorithms */

   883 template<typename SuperMeta,typename TagList>

   884 void swap(

   885   random_access_index<SuperMeta,TagList>& x,

   886   random_access_index<SuperMeta,TagList>& y)

   887 {

   888   x.swap(y);

   889 }

   891 } /* namespace multi_index::detail */

   893 /* random access index specifier */

   895 template <typename TagList>

   896 struct random_access

   897 {

   898   BOOST_STATIC_ASSERT(detail::is_tag<TagList>::value);

   900   template<typename Super>

   901   struct node_class

   902   {

   903     typedef detail::random_access_index_node<Super> type;

   904   };

   906   template<typename SuperMeta>

   907   struct index_class

   908   {

   909     typedef detail::random_access_index<

   910       SuperMeta,typename TagList::type>  type;

   911   };

   912 };

   914 } /* namespace multi_index */

   916 } /* namespace boost */

   918 #undef BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT

   920 #endif

author	William Roberts <williamr@symbian.org>
	Wed, 31 Mar 2010 12:33:34 +0100
branch	Symbian3
changeset 4	837f303aceeb
permissions	-rw-r--r--