#ifndef _STL_VECTOR_HPP_
#define _STL_VECTOR_HPP_

#include <stl/algorithm.hpp>
#include <stl/allocator.hpp>
#include <stl/iterator.hpp>
#include <stl/memory.hpp>

namespace stl
{
    /*
	 * class base_vector
	 * Base class for the vector container. All memory allocation and
	 * deallocation is performed in this class.
	 * */
	template <
		class ValueTy,
		class AllocatorTy>
	class base_vector : public traits<ValueTy, ValueTy*>
	{
	private:
		typedef base_vector<ValueTy,AllocatorTy> this_type;
		const size_type __mMaxSize;
	public:
		typedef AllocatorTy allocator_type;
	protected:
		allocator_type _mAllocator;
		pointer_type   _mBegin;
		pointer_type   _mEnd;
		pointer_type   _mCapacity;

		void _do_assign(const size_type, const_reference_type);
		pointer_type _do_create_copy();
        void _do_destroy_values(pointer_type, pointer_type);
		void _do_reallocate(const size_type);
		void _do_remove(const size_type, const size_type);
		void _do_resize(const size_type);
	public:
		base_vector();
		~base_vector();

		bool empty() const;
		size_type capacity() const;
		size_type size() const;
		size_type max_size() const;

        allocator_type get_allocator() const;
	};

	/*
	 * Constructor
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	base_vector<ValueTy, AllocatorTy>::base_vector()
		: __mMaxSize(stl::npos / this_type::base_size),
		  _mBegin(NULL),
		  _mEnd(NULL),
		  _mCapacity(NULL)
	{}

    /*
	 * Destructor
	 * */
	template <class ValueTy, class AllocatorTy>
	base_vector<ValueTy, AllocatorTy>::~base_vector()
	{
		const size_type currentSize = this->size();
		for (size_type i = 0; i < currentSize; ++i) {
			_mAllocator.destroy(_mBegin+i);
		}
		_mAllocator.deallocate(_mBegin);
	}

	/*
	 * _do_assign() returns nothing
	 * Input:
	     * size_type             The index of the element to assign to.
	     * const_reference_type  The value to assign.
	 * */
	template <class ValueTy, class AllocatorTy>
	void
	base_vector<ValueTy, AllocatorTy>::_do_assign(const size_type index, const_reference_type val)
	{
		if (index >= this->size()) {
			this->_do_resize(index+1);
		}
		_mBegin[index] = val;
	}

	/*
	 * _do_create_copy() returns pointer_type
	 * Input:
	     * nothing
	 *
	 * Creates a full copy of the data allocated by the vector.
	 * Returns a pointer to said copy. Will return NULL if vector is empty.
	 * */
	template <class ValueTy, class AllocatorTy>
	typename base_vector<ValueTy, AllocatorTy>::pointer_type
	base_vector<ValueTy, AllocatorTy>::_do_create_copy()
	{
		const size_type len = this->size();
		pointer_type result = NULL;

		if (len > 0)
		{
			result = _mAllocator.allocate(len);
			memcpy(result, _mBegin, len * this_type::base_size);
		}

		return result;
	}

    template <class ValueTy, class AllocatorTy>
	typename base_vector<ValueTy, AllocatorTy>::pointer_type
	base_vector<ValueTy, AllocatorTy>::_do_destroy_values(pointer_type first, pointer_type last)
	{
        for (; first != last; ++first) {
            first->~value_type();
        }
    }

	template <class ValueTy, class AllocatorTy>
	void
	base_vector<ValueTy, AllocatorTy>::_do_reallocate(const size_type newDesiredCapacity)
	{
		if (newDesiredCapacity > this->capacity())
		{
			size_type newCapacity = 1;
			while (newCapacity < newDesiredCapacity) {
				newCapacity *= 2;
			}
			const size_type previousSize = this->size();
			pointer_type backup = _do_create_copy();

			_mAllocator.deallocate(_mBegin);
			_mBegin = _mAllocator.allocate(newCapacity);
			_mEnd = _mBegin + previousSize;
			_mCapacity = _mBegin + newCapacity;

			if (backup != NULL)
			{
				memcpy(_mBegin, backup, previousSize * this_type::base_size);
				_mAllocator.deallocate(backup);
			}
		}
	}

	template <class ValueTy, class AllocatorTy>
	void
	base_vector<ValueTy, AllocatorTy>::_do_remove(const size_type start, const size_type len)
	{
		if (start != stl::npos)
		{
			pointer_type ptr = (_mBegin + start);
			pointer_type ptrEnd = (ptr + len);

			if (ptrEnd <= _mEnd)
			{
				while (ptr != ptrEnd) {
					_mAllocator.destroy(ptr++);
				}
				_mEnd -= len;

				if (ptrEnd != _mEnd) {
					memmove((_mBegin+start), ptrEnd, len * this_type::base_size);
				}
			}
		}
	}

	template <class ValueTy, class AllocatorTy>
	inline void
	base_vector<ValueTy, AllocatorTy>::_do_resize(const size_type newSize)
	{
		this->_do_reallocate(newSize);
		_mEnd = (_mBegin + newSize);
	}

	/*
	 * empty() returns bool
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	inline bool
	base_vector<ValueTy, AllocatorTy>::empty() const
	{
		return (_mBegin == _mEnd);
	}

	/*
	 * capacity() returns size_type
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	inline typename base_vector<ValueTy, AllocatorTy>::size_type
	base_vector<ValueTy, AllocatorTy>::capacity() const
	{
		return (_mCapacity - _mBegin);
	}

	/*
	 * size() returns size_type
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	inline typename base_vector<ValueTy, AllocatorTy>::size_type
	base_vector<ValueTy, AllocatorTy>::size() const
	{
		return (_mEnd - _mBegin);
	}

	/*
	 * max_size() returns size_type
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	inline typename base_vector<ValueTy, AllocatorTy>::size_type
	base_vector<ValueTy, AllocatorTy>::max_size() const
	{
		return __mMaxSize;
	}

	/*
	 * class vector
	 * 
	 * */
	template <
		class ValueTy,
		class AllocatorTy=allocator<ValueTy>>
	class vector : public base_vector<ValueTy, AllocatorTy>
	{
	private:
		typedef vector<ValueTy,AllocatorTy>           this_type;
		typedef base_vector<ValueTy,AllocatorTy>      base_type;
	public:
		typedef pointer_type                          iterator;
		typedef const_pointer_type                    const_iterator;
		typedef stl::reverse_iterator<iterator>       reverse_iterator;
		typedef stl::reverse_iterator<const_iterator> const_reverse_iterator;

		vector();
		vector(const size_type);
		vector(const size_type, const_reference_type);

		reference_type          operator [] (const size_type);
		const_reference_type    operator [] (const size_type) const;

		reference_type          at(const size_type);
		const_reference_type    at(const size_type) const;

        reference_type          front();
        reference_type          back();
        const_reference_type    front() const;
        const_reference_type    back() const;

		iterator                begin();
		iterator                end();
		const_iterator          begin() const;
		const_iterator          end() const;

		reverse_iterator        rbegin();
		reverse_iterator        rend();
		const_reverse_iterator  rbegin() const;
		const_reverse_iterator  rend() const;

		void                    push_back(const_reference_type);
		void                    pop_back();

		void                    reserve(const size_type);
		void                    resize(const size_type);
		void                    resize(const size_type, const_reference_type);

        void                    assign(iterator, iterator);
        void                    assign(size_type, const_reference_type);
		iterator                erase(iterator);
		iterator                erase(iterator, iterator);
		iterator                insert(iterator, const_reference_type);
		void                    insert(iterator, size_type, const_reference_type);
		template <class InputIteratorTy>
		void                    insert(iterator, InputIteratorTy, InputIteratorTy);

		void                    clear();
		void                    swap(this_type&);
	};

	/*
	 * operator [] returns reference_type
	 * Input:
	     * size_type  The index position of the element to return.
	 * */
	template <class Ty, class AllocatorTy>
	inline typename vector<Ty, AllocatorTy>::reference_type
	vector<Ty, AllocatorTy>::operator [] (const size_type index)
	{
		return _mBegin[index];
	}

	/*
	 * operator [] returns const_reference_type
	 * Input:
	     * size_type  The index position of the element to return.
	 * */
	template <class Ty, class AllocatorTy>
	inline typename vector<Ty, AllocatorTy>::const_reference_type
	vector<Ty, AllocatorTy>::operator [] (const size_type index) const
	{
		return _mBegin[index];
	}

	/*
	 * Constructor
	 * */
	template <class ValueTy, class AllocatorTy>
	vector<ValueTy, AllocatorTy>::vector()
	{
		/* Intentionally left blank. */
	}

	/*
	 * Constructor
	 * */
	template <class ValueTy, class AllocatorTy>
	vector<ValueTy, AllocatorTy>::vector(const size_type num)
	{
		this->resize(num, value_type());
	}

	/*
	 * Constructor
	 * */
	template <class ValueTy, class AllocatorTy>
	vector<ValueTy, AllocatorTy>::vector(const size_type num, const_reference_type val)
	{
		this->resize(num, val);
	}

	/*
	 * at() returns reference_type
	 * Input:
	     * size_type  The index of the element to return.
	 * */
	template <class ValueTy, class AllocatorTy>
	inline typename vector<ValueTy, AllocatorTy>::reference_type
	vector<ValueTy, AllocatorTy>::at(const size_type index)
	{
		return _mBegin[index];
	}

	/*
	 * at() const returns const_reference_type
	 * Input:
	     * size_type  The index of the element to return.
	 * */
	template <class ValueTy, class AllocatorTy>
	inline typename vector<ValueTy, AllocatorTy>::const_reference_type
	vector<ValueTy, AllocatorTy>::at(const size_type index) const
	{
		return _mBegin[index];
	}

    /*
	 * front() returns reference_type
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	inline typename vector<ValueTy, AllocatorTy>::reference_type
	vector<ValueTy, AllocatorTy>::front()
	{
		return *_mBegin;
	}

    /*
	 * back() returns reference_type
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	inline typename vector<ValueTy, AllocatorTy>::reference_type
	vector<ValueTy, AllocatorTy>::back()
	{
		return *_mEnd;
	}

    /*
	 * front() const returns const_reference_type
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	inline typename vector<ValueTy, AllocatorTy>::const_reference_type
	vector<ValueTy, AllocatorTy>::front() const
	{
		return *_mBegin;
	}

    /*
	 * back() const returns const_reference_type
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	inline typename vector<ValueTy, AllocatorTy>::const_reference_type
	vector<ValueTy, AllocatorTy>::back() const
	{
		return *_mEnd;
	}

	/*
	 * begin() returns iterator
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	inline typename vector<ValueTy, AllocatorTy>::iterator
	vector<ValueTy, AllocatorTy>::begin()
	{
		return iterator(_mBegin);
	}

	/*
	 * end() returns iterator
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	inline typename vector<ValueTy, AllocatorTy>::iterator
	vector<ValueTy, AllocatorTy>::end()
	{
		return iterator(_mEnd);
	}

	/*
	 * begin() const returns iterator
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	inline typename vector<ValueTy, AllocatorTy>::const_iterator
	vector<ValueTy, AllocatorTy>::begin() const
	{
		return const_iterator(_mBegin);
	}

	/*
	 * end() const returns iterator
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	inline typename vector<ValueTy, AllocatorTy>::const_iterator
	vector<ValueTy, AllocatorTy>::end() const
	{
		return const_iterator(_mEnd);
	}

    template <class ValueTy, class AllocatorTy>
	inline typename vector<ValueTy, AllocatorTy>::reverse_iterator
	vector<ValueTy, AllocatorTy>::rbegin()
	{
		return reverse_iterator(_mEnd);
	}

    template <class ValueTy, class AllocatorTy>
	inline typename vector<ValueTy, AllocatorTy>::reverse_iterator
	vector<ValueTy, AllocatorTy>::rend()
	{
		return reverse_iterator(_mBegin);
	}

    template <class ValueTy, class AllocatorTy>
	inline typename vector<ValueTy, AllocatorTy>::const_reverse_iterator
	vector<ValueTy, AllocatorTy>::rbegin() const
	{
		return const_reverse_iterator(_mEnd);
	}

    template <class ValueTy, class AllocatorTy>
	inline typename vector<ValueTy, AllocatorTy>::const_reverse_iterator
	vector<ValueTy, AllocatorTy>::rend() const
	{
		return const_reverse_iterator(_mBegin);
	}

	/*
	 * push_back() returns nothing
	 * Input:
	     * const_reference_type  The value to push.
	 *
	 * Pushes the passed value onto the end of the vector.
	 * */
	template <class ValueTy, class AllocatorTy>
	inline void
	vector<ValueTy, AllocatorTy>::push_back(const_reference_type val)
	{
		this->_do_assign(this->size(), val);
	}

	/*
	 * pop_back() returns nothing
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	inline void
	vector<ValueTy, AllocatorTy>::pop_back()
	{
		this->_do_remove(this->size()-1, 1);
	}

	/*
	 * reserve() returns nothing
	 * Input:
	     * size_type  The new capacity.
	 *
	 * This function is a public alias for basic_vector::_do_reallocate.
	 * */
	template <class ValueTy, class AllocatorTy>
	inline void
	vector<ValueTy, AllocatorTy>::reserve(const size_type newCapacity)
	{
		this->_do_reallocate(newCapacity);
	}

	/*
	 * resize() returns nothing
	 * Input:
	     * size_type  The new size.
	 * */
	template <class ValueTy, class AllocatorTy>
	inline void
	vector<ValueTy, AllocatorTy>::resize(const size_type newSize)
	{
        if (newSize > this->size()) {
		    this->_do_resize(newSize);
        } else {
            this->erase(_mBegin + newSize, _mEnd);
        }
	}

	/*
	 * resize() returns nothing
	 * Input:
	     * size_type             The new size.
	     * const_reference_type  The value to assign the each element.
	 * */
	template <class ValueTy, class AllocatorTy>
	void
	vector<ValueTy, AllocatorTy>::resize(const size_type newSize, const_reference_type val)
	{
		this->_do_resize(newSize);
		for (iterator itr = begin(); itr != end(); ++itr) {
			*itr = val;
		}
	}

    /*
	 * assign() returns nothing
	 * Input:
	     * size_type             The number of elements to assign.
	     * const_reference_type  The value to assign the each element.
	 * */
    template <class ValueTy, class AllocatorTy>
    void
    vector<ValueTy, AllocatorTy>::assign(size_type n, const_reference_type source)
    {
        if (n > this->size()) {
            this->resize(n, source);
        } else {
            while (n-- > 0) {
                _mBegin[n] = source;
            }
        }
    }

    /*
	 * erase() returns iterator
	 * Input:
	     * iterator  The position of the element to be removed.
	 *
	 * Removes the element at the position defined by the passed iterator.
	 * The returned iterator will be equal to the element one past the
	 * element defined by the passed iterator.
	 * For example:
	     * vector<int> vec(3);
	     * vec[0]=1; vec[1]=2; vec[2]=3;
         * 
         * int n = *(vec.erase(vec.begin()+1)); // 3
	 * */
    template <class ValueTy, class AllocatorTy>
    typename vector<ValueTy, AllocatorTy>::iterator
    vector<ValueTy, AllocatorTy>::erase(iterator itr)
    {
        iterator result = this->end();

        if (this->empty() == false)
        {
            if (this->size() > 1)
            {
                result = &*itr;
                memmove(&*itr, &*itr+1, (this->size()-(&*itr-_mBegin)) * sizeof value_type);
            }

            --_mEnd;
        }

        return result;
    }

    template <class ValueTy, class AllocatorTy>
    typename vector<ValueTy, AllocatorTy>::iterator
    vector<ValueTy, AllocatorTy>::erase(iterator first, iterator last)
    {
        iterator result = this->end();

        if (this->empty() == false)
        {
            const difference_type len = (&*last - &*first);

            if (len == 0)
            {
                result = this->erase(first);
                --_mEnd;
            }
            else
            {
                result = &*last;
                _mEnd -= len;
                memmove(&*first, &*last+1, (this->size()-len) * sizeof value_type);
            }
        }

        return result;
    }

	/*
	 * clear() returns nothing
	 * Input:
	     * nothing
	 * */
	template <class ValueTy, class AllocatorTy>
	inline void
	vector<ValueTy, AllocatorTy>::clear()
	{
        _do_destroy_values(_mBegin, _mEnd);
		_mEnd = _mBegin;
	}

	/*
	 * swap() returns nothing
	 * Input:
	     * this_type&  A reference to the vector to swap with.
	 * */
	template <class ValueTy, class AllocatorTy>
	inline void
	vector<ValueTy, AllocatorTy>::swap(this_type& source)
	{
		memswap(this, &source, sizeof this_type);
	}
}

#endif