Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- 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);
- }
- //================================================================
- //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(); //exception.what()
- throw;
- }
- catch(...)
- {
- Log::Message(); //Unknown exception
- 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)
- {
- 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];
- }
- //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.
- }
- //================================================================
- //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())
- {
- //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->moveElements(oldMemory, oldCapacity, newMemory.get(), newCapacity, this->bounds);
- //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' 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;
- //=================================================================
- //Incase a constructor throws an exception, keep track of the last row and column.
- size_t lastRow = 0;
- size_t lastColumn = 0;
- try
- {
- //Move-construct all the new elements.
- for(size_t row = 0; row < rows; lastRow = row++)
- {
- for(size_t column = 0; column < columns; lastColumn = 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]));
- }
- }
- }
- 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(size_t row = 0; row < lastRow; row++)
- {
- for(size_t column = 0; column < lastColumn; column++)
- {
- size_t newIndex = (row * newStride) + column;
- newIndex += newOffset;
- //Destruct the element we constructed in the previous for() loops.
- this->destruct(newMemory[newIndex]);
- }
- }
- throw;
- }
- //=================================================================
- //Destruct all the old elements.
- for(size_t row = 0; row < rows; row++)
- {
- for(size_t column = 0; column < columns; column++)
- {
- size_t oldIndex = (row * oldStride) + column;
- oldIndex += oldOffset;
- //Destruct old location.
- this->destruct(oldMemory[oldIndex]);
- }
- }
- }
- //================================================================
- private:
- Type *memory;
- 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.
- 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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement