1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/multi_index/random_access_index.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,920 @@
1.4 +/* Copyright 2003-2007 Joaquín M López Muñoz.
1.5 + * Distributed under the Boost Software License, Version 1.0.
1.6 + * (See accompanying file LICENSE_1_0.txt or copy at
1.7 + * http://www.boost.org/LICENSE_1_0.txt)
1.8 + *
1.9 + * See http://www.boost.org/libs/multi_index for library home page.
1.10 + */
1.11 +
1.12 +#ifndef BOOST_MULTI_INDEX_RANDOM_ACCESS_INDEX_HPP
1.13 +#define BOOST_MULTI_INDEX_RANDOM_ACCESS_INDEX_HPP
1.14 +
1.15 +#if defined(_MSC_VER)&&(_MSC_VER>=1200)
1.16 +#pragma once
1.17 +#endif
1.18 +
1.19 +#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
1.20 +#include <algorithm>
1.21 +#include <boost/call_traits.hpp>
1.22 +#include <boost/detail/no_exceptions_support.hpp>
1.23 +#include <boost/detail/workaround.hpp>
1.24 +#include <boost/iterator/reverse_iterator.hpp>
1.25 +#include <boost/mpl/push_front.hpp>
1.26 +#include <boost/multi_index/detail/access_specifier.hpp>
1.27 +#include <boost/multi_index/detail/index_node_base.hpp>
1.28 +#include <boost/multi_index/detail/rnd_node_iterator.hpp>
1.29 +#include <boost/multi_index/detail/rnd_index_node.hpp>
1.30 +#include <boost/multi_index/detail/rnd_index_ops.hpp>
1.31 +#include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
1.32 +#include <boost/multi_index/detail/safe_ctr_proxy.hpp>
1.33 +#include <boost/multi_index/detail/safe_mode.hpp>
1.34 +#include <boost/multi_index/detail/scope_guard.hpp>
1.35 +#include <boost/multi_index/random_access_index_fwd.hpp>
1.36 +#include <boost/throw_exception.hpp>
1.37 +#include <boost/tuple/tuple.hpp>
1.38 +#include <cstddef>
1.39 +#include <functional>
1.40 +#include <stdexcept>
1.41 +#include <utility>
1.42 +
1.43 +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1.44 +#include <boost/bind.hpp>
1.45 +#include <boost/multi_index/detail/rnd_index_loader.hpp>
1.46 +#endif
1.47 +
1.48 +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
1.49 +#define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT \
1.50 + detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \
1.51 + detail::make_obj_guard(*this,&random_access_index::check_invariant_); \
1.52 + BOOST_JOIN(check_invariant_,__LINE__).touch();
1.53 +#else
1.54 +#define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT
1.55 +#endif
1.56 +
1.57 +namespace boost{
1.58 +
1.59 +namespace multi_index{
1.60 +
1.61 +namespace detail{
1.62 +
1.63 +/* random_access_index adds a layer of random access indexing
1.64 + * to a given Super
1.65 + */
1.66 +
1.67 +template<typename SuperMeta,typename TagList>
1.68 +class random_access_index:
1.69 + BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
1.70 +
1.71 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.72 +#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
1.73 + ,public safe_ctr_proxy_impl<
1.74 + rnd_node_iterator<
1.75 + random_access_index_node<typename SuperMeta::type::node_type> >,
1.76 + random_access_index<SuperMeta,TagList> >
1.77 +#else
1.78 + ,public safe_mode::safe_container<
1.79 + random_access_index<SuperMeta,TagList> >
1.80 +#endif
1.81 +#endif
1.82 +
1.83 +{
1.84 +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1.85 + BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1.86 +/* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
1.87 + * lifetime of const references bound to temporaries --precisely what
1.88 + * scopeguards are.
1.89 + */
1.90 +
1.91 +#pragma parse_mfunc_templ off
1.92 +#endif
1.93 +
1.94 + typedef typename SuperMeta::type super;
1.95 +
1.96 +protected:
1.97 + typedef random_access_index_node<
1.98 + typename super::node_type> node_type;
1.99 +
1.100 +public:
1.101 + /* types */
1.102 +
1.103 + typedef typename node_type::value_type value_type;
1.104 + typedef tuples::null_type ctor_args;
1.105 + typedef typename super::final_allocator_type allocator_type;
1.106 + typedef typename allocator_type::reference reference;
1.107 + typedef typename allocator_type::const_reference const_reference;
1.108 +
1.109 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.110 +#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
1.111 + typedef safe_mode::safe_iterator<
1.112 + rnd_node_iterator<node_type>,
1.113 + safe_ctr_proxy<
1.114 + rnd_node_iterator<node_type> > > iterator;
1.115 +#else
1.116 + typedef safe_mode::safe_iterator<
1.117 + rnd_node_iterator<node_type>,
1.118 + random_access_index> iterator;
1.119 +#endif
1.120 +#else
1.121 + typedef rnd_node_iterator<node_type> iterator;
1.122 +#endif
1.123 +
1.124 + typedef iterator const_iterator;
1.125 +
1.126 + typedef std::size_t size_type;
1.127 + typedef std::ptrdiff_t difference_type;
1.128 + typedef typename allocator_type::pointer pointer;
1.129 + typedef typename allocator_type::const_pointer const_pointer;
1.130 + typedef typename
1.131 + boost::reverse_iterator<iterator> reverse_iterator;
1.132 + typedef typename
1.133 + boost::reverse_iterator<const_iterator> const_reverse_iterator;
1.134 + typedef TagList tag_list;
1.135 +
1.136 +protected:
1.137 + typedef typename super::final_node_type final_node_type;
1.138 + typedef tuples::cons<
1.139 + ctor_args,
1.140 + typename super::ctor_args_list> ctor_args_list;
1.141 + typedef typename mpl::push_front<
1.142 + typename super::index_type_list,
1.143 + random_access_index>::type index_type_list;
1.144 + typedef typename mpl::push_front<
1.145 + typename super::iterator_type_list,
1.146 + iterator>::type iterator_type_list;
1.147 + typedef typename mpl::push_front<
1.148 + typename super::const_iterator_type_list,
1.149 + const_iterator>::type const_iterator_type_list;
1.150 + typedef typename super::copy_map_type copy_map_type;
1.151 +
1.152 +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1.153 + typedef typename super::index_saver_type index_saver_type;
1.154 + typedef typename super::index_loader_type index_loader_type;
1.155 +#endif
1.156 +
1.157 +private:
1.158 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.159 +#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
1.160 + typedef safe_ctr_proxy_impl<
1.161 + rnd_node_iterator<node_type>,
1.162 + random_access_index> safe_super;
1.163 +#else
1.164 + typedef safe_mode::safe_container<
1.165 + random_access_index> safe_super;
1.166 +#endif
1.167 +#endif
1.168 +
1.169 + typedef typename call_traits<
1.170 + value_type>::param_type value_param_type;
1.171 +
1.172 +public:
1.173 +
1.174 + /* construct/copy/destroy
1.175 + * Default and copy ctors are in the protected section as indices are
1.176 + * not supposed to be created on their own. No range ctor either.
1.177 + */
1.178 +
1.179 + random_access_index<SuperMeta,TagList>& operator=(
1.180 + const random_access_index<SuperMeta,TagList>& x)
1.181 + {
1.182 + this->final()=x.final();
1.183 + return *this;
1.184 + }
1.185 +
1.186 + template <class InputIterator>
1.187 + void assign(InputIterator first,InputIterator last)
1.188 + {
1.189 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.190 + clear();
1.191 + for(;first!=last;++first)push_back(*first);
1.192 + }
1.193 +
1.194 + void assign(size_type n,value_param_type value)
1.195 + {
1.196 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.197 + clear();
1.198 + for(size_type i=0;i<n;++i)push_back(value);
1.199 + }
1.200 +
1.201 + allocator_type get_allocator()const
1.202 + {
1.203 + return this->final().get_allocator();
1.204 + }
1.205 +
1.206 + /* iterators */
1.207 +
1.208 + iterator begin()
1.209 + {return make_iterator(node_type::from_impl(*ptrs.begin()));}
1.210 + const_iterator begin()const
1.211 + {return make_iterator(node_type::from_impl(*ptrs.begin()));}
1.212 + iterator end(){return make_iterator(header());}
1.213 + const_iterator end()const{return make_iterator(header());}
1.214 + reverse_iterator rbegin(){return make_reverse_iterator(end());}
1.215 + const_reverse_iterator rbegin()const{return make_reverse_iterator(end());}
1.216 + reverse_iterator rend(){return make_reverse_iterator(begin());}
1.217 + const_reverse_iterator rend()const{return make_reverse_iterator(begin());}
1.218 +
1.219 + /* capacity */
1.220 +
1.221 + bool empty()const{return this->final_empty_();}
1.222 + size_type size()const{return this->final_size_();}
1.223 + size_type max_size()const{return this->final_max_size_();}
1.224 + size_type capacity()const{return ptrs.capacity();}
1.225 + void reserve(size_type n){ptrs.reserve(n);}
1.226 +
1.227 + void resize(size_type n,value_param_type x=value_type())
1.228 + {
1.229 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.230 + if(n>size())insert(end(),n-size(),x);
1.231 + else if(n<size())erase(begin()+n,end());
1.232 + }
1.233 +
1.234 + /* access: no non-const versions provided as random_access_index
1.235 + * handles const elements.
1.236 + */
1.237 +
1.238 + const_reference operator[](size_type n)const
1.239 + {
1.240 + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(n<size(),safe_mode::out_of_bounds);
1.241 + return node_type::from_impl(*ptrs.at(n))->value();
1.242 + }
1.243 +
1.244 + const_reference at(size_type n)const
1.245 + {
1.246 + if(n>=size())throw_exception(std::out_of_range("random access index"));
1.247 + return node_type::from_impl(*ptrs.at(n))->value();
1.248 + }
1.249 +
1.250 + const_reference front()const{return operator[](0);}
1.251 + const_reference back()const{return operator[](size()-1);}
1.252 +
1.253 + /* modifiers */
1.254 +
1.255 + std::pair<iterator,bool> push_front(value_param_type x)
1.256 + {return insert(begin(),x);}
1.257 + void pop_front(){erase(begin());}
1.258 + std::pair<iterator,bool> push_back(value_param_type x)
1.259 + {return insert(end(),x);}
1.260 + void pop_back(){erase(--end());}
1.261 +
1.262 + std::pair<iterator,bool> insert(iterator position,value_param_type x)
1.263 + {
1.264 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.265 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.266 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.267 + std::pair<final_node_type*,bool> p=this->final_insert_(x);
1.268 + if(p.second&&position.get_node()!=header()){
1.269 + relocate(position.get_node(),p.first);
1.270 + }
1.271 + return std::pair<iterator,bool>(make_iterator(p.first),p.second);
1.272 + }
1.273 +
1.274 + void insert(iterator position,size_type n,value_param_type x)
1.275 + {
1.276 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.277 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.278 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.279 + size_type s=0;
1.280 + BOOST_TRY{
1.281 + while(n--){
1.282 + if(push_back(x).second)++s;
1.283 + }
1.284 + }
1.285 + BOOST_CATCH(...){
1.286 + relocate(position,end()-s,end());
1.287 + BOOST_RETHROW;
1.288 + }
1.289 + BOOST_CATCH_END
1.290 + relocate(position,end()-s,end());
1.291 + }
1.292 +
1.293 + template<typename InputIterator>
1.294 + void insert(iterator position,InputIterator first,InputIterator last)
1.295 + {
1.296 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.297 + size_type s=0;
1.298 + BOOST_TRY{
1.299 + for(;first!=last;++first){
1.300 + if(push_back(*first).second)++s;
1.301 + }
1.302 + }
1.303 + BOOST_CATCH(...){
1.304 + relocate(position,end()-s,end());
1.305 + BOOST_RETHROW;
1.306 + }
1.307 + BOOST_CATCH_END
1.308 + relocate(position,end()-s,end());
1.309 + }
1.310 +
1.311 + iterator erase(iterator position)
1.312 + {
1.313 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.314 + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
1.315 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.316 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.317 + this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
1.318 + return position;
1.319 + }
1.320 +
1.321 + iterator erase(iterator first,iterator last)
1.322 + {
1.323 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
1.324 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
1.325 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
1.326 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
1.327 + BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
1.328 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.329 + difference_type n=last-first;
1.330 + relocate(end(),first,last);
1.331 + while(n--)pop_back();
1.332 + return last;
1.333 + }
1.334 +
1.335 + bool replace(iterator position,value_param_type x)
1.336 + {
1.337 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.338 + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
1.339 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.340 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.341 + return this->final_replace_(
1.342 + x,static_cast<final_node_type*>(position.get_node()));
1.343 + }
1.344 +
1.345 + template<typename Modifier>
1.346 + bool modify(iterator position,Modifier mod)
1.347 + {
1.348 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.349 + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
1.350 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.351 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.352 +
1.353 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.354 + /* MSVC++ 6.0 optimizer on safe mode code chokes if this
1.355 + * this is not added. Left it for all compilers as it does no
1.356 + * harm.
1.357 + */
1.358 +
1.359 + position.detach();
1.360 +#endif
1.361 +
1.362 + return this->final_modify_(
1.363 + mod,static_cast<final_node_type*>(position.get_node()));
1.364 + }
1.365 +
1.366 + void swap(random_access_index<SuperMeta,TagList>& x)
1.367 + {
1.368 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.369 + this->final_swap_(x.final());
1.370 + }
1.371 +
1.372 + void clear()
1.373 + {
1.374 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.375 + this->final_clear_();
1.376 + }
1.377 +
1.378 + /* list operations */
1.379 +
1.380 + void splice(iterator position,random_access_index<SuperMeta,TagList>& x)
1.381 + {
1.382 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.383 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.384 + BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(*this,x);
1.385 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.386 + iterator first=x.begin(),last=x.end();
1.387 + size_type n=0;
1.388 + BOOST_TRY{
1.389 + while(first!=last){
1.390 + if(push_back(*first).second){
1.391 + first=x.erase(first);
1.392 + ++n;
1.393 + }
1.394 + else ++first;
1.395 + }
1.396 + }
1.397 + BOOST_CATCH(...){
1.398 + relocate(position,end()-n,end());
1.399 + BOOST_RETHROW;
1.400 + }
1.401 + BOOST_CATCH_END
1.402 + relocate(position,end()-n,end());
1.403 + }
1.404 +
1.405 + void splice(
1.406 + iterator position,random_access_index<SuperMeta,TagList>& x,iterator i)
1.407 + {
1.408 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.409 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.410 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
1.411 + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
1.412 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x);
1.413 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.414 + if(&x==this)relocate(position,i);
1.415 + else{
1.416 + if(insert(position,*i).second){
1.417 +
1.418 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.419 + /* MSVC++ 6.0 optimizer has a hard time with safe mode, and the following
1.420 + * workaround is needed. Left it for all compilers as it does no
1.421 + * harm.
1.422 + */
1.423 + i.detach();
1.424 + x.erase(x.make_iterator(i.get_node()));
1.425 +#else
1.426 + x.erase(i);
1.427 +#endif
1.428 +
1.429 + }
1.430 + }
1.431 + }
1.432 +
1.433 + void splice(
1.434 + iterator position,random_access_index<SuperMeta,TagList>& x,
1.435 + iterator first,iterator last)
1.436 + {
1.437 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.438 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.439 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
1.440 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
1.441 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x);
1.442 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x);
1.443 + BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
1.444 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.445 + if(&x==this)relocate(position,first,last);
1.446 + else{
1.447 + size_type n=0;
1.448 + BOOST_TRY{
1.449 + while(first!=last){
1.450 + if(push_back(*first).second){
1.451 + first=x.erase(first);
1.452 + ++n;
1.453 + }
1.454 + else ++first;
1.455 + }
1.456 + }
1.457 + BOOST_CATCH(...){
1.458 + relocate(position,end()-n,end());
1.459 + BOOST_RETHROW;
1.460 + }
1.461 + BOOST_CATCH_END
1.462 + relocate(position,end()-n,end());
1.463 + }
1.464 + }
1.465 +
1.466 + void remove(value_param_type value)
1.467 + {
1.468 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.469 + difference_type n=
1.470 + end()-make_iterator(
1.471 + random_access_index_remove<node_type>(
1.472 + ptrs,std::bind2nd(std::equal_to<value_type>(),value)));
1.473 + while(n--)pop_back();
1.474 + }
1.475 +
1.476 + template<typename Predicate>
1.477 + void remove_if(Predicate pred)
1.478 + {
1.479 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.480 + difference_type n=
1.481 + end()-make_iterator(random_access_index_remove<node_type>(ptrs,pred));
1.482 + while(n--)pop_back();
1.483 + }
1.484 +
1.485 + void unique()
1.486 + {
1.487 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.488 + difference_type n=
1.489 + end()-make_iterator(
1.490 + random_access_index_unique<node_type>(
1.491 + ptrs,std::equal_to<value_type>()));
1.492 + while(n--)pop_back();
1.493 + }
1.494 +
1.495 + template <class BinaryPredicate>
1.496 + void unique(BinaryPredicate binary_pred)
1.497 + {
1.498 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.499 + difference_type n=
1.500 + end()-make_iterator(
1.501 + random_access_index_unique<node_type>(ptrs,binary_pred));
1.502 + while(n--)pop_back();
1.503 + }
1.504 +
1.505 + void merge(random_access_index<SuperMeta,TagList>& x)
1.506 + {
1.507 + if(this!=&x){
1.508 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.509 + size_type s=size();
1.510 + splice(end(),x);
1.511 + random_access_index_inplace_merge<node_type>(
1.512 + get_allocator(),ptrs,ptrs.at(s),std::less<value_type>());
1.513 + }
1.514 + }
1.515 +
1.516 + template <typename Compare>
1.517 + void merge(random_access_index<SuperMeta,TagList>& x,Compare comp)
1.518 + {
1.519 + if(this!=&x){
1.520 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.521 + size_type s=size();
1.522 + splice(end(),x);
1.523 + random_access_index_inplace_merge<node_type>(
1.524 + get_allocator(),ptrs,ptrs.at(s),comp);
1.525 + }
1.526 + }
1.527 +
1.528 + void sort()
1.529 + {
1.530 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.531 + random_access_index_sort<node_type>(
1.532 + get_allocator(),ptrs,std::less<value_type>());
1.533 + }
1.534 +
1.535 + template <typename Compare>
1.536 + void sort(Compare comp)
1.537 + {
1.538 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.539 + random_access_index_sort<node_type>(
1.540 + get_allocator(),ptrs,comp);
1.541 + }
1.542 +
1.543 + void reverse()
1.544 + {
1.545 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.546 + random_access_index_node_impl::reverse(ptrs.begin(),ptrs.end());
1.547 + }
1.548 +
1.549 + /* rearrange operations */
1.550 +
1.551 + void relocate(iterator position,iterator i)
1.552 + {
1.553 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.554 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.555 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
1.556 + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
1.557 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,*this);
1.558 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.559 + if(position!=i)relocate(position.get_node(),i.get_node());
1.560 + }
1.561 +
1.562 + void relocate(iterator position,iterator first,iterator last)
1.563 + {
1.564 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.565 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.566 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
1.567 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
1.568 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
1.569 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
1.570 + BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
1.571 + BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last);
1.572 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.573 + if(position!=last)relocate(
1.574 + position.get_node(),first.get_node(),last.get_node());
1.575 + }
1.576 +
1.577 + template<typename InputIterator>
1.578 + void rearrange(InputIterator first)
1.579 + {
1.580 + BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
1.581 + for(random_access_index_node_impl** p0=ptrs.begin(),** p0_end=ptrs.end();
1.582 + p0!=p0_end;++first,++p0){
1.583 + const value_type& v1=*first;
1.584 + random_access_index_node_impl** p1=node_from_value<node_type>(&v1)->up();
1.585 +
1.586 + std::swap(*p0,*p1);
1.587 + (*p0)->up()=p0;
1.588 + (*p1)->up()=p1;
1.589 + }
1.590 + }
1.591 +
1.592 +BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
1.593 + random_access_index(
1.594 + const ctor_args_list& args_list,const allocator_type& al):
1.595 + super(args_list.get_tail(),al),
1.596 + ptrs(al,header()->impl(),0)
1.597 + {
1.598 + }
1.599 +
1.600 + random_access_index(const random_access_index<SuperMeta,TagList>& x):
1.601 + super(x),
1.602 +
1.603 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.604 + safe_super(),
1.605 +#endif
1.606 +
1.607 + ptrs(x.get_allocator(),header()->impl(),x.size())
1.608 + {
1.609 + /* The actual copying takes place in subsequent call to copy_().
1.610 + */
1.611 + }
1.612 +
1.613 + ~random_access_index()
1.614 + {
1.615 + /* the container is guaranteed to be empty by now */
1.616 + }
1.617 +
1.618 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.619 + iterator make_iterator(node_type* node){return iterator(node,this);}
1.620 + const_iterator make_iterator(node_type* node)const
1.621 + {return const_iterator(node,const_cast<random_access_index*>(this));}
1.622 +#else
1.623 + iterator make_iterator(node_type* node){return iterator(node);}
1.624 + const_iterator make_iterator(node_type* node)const
1.625 + {return const_iterator(node);}
1.626 +#endif
1.627 +
1.628 + void copy_(
1.629 + const random_access_index<SuperMeta,TagList>& x,const copy_map_type& map)
1.630 + {
1.631 + for(random_access_index_node_impl** begin_org=x.ptrs.begin(),
1.632 + ** begin_cpy=ptrs.begin(),
1.633 + ** end_org=x.ptrs.end();
1.634 + begin_org!=end_org;++begin_org,++begin_cpy){
1.635 + *begin_cpy=
1.636 + static_cast<node_type*>(
1.637 + map.find(
1.638 + static_cast<final_node_type*>(
1.639 + node_type::from_impl(*begin_org))))->impl();
1.640 + (*begin_cpy)->up()=begin_cpy;
1.641 + }
1.642 +
1.643 + super::copy_(x,map);
1.644 + }
1.645 +
1.646 + node_type* insert_(value_param_type v,node_type* x)
1.647 + {
1.648 + ptrs.room_for_one();
1.649 + node_type* res=static_cast<node_type*>(super::insert_(v,x));
1.650 + if(res==x)ptrs.push_back(x->impl());
1.651 + return res;
1.652 + }
1.653 +
1.654 + node_type* insert_(value_param_type v,node_type* position,node_type* x)
1.655 + {
1.656 + ptrs.room_for_one();
1.657 + node_type* res=static_cast<node_type*>(super::insert_(v,position,x));
1.658 + if(res==x)ptrs.push_back(x->impl());
1.659 + return res;
1.660 + }
1.661 +
1.662 + void erase_(node_type* x)
1.663 + {
1.664 + ptrs.erase(x->impl());
1.665 + super::erase_(x);
1.666 +
1.667 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.668 + detach_iterators(x);
1.669 +#endif
1.670 + }
1.671 +
1.672 + void delete_all_nodes_()
1.673 + {
1.674 + for(random_access_index_node_impl** x=ptrs.begin(),**x_end=ptrs.end();
1.675 + x!=x_end;++x){
1.676 + this->final_delete_node_(
1.677 + static_cast<final_node_type*>(node_type::from_impl(*x)));
1.678 + }
1.679 + }
1.680 +
1.681 + void clear_()
1.682 + {
1.683 + super::clear_();
1.684 + ptrs.clear();
1.685 +
1.686 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.687 + safe_super::detach_dereferenceable_iterators();
1.688 +#endif
1.689 + }
1.690 +
1.691 + void swap_(random_access_index<SuperMeta,TagList>& x)
1.692 + {
1.693 + ptrs.swap(x.ptrs);
1.694 +
1.695 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.696 + safe_super::swap(x);
1.697 +#endif
1.698 +
1.699 + super::swap_(x);
1.700 + }
1.701 +
1.702 + bool replace_(value_param_type v,node_type* x)
1.703 + {
1.704 + return super::replace_(v,x);
1.705 + }
1.706 +
1.707 + bool modify_(node_type* x)
1.708 + {
1.709 + BOOST_TRY{
1.710 + if(!super::modify_(x)){
1.711 + ptrs.erase(x->impl());
1.712 +
1.713 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.714 + detach_iterators(x);
1.715 +#endif
1.716 +
1.717 + return false;
1.718 + }
1.719 + else return true;
1.720 + }
1.721 + BOOST_CATCH(...){
1.722 + ptrs.erase(x->impl());
1.723 +
1.724 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.725 + detach_iterators(x);
1.726 +#endif
1.727 +
1.728 + BOOST_RETHROW;
1.729 + }
1.730 + BOOST_CATCH_END
1.731 + }
1.732 +
1.733 +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1.734 + /* serialization */
1.735 +
1.736 + template<typename Archive>
1.737 + void save_(
1.738 + Archive& ar,const unsigned int version,const index_saver_type& sm)const
1.739 + {
1.740 + sm.save(begin(),end(),ar,version);
1.741 + super::save_(ar,version,sm);
1.742 + }
1.743 +
1.744 + template<typename Archive>
1.745 + void load_(
1.746 + Archive& ar,const unsigned int version,const index_loader_type& lm)
1.747 + {
1.748 + {
1.749 + typedef random_access_index_loader<node_type,allocator_type> loader;
1.750 +
1.751 + loader ld(get_allocator(),ptrs);
1.752 + lm.load(::boost::bind(&loader::rearrange,&ld,_1,_2),ar,version);
1.753 + } /* exit scope so that ld frees its resources */
1.754 + super::load_(ar,version,lm);
1.755 + }
1.756 +#endif
1.757 +
1.758 +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
1.759 + /* invariant stuff */
1.760 +
1.761 + bool invariant_()const
1.762 + {
1.763 + if(size()>capacity())return false;
1.764 + if(size()==0||begin()==end()){
1.765 + if(size()!=0||begin()!=end())return false;
1.766 + }
1.767 + else{
1.768 + size_type s=0;
1.769 + for(const_iterator it=begin(),it_end=end();;++it,++s){
1.770 + if(*(it.get_node()->up())!=it.get_node()->impl())return false;
1.771 + if(it==it_end)break;
1.772 + }
1.773 + if(s!=size())return false;
1.774 + }
1.775 +
1.776 + return super::invariant_();
1.777 + }
1.778 +
1.779 + /* This forwarding function eases things for the boost::mem_fn construct
1.780 + * in BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT. Actually,
1.781 + * final_check_invariant is already an inherited member function of index.
1.782 + */
1.783 + void check_invariant_()const{this->final_check_invariant_();}
1.784 +#endif
1.785 +
1.786 +private:
1.787 + node_type* header()const{return this->final_header();}
1.788 +
1.789 + static void relocate(node_type* position,node_type* x)
1.790 + {
1.791 + random_access_index_node_impl::relocate(position->up(),x->up());
1.792 + }
1.793 +
1.794 + static void relocate(node_type* position,node_type* first,node_type* last)
1.795 + {
1.796 + random_access_index_node_impl::relocate(
1.797 + position->up(),first->up(),last->up());
1.798 + }
1.799 +
1.800 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.801 + void detach_iterators(node_type* x)
1.802 + {
1.803 + iterator it=make_iterator(x);
1.804 + safe_mode::detach_equivalent_iterators(it);
1.805 + }
1.806 +#endif
1.807 +
1.808 + random_access_index_ptr_array<typename super::final_allocator_type> ptrs;
1.809 +
1.810 +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1.811 + BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1.812 +#pragma parse_mfunc_templ reset
1.813 +#endif
1.814 +};
1.815 +
1.816 +/* comparison */
1.817 +
1.818 +template<
1.819 + typename SuperMeta1,typename TagList1,
1.820 + typename SuperMeta2,typename TagList2
1.821 +>
1.822 +bool operator==(
1.823 + const random_access_index<SuperMeta1,TagList1>& x,
1.824 + const random_access_index<SuperMeta2,TagList2>& y)
1.825 +{
1.826 + return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
1.827 +}
1.828 +
1.829 +template<
1.830 + typename SuperMeta1,typename TagList1,
1.831 + typename SuperMeta2,typename TagList2
1.832 +>
1.833 +bool operator<(
1.834 + const random_access_index<SuperMeta1,TagList1>& x,
1.835 + const random_access_index<SuperMeta2,TagList2>& y)
1.836 +{
1.837 + return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
1.838 +}
1.839 +
1.840 +template<
1.841 + typename SuperMeta1,typename TagList1,
1.842 + typename SuperMeta2,typename TagList2
1.843 +>
1.844 +bool operator!=(
1.845 + const random_access_index<SuperMeta1,TagList1>& x,
1.846 + const random_access_index<SuperMeta2,TagList2>& y)
1.847 +{
1.848 + return !(x==y);
1.849 +}
1.850 +
1.851 +template<
1.852 + typename SuperMeta1,typename TagList1,
1.853 + typename SuperMeta2,typename TagList2
1.854 +>
1.855 +bool operator>(
1.856 + const random_access_index<SuperMeta1,TagList1>& x,
1.857 + const random_access_index<SuperMeta2,TagList2>& y)
1.858 +{
1.859 + return y<x;
1.860 +}
1.861 +
1.862 +template<
1.863 + typename SuperMeta1,typename TagList1,
1.864 + typename SuperMeta2,typename TagList2
1.865 +>
1.866 +bool operator>=(
1.867 + const random_access_index<SuperMeta1,TagList1>& x,
1.868 + const random_access_index<SuperMeta2,TagList2>& y)
1.869 +{
1.870 + return !(x<y);
1.871 +}
1.872 +
1.873 +template<
1.874 + typename SuperMeta1,typename TagList1,
1.875 + typename SuperMeta2,typename TagList2
1.876 +>
1.877 +bool operator<=(
1.878 + const random_access_index<SuperMeta1,TagList1>& x,
1.879 + const random_access_index<SuperMeta2,TagList2>& y)
1.880 +{
1.881 + return !(x>y);
1.882 +}
1.883 +
1.884 +/* specialized algorithms */
1.885 +
1.886 +template<typename SuperMeta,typename TagList>
1.887 +void swap(
1.888 + random_access_index<SuperMeta,TagList>& x,
1.889 + random_access_index<SuperMeta,TagList>& y)
1.890 +{
1.891 + x.swap(y);
1.892 +}
1.893 +
1.894 +} /* namespace multi_index::detail */
1.895 +
1.896 +/* random access index specifier */
1.897 +
1.898 +template <typename TagList>
1.899 +struct random_access
1.900 +{
1.901 + BOOST_STATIC_ASSERT(detail::is_tag<TagList>::value);
1.902 +
1.903 + template<typename Super>
1.904 + struct node_class
1.905 + {
1.906 + typedef detail::random_access_index_node<Super> type;
1.907 + };
1.908 +
1.909 + template<typename SuperMeta>
1.910 + struct index_class
1.911 + {
1.912 + typedef detail::random_access_index<
1.913 + SuperMeta,typename TagList::type> type;
1.914 + };
1.915 +};
1.916 +
1.917 +} /* namespace multi_index */
1.918 +
1.919 +} /* namespace boost */
1.920 +
1.921 +#undef BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT
1.922 +
1.923 +#endif