// Copyright Thorsten Ottosen, 2009.
// 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)

#ifndef BOOST_UTILITY_AUTO_BUFFER_HPP_25_02_2009
#define BOOST_UTILITY_AUTO_BUFFER_HPP_25_02_2009

#if defined(_MSC_VER) && (_MSC_VER >= 1200)
# pragma once
#endif

#if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)  
#pragma warning(push)  
#pragma warning(disable:4996)
#endif

#include <boost/assert.hpp>
#include <boost/iterator/reverse_iterator.hpp>
#include <boost/mpl/if.hpp>
#include <boost/multi_index/detail/scope_guard.hpp>
#include <boost/swap.hpp>
#include <boost/type_traits/aligned_storage.hpp>
#include <boost/type_traits/alignment_of.hpp>
#include <boost/type_traits/has_nothrow_copy.hpp>
#include <boost/type_traits/has_nothrow_assign.hpp>
#include <boost/type_traits/has_trivial_assign.hpp>
#include <boost/type_traits/has_trivial_destructor.hpp>
#include <algorithm>
#include <cstring>
#include <iterator>
#include <memory>
#include <stdexcept>

namespace boost
{

    //
    // Policies for creating the stack buffer.
    //
    template< unsigned N >
    struct store_n_objects
    {
        BOOST_STATIC_CONSTANT( unsigned, value = N );
    };

    template< unsigned N >
    struct store_n_bytes
    {
        BOOST_STATIC_CONSTANT( unsigned, value = N );        
    };

    namespace auto_buffer_detail
    {
        template< class Policy, class T >
        struct compute_buffer_size
        {
            BOOST_STATIC_CONSTANT( unsigned, value = Policy::value * sizeof(T) );
        };

        template< unsigned N, class T >
        struct compute_buffer_size< boost::store_n_bytes<N>, T >
        {
            BOOST_STATIC_CONSTANT( unsigned, value = N ); 
        };

        template< class Policy, class T >
        struct compute_buffer_objects
        {
            BOOST_STATIC_CONSTANT( unsigned, value = Policy::value );            
        };

        template< unsigned N, class T >
        struct compute_buffer_objects< boost::store_n_bytes<N>, T >
        {
            BOOST_STATIC_CONSTANT( unsigned, value = N / sizeof(T) ); 
        };
    }
    
    //
    // As simple scoped buffer class that stores smaller arrays
    // on the stack and larger on the heap. It can be seen as a
    // C++ version of C99's variable length arrays, with almost
    // all its postitive effects, and none of its negative.
    // 
    // Using this class lead to a major speed-improvement in many
    // cases.
    // 
    // The idea originates from Matthew Wilson's stlsoft::auto_buffer,
    // albeit there are some minor differences.
    // 
    template< class T, 
              class StackBufferPolicy = boost::store_n_objects<256>, 
              class Allocator         = std::allocator<T> >
    class auto_buffer;

    

    template< class T, class StackBufferPolicy, class Allocator >
    class auto_buffer : Allocator
    {
    private:        
        enum { N = auto_buffer_detail::
                   compute_buffer_objects<StackBufferPolicy,T>::value };
        BOOST_STATIC_ASSERT( N > 0 );

    public:
        typedef Allocator                                allocator_type;
        typedef T                                        value_type;
        typedef typename Allocator::size_type            size_type;
        typedef typename Allocator::difference_type      difference_type;
        typedef T*                                       pointer;
        typedef typename Allocator::pointer              allocator_pointer;           
        typedef const T*                                 const_pointer;
        typedef T&                                       reference;
        typedef const T&                                 const_reference;
        typedef pointer                                  iterator;
        typedef const_pointer                            const_iterator;
        typedef boost::reverse_iterator<iterator>        reverse_iterator;
        typedef boost::reverse_iterator<const_iterator>  const_reverse_iterator;
        typedef typename boost::mpl::if_c< boost::has_trivial_assign<T>::value
                                           && sizeof(T) <= sizeof(long double),
                                          const value_type, 
                                          const_reference >::type
                                                      optimized_const_reference;
    private:

        pointer allocate( size_type capacity )
        {
            if( capacity > N )
                return &*get_allocator().allocate( capacity );
            else
                return static_cast<T*>( stack_storage_.address() );
        }

        void deallocate( pointer where, size_type capacity )
        {
            if( capacity <= N )
                return;
            get_allocator().deallocate( allocator_pointer(where), capacity );            
        }

        template< class I >
        static void copy_impl( I begin, I end, pointer where, std::random_access_iterator_tag )
        {
            copy_rai( begin, end, where, boost::has_trivial_assign<T>() );
        }

        static void copy_rai( const T* begin, const T* end, 
                              pointer where, const boost::true_type& )
        {
            std::memcpy( where, begin, sizeof(T) * std::distance(begin,end) );
        }

        template< class I, bool b >
        static void copy_rai( I begin, I end, 
                              pointer where, const boost::integral_constant<bool, b>& )
        {
            std::uninitialized_copy( begin, end, where );
        }        
        
        template< class I >
        static void copy_impl( I begin, I end, pointer where, std::forward_iterator_tag )
        {
            std::uninitialized_copy( begin, end, where );
        }
        
        template< class I >
        static void copy_impl( I begin, I end, pointer where )
        {
            copy_impl( begin, end, where, 
                       typename std::iterator_traits<I>::iterator_category() );
        }

        template< class I, class I2 >
        static void assign_impl( I begin, I end, I2 where )
        {
            assign_impl( begin, end, where, boost::has_trivial_assign<T>() );
        }

        template< class I, class I2 >
        static void assign_impl( I begin, I end, I2 where, const boost::true_type& )
        {
            std::memcpy( where, begin, sizeof(T) * std::distance(begin,end) ); 
        }

        template< class I, class I2 >
        static void assign_impl( I begin, I end, I2 where, const boost::false_type& )
        {
            for( ; begin != end; ++begin, ++where )
                *where = *begin;
        }

        void unchecked_push_back_n( size_type n, const boost::true_type& )
        {
            std::uninitialized_fill( end(), end() + n, T() );
        }

        void unchecked_push_back_n( size_type n, const boost::false_type& )
        {
            for( size_type i = 0u; i < n; ++i )
                unchecked_push_back();
        }
        
        void auto_buffer_destroy( pointer where, const boost::false_type& )
        {
            (*where).~T();
        }

        void auto_buffer_destroy( pointer, const boost::true_type& )
        { }

        void auto_buffer_destroy( pointer where )
        {
            auto_buffer_destroy( where, boost::has_trivial_destructor<T>() );
        }

        void destroy_back_n( size_type n, const boost::false_type& )
        {
            pointer buffer = buffer_ + size_ - 1;
            for( ; buffer >= buffer_; --buffer )
                auto_buffer_destroy( buffer );
        }

        void destroy_back_n( size_type n, const boost::true_type& )
        { }                

        void auto_buffer_destroy( const boost::false_type& x ) 
        {
            destroy_back_n( size_, x );
            deallocate( buffer_, capacity_ );
        }

        void auto_buffer_destroy( const boost::true_type& ) 
        {
            deallocate( buffer_, capacity_ );
        }
        
        pointer move_to_new_buffer( size_type new_capacity, const boost::false_type& )
        {
            pointer new_buffer = allocate( new_capacity ); // strong
            boost::multi_index::detail::scope_guard guard = 
                boost::multi_index::detail::make_obj_guard( *this, 
                                                            &auto_buffer::deallocate,         
                                                            new_buffer,
                                                            new_capacity );
            copy_impl( begin(), end(), new_buffer ); // strong
            guard.dismiss();                         // nothrow
            return new_buffer;
        }

        pointer move_to_new_buffer( size_type new_capacity, const boost::true_type& )
        {
            pointer new_buffer = allocate( new_capacity ); // strong
            copy_impl( begin(), end(), new_buffer );       // nothrow
            return new_buffer;
        }

        void reserve_impl( size_type new_capacity )
        {
            pointer new_buffer = move_to_new_buffer( new_capacity,
                                                 boost::has_nothrow_copy<T>() );
            (*this).~auto_buffer();
            buffer_   = new_buffer;
            capacity_ = new_capacity;     
            BOOST_ASSERT( size_ < capacity_ );  
        }

        static void swap_helper( auto_buffer& l, auto_buffer& r,
                                 const boost::true_type& )
        {
            BOOST_ASSERT( l.is_on_stack() && r.is_on_stack() );
            
            auto_buffer temp( l.begin(), l.end() );
            copy_impl( r.begin(), r.end(), l.begin() );
            copy_impl( temp.begin(), temp.end(), r.begin() ); 
            boost::swap( l.size_, r.size_ );
            boost::swap( l.capacity_, r.capacity_ );
        }

        static void swap_helper( auto_buffer& l, auto_buffer& r,
                                 const boost::false_type& )
        {
            BOOST_ASSERT( l.is_on_stack() && r.is_on_stack() );
            size_type min_size    = l.size_ < r.size_ ? l.size_ : r.size_;
            size_type max_size    = l.size_ > r.size_ ? l.size_ : r.size_;
            size_type diff        = max_size - min_size;
            auto_buffer* smallest = l.size_ == min_size ? &l : &r;
            auto_buffer* largest  = smallest == &l ? &r : &l;
            
            for( unsigned i = 0u; i < diff; ++i )
                smallest->unchecked_push_back();
            
            for( size_type i = 0u; i < max_size; ++i )
                boost::swap( (*smallest)[i], (*largest)[i] ); 
            largest->pop_back_n( diff );
            boost::swap( l.capacity_, r.capacity_ );
        }
        
        bool is_valid() const
        {
            if( buffer_ == 0 )
                return false;

            if( capacity_ < N )
                return false;

            if( !is_on_stack() && capacity_ <= N )
                return false;
            
            if( buffer_ == stack_storage_.address() )
                if( capacity_ > N )
                    return false;                
                
            if( size_ > capacity_ )
                return false;
            
            return true;
        }
        
    public:
        auto_buffer()
            : capacity_( N ),
              buffer_( static_cast<T*>(stack_storage_.address()) ),
              size_( 0 )
        {
            BOOST_ASSERT( is_valid() ); 
        }

        auto_buffer( const auto_buffer& r ) 
            : capacity_( r.size_ > N ? r.size_ : N ),
              buffer_( allocate(capacity_) ),
              size_( 0 )
        {
            copy_impl( r.begin(), r.end(), buffer_ );
            size_ = r.size_;
            BOOST_ASSERT( is_valid() );
        }

        auto_buffer& operator=( const auto_buffer& r ) // basic
        {
            BOOST_ASSERT( this != &r );
            difference_type diff = size_ - r.size_;
            if( diff >= 0 )
            {
                pop_back_n( static_cast<size_type>(diff) );
                assign_impl( r.begin(), r.end(), begin() );
            }
            else
            {
                if( capacity_ >= r.size() )
                {
                    unchecked_push_back_n( static_cast<size_type>(-diff) );
                    assign_impl( r.begin(), r.end(), begin() );
                }
                else 
                {
                    pointer new_buffer = allocate( r.size() );
                    (*this).~auto_buffer();
                    buffer_   = new_buffer;
                    capacity_ = r.size();
                    copy_impl( r.begin(), r.end(), buffer_ );
                    size_     = capacity_;
                }
            }

            BOOST_ASSERT( size() == r.size() );
            BOOST_ASSERT( is_valid() );   
            return *this;          
        }
        
        explicit auto_buffer( size_type capacity ) 
            : capacity_( capacity > N ? capacity : N ),
              buffer_( allocate(capacity_) ),
              size_( 0 )
        {
            BOOST_ASSERT( is_valid() ); 
        }
        
        auto_buffer( size_type capacity, optimized_const_reference init_value )
            : capacity_( capacity > N ? capacity : N ),
              buffer_( allocate(capacity_) ),
              size_( 0 )
        {
            std::uninitialized_fill( buffer_, buffer_ + capacity, init_value );
            size_ = capacity;
            BOOST_ASSERT( is_valid() );  
        }

        auto_buffer( size_type capacity, const allocator_type& a )
            : allocator_type( a ),
              capacity_( capacity > N ? capacity : N ),
              buffer_( allocate(capacity_) ),
              size_( 0 )
        {
            BOOST_ASSERT( is_valid() );  
        }

        auto_buffer( size_type capacity, optimized_const_reference init_value, 
                     const allocator_type& a )
            : allocator_type( a ),
              capacity_( capacity > N ? capacity : N ),
              buffer_( allocate(capacity_) ),
              size_( 0 )
        {
            std::uninitialized_fill( buffer_, buffer_ + capacity, init_value );
            size_ = capacity;
            BOOST_ASSERT( is_valid() );  
        }        

        template< class ForwardIterator >
        auto_buffer( ForwardIterator begin, ForwardIterator end )
            : capacity_( std::distance(begin,end) ),
              buffer_( allocate(capacity_) ),
              size_( 0 )
        {
            copy_impl( begin, end, buffer_ );
            size_ = capacity_;
            if( capacity_ < N )
                capacity_ = N;
            BOOST_ASSERT( is_valid() );  
        }

        template< class ForwardIterator >
        auto_buffer( ForwardIterator begin, ForwardIterator end, 
                     const allocator_type& a )
            : allocator_type( a ),
              capacity_( std::distance(begin,end) ),
              buffer_( allocate(capacity_) ),
              size_( 0 )
        {
            copy_impl( begin, end, buffer_ );                      
            size_ = capacity_;
            if( capacity_ < N )
                capacity_ = N;
            BOOST_ASSERT( is_valid() );  
        }

        ~auto_buffer() 
        {
            BOOST_ASSERT( is_valid() ); 
            if( buffer_ )
                auto_buffer_destroy( boost::has_trivial_destructor<T>() );
        }
        
    public:
        bool empty() const
        {
            return size_ == 0;
        }

        bool full() const
        {
            return size_ == capacity_;
        }
        
        bool is_on_stack() const
        {
            return capacity_ <= N;
        }
        
        size_type size() const
        {
            return size_;
        }
        
        size_type capacity() const
        {
            return capacity_;
        }

    public:
        pointer data()
        {
            return buffer_;
        }
        
        const_pointer data() const
        {
            return buffer_;
        }
        
        allocator_type& get_allocator()
        { 
            return static_cast<allocator_type&>(*this); 
        }
        
        const allocator_type& get_allocator() const
        { 
            return static_cast<const allocator_type&>(*this); 
        }

    public:
        iterator begin()
        {
            return buffer_;
        }
        
        const_iterator begin() const
        {
            return buffer_;
        }
        
        iterator end()
        {
            return buffer_ + size_;
        }
        
        const_iterator end() const
        {
            return buffer_ + size_;
        }
        
        reverse_iterator rbegin()
        {
            return reverse_iterator(end());
        }
        
        const_reverse_iterator rbegin() const
        {
            return const_reverse_iterator(end());
        }
        
        reverse_iterator rend()
        {
            return reverse_iterator(begin());
        }
        
        const_reverse_iterator rend() const
        {
            return const_reverse_iterator(begin());
        }
        
        const_iterator cbegin() const
        {
            return const_cast<const auto_buffer*>(this)->begin();
        }
        
        const_iterator cend() const
        {
            return const_cast<const auto_buffer*>(this)->end();
        }
        
        const_reverse_iterator crbegin() const
        {
            return const_cast<const auto_buffer*>(this)->rbegin();
        }
        
        const_reverse_iterator crend() const
        {
            return const_cast<const auto_buffer*>(this)->rend();
        }

    public:
        reference front()
        {
            return buffer_[0];
        }
        
        optimized_const_reference front() const
        {
            return buffer_[0];
        }
        
        reference back()
        {
            return buffer_[size_-1];
        }
        
        optimized_const_reference back() const
        {
            return buffer_[size_-1];
        }
        
        reference operator[]( size_type n )
        {
            BOOST_ASSERT( n < size_ );
            return buffer_[n];
        }
        
        optimized_const_reference operator[]( size_type n ) const
        {
            BOOST_ASSERT( n < size_ );
            return buffer_[n];
        }

        void unchecked_push_back()
        {
            BOOST_ASSERT( !full() );
            new (buffer_ + size_) T;
            ++size_;            
        }

        void unchecked_push_back_n( size_type n )
        {
            BOOST_ASSERT( size_ + n <= capacity_ );
            unchecked_push_back_n( n, boost::has_trivial_assign<T>() );
        }

        void unchecked_push_back( optimized_const_reference x ) // non-growing
        {
            BOOST_ASSERT( !full() );
            new (buffer_ + size_) T( x );
            ++size_;            
        }

        template< class ForwardIterator >
        void unchecked_push_back( ForwardIterator begin, 
                                  ForwardIterator end ) // non-growing
        {
            BOOST_ASSERT( size_ + std::distance(begin,end) <= capacity_ );
            copy_impl( begin, end, buffer_ + size_ );                      
            size_ += std::distance(begin,end);            
        }
                
        void reserve_precisely( size_type n ) 
        {
            BOOST_ASSERT( capacity_  >= N );

            if( n <= capacity_ )
                return;
            reserve_impl( n );
            BOOST_ASSERT( capacity_ == n );
        }
        
        void reserve( size_type n ) // strong
        {
            BOOST_ASSERT( capacity_  >= N );
            
            if( n <= capacity_ )
                return;

            //
            // Remark: we grow the capacity quite agressively.
            //         this is justified since we aim to minimize
            //         heap-allocations, and because we only use
            //         the buffer locally.
            size_type new_capacity       = capacity_ * 2u;
            new_capacity                 = new_capacity < n ? n : new_capacity;
            bool      has_wrapped_around = new_capacity < capacity_;
            if( has_wrapped_around )
            {
                std::length_error e( "Could not expand buffer! Maximum limit exceeded." );
                boost::throw_exception( e ); 
            }

            reserve_impl( new_capacity );
            BOOST_ASSERT( capacity_ >= n );
        }

        void push_back()
        {
            if( size_ == capacity_ )
                reserve( size_ + 1u );
            unchecked_push_back();            
        }

        void push_back( optimized_const_reference x )
        {
            if( size_ == capacity_ )
                reserve( size_ + 1u );
            unchecked_push_back( x );         
        }

        template< class ForwardIterator >
        void push_back( ForwardIterator begin, ForwardIterator end )
        {
            difference_type diff = std::distance(begin,end);
            if( size_ + diff > capacity_ )
                reserve( size_ + diff );
            unchecked_push_back( begin, end );
        }        

        void pop_back()
        {
            BOOST_ASSERT( !empty() );
            auto_buffer_destroy( buffer_ + size_ - 1u );
            --size_;
        }

        void pop_back_n( size_type n )
        {
            BOOST_ASSERT( n <= size_ );
            destroy_back_n( n, boost::has_trivial_destructor<T>() ); 
            size_ -= n;
        }

        void clear()
        {
            pop_back_n( size_ );
        }
        
        pointer uninitialized_grow( size_type n ) // nothrow
        {
            BOOST_ASSERT( size_ + n <= capacity_ );
            pointer res = end();
            size_ += n;
            return res;
        }
        
        void uninitialized_shrink( size_type n ) // nothrow
        {
            // @remark: test for wrap-around
            BOOST_ASSERT( size_ - n <= capacity_ );
            size_ -= n;
        }

        void uninitialized_resize( size_type n )
        {
            if( n > size() )
                uninitialized_grow( n - size() );
            else if( n < size() )
                uninitialized_shrink( size() - n );
            else
                ;
            
           BOOST_ASSERT( size() == n );
        }
        
        // nothrow  - if both buffer are on the heap, or
        //          - if one buffer is on the heap and one has
        //            'has_allocated_buffer() == false', or
        //          - if copy-construction cannot throw
        // basic    - otherwise (better guarantee impossible)
        // requirement: the allocator must be no-throw-swappable
        void swap( auto_buffer& r ) 
        {
            bool on_stack      = is_on_stack();
            bool r_on_stack    = r.is_on_stack();
            bool both_on_heap  = !on_stack && !r_on_stack;
            if( both_on_heap )                
            {
                boost::swap( get_allocator(), r.get_allocator() );
                boost::swap( capacity_, r.capacity_ );
                boost::swap( buffer_, r.buffer_ );
                boost::swap( size_, r.size_ );
                BOOST_ASSERT( is_valid() );
                BOOST_ASSERT( r.is_valid() );
                return;
            }

            BOOST_ASSERT( on_stack || r_on_stack );
            bool exactly_one_on_stack = (on_stack && !r_on_stack) ||
                                        (!on_stack && r_on_stack);

            //
            // Remark: we now know that we cannot copy into
            //         the unused stack buffer. 
            //
            if( exactly_one_on_stack )
            {
                auto_buffer* one_on_stack = on_stack ? this : &r;
                auto_buffer* other        = on_stack ? &r : this;
                pointer new_buffer = static_cast<T*>(other->stack_storage_.address());
                copy_impl( one_on_stack->begin(), one_on_stack->end(), 
                           new_buffer );                            // strong
                one_on_stack->~auto_buffer();                       // nothrow
                boost::swap( get_allocator(), r.get_allocator() );  // assume nothrow
                boost::swap( capacity_, r.capacity_ );
                boost::swap( size_, r.size_ );
                one_on_stack->buffer_ = other->buffer_;
                other->buffer_        = new_buffer;
                BOOST_ASSERT( other->is_on_stack() );
                BOOST_ASSERT( !one_on_stack->is_on_stack() );
                BOOST_ASSERT( is_valid() );
                BOOST_ASSERT( r.is_valid() );
                return;
            }
            
            BOOST_ASSERT( on_stack && r_on_stack );
            swap_helper( *this, r, boost::has_trivial_assign<T>() );
            BOOST_ASSERT( is_valid() );
            BOOST_ASSERT( r.is_valid() );
        }
        
    private:
        typedef boost::aligned_storage< N * sizeof(T), 
                                        boost::alignment_of<T>::value >
                               storage;
        size_type   capacity_;        
        pointer     buffer_;
        size_type   size_;
        storage     stack_storage_;
    };

    template< class T, class SBP, class A >
    inline void swap( auto_buffer<T,SBP,A>& l, auto_buffer<T,SBP,A>& r )
    {
        l.swap( r );
    }

    template< class T, class SBP, class A >
    inline bool operator==( const auto_buffer<T,SBP,A>& l, 
                            const auto_buffer<T,SBP,A>& r )
    {
        if( l.size() != r.size() )
            return false;
        return std::equal( l.begin(), l.end(), r.begin() );
    }

    template< class T, class SBP, class A >
    inline bool operator!=( const auto_buffer<T,SBP,A>& l, 
                            const auto_buffer<T,SBP,A>& r )
    {
        return !(l == r);
    }

    template< class T, class SBP, class A >
    inline bool operator<( const auto_buffer<T,SBP,A>& l, 
                           const auto_buffer<T,SBP,A>& r )
    {
        return std::lexicographical_compare( l.begin(), l.end(),
                                             r.begin(), r.end() );
    }

    template< class T, class SBP, class A >
    inline bool operator>( const auto_buffer<T,SBP,A>& l, 
                           const auto_buffer<T,SBP,A>& r )
    {
        return (r < l);
    }

    template< class T, class SBP, class A >
    inline bool operator<=( const auto_buffer<T,SBP,A>& l, 
                            const auto_buffer<T,SBP,A>& r )
    {
        return !(r > l);
    }

    template< class T, class SBP, class A >
    inline bool operator>=( const auto_buffer<T,SBP,A>& l, 
                            const auto_buffer<T,SBP,A>& r )
    {
        return !(l < r);
    }
    
}

#if BOOST_WORKAROUND(BOOST_MSVC, >= 1400)  
#pragma warning(pop)  
#endif  

#endif