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

#pragma once

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

#include "glmContainersUtils.h"
#include "glmArray.h"

// this File declares an array of Lists. The advantage of this container is to pre-allocate its list nodes, shared on all lists

namespace glm
{
    //-----------------------------------------------------------------------------
    template <typename value_type>
    class ArrayOfList
    {

    public:
        typedef glm::ArrayOfList<value_type> ThisArrayOfList;

        //-----------------------------------------------------------------------------
        class ArrayOfListNode
        {
        public:
            GLM_CLASS_STAT_ID( ThisArrayOfList::getDefaultArrayMemoryStatId())

            value_type _data;
            int _prev; // index in buffer, allows reallocation of buffer
            int _next; // index in buffer, allows reallocation of buffer

            ArrayOfListNode(const value_type& d = value_type(), int p = -1, int n = -1)
                : _data(d)
                , _prev(p)
                , _next(n)
            {
            }
        };

        GLM_CLASS_STAT_ID( getDefaultArrayMemoryStatId())

        ArrayOfList(size_t initialArraySize = 0, size_t initialNodeBufferCapacity = 0, const MemAllocStatId memAllocStatId = getDefaultArrayMemoryStatId());
        ~ArrayOfList();

        void addListInArray();
        void resizeArray(size_t newSize);
        size_t arraySize();
        void clearArray();

        void reserveElements(size_t elementsCount);
        void addListElement(size_t listIndex, value_type value);
        void removeListElement(size_t listIndex, size_t entryIndex);
        size_t listSize(size_t listIndex);
        const value_type& getListElement(size_t listIndex, size_t entryIndex);
        void clearList(size_t listIndex);

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

    private:
        int getFreeNodeIndex();
        void recycleFreeNode(int index);

        PODArray<int> _firstIndices;
        PODArray<int> _lastIndices;
        PODArray<size_t> _sizes;
        Array<ArrayOfListNode> _nodesBuffer;
        int _firstFreeNode; // free nodes are chained from this with _next 'links'

        MemAllocStatId _memAllocStatId;
    };

    //-----------------------------------------------------------------------------
    template <typename value_type>
    int ArrayOfList<value_type>::getFreeNodeIndex()
    {
        if (_firstFreeNode != -1)
        {
            int returnedFreeNode = _firstFreeNode;
            _firstFreeNode = _nodesBuffer[_firstFreeNode]._next;
            return returnedFreeNode;
        }
        else
        {
            // allocate new ones :
            _nodesBuffer.addOne(); //  let nodesBuffer grow
            return (_nodesBuffer.sizeInt() - 1);
        }
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void ArrayOfList<value_type>::recycleFreeNode(int index)
    {
        GLM_DEBUG_ASSERT(index != -1);
        int nextFreeNode = _firstFreeNode;
        _firstFreeNode = index;
        _nodesBuffer[_firstFreeNode]._next = nextFreeNode;
        //_nodesBuffer[_firstFreeNode]._prev = -1; // not used
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    ArrayOfList<value_type>::ArrayOfList(size_t initialArraySize, size_t initialNodeBufferCapacity, const MemAllocStatId memAllocStatId)
        : _firstIndices(memAllocStatId)
        , _lastIndices(memAllocStatId)
        , _sizes(memAllocStatId)
        , _nodesBuffer(memAllocStatId)
		, _memAllocStatId(memAllocStatId)
    {
        _firstIndices.resize(initialArraySize, -1);
        _lastIndices.resize(initialArraySize, -1);
        _sizes.resize(initialArraySize, 0);
        // resize array to given size, every index is -1 (empty) :
        _nodesBuffer.reserve(initialNodeBufferCapacity);
        _firstFreeNode = -1;
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    ArrayOfList<value_type>::~ArrayOfList()
    {
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void ArrayOfList<value_type>::addListInArray()
    {
        _firstIndices.resize(_firstIndices.size() + 1, -1);
        _lastIndices.resize(_lastIndices.size() + 1, -1);
        _sizes.resize(_sizes.size() + 1, 0);
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void ArrayOfList<value_type>::resizeArray(size_t newSize)
    {
        if (newSize < _firstIndices.size())
        {
            // must recycle items :
            for (size_t iList = newSize; iList < _firstIndices.size(); iList++)
            {
                clearList(iList);
            }
        }
        _firstIndices.resize(newSize, -1);
        _lastIndices.resize(newSize, -1);
        _sizes.resize(newSize, 0);
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    size_t ArrayOfList<value_type>::arraySize()
    {
        return _firstIndices.size();
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void ArrayOfList<value_type>::clearArray()
    {
        _firstIndices.clear();
        _lastIndices.clear();
        _sizes.clear();
        _nodesBuffer.clear();
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void ArrayOfList<value_type>::reserveElements(size_t elementsCount)
    {
        _nodesBuffer.reserve(elementsCount);
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void ArrayOfList<value_type>::addListElement(size_t listIndex, value_type value)
    {
        GLM_DEBUG_ASSERT(listIndex < _firstIndices.size());

        int newEntryIndex = getFreeNodeIndex();
        ArrayOfListNode& newEntry = _nodesBuffer[newEntryIndex];
        newEntry._data = value;
        newEntry._next = -1;

        if (_firstIndices[listIndex] == -1)
        {
            _firstIndices[listIndex] = newEntryIndex;
            _lastIndices[listIndex] = newEntryIndex;
            ++(_sizes[listIndex]);

            newEntry._prev = -1;
        }
        else
        {
            _nodesBuffer[_lastIndices[listIndex]]._next = newEntryIndex;
            newEntry._prev = _lastIndices[listIndex];
            _lastIndices[listIndex] = newEntryIndex;
            ++(_sizes[listIndex]);
        }
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void ArrayOfList<value_type>::removeListElement(size_t listIndex, size_t entryIndex)
    {
        GLM_DEBUG_ASSERT(listIndex < _firstIndices.size());
        GLM_DEBUG_ASSERT(entryIndex < _sizes[listIndex]);

        int bufferIndex = _firstIndices[listIndex];

        size_t currentEntryIndex = 0;
        while (currentEntryIndex < entryIndex)
        {
            bufferIndex = _nodesBuffer[bufferIndex]._next;
            currentEntryIndex++;
        }

        int prevIndex = _nodesBuffer[bufferIndex]._prev;
        if (prevIndex != -1)
            _nodesBuffer[prevIndex]._next = _nodesBuffer[bufferIndex]._next;
        else
            _firstIndices[listIndex] = _nodesBuffer[bufferIndex]._next;

        int nextIndex = _nodesBuffer[bufferIndex]._next;
        if (nextIndex != -1)
        {
            _nodesBuffer[nextIndex]._prev = _nodesBuffer[bufferIndex]._prev;
        }
        else
            _lastIndices[listIndex] = _nodesBuffer[bufferIndex]._prev;

        --(_sizes[listIndex]);

        // recycle node now :
        recycleFreeNode(bufferIndex);
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    size_t ArrayOfList<value_type>::listSize(size_t listIndex)
    {
        GLM_DEBUG_ASSERT(listIndex < _sizes.size());
        return _sizes[listIndex];
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    const value_type& ArrayOfList<value_type>::getListElement(size_t listIndex, size_t entryIndex)
    {
        GLM_DEBUG_ASSERT(listIndex < _sizes.size());
        GLM_DEBUG_ASSERT(entryIndex < _sizes[listIndex]);

        int bufferIndex = _firstIndices[listIndex];

        size_t currentEntryIndex = 0;
        while (currentEntryIndex < entryIndex)
        {
            bufferIndex = _nodesBuffer[bufferIndex]._next;
            currentEntryIndex++;
        }

        return _nodesBuffer[bufferIndex]._data;
    }

    //-----------------------------------------------------------------------------
    template <typename value_type>
    void ArrayOfList<value_type>::clearList(size_t listIndex)
    {
        GLM_DEBUG_ASSERT(listIndex < _sizes.size());

        int bufferIndex = _firstIndices[listIndex];
        int nextBufferIndex;

        while (bufferIndex != -1)
        {
            nextBufferIndex = _nodesBuffer[bufferIndex]._next;
            recycleFreeNode(bufferIndex);
            bufferIndex = nextBufferIndex;
        }

        _firstIndices[listIndex] = -1;
        _lastIndices[listIndex] = -1;
        _sizes[listIndex] = 0;
    }
} // namespace glm
