#include "game_tools.h"

#include <assert.h>
#include <stdlib.h>

#include "game_aux.h"
#include "game_struct.h"

// @copyright University of Bordeaux. All rights reserved, 2024.

/* ************************************************************************** */

/** @brief Hard-coding of pieces (shape & orientation) in an integer array.
 * @details The 4 least significant bits encode the presence of an half-edge in
 * the N-E-S-W directions (in that order). Thus, binary coding 1100 represents
 * the piece "└" (a corner in north orientation).
 */
static uint _code[NB_SHAPES][NB_DIRS] = {
    {0b0000, 0b0000, 0b0000, 0b0000},  // EMPTY {" ", " ", " ", " "}
    {0b1000, 0b0100, 0b0010, 0b0001},  // ENDPOINT {"^", ">", "v", "<"},
    {0b1010, 0b0101, 0b1010, 0b0101},  // SEGMENT {"|", "-", "|", "-"},
    {0b1100, 0b0110, 0b0011, 0b1001},  // CORNER {"└", "┌", "┐", "┘"}
    {0b1101, 0b1110, 0b0111, 0b1011},  // TEE {"┴", "├", "┬", "┤"}
    {0b1111, 0b1111, 0b1111, 0b1111}   // CROSS {"+", "+", "+", "+"}
};

/* ************************************************************************** */

/** encode a shape and an orientation into an integer code */
static uint _encode_shape(shape s, direction o) { return _code[s][o]; }

/* ************************************************************************** */

/** decode an integer code into a shape and an orientation */
static bool _decode_shape(uint code, shape* s, direction* o) {
  assert(code >= 0 && code < 16);
  assert(s);
  assert(o);
  for (int i = 0; i < NB_SHAPES; i++)
    for (int j = 0; j < NB_DIRS; j++)
      if (code == _code[i][j]) {
        *s = i;
        *o = j;
        return true;
      }
  return false;
}

/* ************************************************************************** */

/** add an half-edge in the direction d */
static void _add_half_edge(game g, uint i, uint j, direction d) {
  assert(g);
  assert(i < game_nb_rows(g));
  assert(j < game_nb_cols(g));
  assert(d < NB_DIRS);

  shape s = game_get_piece_shape(g, i, j);
  direction o = game_get_piece_orientation(g, i, j);
  uint code = _encode_shape(s, o);
  uint mask = 0b1000 >> d;     // mask with half-edge in the direction d
  assert((code & mask) == 0);  // check there is no half-edge in the direction d
  uint newcode = code | mask;  // add the half-edge in the direction d
  shape news;
  direction newo;
  assert(_decode_shape(newcode, &news, &newo));
  game_set_piece_shape(g, i, j, news);
  game_set_piece_orientation(g, i, j, newo);
}

/* ************************************************************************** */

#define OPPOSITE_DIR(d) ((d + 2) % NB_DIRS)

/* ************************************************************************** */

/**
 * @brief Add an edge between two adjacent squares.
 * @details This is done by modifying the pieces of the two adjacent squares.
 * More precisely, we add an half-edge to each adjacent square, so as to build
 * an edge between these two squares.
 * @param g the game
 * @param i row index
 * @param j column index
 * @param d the direction of the adjacent square
 * @pre @p g must be a valid pointer toward a game structure.
 * @pre @p i < game height
 * @pre @p j < game width
 * @return true if an edge can be added, false otherwise
 */
static bool _add_edge(game g, uint i, uint j, direction d) {
  assert(g);
  assert(i < game_nb_rows(g));
  assert(j < game_nb_cols(g));
  assert(d < NB_DIRS);

  uint nexti, nextj;
  bool next = game_get_ajacent_square(g, i, j, d, &nexti, &nextj);
  if (!next) return false;

  // check if the two half-edges are free
  bool he = game_has_half_edge(g, i, j, d);
  if (he) return false;
  bool next_he = game_has_half_edge(g, nexti, nextj, OPPOSITE_DIR(d));
  if (next_he) return false;

  _add_half_edge(g, i, j, d);
  _add_half_edge(g, nexti, nextj, OPPOSITE_DIR(d));

  return true;
}

/* ************************************************************************** */

void verify_p(void* p, char* msg);
void verify_val_range(uint val, uint min, uint max, char* msg);

game game_load(char* filename) {
  FILE* f = fopen(filename, "r");
  verify_p((void*)f, "Can't open the file in game_load.");
  uint nb_rows, nb_cols, wrapping;
  fscanf(f, "%u %u %d\n", &nb_rows, &nb_cols, &wrapping);
  verify_val_range(nb_rows, 1, -1, "Invalid number of rows in game_load.");
  verify_val_range(nb_cols, 1, -1, "Invalid number of cols in game_load.");
  game g = game_new_empty_ext(nb_rows, nb_cols, wrapping);
  verify_p((void*)g, "game not created in game_load.");
  for (uint row = 0; row < nb_rows; row++) {
    for (uint col = 0; col < nb_cols; col++) {
      char s, o;
      fscanf(f, "%c%c ", &s, &o);
      switch (s) {  // load the piece shape based on the char in the file
        case 'E':
          game_set_piece_shape(g, row, col, EMPTY);
          break;
        case 'N':
          game_set_piece_shape(g, row, col, ENDPOINT);
          break;
        case 'S':
          game_set_piece_shape(g, row, col, SEGMENT);
          break;
        case 'C':
          game_set_piece_shape(g, row, col, CORNER);
          break;
        case 'T':
          game_set_piece_shape(g, row, col, TEE);
          break;
        case 'X':
          game_set_piece_shape(g, row, col, CROSS);
          break;
        default:
          fprintf(stderr, "game_load read an invalid shape!\n");
          exit(EXIT_FAILURE);
      };
      switch (o) {  // load the piece orientation based on the char in the file
        case 'N':
          game_set_piece_orientation(g, row, col, NORTH);
          break;
        case 'S':
          game_set_piece_orientation(g, row, col, SOUTH);
          break;
        case 'E':
          game_set_piece_orientation(g, row, col, EAST);
          break;
        case 'W':
          game_set_piece_orientation(g, row, col, WEST);
          break;
        default:
          fprintf(stderr, "game_load read an invalid orientation!\n");
          exit(EXIT_FAILURE);
      };
    }
    fscanf(f, "\n");
  }
  fclose(f);
  printf("\nFile %s loaded\n\n", filename);
  return g;
}

void game_save(cgame g, char* filename) {
  verify_p((void*)g, "Null pointer for game_save.");
  verify_p((void*)filename, "Null filename for game_save.");
  FILE* stream = fopen(filename, "w");
  fprintf(stream, "%d %d %d\n", game_nb_rows(g), game_nb_cols(g),
          game_is_wrapping(g));
  for (unsigned int i = 0; i < game_nb_rows(g); i++) {
    for (unsigned int j = 0; j < game_nb_cols(g); j++) {
      // save the piece shape in a char on the file
      switch (game_get_piece_shape(g, i, j)) {
        case EMPTY:
          fprintf(stream, "E");
          break;
        case ENDPOINT:
          fprintf(stream, "N");
          break;
        case SEGMENT:
          fprintf(stream, "S");
          break;
        case CORNER:
          fprintf(stream, "C");
          break;
        case TEE:
          fprintf(stream, "T");
          break;
        case CROSS:
          fprintf(stream, "X");
          break;
        default:
          break;
      };
      // save the piece orientation in a char on the file
      switch (game_get_piece_orientation(g, i, j)) {
        case NORTH:
          fprintf(stream, "N");
          break;
        case EAST:
          fprintf(stream, "E");
          break;
        case SOUTH:
          fprintf(stream, "S");
          break;
        case WEST:
          fprintf(stream, "W");
          break;
        default:
          break;
      };
      fprintf(stream, " ");
    }
    fprintf(stream, "\n");
  }
  fclose(stream);
  printf("Game saved as %s!\n", filename);
}

/**
 * @brief Search for the position inside the table.
 * @param candidate table which contains the position of the non-empty pieces
 * @param pos the position of the piece inside the game
 * @param nb_pieces the number of candidate pieces.
 * @pre @p candidate must be a valid pointer toward a uint table.
 * @pre @p pos < nb_cols*nb_rows
 * @pre @p nb_pieces < (nb_cols*nb_rows - nb_empty)
 * @return the index if the piece is a candidate, -1 otherwise
 */
int index_candidate(uint* candidate, uint pos, uint* nb_pieces) {
  int i = 0;
  while (i < *nb_pieces && candidate[i] != pos) {
    i++;
  }
  if (i == *nb_pieces) i = -1;
  return i;
}

/**
 * @brief Add the coordinates of a piece (new candidate).
 * @param candidate table which contains the position of the non-empty pieces
 * @param pos the position of the piece inside the game
 * @param nb_pieces the number of candidate pieces.
 * @pre @p candidate must be a valid pointer toward a uint table.
 * @pre @p pos < nb_cols*nb_rows
 * @pre @p nb_pieces < (nb_cols*nb_rows - nb_empty)
 */
void add_candidate(uint* candidate, uint pos, uint* nb_pieces) {
  candidate[*nb_pieces] = pos;
  (*nb_pieces)++;
}

/**
 * @brief Creates a random game solution with a given size and options.
 * @param nb_rows number of rows in game
 * @param nb_cols number of columns in game
 * @param wrapping wrapping option
 * @param nb_empty number of empty squares
 * @param nb_extra number of extra edges, that make cycles (if possible)
 * @pre nb_cols * nb_rows >= 2
 * @pre nb_empty <= (nb_cols * nb_rows - 2)
 * @pre nb_extra must be small enough compared to the number of non-empty
 * squares
 * @return the generated random game (or NULL in case of error)
 */
game game_random(uint nb_rows, uint nb_cols, bool wrapping, uint nb_empty,
                 uint nb_extra) {
  // We need to verify if there isn't too many extra:
  int nb_hedge_possible;
  // When the game is created without loop, each connection create 2 half edges,
  // we remove 2 for the start and end (ex: >< = 1 connection)
  int nb_hedge_linked = (nb_rows * nb_cols - nb_empty - 1) * 2;
  if (wrapping) {
    // when wrapping is true, every piece can have 4 half edges
    nb_hedge_possible = (nb_rows * nb_cols - nb_empty) * 4;
  } else {
    // Otherwise, every corner of the game has 2 half edges, those on the side
    // have 3, and the other 4
    // We can't predict if the empty piece will be on the side or the middle, so
    // we will remove 4 half edge for each empty piece
    nb_hedge_possible = ((nb_rows - 2) * 2 + (nb_cols - 2) * 2) * 3 + 4 * 2 +
                        (nb_rows - 2) * (nb_cols - 2) * 4 - nb_empty * 4;
  }
  if (nb_rows * nb_cols - nb_empty < 2 ||
      nb_extra > (nb_hedge_possible - nb_hedge_linked) / 2)
    return NULL;
  game g = game_new_empty_ext(nb_rows, nb_cols, wrapping);
  uint candidate[(nb_cols * nb_rows) - nb_empty];
  uint nb_piece = 0;
  uint i, j, d, inext = 0, jnext = 0;
  do {
    i = rand() % nb_rows;
    j = rand() % nb_cols;
    d = rand() % NB_DIRS;
    // If the next piece is identical to the selected piece or if we cannot add
    // an edge
  } while (!(game_get_ajacent_square(g, i, j, d, &inext, &jnext) &&
             (i != inext || j != jnext)) ||
           !_add_edge(g, i, j, d));
  add_candidate(candidate, i * nb_cols + j, &nb_piece);
  add_candidate(candidate, inext * nb_cols + jnext, &nb_piece);

  while (nb_piece < (nb_cols * nb_rows) - nb_empty || nb_extra > 0) {
    // We choose a piece from the candidate
    uint pos = rand() % nb_piece;
    i = candidate[pos] / nb_cols;
    j = candidate[pos] % nb_cols;
    uint d = rand() % NB_DIRS;
    // Check if we can get the adjacent piece
    if (game_get_ajacent_square(g, i, j, d, &inext, &jnext)) {
      // Check if the adjacent piece is not already candidate
      if (game_get_piece_shape(g, inext, jnext) == EMPTY) {
        if (nb_piece < (nb_cols * nb_rows)) {
          _add_edge(g, i, j, d);
          add_candidate(candidate, inext * nb_cols + jnext, &nb_piece);
        }
      }
      // Check if we need to add an extra and if we can
      else if (nb_extra > 0 && _add_edge(g, i, j, d)) {
        nb_extra--;
      }
    }
  }

  return g;
}

bool solver_mismatch(cgame g, uint pos, uint nb_rows, uint nb_cols, bool wrap) {
  uint row = pos / nb_cols, col = pos % nb_cols;
  if (row != 0 || !wrap) {
    if (game_check_edge(g, row, col, NORTH) == MISMATCH) return true;
  }
  if (row == nb_rows - 1 && game_check_edge(g, row, col, SOUTH) == MISMATCH)
    return true;
  if (col != 0 || !wrap) {
    if (game_check_edge(g, row, col, WEST) == MISMATCH) return true;
  }
  if (col == nb_cols - 1 && game_check_edge(g, row, col, EAST) == MISMATCH)
    return true;
  return false;
}

void solver_rec(game g, int pos, int len, bool* solution, bool findall,
                uint* nbsolutions) {
  // if we have a solution we end everything
  if (*solution) return;

  if (pos == len) {
    // We don't need to use game_is_well paired, because we know that everything
    // is already well_paired
    if (game_is_connected(g)) {
      if (findall) {
        *nbsolutions = *nbsolutions + 1;
      } else {
        *solution = true;
      }
    }
    return;
  }
  bool wrap = game_is_wrapping(g);
  int nb_cols = game_nb_cols(g), nb_rows = game_nb_rows(g);
  if (g->shapes[pos] == CROSS || g->shapes[pos] == EMPTY) {
    if (!solver_mismatch(g, pos, nb_rows, nb_cols, wrap)) {
      solver_rec(g, pos + 1, len, solution, findall, nbsolutions);
    }
  } else if (g->shapes[pos] == SEGMENT) {
    if (!solver_mismatch(g, pos, nb_rows, nb_cols, wrap)) {
      solver_rec(g, pos + 1, len, solution, findall, nbsolutions);
      if (*solution) return;
    }
    g->directions[pos] = (g->directions[pos] + 1) % NB_DIRS;
    if (!solver_mismatch(g, pos, nb_rows, nb_cols, wrap)) {
      solver_rec(g, pos + 1, len, solution, findall, nbsolutions);
    }
  } else {
    for (int d = 0; d < NB_DIRS; d++) {
      if (!solver_mismatch(g, pos, nb_rows, nb_cols, wrap)) {
        solver_rec(g, pos + 1, len, solution, findall, nbsolutions);
        if (*solution) return;
      }
      g->directions[pos] = (g->directions[pos] + 1) % NB_DIRS;
    }
  }
}

bool game_solve(game g) {
  verify_p((void*)g, "Null game pointer in game_solve");
  game tosolve = game_copy(g);
  bool solutionfound = false;
  solver_rec(tosolve, 0, game_nb_cols(tosolve) * game_nb_rows(tosolve),
             &solutionfound, false, NULL);
  if (solutionfound) {
    struct game_s tmp = *g;
    *g = *tosolve;
    *tosolve = tmp;
    game_delete(tosolve);
    return true;
  } else {
    game_delete(tosolve);
    return false;
  }
}

uint game_nb_solutions(cgame g) {
  verify_p((void*)g, "Null game pointer in game_nb_solutions");
  game tosolve = game_copy(g);

  bool solutionfound = false;
  uint nbsolutions = 0;
  solver_rec(tosolve, 0, game_nb_cols(tosolve) * game_nb_rows(tosolve),
             &solutionfound, true, &nbsolutions);
  game_delete(tosolve);
  return nbsolutions;
}