Header:
#ifndef COMMON_CONTAINERS_GRID_H
#define COMMON_CONTAINERS_GRID_H
#include "Common/Basics.h"
class cPoint;
class cRect;
namespace Common
{
typedef int Type; //TEMP for development
/*
    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.
*/
class Grid
{
public:
    Grid();
    Grid(const cRect &newBounds, const Type &value = Type()); //Calls Resize().
    ~Grid();

    //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();
    //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();

    //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;
    //True if the grid is 0 by 0 *and* its position is at (0,0).
    bool IsNull() const;

    //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 throws any exceptions thrown by element constructors.
    void Resize(const cRect &newBounds, const Type &value = Type());
    const cRect &GetBounds() const;

    //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 throws any exceptions thrown by element constructors.
    void Reserve(const cRect &newCapacity);
    //Releases all capacity that is no longer needed. This will reallocate the memory and move the elements to new addresses.
    void Conserve();

    //Returns the amount of memory held in reserve for future resizing.
    const cRect &GetCapacity() const;

    //Resizes the grid. Negative values shrink the grid.
    void Expand(int amount);
    void Expand(int horizontal, int vertical);
    void Expand(int left, int right, int top, int bottom);

    //Resizes the grid. Negative values enlarge the grid.
    void Shrink(int amount);
    void Shrink(int horizontal, int vertical);
    void Shrink(int left, int right, int top, int bottom);

    Type &At(const cPoint &pos); //Throws std::out_of_range if out of range.
    Type &operator[](const cPoint &pos); //Doesn't check for range.

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());

    //Construct a single element.
    void construct(Type &element, const Type &value = Type());
    //Constructs an element with move semantics.
    void moveConstruct(Type &element, Type &&value);
    //Destruct a single element.
    void destruct(Type &element);

    //Ensures *at least* enough room for 'bounds'.
    //If 'addExtra' is true, includes even more capacity for future growth.
    void ensureCapacity(const cRect &bounds, bool addExtra);

    //This allocates enough memory for 'capacity', without constructing any elements.
    Type *allocate(const cRect &capacity);
    //This deallocates 'memory', without calling any destructors.
    void deallocate(Type *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);
    //Called by 'reallocateMemory' only.
    void moveElements(Type *oldMemory, const cRect &oldCapacity, Type *newMemory,
                      const cRect &newCapacity, const cRect &bounds);
private:
    Type *memory;

    cRect bounds; //Current grid boundries.
    cRect capacity; //Currently allocated memory capacity, garunteed to be at least 'bounds' and maybe larger.
};
} //End of namespace.
#endif // COMMON_CONTAINERS_GRID_H[/code]



Source:
#include "Grid.h"
#include <utility> //For std::move()
#include <stdexcept> //For std::out_of_range exception.
namespace Common
{
Grid::Grid() : memory(nullptr)
{   }
Grid::Grid(const cRect &newBounds, const Type &value) : memory(nullptr)
{
    this->Resize(newBounds, value);
}
Grid::~Grid()
{
    //Clear the grid, calling the destructors on any constructed elements.
    this->Clear();

    //Deallocate any reserved memory.
    this->deallocate(this->memory);
}
//Erases the grid, resetting the bounds to (0,0,0,0).
//Does not free the reserved capacity. Call Conserve() afterward to do that.
void Grid::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 Grid::Reset()
{
    this->Clear();
    this->Conserve();
}
//True if the grid is 0 by 0 in size, *even* if its position is *not* at (0,0).
bool Grid::IsEmpty() const
{
    return this->bounds.IsEmpty();
}
//True if the grid is 0 by 0 *and* its position is at (0,0).
bool Grid::IsNull() const
{
    return this->bounds.IsNull();
}

//Resizes the grid to 'newBounds'. If Grid doesn't have enough capacity, it'll reallocate storage and move the elements to new memory addresses.
void Grid::Resize(const cRect &newBounds, const Type &value)
{
    this->ensureCapacity(newBounds, true);
    this->constructAdditions(this->bounds, newBounds, value);

    this->bounds = newBounds;
}
const cRect &Grid::GetBounds() const
{
    return this->bounds;
}

//Reserves 'rect' amount of memory, without actually resizing the grid. This will reallocate storage and move the elements to new memory addresses.
//Reserve() will not allow the grid to shrink smaller than the capacity currently is reserved to.
void Grid::Reserve(const cRect &newCapacity)
{
    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 Grid::Conserve()
{
    this->reallocateMemory(this->bounds);
}
//Returns the amount of memory held in reserve for future resizing.
const cRect &Grid::GetCapacity() const
{
    return this->capacity;
}

//Resizes the grid. Negative values shrink the grid.
void Grid::Expand(int amount)
{
    this->Expand(amount, amount, amount, amount);
}
void Grid::Expand(int horizontal, int vertical)
{
    this->Expand(horizontal, horizontal, vertical, vertical);
}
void Grid::Expand(int left, int right, int top, int bottom)
{
    cRect newBounds = this->bounds;
    newBounds.Pad(left, right, top, bottom);

    this->Resize(newBounds);
}

//Resizes the grid. Negative values enlarge the grid.
void Grid::Shrink(int amount)
{
    this->Shrink(amount, amount, amount, amount);
}
void Grid::Shrink(int horizontal, int vertical)
{
    this->Shrink(horizontal, horizontal, vertical, vertical);
}
void Grid::Shrink(int left, int right, int top, int bottom)
{
    cRect newBounds = this->bounds;
    newBounds.Pad(-left, -right, -top, -bottom);

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

        throw std::out_of_range(message);
    }

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

    return this->memory[index];
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
//XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX//
/////////////////////////////////////////////////////////////////////////////////////////////////////////
//Constructs all the new elements between oldBounds and newBounds.
//If 'newBounds' is smaller than 'oldBounds', deconstructs the old elements.
void Grid::constructAdditions(const cRect &oldBounds, const cRect &newBounds, const Type &value)
{
    //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);

    size_t constructed = 0, destructed = 0, preserved = 0, ignored = 0;

    for(cPoint point : totalArea)
    {
        if(reducedArea.Contains(point))
        {
            //Do nothing - this area is already constructed.
            preserved++;
        }
        else if(newBounds.Contains(point))
        {
            //Needs to be constructed.
            this->construct((*this)[point], value);

            constructed++;
        }
        else if(oldBounds.Contains(point))
        {
            //Needs to be destructed.
            this->destruct((*this)[point]);

            destructed++;
        }
        else
        {
            //Do nothing - this area is already destructed.

            ignored++;
        }
    }
}
//Construct a single element.
void Grid::construct(Type &element, const Type &value)
{
    new (&element) Type(value); //Call constructor.
}
//Constructs an element with move semantics.
void Grid::moveConstruct(Type &element, Type &&value)
{
    new (&element) Type(value); //Call move constructor.
}
//Destruct a single element.
void Grid::destruct(Type &element)
{
    element.~Type(); //Call destructor.
}
//Ensures *at least* enough room for 'bounds'.
void Grid::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.
        this->reallocateMemory(desiredCapacity);
    }
}
//This allocates enough memory for 'capacity', without constructing any elements.
Type *Grid::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 Grid::deallocate(Type *data)
{
    ::operator delete(data);
}
//Reallocates the memory and migrates the elements over using moveElements().
//Throws std::bad_alloc if the allocation failed.
void Grid::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.
       this->memory = this->allocate(newCapacity);
    }
    else if(newCapacity.IsEmpty())
    {
        //Free all the memory.
        this->deallocate(this->memory);

        this->memory = nullptr;
    }
    else
    {
        //Allocate the new memory.
        Type *newMemory = this->allocate(newCapacity);

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

        //Move the elements.
        this->moveElements(oldMemory, oldCapacity, newMemory, newCapacity, this->bounds);

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

        //And store the new pointer.
        this->memory = newMemory;
    }

    //Record the new capacity.
    this->capacity = newCapacity;
}
//Called by 'reallocateMemory' only.
void Grid::moveElements(Type *oldMemory, const cRect &oldCapacity,
                        Type *newMemory, const cRect &newCapacity, const cRect &bounds)
{
    //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 length of each 'row' of the grid's capacity in memory.
    size_t oldStride = oldCapacity.size.width;
    size_t newStride = newCapacity.size.width;

    //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);

    //The number of rows and columns of actual elements we need to move.
    size_t rows = bounds.size.height;
    size_t columns = bounds.size.width;

    for(size_t row = 0; row < rows; row++)
    {
        for(size_t column = 0; column < columns; column++)
        {
            size_t oldIndex = (row * oldStride) + column;
            oldIndex += oldOffset;

            size_t newIndex = (row * newStride) + column;
            newIndex += newOffset;

            //Construct the new location, and move the element.
            this->moveConstruct(newMemory[newIndex], std::move(oldMemory[oldIndex]));

            //Destruct old location.
            this->destruct(oldMemory[oldIndex]);
        }
    }
}

} //End of namespace.