#include "gamestate.h"

#include <SDL_ttf.h>

#include <algorithm>
#include <bitset>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <set>
#include <sstream>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include "highscore.h"
#include "hslist.h"
#include "mazeoflife.h"
#include "titlestate.h"
#include "util.h"

class GameBoard {
 public:
  GameBoard(int level, int playerx, int playery);
  void tick(int playerx, int playery);
  void render(SDL_Renderer* renderer, int level) const;
  bool isObstructed(int x, int y) const;
  bool operator<(const GameBoard& other) const;

  using coord = std::tuple<int, int>;

 private:
  void initialize(int level);
  bool solve(int playerx, int playery) const;
  std::string dump() const;

  using board_type = std::bitset<WIDTH * HEIGHT>;

  void incrementIfNeighbor(int x, int y, const board_type& temp, int playerx,
                           int playery, int& tick) const;

  bool applyNeighbors(int x, int y, const board_type& temp, int playerx,
                      int playery) const;

  board_type blocks;
  board_type updateable;
  int oldx;
  int oldy;
};

class LoadGameState : public State {
 public:
  LoadGameState(int level);
  State* operator()(SDL_Window* window, SDL_Renderer* renderer);

 private:
  int level;
};

class PlayGameState : public State {
 public:
  PlayGameState(int level, GameBoard* board, int playerx, int playery);
  State* operator()(SDL_Window* window, SDL_Renderer* renderer);

 private:
  bool move(int x, int y);
  int level;
  GameBoard* board;
  int playerx;
  int playery;
};

void setRendererAliveColor(SDL_Renderer* renderer, int level) {
  switch ((level / 10) % 5) {
    case 0:
      SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255);
      break;  // Black
    case 1:
      SDL_SetRenderDrawColor(renderer, 255, 0, 0, 255);
      break;  // Red
    case 2:
      SDL_SetRenderDrawColor(renderer, 0, 255, 0, 255);
      break;  // Green
    case 3:
      SDL_SetRenderDrawColor(renderer, 85, 85, 85, 255);
      break;  // Dark Gray
    case 4:
      SDL_SetRenderDrawColor(renderer, 255, 0, 255, 255);
      break;  // Magenta
  }
}

void setRendererDeadColor(SDL_Renderer* renderer, int level) {
  switch ((level / 10) % 5) {
    case 0:
      SDL_SetRenderDrawColor(renderer, 255, 255, 255, 255);
      break;  // White
    case 1:
      SDL_SetRenderDrawColor(renderer, 255, 192, 203, 255);
      break;  // Pink
    case 2:
      SDL_SetRenderDrawColor(renderer, 0, 255, 255, 255);
      break;  // Cyan
    case 3:
      SDL_SetRenderDrawColor(renderer, 170, 170, 170, 255);
      break;  // Light Gray
    case 4:
      SDL_SetRenderDrawColor(renderer, 255, 128, 0, 255);
      break;  // Orange
  }
}

void GameBoard::incrementIfNeighbor(int x, int y, const board_type& temp,
                                    int playerx, int playery, int& tick) const {
  int nx = x;
  int ny = y;

  wrap(x, y);

  if (!((nx != x) && (ny != y))) {
    if ((temp[x + y * WIDTH]) || ((playerx == x) && (playery == y)) ||
        ((x == 15) && (y == 15))) {
      ++tick;
    }
  }
}

State* GameState::operator()(SDL_Window* window, SDL_Renderer* renderer) {
  return new LoadGameState(0);
}

LoadGameState::LoadGameState(int m_level) { level = m_level; }

State* LoadGameState::operator()(SDL_Window* window, SDL_Renderer* renderer) {
  char* wintitle = new char[50];
  sprintf(wintitle, "Maze Of Life - Level %d", level);
  SDL_SetWindowTitle(window, wintitle);

  // Randomly place the player in a corner
  int playerx, playery;
  switch (rand() % 4) {
    case 0:
      playerx = 1;
      playery = 1;
      break;
    case 1:
      playerx = 1;
      playery = HEIGHT - 2;
      break;
    case 2:
      playerx = WIDTH - 2;
      playery = HEIGHT - 2;
      break;
    case 3:
      playerx = WIDTH - 2;
      playery = 1;
      break;
  }

  // Display the level number
  setRendererDeadColor(renderer, level);
  SDL_RenderClear(renderer);

  TTF_Font* font = loadFont(100);
  SDL_Color fontColor = {0, 0, 0, 0};
  char levelnum[8];
  sprintf(levelnum, "%d", level);
  SDL_Surface* dispsurf = TTF_RenderText_Solid(font, levelnum, fontColor);
  SDL_Texture* disptext = SDL_CreateTextureFromSurface(renderer, dispsurf);
  SDL_FreeSurface(dispsurf);

  SDL_Rect pos;
  SDL_QueryTexture(disptext, NULL, NULL, &pos.w, &pos.h);
  pos.x = 240 - (pos.w / 2);
  pos.y = 240 - (pos.h / 2);

  SDL_RenderCopy(renderer, disptext, NULL, &pos);
  SDL_RenderPresent(renderer);

  // Do 50 gens of Conway
  GameBoard* board = new GameBoard(level, playerx, playery);

  // Wait a bit
  SDL_Delay(500);

  // Start the level
  return new PlayGameState(level, board, playerx, playery);
}

PlayGameState::PlayGameState(int m_level, GameBoard* m_board, int m_playerx,
                             int m_playery) {
  level = m_level;
  board = m_board;
  playerx = m_playerx;
  playery = m_playery;
}

State* PlayGameState::operator()(SDL_Window* window, SDL_Renderer* renderer) {
  SDL_Event e;

  for (;;) {
    // Tick board
    board->tick(playerx, playery);

    // Paint board
    board->render(renderer, level);

    // Paint event
    SDL_Rect block;
    block.w = 16;
    block.h = 16;
    block.x = 15 * 16;
    block.y = 15 * 16;
    SDL_SetRenderDrawColor(renderer, 0, 0, 255, 255);
    SDL_RenderFillRect(renderer, &block);

    // Paint player
    block.x = playerx * 16;
    block.y = playery * 16;
    SDL_SetRenderDrawColor(renderer, 255, 255, 0, 255);
    SDL_RenderFillRect(renderer, &block);

    SDL_RenderPresent(renderer);

    while (SDL_PollEvent(&e)) {
      if (e.type == SDL_QUIT) {
        return NULL;
      } else if (e.type == SDL_KEYDOWN) {
        switch (e.key.keysym.sym) {
          case SDLK_LEFT:
            if (move(playerx - 1, playery)) {
              return new LoadGameState(level + 1);
            } else {
              break;
            }

          case SDLK_RIGHT:
            if (move(playerx + 1, playery)) {
              return new LoadGameState(level + 1);
            } else {
              break;
            }

          case SDLK_UP:
            if (move(playerx, playery - 1)) {
              return new LoadGameState(level + 1);
            } else {
              break;
            }

          case SDLK_DOWN:
            if (move(playerx, playery + 1)) {
              return new LoadGameState(level + 1);
            } else {
              break;
            }

          case SDLK_ESCAPE:
            SDL_SetWindowTitle(window, "");

            std::ifstream exists(getDataFile());
            if (exists) {
              FILE* hslist = fopen(getDataFile(), "r");
              int scores;
              Highscore* h;

              fscanf(hslist, "%d%*c", &scores);

              if (scores < 10) {
                fclose(hslist);

                return new EnterHighscoreState(level);
              } else {
                for (int i = 0; i < scores; i++) {
                  int namelen;
                  char namelens[4];
                  char* name = (char*)calloc(25, sizeof(char));
                  int score;

                  fscanf(hslist, "%d", &namelen);
                  sprintf(namelens, "%%%dc", namelen);
                  fscanf(hslist, namelens, name);
                  fscanf(hslist, "%d%*c", &score);

                  h = new Highscore(name, score);
                }

                fclose(hslist);

                if (h->getLevel() < level) {
                  return new EnterHighscoreState(level);
                } else {
                  return new DisplayAndReturnLocalHighscoreListState();
                }
              }
            } else {
              return new EnterHighscoreState(level);
            }
        }
      }
    }

    SDL_Delay(5);
  }
}

bool PlayGameState::move(int x, int y) {
  wrap(x, y);

  // Are we at the event?
  if ((x == 15) && (y == 15)) {
    return true;
  }

  // Can we even go there?
  if (!board->isObstructed(x, y)) {
    playerx = x;
    playery = y;
  }

  return false;
}

GameBoard::GameBoard(int level, int playerx, int playery) {
  for (;;) {
    initialize(level);
    updateable.set();
    oldx = playerx;
    oldy = playery;

    for (int i = 0; i < 50; i++) {
      tick(playerx, playery);
    }

    if (solve(playerx, playery)) {
      break;
    } else {
      std::cout << "Impossible board: " << playerx << "," << playery << ","
                << dump() << std::endl;
    }
  }
}

void GameBoard::tick(int playerx, int playery) {
  board_type temp{blocks};
  board_type tempdateable{updateable};
  if ((playerx != oldx) || (playery != oldy)) {
    for (int dy = -1; dy <= 1; dy++) {
      for (int dx = -1; dx <= 1; dx++) {
        int tdx = oldx + dx;
        int tdy = oldy + dy;
        wrap(tdx, tdy);
        tempdateable.set(tdx + tdy * WIDTH);

        tdx = playerx + dx;
        tdy = playery + dy;
        wrap(tdx, tdy);
        tempdateable.set(tdx + tdy * WIDTH);
      }
    }
  }

  oldx = playerx;
  oldy = playery;

  updateable.reset();

  for (int y = 0; y < HEIGHT; y++) {
    for (int x = 0; x < WIDTH; x++) {
      if (((x == 15) && (y == 15)) || (!tempdateable[x + y * WIDTH])) {
        continue;
      }

      blocks[x + y * WIDTH] = applyNeighbors(x, y, temp, playerx, playery);

      if (temp[x + y * WIDTH] != blocks[x + y * WIDTH]) {
        for (int dy = -1; dy <= 1; dy++) {
          for (int dx = -1; dx <= 1; dx++) {
            int tdx = x + dx;
            int tdy = y + dy;
            wrap(tdx, tdy);
            updateable.set(tdx + tdy * WIDTH);
          }
        }
      }
    }
  }
}

bool GameBoard::applyNeighbors(int x, int y, const board_type& temp,
                               int playerx, int playery) const {
  int neighbors = 0;

  incrementIfNeighbor(x - 1, y - 1, temp, playerx, playery, neighbors);
  incrementIfNeighbor(x - 1, y, temp, playerx, playery, neighbors);
  incrementIfNeighbor(x - 1, y + 1, temp, playerx, playery, neighbors);
  incrementIfNeighbor(x, y - 1, temp, playerx, playery, neighbors);
  incrementIfNeighbor(x, y + 1, temp, playerx, playery, neighbors);
  incrementIfNeighbor(x + 1, y - 1, temp, playerx, playery, neighbors);
  incrementIfNeighbor(x + 1, y, temp, playerx, playery, neighbors);
  incrementIfNeighbor(x + 1, y + 1, temp, playerx, playery, neighbors);

  if (temp[x + y * WIDTH]) {
    return ((neighbors >= 1) && (neighbors <= 4));
  } else {
    return (neighbors == 3);
  }
}

void GameBoard::render(SDL_Renderer* renderer, int level) const {
  SDL_Rect block;
  block.w = 16;
  block.h = 16;

  for (int y = 0; y < HEIGHT; y++) {
    for (int x = 0; x < WIDTH; x++) {
      block.x = x * 16;
      block.y = y * 16;

      if (blocks[x + y * WIDTH]) {
        setRendererAliveColor(renderer, level);
      } else {
        setRendererDeadColor(renderer, level);
      }

      SDL_RenderFillRect(renderer, &block);
    }
  }
}

bool GameBoard::isObstructed(int x, int y) const {
  return blocks[x + y * WIDTH] || (x == 15 && y == 15);
}

void GameBoard::initialize(int level) {
  for (int y = 0; y < HEIGHT; y++) {
    for (int x = 0; x < WIDTH; x++) {
      blocks[x + y * WIDTH] = false;

      switch (level / 10 + 1) {
        case 1:
          if ((x > 13) && (x < 17) && (y > 13) && (y < 17)) {
            blocks[x + y * WIDTH] = rand() % 2;
          }
          break;
        case 2:
        case 3:
          if ((x > 12) && (x < 18) && (y > 12) && (y < 18)) {
            blocks[x + y * WIDTH] = rand() % 2;
          }
          break;
        case 4:
        case 5:
          if ((x > 11) && (x < 19) && (y > 11) && (y < 19)) {
            blocks[x + y * WIDTH] = rand() % 2;
          }
          break;
        default:
          blocks[x + y * WIDTH] = rand() % 2;
      }
    }
  }

  blocks[15 + 15 * WIDTH] = false;
}

bool GameBoard::operator<(const GameBoard& other) const {
  for (int i = WIDTH * HEIGHT - 1; i >= 0; i--) {
    if (blocks[i] ^ other.blocks[i]) {
      return other.blocks[i];
    }
  }

  return false;
}

bool GameBoard::solve(int playerx, int playery) const {
  std::deque<std::tuple<GameBoard, coord, int>> search;
  std::unordered_map<board_type, board_type> done;

  // Assume that the player will not move while the board is changing, so tick
  // the board until it either stops changing, or it reaches a state that it has
  // already been in (in the case of alternating systems).
  {
    GameBoard original = *this;

    std::unordered_set<board_type> pastStates;
    pastStates.insert(original.blocks);

    while (original.updateable.any()) {
      original.tick(playerx, playery);

      if (pastStates.count(original.blocks)) {
        break;
      }

      pastStates.insert(original.blocks);
    }

    search.emplace_front(std::move(original), coord{playerx, playery}, 0);
  }

  // Use breadth first search to find a solution.
  bool exists = false;
  while (!search.empty()) {
    auto cur = std::move(search.front());
    search.pop_front();

    GameBoard& cbr = std::get<0>(cur);
    coord& cpl = std::get<1>(cur);
    int cns = std::get<2>(cur);

    // If it has been over 100 generations, give up.
    if (cns > 100) {
      continue;
    }

    int cplx = std::get<0>(cpl);
    int cply = std::get<1>(cpl);

    // If this section of this board state has already been checked, skip it.
    if (done.count(cbr.blocks) && done.at(cbr.blocks)[cplx + cply * WIDTH]) {
      continue;
    }

    // Use a flood fill to find a set of positions accessible to the player
    // without modifying the board state, as well as a set of positions adjacent
    // to the flood that /will/ modify the board state.
    board_type flood;
    std::deque<coord> front;
    front.push_front(cpl);
    flood[cplx + cply * WIDTH] = true;

    std::set<coord> edges;

    while (!front.empty()) {
      coord frontLoc = std::move(front.front());
      front.pop_front();

      // Iterate over the positions 4-adjacent to the current one.
      for (coord& fc : std::list<coord>{
               {std::get<0>(frontLoc) - 1, std::get<1>(frontLoc)},
               {std::get<0>(frontLoc) + 1, std::get<1>(frontLoc)},
               {std::get<0>(frontLoc), std::get<1>(frontLoc) - 1},
               {std::get<0>(frontLoc), std::get<1>(frontLoc) + 1},
           }) {
        wrap(std::get<0>(fc), std::get<1>(fc));
        int fcx = std::get<0>(fc);
        int fcy = std::get<1>(fc);

        // If this position is already in the flood, skip it.
        if (flood[fcx + fcy * WIDTH]) {
          continue;
        }

        // If the player could not move into this position, skip it.
        if (cbr.isObstructed(fcx, fcy)) {
          continue;
        }

        // If this position is adjacent to the event, then the board is
        // solvable.
        if (((fcx == 15) && ((fcy == 14) || (fcy == 16))) ||
            ((fcy == 15) && ((fcx == 14) || (fcx == 16)))) {
          exists = true;
          break;
        }

        // Check if the player moving would cause any positions 8-adjacent to
        // the start or end positions to change. This is more efficient than
        // copying the board state and then running tick.
        bool changed = false;
        for (int dy = -1; dy <= 1; dy++) {
          for (int dx = -1; dx <= 1; dx++) {
            if (dx == 0 && dy == 0) {
              continue;
            }

            int cpldx = cplx + dx;
            int cpldy = cply + dy;
            wrap(cpldx, cpldy);

            if (cbr.isObstructed(cpldx, cpldy) !=
                applyNeighbors(cpldx, cpldy, cbr.blocks, fcx, fcy)) {
              changed = true;
              break;
            }

            int fcxdx = fcx + dx;
            int fcydy = fcy + dy;
            wrap(fcxdx, fcydy);

            if (cbr.isObstructed(fcxdx, fcydy) !=
                applyNeighbors(fcxdx, fcydy, cbr.blocks, fcx, fcy)) {
              changed = true;
              break;
            }
          }

          if (changed) {
            break;
          }
        }

        // If moving to this position would change the board state, add it to
        // the set of edges; otherwise, add it to the flood and the flood front.
        if (changed) {
          edges.insert(fc);
        } else {
          flood[fcx + fcy * WIDTH] = true;
          front.push_back(fc);
        }
      }

      if (exists) {
        break;
      }
    }

    if (exists) {
      break;
    }

    // Add the flood to the set of checked positions for this board state.
    done[cbr.blocks] |= flood;

    // Add the edges to the search queue.
    for (const coord& newLoc : edges) {
      GameBoard nextState1 = cbr;
      nextState1.tick(std::get<0>(newLoc), std::get<1>(newLoc));

      // Assume that the player will not move while the board is changing, so
      // tick the board until it either stops changing, or it reaches a state
      // that it has already been in (in the case of alternating systems).
      std::unordered_set<board_type> pastStates;
      pastStates.insert(nextState1.blocks);

      while (nextState1.updateable.any()) {
        nextState1.tick(std::get<0>(newLoc), std::get<1>(newLoc));

        if (pastStates.count(nextState1.blocks)) {
          break;
        }

        pastStates.insert(nextState1.blocks);
      }

      if (!done.count(nextState1.blocks) ||
          !done.at(nextState1.blocks)[std::get<0>(newLoc) +
                                      std::get<1>(newLoc) * WIDTH]) {
        search.emplace_back(std::move(nextState1), newLoc, cns + 1);
      }
    }
  }

  return exists;
}

std::string GameBoard::dump() const {
  std::stringstream output;
  output << std::hex;
  for (int i = 0; i < WIDTH * HEIGHT / 4; i++) {
    int chunk = (8 * blocks[i * 4]) + (4 * blocks[i * 4 + 1]) +
                (2 * blocks[i * 4 + 2]) + blocks[i * 4 + 3];
    output << chunk;
  }

  return output.str();
}