#ifndef ORIGIN_VECTOR_BASE_HPP
#define ORIGIN_VECTOR_BASE_HPP

#include <origin/utility/typestr.hpp>

namespace origin {

// NOTE: We're basically defining a subtle implementation-specific concept
// over the vector. Specifically, we have a concept that denotes operations
// and properties of the "three pointer system". In fact, we could probably
// generalize it in such a way that it becomes an extractable base class for
// working with raw, dynamically allocated memory.
// What shoudl we call this? MemoryRange.

#if ORIGIN_HAS_CONCEPTS
concept MemoryRange<typename Range>
    : HasAllocator<Range>
{
    pointer Range::start();
    pointer Range::finish();
    pointer Range::extent();
    allocator_type& get_allocator();
}
#endif

/** @internal
 * The vector_impl defines a vector-specific allocator that tracks the start,
 * finish, and capacity of the region of memory that has been allocated. This
 * class partially implements the underlying structure of the MemoryRange
 * concept, but does not implement measures on size and capacity. Note that
 * this class does not actually manage the memory defined by these pointers,
 * it simply describes them.
 *
 * I guess the concept of this class binds the allocator over a specific
 * region of memory.
 *
 * @note This class uses the EBO (on the allocator type) to reduce the size
 * of the vector object.
 */
template <typename Alloc>
struct vector_impl : Alloc
{
    typedef Alloc allocator_type;
    typedef typename allocator_type::size_type size_type;
    typedef typename allocator_type::pointer pointer;

    vector_impl()
        : allocator_type(), _start(0), _finish(0), _extent(0)
    { }

    vector_impl(vector_impl const& x)
        : allocator_type(x), _start(x._start), _finish(x._finish), _extent(x._extent)
    { }

    /**
     * The move constructor copies the pointer structure from x and then resets
     * x so that it no longer refers to its original memory range.
     */
    vector_impl(vector_impl&& x)
        : allocator_type(x), _start(x._start), _finish(x._finish), _extent(x._extent)
    { x.reset(); }

    /** @name Allocate and Deallocate
     * The allocate and deallocate functions guard the underlying allocator
     * implementation from either allocating 0 elements or deallocating a null
     * pointer.
     *
     * @todo Do we really need to provide these overloads?
     */
    //@{
    pointer allocate(size_type n)
    { return n != 0 ? Alloc::allocate(n) : 0; }

    void deallocate(pointer p, size_type n)
    { if(p) Alloc::deallocate(p, n); }
    //@}

    /** Reset the allocator to null values. */
    void reset()
    { _start = _finish = _extent = 0; }

    pointer _start;
    pointer _finish;
    pointer _extent;
};


/** @internal
 * The vector_base class implements the private components of the vector that
 * binds the standard interface to the allocation mechanisms. This class is
 * inherited privately from the vector class.
 *
 * @note According to STLPort (from which the GCC implementation is derived)
 * is to allocate, but not initialize the elements of the vector. Deferring
 * initialization makes exception safety easier to guarantee in this class.
 *
 * @note GCC delegates the pointer information to the implementation class,
 * which is also derived from the allocator. STLPort seems to move this into
 * an allocator proxy. Both of these use the EBO to reduce the size of the
 * vector.
 *
 * @todo This needs some serious cleanup and refactoring. Can we get rid of
 * the do_insert and do_erase functions and make something a little more...
 * comprehensible. Also, the request function is called only once. Does it
 * actually make sense to leave it there? One thing that might be nice is
 * to actually delegate all of the memory management to the various policies.
 * That would make grow() and shrink() legitimate functions. Maybe.
 */
template <typename T, typename Policies>
struct vector_base
    : vector_policies<T, Policies>
{
private:
    typedef vector_policies<T, Policies> base_type;
public:
    typedef typename base_type::allocator_type allocator_type;
    typedef typename allocator_type::pointer pointer;
    typedef typename allocator_type::const_pointer const_pointer;
    typedef typename allocator_type::size_type size_type;

    typedef vector_impl<allocator_type> impl_type;

    /** @name Constructors and Destructor */
    //@{
    vector_base()
        : _impl()
    { }

    /**
     * Create a copy of the memory of x such that this vector will have a
     * capacity equal to the size of x. The elements of x are not copied by
     * this constructor. All memory is uninitialized.
     */
    vector_base(vector_base const& x)
        : _impl()
    {
        _impl._finish = _impl._start = allocate(x.size());
        _impl._extent = _impl._start + x.size();
    }

    /**
     * The move constructor copies the pointers that denote the range of
     * memory occupied the vector x and then resets x. No elements are required
     * to be copied or moved.
     */
    vector_base(vector_base&& x)
        : _impl(std::forward<impl_type>(x._impl))
    { }

    /**
     * Construct the vector with a capacity for n elements, all uninitialized
     * and with the actual number of elements (size) equal to zero.
     */
    vector_base(size_type n)
        : _impl()
    {
        _impl._finish = _impl._start = allocate(n);
        _impl._extent = _impl._start + n;
    }

    ~vector_base()
    { _impl.deallocate(_impl._start, capacity()); }
    //@}

    /** @name Memory Access
     * These functions provide access to the underlying pointers in the
     * MemoryRange implemented by this class. These are generally not part of
     * the public interface of the class, but are made accessible for different
     * policies that need to operate on them.
     */
    //@{
    /** Return a pointer to the start of the memory range. */
    pointer start()
    { return _impl._start; }

    /** Set the starting pointer to p, returning the previous value. */
    pointer start(pointer p)
    { std::swap(p, _impl._start); return p; }

    /** Return a pointer past the last initialized element in the memory range. */
    pointer finish()
    { return _impl._finish; }

    /** Set the finishing pointer to p, returning the previous value. */
    pointer finish(pointer p)
    { std::swap(p, _impl._finish); return p; }

    /** Return a pointer past the allocated extent of the memory range. */
    pointer extent() { return _impl._extent; }

    /** Set the extent to p, returning the previous value. */
    pointer extent(pointer p)
    { std::swap(p, _impl._extent); return p; }
    //@}

    /** @name Size and Capacity
     * Return the current size (number of elements) or the capacity (number of
     * allowable elememnts) in the vector. The max_size() function returns the
     * largest possible size/capacity of any vector.
     *
     * @note These functions are traditionally only defined in the vector class,
     * but defining them here helps separate concerns. Specifically, the vector
     * base is no responsible for maintenance of the capacity, but not the
     * elements within it. More or less.
     */
    //@{
    /** Return the number of elements in the vector. */
    size_type size() const
    { return _impl._finish - _impl._start; }

    /** Return the maximum allowable size of the vector. */
    size_type max_size() const
    { return _impl.max_size(); }

    /** Return the current capacity of the vector. */
    size_type capacity() const
    { return _impl._extent - _impl._start; }

    /** Returns true when the number of elements has reached capacity. */
    bool full() const
    { return _impl._finish == _impl._extent; }

    /** Allocate capacity for n elements */
    void reserve(size_type n);

    /** Request up to n additional elements of capacity. */
    size_type request(size_type n) const;

    template <typename... Args> void do_insert(pointer pos, Args&&... args);
    void do_erase();
    //@}

    /** @name Get Allocator */
    //@{
    allocator_type& get_allocator() { return _impl; }
    //@}

    impl_type _impl;        ///< The underlying implementation
};

// Request n additional elements of capacity.
template <typename T, typename P>
auto vector_base<T, P>::request(size_type n) const -> size_type
{
    // Make sure we're not exceeding the max allowable size.
    if(max_size() - size() < n) {
        raise_length_error("vector::request", this->get_length_error());
    }

    // Use the grow policy to request more space for the vector.
    size_type len = this->grow_function()(*this, n);
    return (len < size() || len > max_size()) ? max_size() : len;
}

template <typename T, typename P>
void vector_base<T, P>::reserve(size_type n)
{
    // Make sure we're not exceeding the max allowable size.
    if(n > max_size()) {
        raise_length_error("vector_base::reserve", this->get_length_error());
    }

    // We're ing more memory so we need to grow the vector.
    if(capacity() < n) {
        // Grab the size prior to reallocation.
        size_type len = size();

        // Reallocate vector and move the elements in [start, finish) into
        // the new location.
        pointer tmp = allocate_and_move(n, _impl._start, _impl._finish, _impl);
        destruct(_impl._start, _impl._finish, _impl);
        _impl.deallocate(_impl._start, capacity());

        // Reset the pointer structure over the new values.
        _impl._start = tmp;
        _impl._finish = tmp + len;
        _impl._extent = tmp + n;
    }
}

// Here, args... are parameters to the construction over *pos, either default,
// copy, move, or other.
// This funtion actually combines the responsibilities of grow and shift
// because its' convenient to keep these operations together. I suppose that
// the single largest reason is that you don't want a bunch partially allocated
// and initialized memory floating around.
template <typename T, typename P>
template <typename... Args>
void vector_base<T, P>::do_insert(pointer pos, Args&&... args)
{
    // This is taken from libstdc++ and plays a little double duty here.
    // Basically, if we've called grow before we need to, we're just going
    // to construct the element in place and not do anything else.
    if(!full()) {
        // If this isn't full, just shift the elements in [pos, finish - 1)
        // right by one slot.
        // NOTE: The GCC version explicitly moves the last element before the
        // backward copy. Not sure why.
        std::move_backward(pos, _impl._finish, _impl._finish + 1);
        ++_impl._finish;
        *pos = T(std::forward<Args>(args)...);
    }
    else {
        // Note that is not really requesting only a single element. Its going to
        // request twice the size of the vector.
        size_type len = request(1);
        size_type before = pos - _impl._start;

        // Allocate new memory for
        pointer start = _impl.allocate(len);
        pointer finish = start;
        try {
            // Construct the inserted object over the args.
            _impl.construct(start + before, std::forward<Args>(args)...);

            // This moves the previous data into its new location. It's also
            // responsible for data on inserts. Note that finish use used as
            // a kind of status indicator here.
            finish = 0;
            finish = uninitialized_move(_impl._start, pos, start, _impl);
            ++finish;
            finish = uninitialized_move(pos, _impl._finish, finish, _impl);
        }
        catch(...) {
            // What failed? Where?
            if(!finish) {
                _impl.destroy(start + before);
            }
            else {
                destruct(start, finish, _impl);
                _impl.deallocate(start, len);
                throw;
            }
        }

        // Clean up the previous structures.
        destruct(_impl._start, _impl._finish, _impl);
        _impl.deallocate(_impl._start, capacity());

        // Reset the pointers
        _impl._start = start;
        _impl._finish = finish;
        _impl._extent = start + len;
    }
}

/** @internal
 * The do_erase function is responsible for the (possible) reallocation of
 * the underlying memory region when the size() has fallen below some
 * fractional threshhold of the capacity(). This delegates the operation to
 * the shrink policy.
 */
template <typename T, typename P>
void vector_base<T, P>::do_erase()
{ this->shrink_function()(*this); }

} // namespace origin

#endif