package username.analysis;

import java.math.BigInteger;
import java.util.Vector;

/**
 * A class that supports various kinds of searches.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of April 2006
 */
public class Searcher<T extends Comparable>
{

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

  /** The analyst that helps determine running time. */
  Analyst a;


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

  /**
   * Build a new searcher that records information using 
   * an analyst.
   */
  public Searcher(Analyst _a)
  {
    this.a = _a;
  } // Searcher(Analyst)


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

  /**
   * Search for val in a Vector.
   *
   * @param val 
   *   The value to search for
   * @param a
   *   A vector of values to search
   *
   * @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(T val, Vector<T> vals)
  {
    // Look at each index in turn
    int len = vals.size();
    for (int i = 0; i < len; i++) {
      // If it matches, return it
      if (val.equals(vals.get(i))) {
        return i;
      } // if
    } // look at each index
    // If we've reached this point, it's not there
    return -1;
  } // sequentialSearch(T, Vector<T>)

  /**
   * Search for val in a sorted vector.
   *
   * @param val 
   *   The value to search for
   * @param a
   *   A vector of values to search
   *
   * @result
   *   index, the index of val
   * @pre
   *   Values are comparable
   * @pre
   *   a is in increasing order.
   * @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(T val, Vector<T> vals)
  {
    // Determine the lower-bound of the range on interest.
    int lb = 0;

    // Determine  the upper-bound of the range of interest.
    int ub = vals.size() - 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 = val.compareTo(vals.get(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

} // class Searcher