1 #ifndef __DALI_DEMO_GRID_FLAGS_H_
2 #define __DALI_DEMO_GRID_FLAGS_H_
4 * Copyright (c) 2014 Samsung Electronics Co., Ltd.
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
10 * http://www.apache.org/licenses/LICENSE-2.0
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.
21 #include <dali/dali.h>
23 /** Controls the output of application logging. */
24 //#define DEBUG_PRINT_GRID_DIAGNOSTICS
31 * @brief A 2D grid of booleans, settable and gettable via integer (x,y) coordinates.
37 * Create grid of specified dimensions.
39 GridFlags( unsigned width, unsigned height ) : mCells( width * height ), mWidth( width ), mHeight( height ), mHighestUsedRow( 0 )
41 #ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
42 fprintf(stderr, "Grid created with dimensions: (%u, %u).\n", mWidth, mHeight );
46 void Set( const unsigned x, const unsigned y )
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 );
53 bool Get( unsigned x, unsigned y ) const
55 return mCells[ CellIndex( x, y ) ] != 0;
58 unsigned GetHighestUsedRow() const
60 return mHighestUsedRow;
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.
73 bool AllocateRegion( const Vector2& region, unsigned& outCellX, unsigned& outCellY, Vector2& outRegion )
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 );
80 unsigned bestRegionWidth = 0;
81 unsigned bestRegionHeight = 0;
82 unsigned bestCellX = 0;
83 unsigned bestCellY = 0;
85 // Look for a non-set cell:
86 for( unsigned y = 0; y < mHeight; ++y )
88 for( unsigned x = 0; x < mWidth; ++x )
92 // Look for clear grid cells under the desired region:
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;
99 for( unsigned regionY = y; regionY < regionLimitY; ++regionY )
101 for( unsigned regionX = x; regionX < regionLimitX; ++regionX )
103 if( Get( regionX, regionY ) )
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 )
113 bestRegionWidth = clearRegionWidth;
114 bestRegionHeight = clearRegionHeight;
116 goto whole_region_not_found;
121 // Every cell in the region is clear so check if it is the best one yet:
122 if( clampedRegionWidth * clampedRegionHeight > bestRegionWidth * bestRegionHeight )
126 bestRegionWidth = clampedRegionWidth;
127 bestRegionHeight = clampedRegionHeight;
130 // If a big-enough region was found, end the search early and greedily allocate it:
131 if( clampedRegionHeight == regionHeight && clampedRegionWidth == regionWidth )
136 whole_region_not_found:
142 // Allocate and return the best cell region found:
144 if( bestRegionWidth == 0 || bestRegionHeight == 0 )
146 #ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
147 fputs( "false.\n", stderr );
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 );
156 for( unsigned y = bestCellY; y < bestCellY + bestRegionHeight; ++y )
158 for( unsigned x = bestCellX; x < bestCellX + bestRegionWidth; ++x )
164 outCellX = bestCellX;
165 outCellY = bestCellY;
166 outRegion = Vector2( bestRegionWidth, bestRegionHeight );
167 #ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
168 fputs( "true.\n", stderr );
173 /** @return True if every cell was set one or zero times, else false. */
174 bool DebugCheckGridValid()
176 for( unsigned cell = 0; cell < mWidth * mHeight; ++cell )
178 if( mCells[cell] > 1 )
187 unsigned CellIndex( unsigned x, unsigned y ) const
189 const unsigned offset = mWidth * y + x;
190 assert( offset < mCells.size() && "Out of range access to grid." );
194 std::vector<unsigned char> mCells;
195 const unsigned mWidth;
196 const unsigned mHeight;
197 unsigned mHighestUsedRow;
200 } /* namespace Demo */
201 } /* namespace Dali */
203 #endif /* __DALI_DEMO_GRID_FLAGS_H_ */