/* Sequential Access File Demo Program, version 1.01, created April 2 , 1999.    */
/* Last modified April 3, 1999, by Rick Wagner.                                  */
/* Copyright 1999 by Rick Wagner, all rights reserved.                           */
/* Source code use with attribution for educational purposes only.               */
/* Created for use with Computer Science 101 at USC.                             */

#include <stdio.h>
#include <conio.h>                  /* For getch(). */
#include <ctype.h>                  /* For various character type functions.*/
#include <stdlib.h>                 /* For exit(). */
#include <string.h>                 /* For strlen(), strcpy(), and strcmp(). */

typedef struct
{
  char sWord[30];                   /* The word string. */
  int iNumOccurrences;              /* Number of times the word occurs         */
} Word;                             /* in the input.                           */

typedef struct
{
  Word WordArray[10000];            /* Up to ten thousand words. */
  int iNumWords;
} Dictionary;

/* Function prototypes: */
void about();                       /* Tell about the program.                   */
void menu(Dictionary* d);           /* Menu driven user interface.               */
void readFile(Dictionary* d);
void showDict(Dictionary* d);
void insertWord(char* sNewWord, Dictionary* d);
int searchForWord(int* ptrPosition, char* sSearchWord, Dictionary* d, int iLeft, int iRight);
void lcase(char* s);

void main()
{
  Dictionary d;
  int i = 0;

  d.iNumWords = 0;                  /* Initialize the dictionary word count      */
  
  for (i = 0; i < 1000; i++)        /* Initialize the word array */
  {
    d.WordArray[i].iNumOccurrences = 0;
    d.WordArray[i].sWord[0] = '\0';
  }

  about();                          /* Tell about the program.                   */
  menu(&d);                         /* Pass by reference.                        */
}

void about()
{
  puts("                   Sequential Access File Demo Program");
  puts("                               Version 1.01");
  puts("");
  puts("              Created for use in Computer Science 101 at USC.");
  puts("            Copyright 1999 by Rick Wagner, all rights reserved.");
  puts("");
}

/* Menu driven user interface. */
void menu(Dictionary* d)
{
  char cChoice = 0;

  while(1)
  {
    puts("a. Read a file and count word occurrences.");
    puts("b. Show the dictionary.");
    puts("");
    puts("q. Quit.");
    puts("");
    printf("Enter your choice: ");
    scanf("%c", &cChoice);
    fflush(stdin);
    cChoice = (char) tolower((int) cChoice);
    switch (cChoice)
    {
      case 'a':
      {
        readFile(d);
        break;
      }
      case 'b':
      {
        showDict(d);
        break;
      }
      case 'q':
      {
        puts("\nQuitting. Goodbye.");
        exit(0);
        break;
      }
      default:
      {
        puts("\nBad choice, try again.\n");
        break;
      }
    }
  }
}

/* Step through the input file. */
void readFile(Dictionary* d)
{
  FILE* ptrInFile;                       /* FILE's a struct defined in stdio.h. */
  char cIn = 0;                          /* Input character from file. */
  char sWord[30];                        /* Array to hold input word characters. */
  int iWordIndex = 0;                    /* Position in the word. */
  int iDoingWord = 0;                    /* Flag: we are in the middle of a word. */
  char sInFile[80];                      /* String for user input file spec. */
  int iNotAtEOF = 1;

  printf("\nEnter the file specification: ");
  gets(sInFile);
  if (strlen(sInFile) == 0)
  {
    strcpy(sInFile, "sps.txt");
  }
  ptrInFile = fopen(sInFile, "r");

  /* Parse the file character by character: */
  while (iNotAtEOF)
  {
   cIn = getc(ptrInFile);
   printf("%c", cIn);
   if(isalnum(cIn) != 0)
    {
      /* It's an alphanumeric charater: */
      iDoingWord = 1;
      sWord[iWordIndex] = cIn;
      iWordIndex++;
    }
    else
    {
      if (iDoingWord)
      {
        /* Need to finish off the word and reset things. */
        sWord[iWordIndex] = '\0';
        iWordIndex = 0;
        iDoingWord = 0;

        /* Put the word in the dictionary. */
        insertWord(sWord, d);
      }
    }
    if (cIn == EOF)
    {
      iNotAtEOF = 0;
    }
  }
  printf("\n");
  fclose(ptrInFile);
}

/* Insert a word in sorted order into the dictionary word array. */
void insertWord(char* sNewWord, Dictionary* d)
{
  int i = 0;
  int iPosition = 0;
  int iFound = 0;

  iFound = searchForWord(&iPosition, sNewWord, d, 0, d->iNumWords);

  if (iFound)
  {
    /* The word is in the dictionary. Increment its counter. */
    d->WordArray[iPosition].iNumOccurrences++;
  }
  else
  {
    /* Insert the word in the dictionary array */
    for (i = d->iNumWords; i > iPosition; i--)
    {
      /* Move the position word and those greater one place over. */
      strcpy(d->WordArray[i].sWord, d->WordArray[i - 1].sWord);
      d->WordArray[i].iNumOccurrences = d->WordArray[i - 1].iNumOccurrences;
    }
    strcpy(d->WordArray[iPosition].sWord, sNewWord);
    d->WordArray[iPosition].iNumOccurrences = 1;
    d->iNumWords++;
  }
}

int searchForWord(int* ptrPosition, char* sSearchWord, Dictionary* d, int iLeft, int iRight)
{
  int r = 0;  /* Return value default is "not found." */
  char sTemp1[30];
  char sTemp2[30];

  /* Make a copy of the search word for conversion to lower case for sort comparison: */
  strcpy(sTemp1, sSearchWord);
  lcase(sTemp1);

  /* Assumes the array to be searched is sorted */
  int iMiddle = 0;

  if (iRight - iLeft > 0)
  {
    /* There is at least one word in the array */
    int iMiddle = (iLeft + iRight) / 2;           /* Integer division */
    strcpy(sTemp2, d->WordArray[iMiddle].sWord);  /* Copy the array word */
    lcase(sTemp2);                                /* and convert the copy to lower case. */

    if (strcmp(sTemp1, sTemp2) == 0)
    {
      /* Word is in the dictionary already */
      *ptrPosition = iMiddle;
      r = 1;
    }
    else
    {
      if (strcmp(sTemp1, sTemp2) > 0)
      {
        /* Search the right half of the array: */
        r = searchForWord(ptrPosition, sSearchWord, d, iMiddle + 1, iRight);
      }
      else
      {
        /* Search the left half of the array: */
        r = searchForWord(ptrPosition, sSearchWord, d, iLeft, iMiddle);
      }
    }
  }
  else
  {
    *ptrPosition = iLeft;
  }
  return r;
}

/* Show the word list: */
void showDict(Dictionary* d)
{
  int i = 0;
  char k = 0;
  for (i = 0; i < d->iNumWords; i ++)
  {
    printf("%-4d %-29s %-3d\n", i + 1, d->WordArray[i].sWord, d->WordArray[i].iNumOccurrences);
    if ((i + 1) % 23 == 0)
    {
      printf("\nHit any key for more. ");
      k = getch();
      printf("\n");
    }
  }
  printf("\n");
}

void lcase(char* s)
{
  int i = 0;
  int iLength = 0;

  iLength = strlen(s);
  for (i = 0; i < iLength; i++)
  {
    s[i] = (char) tolower((int) s[i]);
  }

  /* Could have written it this way more cryptically:

  int i;for(i=0;i<(int)strlen(s);i++)s[i]=(char)tolower((int)s[i]);

  */
}