import SimpleOutput;

/**
 * Trinary search.  A strange variant of binary search.  Intended
 * as an example for the answer key for HW6 of CS152 99S.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of March 1999
 */
public class TrinarySearch {

  // +---------+-------------------------------------------------
  // | Methods |
  // +---------+

  /**
   * Determine the index of x in array A.
   * Pre: A is sorted in increasing order.
   * Post: If x is in A, then returns i s.t. A[i] == x
   * Post: If x is not in A, then throws an exception
   */
  public int trinarySearch(int x, int[] A) 
    throws Exception
  {
    // Use the marvelous helper function
    return trinarySearch(x, A, 0, A.length-1);
  } // trinarySearch(int, int[])
  
  /**
   * Determine the index of x in the subarray of A given by lb..ub.
   * Pre: A is sorted in increasing order.
   * Pre: If x is in A, then x is in the subarray.
   * Pre: If x is not in A, then x is not in the subarray.
   * Post: If x is in A, then returns i s.t. A[i] == x
   * Post: If x is not in A, then throws an exception
   */
  public int trinarySearch(int x, int[] A, int lb, int ub) 
    throws Exception
  {
    // Base case: empty subarray.  x is not in A.
    if (ub < lb) throw new Exception("Not found");
    // Base case: single-element subarray.  See if x is that element.
    else if (lb == ub) {
      if (x == A[lb]) return lb;
      else throw new Exception("Not found");
    } // single-element subarray
    // Recursive cases: split the array and search the appropriate subarray.
    else {
      // The first split point is one-third of the way from lb to ub.  We
      // compute the distance from lb to ub, take 1/3 of that, and add it
      // to lb.
      int splitOne = lb + (ub-lb)/3;
      // The second split point is two-thirds of the way from lb to ub.  We
      // compute the distance from lb to ub, take 2/3 of that, and add it
      // to lb.
      int splitTwo = lb + (2 * (ub-lb))/3;
      
      // Recursive case: in the first third of the array.
      if (x <= A[splitOne]) 
        return trinarySearch(x, A, lb, splitOne);
      // Recursive case: in the second third of the array.
      else if (x <= A[splitTwo]) 
        return trinarySearch(x, A, splitOne+1, splitTwo);
      // Recursive case: in the third third of the array.
      else 
        return trinarySearch(x, A, splitTwo+1, ub);
    }
  } // trinarySearch(int, int[], int, int)
  
  // +------+----------------------------------------------------
  // | Main |
  // +------+

  /**
   * Test the search method.  Technique: build a number of sorted
   * arrays of different lengths (note that content should not
   * affect our search method, so we can use any sorted content
   * we choose) and consider every position in each array, as
   * well as every "between" position in each array.  To make it
   * easier to do this, we make arrays of the form {2,4,6,8,...2*n}
   * and search for values from 1 to 2*n+1.
   */
  public static void main(String[] args) {
    // Create something that can search.
    TrinarySearch searcher = new TrinarySearch();
    // The array we'll be using
    int[] values;
    // The position found.
    int pos;
    // For output.
    SimpleOutput out = new SimpleOutput();

    // For each reasonable size of array
    for (int size = 1; size <= 10; ++size) {
      // A note.
      out.println("Checking array of size " + size);
      // Build the array.
      values = new int[size];
      // Fill in the elements of the array with the numbers
      // from 2 to 2*size.
      for (int i = 1; i <= size; ++i) {
        values[i-1] = 2*i;
      }
      // Search for values between 1 and 2*size + 1.
      for (int val = 1; val <= 2*size+1; ++val) {
        try {
          pos = searcher.trinarySearch(val,values);
          // If it's odd, it shouldn't have a position.
          if (val % 2 == 1) 
            out.println("  ERROR!  The position of " + val + 
                      " was given as " + pos);
          // If it's even, it's position should be (val/2)-1.
          else if (pos != (val/2)-1) {
            out.println("  ERROR!  The position of " + val + 
                      " was given as " + pos);
          }
        }
        catch (Exception e) {
          // It's okay to throw exceptions for odd numbers
          // (which aren't in the array).  But even numbers
          // should be there.
          if (val % 2 == 0) 
            out.println("  ERROR!  Indicated that " + val + 
                        " was not in the array");
        }  // catch
      } // for each value
    } // for each size
  
  } // main
} // TrinarySearch