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