Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

2D resizable negative-positions Grid container

By: JaminGrey on Nov 5th, 2012  |  syntax: C++  |  size: 16.61 KB  |  views: 33  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #ifndef COMMON_CONTAINERS_GRID_H
  2. #define COMMON_CONTAINERS_GRID_H
  3.  
  4. #include "Common/Basics.h"
  5.  
  6. #include <utility> //For std::move()
  7. #include <stdexcept> //For std::out_of_range exception.
  8.  
  9. class cPoint;
  10. class cRect;
  11.  
  12. namespace Common {
  13.  
  14. template<class Type> class GridIterator;
  15.  
  16. /*
  17.     A resizable 2D array container, that resizes without harming the relative location of the elements held
  18.     by the container, and supports negative indices, like a 2D Cartesian grid.
  19. */
  20. template<typename Type>
  21. class Grid
  22. {
  23. public:
  24.     typedef GridIterator<Type> iterator;
  25.    
  26. public:
  27.     Grid() : memory(nullptr), boundsOffset(0)
  28.     {   }
  29.    
  30.     //Construct and call Resize().
  31.     Grid(const cRect &newBounds, const Type &value = Type()) : memory(nullptr)
  32.     {
  33.         this->Resize(newBounds, value);
  34.     }
  35.    
  36.     ~Grid()
  37.     {
  38.         //Clear the grid, calling the destructors on any constructed elements.
  39.         this->Clear();
  40.        
  41.         //Deallocate any reserved memory.
  42.         this->deallocate(this->memory);
  43.     }
  44.    
  45.     //================================================================
  46.    
  47.     //Erases the grid, resetting the bounds to (0,0,0,0).
  48.     //Does not free the reserved capacity. Call Conserve() afterward to do that.
  49.     void Clear()
  50.     {
  51.         this->Resize(cRect(0,0,0,0));
  52.     }
  53.    
  54.     //Resets the grid to (0,0,0,0) and releases the reserved memory as well.
  55.     //This is the same as calling Clear() followed by Conserve().
  56.     void Reset()
  57.     {
  58.         this->Clear();
  59.         this->Conserve();
  60.     }
  61.    
  62.     //================================================================
  63.    
  64.     //Returns true if the width *or* the height (or both) of the grid is 0, *even* if its position is *not* at (0,0).
  65.     bool IsEmpty() const
  66.     {
  67.         return this->bounds.IsEmpty();
  68.     }
  69.    
  70.     //True if the grid is 0 by 0 *and* its position is at (0,0).
  71.     bool IsNull() const
  72.     {
  73.         return this->bounds.IsNull();
  74.     }
  75.    
  76.     //================================================================
  77.    
  78.     //Resizes the grid to 'newBounds', constructing the new elements with 'value' (or the default constructor if 'value' is not set).
  79.     //If Grid doesn't have enough capacity, it'll reallocate storage and move the elements to new memory addresses.
  80.     //Throws std::bad_alloc if the allocation failed, and throws any exceptions thrown by element constructors.
  81.     void Resize(const cRect &newBounds, const Type &value = Type())
  82.     {
  83.         this->ensureCapacity(newBounds, true);
  84.         this->constructAdditions(this->bounds, newBounds, value);
  85.        
  86.         this->bounds = newBounds;
  87.         this->boundsOffset = this->capacity.Index(this->bounds.position);
  88.     }
  89.  
  90.     const cRect &GetBounds() const
  91.     {
  92.         return this->bounds;
  93.     }
  94.    
  95.     //================================================================
  96.    
  97.     //Reserves 'newCapacity' amount of memory, without actually resizing the grid. This will reallocate the memory and move the elements to new addresses.
  98.     //Reserve() will not allow the grid to shrink smaller than the capacity currently is reserved to.
  99.     //Throws std::bad_alloc if the allocation failed, and throws any exceptions thrown by element constructors.
  100.     void Reserve(const cRect &newCapacity)
  101.     {
  102.         this->ensureCapacity(newCapacity, false);
  103.     }
  104.    
  105.     //Releases all capacity that is no longer needed. This will reallocate the memory and move the elements to new addresses.
  106.     void Conserve()
  107.     {
  108.         this->reallocateMemory(this->bounds);
  109.     }
  110.    
  111.     //Returns the amount of memory held in reserve for future resizing.
  112.     const cRect &GetCapacity() const
  113.     {
  114.         return this->capacity;
  115.     }
  116.    
  117.     //================================================================
  118.    
  119.     //Resizes the grid. Negative values shrink the grid.
  120.     void Expand(int amount)
  121.     {
  122.         this->Expand(amount, amount, amount, amount);
  123.     }
  124.    
  125.     void Expand(int horizontal, int vertical)
  126.     {
  127.         this->Expand(horizontal, horizontal, vertical, vertical);
  128.     }
  129.    
  130.     void Expand(int left, int right, int top, int bottom)
  131.     {
  132.         cRect newBounds = this->bounds;
  133.         newBounds.Pad(left, right, top, bottom);
  134.        
  135.         this->Resize(newBounds);
  136.     }
  137.    
  138.     //Resizes the grid. Negative values enlarge the grid.
  139.     void Shrink(int amount)
  140.     {
  141.         this->Shrink(amount, amount, amount, amount);
  142.     }
  143.    
  144.     void Shrink(int horizontal, int vertical)
  145.     {
  146.         this->Shrink(horizontal, horizontal, vertical, vertical);
  147.     }
  148.    
  149.     void Shrink(int left, int right, int top, int bottom)
  150.     {
  151.         cRect newBounds = this->bounds;
  152.         newBounds.Pad(-left, -right, -top, -bottom);
  153.        
  154.         this->Resize(newBounds);
  155.     }
  156.    
  157.     //================================================================
  158.    
  159.     //Throws std::out_of_range if out of range.
  160.     Type &At(const cPoint &pos)
  161.     {
  162.         if(!this->bounds.Contains(pos))
  163.         {
  164.             std::string message = std::string("Grid::At() - 'pos' is not within range.\n")
  165.                                 + "\t'pos' = " + pos.ToString()
  166.                                 + "\n\t'bounds' = " + this->bounds.ToString();
  167.            
  168.             throw std::out_of_range(message);
  169.         }
  170.        
  171.         return (*this)[pos];
  172.     }
  173.  
  174.     //Doesn't check for range.
  175.     Type &operator[](const cPoint &pos)
  176.     {
  177.         //Convert the point to a index into the memory.
  178.         size_t index = this->capacity.Index(pos);
  179.        
  180.         return this->memory[index];
  181.     }
  182.  
  183.     //Doesn't check for range. Index-based lookup for iteration (from index '0' to "this->bounds: (width * height)").
  184.     Type &AtIndex(unsigned index)
  185.     {
  186.         cPoint pos = this->bounds.FromIndex(index);
  187.         int newIndex = this->capacity.Index(std::move(pos));
  188.        
  189.         return this->memory[newIndex];
  190.     }
  191.    
  192.     //================================================================
  193.    
  194.     iterator begin()
  195.     { return iterator(*this, 0); }
  196.    
  197.     iterator end()
  198.     { return iterator(*this, this->bounds.Area()); }
  199.    
  200.     //================================================================
  201.    
  202. private:
  203.     //Constructs all the new elements between oldBounds and newBounds setting them to 'value'.
  204.     //If 'newBounds' is smaller than 'oldBounds', deconstructs the old elements.
  205.     void constructAdditions(const cRect &oldBounds, const cRect &newBounds, const Type &value = Type())
  206.     {
  207.         //The largest extent of both rects.
  208.         cRect totalArea = cRect::Encompassing(oldBounds, newBounds);
  209.         //The overlapping portion of both rects (if any).
  210.         cRect reducedArea = cRect::Intersection(oldBounds, newBounds);
  211.        
  212.         size_t constructed = 0, destructed = 0, preserved = 0, ignored = 0;
  213.        
  214.         for(cPoint point : totalArea)
  215.         {
  216.             if(reducedArea.Contains(point))
  217.             {
  218.                 //Do nothing - this area is already constructed.
  219.                 preserved++;
  220.             }
  221.             else if(newBounds.Contains(point))
  222.             {
  223.                 //Needs to be constructed.
  224.                 this->construct((*this)[point], value);
  225.                
  226.                 constructed++;
  227.             }
  228.             else if(oldBounds.Contains(point))
  229.             {
  230.                 //Needs to be destructed.
  231.                 this->destruct((*this)[point]);
  232.                
  233.                 destructed++;
  234.             }
  235.             else
  236.             {
  237.                 //Do nothing - this area is already destructed.
  238.                
  239.                 ignored++;
  240.             }
  241.         }
  242.     }
  243.    
  244.     //================================================================
  245.    
  246.     //Construct a single element.
  247.     void construct(Type &element, const Type &value = Type())
  248.     {
  249.         new (&element) Type(value); //Call constructor.
  250.     }
  251.    
  252.     //Constructs an element with move semantics.
  253.     void moveConstruct(Type &element, Type &&value)
  254.     {
  255.         new (&element) Type(value); //Call move constructor.
  256.     }
  257.  
  258.     //Destruct a single element.
  259.     void destruct(Type &element)
  260.     {
  261.         element.~Type(); //Call destructor.
  262.     }
  263.    
  264.     //================================================================
  265.    
  266.     //Ensures *at least* enough room for 'bounds'.
  267.     //If 'addExtra' is true, includes even more capacity for future growth.
  268.     void ensureCapacity(const cRect &bounds, bool addExtra)
  269.     {
  270.         //Check whether we have enough capacity to resize.
  271.         if(!this->capacity.Contains(bounds))
  272.         {
  273.             cRect desiredCapacity = bounds;
  274.            
  275.             if(addExtra)
  276.             {
  277.                 //If we're bothering to grow in size, we might as well reserve a little extra for future growth.
  278.                 int quarterWidth = (bounds.size.width / 4) + 1;
  279.                 int quarterHeight = (bounds.size.height / 4) + 1;
  280.                
  281.                 desiredCapacity.Pad(quarterWidth, quarterWidth, quarterHeight, quarterHeight);
  282.             }
  283.            
  284.             //Allocate and move the elements.
  285.             this->reallocateMemory(desiredCapacity);
  286.         }
  287.     }    
  288.    
  289.     //================================================================
  290.    
  291.     //This allocates enough memory for 'capacity', without constructing any elements.
  292.     Type *allocate(const cRect &capacity)
  293.     {
  294.         //Allocate the new memory.
  295.         size_t numElements = capacity.size.Area();
  296.         size_t numBytes = (sizeof(Type) * numElements);
  297.         void *data = ::operator new(numBytes);
  298.        
  299.         return static_cast<Type*>(data);
  300.     }
  301.    
  302.     //This deallocates 'memory', without calling any destructors.
  303.     void deallocate(Type *data)
  304.     {
  305.         ::operator delete(data);
  306.     }
  307.    
  308.     //================================================================
  309.    
  310.     //Reallocates the memory and migrates the elements over using moveElements().
  311.     //Throws std::bad_alloc if the allocation failed, and throws any exceptions thrown by element constructors.
  312.     void reallocateMemory(const cRect &newCapacity)
  313.     {
  314.         if(!this->memory)
  315.         {
  316.             //If we don't have any memory, just allocate some and don't worry about moving any elements.
  317.            this->memory = this->allocate(newCapacity);
  318.         }
  319.         else if(newCapacity.IsEmpty())
  320.         {
  321.             //Free all the memory.
  322.             this->deallocate(this->memory);
  323.            
  324.             this->memory = nullptr;
  325.         }
  326.         else
  327.         {
  328.             //Allocate the new memory.
  329.             Type *newMemory = this->allocate(newCapacity);
  330.            
  331.             //A few extra variables for readability.
  332.             Type *oldMemory = this->memory;
  333.             const cRect &oldCapacity = this->capacity;
  334.            
  335.             //Move the elements.
  336.             this->moveElements(oldMemory, oldCapacity, newMemory, newCapacity, this->bounds);
  337.            
  338.             //Delete the old memory.
  339.             this->deallocate(oldMemory);
  340.             oldMemory = nullptr;
  341.            
  342.             //And store the new pointer.
  343.             this->memory = newMemory;
  344.         }
  345.        
  346.         //Record the new capacity.
  347.         this->capacity = newCapacity;
  348.     }
  349.    
  350.     //Called by 'reallocateMemory' only.
  351.     void moveElements(Type *oldMemory, const cRect &oldCapacity, Type *newMemory,
  352.                       const cRect &newCapacity, const cRect &bounds)
  353.     {
  354.         //Insanity preservation.
  355.         //Assert that our elements are actually within the capacity of both the new and old blocks of memory.
  356.         BOOST_ASSERT(oldCapacity.Contains(bounds));
  357.         BOOST_ASSERT(newCapacity.Contains(bounds));
  358.        
  359.         //Assert that neither block of memory's size is empty (they have to have a positive non-zero width and height).
  360.         BOOST_ASSERT(!oldCapacity.IsEmpty());
  361.         BOOST_ASSERT(!newCapacity.IsEmpty());
  362.        
  363.         //Assert that neither pointer to the allocated memory is empty.
  364.         BOOST_ASSERT(oldMemory != nullptr);
  365.         BOOST_ASSERT(newMemory != nullptr);
  366.        
  367.         //The length of each 'row' of the grid's capacity in memory.
  368.         size_t oldStride = oldCapacity.size.width;
  369.         size_t newStride = newCapacity.size.width;
  370.        
  371.         //The initial offset of the actual bounds from the memory capacity.
  372.         size_t oldOffset = oldCapacity.Index(bounds.position);
  373.         size_t newOffset = newCapacity.Index(bounds.position);
  374.        
  375.         //The number of rows and columns of actual elements we need to move.
  376.         size_t rows = bounds.size.height;
  377.         size_t columns = bounds.size.width;
  378.        
  379.         for(size_t row = 0; row < rows; row++)
  380.         {
  381.             for(size_t column = 0; column < columns; column++)
  382.             {
  383.                 size_t oldIndex = (row * oldStride) + column;
  384.                 oldIndex += oldOffset;
  385.                
  386.                 size_t newIndex = (row * newStride) + column;
  387.                 newIndex += newOffset;
  388.                
  389.                 //Construct the new location, and move the element.
  390.                 this->moveConstruct(newMemory[newIndex], std::move(oldMemory[oldIndex]));
  391.                
  392.                 //Destruct old location.
  393.                 this->destruct(oldMemory[oldIndex]);
  394.             }
  395.         }
  396.     }
  397.  
  398.     //================================================================
  399.    
  400. private:
  401.     Type *memory;
  402.     unsigned int boundsOffset; //The offset of 'bounds' within 'capacity'. Only used for AtIndex, for faster iteration.
  403.    
  404.     cRect bounds; //Current grid boundries.
  405.     cRect capacity; //Currently allocated memory capacity, garunteed to be at least 'bounds' and maybe larger.
  406. };
  407.  
  408. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////
  409. //XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX//
  410. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////
  411.  
  412. //A random-access iterator for iterating over each element of a Common::Grid.
  413. template <typename Type>
  414. class GridIterator
  415. {
  416. public:
  417.     GridIterator(Common::Grid<Type> &grid, unsigned index) : grid(grid), index(index)
  418.     {
  419.         this->maxIndex = this->grid.GetBounds().Area();
  420.     }
  421.    
  422.     //================================================================
  423.    
  424.     //De-reference.
  425.     Type &operator*()
  426.     {
  427.         return this->grid.AtIndex(this->index);
  428.     }
  429.    
  430.     Type &operator->()
  431.     {
  432.         return (operator*());
  433.     }
  434.    
  435.     //================================================================
  436.    
  437.     //Comparison.
  438.     bool operator==(const GridIterator &other) const
  439.     {
  440.         return (&this->grid == &other.grid) && (this->index == other.index);
  441.     }
  442.    
  443.     bool operator!=(const GridIterator &other) const
  444.     {
  445.         return !operator==(other);
  446.     }
  447.    
  448.     //================================================================
  449.    
  450.     //Increment/decrement.
  451.     GridIterator &operator++()
  452.     {
  453.         this->index++;
  454.         Limit(this->index, this->maxIndex);
  455.         return *this;
  456.     }
  457.    
  458.     GridIterator operator++(int)
  459.     {
  460.         GridIterator temp(*this);
  461.         ++(*this);
  462.         return temp;
  463.     }
  464.    
  465.     GridIterator &operator--()
  466.     {
  467.         this->index--;
  468.         return *this;
  469.     }
  470.    
  471.     GridIterator operator--(int)
  472.     {
  473.         GridIterator temp(*this);
  474.         --(*this);
  475.         return temp;
  476.     }
  477.    
  478.     //================================================================
  479.  
  480.     //Random access.
  481.     GridIterator operator+(int n)
  482.     {
  483.         GridIterator temp(*this);
  484.         temp.index += n;
  485.         return temp;
  486.     }
  487.    
  488.     GridIterator &operator+=(int n)
  489.     {
  490.         this->index += n;
  491.         Limit(this->index, this->maxIndex);
  492.         return *this;
  493.     }
  494.    
  495.     GridIterator operator-(int n)
  496.     {
  497.         GridIterator temp(*this);
  498.         temp.index -= n;
  499.         return temp;
  500.     }
  501.    
  502.     GridIterator &operator-=(int n)
  503.     {
  504.         this->index -= n;
  505.         return *this;
  506.     }
  507.    
  508.     //================================================================
  509.    
  510. private:
  511.     Common::Grid<Type> &grid;
  512.     unsigned index; //The current index.
  513.     unsigned maxIndex; //The maximum value (and the result returned by 'std::end()'.
  514. };
  515.  
  516. //================================================================
  517.  
  518. } //End of namespace.
  519.  
  520. #endif // COMMON_CONTAINERS_GRID_H