/** Let's implement a simple spell checker that uses a binary search
 *  to find a word in a dictionary.  This is pretty much the same Spell-
 *  Checking class we did in CS 11.  I've commented out the output.
 */
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();
    }
    //    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 that it does not exist.
   */
  public boolean findWord(String word)
  {
    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("  " + dictionary[middle] + 
        //                 " is 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.compareToIgnoreCase(dictionary[middle]) < 0)
      {
	  //System.out.println("  " + dictionary[middle] + 
	  //               " is 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.

    // Make one last try to look at the extremes of the dictionary
    if (word.equalsIgnoreCase(dictionary[left]) ||
        word.equalsIgnoreCase(dictionary[right]))
    {
	//System.out.println("Rare case of finding the word at the ends.");
      return true;
    }
    else
    {
	//System.out.println("Not even at the ends of the dictionary.");
      return false;
    }
  }
}