package username.analysis;

import java.math.BigDecimal;
import java.io.PrintWriter;
import java.util.Comparator;

/**
 * A class that computes various functions and serves as an
 * illustration of how we might experimentally analyze those
 * functions.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of March 2005
 */
public class Computer
{

  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /** A counter for the number of steps an algorithm takes. */
  long steps;


  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+

  // We rely on the default zeroary constructor.


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

  /**
   * Compute x^n using a straightforward for loop.
   *
   * @pre
   *   n >= 0
   * @post
   *   result = x * x * x * ... * x, with n x's.
   */
  public BigDecimal exptFor(BigDecimal x, int n)
  {
    BigDecimal result = new BigDecimal(1.0);
    for (int i = 0; i < n ; i++) {
      this.step();
      result = result.multiply(x);
    }
    return result;
  } // exptFor(BigDecimal, int)

  /**
   * Compute x^n using a clever algorithm.
   *
   * @pre
   *   n >= 0
   * @post
   *   result = x * x * x * ... * x, with n x's.
   */
  public BigDecimal exptWhile(BigDecimal x, int n)
  {
    BigDecimal accumulator = new BigDecimal(1);
    // need to repeatedly reduce the power.  Idea:
    // currentx^currentn * accumulator = originalx^originaln
    while (n > 0) {
      this.step();
      // If n is even, divide it by two and multiply x by
      // itself, using the amazing rule that
      // (x^n = (x^2)^(n/2))
      if ((n % 2) == 0) {
        // Recursive version: expt3(x.multiply(x), n/2, accumulator);
        n = n/2;
	x = x.multiply(x);
      } // n is even
      // If n is odd, subtract 1 from it and ..
      else {
        // Recursive version: expt3(x, n-1, x.multiply(accumulator));
        n = n - 1;
	accumulator = x.multiply(accumulator);
      } // n is odd
    } // while
    return accumulator;
  } // exptWhile(BigDecimal, int)

  /**
   * Search for val in an array.
   *
   * @param val 
   *   The value to search for
   * @param a
   *   An array of values to search
   * @param c
   *   A comparator for determining whether two values are equal.
   *
   * @result
   *   index, the index of val
   * @pre
   *   Values are comparable
   * @post
   *   If index >=0, a[index] = val.
   *   If index is -1, there exists no i s.t. a[i] = val
   *   Does not modify a.
   */
  public int sequentialSearch(Object val, Object[] a, Comparator c)
  {
    // Look at each index in turn
    for (int i = 0; i < a.length; i++) {
      // If it matches, return it
      if (c.compare(val, a[i]) == 0)
        return i;
    } // look at each index
    // If we've reached this point, it's not there
    return -1;
  } // sequentialSearch(Object, Object[], Comparator)

  /**
   * Search for val in an array.
   *
   * @param val 
   *   The value to search for
   * @param a
   *   An array of values to search
   * @param c
   *   A comparator for determining whether two values are equal.
   *
   * @result
   *   index, the index of val
   * @pre
   *   Values are comparable
   * @pre
   *   a is in increasing order (as determined by c)
   * @post
   *   If index >=0, a[index] = val.
   *   If index is -1, there exists no i s.t. a[i] = val
   *   Does not modify a.
   */
  public int binarySearch(Object val, Object[] a, Comparator c)
  {
    // Determine the lower-bound of the range on interest.
    int lb = 0;

    // Determine  the upper-bound of the range of interest.
    int ub = a.length - 1;

    // Repeatedly look in the middle and discard as necessary
    while (lb <= ub) {
      // Get the middle
      int mid = (lb+ub)/2;
      // Determine relationships
      int order = c.compare(val, a[mid]);
      // Best possible option: the middle matches
      if (order == 0)
        return mid;
      // Another option: the middle is too large
      else if (order < 0) {
        ub = mid-1;
      }
      // The last option: The middle is too small
      else {
        lb = mid + 1;
      } 
    } // while
    // If we've reached this point, it's not there.
    return -1;
  } // binarySearch

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

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

  /**
   * Reset the count of the number of steps spent.
   */
  void reset()
  {
    this.steps = 0;
  } // reset()

  /**
   * Count one step.
   */
  void step()
  {
    ++this.steps;
  } // step()

  /**
   * Get the total number of steps used.
   */
 long steps() 
 {
   return this.steps;
 } // steps()


  // +-------+---------------------------------------------------
  // | Tests |
  // +-------+

  void testExptFor(PrintWriter pen)
  {
    BigDecimal x;
    // Try a variety of exponents
    for (int n = 0; n < 5000; n = n*2+1) {
      // Try a variety of bases
      for (int i = 0; i <= 6; i++) {
        x = new BigDecimal(((double) i) / 2);
        this.reset();
        long alpha = System.currentTimeMillis();
        BigDecimal result = this.exptFor(x,n);
        long omega = System.currentTimeMillis();
	pen.println("x: " + x 
	            + "\tn: " + n
	            + "\tsteps: " + this.steps() 
	            + "\ttime: " + (omega-alpha));
      } // for each base
    } // for each exponent
  } // testExptFor(Computer, PrintWriter)


  // +------+----------------------------------------------------
  // | Main |
  // +------+

  public static void main(String[] args)
  {
    PrintWriter pen = 
      new PrintWriter(System.out, true);
    Computer vax = new Computer();
    vax.testExptFor(pen);
  } // main(String[])

} // class Exponent