/**
 * An ``intelligent'' number guesser that can guess numbers within a 
 * particular range, provided an oracle can tell it a little about its
 * guesses.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of January 1999
 */
public class NumberGameGuesser {
  // +---------+-----------------------------------------------------------
  // | Methods |
  // +---------+

  /**
   * Try to guess a number in the range [lower ... upper].  Only the
   * oracle knows the correct answer.  The upper end of the range cannot
   * be larger than Long.MAX_VALUE/2, and the lower end of the range
   * cannot be smaller than Long.MAX_VALUE/2 (see if you can figure out
   * why).
   */
  void guessNumber(long lower, long upper, 
                   SimpleOutput out, 
                   NumberGameOracle oracle) {
    // Make sure there are possibilities.
    if (upper < lower) {
      out.println("No possible answers!");
      return;
    } // if the range is empty.
    if (upper > Long.MAX_VALUE/2) {
      out.println("The upper bound of the range cannot be higher than " +
                  Long.MAX_VALUE/2);
      return;
    } // If the upper bound is too high.
    if (lower < Long.MIN_VALUE/2) {
      out.println("The lower bound of the range cannot be smaller than " +
                  Long.MIN_VALUE/2);
      return;
    }
    // Make a guess directly between the two.
    long guess = (lower+upper) / 2;
    out.println("I guess: " + guess);
    // Is it correct?
    if (oracle.isCorrect(guess)) {
      out.println("Wa hoo!  The answer is " + guess);
    }
    // Is it too small?  If so, we know it has to be in the range
    // [guess+1 ... upper].
    else if (oracle.isSmall(guess)) {
      out.println("  Oh well, that guess is too small.");
      guessNumber(guess+1,upper,out,oracle);
    }
    // It's not correct.  It's not too small.  It must be too large.
    // Hence, the number must be in the range [lower ... guess-1].
    else {
      out.println("  Hmmm.  That guess is too large.");
      guessNumber(lower,guess-1,out,oracle);
    }
  } // guessNumber(long,long,SimpleOutput,Oracle)
} // class NumberGameGuesser