/*
Solution for Comp2303 Assignment 1
It implements all normal and advanced functionality.

This program consists of 3 main pieces:
1) WordList and associated routines - add to list, sort list, write to file.
2) Grid and associate routines - read, search for words, find unused letters.
3) main() and file handling functions.

I have passed structs by value unless they need to be modified.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef int boolean;
#define TRUE 1
#define FALSE 0

#define BAD_USE 1
#define BAD_SIZE 4
#define BAD_FILE_OPEN 3
#define MISSING_DATA 5

#define DEFAULT_OUT_NAME "found"
#define MAX_LETTERS 40

/* Comment me */


/* WordList stuff 
The elements are stored in an array.
*/

typedef struct {
    int len;
    int capacity;
    char** data;
} WordList;

/* Populate WordList as an empty list */
void alloc_list(WordList* list)
{
    int i;
    list->len = 0;
    list->capacity = 10;
    list->data = (char**)malloc(sizeof(char*)*10);
    for (i = 0; i<10; ++i) {
        list->data[i] = 0;
    }
}

/* Add a word to the list (increasing capacity if required) */
void add_item(WordList* list, char* word) 
{
    char* t;
    int newCap = list->capacity+10;
    if (list->len==list->capacity) {
        list->data = (char**)realloc(list->data, newCap*sizeof(char*));
        list->capacity = newCap;
    }
    t = (char*)malloc(sizeof(char)*strlen(word)+1);
    strcpy(t, word);
    list->data[list->len++] = t;
}

/* free memory used by the list, does not free the head (l) */
void free_list(WordList l)
{
    int i;
    for (i = 0; i<l.len; ++i) {
        free(l.data[i]);
    }
    free(l.data);
}

/* Sort the list */
/* don't hate me because I used an O(n^2) sort */
void sort(WordList l)
{
    char* temp;
    int i, j, m;
    for (i = 0; i<l.len; ++i) {
        m = i;
        for(j = i; j<l.len; ++j) {
            if (strcmp(l.data[j], l.data[m])<0) {
                m = j;
            }
        }
	temp = l.data[m];
        l.data[m] = l.data[i];
        l.data[i] = temp;
    }
}

/* Output the contents of l to a file */
void write_list(WordList l, FILE* out)
{
    int i;
    for (i = 0; i<l.len; ++i) {
        fprintf(out, "%s\n", l.data[i]);
    }
}

/* end WordList*/


/* Grid struct routines */

/* access element R, C in grid A */ 
#define IND(A, R, C) A.data[R][C]

/* True if V is a valid index for A*/
#define IN_RANGE(A, V) ((V<A.dim) && (V>-1))

typedef struct {
    int dim;
    char** data;
} Grid;

/* Allocate memory for (r) as a 2D array with dimension (size) */
void alloc_grid(Grid* r, unsigned int size)
{
    unsigned int c; 
    r->dim = size;
    r->data = (char**)malloc(sizeof(char*)*size);
    for (c = 0; c<size; ++c) {
        r->data[c] = (char*)malloc(sizeof(char)*size);
    }
}

/* Free memory for Grid g - does not free the struct itself */
void free_grid(Grid g)
{
    int c;
    for (c = 0; c<g.dim; ++c) {
        free(g.data[c]);
    }
    free(g.data);
}

/* Uses info in file (f) to create and populate two grids.
chars from f are copied into g while (used) is filled with '*'
The return value is an error code.
Error conditions include 
- invalid grid dimension (the first line of the file).
- incomplete or missing lines.
- extra chars or extra lines.
- non letter chars in the grid.
*/
int read_grid(FILE* f, Grid* g, Grid* used) 
{
    int res;
    unsigned int dim, i, j;
    char c;
    res = fscanf(f, "%u", &dim);	
    if ((res!=1) || (dim==0) || ((int)dim < 0)) {  
        return BAD_SIZE;
    }
    res = fscanf(f, "%c", &c);   /* check to see if \n follows number */
    if ((res!=1) || (c!='\n')) {
        return BAD_SIZE;
    }
    alloc_grid(g, dim);
    alloc_grid(used, dim);
    for (i = 0; i<dim; ++i) {
        for (j = 0; j<dim; ++j) {
            res = fscanf(f, "%c", &c);
            if ((res!=1) || (!isalpha(c))) {
                free_grid(*g);
                free_grid(*used);
		return MISSING_DATA;
            }
            g->data[i][j] = c;
            used->data[i][j] = '*';
        }
        res = fscanf(f, "%c", &c);
        if ((res!=1) || (c!='\n')) {
            return MISSING_DATA;	/* actually its too much */
        }
    }
    return 0;
}

/* End Grid routines */

/* Send unused letters from g to stdout */
/* used for debugging */
void print_remaining(Grid g, Grid used)
{
    int r, c;
    for (r = 0; r<g.dim; ++r) {
        for (c = 0; c<g.dim; ++c) {
            if (IND(used, r, c)!='.') {
                printf("%c", IND(g, r, c));
            }
        }
    }
    printf("\n");
}

/* 
Used as a helper for find_word.
search for word (w) in grid (g). starting at row r and column c.
The search moves in the direction indicated by cstep and rstep.
If a word is found, the corresponding cells in (used) are replaced
with '.'
Returns FALSE if the word is not found, TRUE if it is.
*/
boolean match_word(Grid g, Grid used, char* w, int r, int c, 
                   int cstep, int rstep)
{
    int pos;
    int sr = r, sc = c;
    int len = 0;
    for (;*w!='\0';w++) {
        if (!IN_RANGE(g, r) || !IN_RANGE(g, c) ||
                (toupper(IND(g, r, c))!=toupper(*w))) {
            return FALSE;
        }
        r += rstep;
        c += cstep;
        len++;
    }
    /* if we get here, then we have a match */
    r = sr;
    c = sc;
    for (pos = 0; pos<len; ++pos) {
        IND(used, r, c) = '.';
        r += rstep;
        c += cstep;
    }
    return TRUE;
} 

/* Called from find_words.
search the grid for word w.
Look for the first letter in the grid and search starting at each
possibility. */
boolean find_word(Grid g, Grid used, char* w)
{
    /* Find each location of the first letter */
    /* Search in each of the 8 directions for the word*/
    int r, c, dx, dy;
    for (r = 0; r<g.dim; ++r) {
        for (c = 0; c<g.dim; ++c) {
            if (toupper(IND(g, r, c))==toupper(*w)) {
                for (dx = -1; dx<2; ++dx) {
                    for (dy = -1; dy<2; ++dy) {
                        if (((dx!=0) || (dy!=0)) 
                                && match_word(g, used,  w, r, c, dx, dy)) {
                            return TRUE;
                        }
                    }
                }
            }
        }
    }
    return FALSE;
}

/* Display an error message to stderr and exit the program.
Does not close files. */
void print_and_exit(int errNum, const char* extra) 
{
    switch (errNum) {
        case MISSING_DATA:
            fprintf(stderr, "Error: invalid grid lines\n");
            break;
        case BAD_SIZE:
            fprintf(stderr, "Error: invalid grid size\n");
            break;
        case BAD_FILE_OPEN:
            fprintf(stderr, "Error: could not open file %s\n", extra); 
            break;
        case BAD_USE:
            fprintf(stderr, "Usage: wordsearch [-sort] [-out "
                    "output-filename] grid-filename list-filename\n");
            break;
    }
    exit(errNum);
}

/* Process command parameters. Open files are passed back via params.
On error, files are closed and exit() is called.
*/
void do_params(int argc, const char** argv, const char** gridName, 
    const char** listName, const char** outName)
{
    int i = 1;
    boolean haveSort = FALSE;
    *gridName = 0;
    *listName = 0;
    *outName = 0;
    if (argc<3 || argc>6)
    {
        print_and_exit(BAD_USE, 0);
    }
    /* Look for -sort and -out in either order */
    while (i<argc) {
        if (strcmp(argv[i], "-sort")==0 && !haveSort) {
           haveSort = TRUE;
           ++i;
        } else if (strcmp(argv[i], "-out")==0 && outName!=0) {
            if (i+1<argc) {
                *outName = argv[i+1];
            }
            i += 2;
        } else {
            break;
        }
    }
    if (i==argc-2) {
        *gridName = argv[i++];
        *listName = argv[i];
        if (*outName==0) {
            *outName = DEFAULT_OUT_NAME;
        } 
    } else {
        print_and_exit(BAD_USE, 0);
    }
}

/* read lines from wFile and search for them in the grid */
void find_words(Grid g, Grid used, FILE* wFile, FILE* foundFile)
{
    char line[MAX_LETTERS];
    WordList wl;
    alloc_list(&wl);
    while (fscanf(wFile, "%40s\n", line)==1) {
        if (find_word(g, used, line)) {
            add_item(&wl, line);
        }
    }
    sort(wl);
    write_list(wl, foundFile);
    free_list(wl);
}

/* Open files for the grid, the list and the found file.
File pointers are returned by reference.
On error, open files are closed and the program exits. */
void open_files(const char* gName, const char* listName, 
               const char* outName, FILE** gFile, 
               FILE** wFile, FILE** foundFile)
{
    *gFile = fopen(gName, "r");
    if (*gFile==0) {
        print_and_exit(BAD_FILE_OPEN, gName);
    }
    *wFile = fopen(listName, "r");
    if (*wFile==0) {
        fclose(*gFile);
        print_and_exit(BAD_FILE_OPEN, listName);
    }
    *foundFile = fopen(outName, "w");
    if (*foundFile==0) {
        fclose(*gFile);
        fclose(*gFile);
        print_and_exit(BAD_FILE_OPEN, outName);
    }
}

int main(int argc, const char** argv)
{
    const char* gName, *listName;
    const char* outName;
    int res = 0;
    FILE* gFile, *wFile, *foundFile;
    Grid inGrid;
    Grid used;
    do_params(argc, argv, &gName, &listName, &outName);
    open_files(gName, listName, outName, &gFile, &wFile, &foundFile);
    res = read_grid(gFile, &inGrid, &used);
    fclose(gFile);
    if (res!=0) {
        fclose(wFile);
        print_and_exit(res, "");
    }
    /* any exits past this point need to free Grid */
    find_words(inGrid, used, wFile, foundFile);
    print_remaining(inGrid, used);
    free_grid(inGrid);
    free_grid(used);   
    return 0;
}