import java.util.Random;

/**
 * Sequences of integers that support various algorithms.
 *
 * @author Samuel A. Rebelsky
 * @version 1.2 of January 1999
 */
public class IntSeq {

  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+
 
  /**
   * The elements in the sequence (plus some spare spaces
   * so that we can easily add more elements).
   */
  protected int[] elements;

  /**
   * The number of steps used in the most-recently-executed
   * algorithm.  Will be used in the laboratory on algorithm
   * analysis.
   */
  protected int steps;


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

  /**
   * Get the value of the ith element of the sequence.
   * Returns the value of the ith element.  If a negative
   * index is given, return 0.
   */
  public int get(int i) {
    // Check for negative indices
    if (i < 0) {
      return 0;
    } // negative index
    // Check for indices outside the range of the array
    else if ((this.elements == null) || (i >= this.elements.length)) {
      return 0;
    } // really large index
    // Everything else
    else {
      return this.elements[i];
    } // everything else
  } // get(int)

  /**
   * Set the value of the ith element of the sequence.  
   * Returns the old ith element.   If a negative index
   * is given, does not affect the sequence and returns 0.
   */
  public int set(int i, int val) {
    // Check for negative indices
    if (i < 0) {
      return 0;
    }
    // Make sure the array is big enough
    verifyCapacity(i+1);
    // Get the old value
    int old = elements[i];
    // Fill in the new value
    elements[i] = val;
    // Return the old value
    return old;
  } // set(int,int)
    
  /**
   * Get the ``length'' of the sequence.  In general, this is one
   * higher than the index of the highest element accessed.
   */
  public int length() {
    if (this.elements == null) {
      return 0;
    }
    else {
      return this.elements.length;
    } 
  } // length()
  
  /**
   * Convert the sequence to a string.
   */
  public String toString() {
    // Handle empty sequences
    if (this.elements.length == 0) {
      return "[]";
    }
    // Handle nonempty sequences
    else {
      int i;      // A counter
      String str; // The string we generate
      str = "[" + this.elements[0];
      for (i = 1; i < this.elements.length; ++i) {
        str = str + "," + this.elements[i];
      } // for
      str = str + "]";;
      return str;
    } // nonempty sequence
  } // toString()
  
  /**
   * Swap the values at positions i and j.
   */
  public void swap(int i, int j) {
    int tmp;  // A temporary value used in swapping
    // Make sure there are sufficiently many elements
    verifyCapacity(j+1);
    // Swap by copying
    tmp = this.elements[i];
    this.elements[i] = this.elements[j];
    this.elements[j] = tmp;
  } // swap(int,int)


  // +------------------+----------------------------------------
  // | Fill in elements |
  // +------------------+

  /**
   * Fill the subsequence [lb .. ub] with the sequence of elements
   * starting with one value and incrementing by inc at every step.  For
   * example, fill(2,5,3,4) puts 3 in position 2, 7 in position 3,
   * 11 in position 4, and 15 in position 5.
   */
  public void fill(int lb, int ub, int start, int inc) {
    int current; // The current value being inserted
    int i;       // A counter
    // Make sure the array is big enough
    verifyCapacity(ub+1);
    // Set the initial value
    current = start;
    // Fill in the values
    for (i = lb; i <= ub; ++i) {
      this.elements[i] = current;
      current += inc;
    } // for
  } // fill(int,int,int,int)
  
  /**
   * Fill the first n elements of a sequence with n random elements.
   */
  public void randomFill(int n) {
    randomFill(0, n-1, 0);
  } // randomFill(int)
  
  /**
   * Fill the subsequence [lb .. ub] with the kth sequence
   * of ``random'' elements.  If k is 0, use an unspecified sequence
   * of ``random'' elements.
   */
  public void randomFill(int lb, int ub, int k) {
    int i;      // Counter variable
    Random gen; // A random sequence generator
    // Set up the random sequence generator
    if (k == 0) {
      gen = new Random();
    }
    else {
      gen = new Random(k);
    }
    // Make sure the array has sufficient capacity
    verifyCapacity(ub+1);
    // Fill it with random elements
    for (i = lb; i <= ub; ++i) {
      this.elements[i] = gen.nextInt();
    } // for
  } // randomFill(int,int,int)
  
  /**
   * Fill the first n elements of the sequence with a ``random''
   * increasing sequence.
   */
  public void randomFillIncreasing(int n) {
    randomFillIncreasing(0, n-1, 0);
  } // randomFillIncreasing(int)
  
  /**
   * Fill the subsequence [lb .. ub] with the kth sequence of
   * ``random'' increasing elements.  If k is 0, use an unspecified
   * squence of ``random'  elements.
   */
  public void randomFillIncreasing(int lb, int ub, int k) {
    int i;      // Counter variable
    Random gen; // A random sequence generator
    int bias;	// For biasing the sequence so that it does not
                // increase too quickly. 
    // Sanity check.  Make sure the sequence is nonempty.
    if (ub < lb) return;
    // Set up the random sequence generator.
    if (k == 0) {
      gen = new Random();
    }
    else {
      gen = new Random(k);
    }
    // Make sure the array has sufficient capacity.
    verifyCapacity(ub+1);
    // Put in the first element.
    this.elements[lb] = gen.nextInt();
    // Fill it with random elements.  We compute a number between
    // the previous number and Integer.MAX_VALUE (although not with
    // equal probability).
    for (i = lb+1; i <= ub; ++i) {
      // If the previous number is not positive, we simply add some
      // positive number.
      if (this.elements[i-1] < 0) {
        this.elements[i] = this.elements[i-1] + Math.abs(gen.nextInt());
      }
      // If the previous number is positive, we find a number between
      // previous and (previous+Integer.MAX_VALUE/elements_remaining).  
      // This helps prevent the sequence from becoming top-heavy
      else {
        // The number of possible values remaining, divided by the
        // number of elements we have eft to fill in.
        bias = (Integer.MAX_VALUE - this.elements[i-1])/(1+ub-i);
        this.elements[i] = this.elements[i-1]+
                           (Math.abs(gen.nextInt()) % bias);
      } // if the number is positive.
    } // for
  } // fillRandomIncreasing(int,int,int)
  

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

  /**
   * Search through a sorted array of integers for a particular value.
   * Return the index of the value if it is found.
   * Return -1 otherwise.
   */
  public int binarySearch(int val) {
    return binarySearch(val, 0, this.elements.length-1);
  } // binarySearch(int)

  /**
   * Search for a value in  a subarray of a sorted array of integers.
   * The subarray is given by lb .. ub.
   * Return the index of the value if it is found.
   * Return -1 otherwise.
   */
  protected int binarySearch(int val, int lb, int ub) {
    // Compute the index of the middle value.
    int mid = (lb + ub) / 2;
    // Is the subarray empty?
    if (lb > ub) {
      return -1;
    } // empty subarray
    // Is the value at the middle?
    else if (val == this.elements[mid]) {
      return mid;
    } // Found it!
    // Should the value be in the left half?
    else if (val < this.elements[mid]) {
      return binarySearch(val, lb, mid-1);
    } // left half
    // The value must be in the right half.
    else {
      return binarySearch(val, mid+1, ub);
    } // right half
  } // binarySearch(int, int, int)

  /**
   * Search through an array of integers for a particular value.
   * Return the index of the value if it is found.
   * Return -1 otherwise.
   */
  public int sequentialSearch(int val) {
    int i; // An index into the sequence.
    // Check each position of the sequence.
    for (i = 0; i < this.elements.length; ++i) {
       // If the value is at position i, we're done.
      if (this.elements[i] == val) {
        return i;
      } // if
    } // for
    // Unable to find the element.  Return -1.
    return -1;
  } // sequentialSearch(int).


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

  /** 
   * Compute the index of the smallest element in the subsequence
   * given by lower bound lb and upper bound ub.  The subsequence
   * [lb .. ub] must be nonempty.
   */
  public int indexOfSmallest(int lb, int ub) {
    // Make sure there are elements in the sequence
    if (this.elements == null) {
      return Integer.MIN_VALUE;
    }
    // Make sure the upper bound and lower bound are reasonable.
    if (lb < 0) {
       lb = 0;
    }
    if (ub >= this.elements.length) {
       ub = this.elements.length - 1;
    }
    // Our guess as to the index of the smallest element
    int guess = lb;
    // A counter variable
    int i;
    // Look through all subsequent elements
    for (i = lb + 1; i <= ub; ++i) {
      // If the element is smaller than our guess, then
      //   update the guess
      if (this.elements[i] < this.elements[guess]) {
        guess = i;
      } // if
    } // for
    // That's it, we're done
    return guess;
  } // indexOfSmallest(int)

  /** 
   * Compute the smallest element in the sequence.  The sequence
   * must be nonempty.
   */
  public int smallest() {
    // Our guess as to the smallest element
    int guess = this.elements[0];
    // A counter variable
    int i;
    // Look through all subsequent elements
    for (i = 1; i < this.elements.length; ++i) {
      // If the element is smaller than our guess, then
      //   update the guess
      if (this.elements[i] < guess) {
        guess = this.elements[i];
      } // if
    } // for
    // That's it, we're done
    return guess;
  } // smallest()

  /**
   * Put the two smallest elements of the sequence at the beginning
   * of the sequence.  The sequence must have at least two elements.
   */
  public void twoSmallest() {
    // Swap the initial element with the smallest
    swap(0, indexOfSmallest(0,this.length()-1));
    // Swap the next element with the smallest remaining
    swap(1, indexOfSmallest(1,this.length()-1));
  } // twoSmallest()
  
  /**
   * Put the five smallest elements of the array at the beginning of
   * the array (naive method).  The sequence should have at least
   * five elements.
   */
  public void fiveSmallest() {
    // For each index i from 0 to 4, swap the smallest element in
    // [i .. last] with the ith element.
    int i;
    for (i = 0; i < 5; ++i) {
      swap(i, indexOfSmallest(i, this.length()-1));
    } // for
  } // fiveSmallest()
  
  /**
   * Put the five smallest elements of the array at the beginning of
   * the array (better method).  The sequence should have at least
   * five elements.
   */
  public void newFiveSmallest() {
    int i; // Everybody's favorite counter variable
    // Put the first five elements in order using the naive method
    for (i = 0; i < 4; ++i) {
      swap(i, indexOfSmallest(i, 4));
    } // for
    // For each remaining element, if it belongs in the first five
    // (or, more precisely, our estimate of the first five), then
    // put it in the correct place in that sorted sublist.
    for (i = 5; i < this.length(); ++i) {
      // Does the remaining element belong in our guess about the
      // first five elements?
      if (this.elements[i] < this.elements[4]) {
        // If so, put it at the end of that group
        swap(4, i);
        // And then move it to the right place in that group
        insertLast(0,4);
      } // if the ith element belongs in our current guess
    } // for
  } // newFiveSmallest()
  
  
  // +----------------+------------------------------------------
  // | Helper Methods |
  // +----------------+

  /**
   * Insert the last element in the subrange [lb .. ub] into the
   * appropriate place in [lb .. ub], assuming that the subrange
   * [lb .. ub-1] is arranged in increasing order.
   */
  protected void insertLast(int lb, int ub) {
    int i; // A counter variable
    // Start at the upper end of the range
    i = ub;
    // As long as the ith element is out of order,
    while ((i > 0) && (this.elements[i] < this.elements[i-1])) {
      // Swap the two out-of-order elements
      swap(i,i-1);
      // Move back one element
      i = i - 1;
    } // while
  } // insertLast(int,int)
  
  /**
   * Increase the capacity of the elements array.
   */
  protected void verifyCapacity(int newcap) {
    // Special case: empty array
    if (this.elements == null) {
      // Create an appropriate sized array
      this.elements = new int[newcap];
      // Fill it with sufficiently many 0 elements
      int i;
      for (i = 0; i < this.elements.length; ++i) {
        this.elements[i] = 0;
      } // for
    } // if the array is empty
    // Normal case: too few elements
    else if (this.elements.length < newcap) {
      // Build a new array of the appropriate size
      int[] new_elements = new int[newcap];
      // Set up a counter
      int j;
      // Copy the existing elements
      for (j = 0; j < this.elements.length; ++j) {
        new_elements[j] = this.elements[j];
      } // for
      // Use 0 for the remaining elements
      for (j = this.elements.length; j < new_elements.length; ++j) {
        new_elements[j] = 0;
      } // for
      // And update elements
      this.elements = new_elements;
    } // if we need to increase the capacity
  } // verifyCapacity(int)


  // +-----------------+-----------------------------------------
  // | Computing Steps |
  // +-----------------+
 
  /**
   * Reset the count of steps to 0.
   */
  public void resetCounter() {
    steps = 0;
  } // resetCounter()

  /**
   * Determine the number of steps used since the last call to
   * resetCounter().
   */
  public int getSteps() {
    return steps;
  } // getSteps()

} // class IntSeq