/* -------------------------------------------------------------------------
 * Margana - A general purpose anagrammer with pattern-anchored matching.
 * Copyright (C) 2000 Moshe Jacobson <moshe@runslinux.net>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * -------------------------------------------------------------------------
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>
#include <sys/ioctl.h> /* For getting screen width */
#include <signal.h>
#include <termios.h>
#include <unistd.h>

#define VERSION "1.1"
#define DEFAULT_DICTFILE "words"
#define MAXWORDLEN 30  /* Maximum word length + 2 */

typedef struct _letter {
    struct _letter **next;
    unsigned int nptrs  : 5;
    unsigned int isword : 1;
    unsigned int padding:26;
} letter;

/* The 27 subarrays of after_i_ranked_j represent the 26 letters of the
 * alphabet plus the start-of-word, represented by 27. The numbers in the
 * subarrays each represent a letter of the alphabet (0=a, 25=z). Their
 * position in each of the subarrays indicates how frequently they appear
 * after the letter represented by the entire subarray (e.g., the letter at
 * index 0 appears most frequently after the letter represented by the
 * subarray in which it appears). The last subarray indicates how frequently
 * the letters appear at the heads of words, relative to each other. The i and
 * j in the variable name represent, respectively, the 1st and 2nd indices
 * into the matrix. */
int after_i_ranked_j[27][26] = {
/*A*/{ 19,11,13,17,18,2,1,12,3,15,6,8,20,21,24,10,22,5,4,25,23,7,9,16,14,0 },
/*B*/{ 11,8,4,0,14,17,20,1,18,24,19,3,2,9,12,13,21,7,15,5,22,6,10,25,16,23 },
/*C*/{ 14,0,7,4,8,19,10,17,20,11,24,2,18,16,13,3,25,12,1,15,22,5,6,9,21,23 },
/*D*/{ 4,8,14,0,18,17,20,11,3,13,24,6,12,22,1,7,21,5,9,15,2,19,25,10,16,23 },
/*E*/{ 18,17,3,13,11,19,0,2,12,4,15,23,6,5,8,14,21,1,20,22,24,7,16,10,25,9 },
/*F*/{ 8,4,14,11,20,0,5,17,19,24,18,1,13,7,15,3,12,2,22,6,9,10,16,21,23,25 },
/*G*/{ 4,8,17,0,11,14,18,20,7,6,13,24,12,1,19,22,5,3,15,2,10,9,25,21,16,23 },
/*H*/{ 4,14,8,0,24,17,20,19,18,11,13,12,1,22,5,15,3,2,7,10,6,9,16,25,21,23 },
/*I*/{ 13,18,2,19,14,4,11,0,3,25,12,21,17,6,15,5,1,10,20,23,16,7,22,8,9,24 },
/*J*/{ 20,0,4,14,8,9,13,3,18,10,1,2,5,6,7,11,12,15,16,17,19,21,22,23,24,25 },
/*K*/{ 4,8,18,0,11,13,14,24,7,1,17,20,22,12,19,5,15,10,3,2,6,21,9,16,23,25 },
/*L*/{ 4,8,0,11,14,24,20,18,19,3,12,13,10,2,5,21,15,1,6,7,22,17,25,16,23,9 },
/*M*/{ 4,8,0,14,15,18,1,20,12,24,13,11,5,17,2,22,21,7,19,3,10,6,9,25,16,23 },
/*N*/{ 6,4,19,18,8,0,3,14,2,13,20,5,10,21,11,24,7,17,1,12,15,22,9,16,25,23 },
/*O*/{ 13,17,20,11,12,18,19,15,6,2,14,3,21,22,8,1,0,4,5,10,23,24,25,7,16,9 },
/*P*/{ 4,17,14,7,0,8,11,18,15,20,19,24,13,1,12,22,5,2,3,6,10,9,16,21,23,25 },
/*Q*/{ 20,8,0,18,14,22,4,1,2,3,5,6,7,9,10,11,12,13,15,16,17,19,21,23,24,25 },
/*R*/{ 4,8,0,14,18,19,20,12,3,17,24,2,13,6,1,15,11,10,21,5,7,22,16,9,25,23 },
/*S*/{ 19,4,18,8,7,20,2,15,14,0,12,11,13,24,10,22,16,5,1,17,3,6,21,9,25,23 },
/*T*/{ 8,4,0,17,14,18,7,20,19,24,11,2,22,5,12,13,1,25,15,6,3,21,9,10,16,23 },
/*U*/{ 13,18,17,11,19,12,15,2,1,0,8,4,3,6,5,14,10,21,23,25,24,9,20,7,16,22 },
/*V*/{ 4,8,0,14,20,24,17,21,18,11,13,6,10,3,25,1,2,5,7,9,12,15,16,19,22,23 },
/*W*/{ 0,4,8,14,7,13,18,17,11,1,3,10,19,5,24,12,15,20,2,22,6,25,9,16,21,23 },
/*X*/{ 8,4,19,15,0,2,14,24,20,7,18,11,5,22,1,12,16,6,13,3,21,9,10,17,23,25 },
/*Y*/{ 18,15,11,12,4,2,19,8,13,0,17,14,3,6,1,22,25,5,7,20,23,10,21,9,24,16 },
/*Z*/{ 4,0,8,14,25,24,11,20,12,15,22,7,13,21,1,2,10,16,18,3,6,9,19,5,17,23 },
/*^*/{ 18,2,15,0,17,3,12,1,19,4,8,5,7,14,6,20,11,13,22,21,10,9,16,24,25,23 }
};

/* This matrix is the same as above, except the positions of the values above
 * are now the values of the positions. Think about it; you'll understand. */
int after_i_rankof_j[27][26] = {
/*A*/{ 25,6,5,8,18,17,10,21,11,22,15,1,7,2,24,9,23,3,4,0,12,13,16,20,14,19 },
/*B*/{ 3,7,12,11,2,19,21,17,1,13,22,0,14,15,4,18,24,5,8,10,6,16,20,25,9,23 },
/*C*/{ 1,18,11,15,3,21,22,2,4,23,6,9,17,14,0,19,13,7,12,5,8,24,20,25,10,16 },
/*D*/{ 3,14,20,8,0,17,11,15,1,18,23,7,12,9,2,19,24,5,4,21,6,16,13,25,10,22 },
/*E*/{ 6,17,7,2,9,13,12,21,14,25,23,4,8,3,15,10,22,1,0,5,18,16,19,11,20,24 },
/*F*/{ 5,11,17,15,1,6,19,13,0,20,21,3,16,12,2,14,22,7,10,8,4,23,18,24,9,25 },
/*G*/{ 3,13,19,17,0,16,9,8,1,21,20,4,12,10,5,18,24,2,6,14,7,23,15,25,11,22 },
/*H*/{ 3,12,17,16,0,14,20,18,2,21,19,9,11,10,1,15,22,5,8,7,6,24,13,25,4,23 },
/*I*/{ 7,16,2,8,5,15,13,21,23,24,17,6,10,0,4,14,20,12,1,3,18,11,22,19,25,9 },
/*J*/{ 1,10,11,7,2,12,13,14,4,5,9,15,16,6,3,17,18,19,8,20,0,21,22,23,24,25 },
/*K*/{ 3,9,19,18,0,15,20,8,1,22,17,4,13,5,6,16,23,10,2,14,11,21,12,24,7,25 },
/*L*/{ 2,17,13,9,0,14,18,19,1,25,12,3,10,11,4,16,23,21,7,8,6,15,20,24,5,22 },
/*M*/{ 2,6,14,19,0,12,21,17,1,22,20,11,8,10,3,4,24,13,5,18,7,16,15,25,9,23 },
/*N*/{ 5,18,8,6,1,11,0,16,4,22,12,14,19,9,7,20,23,17,3,2,10,13,21,25,15,24 },
/*O*/{ 16,15,9,11,17,18,8,23,14,25,19,3,4,0,10,7,24,1,5,6,2,12,13,20,21,22 },
/*P*/{ 4,13,17,18,0,16,19,3,5,21,20,6,14,12,2,8,22,1,7,10,9,23,15,24,11,25 },
/*Q*/{ 2,7,8,9,6,10,11,12,1,13,14,15,16,17,4,18,19,20,3,21,0,22,5,23,24,25 },
/*R*/{ 2,14,11,8,0,19,13,20,1,23,17,16,7,12,3,15,22,9,4,5,6,18,21,25,10,24 },
/*S*/{ 9,18,6,20,1,17,21,4,3,23,14,11,10,12,8,7,16,19,2,0,5,22,15,25,13,24 },
/*T*/{ 2,16,11,20,1,13,19,6,0,22,23,10,14,15,4,18,24,3,5,8,7,21,12,25,9,17 },
/*U*/{ 9,8,7,12,11,14,13,23,10,21,16,3,5,0,15,6,24,2,1,4,22,17,25,18,20,19 },
/*V*/{ 2,15,16,13,0,17,11,18,1,19,12,9,20,10,3,21,22,6,8,23,4,7,24,25,5,14 },
/*W*/{ 0,9,18,10,1,13,20,4,2,22,11,8,15,5,3,16,23,7,6,12,17,24,19,25,14,21 },
/*X*/{ 4,14,5,19,1,12,17,9,0,21,22,11,15,18,6,3,16,23,10,2,8,20,13,24,7,25 },
/*Y*/{ 9,14,5,12,4,17,13,18,7,23,21,2,3,8,11,1,25,10,0,6,19,22,15,20,24,16 },
/*Z*/{ 1,14,15,19,0,23,20,11,2,21,16,6,8,12,3,9,17,24,18,22,7,13,10,25,5,4 },
/*^*/{ 3,7,1,5,9,11,14,12,10,21,20,16,6,17,13,2,22,4,0,8,15,19,18,25,23,24 }
};

letter *dict = NULL;
letter *valid = NULL;

int numvalid = 0;
char **list = NULL;
int maxwordlen;
int screenwidth;

/* Adds a word to the passed-in trie */
int addword( const char *word, letter **headp ) {
    static char last='a'+26;
    char curr=*word;
    
    /* Should never be passed a NULL headp */
    if( !headp ) return -1;

    /* If our current node has not yet been allocated . . . */
    if( !*headp ) {
        if( (*headp=calloc(1,sizeof(letter))) == NULL ) return -1;
    }

    /* When we reach the end of our word . . . */
    if( !curr ) {
        (*headp)->isword = 1;
        last='a'+26;
        return 0;
    } else {
        int rank = after_i_rankof_j[last-'a'][curr-'a'];
        letter *head=*headp;
        int i;

        /* If our array of pointers isn't large enough yet, we must allocate
         * more space for this new letter */
        if( head->nptrs <= rank ) {
            head->next = realloc(head->next, (1+rank)*sizeof(letter*));
            if( !head->next ) return -1;
            for( i=head->nptrs; i<=rank; i++ ) head->next[i] = NULL;
            head->nptrs = rank+1;
        }

        /* Update "last" and recurse */
        last=curr;
        return addword( word+1, &head->next[rank] );
    }
}

/* Checks the given trie for the existence of word */
int isword( const char *word, const letter *head ) {
    /* We set the initial value of our last character to 'a'+26, which is the
     * start-of-word index into the matrices above. */
    static char last='a'+26;
    char this=*word;
    int rc=0;

    if( !head ) goto end;

    if( !this ) {
        rc=head->isword;
        goto end;
    } else {
        int rank;
        
        /* Got a nonalphabetic request. Shouldn't happen. */
        if( !isalpha((int)this) ) goto end;

        rank = after_i_rankof_j[last-'a'][this-'a'];
        if( head->nptrs < rank+1 ) {
            goto end;
        } else {
            last=this;
            rc=isword( word+1, head->next[rank] );
            goto end;
        }
    }

end:
    last='a'+26;
    return rc;

}

/* Take our rack's letters and move the blanks to the end */
int blanks2end( char *rack ) {
    int numblank=0;
    char *cp2, *cp1;

    for( cp2=rack; *cp2; cp2++ ) {
        if( *cp2 == '?' ) numblank++;
    }
    cp2--;
    while( cp2 > rack && *cp2 == '?' ) cp2--;
    for( cp1 = rack; cp1 < cp2; cp1++ ) {
        if( *cp1 == '?' ) {
            *cp1 = *cp2;
            *(cp2--) = '?';
        }
    }
    return numblank;
}

/* Make sure our rack is all lowercase.
 * Return -1 if rack has invalid characters or 0 o.w. */
int strlower( char *str ) {
    char *cp = str-1;
    while( *(++cp) ) {
        if( !isalpha((int)*cp) && *cp != '?' ) return -1;
        *cp = tolower(*cp);
    }
    return 0;
}

int addtolist( char *word ) {
    char **listtmp = realloc(list, numvalid * sizeof(char*));

    if( !listtmp ) return -1;
    list = listtmp;

    if( (list[numvalid-1]=malloc(strlen(word))) == NULL ) return -1;
    strcpy( list[numvalid-1], word );
    return 0;
}

int lencmp( const void *word1, const void *word2 ) {
    int lendiff = strlen(*(char**)word1) - strlen(*(char**)word2);
    if( !lendiff ) return strcmp( *(char**)word1, *(char**)word2 );
    else return lendiff;
}

/* Sorts and prints the words in list */
int printlist( void ) {
    int i;

    qsort( list, numvalid, sizeof(char*), lencmp );
    
    if( numvalid ) maxwordlen = strlen(list[numvalid-1]); 
    else maxwordlen = MAXWORDLEN;

    i=0;
    while( i<numvalid ) {
        int col = 2;

        printf( " " );
        while( col + maxwordlen + 1 < screenwidth && i<numvalid ) {
            printf( "%-*s ", maxwordlen, list[i] );
            free(list[i++]);
            col += maxwordlen + 1;
        }
        printf( "\n" );
    }
    free(list);
    list = NULL;

    return 0;
}


/* Frees the memory used by the passed-in tree */
void freetree( letter **headp ) {
    int i;
    letter *head=*headp;

    if(!head) return;
    for( i = 0; i < head->nptrs; i++ ) freetree( &head->next[i] );
    if( head->nptrs ) free(head->next);
    free(head);
    *headp = NULL;
}

/* Anagrams the letters in rack_in against the wordlist trie in *head. Goes
 * through every word and attempts to make it with the letters in the rack.
 * More efficient than anagpat, but does not allow for pattern matching. */
void anagram( const letter *head, char *curr, const char *rack_in ) {
    int i, j;
    char last='a'+26;
    static char rack[MAXWORDLEN];
    int foundltr = 0;
    int currlen = strlen(curr);
    int racklen = strlen(rack_in);

    /* Return if this letter is null, or the word is longer
     * than our rack itself */
    if( !head || currlen > racklen ) return;

    if( head->isword ) {
        /* Make a local copy of the rack so we can play with it */
        strcpy( rack, rack_in );

        /* Iterate through the letters of the current word */
        for( i = 0; i<currlen; i++ ) {
            foundltr = 0;

            /* Iterate through the letters of our rack */
            for( j = 0; j < racklen; j++ ) {

                /* If we have a letter or wildcard match, place a 
                 * "#" over the letter so it won't be reused */
                if( rack[j] == curr[i] || rack[j] == '?' ) {
                    rack[j] = '#';
                    foundltr = 1;
                    break;
                }
            }
            if( !foundltr ) break;
        }

        if( foundltr && !isword(curr, valid) ) {
            numvalid++;
            addword( curr, &valid );
            addtolist( curr );
        }
    }

    last = (currlen ? curr[currlen-1] : 'a'+26);
    curr[currlen+1] = '\0';
    
    for( i = 0; i < head->nptrs; i++ ) {
        curr[currlen] = 'a' + after_i_ranked_j[last-'a'][i];
        anagram( head->next[i], curr, rack_in );
    }

    curr[currlen] = '\0';
    last='a'+26;

    return;
}
    

/* Anagrams the letters in 'rack' against the pattern in 'pattern', by
 * permuting the letters in 'rack' into the pattern space and checking whether
 * each permutation is a word. Less efficient, but works with patterns.
 * Note: Only attempts to make words that start in the first character of the
 * pattern space. This is why anagpat_main() is used. */
void anagpat( char *pattern, char *rack, unsigned int minlen ) {
    int racklen = strlen(rack);
    int i;
    char *spot, *endp, tmp;

    /* Point spot at the first '?' */
    if( (spot=strchr(pattern, '?')) == NULL ) return;
    
    /* Cycle through the letters in the rack */
    for( i = 0; i < racklen; i++ ) {
        /* Set the first '?' to the current rack letter */
        *spot = rack[i];
        /* Remove this letter from the rack */
        rack[i] = rack[racklen-1];
        rack[racklen-1] = '\0';
        /* If there is another '?' after this, make it the end of string */
        endp=strchr(spot+1, '?');
        /* If what we have now is a valid word, add it */

        tmp=*spot;
        for( *spot = (tmp=='?'?'a':tmp); *spot <= (tmp=='?'?'z':tmp); (*spot)++ ) {
            if(endp) *endp = '\0';
            if( strlen(pattern) >= minlen ) {
                if( isword( pattern, dict ) && !isword( pattern, valid ) ) {
                    numvalid++;
                    addword( pattern, &valid );
                    addtolist( pattern );
                }
            }
            if(endp) *endp = '?';
            anagpat( pattern, rack, minlen );
        }
        *spot = tmp;

        /* Restore stuff */
        rack[racklen-1] = rack[i];
        rack[racklen] = '\0';
        rack[i] = *spot;
        *spot = '?';
    }
    return;
}

/* Basically calls anagpat() for every valid starting spot in pattern */
void anagpat_main( char *pattern, char *rack ) {
    char qmark[2] = { '?', '\0' };
    int patlen = strlen(pattern);
    int minlen = strspn(pattern,qmark);
    int showall = !(patlen-minlen);
    
    anagpat( pattern, rack, minlen );
    while( *(++pattern) ) {
        minlen = strspn(pattern, qmark);
        patlen--;
            if( *(pattern-1) != '?' || 
                (patlen <= minlen && !showall) ) continue;
        anagpat( pattern, rack, minlen );
    }
}
    
/* Reads the dictionary into memory */
int index_dict( char *fname, letter **dictp ) {
    FILE *fp;
    char curr[MAXWORDLEN] = {0}, tmp;
    int currlen, i;

    if( (fp=fopen(fname,"r")) == NULL ) {
        fprintf( stderr, "Invalid dictionary filename, \"%s\".\n", fname );
        return -1;
    }

    fprintf( stderr, "Indexing dictionary . . . " );
    fflush(stderr);
    while( (fgets( curr, MAXWORDLEN, fp )) ) {
        currlen = strlen(curr)-1;

        /* If we didn't read a whole line, the word is too long. 
         * Read remainder of line, then continue */
        if( curr[currlen] != '\n' ) {
            char c;
            while( (c=fgetc(fp)) != EOF && c != '\n' ) ;
            continue;
        }

        curr[currlen] = '\0';
        for( i=0; i<currlen; i++ ) {
            tmp = curr[i];
            if( tmp < 'a' || tmp > 'z' ) break;
        }
        if( i<currlen ) continue;
        
        if( addword( curr, dictp ) == -1 ) {
            fprintf( stderr, "Error (out of memory?)\n" );
            return -1;
        }
    }
    fprintf( stderr, "done.\n" );
    fflush(stderr);
    return 0;
}


void print_usage( void ) {
    printf( "  Margana v" VERSION ", (c) 2001 \n"
    "  Moshe Jacobson <moshe@runslinux.net>\n"
    "  \n"
    "      Usage: margana [dictfile]\n"
    "  \n"
    "  Margana is a interactive anagrammer geared toward use with Scrabble.\n"
    "  It prompts for a rack of letters and a pattern of open letters and\n"
    "  surrounding spaces on the board. It then returns all words composed\n"
    "  of at least one letter on the board and at least one letter from\n"
    "  your rack, that fit _within_ the given pattern.\n"
    "  \n" );
    printf( "  Margana requires a list of valid words against which to anagram. It\n"
    "  assumes your word list is in a file called \""DEFAULT_DICTFILE"\" in the current\n"
    "  directory. However, an alternate wordlist may optionally be specified\n"
    "  as the first parameter.\n"
    "  \n" );
    printf( "  If the board pattern provided is a single * character, all possible\n"
    "  anagrams of any size, that can be made from your rack, will be shown.\n"
    "  If the board pattern contains all ? characters, all anagrams of your\n"
    "  letters that fit within the number of spaces indicated will be shown.\n" );
}

/* Signal handler for SIGWINCH, the window size change signal */
void setwidth( int signum ) {
    struct winsize windowsize;

    if( ioctl(0, TIOCGWINSZ, &windowsize) == 0 ) {
        screenwidth = windowsize.ws_col;
    } else {
        screenwidth = 80;
    } 
    signal(signum, setwidth);
}

/* A specialized function to read a line of input and do some rudimentary
 * error checking. This avoids a lot of repeated code in main(). */
char *readline( char *desc, char *defval ) {
    static char input[MAXWORDLEN];
    int len;

    while(1) {
        printf( "%s [%s]: ", desc, defval );
        do {
            errno = 0;
            fgets( input, MAXWORDLEN, stdin );
        } while( errno == EINTR );

        len = strlen(input) - 1;

        if( *input == '\n' && !*defval ) {
            fprintf( stderr, "Must enter something!\n" );
            continue;
        }

        if( input[len] != '\n' ) {
            char c;
            fprintf( stderr, "Line too long. Try again.\n" );
            while( (c=fgetc(stdin)) != '\n' ) ;
            continue;
        }

        input[len] = '\0';

        if( !*input ) strcpy(input, defval);
        break;
    }
    return input;
}
    

int main( int argc, char *argv[] ) {
    char *tmp;
    char pat[MAXWORDLEN] = {0};
    char rack[MAXWORDLEN] = {0};
    char *dictfile = DEFAULT_DICTFILE;
    int racklen = 0, patlen = 0;
    int numblank = 0;

    if( argv[1] && !strcmp(argv[1], "--help") ) {
        print_usage();
        return EXIT_SUCCESS;
    }

    if( argc > 1 ) dictfile = argv[1];

    setwidth(SIGWINCH);

    fprintf( stderr, 
        "Margana v%s, (c) 2001 Moshe Jacobson <moshe@runslinux.net>\n"
        "Invoke with --help for usage information.\n",
        VERSION );

    if( index_dict(dictfile, &dict) == -1 ) return EXIT_FAILURE;
       
    while(1) {
        numvalid=0;

        while (1) {
            tmp = readline( "Rack ('?' for blanks)", rack );

            if( strlower(tmp) == -1 ) { 
                fprintf( stderr, "Invalid letters in input. Try again.\n" );
                continue;
            }
            numblank=blanks2end(tmp);

            strcpy(rack,tmp);
            racklen = strlen(rack);
            break;
        }
             
        if( numblank > 2 ) {
            fprintf( stderr, 
            "Over 2 blank tiles in rack. Assuming board pattern '*'.\n" );
            pat[0] = '*'; pat[1] = '\0';
        } else {
            while(1) {
                tmp = readline( "Board pattern ('?' for open spaces), or *", pat );

                if( *tmp != '*' && strlower(tmp) == -1 ) { 
                    fprintf( stderr, "Invalid letters in input. Try again.\n" );
                    continue;
                }
                strcpy(pat,tmp);
                patlen = strlen(pat);
                break;
            }
        }

        if( *pat != '*' ) {
            if(numblank == 2 && racklen >= 6) 
                printf( "Please wait. This will take a while . . .\n" );
            anagpat_main( pat, rack );
        } else {
            *tmp = '\0';
            anagram( dict, tmp, rack );
        }

        if( printlist() == -1 )
            fprintf( stderr, "Error listing words (out of memory).\n" );

        freetree( &valid );
    }
}