/*
 *  chainword.c --- Lecture version 4/11/2005
 *  Nadeem Abdul Hamid
 *
 *  (Based on Ch. 3, The Practice of Programming, Kernighan/Pike)
 */
 
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "chainword.h"

/* uncomment this for extra debugging printouts */
/* #define DEBUG */

#ifdef DEBUG
#define DEBUGPRN( s )  printf( ">>>### %s\n", s )
#else
#define DEBUGPRN( s )
#endif


/************************************************************************/
/* Function implementations */

/* Displays an entry node: its prefix and suffixes */
void print_entry( Entry e ) {
        int i;
        Suffix *suf;
        
        for ( i = 0; i < NUMPREFS; i++ ) 
            printf("pref[%d] = %s | ", i, e.pref[i] );
        printf("num sufs = %d | ", e.num_sufs );
        suf = e.suf;
        while ( suf != NULL ) {
            printf( "%s | ", suf->word);
            suf = suf->next_suffix;
        }
        printf("\n");
}


/* Displays a list of entry nodes */
void print_table( Entry* table ) {
    Entry *cur = table;
    int count = 0;
    
    while ( cur != NULL ) {
        printf("\n ENTRY %d ===========\n", count++);
        print_entry( *cur );
        cur = cur->next_entry;
    }
}


/* inputs a word from keyboard and 
   returns it */
char* input_word( void ) {
    char buf[100];
    char *word;
    int len;
    
    if ( scanf( "%99s", buf ) != 1 ) {
        return NULL;
    }
    buf[99] = '\0';

    /* buf array will be reclaimed upon function exit, so we
       dynamically allocate some memory for the string just read
       and copy the buf string into it */
    len = strlen(buf);
    word = malloc( (len+1) * sizeof(char) );
    strcpy( word, buf );
    DEBUGPRN( word );
    return word;
}


/* compares two arrays of strings for equality */
boolean compare_pref( char* prefA[NUMPREFS], char* prefB[NUMPREFS] ) {
    int i;
    for ( i = 0; i < NUMPREFS; i++ ) 
        if ( strcasecmp( prefA[i], prefB[i] ) != 0 )
            return false;
    return true;
}


/* returns pointer to entry in the table with the prefix
   returns NULL if not found */
Entry* lookup( Entry *table, char* pref[NUMPREFS] ) {
    Entry *cur = table;

    DEBUGPRN( "in lookup" );
    while ( cur != NULL ) {
        if ( compare_pref( cur->pref, pref ) ) {
            return cur;
        }
        cur = cur->next_entry;
    }
    DEBUGPRN( "lookup ret: NULL?" );
    return cur;  /* == NULL */
}


/* adds entry for the prefix into the table, possibly modifying
   the table pointer and returns a pointer to the newly inserted
   entry */
Entry* add( Entry **table_ptr, char* pref[NUMPREFS] ) {
    Entry *new_entry = malloc( sizeof(Entry) );
    int i;
    
    DEBUGPRN( "in add" );
    for ( i = 0; i < NUMPREFS; i++ ) 
        new_entry->pref[i] = pref[i];
    new_entry->next_entry = *table_ptr;
    new_entry->num_sufs = 0;
    new_entry->suf = NULL;
    
    *table_ptr = new_entry;
    return new_entry;
}


/* adds a suffix entry to the list of suffix words for
   a given entry */
void add_suffix( Entry *entry, char *word ) {
    Suffix *new_suf = malloc( sizeof(Suffix) );

    DEBUGPRN( "in add_suffix" );
    new_suf->word = word;
    new_suf->next_suffix = entry->suf;
    entry->suf = new_suf;
    entry->num_sufs++;
}


/* Function to build up a table of Entry's from input */
Entry* build( void ) {
    Entry *etable = NULL;
    char *pref[NUMPREFS];   /* current prefix */
    char *word;
    int i;

    DEBUGPRN( "in build" );
    for ( i = 0; i < NUMPREFS; i++ ) {
        if ( (pref[i] = input_word()) == NULL ) {
            printf( "Error reading initial input words.\nProgram terminating.\n" );
            exit(-1);
        }
    }

    while ( ( word = input_word() ) != NULL ) {
        Entry *entry = lookup( etable, pref );
        if ( entry == NULL ) 
            entry = add( &etable, pref );
        add_suffix( entry, word );
        
        for ( i = 1; i < NUMPREFS; i++ )
            pref[i-1] = pref[i];
        pref[i-1] = word;
    }

    return etable;
}


/* pick a random suffix word from an entry */
char* pick_suffix( Entry e ) {
    int i = 0;
    int pos = rand() % e.num_sufs;
    Suffix *suf = e.suf;
    
    while ( i++ < pos )
        suf = suf->next_suffix;
    return suf->word;
}


/* generate a bunch of words from the table, using
   the markov chain algorithm */
void generate( Entry *etable ) {
    Entry *cur = etable;
    char **sel_pref = cur->pref;
    char *pref[NUMPREFS];
    int i = 0, words = NUMPREFS;

    printf( "\n\n" );

    while ( cur->next_entry != NULL ) {
        cur = cur->next_entry;
        if ( rand() % ++i == 0 )
            sel_pref = cur->pref;
    }
    
    for ( i = 0; i < NUMPREFS; i++ ) {
        pref[i] = *(sel_pref + i);
        printf( "%s ", pref[i] );
    }
    
    cur = lookup( etable, pref );
        
    while ( cur != NULL && words++ < WORDSTOGEN ) {
        char *suf = pick_suffix( *cur );
        printf ( " %s ", suf );
        for ( i = 1; i < NUMPREFS; i++ )
            *(pref+i-1) = *(pref+i);
        *(pref+i-1) = suf;
        cur = lookup( etable, pref );
    }

    printf( "\n\n" );
}


int main( void ) {
    Entry *etable;
    
    srand( time(NULL) );
    
    etable = build();
    /* print_table( etable ); */

    generate( etable );

    return 0;
}