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