ptr_sequence_adapter.hpp

support vector clustering for vc++

        void reverse()
        {
            this->c_private().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 )
        {
            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) || BOOST_WORKAROUND(__SUNPRO_CC, <= 0x580)
#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->c_private().
                insert( before.base(), 
                        first.base(), last.base() ); // strong
            from.c_private().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->c_private().
                insert( before.base(),
                        *object.base() );                 // strong
            from.c_private().erase( object.base() );      // nothrow
        }

#if defined(BOOST_NO_SFINAE) || BOOST_WORKAROUND(__SUNPRO_CC, <= 0x580)
#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->c_private().
                insert( before.base(),
                        from.begin().base(), from.end().base() ); // strong
            from.c_private().clear();                             // nothrow
        }

    public: // null functions
         
        bool is_null( size_type idx ) const
        {
            BOOST_ASSERT( idx < this->size() );
            return this->c_private()[idx] == 0;
        }

    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;
            }
        };

        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->c_private().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);

            iterator next = first; 
            for( ; next != last; ++next )
            {
                BOOST_ASSERT( !::boost::is_null(next) );
                if( pred( *next ) )
                {
                    this->remove( next ); // delete object
                    *next.base() = 0;     // mark pointer as deleted
                }
            }

            compact_and_erase_nulls( first, last );
        }
        
        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