// Let's implement a simple spell checker that uses a binary search
// to find a word in a (short) dictionary.

import java.io.*;

public class Spell
{
  private String [] dictionary;

  /** Read the system dictionary (list of words) and put the words in
   *  my dictionary.  There are 2 loops.  One counts the words so we know how
   *  big the dictionary is, and the second loop actually puts all these words
   *  into our array.  (Later, we will see a more efficient way to do this.)
   *  We could have just looked at the dictionary ourselves and noticed it has
   *  25143 words and put that number in the code, but we'd rather have a more
   *  flexible program.  It's not a good idea to use "magic numbers".
   */
  public Spell() throws IOException
  {
    // First, count the words in the dictionary (one per line).
    // Note that the name of the dictionary file may change (we could
    // ask the user for the location).
    BufferedReader in = new BufferedReader(new FileReader("/usr/dict/words"));
    int numWords = 0;
    while (true)
    {
      String word = in.readLine();
      if (word == null)
        break;
      ++numWords;
    }

    // Allocate space for the array, and reopen the dictionary.
    dictionary = new String[numWords];
    in = new BufferedReader(new FileReader("/usr/dict/words"));

    for (int i = 0; i < numWords; ++i)
    {
      dictionary[i] = in.readLine().toLowerCase();
    }
    System.out.println("Done reading in dictionary.");
  }

  // The idea here is to use a binary search.  The variables left and right
  // will keep track of the endpoints of the search, and we guess in the
  // middle.  If we are wrong, then we cut the search space in half, until
  // we find the word or conclude it does not exist.
  public boolean findWord(String word)
  {
    // immediately change to lowercase 
    word = word.toLowerCase();

    int left = 0;
    int right = dictionary.length - 1;

    // Keep going until we run out of space.
    do
    {
      System.out.println("I think the word is somewhere between " +
                         dictionary[left] + " and " + dictionary[right]);

      // Guess somewhere in the middle
      int middle = (left + right) / 2;

      // See what word it is and compare it to the word we're searching for.
      // If the word I'm looking for is greater than the middle word, then
      // we need to look in the right half of the array.
      if (word.compareToIgnoreCase(dictionary[middle]) > 0)
      {
        System.out.println("  Too low -- setting left to " + middle);
        left = middle;
      }

      // If the word I'm looking for is less than the middle word, then we
      // need to look in the left half of the array.
      else if (word.compareTo(dictionary[middle]) < 0)
      {
        System.out.println("  Too high -- setting right to " + middle);
        right = middle;
      }

      // Else we have a match!
      else
      {
        System.out.println ("  I found the word at position " + middle);
        return true;
      }
    } while (right >= left + 2);

    // The above test condition to continue looping means that we want to
    // keep trying to look in the dictionary as long as:  right >= left + 2.
    // This means we still have some middle ground to divide.  If this
    // condition weren't true, then the difference between the left and right
    // would only be 1, and there is no word in the middle to search for.

    System.out.println("I could not find the word, sorry.");
    return false;
  }
}