// | |
// Boost.Pointer Container | |
// | |
// Copyright Thorsten Ottosen 2003-2005. Use, modification and | |
// distribution is subject to 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) | |
// | |
// For more information, see http://www.boost.org/libs/ptr_container/ | |
// | |
#ifndef BOOST_PTR_CONTAINER_PTR_SEQUENCE_ADAPTER_HPP | |
#define BOOST_PTR_CONTAINER_PTR_SEQUENCE_ADAPTER_HPP | |
#if defined(_MSC_VER) && (_MSC_VER >= 1200) | |
# pragma once | |
#endif | |
#include <boost/ptr_container/detail/reversible_ptr_container.hpp> | |
#include <boost/ptr_container/indirect_fun.hpp> | |
#include <boost/ptr_container/detail/void_ptr_iterator.hpp> | |
#include <boost/type_traits/remove_pointer.hpp> | |
#include <boost/type_traits/is_same.hpp> | |
namespace boost | |
{ | |
namespace ptr_container_detail | |
{ | |
template | |
< | |
class T, | |
class VoidPtrSeq | |
> | |
struct sequence_config | |
{ | |
typedef BOOST_DEDUCED_TYPENAME remove_nullable<T>::type | |
U; | |
typedef VoidPtrSeq | |
void_container_type; | |
typedef BOOST_DEDUCED_TYPENAME VoidPtrSeq::allocator_type | |
allocator_type; | |
typedef U value_type; | |
typedef void_ptr_iterator< | |
BOOST_DEDUCED_TYPENAME VoidPtrSeq::iterator, U > | |
iterator; | |
typedef void_ptr_iterator< | |
BOOST_DEDUCED_TYPENAME VoidPtrSeq::const_iterator, const U > | |
const_iterator; | |
#if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) | |
template< class Iter > | |
static U* get_pointer( Iter i ) | |
{ | |
return static_cast<U*>( *i.base() ); | |
} | |
#else | |
template< class Iter > | |
static U* get_pointer( void_ptr_iterator<Iter,U> i ) | |
{ | |
return static_cast<U*>( *i.base() ); | |
} | |
template< class Iter > | |
static U* get_pointer( Iter i ) | |
{ | |
return &*i; | |
} | |
#endif | |
#if defined(BOOST_NO_SFINAE) && !BOOST_WORKAROUND(__MWERKS__, <= 0x3003) | |
template< class Iter > | |
static const U* get_const_pointer( Iter i ) | |
{ | |
return static_cast<const U*>( *i.base() ); | |
} | |
#else // BOOST_NO_SFINAE | |
#if BOOST_WORKAROUND(__MWERKS__, <= 0x3003) | |
template< class Iter > | |
static const U* get_const_pointer( void_ptr_iterator<Iter,U> i ) | |
{ | |
return static_cast<const U*>( *i.base() ); | |
} | |
#else // BOOST_WORKAROUND | |
template< class Iter > | |
static const U* get_const_pointer( void_ptr_iterator<Iter,const U> i ) | |
{ | |
return static_cast<const U*>( *i.base() ); | |
} | |
#endif // BOOST_WORKAROUND | |
template< class Iter > | |
static const U* get_const_pointer( Iter i ) | |
{ | |
return &*i; | |
} | |
#endif // BOOST_NO_SFINAE | |
BOOST_STATIC_CONSTANT(bool, allow_null = boost::is_nullable<T>::value ); | |
}; | |
} // ptr_container_detail | |
template< class Iterator, class T > | |
inline bool is_null( void_ptr_iterator<Iterator,T> i ) | |
{ | |
return *i.base() == 0; | |
} | |
template | |
< | |
class T, | |
class VoidPtrSeq, | |
class CloneAllocator = heap_clone_allocator | |
> | |
class ptr_sequence_adapter : public | |
ptr_container_detail::reversible_ptr_container< ptr_container_detail::sequence_config<T,VoidPtrSeq>, | |
CloneAllocator > | |
{ | |
typedef ptr_container_detail::reversible_ptr_container< ptr_container_detail::sequence_config<T,VoidPtrSeq>, | |
CloneAllocator > | |
base_type; | |
typedef ptr_sequence_adapter<T,VoidPtrSeq,CloneAllocator> | |
this_type; | |
protected: | |
typedef BOOST_DEDUCED_TYPENAME base_type::scoped_deleter scoped_deleter; | |
public: | |
typedef BOOST_DEDUCED_TYPENAME base_type::value_type value_type; | |
typedef BOOST_DEDUCED_TYPENAME base_type::reference reference; | |
typedef BOOST_DEDUCED_TYPENAME base_type::const_reference | |
const_reference; | |
typedef BOOST_DEDUCED_TYPENAME base_type::auto_type auto_type; | |
typedef BOOST_DEDUCED_TYPENAME base_type::clone_allocator_type | |
clone_allocator_type; | |
typedef BOOST_DEDUCED_TYPENAME base_type::iterator iterator; | |
typedef BOOST_DEDUCED_TYPENAME base_type::size_type size_type; | |
typedef BOOST_DEDUCED_TYPENAME base_type::allocator_type | |
allocator_type; | |
ptr_sequence_adapter() | |
{ } | |
template< class Allocator > | |
explicit ptr_sequence_adapter( const Allocator& a ) | |
: base_type( a ) | |
{ } | |
template< class SizeType > | |
ptr_sequence_adapter( SizeType n, | |
ptr_container_detail::fixed_length_sequence_tag tag ) | |
: base_type( n, tag ) | |
{ } | |
template< class SizeType, class Allocator > | |
ptr_sequence_adapter( SizeType n, const Allocator& a, | |
ptr_container_detail::fixed_length_sequence_tag tag ) | |
: base_type( n, a, tag ) | |
{ } | |
template< class InputIterator > | |
ptr_sequence_adapter( InputIterator first, InputIterator last ) | |
: base_type( first, last ) | |
{ } | |
template< class InputIterator, class Allocator > | |
ptr_sequence_adapter( InputIterator first, InputIterator last, | |
const Allocator& a ) | |
: base_type( first, last, a ) | |
{ } | |
template< class ForwardIterator > | |
ptr_sequence_adapter( ForwardIterator first, | |
ForwardIterator last, | |
ptr_container_detail::fixed_length_sequence_tag tag ) | |
: base_type( first, last, tag ) | |
{ } | |
template< class SizeType, class ForwardIterator > | |
ptr_sequence_adapter( SizeType n, | |
ForwardIterator first, | |
ForwardIterator last, | |
ptr_container_detail::fixed_length_sequence_tag tag ) | |
: base_type( n, first, last, tag ) | |
{ } | |
ptr_sequence_adapter( const ptr_sequence_adapter& r ) | |
: base_type( r ) | |
{ } | |
template< class U > | |
ptr_sequence_adapter( const ptr_sequence_adapter<U,VoidPtrSeq,CloneAllocator>& r ) | |
: base_type( r ) | |
{ } | |
ptr_sequence_adapter( const ptr_sequence_adapter& r, | |
ptr_container_detail::fixed_length_sequence_tag tag ) | |
: base_type( r, tag ) | |
{ } | |
template< class U > | |
ptr_sequence_adapter( const ptr_sequence_adapter<U,VoidPtrSeq,CloneAllocator>& r, | |
ptr_container_detail::fixed_length_sequence_tag tag ) | |
: base_type( r, tag ) | |
{ } | |
template< class PtrContainer > | |
explicit ptr_sequence_adapter( std::auto_ptr<PtrContainer> clone ) | |
: base_type( clone ) | |
{ } | |
ptr_sequence_adapter& operator=( const ptr_sequence_adapter r ) | |
{ | |
this->swap( r ); | |
return *this; | |
} | |
template< class PtrContainer > | |
ptr_sequence_adapter& operator=( std::auto_ptr<PtrContainer> clone ) | |
{ | |
base_type::operator=( clone ); | |
return *this; | |
} | |
///////////////////////////////////////////////////////////// | |
// modifiers | |
///////////////////////////////////////////////////////////// | |
void push_back( value_type x ) // strong | |
{ | |
this->enforce_null_policy( x, "Null pointer in 'push_back()'" ); | |
auto_type ptr( x ); // notrow | |
this->base().push_back( x ); // strong, commit | |
ptr.release(); // nothrow | |
} | |
template< class U > | |
void push_back( std::auto_ptr<U> x ) | |
{ | |
push_back( x.release() ); | |
} | |
void push_front( value_type x ) | |
{ | |
this->enforce_null_policy( x, "Null pointer in 'push_front()'" ); | |
auto_type ptr( x ); // nothrow | |
this->base().push_front( x ); // strong, commit | |
ptr.release(); // nothrow | |
} | |
template< class U > | |
void push_front( std::auto_ptr<U> x ) | |
{ | |
push_front( x.release() ); | |
} | |
auto_type pop_back() | |
{ | |
BOOST_ASSERT( !this->empty() && | |
"'pop_back()' on empty container" ); | |
auto_type ptr( static_cast<value_type>( this->base().back() ) ); | |
// nothrow | |
this->base().pop_back(); // nothrow | |
return ptr_container_detail::move( ptr ); // nothrow | |
} | |
auto_type pop_front() | |
{ | |
BOOST_ASSERT( !this->empty() && | |
"'pop_front()' on empty container" ); | |
auto_type ptr( static_cast<value_type>( this->base().front() ) ); | |
// nothrow | |
this->base().pop_front(); // nothrow | |
return ptr_container_detail::move( ptr ); | |
} | |
reference front() | |
{ | |
BOOST_ASSERT( !this->empty() && | |
"accessing 'front()' on empty container" ); | |
BOOST_ASSERT( !::boost::is_null( this->begin() ) ); | |
return *this->begin(); | |
} | |
const_reference front() const | |
{ | |
return const_cast<ptr_sequence_adapter*>(this)->front(); | |
} | |
reference back() | |
{ | |
BOOST_ASSERT( !this->empty() && | |
"accessing 'back()' on empty container" ); | |
BOOST_ASSERT( !::boost::is_null( --this->end() ) ); | |
return *--this->end(); | |
} | |
const_reference back() const | |
{ | |
return const_cast<ptr_sequence_adapter*>(this)->back(); | |
} | |
public: // deque/vector inerface | |
reference operator[]( size_type n ) // nothrow | |
{ | |
BOOST_ASSERT( n < this->size() ); | |
BOOST_ASSERT( !this->is_null( n ) ); | |
return *static_cast<value_type>( this->base()[n] ); | |
} | |
const_reference operator[]( size_type n ) const // nothrow | |
{ | |
BOOST_ASSERT( n < this->size() ); | |
BOOST_ASSERT( !this->is_null( n ) ); | |
return *static_cast<value_type>( this->base()[n] ); | |
} | |
reference at( size_type n ) | |
{ | |
BOOST_PTR_CONTAINER_THROW_EXCEPTION( n >= this->size(), bad_index, | |
"'at()' out of bounds" ); | |
BOOST_ASSERT( !this->is_null( n ) ); | |
return (*this)[n]; | |
} | |
const_reference at( size_type n ) const | |
{ | |
BOOST_PTR_CONTAINER_THROW_EXCEPTION( n >= this->size(), bad_index, | |
"'at()' out of bounds" ); | |
BOOST_ASSERT( !this->is_null( n ) ); | |
return (*this)[n]; | |
} | |
public: // vector interface | |
size_type capacity() const | |
{ | |
return this->base().capacity(); | |
} | |
void reserve( size_type n ) | |
{ | |
this->base().reserve( n ); | |
} | |
void reverse() | |
{ | |
this->base().reverse(); | |
} | |
public: // assign, insert, transfer | |
// overhead: 1 heap allocation (very cheap compared to cloning) | |
template< class InputIterator > | |
void assign( InputIterator first, InputIterator last ) // strong | |
{ | |
base_type temp( first, last ); | |
this->swap( temp ); | |
} | |
template< class Range > | |
void assign( const Range& r ) // strong | |
{ | |
assign( boost::begin(r), boost::end(r ) ); | |
} | |
private: | |
template< class I > | |
void insert_impl( iterator before, I first, I last, std::input_iterator_tag ) // strong | |
{ | |
ptr_sequence_adapter temp(first,last); // strong | |
transfer( before, temp ); // strong, commit | |
} | |
template< class I > | |
void insert_impl( iterator before, I first, I last, std::forward_iterator_tag ) // strong | |
{ | |
if( first == last ) | |
return; | |
scoped_deleter sd( first, last ); // strong | |
this->insert_clones_and_release( sd, before ); // strong, commit | |
} | |
public: | |
using base_type::insert; | |
template< class InputIterator > | |
void insert( iterator before, InputIterator first, InputIterator last ) // strong | |
{ | |
insert_impl( before, first, last, BOOST_DEDUCED_TYPENAME | |
iterator_category<InputIterator>::type() ); | |
} | |
#if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) | |
#else | |
template< class Range > | |
BOOST_DEDUCED_TYPENAME | |
boost::disable_if< ptr_container_detail::is_pointer_or_integral<Range> >::type | |
insert( iterator before, const Range& r ) | |
{ | |
insert( before, boost::begin(r), boost::end(r) ); | |
} | |
#endif | |
template< class PtrSeqAdapter > | |
void transfer( iterator before, | |
BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator first, | |
BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator last, | |
PtrSeqAdapter& from ) // strong | |
{ | |
BOOST_ASSERT( (void*)&from != (void*)this ); | |
if( from.empty() ) | |
return; | |
this->base(). | |
insert( before.base(), first.base(), last.base() ); // strong | |
from.base().erase( first.base(), last.base() ); // nothrow | |
} | |
template< class PtrSeqAdapter > | |
void transfer( iterator before, | |
BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator object, | |
PtrSeqAdapter& from ) // strong | |
{ | |
BOOST_ASSERT( (void*)&from != (void*)this ); | |
if( from.empty() ) | |
return; | |
this->base().insert( before.base(), *object.base() ); // strong | |
from.base().erase( object.base() ); // nothrow | |
} | |
#if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) | |
#else | |
template< class PtrSeqAdapter, class Range > | |
BOOST_DEDUCED_TYPENAME boost::disable_if< boost::is_same< Range, | |
BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator > >::type | |
transfer( iterator before, const Range& r, PtrSeqAdapter& from ) // strong | |
{ | |
transfer( before, boost::begin(r), boost::end(r), from ); | |
} | |
#endif | |
template< class PtrSeqAdapter > | |
void transfer( iterator before, PtrSeqAdapter& from ) // strong | |
{ | |
BOOST_ASSERT( (void*)&from != (void*)this ); | |
if( from.empty() ) | |
return; | |
this->base(). | |
insert( before.base(), | |
from.begin().base(), from.end().base() ); // strong | |
from.base().clear(); // nothrow | |
} | |
public: // C-array support | |
void transfer( iterator before, value_type* from, | |
size_type size, bool delete_from = true ) // strong | |
{ | |
BOOST_ASSERT( from != 0 ); | |
if( delete_from ) | |
{ | |
BOOST_DEDUCED_TYPENAME base_type::scoped_deleter | |
deleter( from, size ); // nothrow | |
this->base().insert( before.base(), from, from + size ); // strong | |
deleter.release(); // nothrow | |
} | |
else | |
{ | |
this->base().insert( before.base(), from, from + size ); // strong | |
} | |
} | |
value_type* c_array() // nothrow | |
{ | |
if( this->empty() ) | |
return 0; | |
T** res = reinterpret_cast<T**>( &this->begin().base()[0] ); | |
return res; | |
} | |
public: // null functions | |
bool is_null( size_type idx ) const | |
{ | |
BOOST_ASSERT( idx < this->size() ); | |
return this->base()[idx] == 0; | |
} | |
public: // resize | |
void resize( size_type size ) // basic | |
{ | |
size_type old_size = this->size(); | |
if( old_size > size ) | |
{ | |
this->erase( boost::next( this->begin(), size ), this->end() ); | |
} | |
else if( size > old_size ) | |
{ | |
for( ; old_size != size; ++old_size ) | |
this->push_back( new BOOST_DEDUCED_TYPENAME | |
boost::remove_pointer<value_type>::type() ); | |
} | |
BOOST_ASSERT( this->size() == size ); | |
} | |
void resize( size_type size, value_type to_clone ) // basic | |
{ | |
size_type old_size = this->size(); | |
if( old_size > size ) | |
{ | |
this->erase( boost::next( this->begin(), size ), this->end() ); | |
} | |
else if( size > old_size ) | |
{ | |
for( ; old_size != size; ++old_size ) | |
this->push_back( this->null_policy_allocate_clone( to_clone ) ); | |
} | |
BOOST_ASSERT( this->size() == size ); | |
} | |
void rresize( size_type size ) // basic | |
{ | |
size_type old_size = this->size(); | |
if( old_size > size ) | |
{ | |
this->erase( this->begin(), | |
boost::next( this->begin(), old_size - size ) ); | |
} | |
else if( size > old_size ) | |
{ | |
for( ; old_size != size; ++old_size ) | |
this->push_front( new BOOST_DEDUCED_TYPENAME | |
boost::remove_pointer<value_type>::type() ); | |
} | |
BOOST_ASSERT( this->size() == size ); | |
} | |
void rresize( size_type size, value_type to_clone ) // basic | |
{ | |
size_type old_size = this->size(); | |
if( old_size > size ) | |
{ | |
this->erase( this->begin(), | |
boost::next( this->begin(), old_size - size ) ); | |
} | |
else if( size > old_size ) | |
{ | |
for( ; old_size != size; ++old_size ) | |
this->push_front( this->null_policy_allocate_clone( to_clone ) ); | |
} | |
BOOST_ASSERT( this->size() == size ); | |
} | |
public: // algorithms | |
void sort( iterator first, iterator last ) | |
{ | |
sort( first, last, std::less<T>() ); | |
} | |
void sort() | |
{ | |
sort( this->begin(), this->end() ); | |
} | |
template< class Compare > | |
void sort( iterator first, iterator last, Compare comp ) | |
{ | |
BOOST_ASSERT( first <= last && "out of range sort()" ); | |
BOOST_ASSERT( this->begin() <= first && "out of range sort()" ); | |
BOOST_ASSERT( last <= this->end() && "out of range sort()" ); | |
// some static assert on the arguments of the comparison | |
std::sort( first.base(), last.base(), | |
void_ptr_indirect_fun<Compare,T>(comp) ); | |
} | |
template< class Compare > | |
void sort( Compare comp ) | |
{ | |
sort( this->begin(), this->end(), comp ); | |
} | |
void unique( iterator first, iterator last ) | |
{ | |
unique( first, last, std::equal_to<T>() ); | |
} | |
void unique() | |
{ | |
unique( this->begin(), this->end() ); | |
} | |
private: | |
struct is_not_zero_ptr | |
{ | |
template< class U > | |
bool operator()( const U* r ) const | |
{ | |
return r != 0; | |
} | |
}; | |
protected: | |
template< class Fun, class Arg1 > | |
class void_ptr_delete_if | |
{ | |
Fun fun; | |
public: | |
void_ptr_delete_if() : fun(Fun()) | |
{ } | |
void_ptr_delete_if( Fun f ) : fun(f) | |
{ } | |
bool operator()( void* r ) const | |
{ | |
BOOST_ASSERT( r != 0 ); | |
Arg1 arg1 = static_cast<Arg1>(r); | |
if( fun( *arg1 ) ) | |
{ | |
clone_allocator_type::deallocate_clone( arg1 ); | |
return true; | |
} | |
return false; | |
} | |
}; | |
private: | |
void compact_and_erase_nulls( iterator first, iterator last ) // nothrow | |
{ | |
typename base_type::ptr_iterator p = std::stable_partition( | |
first.base(), | |
last.base(), | |
is_not_zero_ptr() ); | |
this->base().erase( p, this->end().base() ); | |
} | |
void range_check_impl( iterator first, iterator last, | |
std::bidirectional_iterator_tag ) | |
{ /* do nothing */ } | |
void range_check_impl( iterator first, iterator last, | |
std::random_access_iterator_tag ) | |
{ | |
BOOST_ASSERT( first <= last && "out of range unique()/erase_if()" ); | |
BOOST_ASSERT( this->begin() <= first && "out of range unique()/erase_if()" ); | |
BOOST_ASSERT( last <= this->end() && "out of range unique()/erase_if)(" ); | |
} | |
void range_check( iterator first, iterator last ) | |
{ | |
range_check_impl( first, last, | |
BOOST_DEDUCED_TYPENAME iterator_category<iterator>::type() ); | |
} | |
public: | |
template< class Compare > | |
void unique( iterator first, iterator last, Compare comp ) | |
{ | |
range_check(first,last); | |
iterator prev = first; | |
iterator next = first; | |
++next; | |
for( ; next != last; ++next ) | |
{ | |
BOOST_ASSERT( !::boost::is_null(prev) ); | |
BOOST_ASSERT( !::boost::is_null(next) ); | |
if( comp( *prev, *next ) ) | |
{ | |
this->remove( next ); // delete object | |
*next.base() = 0; // mark pointer as deleted | |
} | |
else | |
{ | |
prev = next; | |
} | |
// ++next | |
} | |
compact_and_erase_nulls( first, last ); | |
} | |
template< class Compare > | |
void unique( Compare comp ) | |
{ | |
unique( this->begin(), this->end(), comp ); | |
} | |
template< class Pred > | |
void erase_if( iterator first, iterator last, Pred pred ) | |
{ | |
range_check(first,last); | |
this->base().erase( std::remove_if( first.base(), last.base(), | |
void_ptr_delete_if<Pred,value_type>(pred) ), | |
last.base() ); | |
} | |
template< class Pred > | |
void erase_if( Pred pred ) | |
{ | |
erase_if( this->begin(), this->end(), pred ); | |
} | |
void merge( iterator first, iterator last, | |
ptr_sequence_adapter& from ) | |
{ | |
merge( first, last, from, std::less<T>() ); | |
} | |
template< class BinPred > | |
void merge( iterator first, iterator last, | |
ptr_sequence_adapter& from, BinPred pred ) | |
{ | |
void_ptr_indirect_fun<BinPred,T> bin_pred(pred); | |
size_type current_size = this->size(); | |
this->transfer( this->end(), first, last, from ); | |
typename base_type::ptr_iterator middle = this->begin().base(); | |
std::advance(middle,current_size); | |
std::inplace_merge( this->begin().base(), | |
middle, | |
this->end().base(), | |
bin_pred ); | |
} | |
void merge( ptr_sequence_adapter& r ) | |
{ | |
merge( r, std::less<T>() ); | |
BOOST_ASSERT( r.empty() ); | |
} | |
template< class BinPred > | |
void merge( ptr_sequence_adapter& r, BinPred pred ) | |
{ | |
merge( r.begin(), r.end(), r, pred ); | |
BOOST_ASSERT( r.empty() ); | |
} | |
}; | |
} // namespace 'boost' | |
#endif |