examples/image-scaling-irregular-grid/grid-flags.h

   1 #ifndef DALI_DEMO_GRID_FLAGS_H
   2 #define DALI_DEMO_GRID_FLAGS_H
   3 /*
   4  * Copyright (c) 2014 Samsung Electronics Co., Ltd.
   5  *
   6  * Licensed under the Apache License, Version 2.0 (the "License");
   7  * you may not use this file except in compliance with the License.
   8  * You may obtain a copy of the License at
   9  *
  10  * http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  *
  18  */
  19 #include <dali/dali.h>
  20 #include <algorithm>
  21 #include <cassert>
  22
  23 /** Controls the output of application logging. */
  24 //#define DEBUG_PRINT_GRID_DIAGNOSTICS
  25
  26 namespace Dali
  27 {
  28 namespace Demo
  29 {
  30 /**
  31  * @brief A 2D grid of booleans, settable and gettable via integer (x,y) coordinates.
  32  * */
  33 class GridFlags
  34 {
  35 public:
  36   /**
  37    * Create grid of specified dimensions.
  38    */
  39   GridFlags(unsigned width, unsigned height)
  40   : mCells(width * height),
  41     mWidth(width),
  42     mHeight(height),
  43     mHighestUsedRow(0)
  44   {
  45 #ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
  46     fprintf(stderr, "Grid created with dimensions: (%u, %u).\n", mWidth, mHeight);
  47 #endif
  48   }
  49
  50   void Set(const unsigned x, const unsigned y)
  51   {
  52     const unsigned index = CellIndex(x, y);
  53     mCells[index] += 1u; ///< += To allow a debug check of the number of times a cell is set.
  54     mHighestUsedRow = std::max(mHighestUsedRow, y);
  55   }
  56
  57   bool Get(unsigned x, unsigned y) const
  58   {
  59     return mCells[CellIndex(x, y)] != 0;
  60   }
  61
  62   unsigned GetHighestUsedRow() const
  63   {
  64     return mHighestUsedRow;
  65   }
  66
  67   /**
  68    * @brief Try to find space in a grid of cells for the region requested.
  69    * @return true if any region (not necessarily an exact match) was found, else false.
  70    * @param[in] region The rectangular region requested
  71    * @param[out] outCellX The X coordinate of the region allocated, if any.
  72    * @param[out] outCellY The Y coordinate of the region allocated, if any.
  73    * @param[out] outRegion The rectangle actually found: the lowest-Y exact match region
  74    *             or the largest area rectangular region no greater than the requested
  75    *             region in x or y. Undefined if false is returned.
  76    */
  77   bool AllocateRegion(const Vector2& region, unsigned& outCellX, unsigned& outCellY, Vector2& outRegion)
  78   {
  79     const unsigned regionWidth  = (region.x + 0.5f);
  80     const unsigned regionHeight = (region.y + 0.5f);
  81 #ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
  82     fprintf(stderr, "Allocation requested for region (%u, %u). Result: ", regionWidth, regionHeight);
  83 #endif
  84     unsigned bestRegionWidth  = 0;
  85     unsigned bestRegionHeight = 0;
  86     unsigned bestCellX        = 0;
  87     unsigned bestCellY        = 0;
  88
  89     // Look for a non-set cell:
  90     for(unsigned y = 0; y < mHeight; ++y)
  91     {
  92       for(unsigned x = 0; x < mWidth; ++x)
  93       {
  94         if(!Get(x, y))
  95         {
  96           // Look for clear grid cells under the desired region:
  97
  98           const unsigned clampedRegionHeight = std::min(regionHeight, mHeight - y);
  99           const unsigned clampedRegionWidth  = std::min(regionWidth, mWidth - x);
 100           const unsigned regionLimitY        = y + clampedRegionHeight;
 101           const unsigned regionLimitX        = x + clampedRegionWidth;
 102
 103           for(unsigned regionY = y; regionY < regionLimitY; ++regionY)
 104           {
 105             for(unsigned regionX = x; regionX < regionLimitX; ++regionX)
 106             {
 107               if(Get(regionX, regionY))
 108               {
 109                 // The region of clear cells is not big enough but remember it
 110                 // anyway in case there is no region that fits:
 111                 const unsigned clearRegionWidth  = regionX - x;
 112                 const unsigned clearRegionHeight = (regionY + 1) - y;
 113                 if(clearRegionWidth * clearRegionHeight > bestRegionWidth * bestRegionHeight)
 114                 {
 115                   bestCellX        = x;
 116                   bestCellY        = y;
 117                   bestRegionWidth  = clearRegionWidth;
 118                   bestRegionHeight = clearRegionHeight;
 119                 }
 120                 goto whole_region_not_found;
 121               }
 122             }
 123           }
 124
 125           // Every cell in the region is clear so check if it is the best one yet:
 126           if(clampedRegionWidth * clampedRegionHeight > bestRegionWidth * bestRegionHeight)
 127           {
 128             bestCellX        = x;
 129             bestCellY        = y;
 130             bestRegionWidth  = clampedRegionWidth;
 131             bestRegionHeight = clampedRegionHeight;
 132           }
 133
 134           // If a big-enough region was found, end the search early and greedily allocate it:
 135           if(clampedRegionHeight == regionHeight && clampedRegionWidth == regionWidth)
 136           {
 137             x = mWidth;
 138             y = mHeight;
 139           }
 140         whole_region_not_found:
 141           continue;
 142         }
 143       }
 144     }
 145
 146     // Allocate and return the best cell region found:
 147
 148     if(bestRegionWidth == 0 || bestRegionHeight == 0)
 149     {
 150 #ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
 151       fputs("false.\n", stderr);
 152 #endif
 153       return false;
 154     }
 155
 156     // Allocate the found region:
 157 #ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
 158     fprintf(stderr, " - bestCellX = %u, bestCellY = %u, bestRegionWidth = %u, bestRegionHeight = %u - ", bestCellX, bestCellY, bestRegionWidth, bestRegionHeight);
 159 #endif
 160     for(unsigned y = bestCellY; y < bestCellY + bestRegionHeight; ++y)
 161     {
 162       for(unsigned x = bestCellX; x < bestCellX + bestRegionWidth; ++x)
 163       {
 164         Set(x, y);
 165       }
 166     }
 167
 168     outCellX  = bestCellX;
 169     outCellY  = bestCellY;
 170     outRegion = Vector2(bestRegionWidth, bestRegionHeight);
 171 #ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
 172     fputs("true.\n", stderr);
 173 #endif
 174     return true;
 175   }
 176
 177   /** @return True if every cell was set one or zero times, else false. */
 178   bool DebugCheckGridValid()
 179   {
 180     for(unsigned cell = 0; cell < mWidth * mHeight; ++cell)
 181     {
 182       if(mCells[cell] > 1)
 183       {
 184         return false;
 185       }
 186     }
 187     return true;
 188   }
 189
 190 private:
 191   unsigned CellIndex(unsigned x, unsigned y) const
 192   {
 193     const unsigned offset = mWidth * y + x;
 194     assert(offset < mCells.size() && "Out of range access to grid.");
 195     return offset;
 196   }
 197
 198   std::vector<unsigned char> mCells;
 199   const unsigned             mWidth;
 200   const unsigned             mHeight;
 201   unsigned                   mHighestUsedRow;
 202 };
 203
 204 } // namespace Demo
 205
 206 } // namespace Dali
 207
 208 #endif // DALI_DEMO_GRID_FLAGS_H