#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<class Type> 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> iterator;
public:
Grid() : memory(nullptr), boundsOffset(0)
{ }
//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);
}
//================================================================
//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 throws any exceptions thrown by element constructors.
void Resize(const cRect &newBounds, const Type &value = Type())
{
this->ensureCapacity(newBounds, true);
this->constructAdditions(this->bounds, newBounds, value);
this->bounds = newBounds;
this->boundsOffset = this->capacity.Index(this->bounds.position);
}
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 throws any exceptions thrown by element constructors.
void 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 Conserve()
{
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)
{
this->Expand(amount, amount, amount, amount);
}
void Expand(int horizontal, int vertical)
{
this->Expand(horizontal, horizontal, vertical, vertical);
}
void 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 Shrink(int amount)
{
this->Shrink(amount, amount, amount, amount);
}
void Shrink(int horizontal, int vertical)
{
this->Shrink(horizontal, horizontal, vertical, vertical);
}
void 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 &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];
}
//================================================================
iterator begin()
{ return iterator(*this, 0); }
iterator end()
{ return 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);
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 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.
}
//================================================================
//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)
{
//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 *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.
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 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]);
}
}
}
//================================================================
private:
Type *memory;
unsigned int boundsOffset; //The offset of 'bounds' within 'capacity'. Only used for AtIndex, for faster iteration.
cRect bounds; //Current grid boundries.
cRect capacity; //Currently allocated memory capacity, garunteed to be at least 'bounds' and maybe larger.
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX//
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//A random-access iterator for iterating over each element of a Common::Grid.
template <typename Type>
class GridIterator
{
public:
GridIterator(Common::Grid<Type> &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)
{
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)
{
GridIterator temp(*this);
temp.index -= n;
return temp;
}
GridIterator &operator-=(int n)
{
this->index -= n;
return *this;
}
//================================================================
private:
Common::Grid<Type> &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