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

Untitled

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