/* Copyright 2003-2008 Joaquin M Lopez Munoz. | |
* Distributed under the Boost Software License, Version 1.0. | |
* (See accompanying file LICENSE_1_0.txt or copy at | |
* http://www.boost.org/LICENSE_1_0.txt) | |
* | |
* See http://www.boost.org/libs/multi_index for library home page. | |
*/ | |
#ifndef BOOST_MULTI_INDEX_RANDOM_ACCESS_INDEX_HPP | |
#define BOOST_MULTI_INDEX_RANDOM_ACCESS_INDEX_HPP | |
#if defined(_MSC_VER)&&(_MSC_VER>=1200) | |
#pragma once | |
#endif | |
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ | |
#include <algorithm> | |
#include <boost/call_traits.hpp> | |
#include <boost/detail/no_exceptions_support.hpp> | |
#include <boost/detail/workaround.hpp> | |
#include <boost/iterator/reverse_iterator.hpp> | |
#include <boost/mpl/bool.hpp> | |
#include <boost/mpl/not.hpp> | |
#include <boost/mpl/push_front.hpp> | |
#include <boost/multi_index/detail/access_specifier.hpp> | |
#include <boost/multi_index/detail/index_node_base.hpp> | |
#include <boost/multi_index/detail/rnd_node_iterator.hpp> | |
#include <boost/multi_index/detail/rnd_index_node.hpp> | |
#include <boost/multi_index/detail/rnd_index_ops.hpp> | |
#include <boost/multi_index/detail/rnd_index_ptr_array.hpp> | |
#include <boost/multi_index/detail/safe_ctr_proxy.hpp> | |
#include <boost/multi_index/detail/safe_mode.hpp> | |
#include <boost/multi_index/detail/scope_guard.hpp> | |
#include <boost/multi_index/random_access_index_fwd.hpp> | |
#include <boost/throw_exception.hpp> | |
#include <boost/tuple/tuple.hpp> | |
#include <boost/type_traits/is_integral.hpp> | |
#include <cstddef> | |
#include <functional> | |
#include <stdexcept> | |
#include <utility> | |
#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) | |
#include <boost/bind.hpp> | |
#include <boost/multi_index/detail/rnd_index_loader.hpp> | |
#endif | |
#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) | |
#define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT \ | |
detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \ | |
detail::make_obj_guard(*this,&random_access_index::check_invariant_); \ | |
BOOST_JOIN(check_invariant_,__LINE__).touch(); | |
#else | |
#define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT | |
#endif | |
namespace boost{ | |
namespace multi_index{ | |
namespace detail{ | |
/* random_access_index adds a layer of random access indexing | |
* to a given Super | |
*/ | |
template<typename SuperMeta,typename TagList> | |
class random_access_index: | |
BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type | |
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
#if BOOST_WORKAROUND(BOOST_MSVC,<1300) | |
,public safe_ctr_proxy_impl< | |
rnd_node_iterator< | |
random_access_index_node<typename SuperMeta::type::node_type> >, | |
random_access_index<SuperMeta,TagList> > | |
#else | |
,public safe_mode::safe_container< | |
random_access_index<SuperMeta,TagList> > | |
#endif | |
#endif | |
{ | |
#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ | |
BOOST_WORKAROUND(__MWERKS__,<=0x3003) | |
/* The "ISO C++ Template Parser" option in CW8.3 has a problem with the | |
* lifetime of const references bound to temporaries --precisely what | |
* scopeguards are. | |
*/ | |
#pragma parse_mfunc_templ off | |
#endif | |
typedef typename SuperMeta::type super; | |
protected: | |
typedef random_access_index_node< | |
typename super::node_type> node_type; | |
private: | |
typedef typename node_type::impl_type node_impl_type; | |
typedef random_access_index_ptr_array< | |
typename super::final_allocator_type> ptr_array; | |
typedef typename ptr_array::pointer node_impl_ptr_pointer; | |
public: | |
/* types */ | |
typedef typename node_type::value_type value_type; | |
typedef tuples::null_type ctor_args; | |
typedef typename super::final_allocator_type allocator_type; | |
typedef typename allocator_type::reference reference; | |
typedef typename allocator_type::const_reference const_reference; | |
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
#if BOOST_WORKAROUND(BOOST_MSVC,<1300) | |
typedef safe_mode::safe_iterator< | |
rnd_node_iterator<node_type>, | |
safe_ctr_proxy< | |
rnd_node_iterator<node_type> > > iterator; | |
#else | |
typedef safe_mode::safe_iterator< | |
rnd_node_iterator<node_type>, | |
random_access_index> iterator; | |
#endif | |
#else | |
typedef rnd_node_iterator<node_type> iterator; | |
#endif | |
typedef iterator const_iterator; | |
typedef std::size_t size_type; | |
typedef std::ptrdiff_t difference_type; | |
typedef typename allocator_type::pointer pointer; | |
typedef typename allocator_type::const_pointer const_pointer; | |
typedef typename | |
boost::reverse_iterator<iterator> reverse_iterator; | |
typedef typename | |
boost::reverse_iterator<const_iterator> const_reverse_iterator; | |
typedef TagList tag_list; | |
protected: | |
typedef typename super::final_node_type final_node_type; | |
typedef tuples::cons< | |
ctor_args, | |
typename super::ctor_args_list> ctor_args_list; | |
typedef typename mpl::push_front< | |
typename super::index_type_list, | |
random_access_index>::type index_type_list; | |
typedef typename mpl::push_front< | |
typename super::iterator_type_list, | |
iterator>::type iterator_type_list; | |
typedef typename mpl::push_front< | |
typename super::const_iterator_type_list, | |
const_iterator>::type const_iterator_type_list; | |
typedef typename super::copy_map_type copy_map_type; | |
#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) | |
typedef typename super::index_saver_type index_saver_type; | |
typedef typename super::index_loader_type index_loader_type; | |
#endif | |
private: | |
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
#if BOOST_WORKAROUND(BOOST_MSVC,<1300) | |
typedef safe_ctr_proxy_impl< | |
rnd_node_iterator<node_type>, | |
random_access_index> safe_super; | |
#else | |
typedef safe_mode::safe_container< | |
random_access_index> safe_super; | |
#endif | |
#endif | |
typedef typename call_traits< | |
value_type>::param_type value_param_type; | |
public: | |
/* construct/copy/destroy | |
* Default and copy ctors are in the protected section as indices are | |
* not supposed to be created on their own. No range ctor either. | |
*/ | |
random_access_index<SuperMeta,TagList>& operator=( | |
const random_access_index<SuperMeta,TagList>& x) | |
{ | |
this->final()=x.final(); | |
return *this; | |
} | |
template <class InputIterator> | |
void assign(InputIterator first,InputIterator last) | |
{ | |
assign_iter(first,last,mpl::not_<is_integral<InputIterator> >()); | |
} | |
void assign(size_type n,value_param_type value) | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
clear(); | |
for(size_type i=0;i<n;++i)push_back(value); | |
} | |
allocator_type get_allocator()const | |
{ | |
return this->final().get_allocator(); | |
} | |
/* iterators */ | |
iterator begin() | |
{return make_iterator(node_type::from_impl(*ptrs.begin()));} | |
const_iterator begin()const | |
{return make_iterator(node_type::from_impl(*ptrs.begin()));} | |
iterator end(){return make_iterator(header());} | |
const_iterator end()const{return make_iterator(header());} | |
reverse_iterator rbegin(){return make_reverse_iterator(end());} | |
const_reverse_iterator rbegin()const{return make_reverse_iterator(end());} | |
reverse_iterator rend(){return make_reverse_iterator(begin());} | |
const_reverse_iterator rend()const{return make_reverse_iterator(begin());} | |
const_iterator cbegin()const{return begin();} | |
const_iterator cend()const{return end();} | |
const_reverse_iterator crbegin()const{return rbegin();} | |
const_reverse_iterator crend()const{return rend();} | |
iterator iterator_to(const value_type& x) | |
{ | |
return make_iterator(node_from_value<node_type>(&x)); | |
} | |
const_iterator iterator_to(const value_type& x)const | |
{ | |
return make_iterator(node_from_value<node_type>(&x)); | |
} | |
/* capacity */ | |
bool empty()const{return this->final_empty_();} | |
size_type size()const{return this->final_size_();} | |
size_type max_size()const{return this->final_max_size_();} | |
size_type capacity()const{return ptrs.capacity();} | |
void reserve(size_type n){ptrs.reserve(n);} | |
void resize(size_type n,value_param_type x=value_type()) | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
if(n>size())insert(end(),n-size(),x); | |
else if(n<size())erase(begin()+n,end()); | |
} | |
/* access: no non-const versions provided as random_access_index | |
* handles const elements. | |
*/ | |
const_reference operator[](size_type n)const | |
{ | |
BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(n<size(),safe_mode::out_of_bounds); | |
return node_type::from_impl(*ptrs.at(n))->value(); | |
} | |
const_reference at(size_type n)const | |
{ | |
if(n>=size())throw_exception(std::out_of_range("random access index")); | |
return node_type::from_impl(*ptrs.at(n))->value(); | |
} | |
const_reference front()const{return operator[](0);} | |
const_reference back()const{return operator[](size()-1);} | |
/* modifiers */ | |
std::pair<iterator,bool> push_front(value_param_type x) | |
{return insert(begin(),x);} | |
void pop_front(){erase(begin());} | |
std::pair<iterator,bool> push_back(value_param_type x) | |
{return insert(end(),x);} | |
void pop_back(){erase(--end());} | |
std::pair<iterator,bool> insert(iterator position,value_param_type x) | |
{ | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
std::pair<final_node_type*,bool> p=this->final_insert_(x); | |
if(p.second&&position.get_node()!=header()){ | |
relocate(position.get_node(),p.first); | |
} | |
return std::pair<iterator,bool>(make_iterator(p.first),p.second); | |
} | |
void insert(iterator position,size_type n,value_param_type x) | |
{ | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
size_type s=0; | |
BOOST_TRY{ | |
while(n--){ | |
if(push_back(x).second)++s; | |
} | |
} | |
BOOST_CATCH(...){ | |
relocate(position,end()-s,end()); | |
BOOST_RETHROW; | |
} | |
BOOST_CATCH_END | |
relocate(position,end()-s,end()); | |
} | |
template<typename InputIterator> | |
void insert(iterator position,InputIterator first,InputIterator last) | |
{ | |
insert_iter(position,first,last,mpl::not_<is_integral<InputIterator> >()); | |
} | |
iterator erase(iterator position) | |
{ | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
this->final_erase_(static_cast<final_node_type*>(position++.get_node())); | |
return position; | |
} | |
iterator erase(iterator first,iterator last) | |
{ | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first); | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this); | |
BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last); | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
difference_type n=last-first; | |
relocate(end(),first,last); | |
while(n--)pop_back(); | |
return last; | |
} | |
bool replace(iterator position,value_param_type x) | |
{ | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
return this->final_replace_( | |
x,static_cast<final_node_type*>(position.get_node())); | |
} | |
template<typename Modifier> | |
bool modify(iterator position,Modifier mod) | |
{ | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
/* MSVC++ 6.0 optimizer on safe mode code chokes if this | |
* this is not added. Left it for all compilers as it does no | |
* harm. | |
*/ | |
position.detach(); | |
#endif | |
return this->final_modify_( | |
mod,static_cast<final_node_type*>(position.get_node())); | |
} | |
template<typename Modifier,typename Rollback> | |
bool modify(iterator position,Modifier mod,Rollback back) | |
{ | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
/* MSVC++ 6.0 optimizer on safe mode code chokes if this | |
* this is not added. Left it for all compilers as it does no | |
* harm. | |
*/ | |
position.detach(); | |
#endif | |
return this->final_modify_( | |
mod,back,static_cast<final_node_type*>(position.get_node())); | |
} | |
void swap(random_access_index<SuperMeta,TagList>& x) | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
this->final_swap_(x.final()); | |
} | |
void clear() | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
this->final_clear_(); | |
} | |
/* list operations */ | |
void splice(iterator position,random_access_index<SuperMeta,TagList>& x) | |
{ | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(*this,x); | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
iterator first=x.begin(),last=x.end(); | |
size_type n=0; | |
BOOST_TRY{ | |
while(first!=last){ | |
if(push_back(*first).second){ | |
first=x.erase(first); | |
++n; | |
} | |
else ++first; | |
} | |
} | |
BOOST_CATCH(...){ | |
relocate(position,end()-n,end()); | |
BOOST_RETHROW; | |
} | |
BOOST_CATCH_END | |
relocate(position,end()-n,end()); | |
} | |
void splice( | |
iterator position,random_access_index<SuperMeta,TagList>& x,iterator i) | |
{ | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i); | |
BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x); | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
if(&x==this)relocate(position,i); | |
else{ | |
if(insert(position,*i).second){ | |
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
/* MSVC++ 6.0 optimizer has a hard time with safe mode, and the following | |
* workaround is needed. Left it for all compilers as it does no | |
* harm. | |
*/ | |
i.detach(); | |
x.erase(x.make_iterator(i.get_node())); | |
#else | |
x.erase(i); | |
#endif | |
} | |
} | |
} | |
void splice( | |
iterator position,random_access_index<SuperMeta,TagList>& x, | |
iterator first,iterator last) | |
{ | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first); | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x); | |
BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last); | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
if(&x==this)relocate(position,first,last); | |
else{ | |
size_type n=0; | |
BOOST_TRY{ | |
while(first!=last){ | |
if(push_back(*first).second){ | |
first=x.erase(first); | |
++n; | |
} | |
else ++first; | |
} | |
} | |
BOOST_CATCH(...){ | |
relocate(position,end()-n,end()); | |
BOOST_RETHROW; | |
} | |
BOOST_CATCH_END | |
relocate(position,end()-n,end()); | |
} | |
} | |
void remove(value_param_type value) | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
difference_type n= | |
end()-make_iterator( | |
random_access_index_remove<node_type>( | |
ptrs,std::bind2nd(std::equal_to<value_type>(),value))); | |
while(n--)pop_back(); | |
} | |
template<typename Predicate> | |
void remove_if(Predicate pred) | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
difference_type n= | |
end()-make_iterator(random_access_index_remove<node_type>(ptrs,pred)); | |
while(n--)pop_back(); | |
} | |
void unique() | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
difference_type n= | |
end()-make_iterator( | |
random_access_index_unique<node_type>( | |
ptrs,std::equal_to<value_type>())); | |
while(n--)pop_back(); | |
} | |
template <class BinaryPredicate> | |
void unique(BinaryPredicate binary_pred) | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
difference_type n= | |
end()-make_iterator( | |
random_access_index_unique<node_type>(ptrs,binary_pred)); | |
while(n--)pop_back(); | |
} | |
void merge(random_access_index<SuperMeta,TagList>& x) | |
{ | |
if(this!=&x){ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
size_type s=size(); | |
splice(end(),x); | |
random_access_index_inplace_merge<node_type>( | |
get_allocator(),ptrs,ptrs.at(s),std::less<value_type>()); | |
} | |
} | |
template <typename Compare> | |
void merge(random_access_index<SuperMeta,TagList>& x,Compare comp) | |
{ | |
if(this!=&x){ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
size_type s=size(); | |
splice(end(),x); | |
random_access_index_inplace_merge<node_type>( | |
get_allocator(),ptrs,ptrs.at(s),comp); | |
} | |
} | |
void sort() | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
random_access_index_sort<node_type>( | |
get_allocator(),ptrs,std::less<value_type>()); | |
} | |
template <typename Compare> | |
void sort(Compare comp) | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
random_access_index_sort<node_type>( | |
get_allocator(),ptrs,comp); | |
} | |
void reverse() | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
node_impl_type::reverse(ptrs.begin(),ptrs.end()); | |
} | |
/* rearrange operations */ | |
void relocate(iterator position,iterator i) | |
{ | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i); | |
BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,*this); | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
if(position!=i)relocate(position.get_node(),i.get_node()); | |
} | |
void relocate(iterator position,iterator first,iterator last) | |
{ | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first); | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this); | |
BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last); | |
BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last); | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
if(position!=last)relocate( | |
position.get_node(),first.get_node(),last.get_node()); | |
} | |
template<typename InputIterator> | |
void rearrange(InputIterator first) | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
for(node_impl_ptr_pointer p0=ptrs.begin(),p0_end=ptrs.end(); | |
p0!=p0_end;++first,++p0){ | |
const value_type& v1=*first; | |
node_impl_ptr_pointer p1=node_from_value<node_type>(&v1)->up(); | |
std::swap(*p0,*p1); | |
(*p0)->up()=p0; | |
(*p1)->up()=p1; | |
} | |
} | |
BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: | |
random_access_index( | |
const ctor_args_list& args_list,const allocator_type& al): | |
super(args_list.get_tail(),al), | |
ptrs(al,header()->impl(),0) | |
{ | |
} | |
random_access_index(const random_access_index<SuperMeta,TagList>& x): | |
super(x), | |
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
safe_super(), | |
#endif | |
ptrs(x.get_allocator(),header()->impl(),x.size()) | |
{ | |
/* The actual copying takes place in subsequent call to copy_(). | |
*/ | |
} | |
~random_access_index() | |
{ | |
/* the container is guaranteed to be empty by now */ | |
} | |
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
iterator make_iterator(node_type* node){return iterator(node,this);} | |
const_iterator make_iterator(node_type* node)const | |
{return const_iterator(node,const_cast<random_access_index*>(this));} | |
#else | |
iterator make_iterator(node_type* node){return iterator(node);} | |
const_iterator make_iterator(node_type* node)const | |
{return const_iterator(node);} | |
#endif | |
void copy_( | |
const random_access_index<SuperMeta,TagList>& x,const copy_map_type& map) | |
{ | |
for(node_impl_ptr_pointer begin_org=x.ptrs.begin(), | |
begin_cpy=ptrs.begin(), | |
end_org=x.ptrs.end(); | |
begin_org!=end_org;++begin_org,++begin_cpy){ | |
*begin_cpy= | |
static_cast<node_type*>( | |
map.find( | |
static_cast<final_node_type*>( | |
node_type::from_impl(*begin_org))))->impl(); | |
(*begin_cpy)->up()=begin_cpy; | |
} | |
super::copy_(x,map); | |
} | |
node_type* insert_(value_param_type v,node_type* x) | |
{ | |
ptrs.room_for_one(); | |
node_type* res=static_cast<node_type*>(super::insert_(v,x)); | |
if(res==x)ptrs.push_back(x->impl()); | |
return res; | |
} | |
node_type* insert_(value_param_type v,node_type* position,node_type* x) | |
{ | |
ptrs.room_for_one(); | |
node_type* res=static_cast<node_type*>(super::insert_(v,position,x)); | |
if(res==x)ptrs.push_back(x->impl()); | |
return res; | |
} | |
void erase_(node_type* x) | |
{ | |
ptrs.erase(x->impl()); | |
super::erase_(x); | |
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
detach_iterators(x); | |
#endif | |
} | |
void delete_all_nodes_() | |
{ | |
for(node_impl_ptr_pointer x=ptrs.begin(),x_end=ptrs.end();x!=x_end;++x){ | |
this->final_delete_node_( | |
static_cast<final_node_type*>(node_type::from_impl(*x))); | |
} | |
} | |
void clear_() | |
{ | |
super::clear_(); | |
ptrs.clear(); | |
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
safe_super::detach_dereferenceable_iterators(); | |
#endif | |
} | |
void swap_(random_access_index<SuperMeta,TagList>& x) | |
{ | |
ptrs.swap(x.ptrs); | |
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
safe_super::swap(x); | |
#endif | |
super::swap_(x); | |
} | |
bool replace_(value_param_type v,node_type* x) | |
{ | |
return super::replace_(v,x); | |
} | |
bool modify_(node_type* x) | |
{ | |
BOOST_TRY{ | |
if(!super::modify_(x)){ | |
ptrs.erase(x->impl()); | |
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
detach_iterators(x); | |
#endif | |
return false; | |
} | |
else return true; | |
} | |
BOOST_CATCH(...){ | |
ptrs.erase(x->impl()); | |
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
detach_iterators(x); | |
#endif | |
BOOST_RETHROW; | |
} | |
BOOST_CATCH_END | |
} | |
bool modify_rollback_(node_type* x) | |
{ | |
return super::modify_rollback_(x); | |
} | |
#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) | |
/* serialization */ | |
template<typename Archive> | |
void save_( | |
Archive& ar,const unsigned int version,const index_saver_type& sm)const | |
{ | |
sm.save(begin(),end(),ar,version); | |
super::save_(ar,version,sm); | |
} | |
template<typename Archive> | |
void load_( | |
Archive& ar,const unsigned int version,const index_loader_type& lm) | |
{ | |
{ | |
typedef random_access_index_loader<node_type,allocator_type> loader; | |
loader ld(get_allocator(),ptrs); | |
lm.load(::boost::bind(&loader::rearrange,&ld,_1,_2),ar,version); | |
} /* exit scope so that ld frees its resources */ | |
super::load_(ar,version,lm); | |
} | |
#endif | |
#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) | |
/* invariant stuff */ | |
bool invariant_()const | |
{ | |
if(size()>capacity())return false; | |
if(size()==0||begin()==end()){ | |
if(size()!=0||begin()!=end())return false; | |
} | |
else{ | |
size_type s=0; | |
for(const_iterator it=begin(),it_end=end();;++it,++s){ | |
if(*(it.get_node()->up())!=it.get_node()->impl())return false; | |
if(it==it_end)break; | |
} | |
if(s!=size())return false; | |
} | |
return super::invariant_(); | |
} | |
/* This forwarding function eases things for the boost::mem_fn construct | |
* in BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT. Actually, | |
* final_check_invariant is already an inherited member function of index. | |
*/ | |
void check_invariant_()const{this->final_check_invariant_();} | |
#endif | |
private: | |
node_type* header()const{return this->final_header();} | |
static void relocate(node_type* position,node_type* x) | |
{ | |
node_impl_type::relocate(position->up(),x->up()); | |
} | |
static void relocate(node_type* position,node_type* first,node_type* last) | |
{ | |
node_impl_type::relocate( | |
position->up(),first->up(),last->up()); | |
} | |
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) | |
void detach_iterators(node_type* x) | |
{ | |
iterator it=make_iterator(x); | |
safe_mode::detach_equivalent_iterators(it); | |
} | |
#endif | |
template <class InputIterator> | |
void assign_iter(InputIterator first,InputIterator last,mpl::true_) | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
clear(); | |
for(;first!=last;++first)push_back(*first); | |
} | |
void assign_iter(size_type n,value_param_type value,mpl::false_) | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
clear(); | |
for(size_type i=0;i<n;++i)push_back(value); | |
} | |
template<typename InputIterator> | |
void insert_iter( | |
iterator position,InputIterator first,InputIterator last,mpl::true_) | |
{ | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
size_type s=0; | |
BOOST_TRY{ | |
for(;first!=last;++first){ | |
if(push_back(*first).second)++s; | |
} | |
} | |
BOOST_CATCH(...){ | |
relocate(position,end()-s,end()); | |
BOOST_RETHROW; | |
} | |
BOOST_CATCH_END | |
relocate(position,end()-s,end()); | |
} | |
void insert_iter( | |
iterator position,size_type n,value_param_type x,mpl::false_) | |
{ | |
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); | |
BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); | |
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT; | |
size_type s=0; | |
BOOST_TRY{ | |
while(n--){ | |
if(push_back(x).second)++s; | |
} | |
} | |
BOOST_CATCH(...){ | |
relocate(position,end()-s,end()); | |
BOOST_RETHROW; | |
} | |
BOOST_CATCH_END | |
relocate(position,end()-s,end()); | |
} | |
ptr_array ptrs; | |
#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ | |
BOOST_WORKAROUND(__MWERKS__,<=0x3003) | |
#pragma parse_mfunc_templ reset | |
#endif | |
}; | |
/* comparison */ | |
template< | |
typename SuperMeta1,typename TagList1, | |
typename SuperMeta2,typename TagList2 | |
> | |
bool operator==( | |
const random_access_index<SuperMeta1,TagList1>& x, | |
const random_access_index<SuperMeta2,TagList2>& y) | |
{ | |
return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin()); | |
} | |
template< | |
typename SuperMeta1,typename TagList1, | |
typename SuperMeta2,typename TagList2 | |
> | |
bool operator<( | |
const random_access_index<SuperMeta1,TagList1>& x, | |
const random_access_index<SuperMeta2,TagList2>& y) | |
{ | |
return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end()); | |
} | |
template< | |
typename SuperMeta1,typename TagList1, | |
typename SuperMeta2,typename TagList2 | |
> | |
bool operator!=( | |
const random_access_index<SuperMeta1,TagList1>& x, | |
const random_access_index<SuperMeta2,TagList2>& y) | |
{ | |
return !(x==y); | |
} | |
template< | |
typename SuperMeta1,typename TagList1, | |
typename SuperMeta2,typename TagList2 | |
> | |
bool operator>( | |
const random_access_index<SuperMeta1,TagList1>& x, | |
const random_access_index<SuperMeta2,TagList2>& y) | |
{ | |
return y<x; | |
} | |
template< | |
typename SuperMeta1,typename TagList1, | |
typename SuperMeta2,typename TagList2 | |
> | |
bool operator>=( | |
const random_access_index<SuperMeta1,TagList1>& x, | |
const random_access_index<SuperMeta2,TagList2>& y) | |
{ | |
return !(x<y); | |
} | |
template< | |
typename SuperMeta1,typename TagList1, | |
typename SuperMeta2,typename TagList2 | |
> | |
bool operator<=( | |
const random_access_index<SuperMeta1,TagList1>& x, | |
const random_access_index<SuperMeta2,TagList2>& y) | |
{ | |
return !(x>y); | |
} | |
/* specialized algorithms */ | |
template<typename SuperMeta,typename TagList> | |
void swap( | |
random_access_index<SuperMeta,TagList>& x, | |
random_access_index<SuperMeta,TagList>& y) | |
{ | |
x.swap(y); | |
} | |
} /* namespace multi_index::detail */ | |
/* random access index specifier */ | |
template <typename TagList> | |
struct random_access | |
{ | |
BOOST_STATIC_ASSERT(detail::is_tag<TagList>::value); | |
template<typename Super> | |
struct node_class | |
{ | |
typedef detail::random_access_index_node<Super> type; | |
}; | |
template<typename SuperMeta> | |
struct index_class | |
{ | |
typedef detail::random_access_index< | |
SuperMeta,typename TagList::type> type; | |
}; | |
}; | |
} /* namespace multi_index */ | |
} /* namespace boost */ | |
#undef BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT | |
#endif |