import SimpleOutput;

/**
 * Sorted lists of integers.  Intended for the answer key to
 * exam 2 in Grinnell College's CSC152 99S.  Also serves as
 * its own simple tester: you can specify the elements to
 * add/sort on the command line.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of March 1999
 */
public class SortedIntList {

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

  /** The elements of the list. */
  int[] elements;

  /** The length of the list. */
  int length;

  /** 
   * The cursor, used for iteration (although perhaps not
   * in this simplified implementation).
   */
  int cursor;


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

  /**
   * Build a new list with specified capacity.
   */
  public SortedIntList(int capacity) {
    this.elements = new int[capacity];
    this.length = 0;
    this.cursor = 0;
  } // SortedIntList(int)

  /**
   * Build a new list of default capacity.
   */
  public SortedIntList() {
    this(100);
  } // SortedIntList


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

  /**
   * Add a value to this sorted list of integers.
   * Pre: The list is initialized, and there have been no invalid
   *   operations on the list.
   * Pre: There is space remaining in the list to add the new element.
   * Post: Iteration may be invalidated.
   * Post: The value is added, and will be returned in the proper
   *   order during iteration.
   * Post: The length of the list increases by 1.
   */
  public void add(int val) {
    // Determine the correct position in the list.
    int pos = findPlace(val);
    // Shift right to insert the element.
    for (int j = this.length; j > pos; --j) {
      this.elements[j] = this.elements[j-1];
    }
    // Insert the element.
    this.elements[pos] = val;
    // Update the length.
    this.length += 1;
  } // add(int)
 
  /**
   * Clear the list.
   */
  public void clear() {
    this.length = 0;
  } // clear()

  /** 
   * Convert to a string in prepartion for printing.
   */
  public String toString() {
    if (length == 0) return "()";
    String str = "(";
    for (int i = 0; i < length-1; ++i) {
      str += elements[i] + " ";
    }
    str += elements[length-1] + ")";
    return str;
  } // toString()
 
  // +----------------+------------------------------------------
  // | Helper Methods |
  // +----------------+

  /**
   * Find the correct position for a value in the part of
   * the array used for the list.  
   * Pre: The list is initialized, and there have been no invalid
   *   operations on the list.
   * Pre: The array used to implement the list is sorted.
   * Post: Returns a position, pos, such that (1) the element at position
   *   i is less than or equal to val, for all i less than pos; and (2)
   *   the element at position j is greater than or equal to val, for all 
   *   j greater than or equal to pos.  If no elements already in the subarray
   *   are greater than val, returns ub+1.  If no elements already in the
   *   subarray are less than val, returns lb.
   * Post: No elements are added, deleted, or moved.
   */
  public int findPlace(int val) {
    // Special case: empty array.
    if (this.length == 0) return 0;
    // Special case: After array.
    if (val > this.elements[this.length-1]) return this.length;
    // Everything else.
    return findPlace(val , 0, this.length-1);
  } // findPlace(int)

  /**
   * Find the correct position for a value in a part of the
   * array used to implement the list.  
   * Pre: The list is initialized, and there have been no invalid
   *   operations on the list.
   * Pre: The subarray lb..ub is sorted.
   * Pre: lb <= ub
   * Pre: val <= the element at position ub.
   * Post: See above.  Note that since we have that last precondition,
   *   we'll never return ub+1.
   * Post: No elements are added, deleted, or moved.
   */
  protected int findPlace(int val, int lb, int ub) {
    // Base case: Empty subarray.  Use lb.
    if (ub < lb) return lb;
    // Base case: To the left of lb.
    if (val <= elements[lb]) return lb;
    // Base case: To the right of ub.  This is now not needed
    // (because of the precondition and the change in the way
    // this is called), but kept for clarity's sake.
    // if (val > elements[ub]) return ub+1;
    // Determine the middle of the list (won't work for
    // really large lists, but c'est la vie).
    int mid = (lb + ub) / 2;
    // Recursive case: Left half
    if (val <= elements[mid]) 
      return findPlace(val, lb, mid);
    // Recursive case: Right half
    else
      return findPlace(val, mid+1, ub);
  } // findPlace(int,int,int)


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

  public static void main(String[] args) {
    SimpleOutput out = new SimpleOutput();
    int val;

    // If the user supplies test values, we use them.
    if (args.length != 0) {
      SortedIntList ints = new SortedIntList(args.length);
      for (int i = 0; i < args.length; ++i) {
        out.println("The array is: " + ints.toString());
        try {
          val = Integer.parseInt(args[i]);
          out.println("Adding " + val);
          ints.add(val);
        }
        catch (Exception e) { }
      } // for
      out.println("The final array is: " + ints.toString());
    } 

    // Otherwise, do some interesting testing.  See the
    // discussion of the testing of trinary search for
    // more information.
    else {
      SortedIntList ints = new SortedIntList(20);
      // For each length of list.
      for (int length = 0; length < 20; ++length) {
        // Clear the list
        ints.clear();
        // Fill in the elements 2,4,6,...,20
        for (int i = 1; i <= length; ++i) {
          ints.add(2*i);
        } // for
        // For each value between 1 and 2*length+1.
        for (val = 1; val <= 2*length+1; ++val) {
          // See if findPlace finds the right place.
          // Odd numbers i belong in (i-1)/2.  Even numbers
          // i belong in i/2-1.  Using integer division,
          // both should be (i-1)/2.
          if (ints.findPlace(val) != (val-1)/2) {
            out.println("Error placing " + val + " in " +
                        ints.toString());
            out.println("  Result is: " + ints.findPlace(val));
          }
        } // for each value
      } // for each length
    } // no command line
  } // main(String[])
} // class SortedIntList