/***************************************************************************
*                                                                          *
*  Copyright (C) Golaem S.A.  All Rights Reserved.                         *
*                                                                          *
***************************************************************************/

#pragma once

#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable : 4949)
#pragma managed(push, off)
#endif

#include "glmAssert.h"
#include "glmTypes.h"
#include "glmMemory.h"
#include "glmMemoryStats.h"

#include "glmContainersUtils.h"

#include <ostream>

namespace glm
{
    template <typename value_type>
    class Array
    {

    public:
        GLM_CLASS_STAT_ID( getDefaultArrayMemoryStatId())

        typedef value_type* iterator;
        typedef const value_type* const_iterator;
        typedef const value_type& const_reference;

        explicit Array(const MemAllocStatId memAllocStatId = getDefaultArrayMemoryStatId());
        explicit Array(size_t initialSize, const MemAllocStatId memAllocStatId = getDefaultArrayMemoryStatId());
        Array(size_t initialSize, const value_type& defaultValue, const MemAllocStatId memAllocStatId = getDefaultArrayMemoryStatId());

        template <class OtherIterator>
		Array(OtherIterator otherFirst, OtherIterator otherLast, const MemAllocStatId memAllocStatId = getDefaultArrayMemoryStatId());

        ~Array();
        Array(const Array& other);
        Array(const Array& other, const MemAllocStatId memAllocStatId);
        Array& operator=(const Array& other);

        value_type& at(size_t i);
        const value_type& at(size_t i) const;

        value_type& operator[](size_t i);
        const value_type& operator[](size_t i) const;

        /// The number of elements in the array.
        size_t size() const;
        int sizeInt() const;

        /// Returns true if there are any elements in the array.
        bool any() const;

        /// Returns true if the array is empty.
        bool empty() const;

        /// Used to iterate over the array.
        value_type* begin();
        const value_type* begin() const;
        value_type* end();
        const value_type* end() const;

        /// Returns the first/last element of the array. Don't use these on an
        /// empty array.
        value_type& front();
        const value_type& front() const;
        value_type& back();
        const value_type& back() const;

        /// Changes the size of the array (does not reallocate memory unless necessary).
        void resize(size_t new_size);
        void resize(size_t new_size, const value_type& fillValue);

        /// Removes all items in the array (does not free memory).
        void clear();

        size_t capacity() const;

        /// Reallocates the array to the specified capacity.
        void set_capacity(size_t new_capacity);

        /// Makes sure that the array has at least the specified capacity.
        /// (If not, the array is grown.)
        void reserve(size_t new_capacity);

        /// Grows the array using a geometric progression formula, so that the ammortized
        /// cost of push_back() is O(1). If a min_capacity is specified, the array will
        /// grow to at least that capacity.
        void grow(size_t min_capacity = 0);

        /// Trims the array so that its capacity matches its size.
        void trim();

        /// Pushes the item to the end of the array.
        void push_back(const value_type& item);

        /// Pops the last item from the array. The array cannot be empty.
        void pop_back();

        //void erase(size_t index);
        iterator erase(iterator iterator);
        iterator eraseAt(size_t index);
        iterator erase(iterator first, iterator last);

        void eraseIfExists(const value_type& item);

        // insert another array in this one
        iterator insert(iterator position, const value_type& val);
        void insert(iterator position, size_t n, const value_type& val);
        template <class OtherIterator>
        void insert(iterator position, OtherIterator otherFirst, OtherIterator otherLast); // not a full replacement as other iterator should be a template

        bool operator==(const Array<value_type>& other) const;
        bool operator!=(const Array<value_type>& other) const;

        // non STL standard
        void assign(size_t n, const value_type& val); // same element for all
        void assign(size_t n, const value_type* val); // each element
        void addOne();

        MemAllocStatId getMemoryStatId() const;
        void setMemoryStatId(MemAllocStatId statId);

        const_iterator find(value_type& value) const;
        iterator find(value_type& value);

        static inline MemAllocStatId getDefaultArrayMemoryStatId()
        {
            return (MemAllocStatId)glm::MemoryStatIds::GolaemShared;
        }

        friend std::ostream& operator<<(std::ostream& out, const Array<value_type>& array)
        {
            out << "[ ";
            for (size_t i = 0; i < array.size(); i++)
            {
                if (i > 0)
                {
                    out << ", ";
                }
                out << array[i];
            }
            out << " ]";
            return out;
        }

    private:
        value_type* allocate(size_t capacity);
        void deallocate(value_type*& data);

        size_t _size;
        size_t _capacity;
        value_type* _data;
        MemAllocStatId _memAllocStatId;
    };

    template <typename value_type>
    inline value_type* Array<value_type>::allocate(size_t capacity)
    {
		void* newValue = GLM_ALLOC(sizeof(value_type) * capacity, newValue, _memAllocStatId);
        return static_cast<value_type*>(newValue);
    }

    template <typename value_type>
    inline void Array<value_type>::deallocate(value_type*& data)
    {
        GLM_FREE( data,  _memAllocStatId);
    }

    template <typename value_type>
	inline Array<value_type>::Array(const MemAllocStatId memAllocStatId)
        : _size(0)
        , _capacity(0)
        , _data(0)
		, _memAllocStatId(memAllocStatId)
    {
    }

    template <typename value_type>
	inline Array<value_type>::Array(size_t initialSize, const MemAllocStatId memAllocStatId)
        : _size(0)
        , _capacity(0)
        , _data(0)
		, _memAllocStatId(memAllocStatId)
    {
        resize(initialSize);
    }

    template <typename value_type>
	inline Array<value_type>::Array(size_t initialSize, const value_type& defaultValue, const MemAllocStatId memAllocStatId)
        : _size(0)
        , _capacity(0)
        , _data(0)
		, _memAllocStatId(memAllocStatId)
    {
        set_capacity(initialSize);
        resize(initialSize, defaultValue);
    }

    template <typename value_type>
    template <class OtherIterator>
    Array<value_type>::Array(OtherIterator otherFirst, OtherIterator otherLast, const MemAllocStatId memAllocStatId)
        : _size(0)
        , _capacity(0)
        , _data(0)
		, _memAllocStatId(memAllocStatId)
    {
        GLM_DEBUG_ASSERT(otherFirst <= otherLast);
        size_t elementsCount = otherLast - otherFirst;
        reserve(elementsCount);
        for (OtherIterator ite = otherFirst; ite != otherLast; ++ite)
        {
            // call placement new on item which is not a POD
            new (_data + _size) value_type(*ite);
            _size++;
        }
    }

    template <typename value_type>
    inline Array<value_type>::~Array()
    {
        clear();

        deallocate(_data);
    }

    template <typename value_type>
    Array<value_type>::Array(const Array<value_type>& other, const MemAllocStatId memAllocStatId)
        : _size(0)
        , _capacity(0)
        , _data(0)
		, _memAllocStatId(memAllocStatId)
    {
        const size_t n = other._size;

        reserve(n); // reserve after clear, so we don't need to copy data

        // push new elements
        for (size_t i = 0; i < n; i++)
        {
            // call placement new on item which is not a POD
            new (_data + _size) value_type(*(other._data + i));
            _size++;
        }
    }

    template <typename value_type>
    Array<value_type>::Array(const Array<value_type>& other)
        : _size(0)
        , _capacity(0)
        , _data(0)
		, _memAllocStatId(other._memAllocStatId)
    {
        const size_t n = other._size;

        reserve(n); // reserve after clear, so we don't need to copy data

        // push new elements
        for (size_t i = 0; i < n; i++)
        {
            // call placement new on item which is not a POD
            new (_data + _size) value_type(*(other._data + i));
            _size++;
        }
    }

    template <typename value_type>
    Array<value_type>& Array<value_type>::operator=(const Array<value_type>& other)
    {
        if (this != &other)
        {
            const size_t n = other._size;

            if (n > _capacity)
            {
                clear();    // call destructors on current elements
                reserve(n); // reserve after clear, so we don't need to copy data
            }

            size_t keptElements = _size < n ? _size : n;

            size_t i = 0;

            // assign existing elements :
            for (; i < keptElements; i++)
            {
                *(_data + i) = *(other._data + i); // 0->n or 0->size, lowest one
            }

            // construct some new if needed
            for (; i < n; i++)
            {
                new (_data + _size) value_type(*(other._data + i)); // only if n > _size else this won't be called, keptElements loop does everything
                _size++;
            }

            // destroy remainings from old array
            for (; i < _size; i++)
            {
                (_data + i)->~value_type();
            }
            _size = n;
        }

        return *this;
    }

    template <typename value_type>
    inline size_t Array<value_type>::size() const
    {
        return _size;
    }
    template <typename value_type>
    inline int Array<value_type>::sizeInt() const
    {
        return static_cast<int>(_size);
    }
    template <typename value_type>
    inline bool Array<value_type>::any() const
    {
        return _size != 0;
    }
    template <typename value_type>
    inline bool Array<value_type>::empty() const
    {
        return _size == 0;
    }
    template <typename value_type>
    inline value_type* Array<value_type>::begin()
    {
        return _data;
    }
    template <typename value_type>
    inline const value_type* Array<value_type>::begin() const
    {
        return _data;
    }
    template <typename value_type>
    inline value_type* Array<value_type>::end()
    {
        return _data + _size;
    }
    template <typename value_type>
    inline const value_type* Array<value_type>::end() const
    {
        return _data + _size;
    }
    template <typename value_type>
    inline value_type& Array<value_type>::front()
    {
        GLM_DEBUG_ASSERT(_size > 0);
        return *_data;
    }
    template <typename value_type>
    inline const value_type& Array<value_type>::front() const
    {
        GLM_DEBUG_ASSERT(_size > 0);
        return *_data;
    }
    template <typename value_type>
    inline value_type& Array<value_type>::back()
    {
        GLM_DEBUG_ASSERT(_size > 0);
        return *(_data + _size - 1);
    }
    template <typename value_type>
    inline const value_type& Array<value_type>::back() const
    {
        GLM_DEBUG_ASSERT(_size > 0);
        return *(_data + _size - 1);
    }
    template <typename value_type>
    inline void Array<value_type>::trim()
    {
        set_capacity(_size);
    }
    template <typename value_type>
    inline size_t Array<value_type>::capacity() const
    {
        return _capacity;
    }

    template <typename value_type>
    inline void Array<value_type>::clear()
    {
        for (size_t i = 0; i < _size; i++)
        {
            // call destructor explicitly on item which is not a POD
            (_data + i)->~value_type();
        }

        _size = 0;
    }

    template <typename value_type>
    void Array<value_type>::resize(size_t new_size)
    {
        if (new_size > _capacity)
            grow(new_size);

        // call new on new elements
        for (size_t i = _size; i < new_size; i++)
        {
            new (_data + i) value_type();
        }

        // call destructor on size-exceeding elements
        for (size_t i = new_size; i < _size; i++)
        {
            (_data + i)->~value_type();
        }

        _size = new_size;
    }

    template <typename value_type>
    void Array<value_type>::resize(size_t new_size, const value_type& fillValue)
    {
        if (new_size > _capacity)
            grow(new_size);

        // call new on new items from old size to new size
        // if growing (size lesser than new_size, or it escapes immediatly
        for (size_t i = _size; i < new_size; i++)
        {
            // call placement new on item which is not a POD
            new (_data + i) value_type(fillValue);
        }

        // call destructor on erased items from old size to new size
        // if decreasing ( new_size lesser than size, or it escapes immediatly
        for (size_t i = new_size; i < _size; i++)
        {
            // call destructor explicitly on item which is not a POD
            (_data + i)->~value_type();
        }

        _size = new_size;
    }

    template <typename value_type>
    inline void Array<value_type>::reserve(size_t new_capacity)
    {
        if (new_capacity > _capacity)
            set_capacity(new_capacity);
    }

    template <typename value_type>
    void Array<value_type>::set_capacity(size_t new_capacity)
    {
        if (new_capacity == _capacity)
            return;

        if (new_capacity < _size)
        {
            // size is capped to new capacity (this will be the size used to copy elements below)
            _size = new_capacity;
        }

        value_type* new_data = 0;
        if (new_capacity > 0)
        {
            new_data = allocate(new_capacity);

            // copy-construct elements in new array, delete elements in old one :
            // this is the std vector behavior, conforming with non POD objects (memcpy is unsafe with non POD objects, such as std::map)
            for (size_t i = 0; i < _size; i++)
            {
                new (new_data + i) value_type(*(_data + i));
                (_data + i)->~value_type();
            }
        }
        deallocate(_data);
        _data = new_data;
        _capacity = new_capacity;
    }

    template <typename value_type>
    void Array<value_type>::grow(size_t min_capacity)
    {
        size_t new_capacity = _capacity * 2 + 8;
        if (new_capacity < min_capacity)
            new_capacity = min_capacity;
        set_capacity(new_capacity);
    }

    template <typename value_type>
    inline void Array<value_type>::push_back(const value_type& item)
    {
        if (_size + 1 > _capacity)
            grow();

        // call placement new on item which is not a POD
        new (_data + _size) value_type(item);

        _size++;
    }

    template <typename value_type>
    inline void Array<value_type>::pop_back()
    {
        GLM_DEBUG_ASSERT(_size > 0);

        // call destructor explicitly as it is not a POD
        (_data + _size - 1)->~value_type();

        _size--;
    }

    template <typename value_type>
    inline value_type& Array<value_type>::at(size_t i)
    {
        GLM_DEBUG_ASSERT(i < _size);
        return *(_data + i);
    }

    template <typename value_type>
    inline const value_type& Array<value_type>::at(size_t i) const
    {
        GLM_DEBUG_ASSERT(i < _size);
        return *(_data + i);
    }

    template <typename value_type>
    inline value_type& Array<value_type>::operator[](size_t i)
    {
        GLM_DEBUG_ASSERT(i < _size);
        return *(_data + i);
    }

    template <typename value_type>
    inline const value_type& Array<value_type>::operator[](size_t i) const
    {
        GLM_DEBUG_ASSERT(i < _size);
        return *(_data + i);
    }

    template <typename value_type>
    typename Array<value_type>::iterator Array<value_type>::erase(typename Array<value_type>::iterator ite)
    {
        GLM_DEBUG_ASSERT(ite != NULL);
        size_t index = ite - _data;

        return eraseAt(index);
    }

    template <typename value_type>
    typename Array<value_type>::iterator Array<value_type>::eraseAt(size_t index)
    {
        GLM_DEBUG_ASSERT(index < _size);
        // shift elements in array
        // this is the std vector behavior, conforming with non POD objects (memcpy is unsafe with non POD objects, such as std::map)
        for (size_t i = index, iEnd = _size - 1; i < iEnd; i++)
        {
            *(_data + i) = *(_data + i + 1);
        }

        // erase last item
        (_data + _size - 1)->~value_type();

        _size--;

        typename Array<value_type>::iterator ite = _data + index; // first element after erased ones
        return ite;
    }

    template <typename value_type>
    typename Array<value_type>::iterator Array<value_type>::erase(typename Array<value_type>::iterator first, typename Array<value_type>::iterator last)
    {
        size_t firstIndex = first - _data;
        size_t lastIndex = last - _data;
        size_t eraseSize = lastIndex - firstIndex;

        if (first == NULL || firstIndex >= lastIndex)
            return first;

        GLM_DEBUG_ASSERT(lastIndex <= _size);

        // shift elements in array
        // this is the std vector behavior, conforming with non POD objects (memcpy is unsafe with non POD objects, such as std::map)
        for (size_t i = firstIndex, iEnd = _size - eraseSize; i < iEnd; i++)
        {
            *(_data + i) = *(_data + i + eraseSize);
        }

        // erase last items
        for (size_t i = _size - eraseSize; i < _size; i++)
        {
            (_data + i)->~value_type();
        }

        _size -= eraseSize;

        return _data + firstIndex;
    }

    template <typename value_type>
    typename Array<value_type>::iterator Array<value_type>::insert(typename Array<value_type>::iterator position, const value_type& val)
    {
        size_t index = position - _data; // will evaluate to NULL - NULL if array is empty here

        GLM_DEBUG_ASSERT(position >= begin() && position <= end()); // test position before grow wreallocation

        if (_size + 1 > _capacity)
            grow();

        // build a new data at end to receive shifted ones, default constructed it will be copied after
        new (_data + _size) value_type();
        _size++;

        // if was not empty
        if (_size != 1)
        {
            size_t firstIndexToMove = index;
            size_t lastIndexToMove = _size - 2; // could be negative if size_ == 0

            // if current vector is empty, position may be begin/end == NULL
            // copy items to next slot
            size_t i = lastIndexToMove;
            for (; i > firstIndexToMove; i--) //firstIndexToMove could be 0
            {
                *(_data + i + 1) = *(_data + i);
            }
            // finish loop
            if (i == firstIndexToMove) // to handle properly 0 case without decreasing an unsigned value which is 0
            {
                *(_data + i + 1) = *(_data + i);
            }
        }

        // copy inserted value
        _data[index] = val;

        return (_data + index);
    }

    template <typename value_type>
    void Array<value_type>::insert(typename Array<value_type>::iterator position, size_t n, const value_type& val)
    {
        if (n == 0)
            return;

        GLM_DEBUG_ASSERT(position >= begin() && position <= end()); // test position before grow wreallocation

        size_t index = position - _data; // will evaluate to NULL - NULL if array is empty here

        if (_size + n > _capacity)
            grow(_size + n);

        // create new elements
        for (size_t i = 0; i < n; i++)
        {
            new (_data + _size + i) value_type(); // default construct
        }

        // udpate size
        _size += n;

        if (_size != n)
        {
            size_t firstIndexToMove = index;
            size_t lastIndexToMove = _size - n - 1;

            // if current vector is empty, position may be begin/end == NULL
            // copy items to next slot
            size_t i = lastIndexToMove;
            for (; i > firstIndexToMove; i--) //firstIndexToMove could be 0
            {
                *(_data + i + n) = *(_data + i);
            }
            // finish loop
            if (i == firstIndexToMove) // to handle properly 0 case without decreasing an unsigned value which is 0
            {
                *(_data + i + n) = *(_data + i);
            }
        }

        // copy new elements
        for (size_t i = 0; i < n; i++)
        {
            *(_data + index + i) = val;
        }
    }

    template <typename value_type>
    template <class OtherIterator>
    void Array<value_type>::insert(iterator position, OtherIterator otherFirst, OtherIterator otherLast)
    {
        size_t insertionSize = 0;
        OtherIterator otherFirstBis = otherFirst;
        OtherIterator otherLastBis = otherLast;
        while (otherFirstBis != otherLastBis)
        {
            ++otherFirstBis;
            ++insertionSize;
        }

        if (insertionSize == 0)
            return;

        GLM_DEBUG_ASSERT(position >= begin() && position <= end()); // test position before grow wreallocation

        size_t index = position - _data; // will evaluate to NULL - NULL if array is empty here

        if (_size + insertionSize > _capacity)
            grow(_size + insertionSize);

        // if current vector is empty, position may be begin/end == NULL
        if (_size != 0 && index != _size)
        {
            // i decremented after first entry test in for loop, range from size-1 to 0
            for (size_t i = _size; i-- > 0;)
            {
                *(_data + i + insertionSize) = *(_data + i);
            }
        }

        for (size_t i = 0; i < insertionSize; i++)
        {
            new (_data + index + i) value_type(*otherFirst);
            otherFirst++;
        }

        _size += insertionSize;
    }

    template <typename value_type>
    bool Array<value_type>::operator==(const Array<value_type>& other) const
    {
        bool result = (_size == other._size);
        if (result)
        {
            size_t i = 0;
            while (i < _size && *(_data + i) == *(other._data + i))
            {
                i++;
            }

            result = (i == _size);
        }
        return result;
    }

    template <typename value_type>
    bool Array<value_type>::operator!=(const Array<value_type>& other) const
    {
        return !(operator==(other));
    }

    template <typename value_type>
    void Array<value_type>::assign(size_t n, const value_type& val)
    {
        clear();

        // exact size :
        if (n > _capacity)
            set_capacity(n);

        resize(n, val);
    }

    template <typename value_type>
    void Array<value_type>::assign(size_t n, const value_type* val)
    {
        GLM_DEBUG_ASSERT(n == 0 || val != NULL);

        clear();

        // exact size :
        if (n > _capacity)
            set_capacity(n);

        for (size_t i = 0; i < n; i++)
        {
            // call placement new on item which is not a POD
            new (_data + _size) value_type(val[i]);
            _size++;
        }
    }

    template <typename value_type>
    void Array<value_type>::addOne()
    {
        size_t new_size = _size + 1;
        if (new_size > _capacity)
            grow(new_size);

        // call new on new elements
        new (_data + _size) value_type();

        _size = new_size;
    }

    template <typename value_type>
    void Array<value_type>::eraseIfExists(const value_type& item)
    {
        iterator foundIte = glmFind(begin(), end(), item);
        if (foundIte != end())
        {
            erase(foundIte);
        }
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    MemAllocStatId Array<value_type>::getMemoryStatId() const
    {
        return _memAllocStatId;
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void Array<value_type>::setMemoryStatId(MemAllocStatId statId)
    {
        _memAllocStatId = statId;
    }

    template <typename value_type>
    typename Array<value_type>::const_iterator Array<value_type>::find(value_type& value) const
    {
        return glmFind(begin(), end(), value);
    }

    template <typename value_type>
    typename Array<value_type>::iterator Array<value_type>::find(value_type& value)
    {
        return glmFind(begin(), end(), value);
    }
} // namespace glm

#ifdef _MSC_VER
#pragma managed(pop)
#pragma warning(pop)
#endif
