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 <algorithm>
  20 #include <cassert>
  21 #include <dali/dali.h>
  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 ) :  mCells( width * height ), mWidth( width ), mHeight( height ), mHighestUsedRow( 0 )
  40   {
  41 #ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
  42       fprintf(stderr, "Grid created with dimensions: (%u, %u).\n", mWidth, mHeight );
  43 #endif
  44   }
  45
  46   void Set( const unsigned x, const unsigned y )
  47   {
  48     const unsigned index = CellIndex( x, y );
  49     mCells[index] += 1u; ///< += To allow a debug check of the number of times a cell is set.
  50     mHighestUsedRow = std::max( mHighestUsedRow, y );
  51   }
  52
  53   bool Get( unsigned x, unsigned y ) const
  54   {
  55     return mCells[ CellIndex( x, y ) ] != 0;
  56   }
  57
  58   unsigned GetHighestUsedRow() const
  59   {
  60     return mHighestUsedRow;
  61   }
  62
  63   /**
  64    * @brief Try to find space in a grid of cells for the region requested.
  65    * @return true if any region (not necessarily an exact match) was found, else false.
  66    * @param[in] region The rectangular region requested
  67    * @param[out] outCellX The X coordinate of the region allocated, if any.
  68    * @param[out] outCellY The Y coordinate of the region allocated, if any.
  69    * @param[out] outRegion The rectangle actually found: the lowest-Y exact match region
  70    *             or the largest area rectangular region no greater than the requested
  71    *             region in x or y. Undefined if false is returned.
  72    */
  73   bool AllocateRegion( const Vector2& region, unsigned& outCellX, unsigned& outCellY, Vector2& outRegion )
  74   {
  75     const unsigned regionWidth = (region.x + 0.5f);
  76     const unsigned regionHeight = (region.y + 0.5f);
  77 #ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
  78       fprintf( stderr, "Allocation requested for region (%u, %u). Result: ", regionWidth, regionHeight );
  79 #endif
  80     unsigned bestRegionWidth = 0;
  81     unsigned bestRegionHeight = 0;
  82     unsigned bestCellX = 0;
  83     unsigned bestCellY = 0;
  84
  85     // Look for a non-set cell:
  86     for( unsigned y = 0; y < mHeight; ++y )
  87     {
  88       for( unsigned x = 0; x < mWidth; ++x )
  89       {
  90         if ( !Get( x, y) )
  91         {
  92           // Look for clear grid cells under the desired region:
  93
  94           const unsigned clampedRegionHeight = std::min( regionHeight, mHeight - y);
  95           const unsigned clampedRegionWidth = std::min( regionWidth, mWidth - x);
  96           const unsigned regionLimitY = y + clampedRegionHeight;
  97           const unsigned regionLimitX = x + clampedRegionWidth;
  98
  99           for( unsigned regionY = y; regionY < regionLimitY; ++regionY )
 100           {
 101             for( unsigned regionX = x; regionX < regionLimitX; ++regionX )
 102             {
 103               if( Get( regionX, regionY ) )
 104               {
 105                 // The region of clear cells is not big enough but remember it
 106                 // anyway in case there is no region that fits:
 107                 const unsigned clearRegionWidth = regionX - x;
 108                 const unsigned clearRegionHeight = (regionY + 1) - y;
 109                 if( clearRegionWidth * clearRegionHeight > bestRegionWidth * bestRegionHeight )
 110                 {
 111                   bestCellX = x;
 112                   bestCellY = y;
 113                   bestRegionWidth = clearRegionWidth;
 114                   bestRegionHeight = clearRegionHeight;
 115                 }
 116                 goto whole_region_not_found;
 117               }
 118             }
 119           }
 120
 121           // Every cell in the region is clear so check if it is the best one yet:
 122           if( clampedRegionWidth * clampedRegionHeight > bestRegionWidth * bestRegionHeight )
 123           {
 124             bestCellX = x;
 125             bestCellY = y;
 126             bestRegionWidth = clampedRegionWidth;
 127             bestRegionHeight = clampedRegionHeight;
 128           }
 129
 130           // If a big-enough region was found, end the search early and greedily allocate it:
 131           if( clampedRegionHeight == regionHeight && clampedRegionWidth == regionWidth )
 132           {
 133             x = mWidth;
 134             y = mHeight;
 135           }
 136 whole_region_not_found:
 137           continue;
 138         }
 139       }
 140     }
 141
 142     // Allocate and return the best cell region found:
 143
 144     if( bestRegionWidth == 0 || bestRegionHeight == 0 )
 145     {
 146 #ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
 147         fputs( "false.\n", stderr );
 148 #endif
 149       return false;
 150     }
 151
 152     // Allocate the found region:
 153 #ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
 154       fprintf( stderr, " - bestCellX = %u, bestCellY = %u, bestRegionWidth = %u, bestRegionHeight = %u - ", bestCellX, bestCellY, bestRegionWidth, bestRegionHeight );
 155 #endif
 156     for( unsigned y = bestCellY; y < bestCellY + bestRegionHeight; ++y )
 157     {
 158       for( unsigned x = bestCellX; x < bestCellX + bestRegionWidth; ++x )
 159       {
 160         Set( x, y );
 161       }
 162     }
 163
 164     outCellX = bestCellX;
 165     outCellY = bestCellY;
 166     outRegion = Vector2( bestRegionWidth, bestRegionHeight );
 167 #ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
 168       fputs( "true.\n", stderr );
 169 #endif
 170     return true;
 171   }
 172
 173   /** @return True if every cell was set one or zero times, else false. */
 174   bool DebugCheckGridValid()
 175   {
 176     for( unsigned cell = 0; cell < mWidth * mHeight; ++cell )
 177     {
 178       if( mCells[cell] > 1 )
 179       {
 180         return false;
 181       }
 182     }
 183     return true;
 184   }
 185
 186 private:
 187   unsigned CellIndex( unsigned x, unsigned y ) const
 188   {
 189     const unsigned offset = mWidth * y + x;
 190     assert( offset < mCells.size() && "Out of range access to grid." );
 191     return offset;
 192   }
 193
 194   std::vector<unsigned char> mCells;
 195   const unsigned mWidth;
 196   const unsigned mHeight;
 197   unsigned mHighestUsedRow;
 198 };
 199
 200 } // namespace Demo
 201
 202 } // namespace Dali
 203
 204 #endif // DALI_DEMO_GRID_FLAGS_H