#ifndef COMMON_CONTAINERS_GRID_H
#define COMMON_CONTAINERS_GRID_H

#include "Common/Basics.h"

#include <utility> //For std::move()
#include <stdexcept> //For std::out_of_range exception.

class cPoint;
class cRect;

namespace Common {

template<typename Type, typename ContainerType> class GridIterator;

/*
    A resizable 2D array container, that resizes without harming the relative location of the elements held
    by the container, and supports negative indices, like a 2D Cartesian grid.
*/
template<typename Type>
class Grid
{
public:
    typedef GridIterator<Type, Grid> iterator;
    typedef GridIterator<const Type, const Grid<Type> > const_iterator;

private:
    enum CopyMode {MoveConstructor, CopyConstructor};

public:
    Grid() : memory(nullptr)
    {   }

    //Construct and call Resize().
    Grid(const cRect &newBounds, const Type &value = Type()) : memory(nullptr)
    {
        this->Resize(newBounds, value);
    }

    ~Grid()
    {
        //Clear the grid, calling the destructors on any constructed elements.
        this->Clear();

        //Deallocate any reserved memory.
        this->deallocate(this->memory);
    }

    //Copy constructor.
    Grid(const Grid &other) : memory(nullptr)
    {
        //Note: Both Reserve() and copyElements() can throw exceptions. If they succeed properly, they will save the new state
        //to member-variables - but no member-variables should be manually altered within this function before their call.

        //Reserve enough memory.
        this->Reserve(other.capacity);

        //Copy-construct the elements.
        this->copyElements(other.memory, other.capacity, this->memory, this->capacity, other.bounds, CopyMode::CopyConstructor);

        //Save the new bounds (once we are sure copyElements() didn't throw).
        this->bounds = other.bounds;
    }

    //Move constructor.
    Grid(Grid &&other) : memory(nullptr)
    {
        this->operator=(std::forward<Grid>(other));
    }

    //Assignment operator
    Grid &operator=(const Grid &other)
    {
        Grid<Type> temp(other);
        this->Swap(temp);
        return *this;
    }

    //Move-assignment.
    Grid &operator=(Grid &&other)
    {
        this->Swap(other);
        return *this;
    }

    //Swaps the contents of this grid with 'other'.
    void Swap(Grid &other) throw()
    {
        //Swap pointers.
        std::swap(this->memory, other.memory);

        //Swap bounds and capacity.
        std::swap(this->bounds, other.bounds);
        std::swap(this->capacity, other.capacity);
    }

    //================================================================

    //Erases the grid, resetting the bounds to (0,0,0,0).
    //Does not free the reserved capacity. Call Conserve() afterward to do that.
    void Clear()
    {
        this->Resize(cRect(0,0,0,0));
    }

    //Resets the grid to (0,0,0,0) and releases the reserved memory as well.
    //This is the same as calling Clear() followed by Conserve().
    void Reset()
    {
        this->Clear();
        this->Conserve();
    }

    //================================================================

    //Returns true if the width *or* the height (or both) of the grid is 0, *even* if its position is *not* at (0,0).
    bool IsEmpty() const
    {
        return this->bounds.IsEmpty();
    }

    //True if the grid is 0 by 0 *and* its position is at (0,0).
    bool IsNull() const
    {
        return this->bounds.IsNull();
    }

    //================================================================

    //Resizes the grid to 'newBounds', constructing the new elements with 'value' (or the default constructor if 'value' is not set).
    //If Grid doesn't have enough capacity, it'll reallocate storage and move the elements to new memory addresses.
    //Throws std::bad_alloc if the allocation failed, and rethrows any exceptions thrown by element constructors or destructors.
    void Resize(const cRect &newBounds, const Type &value = Type())
    {
        try
        {
            //[CAN THROW - Make sure no member variables are changed before these function calls]
            cRect newCapacity = this->ensureCapacity(newBounds, true);

            //[CAN THROW - Make sure no member variables are changed before these function calls]
            this->constructAdditions(this->bounds, newBounds, value);

            //Record the new capacity, after we are sure no exceptions were thrown and everything succeeded.
            this->capacity = newCapacity;
        }
        catch(std::exception &exception)
        {
            Log::Message(MSG_SOURCE("Common", Log::Severity::Error)) << "std::exception caught, when resizing to:\n"
                                                                    << "newBounds = " << Log_HighlightValue(newBounds.ToString()) << "\n"
                                                                    << "exception.what() = " << Log_HighlightBad(exception.what()) << Log::FlushStream;
            throw;
        }
        catch(...)
        {
            Log::Message(MSG_SOURCE("Common", Log::Severity::Error)) << "Unknown exception caught, when resizing to:\n"
                                       << "newBounds = " << Log_HighlightValue(newBounds.ToString()) << Log::FlushStream;
            throw;
        }

        this->bounds = newBounds;
    }

    const cRect &GetBounds() const
    {
        return this->bounds;
    }

    //================================================================

    //Reserves 'newCapacity' amount of memory, without actually resizing the grid. This will reallocate the memory and move the elements to new addresses.
    //Reserve() will not allow the grid to shrink smaller than the capacity currently is reserved to.
    //Throws std::bad_alloc if the allocation failed, and rethrows any exceptions thrown by element constructors.
    void Reserve(const cRect &newCapacity)
    {
        //[CAN THROW - Make sure no member variables are changed before this function call]
        this->capacity = this->ensureCapacity(newCapacity, false);
    }

    //Releases all capacity that is no longer needed. This will reallocate the memory and move the elements to new addresses.
    void Conserve()
    {
        //[CAN THROW - Make sure no member variables are changed before this function call]
        this->reallocateMemory(this->bounds);
    }

    //Returns the amount of memory held in reserve for future resizing.
    const cRect &GetCapacity() const
    {
        return this->capacity;
    }

    //================================================================

    //Resizes the grid. Negative values shrink the grid.
    void Expand(int amount, const Type &value = Type())
    {
        this->Expand(amount, amount, amount, amount, value);
    }

    void Expand(int horizontal, int vertical, const Type &value = Type())
    {
        this->Expand(horizontal, horizontal, vertical, vertical, value);
    }

    void Expand(int left, int right, int top, int bottom, const Type &value = Type())
    {
        cRect newBounds = this->bounds;
        newBounds.Pad(left, right, top, bottom);

        this->Resize(newBounds, value);
    }

    //Resizes the grid. Negative values enlarge the grid.
    void Shrink(int amount, const Type &value = Type())
    {
        this->Shrink(amount, amount, amount, amount, value);
    }

    void Shrink(int horizontal, int vertical, const Type &value = Type())
    {
        this->Shrink(horizontal, horizontal, vertical, vertical, value);
    }

    void Shrink(int left, int right, int top, int bottom, const Type &value = Type())
    {
        cRect newBounds = this->bounds;
        newBounds.Pad(-left, -right, -top, -bottom);

        this->Resize(newBounds, value);
    }

    //================================================================

    //Throws std::out_of_range if out of range.
    Type &At(const cPoint &pos)
    {
        if(!this->bounds.Contains(pos))
        {
            std::string message = std::string("Grid::At() - 'pos' is not within range.\n")
                                + "\t'pos' = " + pos.ToString()
                                + "\n\t'bounds' = " + this->bounds.ToString();

            throw std::out_of_range(message);
        }

        return (*this)[pos];
    }

    //Doesn't check for range.
    Type &operator[](const cPoint &pos)
    {
        //Convert the point to a index into the memory.
        size_t index = this->capacity.Index(pos);

        return this->memory[index];
    }

    //Doesn't check for range. Index-based lookup for iteration (from index '0' to "this->bounds: (width * height)").
    Type &AtIndex(unsigned index)
    {
        cPoint pos = this->bounds.FromIndex(index);
        int newIndex = this->capacity.Index(std::move(pos));

        return this->memory[newIndex];
    }

    //Const version, for const_iterator.
    const Type &AtIndex(unsigned index) const
    {
        cPoint pos = this->bounds.FromIndex(index);
        int newIndex = this->capacity.Index(std::move(pos));

        return this->memory[newIndex];
    }

    //================================================================

    iterator begin()
    { return iterator(*this, 0); }
    iterator end()
    { return iterator(*this, this->bounds.Area()); }

    const_iterator begin() const
    { return const_iterator(*this, 0); }
    const_iterator end() const
    { return const_iterator(*this, this->bounds.Area()); }

    //================================================================

private:
    //Constructs all the new elements between oldBounds and newBounds setting them to 'value'.
    //If 'newBounds' is smaller than 'oldBounds', deconstructs the old elements.
    void constructAdditions(const cRect &oldBounds, const cRect &newBounds, const Type &value = Type())
    {
        //The largest extent of both rects.
        cRect totalArea = cRect::Encompassing(oldBounds, newBounds);
        //The overlapping portion of both rects (if any).
        cRect reducedArea = cRect::Intersection(oldBounds, newBounds);

        //-------------------------------------------

        //If a constructor throws an exception, we want to know which element it was,
        //so we keep track of what the last point was before the exception was thrown.
        cPoint lastPoint;

        try
        {
            for(cPoint point : newBounds)
            {
                if(reducedArea.Contains(point))
                {
                    //Do nothing - this area is already constructed.
                }
                else
                {
                    lastPoint = point;

                    //Needs to be constructed.
                    this->construct((*this)[point], value);
                }
            }
        }
        catch(...)
        {
            //Since we caught an exception, destruct every element we had previously constructed.
            for(cPoint point : newBounds)
            {
                if(reducedArea.Contains(point))
                {
                    //Do nothing - this area is already constructed.
                }
                else if(point == lastPoint)
                {
                    //Stop here - we didn't construct anything beyond this element.
                    break;
                }
                else
                {
                    //Destruct the element we previously constructed.
                    this->destruct((*this)[point]);
                }
            }

            throw;
        }

        //-------------------------------------------

        //Destruct any elements that we no longer want (if we're resizing smaller than our previous size).
        for(cPoint point : oldBounds)
        {
            if(reducedArea.Contains(point))
            {
                //Do nothing - we're preserving these elements.
            }
            else
            {
                //Needs to be destructed.
                this->destruct((*this)[point]);
            }
        }
    }

    //================================================================

    //Construct a single element.
    void construct(Type &element, const Type &value = Type())
    {
        new (&element) Type(value); //Call constructor.
    }

    //Constructs an element with move semantics.
    void moveConstruct(Type &element, Type &&value)
    {
        new (&element) Type(value); //Call move constructor.
    }

    //Destruct a single element.
    void destruct(Type &element)
    {
        element.~Type(); //Call destructor.
    }

    //Destructs multiple elements in a block of memory.
    void destructBounds(Type *memory, const cRect &capacity, const cRect &bounds)
    {
        //The initial offset of the actual bounds from the memory capacity.
        size_t offset = capacity.Index(bounds.position);

        //Destruct all the old elements.
        for(cPoint pos : bounds.size)
        {
            //Convert to position in the bound's area (from {0,0} to {width, height})
            //to the actual location in the memory capacity.
            size_t index = (pos.y * capacity.size.width) + pos.x;
            index += offset;

            //Destruct the element we constructed in the previous for() loops.
            this->destruct(memory[index]);
        }
    }

    //================================================================

    //Ensures *at least* enough room for 'bounds'. Returns the resulting capacity.
    //If 'addExtra' is true, includes even more capacity for future growth.
    cRect ensureCapacity(const cRect &bounds, bool addExtra)
    {
        //Check whether we have enough capacity to resize.
        if(!this->capacity.Contains(bounds))
        {
            cRect desiredCapacity = bounds;

            if(addExtra)
            {
                //If we're bothering to grow in size, we might as well reserve a little extra for future growth.
                int quarterWidth = (bounds.size.width / 4) + 1;
                int quarterHeight = (bounds.size.height / 4) + 1;

                desiredCapacity.Pad(quarterWidth, quarterWidth, quarterHeight, quarterHeight);
            }

            //Allocate and move the elements.
            //[CAN THROW - Make sure no member variables are changed before this function call]
            this->reallocateMemory(desiredCapacity);

            //Return the new capacity.
            return desiredCapacity;
        }

        //Return the current capacity.
        return this->capacity;
    }

    //================================================================

    //This allocates enough memory for 'capacity', without constructing any elements.
    Type *allocate(const cRect &capacity)
    {
        //Allocate the new memory.
        size_t numElements = capacity.size.Area();
        size_t numBytes = (sizeof(Type) * numElements);
        void *data = ::operator new(numBytes);

        return static_cast<Type*>(data);
    }

    //This deallocates 'memory', without calling any destructors.
    void deallocate(Type *data)
    {
        ::operator delete(data);
    }

    //================================================================

    //Reallocates the memory and migrates the elements over using moveElements().
    //Throws std::bad_alloc if the allocation failed, and throws any exceptions thrown by element constructors.
    void reallocateMemory(const cRect &newCapacity)
    {
        if(!this->memory)
        {
            //If we don't have any memory, just allocate some and don't worry about moving any elements.
            //[CAN THROW - Make sure no member variables are changed before this function call]
            this->memory = this->allocate(newCapacity);
        }
        else if(newCapacity.IsEmpty())
        {
            //Destruct all the old elements.
            this->destructBounds(this->memory, this->capacity, this->bounds);

            //Free all the memory.
            this->deallocate(this->memory);
            this->memory = nullptr;
        }
        else
        {
            //Allocate the new memory.
            //Note: I put the allocated memory into a unique_ptr here, incase moveElements() throws.
            //This way, the new memory is properly released.
            //[CAN THROW - Make sure no member variables are changed before this function call]
            std::unique_ptr<Type, use_operator_delete> newMemory(this->allocate(newCapacity));

            //A few extra variables for readability.
            Type *oldMemory = this->memory;
            const cRect &oldCapacity = this->capacity;

            //Move the elements.
            //[CAN THROW - Make sure no member variables are changed before this function call]
            this->copyElements(oldMemory, oldCapacity, newMemory.get(), newCapacity, this->bounds, CopyMode::MoveConstructor);

            //Delete the old memory.
            this->deallocate(oldMemory);

            //And store the new pointer. Have the unique_ptr release ownership of the memory as well.
            this->memory = newMemory.release();
        }

        //Record the new capacity.
        this->capacity = newCapacity;
    }

    //Called by 'reallocateMemory' and the copy-constructor.
    void copyElements(Type *oldMemory, const cRect &oldCapacity, Type *newMemory,
                      const cRect &newCapacity, const cRect &bounds, CopyMode copyMode = CopyMode::CopyConstructor)
    {
        //Insanity preservation.
        //Assert that our elements are actually within the capacity of both the new and old blocks of memory.
        BOOST_ASSERT(oldCapacity.Contains(bounds));
        BOOST_ASSERT(newCapacity.Contains(bounds));

        //Assert that neither block of memory's size is empty (they have to have a positive non-zero width and height).
        BOOST_ASSERT(!oldCapacity.IsEmpty());
        BOOST_ASSERT(!newCapacity.IsEmpty());

        //Assert that neither pointer to the allocated memory is empty.
        BOOST_ASSERT(oldMemory != nullptr);
        BOOST_ASSERT(newMemory != nullptr);

        //=================================================================

        //The initial offset of the actual bounds from the memory capacity.
        size_t oldOffset = oldCapacity.Index(bounds.position);
        size_t newOffset = newCapacity.Index(bounds.position);

        //Incase a constructor throws an exception, keep track of the last position we successfully constructed.
        cPoint lastPos;

        try
        {
            //Move-construct all the new elements.
            for(cPoint pos : bounds.size)
            {
                lastPos = pos;

                //Convert to position in the bound's area (from {0,0} to {width, height})
                //to the actual location in the memory capacity.
                size_t oldIndex = (pos.y * oldCapacity.size.width) + pos.x;
                oldIndex += oldOffset;

                size_t newIndex = (pos.y * newCapacity.size.width) + pos.x;
                newIndex += newOffset;

                //Construct the new location.
                if(copyMode == CopyMode::MoveConstructor)
                {
                    //Move-constructor.
                    this->moveConstruct(newMemory[newIndex], std::move(oldMemory[oldIndex]));
                }
                else
                {
                    //Copy-constructor.
                    this->construct(newMemory[newIndex], oldMemory[oldIndex]);
                }
            }
        }
        catch(...)
        {
            //Since we just caught an exception thrown from one of the element move-constructors,
            //destruct all the new elements we just constructed, up until the failed constructor.
            for(cPoint pos : bounds.size)
            {
                if(pos == lastPos)
                    break;

                //Convert to position in the bound's area (from {0,0} to {width, height})
                //to the actual location in the memory capacity.
                size_t newIndex = (pos.y * newCapacity.size.width) + pos.x;
                newIndex += newOffset;

                //Destruct the element we constructed in the previous for() loops.
                this->destruct(newMemory[newIndex]);
            }

            throw;
        }

        //Destruct all the old elements, unless we are copying and not moving.
        if(copyMode == CopyMode::MoveConstructor)
        {
            this->destructBounds(oldMemory, oldCapacity, bounds);
        }
    }

    //================================================================

private:
    Type *memory;

    cRect bounds; //Current grid boundaries.
    cRect capacity; //Currently allocated memory capacity, guaranteed to be at least 'bounds' and maybe larger.
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX//
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

/*
    A random-access iterator for iterating over each element of a Common::Grid.

    I'm doing a trick here, by taking the type of the container as a second template parameter.
    This allows me to do this:
        typedef GridIterator<const Type, const Grid<Type> > const_iterator;

    ...instead of having to create two seperate iterator classes (one for regular iterator and one for const).
*/
template <typename Type, typename ContainerType = typename Common::Grid<Type> >
class GridIterator
{
public:
    GridIterator(ContainerType &grid, unsigned index) : grid(grid), index(index)
    {
        this->maxIndex = this->grid.GetBounds().Area();
    }

    //================================================================

    //De-reference.
    Type &operator*()
    {
        return this->grid.AtIndex(this->index);
    }
    Type &operator->()
    {
        return (operator*());
    }

    //================================================================

    //Comparison.
    bool operator==(const GridIterator &other) const
    {
        return (&this->grid == &other.grid) && (this->index == other.index);
    }

    bool operator!=(const GridIterator &other) const
    {
        return !operator==(other);
    }

    //================================================================

    //Increment/decrement.
    GridIterator &operator++()
    {
        this->index++;
        Limit(this->index, this->maxIndex);
        return *this;
    }

    GridIterator operator++(int)
    {
        GridIterator temp(*this);
        ++(*this);
        return temp;
    }

    GridIterator &operator--()
    {
        this->index--;
        return *this;
    }

    GridIterator operator--(int)
    {
        GridIterator temp(*this);
        --(*this);
        return temp;
    }

    //================================================================

    //Random access.
    GridIterator operator+(int n) const
    {
        GridIterator temp(*this);
        temp.index += n;
        return temp;
    }

    GridIterator &operator+=(int n)
    {
        this->index += n;
        Limit(this->index, this->maxIndex);
        return *this;
    }

    GridIterator operator-(int n) const
    {
        GridIterator temp(*this);
        temp.index -= n;
        return temp;
    }

    GridIterator &operator-=(int n)
    {
        this->index -= n;
        return *this;
    }

    //================================================================

private:
    ContainerType &grid;

    unsigned index; //The current index.
    unsigned maxIndex; //The maximum value (and the result returned by 'std::end()'.
};

//================================================================

} //End of namespace.

#endif // COMMON_CONTAINERS_GRID_H