/***************************************** 
** File: binary.c
** Author: Marie desJardins
** Date: 
** E-Mail: mariedj@cs.umbc.edu 
** 
** Contains code to read a list of words, and find a particular
** word in the list using linear and binary search.
**
** Must be linked with2darray.c.
*****************************************/ 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "2darray.h"

#define WORDFILE "/usr/dict/words"
#define MAXWORDLEN 100  /* not many English words longer than this... */

char **ReadWordList (int *numWordsPtr);
void LinearSearch (char *word, char **words, int numWords);
void BinarySearch (char *word, char **words, int startIndex, int endIndex);
void ToLowerCase (char *word);


int main (int argc, char **argv) {
  int numWords = 0;
  char **words;

  /* Command line check */
  if ( argc != 2 ) {
    fprintf (stderr, "Usage: a.out WORD\n");
    exit (-1);
  }

  /* Read word file, and look for the word in two different ways */
  words = ReadWordList (&numWords);
  LinearSearch (argv[1], words, numWords);
  BinarySearch (argv[1], words, 0, numWords-1);

  /* Housekeeping! */
  free (words);
  return 0;
}


/***************************************** 
 * Function: ReadWordList
 * Usage: words = ReadWordList (&numWords);
 * 
 * Open the WORDFILE, and read the words into an array of strings.
 * 
 * Input: numWordsPtr, a pointer to the numWords variable
 * Output: an array of strings, and the numWords value (by reference)
*****************************************/

char **ReadWordList (int *numWordsPtr) {
  char word[MAXWORDLEN+1];   /* temp space */
  char **words;
  int i;
  FILE *wordstr;

  /* Open the word file */
  if ( ! ( wordstr = fopen (WORDFILE, "r") ) ) {
    fprintf (stderr, "Can't open word file %s\n", WORDFILE);
    exit (-1);
  }

  /* Figure out how many words there are */
  *numWordsPtr = 0;
  while ( fgets (word, MAXWORDLEN, wordstr) ) {
    *numWordsPtr++;
  }

  /* Allocate enough space */
  words = GetTwoDSpace (*numWordsPtr, MAXWORDLEN + 1);

  /* Read word list */
  rewind (wordstr);
  for ( i=0 ; i < *numWordsPtr ; i++ ) {
    fgets (words[i], MAXWORDLEN, wordstr);
    words[i][strlen(words[i])-1] = '\0';
    ToLowerCase (words[i]);
  }

  /* Close the file and return */
  fclose (wordstr);
  return (words);
}


/***************************************** 
 * Function: LinearSearch
 * Usage: LinearSearch (word, words, numWords);
 * 
 * Use linear search to find the index of a given word in 
 * an array of strings.  Print a message with the index, or
 * failure.
 * 
 * Input: a string to look for, an array of strings, and the
 *   size of the array
 * Output: none
*****************************************/

void LinearSearch (char *word, char **words, int numWords) {
  int i;

  /* Loop through all the words, stopping if we find what we're
     looking for */
  for ( i=0 ; i < numWords ; i++ ) {
    if ( ! (strcmp  (words[i], word)) ) {
      printf ("LinearSearch: Found it!  %s is word number %d\n", word, i);
      return;
    }
  }

  /* Reached end of list, didn't find word */
  printf ("LinearSearch: Couldn't find %s in word file!\n", word);

}


/***************************************** 
 * Function: BinarySearch
 * Usage: BinarySearch (word, words, 0, numWords);
 * 
 * Uses recursive binary search to find the index of a given
 * word in an array of words.  Currently somewhat buggy.
 * Assumes the word list is in alphabetical order!
 * This function is case-sensitive, so will only work correctly
 * if "word" and "words" are all lower case.
 *
 * Input: a string, an array of strings, and the start and end
 *   index of the range of words yet to be searched.
 * Output: none
*****************************************/

void BinarySearch (char *word, char **words, int startIndex, int endIndex) {
  /* Base case #1: endIndex has dropped below startIndex.  Give up! */
  if ( endIndex < startIndex ) {
    printf ("BinarySearch: Couldn't find %s in word file (near %s?)\n",
	    word, words[endIndex]);
    return;
  }

  /* Base case #2: endIndex and startIndex are the same.  Either
     we've found the word, or it's not here! */
  if ( endIndex == startIndex ) {
    if ( ! (strcmp (word, words[endIndex] ) ) ) {
      printf ("BinarySearch: Found %s at index %d\n", word, endIndex);
      return;
    } else {
      printf ("BinarySearch: Couldn't find %s in word file (near %s?)\n",
	      word, words[endIndex]);
      return;
    }
  }

  /* Recursive case:  startIndex < endIndex, so check middle word.
     If the middle word is lexically after the word we're looking
     for, look before the middle word.  Else look after the middle word. */
  if ( strcmp (word, words[(startIndex + endIndex)/2]) < 0 ) {
    BinarySearch (word, words, startIndex, (startIndex + endIndex)/2 - 1);
  } else {
    /* "word" is after middle word */
    BinarySearch (word, words, (startIndex + endIndex)/2+1, endIndex);
  }
}

/***************************************** 
 * Function: 
 * Usage: 
 * 
 * 
 * 
 * Input: 
 * Output: 
*****************************************/

void ToLowerCase (char *word) {
  while ( *word ) {
    *word = tolower (*word);
    word++;
  }
}