--- /dev/null
+/* Copyright 2003-2015 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)
+#pragma once
+#endif
+
+#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
+#include <algorithm>
+#include <boost/bind.hpp>
+#include <boost/call_traits.hpp>
+#include <boost/detail/no_exceptions_support.hpp>
+#include <boost/detail/workaround.hpp>
+#include <boost/foreach_fwd.hpp>
+#include <boost/iterator/reverse_iterator.hpp>
+#include <boost/move/core.hpp>
+#include <boost/move/utility.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/do_not_copy_elements_tag.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_mode.hpp>
+#include <boost/multi_index/detail/scope_guard.hpp>
+#include <boost/multi_index/detail/vartempl_support.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_NO_CXX11_HDR_INITIALIZER_LIST)
+#include<initializer_list>
+#endif
+
+#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
+#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_OF(x) \
+ detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \
+ detail::make_obj_guard(x,&random_access_index::check_invariant_); \
+ BOOST_JOIN(check_invariant_,__LINE__).touch();
+#define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT \
+ BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT_OF(*this)
+#else
+#define BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT_OF(x)
+#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)
+ ,public safe_mode::safe_container<
+ random_access_index<SuperMeta,TagList> >
+#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)
+ typedef safe_mode::safe_iterator<
+ rnd_node_iterator<node_type>,
+ random_access_index> iterator;
+#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)
+ typedef safe_mode::safe_container<
+ random_access_index> safe_super;
+#endif
+
+ typedef typename call_traits<
+ value_type>::param_type value_param_type;
+
+ /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL
+ * expansion.
+ */
+
+ typedef std::pair<iterator,bool> emplace_return_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;
+ }
+
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+ random_access_index<SuperMeta,TagList>& operator=(
+ std::initializer_list<value_type> list)
+ {
+ this->final()=list;
+ return *this;
+ }
+#endif
+
+ template <class InputIterator>
+ void assign(InputIterator first,InputIterator last)
+ {
+ assign_iter(first,last,mpl::not_<is_integral<InputIterator> >());
+ }
+
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+ void assign(std::initializer_list<value_type> list)
+ {
+ assign(list.begin(),list.end());
+ }
+#endif
+
+ 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 BOOST_NOEXCEPT
+ {
+ return this->final().get_allocator();
+ }
+
+ /* iterators */
+
+ iterator begin()BOOST_NOEXCEPT
+ {return make_iterator(node_type::from_impl(*ptrs.begin()));}
+ const_iterator begin()const BOOST_NOEXCEPT
+ {return make_iterator(node_type::from_impl(*ptrs.begin()));}
+ iterator
+ end()BOOST_NOEXCEPT{return make_iterator(header());}
+ const_iterator
+ end()const BOOST_NOEXCEPT{return make_iterator(header());}
+ reverse_iterator
+ rbegin()BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
+ const_reverse_iterator
+ rbegin()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
+ reverse_iterator
+ rend()BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
+ const_reverse_iterator
+ rend()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
+ const_iterator
+ cbegin()const BOOST_NOEXCEPT{return begin();}
+ const_iterator
+ cend()const BOOST_NOEXCEPT{return end();}
+ const_reverse_iterator
+ crbegin()const BOOST_NOEXCEPT{return rbegin();}
+ const_reverse_iterator
+ crend()const BOOST_NOEXCEPT{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 BOOST_NOEXCEPT{return this->final_empty_();}
+ size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
+ size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
+ size_type capacity()const BOOST_NOEXCEPT{return ptrs.capacity();}
+
+ void reserve(size_type n)
+ {
+ BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
+ ptrs.reserve(n);
+ }
+
+ void shrink_to_fit()
+ {
+ BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
+ ptrs.shrink_to_fit();
+ }
+
+ void resize(size_type n)
+ {
+ BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
+ if(n>size())
+ for(size_type m=n-size();m--;)
+ this->final_emplace_(BOOST_MULTI_INDEX_NULL_PARAM_PACK);
+ else if(n<size())erase(begin()+n,end());
+ }
+
+ void resize(size_type n,value_param_type x)
+ {
+ BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
+ if(n>size())for(size_type m=n-size();m--;)this->final_insert_(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 */
+
+ BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
+ emplace_return_type,emplace_front,emplace_front_impl)
+
+ std::pair<iterator,bool> push_front(const value_type& x)
+ {return insert(begin(),x);}
+ std::pair<iterator,bool> push_front(BOOST_RV_REF(value_type) x)
+ {return insert(begin(),boost::move(x));}
+ void pop_front(){erase(begin());}
+
+ BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
+ emplace_return_type,emplace_back,emplace_back_impl)
+
+ std::pair<iterator,bool> push_back(const value_type& x)
+ {return insert(end(),x);}
+ std::pair<iterator,bool> push_back(BOOST_RV_REF(value_type) x)
+ {return insert(end(),boost::move(x));}
+ void pop_back(){erase(--end());}
+
+ BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
+ emplace_return_type,emplace,emplace_impl,iterator,position)
+
+ std::pair<iterator,bool> insert(iterator position,const value_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);
+ }
+
+ std::pair<iterator,bool> insert(iterator position,BOOST_RV_REF(value_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_rv_(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> >());
+ }
+
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+ void insert(iterator position,std::initializer_list<value_type> list)
+ {
+ insert(position,list.begin(),list.end());
+ }
+#endif
+
+ 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,const value_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()));
+ }
+
+ bool replace(iterator position,BOOST_RV_REF(value_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_rv_(
+ 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;
+ BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT_OF(x);
+ this->final_swap_(x.final());
+ }
+
+ void clear()BOOST_NOEXCEPT
+ {
+ 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,
+ ::boost::bind(std::equal_to<value_type>(),::boost::arg<1>(),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_NOEXCEPT
+ {
+ 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(
+ const random_access_index<SuperMeta,TagList>& x,do_not_copy_elements_tag):
+ super(x,do_not_copy_elements_tag()),
+
+#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
+ safe_super(),
+#endif
+
+ ptrs(x.get_allocator(),header()->impl(),0)
+ {
+ }
+
+ ~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);
+ }
+
+ template<typename Variant>
+ final_node_type* insert_(
+ value_param_type v,final_node_type*& x,Variant variant)
+ {
+ ptrs.room_for_one();
+ final_node_type* res=super::insert_(v,x,variant);
+ if(res==x)ptrs.push_back(static_cast<node_type*>(x)->impl());
+ return res;
+ }
+
+ template<typename Variant>
+ final_node_type* insert_(
+ value_param_type v,node_type* position,final_node_type*& x,Variant variant)
+ {
+ ptrs.room_for_one();
+ final_node_type* res=super::insert_(v,position,x,variant);
+ if(res==x)ptrs.push_back(static_cast<node_type*>(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);
+ }
+
+ void swap_elements_(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_elements_(x);
+ }
+
+ template<typename Variant>
+ bool replace_(value_param_type v,node_type* x,Variant variant)
+ {
+ return super::replace_(v,x,variant);
+ }
+
+ 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,::boost::arg<1>(),::boost::arg<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)this->final_insert_ref_(*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(this->final_insert_ref_(*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());
+ }
+
+ template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
+ std::pair<iterator,bool> emplace_front_impl(
+ BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
+ {
+ return emplace_impl(begin(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
+ }
+
+ template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
+ std::pair<iterator,bool> emplace_back_impl(
+ BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
+ {
+ return emplace_impl(end(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
+ }
+
+ template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
+ std::pair<iterator,bool> emplace_impl(
+ iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
+ {
+ 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_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
+ if(p.second&&position.get_node()!=header()){
+ relocate(position.get_node(),p.first);
+ }
+ return std::pair<iterator,bool>(make_iterator(p.first),p.second);
+ }
+
+ 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 */
+
+/* Boost.Foreach compatibility */
+
+template<typename SuperMeta,typename TagList>
+inline boost::mpl::true_* boost_foreach_is_noncopyable(
+ boost::multi_index::detail::random_access_index<SuperMeta,TagList>*&,
+ boost_foreach_argument_dependent_lookup_hack)
+{
+ return 0;
+}
+
+#undef BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT
+#undef BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT_OF
+
+#endif
projects / ceph.git / blobdiff