/***************************************************************************
*                                                                          *
*  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 <type_traits> //needed for std::is_pod
#include <ostream>

#ifdef GLM_IS_COMPILER_GCC
#include <cstring>
#endif

#include "glmContainersUtils.h"

namespace glm
{
    template <typename value_type>
    class PODArray
    {

    public:
        GLM_CLASS_STAT_ID( glm::MemoryStatIds::GolaemShared);

        typedef value_type* iterator;
        typedef const value_type* const_iterator;

        explicit PODArray( const MemAllocStatId memAllocStatId = getDefaultPODArrayMemoryStatId());
        explicit PODArray(size_t initialSize, const MemAllocStatId memAllocStatId = getDefaultPODArrayMemoryStatId());
        PODArray(size_t initialSize, const value_type& defaultValue, const MemAllocStatId memAllocStatId = getDefaultPODArrayMemoryStatId());
        template <class OtherIterator>
        PODArray(OtherIterator otherFirst, OtherIterator otherLast, const MemAllocStatId memAllocStatId = getDefaultPODArrayMemoryStatId());
        PODArray(size_t initialSize, const value_type* initialValues, const MemAllocStatId memAllocStatId = getDefaultPODArrayMemoryStatId()); // special constructor for String

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

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

        value_type& at(size_t i);
        const value_type& at(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.
        iterator begin();
        const_iterator begin() const;
        iterator end();
        const_iterator 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).
        // c++ 2011 style (no effect compared to 98, except no default POD value used if useless)
        void resize(size_t new_size);
        void resize(size_t new_size, const value_type& fillValue);

        inline void addOne()
        {
            resize(size() + 1);
        }

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

        /// Set allocated memory to zero
        void zeroMemory();

        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);
        void insert(iterator position, const_iterator first, const_iterator last); // not a full replacement as other iterator should be a template
        template <class OtherIterator>
        void insert(iterator position, OtherIterator otherFirst, OtherIterator otherLast);

        // first shiftAmount elements are replaced with completionValue
        void shiftForward(size_t startIndex, size_t elementCount, size_t shiftAmount, const value_type& completionValue = value_type());

        // last shiftAmount elements are replaced with completionValue
        void shiftBackward(size_t startIndex, size_t elementCount, size_t shiftAmount, const value_type& completionValue = value_type());

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

        void assign(size_t n, const value_type& val);
        void assign(size_t n, const value_type* val); // for String

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

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

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

    private:
        static inline MemAllocStatId getDefaultPODArrayMemoryStatId()
        {
            return (MemAllocStatId)glm::MemoryStatIds::GolaemShared;
        }
        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* PODArray<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 PODArray<value_type>::deallocate(value_type*& data)
    {
        GLM_FREE( data,  _memAllocStatId);
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
	inline PODArray<value_type>::PODArray(const MemAllocStatId memAllocStatId)
        : _size(0)
        , _capacity(0)
        , _data(0)
		, _memAllocStatId(memAllocStatId)
    {
        static_assert(std::is_trivial<value_type>::value && std::is_standard_layout<value_type>::value, "PODArray requires a POD type");
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
	inline PODArray<value_type>::PODArray(size_t initialSize, const MemAllocStatId memAllocStatId)
        : _size(0)
        , _capacity(0)
        , _data(0)
		, _memAllocStatId(memAllocStatId)
    {
        static_assert(std::is_pod<value_type>::value, "PODArray requires a POD type");
        resize(initialSize);
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
	inline PODArray<value_type>::PODArray(size_t initialSize, const value_type& defaultValue, const MemAllocStatId memAllocStatId)
        : _size(0)
        , _capacity(0)
        , _data(0)
		, _memAllocStatId(memAllocStatId)
    {
        static_assert(std::is_pod<value_type>::value, "PODArray requires a POD type");
        set_capacity(initialSize);
        resize(initialSize, defaultValue);
    }

    //-----------------------------------------------------------------------------
    // for string : constructor from values array
    template <typename value_type>
    inline PODArray<value_type>::PODArray(size_t initialSize, const value_type* initialValues, const MemAllocStatId memAllocStatId)
        : _size(0)
        , _capacity(0)
        , _data(0)
		, _memAllocStatId(memAllocStatId)
    {
        static_assert(std::is_pod<value_type>::value, "PODArray requires a POD type");

        if (initialSize > 0)
        {
            GLM_DEBUG_ASSERT(initialValues != NULL);

            _data = allocate(initialSize);
            _size = _capacity = initialSize;
            memcpy(_data, initialValues, sizeof(value_type) * initialSize);
        }
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    inline PODArray<value_type>::~PODArray()
    {
        if (_data != NULL)
        {
            deallocate(_data);
        }
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    PODArray<value_type>::PODArray(const PODArray<value_type>& other)
        : _size(0)
        , _capacity(0)
        , _data(0)
		, _memAllocStatId(other._memAllocStatId)
    {
        static_assert(std::is_pod<value_type>::value, "PODArray requires a POD type");
        const size_t n = other._size;
        set_capacity(n);
        if (n > 0)
        {
            memcpy(_data, other._data, sizeof(value_type) * n);
        }
        _size = n;
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    PODArray<value_type>::PODArray(const PODArray<value_type>& other, MemAllocStatId memAllocStatId)
        : _size(0)
        , _capacity(0)
        , _data(0)
		, _memAllocStatId(memAllocStatId)
    {
        static_assert(std::is_pod<value_type>::value, "PODArray requires a POD type");
        const size_t n = other._size;
        set_capacity(n);
        if (n > 0)
        {
            memcpy(_data, other._data, sizeof(value_type) * n);
        }
        _size = n;
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    template <class OtherIterator>
    PODArray<value_type>::PODArray(OtherIterator otherFirst, OtherIterator otherLast, const MemAllocStatId memAllocStatId)
        : _size(0)
        , _capacity(0)
        , _data(0)
		, _memAllocStatId(memAllocStatId)
    {
        static_assert(std::is_pod<value_type>::value, "PODArray requires a POD type");
        GLM_DEBUG_ASSERT(otherFirst <= otherLast);
        size_t elementsCount = otherLast - otherFirst;
        reserve(elementsCount);
        for (OtherIterator ite = otherFirst; ite != otherLast; ite++)
        {
            _data[_size++] = *ite;
        }
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    PODArray<value_type>& PODArray<value_type>::operator=(const PODArray<value_type>& other)
    {
        if (this != &other)
        {
            const size_t n = other._size;
            reserve(n);
            resize(n);
            if (n > 0)
            {
                memcpy(_data, other._data, sizeof(value_type) * n);
            }
        }
        return *this;
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    inline size_t PODArray<value_type>::size() const
    {
        return _size;
    }
    template <typename value_type>
    inline int PODArray<value_type>::sizeInt() const
    {
        return static_cast<int>(_size);
    }
    template <typename value_type>
    inline bool PODArray<value_type>::any() const
    {
        return _size != 0;
    }
    template <typename value_type>
    inline bool PODArray<value_type>::empty() const
    {
        return _size == 0;
    }
    template <typename value_type>
    inline value_type* PODArray<value_type>::begin()
    {
        return _data;
    }
    template <typename value_type>
    inline const value_type* PODArray<value_type>::begin() const
    {
        return _data;
    }
    template <typename value_type>
    inline value_type* PODArray<value_type>::end()
    {
        return _data + _size;
    }
    template <typename value_type>
    inline const value_type* PODArray<value_type>::end() const
    {
        return _data + _size;
    }
    template <typename value_type>
    inline value_type& PODArray<value_type>::front()
    {
        GLM_DEBUG_ASSERT(_size > 0);
        return _data[0];
    }
    template <typename value_type>
    inline const value_type& PODArray<value_type>::front() const
    {
        GLM_DEBUG_ASSERT(_size > 0);
        return _data[0];
    }
    template <typename value_type>
    inline value_type& PODArray<value_type>::back()
    {
        GLM_DEBUG_ASSERT(_size > 0);
        return _data[_size - 1];
    }
    template <typename value_type>
    inline const value_type& PODArray<value_type>::back() const
    {
        GLM_DEBUG_ASSERT(_size > 0);
        return _data[_size - 1];
    }
    template <typename value_type>
    inline void PODArray<value_type>::clear()
    {
        resize(0);
    }
    template <typename value_type>
    inline void PODArray<value_type>::zeroMemory()
    {
        memset(_data, 0, sizeof(value_type) * _capacity);
    }
    template <typename value_type>
    inline void PODArray<value_type>::trim()
    {
        set_capacity(_size);
    }
    template <typename value_type>
    inline size_t PODArray<value_type>::capacity() const
    {
        return _capacity;
    }

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

        _size = new_size;
    }

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

        for (size_t i = _size; i < new_size; i++)
        {
            _data[i] = fillValue;
        }

        _size = new_size;
    }

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

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

        if (new_capacity < _size)
            resize(new_capacity);

        value_type* new_data = 0;
        if (new_capacity > 0)
        {
            new_data = allocate(new_capacity);
            if (_size > 0)
            {
                memcpy(new_data, _data, sizeof(value_type) * _size);
            }
        }
        deallocate(_data);
        _data = new_data;
        _capacity = new_capacity;
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void PODArray<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 PODArray<value_type>::push_back(const value_type& item)
    {
        if (_size + 1 > _capacity)
            grow();
        _data[_size++] = item;
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    inline void PODArray<value_type>::pop_back()
    {
        GLM_DEBUG_ASSERT(_size > 0);
        _size--;
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    inline value_type& PODArray<value_type>::at(size_t i)
    {
        GLM_DEBUG_ASSERT(i < _size);
        return _data[i];
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    inline const value_type& PODArray<value_type>::at(size_t i) const
    {
        GLM_DEBUG_ASSERT(i < _size);
        return _data[i];
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    inline value_type& PODArray<value_type>::operator[](size_t i)
    {
        GLM_DEBUG_ASSERT(i < _size);
        return _data[i];
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    inline const value_type& PODArray<value_type>::operator[](size_t i) const
    {
        GLM_DEBUG_ASSERT(i < _size);
        return _data[i];
    }

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

        return eraseAt(index);
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    typename PODArray<value_type>::iterator PODArray<value_type>::eraseAt(size_t index)
    {
        GLM_DEBUG_ASSERT(index < _size);
        memmove(_data + index, _data + index + 1, sizeof(value_type) * (_size - index - 1)); // shift all array after index back
        _size--;

        typename PODArray<value_type>::iterator ite = _data + index;
        return ite;
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    typename PODArray<value_type>::iterator PODArray<value_type>::erase(typename PODArray<value_type>::iterator first, typename PODArray<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 _data + firstIndex;

        GLM_DEBUG_ASSERT(lastIndex <= _size);
        memmove(_data + firstIndex, _data + firstIndex + eraseSize, sizeof(value_type) * (_size - firstIndex - eraseSize)); // shift all array after index back
        _size -= eraseSize;

        return _data + firstIndex;
    }

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

    //-----------------------------------------------------------------------------
    template <typename value_type>
    typename PODArray<value_type>::iterator PODArray<value_type>::insert(typename PODArray<value_type>::iterator position, const value_type& val)
    {
        size_t index = position - _data; // will make NULL - NULL if begin == end == NULL when empty

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

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

        position = _data + index;
        memmove(position + 1, position, sizeof(value_type) * (_size - index)); // shift all array after position one step forward

        *position = val;
        _size++;

        return position;
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void PODArray<value_type>::insert(typename PODArray<value_type>::iterator position, size_t n, const value_type& val)
    {
        size_t index = position - _data; // will make NULL - NULL if begin == end == NULL when empty

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

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

        memmove(_data + index + n, _data + index, sizeof(value_type) * (_size - index)); // shift all array after position n steps forward

        for (size_t i = 0; i < n; i++)
        {
            *(_data + index + i) = val;
        }
        _size += n;
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void PODArray<value_type>::insert(typename PODArray<value_type>::iterator position, typename PODArray<value_type>::const_iterator first, typename PODArray<value_type>::const_iterator last)
    {
        size_t insertionSize = last - first;
        size_t index = position - _data; // will make NULL - NULL if begin == end == NULL when empty

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

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

        memmove(_data + index + insertionSize, _data + index, sizeof(value_type) * (_size - index)); // shift all array after position n steps forward
        memcpy(_data + index, first, sizeof(value_type) * insertionSize);
        _size += insertionSize;
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void PODArray<value_type>::shiftForward(size_t startIndex, size_t elementCount, size_t shiftAmount, const value_type& completionValue)
    {
        // debug check first, last element must not exceed current size.
        GLM_DEBUG_ASSERT(elementCount > 0);
        GLM_DEBUG_ASSERT(shiftAmount > 0);
        GLM_DEBUG_ASSERT((startIndex + elementCount + shiftAmount) <= _size);

        memmove(_data + startIndex + shiftAmount, _data + startIndex, sizeof(value_type) * (elementCount)); // shift all array after position n steps forward
        for (size_t i = startIndex; i < (startIndex + shiftAmount); ++i)
        {
            _data[i] = completionValue;
        }
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void PODArray<value_type>::shiftBackward(size_t startIndex, size_t elementCount, size_t shiftAmount, const value_type& completionValue)
    {
        // debug check first, last element must not exceed current size.
        GLM_DEBUG_ASSERT(elementCount > 0);
        GLM_DEBUG_ASSERT(shiftAmount > 0);
        GLM_DEBUG_ASSERT(startIndex >= shiftAmount);

        memmove(_data + startIndex - shiftAmount, _data + startIndex, sizeof(value_type) * (elementCount)); // shift all array after position n steps forward
        for (size_t i = startIndex + elementCount - shiftAmount; i < startIndex + elementCount; ++i)
        {
            _data[i] = completionValue;
        }
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    template <class OtherIterator>
    void PODArray<value_type>::insert(typename PODArray<value_type>::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 make NULL - NULL if begin == end == NULL when empty

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

        memmove(_data + index + insertionSize, _data + index, sizeof(value_type) * (_size - index)); // shift all array after position n steps forward
        for (size_t i = 0; i < insertionSize; i++)
        {
            new (_data + index + i) value_type(*(otherFirst));
            otherFirst++;
        }
        _size += insertionSize;
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    bool PODArray<value_type>::operator==(const PODArray<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 PODArray<value_type>::operator!=(const PODArray<value_type>& other) const
    {
        return !(operator==(other));
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void PODArray<value_type>::assign(size_t n, const value_type& val)
    {
        _size = 0;

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

        resize(n, val);
    }

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

        _size = 0;

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

        memcpy(_data, val, sizeof(value_type) * n);
        _size = n;
    }

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

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

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

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

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