/*****************************************************
 **                                                 **
 **     CSC444F - Software Engineering              **
 **     Board Management and Scoring Module         **
 **                                                 **
 **     Team name:   NoName[tm]                     **
 **     Tutorial:    Delta                          **
 **                                                 **
 **     Members:     Ian Chesal, Jacob Dalton,      **
 **                  Peter Yeung, Ketan Padalia     **
 **                                                 **
 *****************************************************/


/* FILE: bms.c
 *
 * This module stores the current state of the board and
 * provides a functional interface to other modules to make
 * changes to the current board state.  It is also responsible
 * for checking the validity and calculating the score of a new
 * move.
 *
 * One important note: all routines that return boolean values
 * use the integer type and return 1 or 0 instead.  This is done
 * to allow ease of use by any external code that is calling these
 * routines.
 *
 * One assumption in the code that needs to be verified is that
 * one-tile words are invalid.  Although a one-tile move can be made
 * and it will be called legal, the scoring code currently ignores
 * such words.  This "on the fence" attitude must be corrected soon!
 *
 * Note that the coordinate system we use has (0,0) in the top-left
 * corner of the board.
 *
 *    - Ketan, September 26, 2000
 */


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
#include <string.h>
#include <strings.h>
#include <ctype.h>
#include "bms.h"



/************** Types and defines local to this module **********************/


#define MY_MIN(x,y) (((x) < (y)) ? (x) : (y))
#define MY_MAX(x,y) (((x) > (y)) ? (x) : (y))

/* These are redefinitions of max and min.  They were needed
 * because UNIX compilers look for max/min in sys/ddi.h
 * while Windows ones use stdlib.h.
 */


#define BMS_HUGE_INT 1000

/* This number is used to represent a huge number relative to the board
 * coordinates -- must be greater than max(BOARD_X_SIZE,BOARD_Y_SIZE).
 */


#define BMS_MAX_WORD_SIZE (MY_MAX(BOARD_X_SIZE, BOARD_Y_SIZE))

/* This is the maximum size a word can be - ie. the larger of the two
 * board dimensions.
 */


#define BMS_BINGO_SCORE_VALUE (50)

/* This is the bonus score given to a "bingo" move -- defined as placing
 * the maximum number of tiles possible (BMS_MAX_MOVES_IN_LIST which is 7
 * in the normal Scrabble game).
 */


typedef enum {
   MOVE_DIR_VERTICAL, MOVE_DIR_HORIZONTAL, MOVE_DIR_INVALID, MOVE_DIR_NONE, NUM_MOVE_DIRS
} e_move_dir;

/* This enumerated type contains the different move directions that are
 * possible -- a vertical arrangement, horizontal, or invalid (meaning
 * that the move direction cannot be specified as either vertical or
 * horizontal -- this is invalid according to the rules of Scrabble).
 */


typedef struct {
   signed char letter;
   int tile_base_value;
   e_score_mults score_multiplier;
} t_tile;

/* This structure describes a single tile on the board.  letter is the letter tile
 * that is currently at that location ('\0' if empty).  score_multiplier is the
 * score multiplier associated with the tile.
 * The tile_base_value field is used to score the letter at this tile.
 * This value should be 0 if the tile is blank.
 */


typedef struct {
   t_tile **tiles; /* [0..BOARD_X_SIZE-1][0..BOARD_Y_SIZE-1] */
} t_board;

/* This structure describes a game board of tiles. */


typedef struct {
   t_word_list word_list;
   int **score_of_letter;  /* [0..word_list.num_words-1][0..strlen(word_list.words[iword])-1] */
   t_grid_loc *word_starts;   /* [0..word_list.num_words-1] */
   e_move_dir *word_dirs;  /* [0..word_list.num_words-1] */
} t_mapped_word_list;

/* This word list is used internally by the BMS module to
 * represent words and the locations at which they exist (or would
 * exist in the context of a proposed move).
 */


/*************** Variables local to this module ******************/


static t_board *bms_board_ptr = NULL;

/* This is the data structure that represents the board inside the game. */


static t_move_list *last_move_ptr = NULL;

/* This structure stores the last move made to the board.
 * Note that if a new board is started by calling InitialiseBoard(),
 * any existing last move will be freed and set to NULL (to indicate
 * that there was no last move.
 */


/************** Subroutine declarations local to this module **********************/


static int bms_grid_loc_valid (t_grid_loc grid_loc);

static void bms_save_move_list (t_move_list *move_list_ptr,
                                t_move_list **saved_list_ptr);

static int bms_move_list_contains_center_of_board (t_move_list move_list);

static int bms_move_list_adjacent_to_existing_tile (t_move_list move_list);

static int bms_move_list_in_line (t_move_list move_list);

static int bms_move_list_to_unique_and_valid_empty_locs (t_move_list move_list);

static int bms_move_list_to_valid_locations (t_move_list move_list);

static int bms_move_list_contains_grid_location (t_move_list move_list,
                                                 t_grid_loc grid_loc);

static int bms_move_list_no_real_gaps (t_move_list move_list);

static void **bms_alloc_matrix (int ncmin, int ncmax, int nrmin, int nrmax,
                                int el_size, int clear);

static void bms_free_matrix (void *vptr, int ncmin, int ncmax, int nrmin,
                             int el_size);

static void bms_get_extent_of_move_list (t_move_list move_list, int *xmin_ptr, int *xmax_ptr,
                                         int *ymin_ptr, int *ymax_ptr);

static e_move_dir bms_get_move_direction (t_move_list move_list);

static void bms_commit_move_list (t_move_list move_list);

static void bms_add_tile_to_board (t_grid_loc grid_loc, signed char letter,
                                   int tile_base_value);

static t_mapped_word_list bms_build_mapped_word_list (t_move_list move_list);

static void bms_add_word_to_mapped_list (t_grid_loc word_start, e_move_dir word_dir,
                                         t_mapped_word_list *list_ptr, t_tile **new_letters);

static void bms_get_string_for_word (t_grid_loc word_start, e_move_dir word_dir,
                                     t_tile **new_letters, signed char *dest_string,
                                     int *letter_base_scores);

static void bms_free_mapped_word_list (t_mapped_word_list list);

static void bms_load_premium_squares (void);

static void bms_assign_premium_value (int x, int y, e_score_mults score_mult);


/************** Exported subroutine definitions **********************/


void setLastMove(t_move_list *a)
 {
  last_move_ptr = a;
 }

int AddBMove (t_move_list BMove) {

/* Given a move list BMove, this routine checks the move for validity.  If it
 * is valid, the routine scores the move, makes it, saves it to last_move, and
 * returns the score.  If the move list is invalid, the routine returns 0 for lack
 * of a better value to return.
 */

   int score;

   if (CheckBMove (BMove)) {
      /* Note that you have to get the score before the move is committed
       * because ScoreBMove assumes the move hasn't been made yet.
       */
      score = ScoreBMove (BMove);
      bms_commit_move_list (BMove);
      bms_save_move_list (&BMove, &last_move_ptr);

      return (score);
   }
   else {
      return (0);
   }
}


void SetNewBoard(t_move a[][BOARD_Y_SIZE]) {
   int i, j;

   for (i = 0; i < BOARD_X_SIZE; i++) {
      for (j = 0; j < BOARD_Y_SIZE; j++) {
         bms_board_ptr->tiles[i][j].letter = a[i][j].letter;
         bms_board_ptr->tiles[i][j].tile_base_value = a[i][j].move_base_value;
        }
   }
}
  

void InitialiseBoard (void) {

/* This routine starts a fresh board (in bms_board_ptr), freeing any previous board that
 * existed.
 */

   int i, j;

   /* Free any existing board */
   if (bms_board_ptr != NULL) {

      /*printf ("\nWarning: Found existing board and freeing it to start a new one.\n");*/

      /* Free the tiles matrix */
      assert (bms_board_ptr->tiles != NULL);
      for (i = 0; i < BOARD_X_SIZE; i++) {
         free (bms_board_ptr->tiles[i]);
      }
      free (bms_board_ptr->tiles);

      /* Now free the board and set to NULL to invalidate */
      free (bms_board_ptr);
      bms_board_ptr = NULL;
   }

   /* Allocate the board */
   bms_board_ptr = (t_board *) malloc (sizeof(t_board));

   /* Allocate the tiles matrix of the board */
   bms_board_ptr->tiles = (t_tile **) malloc (BOARD_X_SIZE * sizeof(t_tile *));
   for (i = 0; i < BOARD_X_SIZE; i++) {
      bms_board_ptr->tiles[i] = (t_tile *) malloc (BOARD_Y_SIZE * sizeof(t_tile));
   }

   /* Initialise the tiles matrix of the board */
   for (i = 0; i < BOARD_X_SIZE; i++) {
      for (j = 0; j < BOARD_Y_SIZE; j++) {
         bms_board_ptr->tiles[i][j].letter = '\0';
         bms_board_ptr->tiles[i][j].tile_base_value = BMS_INVALID;
         /* Initialize to none here although the actual premium values will be
          * loaded later in bms_load_premium_squares().
          */
         bms_board_ptr->tiles[i][j].score_multiplier = BMS_SCORE_MULT_NONE;
      }
   }

   /* Free any existing "last_move" structure */
   if (last_move_ptr != NULL) {
      free (last_move_ptr);
      last_move_ptr = NULL;
   }  

   bms_load_premium_squares();

   return;
}


e_score_mults SquareScore (t_grid_loc GridRef) {

/* Given a grid location GridRef, this routine returns the score
 * mutliplier type for that location.  If the location is invalid
 * or has no multiplier, a multiplier of BMS_SCORE_MULT_NONE is returned.
 */

   if (bms_grid_loc_valid (GridRef) == 1) {
      return (bms_board_ptr->tiles[GridRef.x][GridRef.y].score_multiplier);
   }
   else {
      return (BMS_SCORE_MULT_NONE);
   }
}


int RemoveTile (t_grid_loc GridRef) {

/* Given a grid location GridRef, this routine removes any letter tile
 * that is at that location.  If there is no letter there or if the location
 * represented by GridRef is invalid, we return 0; otherwise we return 1.
 */

   /* If the location is invalid or empty, return 0 */
   if (EmptySquare (GridRef)) {
      return (0);
   }
   else {
      /* Remove the tile */
      bms_board_ptr->tiles[GridRef.x][GridRef.y].letter = '\0';
      bms_board_ptr->tiles[GridRef.x][GridRef.y].tile_base_value = BMS_INVALID;

      return (1);
   }
}

void 
setLastMoveNULL()
 {
  last_move_ptr = NULL;
 } 



int CheckBMove (t_move_list BMove) {

/* Given a list of moves (each move being a tile and a grid location),
 * this routine returns 1 if the move is valid according to the rules
 * in the specifications, and 0 otherwise.
 */

   /* Below are checks that all moves need to make */

   /* Check that the number of tiles being placed is valid */
   if (BMove.move_type != BMS_PLACE_MOVE ||
       BMove.num_moves > BMS_MAX_MOVES_IN_LIST ||
       BMove.num_moves < 0) {
	   printf("Returning invalid because of wrong number of letters\n");
      return (0);
   }
   
   


   /* Check that all tiles are going to different locations,
    * and that all these locations are currently empty.
    */
   if (!bms_move_list_to_unique_and_valid_empty_locs (BMove)) {
      printf("Returning invalid because of not empty\n");
      return (0);
   }
   

   /* Check that the tiles are all being placed in either a horizontal
    * or vertical line.
    */
   if (!bms_move_list_in_line (BMove)) {
      printf("returning invalud because of not straight line\n");
      return (0);
   }


   /* Check that there are no real gaps in the move list: ie. any gaps
    * between moving tiles must be occupied by existing tiles.
    */
   if (!bms_move_list_no_real_gaps (BMove)) {
     printf("Returning invalid because of gaps in move\n");
      return (0);
   }


   /* If there was no last move (ie. this is the first move), check
    * that one of the tiles is going to the center.
    */

   /* changed by Navid */
   if (last_move_ptr == NULL) {
      if (!bms_move_list_contains_center_of_board (BMove)) {
	     printf("Returning invalid because first move and not center\n");
         return (0);
      }
   }

  
   /* For moves after the first move, check the set of rules specified
    * in the specifications as applying only to moves after the first.
    */
   else {
   

      /* Make sure the move is made such that it borders
       * at least one existing tile (horizontally or vertically).
       */
      if (!bms_move_list_adjacent_to_existing_tile (BMove)) {
	     printf("returning invalid because not adjacent to letter\n");
         return (0);
      }
   }


   return (1);
}


int ScoreBMove (t_move_list BMove) {

/* Given a move list BMove, this routine determines what the maximum achievable score
 * is for that move and returns it.  If the move is not valid or is empty,
 * this routine returns 0, for lack of a better value to return.
 */

   int total_score = 0;
   int word_score, word_score_mult, letter_score_mult;
   int iword;
   unsigned int ichar;
   int imove, move_x, move_y;
   signed char *curr_word;
   e_move_dir word_dir;
   t_grid_loc current_location;
   t_mapped_word_list mapped_word_list;
   int **temp_board;  /* [0..BOARD_X_SIZE-1][0..BOARD_Y_SIZE-1] */

   if (!CheckBMove (BMove)) {
      return(0);
   }

   /* Allocate temp_board: a blank, board-sized temporary matrix that
    * tracks the tiles involved in the move.
    */
   temp_board = (int **) bms_alloc_matrix (0, BOARD_X_SIZE-1, 0, BOARD_Y_SIZE-1, sizeof(int), 1);
   mapped_word_list = bms_build_mapped_word_list (BMove);

   /* Right off the bat, if BMS_MAX_MOVES_IN_LIST tiles have been played, add
    * BMS_BINGO_SCORE_VALUE points to the total score.
    */
   if (BMove.num_moves == BMS_MAX_MOVES_IN_LIST) {
      total_score += BMS_BINGO_SCORE_VALUE;
   }

   /* Go over all the moves and mark the locations of new moves */
   for (imove = 0; imove < BMove.num_moves; imove++) {
      move_x = BMove.moves[imove].grid_ref.x;
      move_y = BMove.moves[imove].grid_ref.y;

      temp_board[move_x][move_y] = 1;  /* Record this tile's location in temp_board */
   }

   /* Now go over all the new words and score them */
   for (iword = 0; iword < mapped_word_list.word_list.num_words; iword++) {

      /* Initialize values used for each word */
      word_score = 0;
      word_score_mult = 1; /* This is what word_score_mult starts as */
      curr_word = mapped_word_list.word_list.words[iword];
      word_dir = mapped_word_list.word_dirs[iword];
      current_location = mapped_word_list.word_starts[iword];

      for (ichar = 0; ichar < strlen (curr_word); ichar++) {
         /* Apply a letter multiplier if it exists and this is a newly placed letter move */
         if (temp_board[current_location.x][current_location.y] == 1) {
            switch (SquareScore (current_location)) {
            case BMS_SCORE_MULT_DOUBLE_LETTER:
               letter_score_mult = 2;
               break;
            case BMS_SCORE_MULT_TRIPLE_LETTER:
               letter_score_mult = 3;
               break;
            case BMS_SCORE_MULT_DOUBLE_WORD:
               word_score_mult *= 2;
               letter_score_mult = 1;
               break;
            case BMS_SCORE_MULT_TRIPLE_WORD:
               word_score_mult *= 3;
               letter_score_mult = 1;
               break;
            default:
               letter_score_mult = 1;
               word_score_mult *= 1;
            }

            /* Score the new letter */
            word_score += mapped_word_list.score_of_letter[iword][ichar] * letter_score_mult;
         }
         else {
            letter_score_mult = 1;  /* Old letter multipliers are not counted */
            word_score_mult *= 1;

            /* Score the old letter */
            word_score +=
                bms_board_ptr->tiles[current_location.x][current_location.y].tile_base_value *
                letter_score_mult;
         }

         /* Move on to the next character */
         if (word_dir == MOVE_DIR_HORIZONTAL) {
            current_location.x++;
         }
         else if (word_dir == MOVE_DIR_VERTICAL) {
            current_location.y++;
         }
         else {
            assert(0);   /* Should never happen! */
         }
      }

      total_score += word_score * word_score_mult;
   } 

   /* Free the mapped_word_list data structure */
   bms_free_mapped_word_list (mapped_word_list);

   /* Free the temp_board matrix */
   bms_free_matrix (temp_board, 0, BOARD_X_SIZE-1, 0, sizeof(int));

   return (total_score);
}


t_word_list NewWords (t_move_list BMove) {

/* Given a move list, this routine returns a list of the new words
 * that would be formed if the move was made.  This routine calls
 * a helper routine that returns the locations those words would be in
 * as well, but that is ignored by this routine.  If the move list is invalid,
 * the helper routine returns an empty word list.
 *
 * It is the caller's responsibility to free the word_list.words[][] array
 * that is returned!
 */

   int iword;
   t_mapped_word_list mapped_word_list;

   mapped_word_list = bms_build_mapped_word_list (BMove);

   /* Free the unused location data */
   free (mapped_word_list.word_dirs);
   free (mapped_word_list.word_starts);
   for (iword = 0; iword < mapped_word_list.word_list.num_words; iword++) {
      free (mapped_word_list.score_of_letter[iword]);
   }
   free (mapped_word_list.score_of_letter);

   return (mapped_word_list.word_list);
}


int EmptySquare (t_grid_loc GridRef) {

/* Given a grid location GridRef, this routine returns 0 if the location
 * is valid AND has a letter in it.  It returns 1 otherwise.
 *
 * NOTE that a return value of 1 does not indicate that the GridRef was valid!
 */

   if (bms_grid_loc_valid (GridRef) == 1) {
      if (bms_board_ptr->tiles[GridRef.x][GridRef.y].letter != '\0') {
         return (0);
      }
      else {
         return (1);
      }
   }
   else {
      return (1);
   }
}


signed char TileSquare (t_grid_loc GridRef) {

/* This routine returns the letter that is at the location specified by
 * GridRef.  If the location is invalid, or the location has no letter there,
 * this routine returns '\0'.
 */

   if (bms_grid_loc_valid (GridRef) == 1) {
      return (bms_board_ptr->tiles[GridRef.x][GridRef.y].letter);
   }
   else {
      return ('\0');
   }
}


t_move_list LastMove (void) {

/* This routine returns a pointer to a list containing the last
 * move made on this board.
 * If InitialiseBoard() is called, the last move is reset to be "none".
 * If there was no last move, this routine returns a NULL pointer.
 */

   t_move_list temp;

   bcopy(last_move_ptr,&temp,sizeof(t_move_list));

   return (temp);
}



/************** Local subroutine definitions **********************/


static int bms_grid_loc_valid (t_grid_loc grid_loc) {

/* Given a grid location, this routine returns whether the location
 * is a valid location on the board or not.
 */

   if (grid_loc.x >= 0 && grid_loc.x < BOARD_X_SIZE &&
      grid_loc.y >= 0 && grid_loc.y < BOARD_Y_SIZE) {
      return (1);
   }
   else {
      return (0);
   }
}


static void bms_save_move_list (t_move_list *move_list_ptr,
                                t_move_list **saved_list_ptr) {

/* This routine duplicates the contents of move_list
 * into saved_list_ptr.  If *saved_list_ptr is NULL, memory is
 * allocated for it.  Otherwise, the current contents
 * of saved_list_ptr are freed and re-allocated.
 * This routine assumes that saved_list_ptr is never NULL (ie.
 * it always points to some pointer variable which itself might be NULL).
 */

   int imove;

   assert (saved_list_ptr != NULL);

   /* If *saved_list_ptr exists, free it */
   if (*saved_list_ptr != NULL) {
      free ((*saved_list_ptr)->moves);
      (*saved_list_ptr)->moves = NULL;
      (*saved_list_ptr)->num_moves = 0;
      (*saved_list_ptr)->move_type = BMS_PLACE_MOVE;
   }

   (*saved_list_ptr) = (t_move_list *) malloc (sizeof(t_move_list));

   (*saved_list_ptr)->num_moves = move_list_ptr->num_moves;
   (*saved_list_ptr)->move_type = move_list_ptr->move_type;
   (*saved_list_ptr)->moves = (t_move *) malloc ((*saved_list_ptr)->num_moves *
                                                 sizeof(t_move));

   for (imove = 0; imove < (*saved_list_ptr)->num_moves; imove++) {
      (*saved_list_ptr)->moves[imove] = move_list_ptr->moves[imove];
   }

   return;
}


static int bms_move_list_contains_center_of_board (t_move_list move_list) {

/* This routine returns 1 if the move list "move_list" contains
 * a move to the center of the board, and 0 otherwise.
 * This routine assumes that the board has odd dimensions, so that
 * there is one square in the center of the board.
 */

   t_grid_loc center;

   /* This routine doesn't work with even dimensioned boards
    * yet.
    */
   assert (BOARD_X_SIZE % 2 == 1);
   assert (BOARD_Y_SIZE % 2 == 1);

   center.x = (int)(BOARD_X_SIZE / 2);
   center.y = (int)(BOARD_Y_SIZE / 2);

   /* Does move_list hit the center of the board? */
   return (bms_move_list_contains_grid_location (move_list, center));
}


static int bms_move_list_adjacent_to_existing_tile (t_move_list move_list) {

/* Given a move list, this routine returns 1 if one of the moves
 * is adjacent (horizontally or vertically) to an existing tile.
 * Otherwise, it returns 0.
 */

   int imove;
   int tile_x, tile_y;
   t_grid_loc above, below, left, right;

   for (imove = 0; imove < move_list.num_moves; imove++) {
      tile_x = move_list.moves[imove].grid_ref.x;
      tile_y = move_list.moves[imove].grid_ref.y;

      above.x = tile_x;
      above.y = tile_y - 1;

      below.x = tile_x;
      below.y = tile_y + 1;

      left.x = tile_x - 1;
      left.y = tile_y;

      right.x = tile_x + 1;
      right.y = tile_y;

      /* If one of the squares around this one has an existing
       * tile, we have satisfied the requirement.  Note that EmptySquare()
       * returns 1 for invalid locations, so the edge cases are automatically
       * dealt with here.
       */
      if ((EmptySquare(above) && EmptySquare(below) &&
           EmptySquare(left) && EmptySquare(right)) == 0) {
         return (1);
      }
   }

   return (0);
}


static int bms_move_list_in_line (t_move_list move_list) {

/* Given a move list, this routine returns 1 if all the tiles
 * are in the same line (ie. they are either all on the same
 * row or in the same column).  It also returns 1 in the case of
 * an empty move list.
 */

   int xmin, xmax, ymin, ymax;

   bms_get_extent_of_move_list (move_list, &xmin, &xmax, &ymin, &ymax);

   if (move_list.num_moves == 0 || xmin == xmax || ymin == ymax) {
      return (1);
   }
   else {
      return (0);
   }
}


static int bms_move_list_to_unique_and_valid_empty_locs (t_move_list move_list) {

/* Given a move list, this routine returns 1 if all the tiles
 * are going to unique and valid empty locations.  For the empty
 * move list case, this routine returns 1.
 */

   int move_list_valid = 1;   /* Assume validity until problem is found */
   int imove, move_x, move_y;
   int **temp_board;  /* [0..BOARD_X_SIZE-1][0..BOARD_Y_SIZE-1] */

   /* Allocate temp_board: a blank, board-sized temporary matrix that
    * tracks the tiles involved in the move.
    */
   temp_board = (int **) bms_alloc_matrix (0, BOARD_X_SIZE-1, 0, BOARD_Y_SIZE-1, sizeof(int), 1);

   /* Make sure the move list is going to valid locations. */
   if (!bms_move_list_to_valid_locations (move_list)) {
      move_list_valid = 0;
   }

   /* Go over all the moves and make sure they are going to unique
    * locations that are all empty.
    */
   for (imove = 0; imove < move_list.num_moves; imove++) {
      move_x = move_list.moves[imove].grid_ref.x;
      move_y = move_list.moves[imove].grid_ref.y;

      if (EmptySquare (move_list.moves[imove].grid_ref) == 0) {
         move_list_valid = 0;
      }

      if (temp_board[move_x][move_y] != 0) {
         move_list_valid = 0;
      }
      else {
         temp_board[move_x][move_y] = 1;  /* Record this tile's location in temp_board */
      }
   }

   /* Free the temp_board matrix */
   bms_free_matrix (temp_board, 0, BOARD_X_SIZE-1, 0, sizeof(int));

   return (move_list_valid);
}


static int bms_move_list_to_valid_locations (t_move_list move_list) {

/* Given a move list, this routine returns 1 if the list has only valid
 * locations in it, and 0 otherwise.
 */

   int imove;

   for (imove = 0; imove < move_list.num_moves; imove++) {
      if (!bms_grid_loc_valid (move_list.moves[imove].grid_ref)) {
         return (0);
      }
   }

   return (1);
}


static int bms_move_list_no_real_gaps (t_move_list move_list) {

/* Given a move list, this routine returns 1 if the list represents a move
 * that will not result in any gaps between tiles that are not caused by
 * existing tiles on the board.
 * This routine assumes that the move list represents a set of moves in
 * a line -- an assertion to this effect is in the code.
 */

   int no_gaps = 1;  /* Assume no gaps until one is found */
   int imove, move_x, move_y, i, j;
   int xmin, ymin, xmax, ymax;
   int **temp_board;  /* [0..BOARD_X_SIZE-1][0..BOARD_Y_SIZE-1] */
   t_grid_loc test_location;


   /* The moves must be in a single line (ie. row OR column)
    * and the end-point coordinates must be valid.
    */
   bms_get_extent_of_move_list (move_list, &xmin, &xmax, &ymin, &ymax);

   assert (xmin == xmax || ymin == ymax);
   assert (xmin >= 0 && xmin < BOARD_X_SIZE);
   assert (xmax >= 0 && xmax < BOARD_X_SIZE);
   assert (ymin >= 0 && ymin < BOARD_Y_SIZE);
   assert (ymax >= 0 && ymax < BOARD_Y_SIZE);

   /* Allocate temp_board: a blank, board-sized temporary matrix that
    * tracks the tiles involved in the move.
    */
   temp_board = (int **) bms_alloc_matrix (0, BOARD_X_SIZE-1, 0, BOARD_Y_SIZE-1, sizeof(int), 1);

   /* Mark the locations of the moving tiles in temp_board */
   for (imove = 0; imove < move_list.num_moves; imove++) {
      move_x = move_list.moves[imove].grid_ref.x;
      move_y = move_list.moves[imove].grid_ref.y;

      temp_board[move_x][move_y] = 1;
   }

   /* Make sure all locations not in temp_board (ie. not in the move list)
    * but in the line segment that the move list represents,
    * have existing tiles in them (ie. the "no gaps" rule).
    */
   for (i = xmin; i <= xmax; i++) {
      for (j = ymin; j <= ymax; j++) {
         test_location.x = i;
         test_location.y = j;

         if (temp_board[i][j] == 0 &&
             EmptySquare (test_location)) {
            no_gaps = 0;   /* Found a gap! */
         }
      }
   }

   /* Free the temp_board matrix */
   bms_free_matrix (temp_board, 0, BOARD_X_SIZE-1, 0, sizeof(int));

   return (no_gaps);
}


static int bms_move_list_contains_grid_location (t_move_list move_list,
                                                 t_grid_loc grid_loc) {

/* Given a location grid_loc, this routine returns 1 if the move list
 * "move_list" has a move that is going to that location and 0 otherwise.
 */

   int imove;

   for (imove = 0; imove < move_list.num_moves; imove++) {
      if (move_list.moves[imove].grid_ref.x == grid_loc.x &&
          move_list.moves[imove].grid_ref.y == grid_loc.y) {
         return (1);  /* Found matching location! */
      }
   }

   /* Not found */
   return (0);
}


static void **bms_alloc_matrix (int ncmin, int ncmax, int nrmin, int nrmax,
                                int el_size, int clear) {

/* Given the number of rows and columns desired, this routine
 * allocates and returns a matrix that can be indexed in the ranges
 * matrix[ncmin..ncmax][nrmin..nrmax].  el_size is the size in bytes
 * of each matrix element.  The clear flag is used to control whether
 * the matrix is zeroed out or not when allocated.
 * Cast the return value to the appropriate type.
 */

   int i;
   signed char **matrix_ptr;

   matrix_ptr = (signed char **) malloc ((nrmax - nrmin + 1) * sizeof (signed char *));
   matrix_ptr -= nrmin;
   for (i = ncmin; i <= ncmax; i++) {
      if (clear) {
         matrix_ptr[i] = (signed char *) calloc ((nrmax - nrmin + 1), el_size);
      }
      else {
         matrix_ptr[i] = (signed char *) malloc ((nrmax - nrmin + 1) * el_size);
      }
      matrix_ptr[i] -= nrmin * el_size / sizeof(signed char);  /* sizeof(signed char) = 1 */
   }

   return ((void **) matrix_ptr);
}


static void bms_free_matrix (void *vptr, int ncmin, int ncmax, int nrmin,
                             int el_size) {

/* This routine frees a matrix allocated by bms_alloc_matrix.
 * NB: Need to make vptr void * instead of void ** to allow
 * any pointer to be passed in without a cast.
 */

   int i;
   signed char **cptr;
   
   cptr = (signed char **) vptr;
   
   for (i = ncmin; i <= ncmax; i++) {
      free (cptr[i] + nrmin * el_size / sizeof (signed char));
   }
   free (cptr + ncmin);   

   return;
}


static void bms_get_extent_of_move_list (t_move_list move_list, int *xmin_ptr, int *xmax_ptr,
                                         int *ymin_ptr, int *ymax_ptr) {

/* Given a move list, this routine returns (via the xmin_ptr, ..., ymax_ptr pointers)
 * the minimum and maximum coordinates in the move list.  This routine assumes that
 * all the coordinates are greater than -1 and less than BMS_HUGE_INT.  For empty
 * move lists, this routine will return -1 and BMS_HUGE_INT for maximum and minimum
 * values respectively.
 */

   int imove, move_x, move_y;
   int xmin, xmax, ymin, ymax;

   xmin = BMS_HUGE_INT;
   ymin = BMS_HUGE_INT;
   xmax = -1;
   ymax = -1;

   for (imove = 0; imove < move_list.num_moves; imove++) {
      move_x = move_list.moves[imove].grid_ref.x;
      move_y = move_list.moves[imove].grid_ref.y;

      xmin = MY_MIN (xmin, move_x);
      ymin = MY_MIN (ymin, move_y);
      xmax = MY_MAX (xmax, move_x);
      ymax = MY_MAX (ymax, move_y);

   }

   *xmin_ptr = xmin;
   *xmax_ptr = xmax;
   *ymin_ptr = ymin;
   *ymax_ptr = ymax;

   return;
}


static e_move_dir bms_get_move_direction (t_move_list move_list) {

/* Given a move list, this routine returns the direction of the move list
 * ie. is it in a horizontal line or a vertical line or invalid?
 * For a single tile move, this routine returns MOVE_DIR_HORIZONTAL (arbitrary).
 * For an empty move list, this routine returns MOVE_DIR_INVALID.
 */

   int xmin, xmax, ymin, ymax;

   bms_get_extent_of_move_list (move_list, &xmin, &xmax, &ymin, &ymax);

   if (move_list.num_moves == 0) {
      return (MOVE_DIR_NONE);
   }
   else if (xmin == xmax) {
      return (MOVE_DIR_VERTICAL); /* This is what is returned for single tile case */
   }
   else if (ymin == ymax) {
      return (MOVE_DIR_HORIZONTAL);
   }
   else {
      return (MOVE_DIR_INVALID);
   }
}


static void bms_commit_move_list (t_move_list move_list) {

/* This routine commits the moves represented by move_list to the board.
 * It assumes that the move list is valid and that all tiles are going to
 * empty locations... the helper routine called to commit moves asserts these
 * two things.
 */

   int imove;

   for (imove = 0; imove < move_list.num_moves; imove++) {
      bms_add_tile_to_board (move_list.moves[imove].grid_ref,
                             move_list.moves[imove].letter,
                             move_list.moves[imove].move_base_value);
   }

   return;
}


static void bms_add_tile_to_board (t_grid_loc grid_loc, signed char letter,
                                   int tile_base_value) {

/* Given a grid location and a letter, this routine stores the letter
 * at the appropriate board location.  It asserts that the location it is
 * given is valid.  It also asserts that grid_loc is currently empty (for safety).
 * tile_base_value should be the base value of the tile being placed - in particular,
 * it will be 0 for blank tiles.
 */

   assert (bms_grid_loc_valid (grid_loc));
   assert (EmptySquare (grid_loc));

   bms_board_ptr->tiles[grid_loc.x][grid_loc.y].letter = letter;
   bms_board_ptr->tiles[grid_loc.x][grid_loc.y].tile_base_value = tile_base_value;

   return;
}


static t_mapped_word_list bms_build_mapped_word_list (t_move_list move_list) {

/* Given a move list, this routine loads and returns a mapped word list that
 * contains all the new words that would be created by the move as well as the
 * locations that these words would start in and the direction of the word.
 * If the move list sent to this routine is invalid or empty, it will return an empty word
 * list.
 */

   int imove;
   int xmin, xmax, ymin, ymax;
   int max_num_words;
   e_move_dir move_dir;
   t_mapped_word_list mapped_word_list;
   t_tile **temp_board;   /* [0..BOARD_X_SIZE-1][0..BOARD_Y_SIZE-1] */
   t_grid_loc word_start, next_letter;

   if (move_list.num_moves == 0 || !CheckBMove (move_list)) {
      mapped_word_list.word_dirs = NULL;
      mapped_word_list.word_starts = NULL;
      mapped_word_list.word_list.num_words = 0;
      mapped_word_list.word_list.words = NULL;
      mapped_word_list.score_of_letter = NULL;

      return (mapped_word_list); /* Return early for empty and invalid moves */
   }

   /* From this point on, we know that the move list is not empty
    * and is a valid move list according to the rules of Scrabble.
    */

   /* Allocate and fill temp_board: a board-sized temporary matrix that
    * tracks the locations of new letters for the move.  This temp_board
    * is of type t_tile because it needs to store information about the
    * base scores of the tiles so that the word list can be scored properly.
    */
   temp_board = (t_tile **) bms_alloc_matrix (0, BOARD_X_SIZE-1, 0, BOARD_Y_SIZE-1, sizeof(t_tile), 1);
   for (imove = 0; imove < move_list.num_moves; imove++) {
      int move_x = move_list.moves[imove].grid_ref.x;
      int move_y = move_list.moves[imove].grid_ref.y;

      temp_board[move_x][move_y].letter = move_list.moves[imove].letter;
      temp_board[move_x][move_y].tile_base_value = move_list.moves[imove].move_base_value;
      temp_board[move_x][move_y].score_multiplier = BMS_SCORE_MULT_NONE;   /* Not used */
   }

   /* Allocate a maximum-sized word list.  The maximum number of words
    * a move can generate is max(BOARD_X_SIZE, BOARD_Y_SIZE)+1 because
    * a move can at most generate a word across an entire row/column and
    * on every perpendicular column/row.
    */
   max_num_words = MY_MAX(BOARD_X_SIZE, BOARD_Y_SIZE) + 1;
   mapped_word_list.word_dirs = (e_move_dir *) malloc (max_num_words * sizeof(e_move_dir));
   mapped_word_list.word_starts = (t_grid_loc *) malloc (max_num_words * sizeof(t_grid_loc));
   mapped_word_list.word_list.num_words = 0;
   /* Use calloc to start off with all NULL pointers (ie. no words exist yet) */
   mapped_word_list.word_list.words = (signed char **) calloc (max_num_words, sizeof(signed char *));
   mapped_word_list.score_of_letter =
        (int **) calloc (max_num_words, sizeof(int *));


   /* Get some information about the move -- specifically the line segment to which the
    * tiles are going to and the direction of the line of tiles.
    */
   bms_get_extent_of_move_list (move_list, &xmin, &xmax, &ymin, &ymax);
   move_dir = bms_get_move_direction (move_list);

   switch (move_dir) {
   case MOVE_DIR_HORIZONTAL:
      /* Find the start of the word formed by the horizontal tiles */
      word_start.x = xmin;
      word_start.y = ymin;
      next_letter = word_start;
      next_letter.x--;
      while (next_letter.x >= 0 && (!EmptySquare(next_letter) ||
                                    temp_board[next_letter.x][next_letter.y].letter != '\0')) {
         word_start = next_letter;
         next_letter.x--;
      }

      bms_add_word_to_mapped_list (word_start, move_dir, &mapped_word_list, temp_board);

      /* For each new tile, find the start of the word formed by the vertical tiles */
      for (imove = 0; imove < move_list.num_moves; imove++) {
         word_start.x = move_list.moves[imove].grid_ref.x;
         word_start.y = move_list.moves[imove].grid_ref.y;
         next_letter = word_start;
         next_letter.y--;
         /* Don't need to check temp_board since we are checking
          * perpendicular to the moving tiles.
          */
         while (next_letter.y >= 0 && !EmptySquare(next_letter)) {
            word_start = next_letter;
            next_letter.y--;
         }

         /* This routine will automatically reject one-tile words */
         bms_add_word_to_mapped_list (word_start, MOVE_DIR_VERTICAL,
                                      &mapped_word_list, temp_board);
      }

      break;
   case MOVE_DIR_VERTICAL:
      /* Find the start of the word formed by the vertical tiles */
      word_start.x = xmin;
      word_start.y = ymin;
      next_letter = word_start;
      next_letter.y--;
      while (next_letter.y >= 0 &&
             (!EmptySquare(next_letter) ||
              temp_board[next_letter.x][next_letter.y].letter != '\0')) {
         word_start = next_letter;
         next_letter.y--;
      }

      bms_add_word_to_mapped_list (word_start, move_dir, &mapped_word_list, temp_board);

      /* For each new tile, find the start of the word formed by the horizontal tiles */
      for (imove = 0; imove < move_list.num_moves; imove++) {
         word_start.x = move_list.moves[imove].grid_ref.x;
         word_start.y = move_list.moves[imove].grid_ref.y;
         next_letter = word_start;
         next_letter.x--;
         /* Don't need to check temp_board since we are checking
          * perpendicular to the moving tiles.
          */
         while (next_letter.x >= 0 && !EmptySquare(next_letter)) {
            word_start = next_letter;
            next_letter.x--;
         }

         /* This routine will automatically reject one-tile words */
         bms_add_word_to_mapped_list (word_start, MOVE_DIR_HORIZONTAL,
                                      &mapped_word_list, temp_board);
      }

      break;
   case MOVE_DIR_NONE:  /* Only happens for empty move lists */
      /* Nothing to do */
      break;
   default:
      /* This should never happen since the move was checked for validity */
      assert (0);
      break;
   }

   /* Reallocate the mapped_word_list arrays to be sized based on the number of
    * actual words.
    */
   mapped_word_list.word_dirs = (e_move_dir *) realloc (mapped_word_list.word_dirs,
                                                        mapped_word_list.word_list.num_words *
                                                        sizeof(e_move_dir));
   mapped_word_list.word_starts = (t_grid_loc *) realloc (mapped_word_list.word_starts,
                                                          mapped_word_list.word_list.num_words *
                                                          sizeof(t_grid_loc));
   mapped_word_list.word_list.words = (signed char **) realloc (mapped_word_list.word_list.words,
                                                         mapped_word_list.word_list.num_words *
                                                         sizeof(signed char *));

   /* Free temp_board */
   bms_free_matrix (temp_board, 0, BOARD_X_SIZE-1, 0, sizeof(t_tile));

   return (mapped_word_list);
}


static void bms_add_word_to_mapped_list (t_grid_loc word_start, e_move_dir word_dir,
                                         t_mapped_word_list *list_ptr, t_tile **new_letters) {

/* Given a word with starting location word_start and direction word_dir,
 * this routine adds that word to the mapped_word_list structure pointed to by
 * list_ptr.  This routine assumes that the structure is properly allocated and
 * initialized.
 * This routine assumes that words go from top to bottom and from left to
 * right (ie. word_start should be the top-most or left-most tile of the word).
 * The new_letters matrix is a board-sized array that should have the new letters
 * stored at the appropriate locations and what the base score values are for
 * those tiles.
 *
 * Note that this routine automatically rejects one-tile words.  This was done
 * to make it easier to automatically find all the words created by a move.
 * One-tile words can be enabled, but then the first move (for example) will generate
 * N one-tile words in the perpendicular direction to the move (where N is the number
 * of tiles in the move).  This is why we are rejecting all one-tile words as invalid.
 */

   int next_word_slot, ichar;
   signed char string_buffer[BMS_MAX_WORD_SIZE];
   int tile_base_scores[BMS_MAX_WORD_SIZE];

   next_word_slot = list_ptr->word_list.num_words;

   /* Get the string corresponding to this word */
   bms_get_string_for_word (word_start, word_dir, new_letters, string_buffer,
                            tile_base_scores);

   /* Ignore words with less than 2 tiles */
   if (strlen (string_buffer) <= 1) {
      return;
   }

   /* Copy the information */
   list_ptr->word_starts[next_word_slot] = word_start;
   list_ptr->word_dirs[next_word_slot] = word_dir;
   list_ptr->word_list.words[next_word_slot] = strdup (string_buffer);

   list_ptr->score_of_letter[next_word_slot] =
        (int *) malloc (strlen(string_buffer) * sizeof(int));

   for (ichar = 0; string_buffer[ichar] != '\0'; ichar++) {
      list_ptr->score_of_letter[next_word_slot][ichar] = tile_base_scores[ichar];
   }

   /* Increment the counter */
   (list_ptr->word_list.num_words)++;

   return;
}


static void bms_get_string_for_word (t_grid_loc word_start, e_move_dir word_dir,
                                     t_tile **new_letters, signed char *dest_string,
                                     int *letter_base_scores) {

/* This routine gets the string that represents the word at grid location word_start
 * and in direction word_dir and puts that string in dest_string.  For each
 * character in dest_string, this routine also puts an appropriate entry in
 * letter_base_scores[ichar] that holds the base value of that letter.  In particular, note
 * that this value is 0 for blank tiles.  new_letters is an array of letters that are not on the
 * board but are part of the move, including information about their scoring.
 * This routine assumes that dest_string is properly allocated with at least
 * BMS_MAX_WORD_SIZE+1 characters (+1 because of the NULL terminator).
 * This routine also assumes that letter_base_scores is allocated
 * with at least BMS_MAX_WORD_SIZE integers.
 * This routine assumes that words go from top to bottom and from left to
 * right (ie. word_start should be the top-most or left-most tile of the word).
 */

   int ichar;
   t_grid_loc word_end;
   signed char string_buffer[BMS_MAX_WORD_SIZE];


   ichar = 0;
   word_end.x = word_start.x;
   word_end.y = word_start.y;

   switch (word_dir) {
   case MOVE_DIR_HORIZONTAL:
      /* Find the end of the word */
      while (word_end.x < BOARD_X_SIZE && (!EmptySquare (word_end) ||
                                           new_letters[word_end.x][word_end.y].letter != '\0')) {
         if (bms_board_ptr->tiles[word_end.x][word_end.y].letter == '\0') {
            /* Letter must be a new one -- no gaps allowed */
            string_buffer[ichar] = new_letters[word_end.x][word_end.y].letter;
            letter_base_scores[ichar] = new_letters[word_end.x][word_end.y].tile_base_value;
         }
         else {
            string_buffer[ichar] = bms_board_ptr->tiles[word_end.x][word_end.y].letter;
            letter_base_scores[ichar] =
                 bms_board_ptr->tiles[word_end.x][word_end.y].tile_base_value;
         }

         /* Move on across the line */
         word_end.x++;
         ichar++;
      }

      string_buffer[ichar] = '\0';

      break;
   case MOVE_DIR_VERTICAL:
      /* Find the end of the word */
      while (word_end.y < BOARD_Y_SIZE && (!EmptySquare (word_end) ||
                                           new_letters[word_end.x][word_end.y].letter != '\0')) {
         if (bms_board_ptr->tiles[word_end.x][word_end.y].letter == '\0') {
            /* Letter must be a new one -- no gaps allowed */
            string_buffer[ichar] = new_letters[word_end.x][word_end.y].letter;
            letter_base_scores[ichar] = new_letters[word_end.x][word_end.y].tile_base_value;
         }
         else {
            string_buffer[ichar] = bms_board_ptr->tiles[word_end.x][word_end.y].letter;
            letter_base_scores[ichar] =
                 bms_board_ptr->tiles[word_end.x][word_end.y].score_multiplier;
         }

         /* Move on down the line */
         word_end.y++;
         ichar++;
      }

      string_buffer[ichar] = '\0';

      break;
   default:
      assert(0);  /* Shouldn't happen! */
      break;
   }

   /* Copy the result into dest_string */
   strcpy (dest_string, string_buffer);

   return;
}


static void bms_free_mapped_word_list (t_mapped_word_list list) {

/* This routine frees the arrays allocated in the mapped_word_list
 * structure "list".
 */

   int iword;

   free (list.word_dirs);
   free (list.word_starts);

   for (iword = 0; iword < list.word_list.num_words; iword++) {
      free (list.word_list.words[iword]);
      free (list.score_of_letter[iword]);
   }
   free (list.word_list.words);
   free (list.score_of_letter);

   return;
}


static void bms_load_premium_squares (void) {

/* This routine loads the premium square values of all tiles that are not
 * just the normal non-premium type.  The board configuration can be
 * modified simply by changing the values in the local score_mults array
 * below.  The values refer to score multipliers as given below...
 *
 * The numbering used here (independent of the definition of e_score_mults)
 * is:
 *    BMS_SCORE_MULT_NONE = 0 (normal)
 *    BMS_SCORE_MULT_DOUBLE_LETTER = 1 (light blue)
 *    BMS_SCORE_MULT_TRIPLE_LETTER = 2 (dark blue)
 *    BMS_SCORE_MULT_DOUBLE_WORD = 3 (pink)
 *    BMS_SCORE_MULT_TRIPLE_WORD = 4 (red)
 * The numbering is kept independent of e_score_mults to remove the otherwise nasty
 * dependency on the ordering of the e_score_mults enumerated type.
 */

   /* This is the array that holds the board tile score multipliers!
    * The values in any row are the values for a column of the actual board.
    * Be careful here!
    */
   int score_mults[BOARD_X_SIZE][BOARD_Y_SIZE] = {
      {4, 0, 0, 1, 0, 0, 0, 4, 0, 0, 0, 1, 0, 0, 4},
      {0, 3, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 3, 0},
      {0, 0, 3, 0, 0, 0, 1, 0, 1, 0, 0, 0, 3, 0, 0},
      {1, 0, 0, 3, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 1},
      {0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0},
      {0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0},
      {0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0},
      {4, 0, 0, 1, 0, 0, 0, 3, 0, 0, 0, 1, 0, 0, 4},
      {0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0},
      {0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0},
      {0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0},
      {1, 0, 0, 3, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 1},
      {0, 0, 3, 0, 0, 0, 1, 0, 1, 0, 0, 0, 3, 0, 0},
      {0, 3, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 3, 0},
      {4, 0, 0, 1, 0, 0, 0, 4, 0, 0, 0, 1, 0, 0, 4},
   };

   int i, j;

   for (i = 0; i < BOARD_X_SIZE; i++) {
      for (j = 0; j < BOARD_Y_SIZE; j++) {
         switch (score_mults[i][j]) {
         case 0:
            bms_assign_premium_value (i, j, BMS_SCORE_MULT_NONE);
            break;
         case 1:
            bms_assign_premium_value (i, j, BMS_SCORE_MULT_DOUBLE_LETTER);
            break;
         case 2:
            bms_assign_premium_value (i, j, BMS_SCORE_MULT_TRIPLE_LETTER);
            break;
         case 3:
            bms_assign_premium_value (i, j, BMS_SCORE_MULT_DOUBLE_WORD);
            break;
         case 4:
            bms_assign_premium_value (i, j, BMS_SCORE_MULT_TRIPLE_WORD);
            break;
         }
      }
   }

   return;
}


static void bms_assign_premium_value (int x, int y, e_score_mults score_mult) {

/* Given a grid location in (x,y) coordinates, this routine assigns the
 * bms_board_ptr->tiles[x][y].score_multiplier value to score_mult.
 */

   assert (x >= 0 && x < BOARD_X_SIZE);
   assert (y >= 0 && y < BOARD_Y_SIZE);

   bms_board_ptr->tiles[x][y].score_multiplier = score_mult;

   return;
}