williamr@2: // williamr@2: // Boost.Pointer Container williamr@2: // williamr@2: // Copyright Thorsten Ottosen 2003-2005. Use, modification and williamr@2: // distribution is subject to the Boost Software License, Version williamr@2: // 1.0. (See accompanying file LICENSE_1_0.txt or copy at williamr@2: // http://www.boost.org/LICENSE_1_0.txt) williamr@2: // williamr@2: // For more information, see http://www.boost.org/libs/ptr_container/ williamr@2: // williamr@2: /* williamr@2: * © Portions copyright (c) 2006-2007 Nokia Corporation. All rights reserved. williamr@2: */ williamr@2: #ifndef BOOST_ptr_container_PTR_SEQUENCE_ADAPTER_HPP williamr@2: #define BOOST_ptr_container_PTR_SEQUENCE_ADAPTER_HPP williamr@2: williamr@2: #if defined(_MSC_VER) && (_MSC_VER >= 1200) williamr@2: # pragma once williamr@2: #endif williamr@2: williamr@2: williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #ifdef __SYMBIAN32__ williamr@2: #include williamr@2: #include williamr@2: #endif williamr@2: williamr@2: namespace boost williamr@2: { williamr@2: namespace ptr_container_detail williamr@2: { williamr@2: williamr@2: williamr@2: williamr@2: williamr@2: template williamr@2: < williamr@2: class T, williamr@2: class VoidPtrSeq williamr@2: > williamr@2: struct sequence_config williamr@2: { williamr@2: typedef BOOST_DEDUCED_TYPENAME remove_nullable::type williamr@2: U; williamr@2: typedef VoidPtrSeq williamr@2: void_container_type; williamr@2: williamr@2: typedef BOOST_DEDUCED_TYPENAME VoidPtrSeq::allocator_type williamr@2: allocator_type; williamr@2: williamr@2: typedef U value_type; williamr@2: williamr@2: typedef void_ptr_iterator< williamr@2: BOOST_DEDUCED_TYPENAME VoidPtrSeq::iterator, U > williamr@2: iterator; williamr@2: williamr@2: typedef void_ptr_iterator< williamr@2: BOOST_DEDUCED_TYPENAME VoidPtrSeq::const_iterator, const U > williamr@2: const_iterator; williamr@2: williamr@2: #ifdef BOOST_NO_SFINAE williamr@2: williamr@2: template< class Iter > williamr@2: static U* get_pointer( Iter i ) williamr@2: { williamr@2: return static_cast( *i.base() ); williamr@2: } williamr@2: williamr@2: #else williamr@2: template< class Iter > williamr@2: static U* get_pointer( void_ptr_iterator i ) williamr@2: { williamr@2: return static_cast( *i.base() ); williamr@2: } williamr@2: williamr@2: template< class Iter > williamr@2: static U* get_pointer( Iter i ) williamr@2: { williamr@2: return &*i; williamr@2: } williamr@2: #endif williamr@2: williamr@2: #if defined(BOOST_NO_SFINAE) && !BOOST_WORKAROUND(__MWERKS__, <= 0x3003) williamr@2: williamr@2: template< class Iter > williamr@2: static const U* get_const_pointer( Iter i ) williamr@2: { williamr@2: return static_cast( *i.base() ); williamr@2: } williamr@2: williamr@2: #else // BOOST_NO_SFINAE williamr@2: williamr@2: #if BOOST_WORKAROUND(__MWERKS__, <= 0x3003) williamr@2: template< class Iter > williamr@2: static const U* get_const_pointer( void_ptr_iterator i ) williamr@2: { williamr@2: return static_cast( *i.base() ); williamr@2: } williamr@2: #else // BOOST_WORKAROUND williamr@2: template< class Iter > williamr@2: static const U* get_const_pointer( void_ptr_iterator i ) williamr@2: { williamr@2: return static_cast( *i.base() ); williamr@2: } williamr@2: #endif // BOOST_WORKAROUND williamr@2: williamr@2: template< class Iter > williamr@2: static const U* get_const_pointer( Iter i ) williamr@2: { williamr@2: return &*i; williamr@2: } williamr@2: #endif // BOOST_NO_SFINAE williamr@2: williamr@2: BOOST_STATIC_CONSTANT(bool, allow_null = boost::is_nullable::value ); williamr@2: }; williamr@2: williamr@2: } // ptr_container_detail williamr@2: williamr@2: williamr@2: template< class Iterator, class T > williamr@2: inline bool is_null( void_ptr_iterator i ) williamr@2: { williamr@2: return *i.base() == 0; williamr@2: } williamr@2: williamr@2: williamr@2: williamr@2: template williamr@2: < williamr@2: class T, williamr@2: class VoidPtrSeq, williamr@2: class CloneAllocator = heap_clone_allocator williamr@2: > williamr@2: class ptr_sequence_adapter : public williamr@2: ptr_container_detail::reversible_ptr_container< ptr_container_detail::sequence_config, williamr@2: CloneAllocator > williamr@2: { williamr@2: typedef ptr_container_detail::reversible_ptr_container< ptr_container_detail::sequence_config, williamr@2: CloneAllocator > williamr@2: base_type; williamr@2: williamr@2: typedef BOOST_DEDUCED_TYPENAME base_type::scoped_deleter scoped_deleter; williamr@2: williamr@2: typedef ptr_sequence_adapter williamr@2: this_type; williamr@2: williamr@2: public: williamr@2: typedef BOOST_DEDUCED_TYPENAME base_type::value_type value_type; williamr@2: typedef BOOST_DEDUCED_TYPENAME base_type::reference reference; williamr@2: typedef BOOST_DEDUCED_TYPENAME base_type::auto_type auto_type; williamr@2: williamr@2: BOOST_PTR_CONTAINER_DEFINE_CONSTRUCTORS( ptr_sequence_adapter, williamr@2: base_type ) williamr@2: williamr@2: template< class PtrContainer > williamr@2: ptr_sequence_adapter( std::auto_ptr clone ) williamr@2: : base_type( clone ) williamr@2: { } williamr@2: williamr@2: template< class PtrContainer > williamr@2: void operator=( std::auto_ptr clone ) williamr@2: { williamr@2: base_type::operator=( clone ); williamr@2: } williamr@2: williamr@2: ///////////////////////////////////////////////////////////// williamr@2: // modifiers williamr@2: ///////////////////////////////////////////////////////////// williamr@2: williamr@2: void push_back( value_type x ) // strong williamr@2: { williamr@2: this->enforce_null_policy( x, "Null pointer in 'push_back()'" ); williamr@2: williamr@2: auto_type ptr( x ); // notrow williamr@2: this->c_private().push_back( x ); // strong, commit williamr@2: ptr.release(); // nothrow williamr@2: } williamr@2: williamr@2: template< class U > williamr@2: void push_back( std::auto_ptr x ) williamr@2: { williamr@2: push_back( x.release() ); williamr@2: } williamr@2: williamr@2: void push_front( value_type x ) williamr@2: { williamr@2: this->enforce_null_policy( x, "Null pointer in 'push_front()'" ); williamr@2: williamr@2: auto_type ptr( x ); // nothrow williamr@2: this->c_private().push_front( x ); // strong, commit williamr@2: ptr.release(); // nothrow williamr@2: } williamr@2: williamr@2: template< class U > williamr@2: void push_front( std::auto_ptr x ) williamr@2: { williamr@2: push_front( x.release() ); williamr@2: } williamr@2: williamr@2: auto_type pop_back() williamr@2: { williamr@2: BOOST_PTR_CONTAINER_THROW_EXCEPTION( this->empty(), williamr@2: bad_ptr_container_operation, williamr@2: "'pop_back()' on empty container" ); williamr@2: auto_type ptr( static_cast( williamr@2: this->c_private().back() ) ); // nothrow williamr@2: this->c_private().pop_back(); // nothrow williamr@2: return ptr_container_detail::move( ptr ); // nothrow williamr@2: } williamr@2: williamr@2: auto_type pop_front() williamr@2: { williamr@2: BOOST_PTR_CONTAINER_THROW_EXCEPTION( this->empty(), williamr@2: bad_ptr_container_operation, williamr@2: "'pop_front()' on empty container" ); williamr@2: auto_type ptr( static_cast( williamr@2: this->c_private().front() ) ); // nothrow williamr@2: this->c_private().pop_front(); // nothrow williamr@2: return ptr_container_detail::move( ptr ); williamr@2: } williamr@2: williamr@2: reference front() williamr@2: { williamr@2: BOOST_PTR_CONTAINER_THROW_EXCEPTION( this->empty(), williamr@2: bad_ptr_container_operation, williamr@2: "accessing 'front()' on empty container" ); williamr@2: BOOST_ASSERT( !::boost::is_null( this->begin() ) ); williamr@2: return *this->begin(); williamr@2: } williamr@2: williamr@2: const_reference front() const williamr@2: { williamr@2: BOOST_PTR_CONTAINER_THROW_EXCEPTION( this->empty(), williamr@2: bad_ptr_container_operation, williamr@2: "accessing 'front()' on empty container" ); williamr@2: BOOST_ASSERT( !::boost::is_null( this->begin() ) ); williamr@2: return *this->begin(); williamr@2: } williamr@2: williamr@2: reference back() williamr@2: { williamr@2: BOOST_PTR_CONTAINER_THROW_EXCEPTION( this->empty(), williamr@2: bad_ptr_container_operation, williamr@2: "accessing 'back()' on empty container" ); williamr@2: BOOST_ASSERT( !::boost::is_null( --this->end() ) ); williamr@2: return *--this->end(); williamr@2: } williamr@2: williamr@2: const_reference back() const williamr@2: { williamr@2: BOOST_PTR_CONTAINER_THROW_EXCEPTION( this->empty(), williamr@2: bad_ptr_container_operation, williamr@2: "accessing 'back()' on empty container" ); williamr@2: BOOST_ASSERT( !::boost::is_null( --this->end() ) ); williamr@2: return *--this->end(); williamr@2: } williamr@2: williamr@2: public: // deque/vector inerface williamr@2: williamr@2: reference operator[]( size_type n ) // nothrow williamr@2: { williamr@2: BOOST_ASSERT( n < this->size() ); williamr@2: BOOST_ASSERT( !this->is_null( n ) ); williamr@2: return *static_cast( this->c_private()[n] ); williamr@2: } williamr@2: williamr@2: const_reference operator[]( size_type n ) const // nothrow williamr@2: { williamr@2: BOOST_ASSERT( n < this->size() ); williamr@2: BOOST_ASSERT( !this->is_null( n ) ); williamr@2: return *static_cast( this->c_private()[n] ); williamr@2: } williamr@2: williamr@2: reference at( size_type n ) williamr@2: { williamr@2: BOOST_PTR_CONTAINER_THROW_EXCEPTION( n >= this->size(), bad_index, williamr@2: "'at()' out of bounds" ); williamr@2: BOOST_ASSERT( !this->is_null( n ) ); williamr@2: return (*this)[n]; williamr@2: } williamr@2: williamr@2: const_reference at( size_type n ) const williamr@2: { williamr@2: BOOST_PTR_CONTAINER_THROW_EXCEPTION( n >= this->size(), bad_index, williamr@2: "'at()' out of bounds" ); williamr@2: BOOST_ASSERT( !this->is_null( n ) ); williamr@2: return (*this)[n]; williamr@2: } williamr@2: williamr@2: public: // vector interface williamr@2: williamr@2: size_type capacity() const williamr@2: { williamr@2: return this->c_private().capacity(); williamr@2: } williamr@2: williamr@2: void reserve( size_type n ) williamr@2: { williamr@2: this->c_private().reserve( n ); williamr@2: } williamr@2: williamr@2: void reverse() williamr@2: { williamr@2: this->c_private().reverse(); williamr@2: } williamr@2: williamr@2: public: // assign, insert, transfer williamr@2: williamr@2: // overhead: 1 heap allocation (very cheap compared to cloning) williamr@2: template< class InputIterator > williamr@2: void assign( InputIterator first, InputIterator last ) // strong williamr@2: { williamr@2: base_type temp( first, last ); williamr@2: this->swap( temp ); williamr@2: } williamr@2: williamr@2: template< class Range > williamr@2: void assign( const Range& r ) williamr@2: { williamr@2: assign( boost::begin(r), boost::end(r ) ); williamr@2: } williamr@2: williamr@2: private: williamr@2: template< class I > williamr@2: void insert_impl( iterator before, I first, I last, std::input_iterator_tag ) // strong williamr@2: { williamr@2: ptr_sequence_adapter temp(first,last); // strong williamr@2: transfer( before, temp ); // strong, commit williamr@2: } williamr@2: williamr@2: template< class I > williamr@2: void insert_impl( iterator before, I first, I last, std::forward_iterator_tag ) // strong williamr@2: { williamr@2: if( first == last ) williamr@2: return; williamr@2: scoped_deleter sd( first, last ); // strong williamr@2: this->insert_clones_and_release( sd, before ); // strong, commit williamr@2: } williamr@2: williamr@2: public: williamr@2: williamr@2: using base_type::insert; williamr@2: williamr@2: template< class InputIterator > williamr@2: void insert( iterator before, InputIterator first, InputIterator last ) // strong williamr@2: { williamr@2: insert_impl( before, first, last, BOOST_DEDUCED_TYPENAME williamr@2: iterator_category::type() ); williamr@2: } williamr@2: williamr@2: #if defined(BOOST_NO_SFINAE) || BOOST_WORKAROUND(__SUNPRO_CC, <= 0x580) williamr@2: #else williamr@2: template< class Range > williamr@2: BOOST_DEDUCED_TYPENAME williamr@2: boost::disable_if< ptr_container_detail::is_pointer_or_integral >::type williamr@2: insert( iterator before, const Range& r ) williamr@2: { williamr@2: insert( before, boost::begin(r), boost::end(r) ); williamr@2: } williamr@2: williamr@2: #endif williamr@2: williamr@2: template< class PtrSeqAdapter > williamr@2: void transfer( iterator before, williamr@2: BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator first, williamr@2: BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator last, williamr@2: PtrSeqAdapter& from ) // strong williamr@2: { williamr@2: BOOST_ASSERT( (void*)&from != (void*)this ); williamr@2: if( from.empty() ) williamr@2: return; williamr@2: this->c_private(). williamr@2: insert( before.base(), williamr@2: first.base(), last.base() ); // strong williamr@2: from.c_private().erase( first.base(), williamr@2: last.base() ); // nothrow williamr@2: } williamr@2: williamr@2: template< class PtrSeqAdapter > williamr@2: void transfer( iterator before, williamr@2: BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator object, williamr@2: PtrSeqAdapter& from ) // strong williamr@2: { williamr@2: BOOST_ASSERT( (void*)&from != (void*)this ); williamr@2: if( from.empty() ) williamr@2: return; williamr@2: this->c_private(). williamr@2: insert( before.base(), williamr@2: *object.base() ); // strong williamr@2: from.c_private().erase( object.base() ); // nothrow williamr@2: } williamr@2: williamr@2: #if defined(BOOST_NO_SFINAE) || BOOST_WORKAROUND(__SUNPRO_CC, <= 0x580) williamr@2: #else williamr@2: williamr@2: template< class PtrSeqAdapter, class Range > williamr@2: BOOST_DEDUCED_TYPENAME boost::disable_if< boost::is_same< Range, williamr@2: BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator > >::type williamr@2: transfer( iterator before, const Range& r, PtrSeqAdapter& from ) // strong williamr@2: { williamr@2: transfer( before, boost::begin(r), boost::end(r), from ); williamr@2: } williamr@2: williamr@2: #endif williamr@2: template< class PtrSeqAdapter > williamr@2: void transfer( iterator before, PtrSeqAdapter& from ) // strong williamr@2: { williamr@2: BOOST_ASSERT( (void*)&from != (void*)this ); williamr@2: if( from.empty() ) williamr@2: return; williamr@2: this->c_private(). williamr@2: insert( before.base(), williamr@2: from.begin().base(), from.end().base() ); // strong williamr@2: from.c_private().clear(); // nothrow williamr@2: } williamr@2: williamr@2: public: // null functions williamr@2: williamr@2: bool is_null( size_type idx ) const williamr@2: { williamr@2: BOOST_ASSERT( idx < this->size() ); williamr@2: return this->c_private()[idx] == 0; williamr@2: } williamr@2: williamr@2: public: // algorithms williamr@2: williamr@2: void sort( iterator first, iterator last ) williamr@2: { williamr@2: sort( first, last, std::less() ); williamr@2: } williamr@2: williamr@2: void sort() williamr@2: { williamr@2: sort( this->begin(), this->end() ); williamr@2: } williamr@2: williamr@2: template< class Compare > williamr@2: void sort( iterator first, iterator last, Compare comp ) williamr@2: { williamr@2: BOOST_ASSERT( first <= last && "out of range sort()" ); williamr@2: BOOST_ASSERT( this->begin() <= first && "out of range sort()" ); williamr@2: BOOST_ASSERT( last <= this->end() && "out of range sort()" ); williamr@2: // some static assert on the arguments of the comparison williamr@2: std::sort( first.base(), last.base(), williamr@2: void_ptr_indirect_fun(comp) ); williamr@2: } williamr@2: williamr@2: template< class Compare > williamr@2: void sort( Compare comp ) williamr@2: { williamr@2: sort( this->begin(), this->end(), comp ); williamr@2: } williamr@2: williamr@2: void unique( iterator first, iterator last ) williamr@2: { williamr@2: unique( first, last, std::equal_to() ); williamr@2: } williamr@2: williamr@2: void unique() williamr@2: { williamr@2: unique( this->begin(), this->end() ); williamr@2: } williamr@2: williamr@2: private: williamr@2: struct is_not_zero_ptr williamr@2: { williamr@2: template< class U > williamr@2: bool operator()( const U* r ) const williamr@2: { williamr@2: return r != 0; williamr@2: } williamr@2: }; williamr@2: williamr@2: void compact_and_erase_nulls( iterator first, iterator last ) // nothrow williamr@2: { williamr@2: williamr@2: typename base_type::ptr_iterator p = std::stable_partition( williamr@2: first.base(), williamr@2: last.base(), williamr@2: is_not_zero_ptr() ); williamr@2: this->c_private().erase( p, this->end().base() ); williamr@2: williamr@2: } williamr@2: williamr@2: void range_check_impl( iterator first, iterator last, williamr@2: std::bidirectional_iterator_tag ) williamr@2: { /* do nothing */ } williamr@2: williamr@2: void range_check_impl( iterator first, iterator last, williamr@2: std::random_access_iterator_tag ) williamr@2: { williamr@2: BOOST_ASSERT( first <= last && "out of range unique()/erase_if()" ); williamr@2: BOOST_ASSERT( this->begin() <= first && "out of range unique()/erase_if()" ); williamr@2: BOOST_ASSERT( last <= this->end() && "out of range unique()/erase_if)(" ); williamr@2: } williamr@2: williamr@2: void range_check( iterator first, iterator last ) williamr@2: { williamr@2: range_check_impl( first, last, williamr@2: BOOST_DEDUCED_TYPENAME iterator_category::type() ); williamr@2: } williamr@2: williamr@2: public: williamr@2: williamr@2: template< class Compare > williamr@2: void unique( iterator first, iterator last, Compare comp ) williamr@2: { williamr@2: range_check(first,last); williamr@2: williamr@2: iterator prev = first; williamr@2: iterator next = first; williamr@2: ++next; williamr@2: for( ; next != last; ++next ) williamr@2: { williamr@2: BOOST_ASSERT( !::boost::is_null(prev) ); williamr@2: BOOST_ASSERT( !::boost::is_null(next) ); williamr@2: if( comp( *prev, *next ) ) williamr@2: { williamr@2: this->remove( next ); // delete object williamr@2: *next.base() = 0; // mark pointer as deleted williamr@2: } williamr@2: else williamr@2: { williamr@2: prev = next; williamr@2: } williamr@2: // ++next williamr@2: } williamr@2: williamr@2: compact_and_erase_nulls( first, last ); williamr@2: } williamr@2: williamr@2: template< class Compare > williamr@2: void unique( Compare comp ) williamr@2: { williamr@2: unique( this->begin(), this->end(), comp ); williamr@2: } williamr@2: williamr@2: template< class Pred > williamr@2: void erase_if( iterator first, iterator last, Pred pred ) williamr@2: { williamr@2: range_check(first,last); williamr@2: williamr@2: iterator next = first; williamr@2: for( ; next != last; ++next ) williamr@2: { williamr@2: BOOST_ASSERT( !::boost::is_null(next) ); williamr@2: if( pred( *next ) ) williamr@2: { williamr@2: this->remove( next ); // delete object williamr@2: *next.base() = 0; // mark pointer as deleted williamr@2: } williamr@2: } williamr@2: williamr@2: compact_and_erase_nulls( first, last ); williamr@2: } williamr@2: williamr@2: template< class Pred > williamr@2: void erase_if( Pred pred ) williamr@2: { williamr@2: erase_if( this->begin(), this->end(), pred ); williamr@2: } williamr@2: williamr@2: williamr@2: void merge( iterator first, iterator last, williamr@2: ptr_sequence_adapter& from ) williamr@2: { williamr@2: merge( first, last, from, std::less() ); williamr@2: } williamr@2: williamr@2: template< class BinPred > williamr@2: void merge( iterator first, iterator last, williamr@2: ptr_sequence_adapter& from, BinPred pred ) williamr@2: { williamr@2: void_ptr_indirect_fun bin_pred(pred); williamr@2: size_type current_size = this->size(); williamr@2: this->transfer( this->end(), first, last, from ); williamr@2: typename base_type::ptr_iterator middle = this->begin().base(); williamr@2: std::advance(middle,current_size); williamr@2: std::inplace_merge( this->begin().base(), williamr@2: middle, williamr@2: this->end().base(), williamr@2: bin_pred ); williamr@2: } williamr@2: williamr@2: void merge( ptr_sequence_adapter& r ) williamr@2: { williamr@2: merge( r, std::less() ); williamr@2: BOOST_ASSERT( r.empty() ); williamr@2: } williamr@2: williamr@2: template< class BinPred > williamr@2: void merge( ptr_sequence_adapter& r, BinPred pred ) williamr@2: { williamr@2: merge( r.begin(), r.end(), r, pred ); williamr@2: BOOST_ASSERT( r.empty() ); williamr@2: } williamr@2: williamr@2: }; williamr@2: williamr@2: williamr@2: } // namespace 'boost' williamr@2: williamr@2: #endif