#include"state.h"
#include<stdio.h>
#include<string>

namespace {

// Tile color and pattern.
static constexpr const char *kTile[4] =
{
   "\x1b[97;101m<>\x1b[0m",
   "\x1b[97;102m()\x1b[0m",
   "\x1b[97;103m{}\x1b[0m",
   "\x1b[97;104m[]\x1b[0m"
};

// Offsets for the second tile in each block.  Index is block orientation.
static constexpr int kOffsetX[4] = {0, 1, 0, -1};
static constexpr int kOffsetY[4] = {1, 0, -1, 0};

// Random number generator.
static int GenerateRand(int *seed)
{
   *seed ^= *seed << 13;
   *seed &= 0x7fffffff;
   *seed ^= *seed >> 17;
   *seed ^= *seed << 5;
   *seed &= 0x7fffffff;
   return *seed;
}

// Check if a single tile is colliding with grid tiles, returns true if so.
static bool TileCollision(const Grid &grid, int x, int y)
{
   // Note that there is no check for Y<0, since blocks are never
   // generated near the bottom edge.
   return x < 0 || x >= kWidth ||
          (y < static_cast<int>(grid[x].size()) && grid[x][y] != kEmpty);
}

// Check if a block is colliding with the grid tiles, returns true if so.
static bool BlockCollision(const Grid &grid, const PendingBlock &block)
{
   return TileCollision(grid, block.x, block.y) ||
          TileCollision(grid,
                        block.x + kOffsetX[block.orientation],
                        block.y + kOffsetY[block.orientation]);
}

// Apply block movement command to pending block.
static void MovePendingBlock(const Grid &grid,
                             char movement,
                             PendingBlock *block)
{
   switch( movement )
   {
      case PendingBlock::kLeft:
      case PendingBlock::kRight:
         {
            const int dx = movement == PendingBlock::kLeft ? -1 : 1;
            block->x += dx;
            if( BlockCollision(grid, *block) )
            {
               // Undo move on collision.
               block->x -= dx;
            }
            else
            {
               // On successful move, also try to bring the block down
               // to usual height if possible.
               const int y = block->y;
               if( y != kHeight - 1 )
               {
                  block->y = kHeight - 1;
                  if( BlockCollision(grid, *block) )
                     block->y = y;
               }
            }
         }
         break;

      case PendingBlock::kRotate:
         block->orientation = (block->orientation + 1) % 4;
         if( BlockCollision(grid, *block) )
         {
            if( kOffsetX[block->orientation] == 0 )
            {
               // Colliding vertically, try shift the block up just
               // above the grid.
               block->y++;
            }
            else
            {
               // Colliding horizontally.  Try shift the block in the
               // opposite direction to resolve the collision, i.e.
               // translate the rotation to a "kick" off the wall.
               const int dx = kOffsetX[block->orientation];
               block->x -= dx;
               if( BlockCollision(grid, *block) )
               {
                  // Undo rotation if we still can't resolve this conflict.
                  block->x += dx;
                  block->orientation = (block->orientation + 3) % 4;
               }
            }
         }
         break;

      default:
         break;
   }
}

// Compute score from list of clusters.
static int GetScore(const Grid &grid,
                    const ClusterList &clusters,
                    int chain_length)
{
   int tiles_cleared = 0;
   int group_bonus = 0;
   int colors_cleared = 0;
   for(const Cluster &c : clusters)
   {
      if( c.size() < 4 )
         continue;

      colors_cleared |= 1U << grid[c[0].first][c[0].second];
      tiles_cleared += c.size();
      if( c.size() < 11 )
      {
         static constexpr int kGroupBonus[11] =
         {
            -1, -1, -1, -1, 0, 2, 3, 4, 5, 6, 7
         };
         group_bonus += kGroupBonus[c.size()];
      }
      else
      {
         group_bonus += 10;
      }
   }

   int chain_power;
   if( chain_length < 9 )
   {
      static constexpr int kChainPower[9] =
      {
         -1, 0, 8, 16, 32, 64, 128, 256, 512
      };
      chain_power = kChainPower[chain_length];
   }
   else
   {
      chain_power = 999;
   }

   static constexpr int kColorBonus[5] = {-1, 0, 3, 6, 12};
   static constexpr int kBitCount[16] = {
   // 00 01 10 11
      0, 1, 1, 2,  // 00
      1, 2, 2, 3,  // 01
      1, 2, 2, 3,  // 10
      2, 3, 3, 4   // 11
   };
   const int color_bonus = kColorBonus[kBitCount[colors_cleared]];

   const int bonus =
      std::min(std::max(1, chain_power + color_bonus + group_bonus), 999);
   return 10 * tiles_cleared * bonus;
}

// Apply gravity to grid, dropping all tiles to bottom.
static void ApplyGravity(Grid *grid)
{
   for(int x = 0; x < kWidth; x++)
   {
      std::vector<Color> column;
      for (Color c : (*grid)[x])
      {
         if( c != kEmpty )
            column.push_back(c);
      }
      (*grid)[x].swap(column);
   }
}

// Drop block onto grid, and record changes in score.
template <typename Score>
static Score DropBlockAndUpdateScore(const PendingBlock &block, Grid *grid)
{
   // Affix block to grid.  The block is essentially suspended in mid-air at
   // this point, and will be dropped to the proper place with the two tiles
   // in the correct order when we apply gravity in the next loop.
   for(int t = 0; t < 2; t++)
   {
      int x = block.x;
      int y = block.y;
      if( t == 1 )
      {
         x += kOffsetX[block.orientation];
         y += kOffsetY[block.orientation];
      }
      while( static_cast<int>((*grid)[x].size()) <= y )
         (*grid)[x].push_back(kEmpty);
      (*grid)[x][y] = block.color[t];
   }

   // Remove chains and accumulate score.  Note that we get 1 point
   // just for dropping the block, so score is always positive.
   Score score;
   score.Add(1);
   for(int chain_length = 1;; chain_length++)
   {
      ApplyGravity(grid);
      const ClusterList clusters = MarkClusters(*grid);
      const int delta = GetScore(*grid, clusters, chain_length);
      if( delta == 0 )
         break;
      score.Add(delta);
      for(const Cluster &c : clusters)
      {
         if( c.size() < 4 )
            continue;
         for(const auto &p : c)
            (*grid)[p.first][p.second] = kEmpty;
      }
   }
   return score;
}

}  // namespace

// Access palette for a single tile
const char *GetTile(Color c)
{
   return kTile[c];
}

// Print block list to stdout.
void DumpBlockList(const BlockList &block_list)
{
   for(int y = 0; y < static_cast<int>(block_list.size()); y += 25)
   {
      for(int t = 0; t < 2; t++)
      {
         for(int x = 0; x < 25 && x + y < static_cast<int>(block_list.size());
             x++)
         {
            // Note that tile[1] is drawn above tile[0] to match
            // initial orientation.
            printf(" %s", kTile[block_list[x + y][1 - t]]);
         }
         putchar('\n');
      }
      for(int x = 0; x < 25 && x + y < static_cast<int>(block_list.size()); x++)
         printf(" %2d", x + y + 1);
      printf("\n\n");
   }
}

// Print grid state to stdout.
void DumpGrid(const Grid &grid)
{
   const std::string edge(kWidth * 2 + 4, '#');
   puts(edge.c_str());
   for(int y = kHeight - 1; y >= 0; y--)
   {
      fputs("##", stdout);
      for(int x = 0; x < kWidth; x++)
      {
         if( y >= static_cast<int>(grid[x].size()) || grid[x][y] == kEmpty )
            fputs("  ", stdout);
         else
            fputs(kTile[grid[x][y]], stdout);
      }
      puts("##");
   }
   puts(edge.c_str());
}

// Generate list of blocks for a particular seed.
BlockList GenerateBlockList(int seed)
{
   // Generate blocks with equal distribution.
   BlockList block_list;
   block_list.reserve(100);
   for(int i = 0; i < 6; i++)
   {
      for(Color a = 0; a < 4; a++)
      {
         for(Color b = 0; b < 4; b++)
            block_list.push_back({a, b});
      }
   }

   // Add a few more single-color ones so that we get exactly 100 blocks.
   for(Color c = 0; c < 4; c++)
      block_list.push_back({c, c});

   // Fisher-Yates shuffle.
   for(int i = 99; i > 0; i--)
   {
      const int j = GenerateRand(&seed) % (i + 1);
      if( i != j )
         std::swap(block_list[i], block_list[j]);
   }
   return block_list;
}

// Find all connected clusters in grid.
ClusterList MarkClusters(const Grid &grid)
{
   ClusterList clusters;

   // Keep track of cells that have already been marked by previous
   // cluster expansions so that we don't double-count cells.
   //
   // This is a bitmask where each array element is a single row.
   // The number of rows is greater than height of the grid to account
   // for the fact that blocks may be stacked above visible grid.
   std::array<int, kHeight + 2> visited;
   visited.fill(0);

   // Stack for depth-first search.  This is declared outside of the loops
   // to avoid repeated allocation.
   std::vector<std::pair<int, int>> visit_stack;

   for(int i = 0; i < kWidth; i++)
   {
      for(int j = 0; j < static_cast<int>(grid[i].size()); j++)
      {
         // Perform depth-first search starting at current cell.
         const Color color = grid[i][j];
         clusters.push_back(Cluster());
         Cluster *sub_cluster = &clusters.back();

         visit_stack.clear();
         visit_stack.push_back({i, j});
         while( !visit_stack.empty() )
         {
            const std::pair<int, int> cursor = visit_stack.back();
            visit_stack.pop_back();
            if( cursor.first < 0 ||
                cursor.second < 0 ||
                cursor.first >= kWidth ||
                cursor.second >= static_cast<int>(grid[cursor.first].size()) ||
                grid[cursor.first][cursor.second] != color ||
                (visited[cursor.second] & (1U << cursor.first)) != 0 )
            {
               continue;
            }
            visited[cursor.second] |= 1U << cursor.first;
            sub_cluster->push_back(cursor);
            visit_stack.push_back({cursor.first + 1, cursor.second});
            visit_stack.push_back({cursor.first - 1, cursor.second});
            visit_stack.push_back({cursor.first, cursor.second + 1});
            visit_stack.push_back({cursor.first, cursor.second - 1});
         }
         if( sub_cluster->empty() )
            clusters.pop_back();
      }
   }
   return clusters;
}

// Apply a series of movements to pending block.
void ApplyMoves(const Grid &grid, const std::string &moves, PendingBlock *block)
{
   for(char m : moves)
      MovePendingBlock(grid, m, block);
}

// Drop block onto grid, apply chains, and return change in score.
int DropBlock(const PendingBlock &block, Grid *grid)
{
   struct ScalarScore
   {
      inline void Add(int delta) { score += delta; }

      int score = 0;
   };
   return DropBlockAndUpdateScore<ScalarScore>(block, grid).score;
}

// Drop block onto grid, apply chains, and return all changes in score.
std::vector<int> TraceDropBlock(const PendingBlock &block, Grid *grid)
{
   struct VectorScore
   {
      inline void Add(int delta) { scores.push_back(delta); }

      std::vector<int> scores;
   };
   return DropBlockAndUpdateScore<VectorScore>(block, grid).scores;
}