/*===========================================================================*/

/*
 *  Copyright (C) 1998 Jason Hutchens
 *
 *  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 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.,
 *  675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*===========================================================================*/

/*
 *      $Id: megahal.c,v 1.10 2004/02/23 11:12:29 lfousse Exp $
 *
 *      File:           megahal.c
 *
 *      Program:        MegaHAL
 *
 *      Purpose:        To simulate a natural language conversation with a psychotic
 *                      computer.  This is achieved by learning from the user's
 *                      input using a third-order Markov model on the word level.
 *                      Words are considered to be sequences of characters separated
 *                      by whitespace and punctuation.  Replies are generated
 *                      randomly based on a keyword, and they are scored using
 *                      measures of surprise.
 *
 *      Author:     Mr. Jason L. Hutchens (http://www.amristar.com.au/~hutch/)
 *
 *      WWW:        http://megahal.sourceforge.net
 *
 *      Compilation Notes
 *      =================
 *
 *      When compiling, be sure to link with the maths library so that the
 *      log() function can be found.
 *
 *      On the Macintosh, add the library SpeechLib to your project.  It is
 *      very important that you set the attributes to Import Weak.  You can
 *      do this by selecting the lib and then use Project Inspector from the
 *      Window menu.
 *
 *      CREDITS
 *      =======
 *
 *      Amiga (AmigaOS)
 *      ---------------
 *      Dag Agren (dagren@ra.abo.fi)
 *
 *      DEC (OSF)
 *      ---------
 *      Jason Hutchens (hutch@ciips.ee.uwa.edu.au)
 *
 *      Macintosh
 *      ---------
 *      Paul Baxter (pbaxter@assistivetech.com)
 *      Doug Turner (dturner@best.com)
 *
 *      PC (Linux)
 *      ----------
 *      Jason Hutchens (hutch@ciips.ee.uwa.edu.au)
 *
 *      PC (OS/2)
 *      ---------
 *      Bjorn Karlowsky (?)
 *
 *      PC (Windows 3.11)
 *      -----------------
 *      Jim Crawford (pfister_@hotmail.com)
 *
 *      PC (Windows '95)
 *      ----------------
 *      Jason Hutchens (hutch@ciips.ee.uwa.edu.au)
 *
 *      PPC (Linux)
 *      -----------
 *      Lucas Vergnettes (Lucasv@sdf.lonestar.org)
 *
 *      SGI (Irix)
 *      ----------
 *      Jason Hutchens (hutch@ciips.ee.uwa.edu.au)
 *
 *      Sun (SunOS)
 *      -----------
 *      Jason Hutchens (hutch@ciips.ee.uwa.edu.au)
 */

/*===========================================================================*/

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <unistd.h>
#include <getopt.h>
#if !defined(AMIGA) && !defined(__mac_os)
#include <malloc.h>
#endif
#include <string.h>
#include <signal.h>
#include <math.h>
#include <time.h>
#include <ctype.h>
#if defined(__mac_os)
#include <types.h>
#include <Speech.h>
#else
#include <sys/types.h>
#endif
#include "megahal.h"
#if defined(DEBUG)
#include "debug.h"
#endif

#include "../irc.h"
#include "megahal-m.h"


#define P_THINK 40
#define D_KEY 100000
#define V_KEY 50000
#define D_THINK 500000
#define V_THINK 250000

#define MIN(a,b) ((a)<(b))?(a):(b)

#define COOKIE "MegaHALv8"
#define TIMEOUT 1

#define DEFAULT "."

#define COMMAND_SIZE (sizeof(command)/sizeof(command[0]))

#define BYTE1 unsigned char
#define BYTE2 unsigned short
#define BYTE4 unsigned long

#ifdef __mac_os
#define bool Boolean
#endif

#ifdef DOS
#define SEP "\\"
#else
#define SEP "/"
#endif

#ifdef AMIGA
#undef toupper
#define toupper(x) ToUpper(x)
#undef tolower
#define tolower(x) ToLower(x)
#undef isalpha
#define isalpha(x) IsAlpha(_AmigaLocale,x)
#undef isalnum
#define isalnum(x) IsAlNum(_AmigaLocale,x)
#undef isdigit
#define isdigit(x) IsDigit(_AmigaLocale,x)
#undef isspace
#define isspace(x) IsSpace(_AmigaLocale,x)
#endif

#ifndef __mac_os
#undef FALSE
#undef TRUE
typedef enum { FALSE, TRUE } bool;
#endif

typedef struct {
    BYTE1 length;
    char *word;
} STRING;

typedef struct {
    BYTE4 size;
    STRING *entry;
    BYTE2 *index;
} DICTIONARY;

typedef struct {
    BYTE2 size;
    STRING *from;
    STRING *to;
} SWAP;

typedef struct NODE {
    BYTE2 symbol;
    BYTE4 usage;
    BYTE2 count;
    BYTE2 branch;
    struct NODE **tree;
} TREE;

typedef struct {
    BYTE1 order;
    TREE *forward;
    TREE *backward;
    TREE **context;
    DICTIONARY *dictionary;
} MODEL;

typedef enum { UNKNOWN, QUIT, EXIT, SAVE, DELAY, HELP, SPEECH, VOICELIST, VOICE, BRAIN, QUIET} COMMAND_WORDS;

typedef struct {
    STRING word;
    char *helpstring;
    COMMAND_WORDS command;
} COMMAND;

/*===========================================================================*/

static int width=75;
static int order=5;

static bool typing_delay=FALSE;
static bool noprompt=FALSE;
static bool speech=FALSE;
static bool quiet=FALSE;
static bool nowrap=FALSE;
static bool nobanner=FALSE;

static char *errorfilename = "megahal.log";
static char *statusfilename = "megahal.txt";
static DICTIONARY *words=NULL;
static DICTIONARY *greets=NULL;
static MODEL *model=NULL;

static FILE *errorfp;
static FILE *statusfp;

static DICTIONARY *ban=NULL;
static DICTIONARY *aux=NULL;
/*static DICTIONARY *fin=NULL; not used */
static DICTIONARY *grt=NULL;
static SWAP *swp=NULL;
static bool used_key;
static char *directory=NULL;
static char *last=NULL;

static COMMAND command[] = {
    { { 4, "QUIT" }, "quits the program and saves MegaHAL's brain", QUIT },
    { { 4, "EXIT" }, "exits the program *without* saving MegaHAL's brain", EXIT },
    { { 4, "SAVE" }, "saves the current MegaHAL brain", SAVE },
    { { 5, "DELAY" }, "toggles MegaHAL's typing delay (off by default)", DELAY },
    { { 6, "SPEECH" }, "toggles MegaHAL's speech (off by default)", SPEECH },
    { { 6, "VOICES" }, "list available voices for speech", VOICELIST },
    { { 5, "VOICE" }, "switches to voice specified", VOICE },
    { { 5, "BRAIN" }, "change to another MegaHAL personality", BRAIN },
    { { 4, "HELP" }, "displays this message", HELP },
    { { 5, "QUIET" }, "toggles MegaHAL's responses (on by default)",QUIET},
    /*
      { { 5, "STATS" }, "Display stats", STATS},
      { { 5, "STATS-SESSION" }, "Display stats for this session only",STATS_SESSION},
      { { 5, "STATS-ALL" },"Display stats for the whole lifetime",STATS-ALL},
    */
};

#ifdef AMIGA
struct Locale *_AmigaLocale;
#endif

#ifdef __mac_os
Boolean gSpeechExists = false;
SpeechChannel gSpeechChannel = nil;
#endif

/* FIXME - these need to be static  */

static void add_aux(MODEL *, DICTIONARY *, STRING);
static void add_key(MODEL *, DICTIONARY *, STRING);
static void add_node(TREE *, TREE *, int);
static void add_swap(SWAP *, char *, char *);
static TREE *add_symbol(TREE *, BYTE2);
static BYTE2 add_word(DICTIONARY *, STRING);
static int babble(MODEL *, DICTIONARY *, DICTIONARY *);
static bool boundary(char *, int);
static void capitalize(char *);
static void changevoice(DICTIONARY *, int);
static void change_personality(DICTIONARY *, unsigned int, MODEL **);
static void delay(char *);
static void die(int);
static bool dissimilar(DICTIONARY *, DICTIONARY *);
static void error(char *, char *, ...);
static float evaluate_reply(MODEL *, DICTIONARY *, DICTIONARY *);
static COMMAND_WORDS execute_command(DICTIONARY *, int *);
static void exithal(void);
static TREE *find_symbol(TREE *, int);
static TREE *find_symbol_add(TREE *, int);
static BYTE2 find_word(DICTIONARY *, STRING);
static char *generate_reply(MODEL *, DICTIONARY *);
static void help(void);
static void ignore(int);
static bool initialize_error(char *);
#ifdef __mac_os
static bool initialize_speech(void);
#endif
static bool initialize_status(char *);
static void learn(MODEL *, DICTIONARY *);
static void listvoices(void);
static void make_greeting(DICTIONARY *);
static void make_words(char *, DICTIONARY *);
static DICTIONARY *new_dictionary(void);

static char *read_input(char *);
static void save_model(char *, MODEL *);
#ifdef __mac_os
static char *strdup(const char *);
#endif
static void upper(char *);
static void write_input(char *);
static void write_output(char *);
#if defined(DOS) || defined(__mac_os)
static void usleep(int);
#endif


static char *format_output(char *);
static void free_dictionary(DICTIONARY *);
static void free_model(MODEL *);
static void free_tree(TREE *);
static void free_word(STRING);
static void free_words(DICTIONARY *);
static void initialize_context(MODEL *);
static void initialize_dictionary(DICTIONARY *);
static DICTIONARY *initialize_list(char *);
static SWAP *initialize_swap(char *);
static void load_dictionary(FILE *, DICTIONARY *);
static bool load_model(char *, MODEL *);
static void load_personality(MODEL **);
static void load_tree(FILE *, TREE *);
static void load_word(FILE *, DICTIONARY *);
static DICTIONARY *make_keywords(MODEL *, DICTIONARY *);
static char *make_output(DICTIONARY *);
static MODEL *new_model(int);
static TREE *new_node(void);
static SWAP *new_swap(void);
static bool print_header(FILE *);
static bool progress(char *, int, int);
static DICTIONARY *reply(MODEL *, DICTIONARY *);
static void save_dictionary(FILE *, DICTIONARY *);
static void save_tree(FILE *, TREE *);
static void save_word(FILE *, STRING);
static int search_dictionary(DICTIONARY *, STRING, bool *);
static int search_node(TREE *, int, bool *);
static int seed(MODEL *, DICTIONARY *);
static void show_dictionary(DICTIONARY *);
static void speak(char *);
static bool status(char *, ...);
static void train(MODEL *, char *);
static void typein(char);
static void update_context(MODEL *, int);
static void update_model(MODEL *, int);
static bool warn(char *, char *, ...);
static int wordcmp(STRING, STRING);
static bool word_exists(DICTIONARY *, STRING);
static int rnd(int);


/*bot*/


char learnchans[MAXCHANS][35] = {
    "#www.elektroda.pl",
    "#ctsg",
    "#listekklonu",
    "#sylwester",
};
char replychans[MAXCHANS][35] = {
    "#testtest",
    "#sylwester",
};

static const char iso[] = {'ą', 'ć', 'ę', 'ł', 'ń', 'ó', 'ś', 'ż', 'ź', 'Ą', 'Ć', 'Ę', 'Ł', 'Ń', 'Ó', 'Ś', 'Ż', 'Ź'};
static const char asc[] = {'a', 'c', 'e', 'l', 'n', 'o', 's', 'z', 'z', 'A', 'C', 'E', 'L', 'N', 'O', 'S', 'Z', 'Z'};

char modname[] = "MEGAHAL";

static void de_iso(char *text){
    char c;
    unsigned short i;
    while((c = *(text++))){
        for(i=0; i<sizeof(iso); i++){
            if(c == iso[i]){
                *(text-1) = asc[i];
                break;
            }
        }
    }
}

int check_links(char *text){
    if(strstr(text, "http://")) return 1;
    if(strstr(text, "<")) return 1;
    if(strstr(text, "=")) return 1;
    if(strstr(text, "/")) return 1;
    return 0;
}

char *strip_hilight(char *text){
    if(strstr(text, ": ")) return strstr(text, ": ") + 2; //hajlajt
    return text;
}

char *do_megahal(char *text){
    static int i;
    char *otext;

    text = strip_hilight(text);
    if(check_links(text)) return "Nie lubie linkow!";
    de_iso(text);
    otext = megahal_do_reply(text, 1);

    if(++i==20){
        megahal_cleanup();
        i=0;
    }

    return otext;
}

void do_megahal_learn(char *text){
    if(check_links(text)) return;
    text = strip_hilight(text);
    de_iso(text);

    megahal_learn_no_reply(text, 1);
}

void init(void){
    megahal_setdirectory ("./megahal");
    megahal_initialize();
}

void cleanup(void){
    megahal_cleanup();
}

int chmsg(struct irc_msg msg){
    char outmsg[500];

    int reply_ok = 0;
    int i;

    strcpy(outmsg, msg.text);
    if(!strcasecmp(get_nick(msg), "lc")) return 0;
//  for(i=0;i<15;i++){
        if(chan_on_list(learnchans, msg.arg1)){
            do_megahal_learn(msg.text);
//          break;
        }
        if(chan_on_list(replychans, msg.arg1)){
            reply_ok = 1;
//          break;
//      }
    }
    if(reply_ok){
        if(rand()>(RAND_MAX/5)) return 0;
        irc_reply(msg, do_megahal(outmsg), 1);
        return 1;
    }
    return 0;
}

int ctcp(struct irc_msg msg){
    if(!strncmp(msg.text+1, "ACTION", 6) && dst_chan(msg) && chan_on_list(replychans,msg.arg1)){
        sock_printf("PRIVMSG %s :\x01""ACTION nie lubi, kiedy %s uzywa /me :(\x01", msg.arg1, get_nick(msg));
        return 1;
    }
    return 0;
}

/* Function: setnoprompt

   Purpose: Set noprompt variable.

 */
void megahal_setnoprompt(void)
{
    noprompt = TRUE;
}

void megahal_setnowrap (void)
{
    nowrap = TRUE;
}
void megahal_setnobanner (void)
{
    nobanner = TRUE;
}

void megahal_seterrorfile(char *filename)
{
    errorfilename = filename;
}

void megahal_setstatusfile(char *filename)
{
    statusfilename = filename;
}

void megahal_setdirectory (char *dir)
{
    directory = dir;
}

/*
   megahal_initialize --

   Initialize various brains and files.

   Results:

   None.
*/

void megahal_initialize(void)
{
    errorfp = stderr;
    statusfp = stdout;

    initialize_error(errorfilename);
    initialize_status(statusfilename);
    ignore(0);

#ifdef AMIGA
    _AmigaLocale=OpenLocale(NULL);
#endif
#ifdef __mac_os
    gSpeechExists = initialize_speech();
#endif
    if(!nobanner)
    fprintf(stdout,
        "+------------------------------------------------------------------------+\n"
        "|                                                                        |\n"
        "|  #    #  ######   ####     ##    #    #    ##    #                     |\n"
        "|  ##  ##  #       #    #   #  #   #    #   #  #   #               ###   |\n"
        "|  # ## #  #####   #       #    #  ######  #    #  #              #   #  |\n"
        "|  #    #  #       #  ###  ######  #    #  ######  #       #   #   ###   |\n"
        "|  #    #  #       #    #  #    #  #    #  #    #  #        # #   #   #  |\n"
        "|  #    #  ######   ####   #    #  #    #  #    #  ######    #     ###r6 |\n"
        "|                                                                        |\n"
        "|                    Copyright(C) 1998 Jason Hutchens                    |\n"
        "+------------------------------------------------------------------------+\n"
        );

    words = new_dictionary();
    greets = new_dictionary();
    change_personality(NULL, 0, &model);
}

/*
   megahal_do_reply --

   Take string as input, and return allocated string as output.  The
   user is responsible for freeing this memory.

  */

char *megahal_do_reply(char *input, int log)
{
//    static char oldinput[4100];
//    char tmp[4098];
    char *output = NULL;

    if (log != 0)
    write_input(input);  /* log input if so desired */

    upper(input);

//    strncpy(tmp, oldinput, 2048);
//    strcat(tmp, " ");
//    strncat(tmp, input, 2048);
//    strncpy(oldinput, input, 2048);
//    strcat(oldinput, " ");

    make_words(input/*tmp*/, words);

    output = generate_reply(model, words);

    make_words(input, words);

    learn(model, words);

 //   strncat(oldinput, output, 2048);

 //   printf("oldinput: %s\n", oldinput);

    capitalize(output);
    return output;
}

/*
   megahal_learn_no_reply --

   Take string as input, update model but don't generate reply.

  */

void megahal_learn_no_reply(char *input, int log)
{
    if (log != 0)
    write_input(input);  /* log input if so desired */

    upper(input);

    make_words(input, words);

    learn(model, words);
}

/*
   megahal_initial_greeting --

   This function returns an initial greeting.  It can be used to start
   Megahal conversations, but it isn't necessary.

  */

char *megahal_initial_greeting(void)
{
    char *output;

    make_greeting(greets);
    output = generate_reply(model, greets);
    return output;
}

/*
   megahal_output --

   This function pretty prints output.

   Wrapper function to have things in the right namespace.

*/

void megahal_output(char *output)
{
    if(!quiet)
    write_output(output);
}

/*
   megahal_input --

   Get a string from stdin, using a prompt.

  */

char *megahal_input(char *prompt)
{
    if (noprompt)
    return read_input("");
    else
    return read_input(prompt);
}

/*
   megahal_command --

   Check to see if input is a megahal command, and if so, act upon it.

   Returns 1 if it is a command, 0 if it is not.

  */

int megahal_command(char *input)
{
    int position = 0;
    char *output;

    make_words(input,words);
    switch(execute_command(words, &position)) {
    case EXIT:
    exithal();
    break;
    case QUIT:
    save_model("megahal.brn", model);
    exithal();
    break;
    case SAVE:
    save_model("megahal.brn", model);
    break;
    case DELAY:
    typing_delay=!typing_delay;
    printf("MegaHAL typing is now %s.\n", typing_delay?"on":"off");
    return 1;
    case SPEECH:
    speech=!speech;
    printf("MegaHAL speech is now %s.\n", speech?"on":"off");
    return 1;
    case HELP:
    help();
    return 1;
    case VOICELIST:
    listvoices();
    return 1;
    case VOICE:
    changevoice(words, position);
    return 1;
    case BRAIN:
    change_personality(words, position, &model);
    make_greeting(greets);
    output=generate_reply(model, greets);
    write_output(output);
    return 1;
    case QUIET:
    quiet=!quiet;
    return 1;
    default:
    return 0;
    }
    return 0;
}

/*
   megahal_cleanup --

   Clean up everything. Prepare for exit.

  */

void megahal_cleanup(void)
{
    save_model("megahal.brn", model);

#ifdef AMIGA
    CloseLocale(_AmigaLocale);
#endif
}



/*---------------------------------------------------------------------------*/

/*
 *      Function:   Execute_Command
 *
 *      Purpose:        Detect whether the user has typed a command, and
 *                      execute the corresponding function.
 */
COMMAND_WORDS execute_command(DICTIONARY *words, int *position)
{
    register unsigned int i;
    register unsigned int j;

    /*
     *      If there is only one word, then it can't be a command.
     */
    *position=words->size+1;
    if(words->size<=1) return(UNKNOWN);

    /*
     *      Search through the word array.  If a command prefix is found,
     *      then try to match the following word with a command word.  If
     *      a match is found, then return a command identifier.  If the
     *      Following word is a number, then change the judge.  Otherwise,
     *      continue the search.
     */
    for(i=0; i<words->size-1; ++i)
    /*
     *      The command prefix was found.
     */
    if(words->entry[i].word[words->entry[i].length - 1] == '#') {
        /*
         *      Look for a command word.
         */
        for(j = 0; j < COMMAND_SIZE; ++j)
        if(wordcmp(command[j].word, words->entry[i + 1]) == 0) {
            *position = i + 1;
            return(command[j].command);
        }
    }

    return(UNKNOWN);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   ExitHAL
 *
 *      Purpose:        Terminate the program.
 */
void exithal(void)
{
#ifdef __mac_os
    /*
     *      Must be called because it does use some system memory
     */
    if (gSpeechChannel) {
    StopSpeech(gSpeechChannel);
    DisposeSpeechChannel(gSpeechChannel);
    gSpeechChannel = nil;
    }
#endif

    exit(0);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Read_Input
 *
 *      Purpose:        Read an input string from the user.
 */
char *read_input(char *prompt)
{
    static char *input=NULL;
    bool finish;
    int length;
    int c;

    /*
     *      Perform some initializations.  The finish boolean variable is used
     *      to detect a double line-feed, while length contains the number of
     *      characters in the input string.
     */
    finish=FALSE;
    length=0;
    if(input==NULL) {
    input=(char *)malloc(sizeof(char));
    if(input==NULL) {
        error("read_input", "Unable to allocate the input string");
        return(input);
    }
    }

    /*
     *      Display the prompt to the user.
     */
    fprintf(stdout, prompt);
    fflush(stdout);

    /*
     *      Loop forever, reading characters and putting them into the input
     *      string.
     */
    while(TRUE) {

    /*
     *      Read a single character from stdin.
     */
    c=getc(stdin);

    /*
     *      If the character is a line-feed, then set the finish variable
     *      to TRUE.  If it already is TRUE, then this is a double line-feed,
     *      in which case we should exit.  After a line-feed, display the
     *      prompt again, and set the character to the space character, as
     *      we don't permit linefeeds to appear in the input.
     */
    if((char)(c)=='\n') {
        if(finish==TRUE) break;
        fprintf(stdout, prompt);
        fflush(stdout);
        finish=TRUE;
        c=32;
    } else {
        finish=FALSE;
    }

    /*
     *      Re-allocate the input string so that it can hold one more
     *      character.
     */
    ++length;
    input=(char *)realloc((char *)input,sizeof(char)*(length+1));
    if(input==NULL) {
        error("read_input", "Unable to re-allocate the input string");
        return(NULL);
    }

    /*
     *      Add the character just read to the input string.
     */
    input[length-1]=(char)c;
    input[length]='\0';
    }

    while(isspace(input[length-1])) --length;
    input[length]='\0';

    /*
     *      We have finished, so return the input string.
     */
    return(input);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Initialize_Error
 *
 *      Purpose:        Close the current error file pointer, and open a new one.
 */
bool initialize_error(char *filename)
{
    if(errorfp!=stderr) fclose(errorfp);

    if(filename==NULL) return(TRUE);

    errorfp = fopen(filename, "a");
    if(errorfp==NULL) {
    errorfp=stderr;
    return(FALSE);
    }
    return(print_header(errorfp));
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Error
 *
 *      Purpose:        Print the specified message to the error file.
 */
void error(char *title, char *fmt, ...)
{
    va_list argp;

    fprintf(errorfp, "%s: ", title);
    va_start(argp, fmt);
    vfprintf(errorfp, fmt, argp);
    va_end(argp);
    fprintf(errorfp, ".\n");
    fflush(errorfp);

    fprintf(stderr, "MegaHAL died for some reason; check the error log.\n");

    exit(1);
}

/*---------------------------------------------------------------------------*/

bool warn(char *title, char *fmt, ...)
{
    va_list argp;

    fprintf(errorfp, "%s: ", title);
    va_start(argp, fmt);
    vfprintf(errorfp, fmt, argp);
    va_end(argp);
    fprintf(errorfp, ".\n");
    fflush(errorfp);

    fprintf(stderr, "MegaHAL emitted a warning; check the error log.\n");

    return(TRUE);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Initialize_Status
 *
 *      Purpose:        Close the current status file pointer, and open a new one.
 */
bool initialize_status(char *filename)
{
    if(statusfp!=stdout) fclose(statusfp);
    if(filename==NULL) return(FALSE);
    statusfp=fopen(filename, "a");
    if(statusfp==NULL) {
    statusfp=stdout;
    return(FALSE);
    }
    return(print_header(statusfp));
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Status
 *
 *      Purpose:        Print the specified message to the status file.
 */
bool status(char *fmt, ...)
{
    va_list argp;

    va_start(argp, fmt);
    vfprintf(statusfp, fmt, argp);
    va_end(argp);
    fflush(statusfp);

    return(TRUE);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Print_Header
 *
 *      Purpose:        Display a copyright message and timestamp.
 */
bool print_header(FILE *file)
{
    time_t clock;
    char timestamp[1024];
    struct tm *local;

    clock=time(NULL);
    local=localtime(&clock);
    strftime(timestamp, 1024, "Start at: [%Y/%m/%d %H:%M:%S]\n", local);

    fprintf(file, "MegaHALv8\n");
    fprintf(file, "Copyright (C) 1998 Jason Hutchens\n");
    fprintf(file, timestamp);
    fflush(file);

    return(TRUE);
}

/*---------------------------------------------------------------------------*/

/*
 *    Function:   Write_Output
 *
 *    Purpose:    Display the output string.
 */
void write_output(char *output)
{
    char *formatted;
    char *bit;

    capitalize(output);
    speak(output);

    width=75;
    formatted=format_output(output);
    delay(formatted);
    width=64;
    formatted=format_output(output);

    bit=strtok(formatted, "\n");
    if(bit==NULL) (void)status("MegaHAL: %s\n", formatted);
    while(bit!=NULL) {
    (void)status("MegaHAL: %s\n", bit);
    bit=strtok(NULL, "\n");
    }
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Capitalize
 *
 *      Purpose:        Convert a string to look nice.
 */
void capitalize(char *string)
{
    register unsigned int i;
    bool start=TRUE;

    for(i=0; i<strlen(string); ++i) {
    if(isalpha(string[i])) {
        if(start==TRUE) string[i]=(char)toupper((int)string[i]);
        else string[i]=(char)tolower((int)string[i]);
        start=FALSE;
    }
    if((i>2)&&(strchr("!.?", string[i-1])!=NULL)&&(isspace(string[i])))
        start=TRUE;
    }
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Upper
 *
 *      Purpose:        Convert a string to its uppercase representation.
 */
void upper(char *string)
{
    register unsigned int i;

    for(i=0; i<strlen(string); ++i) string[i]=(char)toupper((int)string[i]);
}

/*---------------------------------------------------------------------------*/

/*
 *    Function:   Write_Input
 *
 *    Purpose:    Log the user's input
 */
void write_input(char *input)
{
    char *formatted;
    char *bit;

    width=64;
    formatted=format_output(input);

    bit=strtok(formatted, "\n");
    if(bit==NULL) (void)status("User:    %s\n", formatted);
    while(bit!=NULL) {
    (void)status("User:    %s\n", bit);
    bit=strtok(NULL, "\n");
    }
}

/*---------------------------------------------------------------------------*/

/*
 *    Function:   Format_Output
 *
 *    Purpose:    Format a string to display nicely on a terminal of a given
 *                width.
 */
static char *format_output(char *output)
{
    static char *formatted=NULL;
    register unsigned int i,j,c;
    int l;
    if(formatted==NULL) {
    formatted=(char *)malloc(sizeof(char));
    if(formatted==NULL) {
        error("format_output", "Unable to allocate formatted");
        return("ERROR");
    }
    }

    formatted=(char *)realloc((char *)formatted, sizeof(char)*(strlen(output)+2));
    if(formatted==NULL) {
    error("format_output", "Unable to re-allocate formatted");
    return("ERROR");
    }

    l=0;
    j=0;
    for(i=0; i<strlen(output); ++i) {
    if((l==0)&&(isspace(output[i]))) continue;
    formatted[j]=output[i];
    ++j;
    ++l;
    if(!nowrap)
        if(l>=width)
        for(c=j-1; c>0; --c)
            if(formatted[c]==' ') {
            formatted[c]='\n';
            l=j-c-1;
            break;
            }
    }
    if((j>0)&&(formatted[j-1]!='\n')) {
    formatted[j]='\n';
    ++j;
    }
    formatted[j]='\0';

    return(formatted);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Add_Word
 *
 *      Purpose:        Add a word to a dictionary, and return the identifier
 *                      assigned to the word.  If the word already exists in
 *                      the dictionary, then return its current identifier
 *                      without adding it again.
 */
BYTE2 add_word(DICTIONARY *dictionary, STRING word)
{
    register int i;
    int position;
    bool found;

    /*
     *      If the word's already in the dictionary, there is no need to add it
     */
    position=search_dictionary(dictionary, word, &found);
    if(found==TRUE) goto succeed;

    /*
     *      Increase the number of words in the dictionary
     */
    dictionary->size+=1;

    /*
     *      Allocate one more entry for the word index
     */
    if(dictionary->index==NULL) {
    dictionary->index=(BYTE2 *)malloc(sizeof(BYTE2)*
                      (dictionary->size));
    } else {
    dictionary->index=(BYTE2 *)realloc((BYTE2 *)
                       (dictionary->index),sizeof(BYTE2)*(dictionary->size));
    }
    if(dictionary->index==NULL) {
    error("add_word", "Unable to reallocate the index.");
    goto fail;
    }

    /*
     *      Allocate one more entry for the word array
     */
    if(dictionary->entry==NULL) {
    dictionary->entry=(STRING *)malloc(sizeof(STRING)*(dictionary->size));
    } else {
    dictionary->entry=(STRING *)realloc((STRING *)(dictionary->entry),
                        sizeof(STRING)*(dictionary->size));
    }
    if(dictionary->entry==NULL) {
    error("add_word", "Unable to reallocate the dictionary to %d elements.", dictionary->size);
    goto fail;
    }

    /*
     *      Copy the new word into the word array
     */
    dictionary->entry[dictionary->size-1].length=word.length;
    dictionary->entry[dictionary->size-1].word=(char *)malloc(sizeof(char)*
                                  (word.length));
    if(dictionary->entry[dictionary->size-1].word==NULL) {
    error("add_word", "Unable to allocate the word.");
    goto fail;
    }
    for(i=0; i<word.length; ++i)
    dictionary->entry[dictionary->size-1].word[i]=word.word[i];

    /*
     *      Shuffle the word index to keep it sorted alphabetically
     */
    for(i=(dictionary->size-1); i>position; --i)
    dictionary->index[i]=dictionary->index[i-1];

    /*
     *      Copy the new symbol identifier into the word index
     */
    dictionary->index[position]=dictionary->size-1;

succeed:
    return(dictionary->index[position]);

fail:
    return(0);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Search_Dictionary
 *
 *      Purpose:        Search the dictionary for the specified word, returning its
 *                      position in the index if found, or the position where it
 *                      should be inserted otherwise.
 */
int search_dictionary(DICTIONARY *dictionary, STRING word, bool *find)
{
    int position;
    int min;
    int max;
    int middle;
    int compar;

    /*
     *      If the dictionary is empty, then obviously the word won't be found
     */
    if(dictionary->size==0) {
    position=0;
    goto notfound;
    }

    /*
     *      Initialize the lower and upper bounds of the search
     */
    min=0;
    max=dictionary->size-1;
    /*
     *      Search repeatedly, halving the search space each time, until either
     *      the entry is found, or the search space becomes empty
     */
    while(TRUE) {
    /*
     *      See whether the middle element of the search space is greater
     *      than, equal to, or less than the element being searched for.
     */
    middle=(min+max)/2;
    compar=wordcmp(word, dictionary->entry[dictionary->index[middle]]);
    /*
     *      If it is equal then we have found the element.  Otherwise we
     *      can halve the search space accordingly.
     */
    if(compar==0) {
        position=middle;
        goto found;
    } else if(compar>0) {
        if(max==middle) {
        position=middle+1;
        goto notfound;
        }
        min=middle+1;
    } else {
        if(min==middle) {
        position=middle;
        goto notfound;
        }
        max=middle-1;
    }
    }

found:
    *find=TRUE;
    return(position);

notfound:
    *find=FALSE;
    return(position);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Find_Word
 *
 *      Purpose:        Return the symbol corresponding to the word specified.
 *                      We assume that the word with index zero is equal to a
 *                      NULL word, indicating an error condition.
 */
BYTE2 find_word(DICTIONARY *dictionary, STRING word)
{
    int position;
    bool found;

    position=search_dictionary(dictionary, word, &found);

    if(found==TRUE) return(dictionary->index[position]);
    else return(0);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Wordcmp
 *
 *      Purpose:        Compare two words, and return an integer indicating whether
 *                      the first word is less than, equal to or greater than the
 *                      second word.
 */
int wordcmp(STRING word1, STRING word2)
{
    register int i;
    int bound;

    bound=MIN(word1.length,word2.length);

    for(i=0; i<bound; ++i)
    if(toupper(word1.word[i])!=toupper(word2.word[i]))
        return((int)(toupper(word1.word[i])-toupper(word2.word[i])));

    if(word1.length<word2.length) return(-1);
    if(word1.length>word2.length) return(1);

    return(0);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Free_Dictionary
 *
 *      Purpose:        Release the memory consumed by the dictionary.
 */
void free_dictionary(DICTIONARY *dictionary)
{
    if(dictionary==NULL) return;
    if(dictionary->entry!=NULL) {
    free(dictionary->entry);
    dictionary->entry=NULL;
    }
    if(dictionary->index!=NULL) {
    free(dictionary->index);
    dictionary->index=NULL;
    }
    dictionary->size=0;
}

/*---------------------------------------------------------------------------*/

void free_model(MODEL *model)
{
    if(model==NULL) return;
    if(model->forward!=NULL) {
    free_tree(model->forward);
    }
    if(model->backward!=NULL) {
    free_tree(model->backward);
    }
    if(model->context!=NULL) {
    free(model->context);
    }
    if(model->dictionary!=NULL) {
    free_dictionary(model->dictionary);
    free(model->dictionary);
    }
    free(model);
}

/*---------------------------------------------------------------------------*/

void free_tree(TREE *tree)
{
    static int level=0;
    register unsigned int i;

    if(tree==NULL) return;

    if(tree->tree!=NULL) {
    if(level==0) progress("Freeing tree", 0, 1);
    for(i=0; i<tree->branch; ++i) {
        ++level;
        free_tree(tree->tree[i]);
        --level;
        if(level==0) progress(NULL, i, tree->branch);
    }
    if(level==0) progress(NULL, 1, 1);
    free(tree->tree);
    }
    free(tree);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Initialize_Dictionary
 *
 *      Purpose:        Add dummy words to the dictionary.
 */
void initialize_dictionary(DICTIONARY *dictionary)
{
    STRING word={ 7, "<ERROR>" };
    STRING end={ 5, "<FIN>" };

    (void)add_word(dictionary, word);
    (void)add_word(dictionary, end);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   New_Dictionary
 *
 *      Purpose:        Allocate room for a new dictionary.
 */
DICTIONARY *new_dictionary(void)
{
    DICTIONARY *dictionary=NULL;

    dictionary=(DICTIONARY *)malloc(sizeof(DICTIONARY));
    if(dictionary==NULL) {
    error("new_dictionary", "Unable to allocate dictionary.");
    return(NULL);
    }

    dictionary->size=0;
    dictionary->index=NULL;
    dictionary->entry=NULL;

    return(dictionary);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Save_Dictionary
 *
 *      Purpose:        Save a dictionary to the specified file.
 */
void save_dictionary(FILE *file, DICTIONARY *dictionary)
{
    register unsigned int i;

    fwrite(&(dictionary->size), sizeof(BYTE4), 1, file);
    progress("Saving dictionary", 0, 1);
    for(i=0; i<dictionary->size; ++i) {
    save_word(file, dictionary->entry[i]);
    progress(NULL, i, dictionary->size);
    }
    progress(NULL, 1, 1);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Load_Dictionary
 *
 *      Purpose:        Load a dictionary from the specified file.
 */
void load_dictionary(FILE *file, DICTIONARY *dictionary)
{
    register int i;
    int size;

    fread(&size, sizeof(BYTE4), 1, file);
    progress("Loading dictionary", 0, 1);
    for(i=0; i<size; ++i) {
    load_word(file, dictionary);
    progress(NULL, i, size);
    }
    progress(NULL, 1, 1);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Save_Word
 *
 *      Purpose:        Save a dictionary word to a file.
 */
void save_word(FILE *file, STRING word)
{
    register unsigned int i;

    fwrite(&(word.length), sizeof(BYTE1), 1, file);
    for(i=0; i<word.length; ++i)
    fwrite(&(word.word[i]), sizeof(char), 1, file);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Load_Word
 *
 *      Purpose:        Load a dictionary word from a file.
 */
void load_word(FILE *file, DICTIONARY *dictionary)
{
    register unsigned int i;
    STRING word;

    fread(&(word.length), sizeof(BYTE1), 1, file);
    word.word=(char *)malloc(sizeof(char)*word.length);
    if(word.word==NULL) {
    error("load_word", "Unable to allocate word");
    return;
    }
    for(i=0; i<word.length; ++i)
    fread(&(word.word[i]), sizeof(char), 1, file);
    add_word(dictionary, word);
    free(word.word);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   New_Node
 *
 *      Purpose:        Allocate a new node for the n-gram tree, and initialise
 *                      its contents to sensible values.
 */
TREE *new_node(void)
{
    TREE *node=NULL;

    /*
     *      Allocate memory for the new node
     */
    node=(TREE *)malloc(sizeof(TREE));
    if(node==NULL) {
    error("new_node", "Unable to allocate the node.");
    goto fail;
    }

    /*
     *      Initialise the contents of the node
     */
    node->symbol=0;
    node->usage=0;
    node->count=0;
    node->branch=0;
    node->tree=NULL;

    return(node);

fail:
    if(node!=NULL) free(node);
    return(NULL);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   New_Model
 *
 *      Purpose:        Create and initialise a new ngram model.
 */
MODEL *new_model(int order)
{
    MODEL *model=NULL;

    model=(MODEL *)malloc(sizeof(MODEL));
    if(model==NULL) {
    error("new_model", "Unable to allocate model.");
    goto fail;
    }

    model->order=order;
    model->forward=new_node();
    model->backward=new_node();
    model->context=(TREE **)malloc(sizeof(TREE *)*(order+2));
    if(model->context==NULL) {
    error("new_model", "Unable to allocate context array.");
    goto fail;
    }
    initialize_context(model);
    model->dictionary=new_dictionary();
    initialize_dictionary(model->dictionary);

    return(model);

fail:
    return(NULL);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Update_Model
 *
 *      Purpose:        Update the model with the specified symbol.
 */
void update_model(MODEL *model, int symbol)
{
    register unsigned int i;

    /*
     *      Update all of the models in the current context with the specified
     *      symbol.
     */
    for(i=(model->order+1); i>0; --i)
    if(model->context[i-1]!=NULL)
        model->context[i]=add_symbol(model->context[i-1], (BYTE2)symbol);

    return;
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Update_Context
 *
 *      Purpose:        Update the context of the model without adding the symbol.
 */
void update_context(MODEL *model, int symbol)
{
    register unsigned int i;

    for(i=(model->order+1); i>0; --i)
    if(model->context[i-1]!=NULL)
        model->context[i]=find_symbol(model->context[i-1], symbol);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Add_Symbol
 *
 *      Purpose:        Update the statistics of the specified tree with the
 *                      specified symbol, which may mean growing the tree if the
 *                      symbol hasn't been seen in this context before.
 */
TREE *add_symbol(TREE *tree, BYTE2 symbol)
{
    TREE *node=NULL;

    /*
     *      Search for the symbol in the subtree of the tree node.
     */
    node=find_symbol_add(tree, symbol);

    /*
     *      Increment the symbol counts
     */
    if((node->count<65535)) {
    node->count+=1;
    tree->usage+=1;
    }

    return(node);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Find_Symbol
 *
 *      Purpose:        Return a pointer to the child node, if one exists, which
 *                      contains the specified symbol.
 */
TREE *find_symbol(TREE *node, int symbol)
{
    register unsigned int i;
    TREE *found=NULL;
    bool found_symbol=FALSE;

    /*
     *      Perform a binary search for the symbol.
     */
    i=search_node(node, symbol, &found_symbol);
    if(found_symbol==TRUE) found=node->tree[i];

    return(found);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Find_Symbol_Add
 *
 *      Purpose:        This function is conceptually similar to find_symbol,
 *                      apart from the fact that if the symbol is not found,
 *                      a new node is automatically allocated and added to the
 *                      tree.
 */
TREE *find_symbol_add(TREE *node, int symbol)
{
    register unsigned int i;
    TREE *found=NULL;
    bool found_symbol=FALSE;

    /*
     *      Perform a binary search for the symbol.  If the symbol isn't found,
     *      attach a new sub-node to the tree node so that it remains sorted.
     */
    i=search_node(node, symbol, &found_symbol);
    if(found_symbol==TRUE) {
    found=node->tree[i];
    } else {
    found=new_node();
    found->symbol=symbol;
    add_node(node, found, i);
    }

    return(found);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Add_Node
 *
 *      Purpose:        Attach a new child node to the sub-tree of the tree
 *                      specified.
 */
void add_node(TREE *tree, TREE *node, int position)
{
    register int i;

    /*
     *      Allocate room for one more child node, which may mean allocating
     *      the sub-tree from scratch.
     */
    if(tree->tree==NULL) {
    tree->tree=(TREE **)malloc(sizeof(TREE *)*(tree->branch+1));
    } else {
    tree->tree=(TREE **)realloc((TREE **)(tree->tree),sizeof(TREE *)*
                    (tree->branch+1));
    }
    if(tree->tree==NULL) {
    error("add_node", "Unable to reallocate subtree.");
    return;
    }

    /*
     *      Shuffle the nodes down so that we can insert the new node at the
     *      subtree index given by position.
     */
    for(i=tree->branch; i>position; --i)
    tree->tree[i]=tree->tree[i-1];

    /*
     *      Add the new node to the sub-tree.
     */
    tree->tree[position]=node;
    tree->branch+=1;
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Search_Node
 *
 *      Purpose:        Perform a binary search for the specified symbol on the
 *                      subtree of the given node.  Return the position of the
 *                      child node in the subtree if the symbol was found, or the
 *                      position where it should be inserted to keep the subtree
 *                      sorted if it wasn't.
 */
int search_node(TREE *node, int symbol, bool *found_symbol)
{
    register unsigned int position;
    int min;
    int max;
    int middle;
    int compar;

    /*
     *      Handle the special case where the subtree is empty.
     */
    if(node->branch==0) {
    position=0;
    goto notfound;
    }

    /*
     *      Perform a binary search on the subtree.
     */
    min=0;
    max=node->branch-1;
    while(TRUE) {
    middle=(min+max)/2;
    compar=symbol-node->tree[middle]->symbol;
    if(compar==0) {
        position=middle;
        goto found;
    } else if(compar>0) {
        if(max==middle) {
        position=middle+1;
        goto notfound;
        }
        min=middle+1;
    } else {
        if(min==middle) {
        position=middle;
        goto notfound;
        }
        max=middle-1;
    }
    }

found:
    *found_symbol=TRUE;
    return(position);

notfound:
    *found_symbol=FALSE;
    return(position);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Initialize_Context
 *
 *      Purpose:        Set the context of the model to a default value.
 */
void initialize_context(MODEL *model)
{
    register unsigned int i;

    for(i=0; i<=model->order; ++i) model->context[i]=NULL;
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Learn
 *
 *      Purpose:        Learn from the user's input.
 */
void learn(MODEL *model, DICTIONARY *words)
{
    register unsigned int i;
    register int j;
    BYTE2 symbol;

    /*
     *      We only learn from inputs which are long enough
     */
    if(words->size<=(model->order)) return;

    /*
     *      Train the model in the forwards direction.  Start by initializing
     *      the context of the model.
     */
    initialize_context(model);
    model->context[0]=model->forward;
    for(i=0; i<words->size; ++i) {
    /*
     *      Add the symbol to the model's dictionary if necessary, and then
     *      update the forward model accordingly.
     */
    symbol=add_word(model->dictionary, words->entry[i]);
    update_model(model, symbol);
    }
    /*
     *      Add the sentence-terminating symbol.
     */
    update_model(model, 1);

    /*
     *      Train the model in the backwards direction.  Start by initializing
     *      the context of the model.
     */
    initialize_context(model);
    model->context[0]=model->backward;
    for(j=words->size-1; j>=0; --j) {
    /*
     *      Find the symbol in the model's dictionary, and then update
     *      the backward model accordingly.
     */
    symbol=find_word(model->dictionary, words->entry[j]);
    update_model(model, symbol);
    }
    /*
     *      Add the sentence-terminating symbol.
     */
    update_model(model, 1);

    return;
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Train
 *
 *      Purpose:        Infer a MegaHAL brain from the contents of a text file.
 */
void train(MODEL *model, char *filename)
{
    FILE *file;
    char buffer[1024];
    DICTIONARY *words=NULL;
    int length;

    if(filename==NULL) return;

    file=fopen(filename, "r");
    if(file==NULL) {
    printf("Unable to find the personality %s\n", filename);
    return;
    }

    fseek(file, 0, 2);
    length=ftell(file);
    rewind(file);

    words=new_dictionary();

    progress("Training from file", 0, 1);
    while(!feof(file)) {

    if(fgets(buffer, 1024, file)==NULL) break;
    if(buffer[0]=='#') continue;

    buffer[strlen(buffer)-1]='\0';

    upper(buffer);
    make_words(buffer, words);
    learn(model, words);

    progress(NULL, ftell(file), length);

    }
    progress(NULL, 1, 1);

    free_dictionary(words);
    fclose(file);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Show_Dictionary
 *
 *      Purpose:        Display the dictionary for training purposes.
 */
void show_dictionary(DICTIONARY *dictionary)
{
    register unsigned int i;
    register unsigned int j;
    FILE *file;

    file=fopen("megahal.dic", "w");
    if(file==NULL) {
    warn("show_dictionary", "Unable to open file");
    return;
    }

    for(i=0; i<dictionary->size; ++i) {
    for(j=0; j<dictionary->entry[i].length; ++j)
        fprintf(file, "%c", dictionary->entry[i].word[j]);
    fprintf(file, "\n");
    }

    fclose(file);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Save_Model
 *
 *      Purpose:        Save the current state to a MegaHAL brain file.
 */
void save_model(char *modelname, MODEL *model)
{
    FILE *file;
    static char *filename=NULL;

    if(filename==NULL) filename=(char *)malloc(sizeof(char)*1);

    /*
     *    Allocate memory for the filename
     */
    filename=(char *)realloc(filename,
                 sizeof(char)*(strlen(directory)+strlen(SEP)+12));
    if(filename==NULL) error("save_model","Unable to allocate filename");

    show_dictionary(model->dictionary);
    if(filename==NULL) return;

    sprintf(filename, "%s%smegahal.brn", directory, SEP);
    file=fopen(filename, "wb");
    if(file==NULL) {
    warn("save_model", "Unable to open file `%s'", filename);
    return;
    }

    fwrite(COOKIE, sizeof(char), strlen(COOKIE), file);
    fwrite(&(model->order), sizeof(BYTE1), 1, file);
    save_tree(file, model->forward);
    save_tree(file, model->backward);
    save_dictionary(file, model->dictionary);

    fclose(file);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Save_Tree
 *
 *      Purpose:        Save a tree structure to the specified file.
 */
void save_tree(FILE *file, TREE *node)
{
    static int level=0;
    register unsigned int i;

    fwrite(&(node->symbol), sizeof(BYTE2), 1, file);
    fwrite(&(node->usage), sizeof(BYTE4), 1, file);
    fwrite(&(node->count), sizeof(BYTE2), 1, file);
    fwrite(&(node->branch), sizeof(BYTE2), 1, file);

    if(level==0) progress("Saving tree", 0, 1);
    for(i=0; i<node->branch; ++i) {
    ++level;
    save_tree(file, node->tree[i]);
    --level;
    if(level==0) progress(NULL, i, node->branch);
    }
    if(level==0) progress(NULL, 1, 1);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Load_Tree
 *
 *      Purpose:        Load a tree structure from the specified file.
 */
void load_tree(FILE *file, TREE *node)
{
    static int level=0;
    register unsigned int i;

    fread(&(node->symbol), sizeof(BYTE2), 1, file);
    fread(&(node->usage), sizeof(BYTE4), 1, file);
    fread(&(node->count), sizeof(BYTE2), 1, file);
    fread(&(node->branch), sizeof(BYTE2), 1, file);

    if(node->branch==0) return;

    node->tree=(TREE **)malloc(sizeof(TREE *)*(node->branch));
    if(node->tree==NULL) {
    error("load_tree", "Unable to allocate subtree");
    return;
    }

    if(level==0) progress("Loading tree", 0, 1);
    for(i=0; i<node->branch; ++i) {
    node->tree[i]=new_node();
    ++level;
    load_tree(file, node->tree[i]);
    --level;
    if(level==0) progress(NULL, i, node->branch);
    }
    if(level==0) progress(NULL, 1, 1);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Load_Model
 *
 *      Purpose:        Load a model into memory.
 */
bool load_model(char *filename, MODEL *model)
{
    FILE *file;
    char cookie[16];


    if(filename==NULL) return(FALSE);

    file=fopen(filename, "rb");

    if(file==NULL) {
    warn("load_model", "Unable to open file `%s'", filename);
    return(FALSE);
    }


    fread(cookie, sizeof(char), strlen(COOKIE), file);
    if(strncmp(cookie, COOKIE, strlen(COOKIE))!=0) {
    warn("load_model", "File `%s' is not a MegaHAL brain", filename);
    goto fail;
    }

    fread(&(model->order), sizeof(BYTE1), 1, file);
    load_tree(file, model->forward);
    load_tree(file, model->backward);
    load_dictionary(file, model->dictionary);

    return(TRUE);
fail:
    fclose(file);

    return(FALSE);
}

/*---------------------------------------------------------------------------*/

/*
 *    Function:   Make_Words
 *
 *    Purpose:    Break a string into an array of words.
 */
void make_words(char *input, DICTIONARY *words)
{
    int offset=0;

    /*
     *      Clear the entries in the dictionary
     */
    free_dictionary(words);

    /*
     *      If the string is empty then do nothing, for it contains no words.
     */
    if(strlen(input)==0) return;

    /*
     *      Loop forever.
     */
    while(1) {

    /*
     *      If the current character is of the same type as the previous
     *      character, then include it in the word.  Otherwise, terminate
     *      the current word.
     */
    if(boundary(input, offset)) {
        /*
         *      Add the word to the dictionary
         */
        if(words->entry==NULL)
        words->entry=(STRING *)malloc((words->size+1)*sizeof(STRING));
        else
        words->entry=(STRING *)realloc(words->entry, (words->size+1)*sizeof(STRING));

        if(words->entry==NULL) {
        error("make_words", "Unable to reallocate dictionary");
        return;
        }

        words->entry[words->size].length=offset;
        words->entry[words->size].word=input;
        words->size+=1;

        if(offset==(int)strlen(input)) break;
        input+=offset;
        offset=0;
    } else {
        ++offset;
    }
    }

    /*
     *      If the last word isn't punctuation, then replace it with a
     *      full-stop character.
     */
    if(isalnum(words->entry[words->size-1].word[0])) {
    if(words->entry==NULL)
        words->entry=(STRING *)malloc((words->size+1)*sizeof(STRING));
    else
        words->entry=(STRING *)realloc(words->entry, (words->size+1)*sizeof(STRING));
    if(words->entry==NULL) {
        error("make_words", "Unable to reallocate dictionary");
        return;
    }

    words->entry[words->size].length=1;
    words->entry[words->size].word=".";
    ++words->size;
    }
    else if(strchr("!.?", words->entry[words->size-1].word[words->entry[words->size-1].length-1])==NULL) {
    words->entry[words->size-1].length=1;
    words->entry[words->size-1].word=".";
    }

    return;
}

/*---------------------------------------------------------------------------*/
/*
 *      Function:   Boundary
 *
 *      Purpose:        Return whether or not a word boundary exists in a string
 *                      at the specified location.
 */
bool boundary(char *string, int position)
{
    if(position==0)
    return(FALSE);

    if(position==(int)strlen(string))
    return(TRUE);

    if(
    (string[position]=='\'')&&
    (isalpha(string[position-1])!=0)&&
    (isalpha(string[position+1])!=0)
    )
    return(FALSE);

    if(
    (position>1)&&
    (string[position-1]=='\'')&&
    (isalpha(string[position-2])!=0)&&
    (isalpha(string[position])!=0)
    )
    return(FALSE);

    if(
    (isalpha(string[position])!=0)&&
    (isalpha(string[position-1])==0)
    )
    return(TRUE);

    if(
    (isalpha(string[position])==0)&&
    (isalpha(string[position-1])!=0)
    )
    return(TRUE);

    if(isdigit(string[position])!=isdigit(string[position-1]))
    return(TRUE);

    return(FALSE);
}

/*---------------------------------------------------------------------------*/
/*
 *      Function:   Make_Greeting
 *
 *      Purpose:        Put some special words into the dictionary so that the
 *                      program will respond as if to a new judge.
 */
void make_greeting(DICTIONARY *words)
{
    register unsigned int i;

    for(i=0; i<words->size; ++i) free(words->entry[i].word);
    free_dictionary(words);
    if(grt->size>0) (void)add_word(words, grt->entry[rnd(grt->size)]);
}

/*---------------------------------------------------------------------------*/
/*
 *    Function:   Generate_Reply
 *
 *    Purpose:    Take a string of user input and return a string of output
 *                which may vaguely be construed as containing a reply to
 *                whatever is in the input string.
 */
char *generate_reply(MODEL *model, DICTIONARY *words)
{
    static DICTIONARY *dummy=NULL;
    DICTIONARY *replywords;
    DICTIONARY *keywords;
    float surprise;
    float max_surprise;
    char *output;
    static char *output_none=NULL;
    int count;
    int basetime;
    int timeout = TIMEOUT;

    /*
     *      Create an array of keywords from the words in the user's input
     */
    keywords=make_keywords(model, words);

    /*
     *      Make sure some sort of reply exists
     */
    if(output_none==NULL) {
    output_none=malloc(40);
    if(output_none!=NULL)
        strcpy(output_none, "I don't know enough to answer you yet!");
    }
    output=output_none;
    if(dummy == NULL) dummy = new_dictionary();
    replywords = reply(model, dummy);
    if(dissimilar(words, replywords) == TRUE) output = make_output(replywords);

    /*
     *      Loop for the specified waiting period, generating and evaluating
     *      replies
     */
    max_surprise=(float)-1.0;
    count=0;
    basetime=time(NULL);
/*     progress("Generating reply", 0, 1);  */
    do {
    replywords=reply(model, keywords);
    surprise=evaluate_reply(model, keywords, replywords);
    ++count;
    if((surprise>max_surprise)&&(dissimilar(words, replywords)==TRUE)) {
        max_surprise=surprise;
        output=make_output(replywords);
    }
/*      progress(NULL, (time(NULL)-basetime),timeout); */
    } while((time(NULL)-basetime)<timeout);
    progress(NULL, 1, 1);

    /*
     *      Return the best answer we generated
     */
    return(output);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Dissimilar
 *
 *      Purpose:        Return TRUE or FALSE depending on whether the dictionaries
 *                      are the same or not.
 */
bool dissimilar(DICTIONARY *words1, DICTIONARY *words2)
{
    register unsigned int i;

    if(words1->size!=words2->size) return(TRUE);
    for(i=0; i<words1->size; ++i)
    if(wordcmp(words1->entry[i], words2->entry[i])!=0) return(TRUE);
    return(FALSE);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Make_Keywords
 *
 *      Purpose:        Put all the interesting words from the user's input into
 *                      a keywords dictionary, which will be used when generating
 *                      a reply.
 */
DICTIONARY *make_keywords(MODEL *model, DICTIONARY *words)
{
    static DICTIONARY *keys=NULL;
    register unsigned int i;
    register unsigned int j;
    int c;

    if(keys==NULL) keys=new_dictionary();
    for(i=0; i<keys->size; ++i) free(keys->entry[i].word);
    free_dictionary(keys);

    for(i=0; i<words->size; ++i) {
    /*
     *      Find the symbol ID of the word.  If it doesn't exist in
     *      the model, or if it begins with a non-alphanumeric
     *      character, or if it is in the exclusion array, then
     *      skip over it.
     */
    c=0;
    for(j=0; j<swp->size; ++j)
        if(wordcmp(swp->from[j], words->entry[i])==0) {
        add_key(model, keys, swp->to[j]);
        ++c;
        }
    if(c==0) add_key(model, keys, words->entry[i]);
    }

    if(keys->size>0) for(i=0; i<words->size; ++i) {

    c=0;
    for(j=0; j<swp->size; ++j)
        if(wordcmp(swp->from[j], words->entry[i])==0) {
        add_aux(model, keys, swp->to[j]);
        ++c;
        }
    if(c==0) add_aux(model, keys, words->entry[i]);
    }

    return(keys);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Add_Key
 *
 *      Purpose:        Add a word to the keyword dictionary.
 */
void add_key(MODEL *model, DICTIONARY *keys, STRING word)
{
    int symbol;

    symbol=find_word(model->dictionary, word);
    if(symbol==0) return;
    if(isalnum(word.word[0])==0) return;
    symbol=find_word(ban, word);
    if(symbol!=0) return;
    symbol=find_word(aux, word);
    if(symbol!=0) return;

    add_word(keys, word);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Add_Aux
 *
 *      Purpose:        Add an auxilliary keyword to the keyword dictionary.
 */
void add_aux(MODEL *model, DICTIONARY *keys, STRING word)
{
    int symbol;

    symbol=find_word(model->dictionary, word);
    if(symbol==0) return;
    if(isalnum(word.word[0])==0) return;
    symbol=find_word(aux, word);
    if(symbol==0) return;

    add_word(keys, word);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Reply
 *
 *      Purpose:        Generate a dictionary of reply words appropriate to the
 *                      given dictionary of keywords.
 */
DICTIONARY *reply(MODEL *model, DICTIONARY *keys)
{
    static DICTIONARY *replies=NULL;
    register int i;
    int symbol;
    bool start=TRUE;

    if(replies==NULL) replies=new_dictionary();
    free_dictionary(replies);

    /*
     *      Start off by making sure that the model's context is empty.
     */
    initialize_context(model);
    model->context[0]=model->forward;
    used_key=FALSE;

    /*
     *      Generate the reply in the forward direction.
     */
    while(TRUE) {
    /*
     *      Get a random symbol from the current context.
     */
    if(start==TRUE) symbol=seed(model, keys);
    else symbol=babble(model, keys, replies);
    if((symbol==0)||(symbol==1)) break;
    start=FALSE;

    /*
     *      Append the symbol to the reply dictionary.
     */
    if(replies->entry==NULL)
        replies->entry=(STRING *)malloc((replies->size+1)*sizeof(STRING));
    else
        replies->entry=(STRING *)realloc(replies->entry, (replies->size+1)*sizeof(STRING));
    if(replies->entry==NULL) {
        error("reply", "Unable to reallocate dictionary");
        return(NULL);
    }

    replies->entry[replies->size].length=
        model->dictionary->entry[symbol].length;
    replies->entry[replies->size].word=
        model->dictionary->entry[symbol].word;
    replies->size+=1;

    /*
     *      Extend the current context of the model with the current symbol.
     */
    update_context(model, symbol);
    }

    /*
     *      Start off by making sure that the model's context is empty.
     */
    initialize_context(model);
    model->context[0]=model->backward;

    /*
     *      Re-create the context of the model from the current reply
     *      dictionary so that we can generate backwards to reach the
     *      beginning of the string.
     */
    if(replies->size>0) for(i=MIN(replies->size-1, model->order); i>=0; --i) {
    symbol=find_word(model->dictionary, replies->entry[i]);
    update_context(model, symbol);
    }

    /*
     *      Generate the reply in the backward direction.
     */
    while(TRUE) {
    /*
     *      Get a random symbol from the current context.
     */
    symbol=babble(model, keys, replies);
    if((symbol==0)||(symbol==1)) break;

    /*
     *      Prepend the symbol to the reply dictionary.
     */
    if(replies->entry==NULL)
        replies->entry=(STRING *)malloc((replies->size+1)*sizeof(STRING));
    else
        replies->entry=(STRING *)realloc(replies->entry, (replies->size+1)*sizeof(STRING));
    if(replies->entry==NULL) {
        error("reply", "Unable to reallocate dictionary");
        return(NULL);
    }

    /*
     *      Shuffle everything up for the prepend.
     */
    for(i=replies->size; i>0; --i) {
        replies->entry[i].length=replies->entry[i-1].length;
        replies->entry[i].word=replies->entry[i-1].word;
    }

    replies->entry[0].length=model->dictionary->entry[symbol].length;
    replies->entry[0].word=model->dictionary->entry[symbol].word;
    replies->size+=1;

    /*
     *      Extend the current context of the model with the current symbol.
     */
    update_context(model, symbol);
    }

    return(replies);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Evaluate_Reply
 *
 *      Purpose:        Measure the average surprise of keywords relative to the
 *                      language model.
 */
float evaluate_reply(MODEL *model, DICTIONARY *keys, DICTIONARY *words)
{
    register unsigned int i;
    register int j;
    register int k;
    int symbol;
    float probability;
    int count;
    float entropy=(float)0.0;
    TREE *node;
    int num=0;

    if(words->size<=0) return((float)0.0);
    initialize_context(model);
    model->context[0]=model->forward;
    for(i=0; i<words->size; ++i) {
    symbol=find_word(model->dictionary, words->entry[i]);

    if(find_word(keys, words->entry[i])!=0) {
        probability=(float)0.0;
        count=0;
        ++num;
        for(j=0; j<model->order; ++j) if(model->context[j]!=NULL) {

        node=find_symbol(model->context[j], symbol);
        probability+=(float)(node->count)/
            (float)(model->context[j]->usage);
        ++count;

        }

        if(count>0.0) entropy-=(float)log(probability/(float)count);
    }

    update_context(model, symbol);
    }

    initialize_context(model);
    model->context[0]=model->backward;
    for(k=words->size-1; k>=0; --k) {
    symbol=find_word(model->dictionary, words->entry[k]);

    if(find_word(keys, words->entry[k])!=0) {
        probability=(float)0.0;
        count=0;
        ++num;
        for(j=0; j<model->order; ++j) if(model->context[j]!=NULL) {

        node=find_symbol(model->context[j], symbol);
        probability+=(float)(node->count)/
            (float)(model->context[j]->usage);
        ++count;

        }

        if(count>0.0) entropy-=(float)log(probability/(float)count);
    }

    update_context(model, symbol);
    }

    if(num>=8) entropy/=(float)sqrt(num-1);
    if(num>=16) entropy/=(float)num;

    return(entropy);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Make_Output
 *
 *      Purpose:        Generate a string from the dictionary of reply words.
 */
char *make_output(DICTIONARY *words)
{
    static char *output=NULL;
    register unsigned int i;
    register int j;
    int length;
    static char *output_none=NULL;

    if(output_none==NULL) output_none=malloc(40);

    if(output==NULL) {
    output=(char *)malloc(sizeof(char));
    if(output==NULL) {
        error("make_output", "Unable to allocate output");
        return(output_none);
    }
    }

    if(words->size==0) {
    if(output_none!=NULL)
        strcpy(output_none, "I am utterly speechless!");
    return(output_none);
    }

    length=1;
    for(i=0; i<words->size; ++i) length+=words->entry[i].length;

    output=(char *)realloc(output, sizeof(char)*length);
    if(output==NULL) {
    error("make_output", "Unable to reallocate output.");
    if(output_none!=NULL)
        strcpy(output_none, "I forgot what I was going to say!");
    return(output_none);
    }

    length=0;
    for(i=0; i<words->size; ++i)
    for(j=0; j<words->entry[i].length; ++j)
        output[length++]=words->entry[i].word[j];

    output[length]='\0';

    return(output);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Babble
 *
 *      Purpose:        Return a random symbol from the current context, or a
 *                      zero symbol identifier if we've reached either the
 *                      start or end of the sentence.  Select the symbol based
 *                      on probabilities, favouring keywords.  In all cases,
 *                      use the longest available context to choose the symbol.
 */
int babble(MODEL *model, DICTIONARY *keys, DICTIONARY *words)
{
    TREE *node;
    register int i;
    int count;
    int symbol = 0;

    node = NULL;

    /*
     *      Select the longest available context.
     */
    for(i=0; i<=model->order; ++i)
    if(model->context[i]!=NULL)
        node=model->context[i];

    if(node->branch==0) return(0);

    /*
     *      Choose a symbol at random from this context.
     */
    i=rnd(node->branch);
    count=rnd(node->usage);
    while(count>=0) {
    /*
     *      If the symbol occurs as a keyword, then use it.  Only use an
     *      auxilliary keyword if a normal keyword has already been used.
     */
    symbol=node->tree[i]->symbol;

    if(
        (find_word(keys, model->dictionary->entry[symbol])!=0)&&
        ((used_key==TRUE)||
         (find_word(aux, model->dictionary->entry[symbol])==0))&&
        (word_exists(words, model->dictionary->entry[symbol])==FALSE)
        ) {
        used_key=TRUE;
        break;
    }
    count-=node->tree[i]->count;
    i=(i>=(node->branch-1))?0:i+1;
    }

    return(symbol);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Word_Exists
 *
 *      Purpose:        A silly brute-force searcher for the reply string.
 */
bool word_exists(DICTIONARY *dictionary, STRING word)
{
    register unsigned int i;

    for(i=0; i<dictionary->size; ++i)
    if(wordcmp(dictionary->entry[i], word)==0)
        return(TRUE);
    return(FALSE);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Seed
 *
 *      Purpose:        Seed the reply by guaranteeing that it contains a
 *                      keyword, if one exists.
 */
int seed(MODEL *model, DICTIONARY *keys)
{
    register unsigned int i;
    int symbol;
    unsigned int stop;

    /*
     *      Fix, thanks to Mark Tarrabain
     */
    if(model->context[0]->branch==0) symbol=0;
    else symbol=model->context[0]->tree[rnd(model->context[0]->branch)]->symbol;

    if(keys->size>0) {
    i=rnd(keys->size);
    stop=i;
    while(TRUE) {
        if(
        (find_word(model->dictionary, keys->entry[i])!=0)&&
        (find_word(aux, keys->entry[i])==0)
        ) {
        symbol=find_word(model->dictionary, keys->entry[i]);
        return(symbol);
        }
        ++i;
        if(i==keys->size) i=0;
        if(i==stop) return(symbol);
    }
    }

    return(symbol);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   New_Swap
 *
 *      Purpose:        Allocate a new swap structure.
 */
SWAP *new_swap(void)
{
    SWAP *list;

    list=(SWAP *)malloc(sizeof(SWAP));
    if(list==NULL) {
    error("new_swap", "Unable to allocate swap");
    return(NULL);
    }
    list->size=0;
    list->from=NULL;
    list->to=NULL;

    return(list);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Add_Swap
 *
 *      Purpose:        Add a new entry to the swap structure.
 */
void add_swap(SWAP *list, char *s, char *d)
{
    list->size+=1;

    if(list->from==NULL) {
    list->from=(STRING *)malloc(sizeof(STRING));
    if(list->from==NULL) {
        error("add_swap", "Unable to allocate list->from");
        return;
    }
    }

    if(list->to==NULL) {
    list->to=(STRING *)malloc(sizeof(STRING));
    if(list->to==NULL) {
        error("add_swap", "Unable to allocate list->to");
        return;
    }
    }

    list->from=(STRING *)realloc(list->from, sizeof(STRING)*(list->size));
    if(list->from==NULL) {
    error("add_swap", "Unable to reallocate from");
    return;
    }

    list->to=(STRING *)realloc(list->to, sizeof(STRING)*(list->size));
    if(list->to==NULL) {
    error("add_swap", "Unable to reallocate to");
    return;
    }

    list->from[list->size-1].length=strlen(s);
    list->from[list->size-1].word=strdup(s);
    list->to[list->size-1].length=strlen(d);
    list->to[list->size-1].word=strdup(d);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Initialize_Swap
 *
 *      Purpose:        Read a swap structure from a file.
 */
SWAP *initialize_swap(char *filename)
{
    SWAP *list;
    FILE *file=NULL;
    char buffer[1024];
    char *from;
    char *to;

    list=new_swap();

    if(filename==NULL) return(list);

    file=fopen(filename, "r");
    if(file==NULL) return(list);

    while(!feof(file)) {

    if(fgets(buffer, 1024, file)==NULL) break;
    if(buffer[0]=='#') continue;
    from=strtok(buffer, "\t ");
    to=strtok(NULL, "\t \n#");

    add_swap(list, from, to);
    }

    fclose(file);
    return(list);
}

/*---------------------------------------------------------------------------*/

void free_swap(SWAP *swap)
{
    register int i;

    if(swap==NULL) return;

    for(i=0; i<swap->size; ++i) {
    free_word(swap->from[i]);
    free_word(swap->to[i]);
    }
    free(swap->from);
    free(swap->to);
    free(swap);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Initialize_List
 *
 *      Purpose:        Read a dictionary from a file.
 */
DICTIONARY *initialize_list(char *filename)
{
    DICTIONARY *list;
    FILE *file=NULL;
    STRING word;
    char *string;
    char buffer[1024];

    list=new_dictionary();

    if(filename==NULL) return(list);

    file=fopen(filename, "r");
    if(file==NULL) return(list);

    while(!feof(file)) {

    if(fgets(buffer, 1024, file)==NULL) break;
    if(buffer[0]=='#') continue;
    string=strtok(buffer, "\t \n#");

    if((string!=NULL)&&(strlen(string)>0)) {
        word.length=strlen(string);
        word.word=strdup(buffer);
        add_word(list, word);
    }
    }

    fclose(file);
    return(list);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Delay
 *
 *      Purpose:        Display the string to stdout as if it was typed by a human.
 */
void delay(char *string)
{
    register int i;

    /*
     *      Don't simulate typing if the feature is turned off
     */
    if(typing_delay==FALSE) {
    fprintf(stdout, string);
    return;
    }

    /*
     *      Display the entire string, one character at a time
     */
    for(i=0; i<(int)strlen(string)-1; ++i) typein(string[i]);
    usleep((D_THINK+rnd(V_THINK)-rnd(V_THINK))/2);
    typein(string[i]);
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Typein
 *
 *      Purpose:        Display a character to stdout as if it was typed by a human.
 */
void typein(char c)
{
    /*
     *      Standard keyboard delay
     */
    usleep(D_KEY+rnd(V_KEY)-rnd(V_KEY));
    fprintf(stdout, "%c", c);
    fflush(stdout);

    /*
     *      A random thinking delay
     */
    if((!isalnum(c))&&((rnd(100))<P_THINK))
    usleep(D_THINK+rnd(V_THINK)-rnd(V_THINK));
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Ignore
 *
 *      Purpose:        Log the occurrence of a signal, but ignore it.
 */
void ignore(int sig)
{
    if(sig!=0) warn("ignore", "MegaHAL received signal %d", sig);

#if !defined(DOS)
    //    signal(SIGINT, saveandexit);
    //    signal(SIGILL, die);
    //    signal(SIGSEGV, die);
#endif
    //    signal(SIGFPE, die);
}


/*---------------------------------------------------------------------------*/

/*
 *      Function:   Die
 *
 *      Purpose:        Log the occurrence of a signal, and exit.
 */
void die(int sig)
{
    error("die", "MegaHAL received signal %d", sig);
    exithal();
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Rnd
 *
 *      Purpose:        Return a random integer between 0 and range-1.
 */
int rnd(int range)
{
    static bool flag=FALSE;

    if(flag==FALSE) {
#if defined(__mac_os) || defined(DOS)
    srand(time(NULL));
#else
    srand48(time(NULL));
#endif
    }
    flag=TRUE;
#if defined(__mac_os) || defined(DOS)
    return(rand()%range);
#else
    return(floor(drand48()*(double)(range)));
#endif
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Usleep
 *
 *      Purpose:        Simulate the Un*x function usleep.  Necessary because
 *                      Microsoft provide no similar function.  Performed via
 *                      a busy loop, which unnecessarily chews up the CPU.
 *                      But Windows '95 isn't properly multitasking anyway, so
 *                      no-one will notice.  Modified from a real Microsoft
 *                      example, believe it or not!
 */
#if defined(DOS) || defined(__mac_os)
void usleep(int period)
{
    clock_t goal;

    goal=(clock_t)(period*CLOCKS_PER_SEC)/(clock_t)1000000+clock();
    while(goal>clock());
}
#endif

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Strdup
 *
 *      Purpose:        Provide the strdup() function for Macintosh.
 */
#ifdef __mac_os
char *strdup(const char *str)
{
    char *rval=(char *)malloc(strlen(str)+1);

    if(rval!=NULL) strcpy(rval, str);

    return(rval);
}
#endif

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Initialize_Speech
 *
 *      Purpose:        Initialize speech output.
 */
#ifdef __mac_os
bool initialize_speech(void)
{
    bool speechExists = false;
    long response;
    OSErr err;

    err = Gestalt(gestaltSpeechAttr, &response);

    if(!err) {
    if(response & (1L << gestaltSpeechMgrPresent)) {
        speechExists = true;
    }
    }
    return speechExists;
}
#endif

/*---------------------------------------------------------------------------*/

/*
 *      Function:   changevoice
 *
 *      Purpose:        change voice of speech output.
 */
void changevoice(DICTIONARY* words, int position)
{
#ifdef __mac_os
    register int i, index;
    STRING word={ 1, "#" };
    char buffer[80];
    VoiceSpec voiceSpec;
    VoiceDescription info;
    short count, voiceCount;
    unsigned char* temp;
    OSErr err;
    /*
     *      If there is less than 4 words, no voice specified.
     */
    if(words->size<=4) return;

    for(i=0; i<words->size-4; ++i)
    if(wordcmp(word, words->entry[i])==0) {

        err = CountVoices(&voiceCount);
        if (!err && voiceCount) {
        for (count = 1; count <= voiceCount; count++) {
            err = GetIndVoice(count, &voiceSpec);
            if (err) continue;
            err = GetVoiceDescription(&voiceSpec, &info,
                          sizeof(VoiceDescription));
            if (err) continue;


            for (temp= info.name; *temp; temp++) {
            if (*temp == ' ')
                *temp = '_';
            }

            /*
             *      skip command and get voice name
             */
            index = i + 3;
            strcpy(buffer, words->entry[index].word);
            c2pstr(buffer);
            // compare ignoring case
            if (EqualString((StringPtr)buffer, info.name, false, false)) {
            if (gSpeechChannel) {
                StopSpeech(gSpeechChannel);
                DisposeSpeechChannel(gSpeechChannel);
                gSpeechChannel = nil;
            }
            err = NewSpeechChannel(&voiceSpec, &gSpeechChannel);
            if (!err) {
                p2cstr((StringPtr)buffer);
                printf("Now using %s voice\n", buffer);
                c2pstr(buffer);
                err = SpeakText(gSpeechChannel, &buffer[1], buffer[0]);
            }
            }
        }
        }
    }
#endif
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   listvoices
 *
 *      Purpose:        Display the names of voices for speech output.
 */
void listvoices(void)
{
#ifdef __mac_os
    VoiceSpec voiceSpec;
    VoiceDescription info;
    short count, voiceCount;
    unsigned char* temp;
    OSErr err;

    if(gSpeechExists) {
    err = CountVoices(&voiceCount);
    if (!err && voiceCount) {
        for (count = 1; count <= voiceCount; count++) {
        err = GetIndVoice(count, &voiceSpec);
        if (err) continue;

        err = GetVoiceDescription(&voiceSpec, &info,
                      sizeof(VoiceDescription));
        if (err) continue;

        p2cstr(info.name);
        for (temp= info.name; *temp; temp++)
            if (*temp == ' ')
            *temp = '_';
        printf("%s\n",info.name);
        }
    }
    }
#endif
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Speak
 */
void speak(char *output)
{
    if(speech==FALSE) return;
#ifdef __mac_os
    if(gSpeechExists) {
    OSErr err;

    if (gSpeechChannel)
        err = SpeakText(gSpeechChannel, output, strlen(output));
    else {
        c2pstr(output);
        SpeakString((StringPtr)output);
        p2cstr((StringPtr)output);
    }
    }
#endif
}

/*---------------------------------------------------------------------------*/

/*
 *      Function:   Progress
 *
 *      Purpose:        Display a progress indicator as a percentage.
 */
bool progress(char *message, int done, int total)
{
    static int last=0;
    static bool first=FALSE;

    /*
     *    We have already hit 100%, and a newline has been printed, so nothing
     *    needs to be done.
     */
    if((done*100/total==100)&&(first==FALSE)) return(TRUE);

    /*
     *    Nothing has changed since the last time this function was called,
     *    so do nothing, unless it's the first time!
     */
    if(done*100/total==last) {
    if((done==0)&&(first==FALSE)) {
        fprintf(stderr, "%s: %3d%%", message, done*100/total);
        first=TRUE;
    }
    return(TRUE);
    }

    /*
     *    Erase what we printed last time, and print the new percentage.
     */
    last=done*100/total;

    if(done>0) fprintf(stderr, "%c%c%c%c", 8, 8, 8, 8);
    fprintf(stderr, "%3d%%", done*100/total);

    /*
     *    We have hit 100%, so reset static variables and print a newline.
     */
    if(last==100) {
    first=FALSE;
    last=0;
    fprintf(stderr, "\n");
    }

    return(TRUE);
}

/*---------------------------------------------------------------------------*/

void help(void)
{
    unsigned int j;

    for(j=0; j<COMMAND_SIZE; ++j) {
    printf("#%-7s: %s\n", command[j].word.word, command[j].helpstring);
    }
}

/*---------------------------------------------------------------------------*/

void load_personality(MODEL **model)
{
    FILE *file;
    static char *filename=NULL;

    if(filename==NULL) filename=(char *)malloc(sizeof(char)*1);

    /*
     *      Allocate memory for the filename
     */
    filename=(char *)realloc(filename,
                 sizeof(char)*(strlen(directory)+strlen(SEP)+12));
    if(filename==NULL) error("load_personality","Unable to allocate filename");

    /*
     *      Check to see if the brain exists
     */

    if(strcmp(directory, last)!=0) {
    sprintf(filename, "%s%smegahal.brn", directory, SEP);
    file=fopen(filename, "r");
    if(file==NULL) {
        sprintf(filename, "%s%smegahal.trn", directory, SEP);
        file=fopen(filename, "r");
        if(file==NULL) {
        fprintf(stdout, "Unable to change MegaHAL personality to \"%s\".\n"
            "Reverting to MegaHAL personality \"%s\".\n", directory, last);
        free(directory);
        directory=strdup(last);
        return;
        }
    }
    fclose(file);
    fprintf(stdout, "Changing to MegaHAL personality \"%s\".\n", directory);
    }

    /*
     *      Free the current personality
     */
    free_model(*model);
    free_words(ban);
    free_dictionary(ban);
    free_words(aux);
    free_dictionary(aux);
    free_words(grt);
    free_dictionary(grt);
    free_swap(swp);

    /*
     *      Create a language model.
     */
    *model=new_model(order);

    /*
     *      Train the model on a text if one exists
     */

    sprintf(filename, "%s%smegahal.brn", directory, SEP);
    if(load_model(filename, *model)==FALSE) {
    sprintf(filename, "%s%smegahal.trn", directory, SEP);
    train(*model, filename);
    }

    /*
     *      Read a dictionary containing banned keywords, auxiliary keywords,
     *      greeting keywords and swap keywords
     */
    sprintf(filename, "%s%smegahal.ban", directory, SEP);
    ban=initialize_list(filename);
    sprintf(filename, "%s%smegahal.aux", directory, SEP);
    aux=initialize_list(filename);
    sprintf(filename, "%s%smegahal.grt", directory, SEP);
    grt=initialize_list(filename);
    sprintf(filename, "%s%smegahal.swp", directory, SEP);
    swp=initialize_swap(filename);
}

/*---------------------------------------------------------------------------*/

void change_personality(DICTIONARY *command, unsigned int position, MODEL **model)
{

    if(directory == NULL) {
    directory = (char *)malloc(sizeof(char)*(strlen(DEFAULT)+1));
    if(directory == NULL) {
        error("change_personality", "Unable to allocate directory");
    } else {
        strcpy(directory, DEFAULT);
    }
    }

    if(last == NULL) {
    last = strdup(directory);
    }

    if((command == NULL)||((position+2)>=command->size)) {
    /* no dir set, so we leave it to whatever was set above */
    } else {
        directory=(char *)realloc(directory,
                                  sizeof(char)*(command->entry[position+2].length+1));
        if(directory == NULL)
            error("change_personality", "Unable to allocate directory");
        strncpy(directory, command->entry[position+2].word,
                command->entry[position+2].length);
        directory[command->entry[position+2].length]='\0';
    }

    load_personality(model);
}

/*---------------------------------------------------------------------------*/

void free_words(DICTIONARY *words)
{
    register unsigned int i;

    if(words == NULL) return;

    if(words->entry != NULL)
    for(i=0; i<words->size; ++i) free_word(words->entry[i]);
}

/*---------------------------------------------------------------------------*/

void free_word(STRING word)
{
    free(word.word);
}

/*===========================================================================*/

/*
 *      $Log: megahal.c,v $
 *      Revision 1.10  2004/02/23 11:12:29  lfousse
 *      Changed default working directory and added options to change it.
 *
 *      Revision 1.9  2004/01/13 10:59:20  lfousse
 *      * Applied code cleaning already shipped with the debian package.
 *      * Removed pure debian stuff.
 *      * Added lacking setup.py file for python module.
 *
 *      Revision 1.8  2003/08/26 12:49:16  lfousse
 *      * Added the perl interface
 *      * cleaned up the python interface a bit (but this
 *        still need some work by a python "expert")
 *      * Added a learn_no_reply function.
 *
 *      Revision 1.7  2003/08/18 21:45:23  lfousse
 *      Added megahal_learn_no_reply function for quick learning, and
 *      corresponding python interface.
 *
 *      Revision 1.6  2002/10/16 04:32:53  davidw
 *      * megahal.c (change_personality): [ 541667 ] Added patch from Andrew
 *        Burke to rework logic in change_personality.
 *
 *      * megahal.c: Trailing white space cleanup.
 *
 *      * python-interface.c: [ 546397 ] Change python include path to a more
 *        recent version.  This should really be fixed by using some of
 *        Python's build automation tools.
 *
 *      Revision 1.5  2000/11/08 11:07:11  davidw
 *      Moved README to docs directory.
 *
 *      Changes to debian files.
 *
 *      Revision 1.4  2000/09/07 21:51:12  davidw
 *      Created some library functions that I think are workable, and moved
 *      everything else into megahal.c as static variables/functions.
 *
 *      Revision 1.3  2000/09/07 11:43:43  davidw
 *      Started hacking:
 *
 *      Reduced makefile targets, eliminating non-Linux OS's.  There should be
 *      a cleaner way to do this.
 *
 *      Added Tcl and Python C level interfaces.
 *
 *      Revision 1.23  1998/05/19 03:02:02  hutch
 *      Removed a small malloc() bug, and added a progress display for
 *      generate_reply().
 *
 *      Revision 1.22  1998/04/24 03:47:03  hutch
 *      Quick bug fix to get sunos version to work.
 *
 *      Revision 1.21  1998/04/24 03:39:51  hutch
 *      Added the BRAIN command, to allow user to change MegaHAL personalities
 *      on the fly.
 *
 *      Revision 1.20  1998/04/22 07:12:37  hutch
 *      A few small changes to get the DOS version to compile.
 *
 *      Revision 1.19  1998/04/21 10:10:56  hutch
 *      Fixed a few little errors.
 *
 *      Revision 1.18  1998/04/06 08:02:01  hutch
 *      Added debugging stuff, courtesy of Paul Baxter.
 *
 *      Revision 1.17  1998/04/02 01:34:20  hutch
 *      Added the help function and fixed a few errors.
 *
 *      Revision 1.16  1998/04/01 05:42:57  hutch
 *      Incorporated Mac code, including speech synthesis, and attempted
 *      to tidy up the code for multi-platform support.
 *
 *      Revision 1.15  1998/03/27 03:43:15  hutch
 *      Added AMIGA specific changes, thanks to Dag Agren.
 *
 *      Revision 1.14  1998/02/20 06:40:13  hutch
 *      Tidied up transcript file format.
 *
 *      Revision 1.13  1998/02/20 06:26:19  hutch
 *      Fixed random number generator and Seed() function (thanks to Mark
 *      Tarrabain), removed redundant code left over from the Loebner entry,
 *      prettied things up a little and destroyed several causes of memory
 *      leakage (although probably not all).
 *
 *      Revision 1.12  1998/02/04 02:55:11  hutch
 *      Fixed up memory allocation error which caused SunOS versions to crash.
 *
 *      Revision 1.11  1998/01/22 03:16:30  hutch
 *      Fixed several memory leaks, and the frustrating bug in the
 *      Write_Input routine.
 *
 *      Revision 1.10  1998/01/19 06:44:36  hutch
 *      Fixed MegaHAL to compile under Linux with a small patch credited
 *      to Joey Hess (joey@kitenet.net).  MegaHAL may now be included as
 *      part of the Debian Linux distribution.
 *
 *      Revision 1.9  1998/01/19 06:37:32  hutch
 *      Fixed a minor bug with end-of-sentence punctuation.
 *
 *      Revision 1.8  1997/12/24 03:17:01  hutch
 *      More bug fixes, and hopefully the final contest version!
 *
 *      Revision 1.7  1997/12/22  13:18:09  hutch
 *      A few more bug fixes, and non-repeating implemented.
 *
 *      Revision 1.6  1997/12/22 04:27:04  hutch
 *      A few minor bug fixes.
 *
 *      Revision 1.5  1997/12/15 04:35:59  hutch
 *      Final Loebner version!
 *
 *      Revision 1.4  1997/12/11 05:45:29  hutch
 *      The almost finished version.
 *
 *      Revision 1.3  1997/12/10 09:08:09  hutch
 *      Now Loebner complient (tm).
 *
 *      Revision 1.2  1997/12/08 06:22:32  hutch
 *      Tidied up.
 *
 *      Revision 1.1  1997/12/05  07:11:44  hutch
 *      Initial revision (lots of files were merged into one, RCS re-started)
 *
 *      Revision 1.7  1997/12/04 07:07:13  hutch
 *      Added load and save functions, and tidied up some code.
 *
 *      Revision 1.6  1997/12/02 08:34:47  hutch
 *      Added the ban, aux and swp functions.
 *
 *      Revision 1.5  1997/12/02 06:03:04  hutch
 *      Updated to use a special terminating symbol, and to store only
 *      branches of maximum depth, as they are the only ones used in
 *      the reply.
 *
 *      Revision 1.4  1997/10/28 09:23:12  hutch
 *      MegaHAL is babbling nicely, but without keywords.
 *
 *      Revision 1.3  1997/10/15  09:04:03  hutch
 *      MegaHAL can parrot back whatever the user says.
 *
 *      Revision 1.2  1997/07/21 04:03:28  hutch
 *      Fully working.
 *
 *      Revision 1.1  1997/07/15 01:55:25  hutch
 *      Initial revision.
 */

/*===========================================================================*/