#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>

#define MAXORDER 10
#define BUFSIZE 29
#define BUFINFO 28
#define SPACE 27

int mygetchar(FILE *thefile);
void usage(char *appname);

int lastchar;

int main(int argc, char *argv[])
{
  unsigned int order;
  long i;
  unsigned long index;
  FILE *thefile;
  int thechar;
  unsigned int *array;
  char history[MAXORDER],history2[MAXORDER];
  int size;
  int wait;

  if (argc<2)
    {
      usage(argv[0]);
      exit(0);
    }

  order=atoi(argv[2]);
  wait=order;

  size=(int) pow((double) BUFSIZE,(double) order);

  if ((array=calloc(sizeof(unsigned int),size))==NULL)
    {
      printf("couldn't allocate %i bytes\n",size);
      exit(0);
    }

  if ((thefile=fopen(argv[1],"r"))==NULL)
    {
      perror(argv[1]);
      return;
    }
  

  while (1)
    {
      thechar=mygetchar(thefile);
      if (thechar==EOF)
	break;

      if (isalpha(thechar))
	thechar-='A';
      else
	thechar=SPACE;

      for (i=0;i<order-1;i++)
	  history[i]=history[i+1];
      history[order-1]=thechar;

      index=0;

      for (i=0;i<order-1;i++)
	  index=index*BUFSIZE+history[i];
      index*=BUFSIZE;

      if (wait==0)
	{
	  /* increment the letter count */
	  array[index+BUFINFO]++;
	  
	  /* increment the count for that letter */
	  array[index+thechar]++;
	}
      else
	wait--;
    }
  
  fclose(thefile);
  
  while (1)
    {
      printf("Prefix: ");
      gets(history2);
      
      if (strlen(history2)==0)
	break;
      
      index=0;
      
      for (i=0;i<order-1;i++)
	{
	  if (history2[i]==' ')
	    index=index*BUFSIZE+SPACE;
	  else
	    index=index*BUFSIZE+(history2[i]-'A');
	}

      index*=BUFSIZE;
      printf("%i total\n",array[index+BUFINFO]);
      
      for (thechar=0;thechar<26;thechar++)
	printf("%c  %2.1f\n",thechar+'A',((float) 100* array[index+thechar])/((float) array[index+BUFINFO]));
      printf("SP %2.1f\n",((float) array[index+SPACE])/((float) 100* array[index+BUFINFO]));
    }


  printf("generating\n");

  /* now generate some random text. we'll use our prebuilt history array
     as a place to start from. */

  puts(history);

  while (1)
    {
      index=0;
      
      for (i=0;i<order-1;i++)
	  index=index*BUFSIZE+history[i];

      index*=BUFSIZE;

      i=1+((float) array[index+BUFINFO])*(((float) rand())/((float) RAND_MAX));

      /*      printf("randomizing: %i/%i\n",i,array[index+BUFINFO]); */

      for (thechar=0;thechar<=SPACE;thechar++)
	{
	  i=i-array[index+thechar];

	  if (i<=0)
	    {
	      if (thechar<26)
		printf("%c",thechar+'A');
	      else
		printf(" ");

	      break;
	    }
	  if (thechar==BUFINFO)
	    {
	      printf("generate error\n");
	    }
	}

      for (i=0;i<order-1;i++)
	  history[i]=history[i+1];
      if (order>=2)
	history[order-2]=thechar;
    }
}

int mygetchar(FILE *thefile)
{
  int thechar;
  
  thechar=0;
  
loop:
  while (!isalpha(thechar) && !isspace(thechar) && thechar!=',' && thechar!='.' && thechar!=EOF)
    {
      thechar=fgetc(thefile);
      if (isalpha(thechar))
	thechar=toupper(thechar);
    }
  
  if (isspace(thechar))
    thechar=' ';
  
  if (thechar==' ' && lastchar==' ' && thechar!=EOF)
    {
      thechar=0;
      goto loop;
    }

  if (!isalpha(thechar) && thechar!=' ' && thechar!=EOF)
    {
      thechar=0;
      goto loop;
    }

  lastchar=thechar;

  return (thechar);
}

void usage(char *appname)
{
printf("Usage: %s <filename> <#orders>\n\n",appname);
}