#ifndef DALI_DEMO_GRID_FLAGS_H
#define DALI_DEMO_GRID_FLAGS_H
/*
 * Copyright (c) 2014 Samsung Electronics Co., Ltd.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 */
#include <dali/dali.h>
#include <algorithm>
#include <cassert>

/** Controls the output of application logging. */
//#define DEBUG_PRINT_GRID_DIAGNOSTICS

namespace Dali
{
namespace Demo
{
/**
 * @brief A 2D grid of booleans, settable and gettable via integer (x,y) coordinates.
 * */
class GridFlags
{
public:
  /**
   * Create grid of specified dimensions.
   */
  GridFlags(unsigned width, unsigned height)
  : mCells(width * height),
    mWidth(width),
    mHeight(height),
    mHighestUsedRow(0)
  {
#ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
    fprintf(stderr, "Grid created with dimensions: (%u, %u).\n", mWidth, mHeight);
#endif
  }

  void Set(const unsigned x, const unsigned y)
  {
    const unsigned index = CellIndex(x, y);
    mCells[index] += 1u; ///< += To allow a debug check of the number of times a cell is set.
    mHighestUsedRow = std::max(mHighestUsedRow, y);
  }

  bool Get(unsigned x, unsigned y) const
  {
    return mCells[CellIndex(x, y)] != 0;
  }

  unsigned GetHighestUsedRow() const
  {
    return mHighestUsedRow;
  }

  /**
   * @brief Try to find space in a grid of cells for the region requested.
   * @return true if any region (not necessarily an exact match) was found, else false.
   * @param[in] region The rectangular region requested
   * @param[out] outCellX The X coordinate of the region allocated, if any.
   * @param[out] outCellY The Y coordinate of the region allocated, if any.
   * @param[out] outRegion The rectangle actually found: the lowest-Y exact match region
   *             or the largest area rectangular region no greater than the requested
   *             region in x or y. Undefined if false is returned.
   */
  bool AllocateRegion(const Vector2& region, unsigned& outCellX, unsigned& outCellY, Vector2& outRegion)
  {
    const unsigned regionWidth  = (region.x + 0.5f);
    const unsigned regionHeight = (region.y + 0.5f);
#ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
    fprintf(stderr, "Allocation requested for region (%u, %u). Result: ", regionWidth, regionHeight);
#endif
    unsigned bestRegionWidth  = 0;
    unsigned bestRegionHeight = 0;
    unsigned bestCellX        = 0;
    unsigned bestCellY        = 0;

    // Look for a non-set cell:
    for(unsigned y = 0; y < mHeight; ++y)
    {
      for(unsigned x = 0; x < mWidth; ++x)
      {
        if(!Get(x, y))
        {
          // Look for clear grid cells under the desired region:

          const unsigned clampedRegionHeight = std::min(regionHeight, mHeight - y);
          const unsigned clampedRegionWidth  = std::min(regionWidth, mWidth - x);
          const unsigned regionLimitY        = y + clampedRegionHeight;
          const unsigned regionLimitX        = x + clampedRegionWidth;

          for(unsigned regionY = y; regionY < regionLimitY; ++regionY)
          {
            for(unsigned regionX = x; regionX < regionLimitX; ++regionX)
            {
              if(Get(regionX, regionY))
              {
                // The region of clear cells is not big enough but remember it
                // anyway in case there is no region that fits:
                const unsigned clearRegionWidth  = regionX - x;
                const unsigned clearRegionHeight = (regionY + 1) - y;
                if(clearRegionWidth * clearRegionHeight > bestRegionWidth * bestRegionHeight)
                {
                  bestCellX        = x;
                  bestCellY        = y;
                  bestRegionWidth  = clearRegionWidth;
                  bestRegionHeight = clearRegionHeight;
                }
                goto whole_region_not_found;
              }
            }
          }

          // Every cell in the region is clear so check if it is the best one yet:
          if(clampedRegionWidth * clampedRegionHeight > bestRegionWidth * bestRegionHeight)
          {
            bestCellX        = x;
            bestCellY        = y;
            bestRegionWidth  = clampedRegionWidth;
            bestRegionHeight = clampedRegionHeight;
          }

          // If a big-enough region was found, end the search early and greedily allocate it:
          if(clampedRegionHeight == regionHeight && clampedRegionWidth == regionWidth)
          {
            x = mWidth;
            y = mHeight;
          }
        whole_region_not_found:
          continue;
        }
      }
    }

    // Allocate and return the best cell region found:

    if(bestRegionWidth == 0 || bestRegionHeight == 0)
    {
#ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
      fputs("false.\n", stderr);
#endif
      return false;
    }

    // Allocate the found region:
#ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
    fprintf(stderr, " - bestCellX = %u, bestCellY = %u, bestRegionWidth = %u, bestRegionHeight = %u - ", bestCellX, bestCellY, bestRegionWidth, bestRegionHeight);
#endif
    for(unsigned y = bestCellY; y < bestCellY + bestRegionHeight; ++y)
    {
      for(unsigned x = bestCellX; x < bestCellX + bestRegionWidth; ++x)
      {
        Set(x, y);
      }
    }

    outCellX  = bestCellX;
    outCellY  = bestCellY;
    outRegion = Vector2(bestRegionWidth, bestRegionHeight);
#ifdef DEBUG_PRINT_GRID_DIAGNOSTICS
    fputs("true.\n", stderr);
#endif
    return true;
  }

  /** @return True if every cell was set one or zero times, else false. */
  bool DebugCheckGridValid()
  {
    for(unsigned cell = 0; cell < mWidth * mHeight; ++cell)
    {
      if(mCells[cell] > 1)
      {
        return false;
      }
    }
    return true;
  }

private:
  unsigned CellIndex(unsigned x, unsigned y) const
  {
    const unsigned offset = mWidth * y + x;
    assert(offset < mCells.size() && "Out of range access to grid.");
    return offset;
  }

  std::vector<unsigned char> mCells;
  const unsigned             mWidth;
  const unsigned             mHeight;
  unsigned                   mHighestUsedRow;
};

} // namespace Demo

} // namespace Dali

#endif // DALI_DEMO_GRID_FLAGS_H