// 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

#include <boost/assert.hpp>
#include <boost/iterator/reverse_iterator.hpp>
#include <boost/mpl/if.hpp>
#include <boost/swap.hpp>
#include <boost/type_traits/aligned_storage.hpp>
#include <boost/type_traits/alignment_of.hpp>
#include <boost/type_traits/has_trivial_assign.hpp>
#include <boost/type_traits/has_trivial_destructor.hpp>
#include <cstring>
#include <iterator>
#include <memory>

namespace boost
{

    //
    // 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:
    // 
    // - no swap() and resize() provided
    // - works with allocators from Boost.Interprocess
    // - do not store T[N] on the stack, as this is bad when the
    //   type has a non-trivial default constructor.
    // - handless non-pod types in an exception-safe manner
    // - has a fixed capacity, but a non-fixed size
    // - provides a non-growing (thus inlineable) push_back()
    //
    template< class T, unsigned N = 256, class Allocator = std::allocator<T> >
    class auto_buffer;

    

    template< class T, unsigned N, class Allocator >
    class auto_buffer : Allocator
    {
    private:        
        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_< boost::has_trivial_assign<T>,
                                          const value_type, 
                                          const_reference >::type
                                                      optimized_const_reference;
    private:

        pointer allocate()
        {
            // @remark: we cannot use is_on_stack() yet!
            if( capacity_ > N )
                return &*get_allocator().allocate( capacity_ );
            else
                return static_cast<T*>( stack_storage_.address() );
        }

        void deallocate()
        {
            if( capacity_ <= N )
                return;
            get_allocator().deallocate( allocator_pointer(buffer_), capacity_ );            
        }

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

        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 >
        void copy_rai( I begin, I end, 
                       pointer where, const boost::integral_constant<bool, b>& )
        {
            std::uninitialized_copy( begin, end, where );
        }        
        
        template< class I >
        void copy( I begin, I end, pointer where, std::forward_iterator_tag )
        {
            std::uninitialized_copy( begin, end, where );
        }

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

        void auto_buffer_destroy( const boost::true_type& ) 
        {
            deallocate();
        }

        bool is_valid() const
        {
            if( buffer_ == 0 && (size_ > 0 || capacity_ > 0) )
                return false;
            
            if( buffer_ == stack_storage_.address() )
                if( capacity_ > N )
                    return false;                
                
            if( size_ > capacity_ )
                return false;
            
            return true;
        }

    private: // we cannot copy
        auto_buffer( const auto_buffer& );
        auto_buffer& operator=( const auto_buffer& );
        
    public:
        auto_buffer()
            : capacity_( 0 ),
              buffer_( 0 ),
              size_( 0 )
        {
            BOOST_ASSERT( is_valid() ); 
        }
        
        explicit auto_buffer( size_type capacity ) 
            : capacity_( capacity ),
              buffer_( allocate() ),
              size_( 0 )
        {
            BOOST_ASSERT( is_valid() ); 
        }
        
        auto_buffer( size_type capacity, optimized_const_reference init_value )
            : capacity_( capacity ),
              buffer_( allocate() ),
              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 ),
              buffer_( allocate() ),
              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 ),
              buffer_( allocate() ),
              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() ),
              size_( 0 )
        {
            this->copy( begin, end, buffer_, 
                        typename std::iterator_traits<ForwardIterator>::iterator_category() );
            size_ = capacity_;
            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() ),
              size_( 0 )
        {
            this->copy( begin, end, buffer_,
                        typename std::iterator_traits<ForwardIterator>::iterator_category() );
            size_ = capacity_;
            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 stack_storage_.address() == buffer_;
        }

        bool has_allocated_buffer()
        {
            return buffer_ != 0;
        }
        
        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
        {
            return buffer_[n];
        }

        void allocate_buffer( size_type capacity )
        {
            BOOST_ASSERT( !has_allocated_buffer() );
            capacity_ = capacity;

            struct undo_capacity
            {
                size_type& c;
                bool       dismiss;
                undo_capacity( size_type& c ) : c(c), dismiss(false)
                { }
                ~undo_capacity()
                {
                    if(dismiss)
                        return;
                    c = 0;
                }
            };
            undo_capacity scope_guard( capacity_ );
            buffer_ = allocate();
            scope_guard.dismiss = true;
        }
        
        void push_back()
        {
            BOOST_ASSERT( !full() );
            new (buffer_ + size_) T;
            ++size_;            
        }
        
        void push_back( optimized_const_reference x ) // non-growing
        {
            BOOST_ASSERT( !full() );
            new (buffer_ + size_) T( x );
            ++size_;            
        }

        template< class ForwardIterator >
        void push_back( ForwardIterator begin, 
                        ForwardIterator end ) // non-growing
        {
            BOOST_ASSERT( size_ + std::distance(begin,end) <= capacity_ );
            this->copy( begin, end, buffer_ + size_,
                        typename std::iterator_traits<ForwardIterator>::iterator_category() );
            size_ += std::distance(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_ );
        }

        void clear_buffer()
        {
            (*this).~auto_buffer();
            capacity_ = 0;
            buffer_   = 0;
            size_     = 0;
            BOOST_ASSERT( !has_allocated_buffer() );
        }
        
        void uninitialized_grow( size_type n ) // nothrow
        {
            BOOST_ASSERT( size_ + n <= capacity_ );
            size_ += n;
        }
        
        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 );
        }
        
    private:
        typedef boost::aligned_storage< sizeof(T) * N, 
                                        boost::alignment_of<T>::value > storage;
        size_type   capacity_;        
        pointer     buffer_;
        size_type   size_;
        storage     stack_storage_;
    };
    
}

#endif