#ifndef ORIGIN_VECTOR_HPP
#define ORIGIN_VECTOR_HPP

#include <algorithm>
#include <type_traits>

#include <origin/policies.hpp>
#include <origin/memory.hpp>
#include <origin/algorithm.hpp>
#include <origin/iterators.hpp>
#include <origin/vector/policies.hpp>
#include <origin/vector/base.hpp>

namespace origin {

// NOTE: Because of the use of inheritance to specialize the vector class for
// all of these declaritive styles, constructors must be defined for each
// specialization since they are not inherited. Fortunately, they can be
// trivially designed to delegate to the base class constructor.
//
// TODO: Pending C++0x support for "inheriting constructors", the constructor
// definitions can be replaced with "using base_type::vector". This would
// restore our single point of definition for the various overloads.

// Forward declarations
template <typename, typename> struct vector_base;
template <typename> struct vector_impl;

// Default policies for the vector.
struct default_vector_policies
    : policies<
        allocator<default_allocator>,
        visitor<vector_visitor>,
        vector_::grow<>,
        vector_::shrink<>,
        bounds_error<throw_on_error>,
        length_error<throw_on_error>
    >
{ };
template <> struct is_derived_policy<default_vector_policies> : mpl::true_ { };

// A tag class for the vector container. This is used for tag dispatching and
// metafunctions on various container.
struct vector_container { };

// By default, we want to wrap these policies.
template <typename T, typename... Policies>
class vector :
    public vector<T, policies<Policies...>>
{
    typedef vector<T, policies<Policies...>> base_type;
public:
    vector() : base_type() { }
    vector(vector const& x) : base_type(x) { }
    vector(vector&& x) : base_type(std::forward<base_type>(x)) { }
    explicit vector(typename base_type::size_type n,
                    typename base_type::value_type const& x
                        = typename base_type::value_type())
        : base_type(n, x)
    { }
};

// With this specialization, Policy is either a named policy or a derived
// policy sequence. If this is a derived policy, then we want to inherit from
// the data structure with nested policies. If it's not a derived policy, then
// we inherit from the wrapped version of the unnamed policy.
template <typename T, typename Policy>
class vector<T, Policy>
    : public vector<T, typename normalize_policy<Policy>::type>
{
    typedef vector<T, typename normalize_policy<Policy>::type> base_type;
public:
    vector() : base_type() { }
    vector(vector const& x) : base_type(x) { }
    vector(vector&& x) : base_type(std::forward<base_type>(x)) { }
    explicit vector(typename base_type::size_type n,
                    typename base_type::value_type const& x
                        = typename base_type::value_type())
        : base_type(n, x)
    { }
};

// Just for convenience, if the policy is empty, derive from an empty policies
// This corresponds to the default.
template <typename T>
class vector<T>
    : public vector<T, default_vector_policies>
{
    typedef vector<T, default_vector_policies> base_type;
public:
    vector() : base_type() { }
    vector(vector const& x) : base_type(x) { }
    vector(vector&& x) : base_type(std::forward<base_type>(x)) { }
    explicit vector(typename base_type::size_type n,
                    typename base_type::value_type const& x = typename base_type::value_type())
        : base_type(n, x)
    { }
};

// This is the preferred method of declaring a data structure.
// NOTE: inheritance from base is public so that public typedefs in the base
// and policies class can be accessed via lookup. This is not meant to be a
// polymorphic relationship.
template <typename T, typename... Policies>
class vector<T, policies<Policies...>>
    : public vector_base<T, policies<Policies...>>
{
public:
    typedef policies<Policies...> policies_type;
private:
    typedef vector_base<T, policies_type> base_type;
public:
    typedef vector_container container_category;

    // Value types
    typedef T value_type;
    typedef T& reference;
    typedef T const& const_reference;

    // Allocation related types
    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;

    // Iterator types
    typedef pointer iterator;
    typedef const_pointer const_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    /** @name Constructors and Destructor */
    //@{
    /** Constructs and empty vector with a zero capacity. */
    vector()
        : base_type()
    { }

    /**
     * Construct a copy of the vector x. Only the elements in the range
     * [x.begin(), x.end()] are copied. Uninitialized elements past x.end() are
     * not copied.
     */
    vector(vector const& x)
        : base_type(x)
    {
        // NOTE: This unitilized_copy will call Alloc.construct on each element
        // in [x.begin(), x.end()). The standard function does not take an
        // allocator parameter.
        this->_impl._finish =
            uninitialized_copy(x.begin(), x.end(),begin(), base_type::get_allocator());
    }

    /**
     * Move the elements of x into this vector. Only the elements in the range
     * [x.begin(), x.end()] are moved into this vector. Uninitialized elements
     * past x.end() are not copied.
     */
    vector(vector&& x)
        : base_type(std::forward<base_type>(x))
    { }

    /**
     * Construct a vector with n elements (and capacity) prototyped on the
     * object x. If unspecified, the protype x is the default construction of
     * value_type.
     */
    explicit vector(size_type n, value_type const& x = value_type())
        : base_type(n)
    {
        // NOTE: This uninitialized_fill will call Alloc.construct for each of
        // the n adjacent addresses past the start of the vector. The standard
        // version of this function does not take an allocator.
        uninitialized_fill(begin(), n, x, base_type::get_allocator());
        this->_impl._finish = this->_impl._start + n;
    }

    ~vector()
    { destruct(begin(), end(), this->_impl); }
    //@}

    /** @name Data Accessors */
    //@{
    pointer data()
    { return this->_impl._start; }

    const_pointer data() const
    { return this->_impl._start; }
    //@}

    /** @name Random Access Accessors
     * The at functions implement checked access. Note ignoring bounds errors
     * will most likely result in segmentation faults.
     *
     * @todo Define a policy to force bounds checking on the unchecked
     * accessors.
     */
    //@{
    inline reference operator[](size_type n)
    { return *(this->_impl._start + n); }

    inline const_reference operator[](size_type n) const
    { return *(this->_impl._start + n); }

    inline reference at(size_type n)
    {
        if(n >= size()) {
            raise_bounds_error("vector::at", this->get_bounds_error());
        }
        return (*this)[n];
    }

    inline const_reference at(size_type n) const
    {
        if(n >= size()) {
            raise_bounds_error("vector::at", this->get_bounds_error());
        }
        return (*this)[n];
    }
    //@}

    /** @name Front and Back Accessors */
    //@{
    reference front()
    { return *begin(); }

    reference back()
    { return *(end() - 1); }

    const_reference front() const
    { return *begin(); }

    const_reference back() const
    { return *(end() - 1); }
    //@}

    /** @name Mutators
     * Mutating operations for the sequence of elements in the vector.
     *
     * @note The emplace operation is used to construct an object over an
     * element that has already been allocated, but (possibly) not initialized.
     * The intent is to reduce the number of copies.
     */
    //@{
    template <typename... Args> void emplace_back(Args&&... args);
    template <typename... Args> iterator emplace(iterator pos, Args&&... args);

    void push_back(value_type const& x);
    void push_back(value_type&& x);
    void pop_back();

    iterator insert(iterator pos, T const& x);
    iterator insert(iterator pos, T&& x);

    iterator erase(iterator pos);
    iterator erase(iterator first, iterator last);
    //@}

    /** @name Size and Capacity */
    //@{
    /** Returns true if the vector contains no elements. */
    bool empty() const
    { return begin() == end(); }

    using base_type::size;
    using base_type::max_size;
    using base_type::capacity;
    using base_type::reserve;
    //@}

    /** @name Policy Accessors */
    //@{
    /** Return an allocator object. */
    allocator_type get_allocator() const { return allocator_type(); }
    //@}

    /** @name Forward Container Iteration */
    //@{
    iterator begin()
    { return this->_impl._start; }

    iterator end()
    { return this->_impl._finish; }

    const_iterator begin() const
    { return this->_impl._start; }

    const_iterator end() const
    { return this->_impl._finish; }

    const_iterator cbegin() const
    { return const_iterator(this->_impl.start); }

    const_iterator cend() const
    { return const_iterator(this->_impl.finish); }
    //@}

    /** @name Backwards Container Iteration */
    //@{
    reverse_iterator rbegin()
    { return reverse_iterator(end()); }

    reverse_iterator rend()
    { return reverse_iterator(begin()); }

    const_reverse_iterator rbegin() const
    { return const_reverse_iterator(end()); }

    const_reverse_iterator rend() const
    { return const_reverse_iterator(begin()); }

    const_reverse_iterator crbegin() const
    { return const_reverse_iterator(end()); }

    const_reverse_iterator crend() const
    { return const_reverse_iterator(begin()); }
    //@}

};

template <typename T, typename... P>
void vector<T, policies<P...>>::push_back(T const& x)
{
    // If we're not full, just construct a copy of x over the next (already
    // allocated) element in our capacity. Otherwise, grow and copy.
    if(!this->full()) {
        this->_impl.construct(this->_impl._finish, x);
        ++this->_impl._finish;
    } else {
        // Extend the size of the vector and insert x afterwards.
        this->do_insert(end(), x);
    }
}

template <typename T, typename... P>
void vector<T, policies<P...>>::push_back(T&& x)
{ emplace_back(std::move(x)); }

template <typename T, typename... P>
template <typename... Args>
void vector<T, policies<P...>>::emplace_back(Args&&... args)
{
    // Just like push back, If we're not full, construct the element in place
    // with the given args. Otherwise, grow the vector first.
    if(!this->full()) {
        this->_impl.construct(this->_impl._finish, std::forward<Args>(args)...);
        ++this->_impl._finish;
    }
    else {
      do_insert(end(), std::forward<Args>(args)...);
    }
}

template <typename T, typename... P>
auto vector<T, policies<P...>>::insert(iterator pos, value_type const& x)
    -> iterator
{
    // Grab the offset for later.
    size_type n = pos - begin();

    // If we haven't reached capacity and we're inserting before the end of
    // of the vector, this is identical to a push_back.
    if(!this->full() && pos == end()) {
        this->_impl.construct(this->_impl._finish, x);
        ++this->_impl._finish;
    }
    else {
        // Otherwise, we're going to have to grow and possibly shift the
        // elements of the vector around.
        if(!this->full()) {
            // TODO: I'm not sure why I have to make a copy here.
            value_type tmp = x;
            this->do_insert(pos, std::move(tmp));
        }
        else {
            this->do_insert(pos, x);
        }
    }

    // Return an iterator the nth element past start (the one we inserted).
    return iterator(this->_impl._start + n);
}

template <typename T, typename... P>
auto vector<T, policies<P...>>::insert(iterator pos, value_type&& x) -> iterator
{ return emplace(pos, std::move(x)); }

template <typename T, typename... P>
template <typename... Args>
auto vector<T, policies<P...>>::emplace(iterator pos, Args&&... args) -> iterator
{
    size_type n = pos - begin();

    // If we're not full and emplacing at the end, this is identical to
    // empace_back. Otherwise, we just insert/shift as you'd normally expect
    if(this->full() && pos == end()) {
        this->_impl.construct(this->_impl._finish, std::forward<Args>(args)...);
        ++this->_impl._finish;
    }
    else {
        this->do_insert(pos, std::forward<Args>(args)...);
    }
    return iterator(this->_impl._start + n);
}

template <typename T, typename... P>
void vector<T, policies<P...>>::pop_back()
{
    // Shrink the last pointer and destruct the "erased" element.
    --this->_impl._finish;
    this->_impl.destroy(this->_impl._finish);
    this->do_erase();
}

template <typename T, typename... P>
auto vector<T, policies<P...>>::erase(iterator pos) -> iterator
{
    // Right shift all the elements in this range and remove the last element
    // since its no longer needed.
    if(pos + 1 != end()) {
        // NOTE: The GCC implementation just uses move and then destroys the
        // last element - which isn't the one originally pointed to by pos.
        // The rotation ensures that the targetted element is move to the end
        // of the vector prior to destruction.
        shift_left(pos, end());
    }
    --this->_impl._finish;
    this->_impl.destroy(this->_impl._finish);
    this->do_erase();

    return pos;
}

template <typename T, typename... P>
auto vector<T, policies<P...>>::erase(iterator first, iterator last) -> iterator
{
    if(last != end()) {
        // Collapse the remaining values in (last, end] onto first.
        std::move(last, end(), first);
    }

    // Destruct the remaining elements and reset the end of the vector.
    destruct(first + (end() - last), end(), this->_impl);
    this->_impl._finish = first + (end() - last);
    this->do_erase();

    return first;
}

} /* namespace origin */

#endif