// Dict.cpp: implementation of the CDict class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "words.h"
#include "Dict.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

// Define node type

typedef struct node {
	char letter;
	int terminal;
	struct node *subnode;
	struct node *rest;
} node;

// Type for a board position
typedef struct pos {
   int x;
   int y;
} pos;

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CDict::CDict()
{
	FILE *dict;
 
	dict_filepath = "dict.txt";	
	
	// Open the dictionary file
	if ((dict = fopen(dict_filepath,"r")) == NULL){
		TRACE("Cannot open data file:\n%s\n",dict_filepath);
		abort();
	}else{
		TRACE( "Data file opened successfully\n" );
	}
	
	// Build the dictionary
	lexroot = buildlexicon( dict );

	// Close the data file
	fclose( dict );
	TRACE( "Data file closed\n" );

	// Init bestbrd
	bestbrd=NULL;
	
	// Initialise letter scores
	letter_score[ 0] = 1; letter_score[ 1] = 3;  letter_score[ 2] = 3;
	letter_score[ 3] = 2; letter_score[ 4] = 1;  letter_score[ 5] = 4;
	letter_score[ 6] = 2; letter_score[ 7] = 4;  letter_score[ 8] = 1;
	letter_score[ 9] = 8; letter_score[10] = 5;  letter_score[11] = 1;
   letter_score[12] = 3; letter_score[13] = 1;  letter_score[14] = 1;
	letter_score[15] = 3; letter_score[16] = 10; letter_score[17] = 1;
	letter_score[18] = 1; letter_score[19] = 1;  letter_score[20] = 1;
	letter_score[21] = 4; letter_score[22] = 4;  letter_score[23] = 4;
	letter_score[24] = 8; letter_score[25] = 10;
}


CDict::~CDict()
{

	// Destroy everything
	TRACE( "Should be destroying dictionary\n" );
	
}

/* gets a line from a file and places it in argument line (not inc \n) */
int CDict::nextline(FILE * source, char * line)
{
   int i, ch;  /* loop counter & variable for user input */
   for (i = 0; i < 80 && (ch = getc(source)) != '\n' && ch != EOF; i++)  /* read a line up to 80 characters */
      line[i] = ch;
   line[i] = '\0';  /* add end of string marker */
   return i;  /* return length of string */
}

/* newnode: returns a pointer to a new node in the graph */
node * CDict::newnode(char letter, int terminal)
{
   node *newitem = new node;

   if (newitem == NULL)
   {
      TRACE("Error - Insufficient Memory\n");
      exit(1);
   }

   newitem->letter = letter;
   newitem->terminal = terminal;
   newitem->subnode = NULL;
   newitem->rest = NULL;

   return newitem;	
}

/* buildword: recursively builds a word into existing graph 
  parameters: word = word to be added, letter = index of current letter,
              current = pointer to place where letter should go  */
node * CDict::buildword(char * word, int letter, node * current)
{
   node *start = current;  /* copy of entry point */

   if (current != NULL)  /* if list of subnodes exists ... */
   {
      /* check if the letter already exists, if not, then add it to list */
      while ((current->letter != word[letter]) && (current->rest != NULL)) /* move along node list until letter is found or end */
         current = current->rest;

      if (current->letter != word[letter])  /* if letter doesn't exist ... */
      {
         current->rest = newnode(word[letter],0);  /* ... add letter */
         current = current->rest;  /* and point to it */
      }
   }
   else
   {
      current = newnode(word[letter],0);
      start = current;
   }
      
   /* if letter is last, return start of list, otherwise more letters to add ... */ 
   if (word[letter+1] == '\0')  /* if letter is the last (ie next is \n)... */
      current->terminal = 1;   /* ... mark as end of word */
   else
      current->subnode = buildword(word,letter+1,current->subnode);

   return start;   /* and return start of sub node list */
}

/* rev: reverses all the characters in a string */
void CDict::rev(char * word)
{
   int i=0, j=strlen(word);
   char *tmp = (char *)malloc(sizeof(char)*j);

   if (j>1)
   {
      while (j>0)
         tmp[--j] = word[i++];
      while(j<i)
         word[j++] = tmp[j];
   }
   free(tmp);
}

node * CDict::buildlexicon(FILE *dict)
{
   char line[80], x[80], y[80];
   node *root = newnode('a',0);  /* create root and start point */
   int comb, j, k;

   while (nextline(dict,line) > 0)
   {
      for (comb=0; comb<(int)strlen(line); comb++)  /* generate combinations */
      {
         for(j=0; j<=comb; j++)  
            x[j] = line[j];  /* copy characters into x */
         x[j] = '\0';  /* add end of string marker */
         rev(x);  /* reverse x */

         for(k=0; j<(int)strlen(line); j++) 
            y[k++] = line[j];  /* copy rest into y */
         y[k] = '\0';  /* add end of string marker */

         if (strlen(y)>0)
         {
            strcat(x,"*");  /* add delimeter (if length of y > 0) */
            strcat(x,y);  /* add y to x */
         }

         buildword(x,0,root);  /* add to dict */
      }
   }

   return root;
}

/* validword: checks if a word is in the dictionary (returns true (1) or false (0)) */
int CDict::validword(char *board, pos s, pos e, node *lex)
{
   node *current = lex;
   int i=0, x, y;

   for (x=e.x; x>=s.x; x--)
      for (y=e.y; y>=s.y; y--)
      {
         while (current != NULL && current->rest != NULL && current->letter != board[x+y*15])
            current = current->rest;  /* find letter in dict */
         if (current != NULL && current->letter == board[x+y*15])
         {
            if (x != s.x || y != s.y)  /* letter found, if not last, move to next level */
               current = current->subnode;
         }
         else
            return 0;
      }

   return current->terminal;
}

/* scoreword: calculates score of a word
  parameters: board - the current board state (array of 225 chars)
              s - the (x,y) co-ordinates of first letter
              e - the (x,y) co-ordinates of the last letter */
int CDict::scoreword(char *board, pos s, pos e)
{
   int score=0, multiplier=1, x, y;

   for (x=s.x; x<=e.x; x++)
      for (y=s.y; y<=e.y; y++)  /* for each letter in the new word ... */
      {
         switch(board_score[x+y*15])
         {
            case '0': score += letter_score[board[x+y*15]-'a'];  /* empty normal square */
                      break;
            case '2': score += (letter_score[board[x+y*15]-'a']*2);  /* empty double letter square */
                      break;
            case '3': score += (letter_score[board[x+y*15]-'a']*3);  /* empty triple letter square */
                      break;
            case '4': score += letter_score[board[x+y*15]-'a'];  /* empty double word square */
                      multiplier *= 2;  /* alter word score modifier */
                      break;
            case '5': score += letter_score[board[x+y*15]-'a'];  /* empty triple word square */
                      multiplier *= 3;  /* alter word score modifier */
                      break;
         }
      }
   
   return score * multiplier;  /* letter score * word multiplier */
}

/* compares new & current board states, returns score (-ve for invalid play) */
int CDict::compare(char *board, char *newboard, node *lex) {
   int i, score=0, x, y, adj=1;
   pos s_pos, e_pos, jmp, s, e;

   i = 0;
   while (i<225 && (newboard[i] == board[i]))  /* find first change on board */
      i++;
   s_pos.x = i%15;  /* record start point (x,y) */
   s_pos.y = i/15;

   i = 224;
   while (i>=0 && (newboard[i] == board[i]))  /* find last change on board */
      i--;
   e_pos.x = i%15;  /* record end point (x,y) */
   e_pos.y = i/15;

   /* check that new letters are in same row/column and find direction */
   if (s_pos.x == e_pos.x && s_pos.y != e_pos.y)  /* vertical word */
   {
      jmp.x = 0;
      jmp.y = 1;
   }
   else if (s_pos.x != e_pos.x && s_pos.y == e_pos.y)  /* horizontal word */
   {
      jmp.x = 1;
      jmp.y = 0;
   }
   else if (s_pos.x == e_pos.x && s_pos.y == e_pos.y)  /* one letter added, treat as horizontal */
   {
      jmp.x = 1;
      jmp.y = 0;
   }
   else  
      return -1;  /* letters added not in same row/column, invalid play */

   /* check that no additional invalid tiles have been added */
   for (x=0; x<15; x++)
      for (y=0; y<15; y++)
      {
         if (newboard[x+y*15] != board[x+y*15])
            if ((jmp.x && y != s_pos.y) || (jmp.y && x != s_pos.x))  /* if other letters not in correct row/column ... */
               return -1;  /* invalid play */
      }

   /* check if the original board is empty */
   for (i=0; i<225; i++)
      if (board[i] != '0')
         adj = 0;

   if (adj==0)  /* if not empty */
   {
      for (x=0; x<15; x++)
         for (y=0; y<15; y++)
            if (board[x+y*15] != newboard[x+y*15])  /* check that at least one tile is adjacent */
            {
               if (x>0 && board[(x-1)+y*15] != '0')
                  adj = 1;
               else if (x<14 && board[(x+1)+y*15] != '0')
                  adj = 1;
               else if (y>0 && board[x+(y-1)*15] != '0')
                  adj = 1;
               else if (y<14 && board[x+(y+1)*15] != '0')
                  adj = 1;
            }
   }
   else
      if (newboard[7+7*15] == '0')  /* if board is empty check that new word passes through centre square */
         return -1;

   if (adj==0) return -1;
               
   /* check and score and new words that may be created perpendicularly in addition to main word */
   for (x=s_pos.x; x<=e_pos.x; x++)
      for (y=s_pos.y; y<=e_pos.y; y++)
         if (newboard[x+y*15] != board[x+y*15])
         {
            s.x = x; s.y = y;
            e.x = x; e.y = y;
            while (((s.x>0 && jmp.y) || (s.y>0 && jmp.x)) && newboard[(s.x-jmp.y)+(s.y-jmp.x)*15] != '0')  /* find left/upper most start letter */
            {
               s.x -= jmp.y;
               s.y -= jmp.x;
            }
            while (((e.x<14 && jmp.y) || (e.y<14 && jmp.x)) && newboard[(e.x+jmp.y)+(e.y+jmp.x)*15] != '0')  /* find right/lower most end letter */
            {
               e.x += jmp.y;
               e.y += jmp.x;
            }
            if (s.x != e.x || s.y != e.y)
               if (validword(newboard,s,e,lex))  /* validate word */
                  score += scoreword(newboard,s,e);
               else
                  return -1;
         }

   /* find start of new word (may be before new letters) */
   while (((s_pos.x>0 && jmp.x) || (s_pos.y>0 && jmp.y)) && newboard[(s_pos.x-jmp.x)+(s_pos.y-jmp.y)*15] != '0')  /* find left/upper most start letter */
   {
      s_pos.x -= jmp.x;
      s_pos.y -= jmp.y;
   }
   while (((e_pos.x<14 && jmp.x) || (e_pos.y<14 && jmp.y)) && newboard[(e_pos.x+jmp.x)+(e_pos.y+jmp.y)*15] != '0')  /* find right/lower most end letter */
   {
      e_pos.x += jmp.x;
      e_pos.y += jmp.y;
   }
   
   /* validate & score new word */
   if (s_pos.x != e_pos.x || s_pos.y != e_pos.y)
      if (validword(newboard,s_pos,e_pos,lex))
         score += scoreword(newboard,s_pos,e_pos);
      else
         return -1;

   return score;
}


node *CDict::nextarc(node *arc, char L)
{
   while (arc != NULL && arc->letter != L)
      arc = arc->rest;
   if (arc == NULL)
      return NULL;
   else
      return arc->subnode;
}

void CDict::Gen(pos anchor, pos p, pos dir, char *rack, node *lex, char *board, char *old)
{
   int i;
   char L, newrack[7];
   node *next;

   L = board[p.x+p.y*15];

   if (L != '0')  /* if a letter, L, is already on this square ... */
   {
      GoOn(anchor,p,dir,L,rack,nextarc(lex,L),lex,board,old);
   }
   else
      for (i=0; i<7; i++)  /* for letter left on the rack ... */
         if (rack[i] != '0')
         {
            next = lex;  /* reset list */
            while (next->rest != NULL && next->letter != rack[i])  /* find subnode for this letter */
                  next = next->rest;
            if (next->letter == rack[i])  /* if letter allowed on square ... */
            {
               strcpy(newrack,rack);
               L = newrack[i];
               newrack[i] = '0';  /* remove letter from rack */
               GoOn(anchor,p,dir,L,newrack,next->subnode,lex,board,old);
            }
         }
}


void CDict::GoOn(pos anchor, pos p, pos dir, char L, char *rack, node *newlex, node *oldlex, char *board, char *old)
{
   node *next = oldlex;
   char newboard[225];
   int score;

   while (next->rest != NULL && next->letter != L)  /* find subnode for this letter */
      next = next->rest;

   if (p.x <= anchor.x && p.y <= anchor.y)  /* left/up */
   {
      if (L == next->letter && board[(p.x-dir.x)+(p.y-dir.y)*15] == '0')  /* L is in lex and no letter left/above ... */
      {
         strcpy(newboard,board);
         newboard[p.x+p.y*15] = L;  /* record play */
      }

      p.x -= dir.x;  /* move left/up */
      p.y -= dir.y;
      
      if (newlex != NULL)
      {
         if (newboard[p.x+p.y*15] == '0' && p.x >= 0 && p.y >= 0)  /* if room to left/above ... */
            Gen(anchor,p,dir,rack,newlex,newboard,old);
         
         newlex = nextarc(newlex,'*');  /* shift direction */

         if (newlex != NULL && newboard[p.x+p.y*15] == '0' && board[(anchor.x+dir.x)+(anchor.y+dir.y)*15] == '0')
         {
            if (p.x <= 14 && p.y <= 14)
            {
               p.x = anchor.x + dir.x;  /* position now right/below anchor */
               p.y = anchor.y + dir.y;
               Gen(anchor,p,dir,rack,newlex,newboard,old);
            }
         }
      }
   }
   else  /* right/down */
   {
      if (L == next->letter && board[(p.x+dir.x)+(p.y+dir.y)*15] == '0')  /* L is in lex and no letter left/above ... */
      {
         strcpy(newboard,board);
         newboard[p.x+p.y*15] = L;  /* record play */
      }

      p.x += dir.x;  /* move right/down */
      p.y += dir.y;

      if (newlex != NULL && newboard[p.x+p.y*15] == '0' && p.x <= 14 && p.y <= 14)  /* if room to right/below ... */
         Gen(anchor,p,dir,rack,newlex,newboard,old);
   }

   /* evaluate words */
   score = compare(old,newboard,lexroot);
   if (score > bestscore)
   {
      free(bestbrd);
      bestscore = score;
      bestbrd = strdup(newboard);
      strcpy(bestrack,rack);
   }
}


char *CDict::genmove(char *board, char *rack, node *lex)
{
   pos p, dir;
   int x, y, none = 1;
   
   bestscore = 0;
   bestbrd = NULL;

   /* horizontal words */
   dir.x = 1;
   dir.y = 0;
   for (y=0; y<15; y++)
      for (x=0; x<15; x++)
         if (board[x+y*15] != '0')
         {
            none = 0;
            p.x = x;
            if (y>0 && board[x+(y-1)*15] == '0')  /* check above vertical words */
            {
               p.y = y-1;
               Gen(p,p,dir,rack,lex,board,board);
            }
            if (y>14 && board[x+(y+1)*15] == '0')  /* check below */
            {
               p.y = y+1;
               Gen(p,p,dir,rack,lex,board,board);
            }
            p.y = y;
            Gen(p,p,dir,rack,lex,board,board);
         }

   /* vertical */
   dir.x = 0;
   dir.y = 1;
   for (x=0; x<15; x++)
      for (y=0; y<15; y++)
         if (board[x+y*15] != '0')
         {
            none = 0;
            p.y = y;
            if (x>0 && board[(x-1)+y*15] == '0')  /* check left of horizontal words */
            {
               p.x = x-1;
               Gen(p,p,dir,rack,lex,board,board);
            }
            if (x<14 && board[(x+1)+y*15] == '0')  /* check right */
            {
               p.x = x+1;
               Gen(p,p,dir,rack,lex,board,board);
            }
            p.x = x;
            Gen(p,p,dir,rack,lex,board,board);
         }

   /* if there are no letters on the board */
   if (none == 1)
   {
      p.x = 7;  /* start on the centre square */
      p.y = 7;
      Gen(p,p,dir,rack,lex,board,board);
   }

   /* ovewrite bonus squares to prevent re-use */
   if (bestbrd != NULL)
      for (x=0; x<15; x++)
         for (y=0; y<15; y++)
            if (bestbrd[x+y*15] != '0')
               board_score[x+y*15] = '0';

   strcpy(rack,bestrack);

   return bestbrd;
}



int CDict::GetLetterScore(char chLetter)
{
	if( chLetter >='a' && chLetter <= 'z' ){
		return letter_score[ chLetter - 'a' ];
	}else{
		return 0;
	}
}

// Function that makes a move, making the changes to the board
// and returning the score that the word is worth
int CDict::BestMove(char * pchBoard, char * pchRack)
{

	char boardNoScores[226];
	int i;

	// Convert the board format
	for( i = 0; i<226; i++ ){

		if ( pchBoard[i] >= 'a' && pchBoard[i] <= 'z' ){
			boardNoScores[i] = pchBoard[i];
			board_score[i] = '0';
		}else{
			boardNoScores[i] = '0';
			board_score[i] = pchBoard[i];
		}
	}
	boardNoScores[225] = '\0';

	// Take the move
	genmove( boardNoScores, pchRack, lexroot );

	// Convert the board format back, and make the changes
	// to the board, as long as a new board was found
	if( bestbrd != NULL ){
		for( i = 0; i<225; i++ ){
	
			if ( bestbrd[i] >= 'a' && bestbrd[i] <= 'z' ){
				pchBoard[i] = bestbrd[i];
			}
		}
		free( bestbrd );
	}

	// Store the rack
	TRACE( "Computer player's rack = %c%c%c%c%c%c%c\n",
         pchRack[0],pchRack[1],pchRack[2],pchRack[3],pchRack[4],pchRack[5],pchRack[6] ); 

	return bestscore;
}

// Checks that a move made by a player is valid and returns
// a positive score, or a negative value for an invalid move
int CDict::CheckMove(char * boardBefore, char * boardAfter)
{
	// Variable that holds a board without embedded
	// scoring information
	char boardBeforeNoScores[226], boardAfterNoScores[226];
	int i, score;

	// Loop through all characters
	for( i = 0; i<225; i++ ){

		if ( boardBefore[i] >= 'a' && boardBefore[i] <= 'z' ){
			boardBeforeNoScores[i] = boardBefore[i];
			board_score[i] = '0';
		}else{
			boardBeforeNoScores[i] = '0';
			board_score[i] = boardBefore[i];
		}

		if ( boardAfter[i] >= 'a' && boardAfter[i] <= 'z' ){
			boardAfterNoScores[i] = boardAfter[i];
		}else{
			boardAfterNoScores[i] = '0';
		}
	}

	boardBeforeNoScores[225] = '\0';
	boardAfterNoScores[225] = '\0';

	score = compare( boardBeforeNoScores, boardAfterNoScores, lexroot );
	
	TRACE( "BoardBefore = %s\nBoardAfter = %s\n",
		boardBeforeNoScores, boardAfterNoScores );

	return score;

}