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: JaminGrey on Nov 6th, 2012  |  syntax: C++  |  size: 21.65 KB  |  views: 37  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. 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<typename Type, typename ContainerType> 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, Grid> iterator;
  25.     typedef GridIterator<const Type, const Grid<Type> > const_iterator;
  26.    
  27. public:
  28.     Grid() : memory(nullptr)
  29.     {   }
  30.    
  31.     //Construct and call Resize().
  32.     Grid(const cRect &newBounds, const Type &value = Type()) : memory(nullptr)
  33.     {
  34.         this->Resize(newBounds, value);
  35.     }
  36.    
  37.     ~Grid()
  38.     {
  39.         //Clear the grid, calling the destructors on any constructed elements.
  40.         this->Clear();
  41.        
  42.         //Deallocate any reserved memory.
  43.         this->deallocate(this->memory);
  44.     }
  45.    
  46.     //================================================================
  47.    
  48.     //Erases the grid, resetting the bounds to (0,0,0,0).
  49.     //Does not free the reserved capacity. Call Conserve() afterward to do that.
  50.     void Clear()
  51.     {
  52.         this->Resize(cRect(0,0,0,0));
  53.     }
  54.    
  55.     //Resets the grid to (0,0,0,0) and releases the reserved memory as well.
  56.     //This is the same as calling Clear() followed by Conserve().
  57.     void Reset()
  58.     {
  59.         this->Clear();
  60.         this->Conserve();
  61.     }
  62.    
  63.     //================================================================
  64.    
  65.     //Returns true if the width *or* the height (or both) of the grid is 0, *even* if its position is *not* at (0,0).
  66.     bool IsEmpty() const
  67.     {
  68.         return this->bounds.IsEmpty();
  69.     }
  70.    
  71.     //True if the grid is 0 by 0 *and* its position is at (0,0).
  72.     bool IsNull() const
  73.     {
  74.         return this->bounds.IsNull();
  75.     }
  76.    
  77.     //================================================================
  78.    
  79.     //Resizes the grid to 'newBounds', constructing the new elements with 'value' (or the default constructor if 'value' is not set).
  80.     //If Grid doesn't have enough capacity, it'll reallocate storage and move the elements to new memory addresses.
  81.     //Throws std::bad_alloc if the allocation failed, and rethrows any exceptions thrown by element constructors or destructors.
  82.     void Resize(const cRect &newBounds, const Type &value = Type())
  83.     {
  84.         try
  85.         {
  86.             //[CAN THROW - Make sure no member variables are changed before these function calls]
  87.             cRect newCapacity = this->ensureCapacity(newBounds, true);
  88.            
  89.             //[CAN THROW - Make sure no member variables are changed before these function calls]
  90.             this->constructAdditions(this->bounds, newBounds, value);
  91.            
  92.             //Record the new capacity, after we are sure no exceptions were thrown and everything succeeded.
  93.             this->capacity = newCapacity;
  94.         }
  95.         catch(std::exception &exception)
  96.         {
  97.             Log::Message(); //exception.what()
  98.             throw;
  99.         }
  100.         catch(...)
  101.         {
  102.             Log::Message(); //Unknown exception
  103.             throw;
  104.         }
  105.  
  106.         this->bounds = newBounds;
  107.     }
  108.  
  109.     const cRect &GetBounds() const
  110.     {
  111.         return this->bounds;
  112.     }
  113.    
  114.     //================================================================
  115.    
  116.     //Reserves 'newCapacity' amount of memory, without actually resizing the grid. This will reallocate the memory and move the elements to new addresses.
  117.     //Reserve() will not allow the grid to shrink smaller than the capacity currently is reserved to.
  118.     //Throws std::bad_alloc if the allocation failed, and rethrows any exceptions thrown by element constructors.
  119.     void Reserve(const cRect &newCapacity)
  120.     {
  121.         //[CAN THROW - Make sure no member variables are changed before this function call]
  122.         this->capacity = this->ensureCapacity(newCapacity, false);
  123.     }
  124.    
  125.     //Releases all capacity that is no longer needed. This will reallocate the memory and move the elements to new addresses.
  126.     void Conserve()
  127.     {
  128.         //[CAN THROW - Make sure no member variables are changed before this function call]
  129.         this->reallocateMemory(this->bounds);
  130.     }
  131.    
  132.     //Returns the amount of memory held in reserve for future resizing.
  133.     const cRect &GetCapacity() const
  134.     {
  135.         return this->capacity;
  136.     }
  137.    
  138.     //================================================================
  139.    
  140.     //Resizes the grid. Negative values shrink the grid.
  141.     void Expand(int amount)
  142.     {
  143.         this->Expand(amount, amount, amount, amount);
  144.     }
  145.    
  146.     void Expand(int horizontal, int vertical)
  147.     {
  148.         this->Expand(horizontal, horizontal, vertical, vertical);
  149.     }
  150.    
  151.     void Expand(int left, int right, int top, int bottom)
  152.     {
  153.         cRect newBounds = this->bounds;
  154.         newBounds.Pad(left, right, top, bottom);
  155.        
  156.         this->Resize(newBounds);
  157.     }
  158.    
  159.     //Resizes the grid. Negative values enlarge the grid.
  160.     void Shrink(int amount)
  161.     {
  162.         this->Shrink(amount, amount, amount, amount);
  163.     }
  164.    
  165.     void Shrink(int horizontal, int vertical)
  166.     {
  167.         this->Shrink(horizontal, horizontal, vertical, vertical);
  168.     }
  169.    
  170.     void Shrink(int left, int right, int top, int bottom)
  171.     {
  172.         cRect newBounds = this->bounds;
  173.         newBounds.Pad(-left, -right, -top, -bottom);
  174.        
  175.         this->Resize(newBounds);
  176.     }
  177.    
  178.     //================================================================
  179.    
  180.     //Throws std::out_of_range if out of range.
  181.     Type &At(const cPoint &pos)
  182.     {
  183.         if(!this->bounds.Contains(pos))
  184.         {
  185.             std::string message = std::string("Grid::At() - 'pos' is not within range.\n")
  186.                                 + "\t'pos' = " + pos.ToString()
  187.                                 + "\n\t'bounds' = " + this->bounds.ToString();
  188.            
  189.             throw std::out_of_range(message);
  190.         }
  191.        
  192.         return (*this)[pos];
  193.     }
  194.  
  195.     //Doesn't check for range.
  196.     Type &operator[](const cPoint &pos)
  197.     {
  198.         //Convert the point to a index into the memory.
  199.         size_t index = this->capacity.Index(pos);
  200.        
  201.         return this->memory[index];
  202.     }
  203.  
  204.     //Doesn't check for range. Index-based lookup for iteration (from index '0' to "this->bounds: (width * height)").
  205.     Type &AtIndex(unsigned index)
  206.     {
  207.         cPoint pos = this->bounds.FromIndex(index);
  208.         int newIndex = this->capacity.Index(std::move(pos));
  209.        
  210.         return this->memory[newIndex];
  211.     }
  212.    
  213.     //Const version, for const_iterator.
  214.     const Type &AtIndex(unsigned index) const
  215.     {
  216.         cPoint pos = this->bounds.FromIndex(index);
  217.         int newIndex = this->capacity.Index(std::move(pos));
  218.        
  219.         return this->memory[newIndex];
  220.     }
  221.    
  222.     //================================================================
  223.    
  224.     iterator begin()
  225.     { return iterator(*this, 0); }
  226.     iterator end()
  227.     { return iterator(*this, this->bounds.Area()); }
  228.    
  229.     const_iterator begin() const
  230.     { return const_iterator(*this, 0); }
  231.     const_iterator end() const
  232.     { return const_iterator(*this, this->bounds.Area()); }
  233.    
  234.     //================================================================
  235.    
  236. private:
  237.     //Constructs all the new elements between oldBounds and newBounds setting them to 'value'.
  238.     //If 'newBounds' is smaller than 'oldBounds', deconstructs the old elements.
  239.     void constructAdditions(const cRect &oldBounds, const cRect &newBounds, const Type &value = Type())
  240.     {
  241.         //The largest extent of both rects.
  242.         cRect totalArea = cRect::Encompassing(oldBounds, newBounds);
  243.         //The overlapping portion of both rects (if any).
  244.         cRect reducedArea = cRect::Intersection(oldBounds, newBounds);
  245.        
  246.         //-------------------------------------------
  247.        
  248.         //If a constructor throws an exception, we want to know which element it was,
  249.         //so we keep track of what the last point was before the exception was thrown.
  250.         cPoint lastPoint;
  251.        
  252.         try
  253.         {
  254.             for(cPoint point : newBounds)
  255.             {
  256.                 if(reducedArea.Contains(point))
  257.                 {
  258.                     //Do nothing - this area is already constructed.
  259.                 }
  260.                 else
  261.                 {
  262.                     lastPoint = point;
  263.                    
  264.                     //Needs to be constructed.
  265.                     this->construct((*this)[point], value);
  266.                 }
  267.             }
  268.         }
  269.         catch(...)
  270.         {
  271.             //Since we caught an exception, destruct every element we had previously constructed.
  272.             for(cPoint point : newBounds)
  273.             {
  274.                 if(reducedArea.Contains(point))
  275.                 {
  276.                     //Do nothing - this area is already constructed.
  277.                 }
  278.                 else if(point == lastPoint)
  279.                 {
  280.                     //Stop here - we didn't construct anything beyond this element.
  281.                     break;
  282.                 }
  283.                 else
  284.                 {
  285.                     //Destruct the element we previously constructed.
  286.                     this->destruct((*this)[point]);
  287.                 }
  288.             }
  289.            
  290.             throw;
  291.         }
  292.        
  293.         //-------------------------------------------
  294.        
  295.         //Destruct any elements that we no longer want (if we're resizing smaller than our previous size).
  296.         for(cPoint point : oldBounds)
  297.         {
  298.             if(reducedArea.Contains(point))
  299.             {
  300.                 //Do nothing - we're preserving these elements.
  301.             }
  302.             else
  303.             {
  304.                 //Needs to be destructed.
  305.                 this->destruct((*this)[point]);
  306.             }
  307.         }
  308.     }
  309.    
  310.     //================================================================
  311.    
  312.     //Construct a single element.
  313.     void construct(Type &element, const Type &value = Type())
  314.     {
  315.         new (&element) Type(value); //Call constructor.
  316.     }
  317.    
  318.     //Constructs an element with move semantics.
  319.     void moveConstruct(Type &element, Type &&value)
  320.     {
  321.         new (&element) Type(value); //Call move constructor.
  322.     }
  323.  
  324.     //Destruct a single element.
  325.     void destruct(Type &element)
  326.     {
  327.         element.~Type(); //Call destructor.
  328.     }
  329.    
  330.     //================================================================
  331.    
  332.     //Ensures *at least* enough room for 'bounds'. Returns the resulting capacity.
  333.     //If 'addExtra' is true, includes even more capacity for future growth.
  334.     cRect ensureCapacity(const cRect &bounds, bool addExtra)
  335.     {
  336.         //Check whether we have enough capacity to resize.
  337.         if(!this->capacity.Contains(bounds))
  338.         {
  339.             cRect desiredCapacity = bounds;
  340.            
  341.             if(addExtra)
  342.             {
  343.                 //If we're bothering to grow in size, we might as well reserve a little extra for future growth.
  344.                 int quarterWidth = (bounds.size.width / 4) + 1;
  345.                 int quarterHeight = (bounds.size.height / 4) + 1;
  346.                
  347.                 desiredCapacity.Pad(quarterWidth, quarterWidth, quarterHeight, quarterHeight);
  348.             }
  349.            
  350.             //Allocate and move the elements.
  351.             //[CAN THROW - Make sure no member variables are changed before this function call]
  352.             this->reallocateMemory(desiredCapacity);
  353.            
  354.             //Return the new capacity.
  355.             return desiredCapacity;
  356.         }
  357.        
  358.         //Return the current capacity.
  359.         return this->capacity;
  360.     }    
  361.    
  362.     //================================================================
  363.    
  364.     //This allocates enough memory for 'capacity', without constructing any elements.
  365.     Type *allocate(const cRect &capacity)
  366.     {
  367.         //Allocate the new memory.
  368.         size_t numElements = capacity.size.Area();
  369.         size_t numBytes = (sizeof(Type) * numElements);
  370.         void *data = ::operator new(numBytes);
  371.        
  372.         return static_cast<Type*>(data);
  373.     }
  374.    
  375.     //This deallocates 'memory', without calling any destructors.
  376.     void deallocate(Type *data)
  377.     {
  378.         ::operator delete(data);
  379.     }
  380.    
  381.     //================================================================
  382.    
  383.     //Reallocates the memory and migrates the elements over using moveElements().
  384.     //Throws std::bad_alloc if the allocation failed, and throws any exceptions thrown by element constructors.
  385.     void reallocateMemory(const cRect &newCapacity)
  386.     {
  387.         if(!this->memory)
  388.         {
  389.             //If we don't have any memory, just allocate some and don't worry about moving any elements.
  390.             //[CAN THROW - Make sure no member variables are changed before this function call]
  391.             this->memory = this->allocate(newCapacity);
  392.         }
  393.         else if(newCapacity.IsEmpty())
  394.         {
  395.             //Free all the memory.
  396.             this->deallocate(this->memory);
  397.             this->memory = nullptr;
  398.         }
  399.         else
  400.         {
  401.             //Allocate the new memory.
  402.             //Note: I put the allocated memory into a unique_ptr here, incase moveElements() throws.
  403.             //This way, the new memory is properly released.
  404.             //[CAN THROW - Make sure no member variables are changed before this function call]
  405.             std::unique_ptr<Type, use_operator_delete> newMemory = this->allocate(newCapacity);
  406.  
  407.             //A few extra variables for readability.
  408.             Type *oldMemory = this->memory;
  409.             const cRect &oldCapacity = this->capacity;
  410.            
  411.             //Move the elements.
  412.             //[CAN THROW - Make sure no member variables are changed before this function call]
  413.             this->moveElements(oldMemory, oldCapacity, newMemory.get(), newCapacity, this->bounds);
  414.  
  415.             //Delete the old memory.
  416.             this->deallocate(oldMemory);
  417.            
  418.             //And store the new pointer. Have the unique_ptr release ownership of the memory as well.
  419.             this->memory = newMemory.release();
  420.         }
  421.        
  422.         //Record the new capacity.
  423.         this->capacity = newCapacity;
  424.     }
  425.    
  426.     //Called by 'reallocateMemory' only.
  427.     void moveElements(Type *oldMemory, const cRect &oldCapacity, Type *newMemory,
  428.                       const cRect &newCapacity, const cRect &bounds)
  429.     {
  430.         //Insanity preservation.
  431.         //Assert that our elements are actually within the capacity of both the new and old blocks of memory.
  432.         BOOST_ASSERT(oldCapacity.Contains(bounds));
  433.         BOOST_ASSERT(newCapacity.Contains(bounds));
  434.        
  435.         //Assert that neither block of memory's size is empty (they have to have a positive non-zero width and height).
  436.         BOOST_ASSERT(!oldCapacity.IsEmpty());
  437.         BOOST_ASSERT(!newCapacity.IsEmpty());
  438.        
  439.         //Assert that neither pointer to the allocated memory is empty.
  440.         BOOST_ASSERT(oldMemory != nullptr);
  441.         BOOST_ASSERT(newMemory != nullptr);
  442.        
  443.         //The length of each 'row' of the grid's capacity in memory.
  444.         size_t oldStride = oldCapacity.size.width;
  445.         size_t newStride = newCapacity.size.width;
  446.        
  447.         //The initial offset of the actual bounds from the memory capacity.
  448.         size_t oldOffset = oldCapacity.Index(bounds.position);
  449.         size_t newOffset = newCapacity.Index(bounds.position);
  450.        
  451.         //The number of rows and columns of actual elements we need to move.
  452.         size_t rows = bounds.size.height;
  453.         size_t columns = bounds.size.width;
  454.        
  455.         //=================================================================
  456.        
  457.         //Incase a constructor throws an exception, keep track of the last row and column.
  458.         size_t lastRow = 0;
  459.         size_t lastColumn = 0;
  460.        
  461.         try
  462.         {
  463.             //Move-construct all the new elements.
  464.             for(size_t row = 0; row < rows; lastRow = row++)
  465.             {
  466.                 for(size_t column = 0; column < columns; lastColumn = column++)
  467.                 {
  468.                     size_t oldIndex = (row * oldStride) + column;
  469.                     oldIndex += oldOffset;
  470.                    
  471.                     size_t newIndex = (row * newStride) + column;
  472.                     newIndex += newOffset;
  473.                    
  474.                     //Construct the new location, and move the element.
  475.                     this->moveConstruct(newMemory[newIndex], std::move(oldMemory[oldIndex]));
  476.                 }
  477.             }
  478.         }
  479.         catch(...)
  480.         {
  481.             //Since we just caught an exception thrown from one of the element move-constructors,
  482.             //destruct all the new elements we just constructed, up until the failed constructor.
  483.             for(size_t row = 0; row < lastRow; row++)
  484.             {
  485.                 for(size_t column = 0; column < lastColumn; column++)
  486.                 {
  487.                     size_t newIndex = (row * newStride) + column;
  488.                     newIndex += newOffset;
  489.                    
  490.                     //Destruct the element we constructed in the previous for() loops.
  491.                     this->destruct(newMemory[newIndex]);
  492.                 }
  493.             }
  494.            
  495.             throw;
  496.         }
  497.        
  498.         //=================================================================
  499.        
  500.         //Destruct all the old elements.
  501.         for(size_t row = 0; row < rows; row++)
  502.         {
  503.             for(size_t column = 0; column < columns; column++)
  504.             {
  505.                 size_t oldIndex = (row * oldStride) + column;
  506.                 oldIndex += oldOffset;
  507.                
  508.                 //Destruct old location.
  509.                 this->destruct(oldMemory[oldIndex]);
  510.             }
  511.         }
  512.     }
  513.  
  514.     //================================================================
  515.    
  516. private:
  517.     Type *memory;
  518.    
  519.     cRect bounds; //Current grid boundries.
  520.     cRect capacity; //Currently allocated memory capacity, garunteed to be at least 'bounds' and maybe larger.
  521. };
  522.  
  523. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////
  524. //XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX//
  525. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////
  526.  
  527. /*
  528.     A random-access iterator for iterating over each element of a Common::Grid.
  529.  
  530.     I'm doing a trick here, by taking the type of the container as a second template parameter.
  531.     This allows me to do this:
  532.         typedef GridIterator<const Type, const Grid<Type> > const_iterator;
  533.    
  534.     ...instead of having to create two seperate iterator classes (one for regular iterator and one for const).
  535. */
  536. template <typename Type, typename ContainerType = typename Common::Grid<Type> >
  537. class GridIterator
  538. {
  539. public:
  540.     GridIterator(ContainerType &grid, unsigned index) : grid(grid), index(index)
  541.     {
  542.         this->maxIndex = this->grid.GetBounds().Area();
  543.     }
  544.    
  545.     //================================================================
  546.    
  547.     //De-reference.
  548.     Type &operator*()
  549.     {
  550.         return this->grid.AtIndex(this->index);
  551.     }
  552.     Type &operator->()
  553.     {
  554.         return (operator*());
  555.     }
  556.    
  557.     //================================================================
  558.    
  559.     //Comparison.
  560.     bool operator==(const GridIterator &other) const
  561.     {
  562.         return (&this->grid == &other.grid) && (this->index == other.index);
  563.     }
  564.    
  565.     bool operator!=(const GridIterator &other) const
  566.     {
  567.         return !operator==(other);
  568.     }
  569.    
  570.     //================================================================
  571.    
  572.     //Increment/decrement.
  573.     GridIterator &operator++()
  574.     {
  575.         this->index++;
  576.         Limit(this->index, this->maxIndex);
  577.         return *this;
  578.     }
  579.    
  580.     GridIterator operator++(int)
  581.     {
  582.         GridIterator temp(*this);
  583.         ++(*this);
  584.         return temp;
  585.     }
  586.    
  587.     GridIterator &operator--()
  588.     {
  589.         this->index--;
  590.         return *this;
  591.     }
  592.    
  593.     GridIterator operator--(int)
  594.     {
  595.         GridIterator temp(*this);
  596.         --(*this);
  597.         return temp;
  598.     }
  599.    
  600.     //================================================================
  601.  
  602.     //Random access.
  603.     GridIterator operator+(int n) const
  604.     {
  605.         GridIterator temp(*this);
  606.         temp.index += n;
  607.         return temp;
  608.     }
  609.    
  610.     GridIterator &operator+=(int n)
  611.     {
  612.         this->index += n;
  613.         Limit(this->index, this->maxIndex);
  614.         return *this;
  615.     }
  616.    
  617.     GridIterator operator-(int n) const
  618.     {
  619.         GridIterator temp(*this);
  620.         temp.index -= n;
  621.         return temp;
  622.     }
  623.    
  624.     GridIterator &operator-=(int n)
  625.     {
  626.         this->index -= n;
  627.         return *this;
  628.     }
  629.    
  630.     //================================================================
  631.    
  632. private:
  633.     ContainerType &grid;
  634.  
  635.     unsigned index; //The current index.
  636.     unsigned maxIndex; //The maximum value (and the result returned by 'std::end()'.
  637. };
  638.  
  639. //================================================================
  640.  
  641. } //End of namespace.
  642.  
  643. #endif // COMMON_CONTAINERS_GRID_H