/* Best seen with tabstop = 3 */
/* By Delta Epsilon Software */
/* You may not use this file in your scrabble software without     
	signing a purchase agreement from Delta Epsilon Software.  You
	may however, evealuate the code for free conditional on not
	distributing this software to anyone else. */

/* FILE: ap_dict.c

	This file contains the routines used to examine the library.
	It is called by the AP to provide various word lists and to
	check the spelling of words.  The interface with the AP is in
	"ap.h".  The interface with the BMS and other modules is in
	"scrabble.h"
*/
#include "ap-internal.h"

/* Global Data ===========================================*/

FILE *dict_file = 0;
/* dict_file is the FILE containing the Dictionary.  It is opened on
	the call to InitialiseAP().  It is not closed until the program is
	closed.
*/


fpos_t letter_offsets['z'-'a'+1];
/* letter_offsets contains the offsets within dict_file where the first
	word starting with each letter is.  This allows us to quickly check
	the spelling of words by jumping to that part of the dictionary.  It
	is initialized by the call to InitialiseAP().
*/


/* Internal Data Structures ==============================*/

typedef int AP_num_tiles['z'-'a'+1];
/* This data structue is used to count how many tiles of each letter
	we have or have left. */


/* Helper functions ======================================*/

/************************************/
void AP_DICT_add_word_node(signed char* word,
									AP_valid_words word_list, signed char index_char) {
/* AP_DICT_add_word_node

	requires: word is a NULL terminated string with length < MAX_BOARDSIZE
		'a' <= index_char <= 'z', word_list must be non-null valid_words.
	effects: creates a new AP_word_node.  Copies word into the new
		node.  Inserts the new node into word_list at the indicated index.
	NOTE: AP_DICT_destroy_valid_words_sub_lists must eventually be called
		to clean this up.
*/
	AP_word_node_ptr node = (AP_word_node_ptr)malloc(sizeof(AP_word_node));
	assert(node != 0);
	assert(strlen(word) <= MAXBOARDSIZE);

	strcpy(node->word, word);
	node->next = word_list[index_char-'a'];
	word_list[index_char-'a'] = node;
	return;
}


/*********************************************************************/
void AP_DICT_check_word(signed char* word, AP_num_tiles tiles, int num_blanks,
								AP_valid_words result) {
/* AP_DICT_check_word

	requires: word is a NULL terminated string.  tiles has been initialized
		to the available tiles.  result is a valid (non-NULL) valid_words.
		num_blanks >= 0
	effects: Tries to see if word could be made from tiles with the
		addition of any one additional tile.  If it can, nodes are inserted
		into result at every index which could be the added tile.
	NOTE: AP_DICT_destroy_valid_words_sub_lists must eventually be called
		to clean this up.
*/
	AP_num_tiles avail_tiles;
	int i;
	int len = strlen(word);
	int avail_blanks = num_blanks + 1;
	/* We want to add one blank to represent the added tile */

	assert(result != 0);

	for (i=0; i<=('z'-'a'); i++) {
		avail_tiles[i] = tiles[i];
	}

	for (i=0; i<len; i++) {
		signed char index = word[i] - 'a';

		if (avail_tiles[index] > 0) {
			/* We have this tile so use it */
			avail_tiles[index]--;

		} else if (avail_blanks > 0) {
			/* We don't have this tile but we have blanks left or
				we'll use this as the added tile */
			avail_blanks--;
			/* We'll mark this letter as being a possible added tile */
			avail_tiles[index] = -1;

		} else {
			/* We can't make this word with only one additional letter */
			return;
		}
	}
	/* If we've made it this far, we can make this word */

	if (avail_blanks > 0) {
		/* We haven't used the added tile yet, so we could replace any
			of our real tiles with the added tile. */
		for (i=0; i<=len; i++) {
			signed char index = word[i] - 'a';

			if (tiles[index] > 0) {
				/* Mark this as a possible added tile */
				avail_tiles[index] = -1;
			}
		}
	}

	for (i=0; i<=('z'-'a'); i++) {
		if (avail_tiles[i] == -1) {
			/* This letter could be added to the tiles to create this
				word so we want to put this word in this letters list. */
			AP_DICT_add_word_node(word, result, i+'a');
		}
	}

	return;
}


/* Exported functions ====================================*/

/***********************/
void InitialiseAP(void) {
/* InitialiseAP

	requires: AP must be uninitialized.
	effects: Opens the dict_file FILE.  Also initializes the
		letter_offsets array.
	NOTE: This function must be called before *ANY* other AP function!
*/
	signed char this_word[MAXBOARDSIZE];
	int i;
	fpos_t dict_offset = 0;

	dict_file = fopen(AP_DICT_FILE, "r");
	assert(dict_file != 0);

	for(i=0; i<=('z'-'a'); i++) {
		letter_offsets[i] = AP_INVALID;
	}

	while (fscanf(dict_file, "%s", this_word) == 1) {
		signed char c = this_word[0] - 'a';
		assert(strlen(this_word) < MAXBOARDSIZE);
		if (letter_offsets[c] < 0 ) {
			letter_offsets[c] = dict_offset;
		}
		fgetpos(dict_file, &dict_offset);
	}

	return;
};


/**********************************************************************/
void AP_DICT_get_valid_words(t_move_list tiles, AP_valid_words result) {
/* AP_DICT_get_valid_words

	requires: tiles must be a valid t_move_list,
		words must be a valid (non-NULL) empty AP_valid_words.
	effects: returns in result a AP_valid_words where each list
		within the returned array contains all words that could be
		created by adding the letter with that index to the
		letters contained in tiles.  If no words can be made then
		all lists will be empty.
	NOTE: The caller must call AP_DICT_destroy_valid_words_sub_lists
		on the result list.
*/
	int i;
	signed char this_word[MAXBOARDSIZE+1];
	AP_num_tiles num_tiles;
	int num_blanks = 0;


	assert(result != 0);

	for (i=0; i<=('z'-'a'); i++) {
		/* Initalize the result */
		result[i] = 0;
		num_tiles[i] = 0;
	}

	for (i=0; i<tiles.num_moves; i++) {
		signed char c = tiles.moves[i].letter;
		if (c == '?') {
			/* This is a blank */
			num_blanks++;
		} else {
			/* This is a regular tile */
			assert((c >= 'a') && (c <= 'z'));
			num_tiles[c-'a']++;
		}
	}

	assert(dict_file != 0);
	fseek(dict_file, 0, SEEK_SET); /* reset the dictionary */

	while (fscanf(dict_file, "%s", this_word) == 1) {
		/* While one word was sucessfully read from the dictionary,
			see if the word can be created from our tiles by adding
			one tile from the board.  If so, add the word to the
			appropriate results. */
		AP_DICT_check_word(this_word, num_tiles, num_blanks, result);
	}

	return;
}

/************************************************************/
AP_word_node_ptr AP_DICT_get_initial_words(t_move_list tiles) {
/* AP_DICT_get_inital_words

	requires: tiles must be a valid t_move_list.
	effects: returns an AP_word_node_ptr pointing to the beginning
		of a linked list of nodes which contains all words which
		can be made out of only the passed tiles.
	NOTE: The caller must call AP_DICT_destroy_word_node on the
		resulting list.
*/
	AP_word_node_ptr list_head = 0;
	AP_word_node_ptr new_node = 0;
	int i;
	signed char this_word[MAXBOARDSIZE+1];
	AP_num_tiles num_tiles;
	int num_blanks = 0;


	for (i=0; i<=('z'-'a'); i++) {
		/* Initalize the num_tile */
		num_tiles[i] = 0;
	}

	for (i=0; i<tiles.num_moves; i++) {
		signed char c = tiles.moves[i].letter;
		if (c == '?') {
			/* This is a blank */
			num_blanks++;
		} else {
			/* This is a regular tile */
			assert((c >= 'a') && (c <= 'z'));
			num_tiles[c-'a']++;
		}
	}

	assert(dict_file != 0);
	fseek(dict_file, 0, SEEK_SET); /* reset the dictionary */

	while (fscanf(dict_file, "%s", this_word) == 1) {
		/* While one word was sucessfully read from the dictionary,
			see if the word can be created from our tiles by adding
			one tile from the board.  If so, add the word to the
			appropriate results. */
		AP_num_tiles avail_tiles;
		int len = strlen(this_word);
		int avail_blanks = num_blanks;
		assert(len < MAXBOARDSIZE);
		/* We want to add one blank to represent the added tile */

		for (i=0; i<=('z'-'a'); i++) {
			avail_tiles[i] = num_tiles[i];
		}

		for (i=0; i<len; i++) {
			signed char index = this_word[i] - 'a';

			if (avail_tiles[index] > 0) {
				/* We have this tile so use it. */
				avail_tiles[index]--;

			} else if (avail_blanks > 0) {
				/* We don't have this tile but we have blanks left. */
				avail_blanks--;

			} else {
				/* We can't make this word. */
				i=AP_INVALID;
				break;
			}
		}
		if (i != AP_INVALID) {
			/* We can make this word */
			new_node = (AP_word_node_ptr)malloc(sizeof(AP_word_node));
			assert(new_node != 0);
			strcpy(new_node->word, this_word);

			new_node->next = list_head;
			list_head = new_node;
		}
	}

	return list_head;
}

/**************************************/
int AP_DICT_check_spelling(signed char* word) {
/* AP_DICT_check_spelling

	requires: word must point to a NULL terminated character string.
	effects: returns 1 if the word is in the dictionary, else 0.
*/

	/* This function uses a jump and scan search routine.  This could
		be made faster by switching to a binary search, however the added
		complexity doesn't seem required as this is fast enough to keep
		moves under 15 seconds.  This is the procedure where the most
		execution time is spent, however, so if the APMove() is too slow,
		swithing to binary search would be an easy solution. */
	signed char this_word[MAXBOARDSIZE+1];
	int found = 0;
	signed char c;
	assert(word != 0);
	c = word[0];

	assert((dict_file != 0) && (letter_offsets[c - 'a'] != AP_INVALID));
	/* We want to start at the first word in the dictionary with the
		same first lette.r */
	fsetpos(dict_file, &(letter_offsets[c - 'a']));

	while ((fscanf(dict_file, "%s", this_word) == 1) && !found) {
		int comp;
		assert(strlen(this_word) < MAXBOARDSIZE);
		/* While one word was sucessfully read from the dictionary,
			see if the word matches our test word. */
		comp = strcmp(this_word, word);
		if(comp == 0) {
			found = 1;
		}
		else if (comp > 0) {
			/* We've passed word's location in the dictionary without
				finding it */
			break;
		}
	}

	return found;
}


/*****************************************************/
void AP_DICT_destroy_word_node(AP_word_node_ptr node) {
/* AP_DICT_destroy_word_node

	requires: node must point to the start of a word_node list or be NULL.
	effects: recursively frees all the nodes of the list.
*/
	if (node == 0) return;
	AP_DICT_destroy_word_node(node->next);
	free(node);

	return;
}


/****************************************************************/
void AP_DICT_destroy_valid_words_sub_lists(AP_valid_words words) {
/* AP_DICT_destroy_valid_words_sub_lists

	requires: words must be a valid AP_valid_words.
	effects: calls AP_DICT_destroy_word_node on each list within
		words.  It sets each element of words to NULL.
*/
	int i;
	for (i='a'; i<='z'; i++) {
		AP_DICT_destroy_word_node(words[i-'a']);
		words[i-'a'] = 0;
	}
	return;
}