/** RunTime provides some methods for solving problems from Assignment 8
 */
import java.util.Vector;
public class RunTime {

  /* in all the following tallies, n is the size of the problem,
   * (Vector, array, or whatever.  Also, the code illustrates
   * the required algorithms, but no promise of correctness
   * is implied.
   */

  /** Question 1:
   *  Shift: move each element of String[] names up one position
   *  and move last element to position 0.
   */
  public void Shift(String[] names) {
    // single comparison
    if (names.length > 1) { // nothing to do, otherwise
      // single assignment
      String lastName= names[names.length - 1];
      // for loop makes n-1 assignments and n comparisons
      for (int k= names.length - 1; k != 0; k--) {
	names[k]= names[k - 1]; // shift a name up
      }
      // single assignment
      names[0]= lastName; // the last shall be first, or whatever
    }
    // tally: for loop has n comparisons, n-1 assignments, for 2n-1
    //        Plus 2 assignments and a comparison, for a total
    //        of 2n + 2.  Disregard the constant 2 and coefficient
    //        2, and the runtime is O(n)
  }

  /** Question 2:
   *  findMin: return the minimum value from an unsorted list of
   *  integers
   */
  public void findMin(int[] list) {
    // single comparison
    if (list.length > 0) {
      // single assignment
      int min= list[0];
      // n comparisons, plus n-1 comparisons inside loop
      for (int k= 1; k != list.length; k++) {
	if (list[k] < min) {min= list[k];}
      }
      System.out.println("Minimum is: " + min);
    }
    else {
      System.out.println("No minimum of an empty list.");
    }
    // tally: 2n-1 comparisons in the for loop, plus an extra
    //        comparison and assignment, for 2n+1 operations
    //        Disregard constant 1 and coefficient 2, and say
    //        this is O(n) runtime
  }

  /** Question 3:
   *  printLast: print the last value of Vector list
   */
  public void printLast(Vector list) {
    // single comparison
    if (list.size() > 0) { // otherwise nothing to do
      System.out.println(list.elementAt(list.size() - 1));
    }
    else { // nothing to print
      System.out.println("Nothing to print...");
    }
    // tally: Constant time to check whether there is a last
    //        element to print, and then print it, so O(1) runtime
  }

  /** Question 4:
   *  findMode: return the value that occurs the most often on a list
   */
  public int findMode(int[] list) {
    // First stage is to create a vector containing values
    // and their frequencies
    //
    // single declaration and instantiation
    Vector vect= new Vector();
    // single declaration
    int index;
    // n comparisons in for loop declaration
    for (int i=0; i != list.length; i++) {
      // search takes log(k), where k == v.size()
      index= binarySearch(vect, list[i]);
      // two comparisons, plus one insertion.  We don't know from
      // the API how "add" is implement, so we make the assumption
      // that it constitutes an operation!!
      if (index >= 0 &&
	  (((IntegerFrequency)vect.elementAt(index)).getValue() == list[i])) {
	((IntegerFrequency)vect.elementAt(index)).incrementFrequency();
	}
      else { //
	  vect.add(index + 1, new IntegerFrequency(list[i]));
      }
    }
    // now vect contains values with their frequencies
    // two declarations and initializations
    int maxIndex= -1; // index of maximum frequency
    int maxFrequency= 0; // an impossible frequency
    // loop interates a maximum of n times
    // and the body has one comparison and two assignments
    for (int k= 0; k != vect.size(); k++) {
      if (((IntegerFrequency)vect.elementAt(k)).getFrequency() >
	  maxFrequency) {
	maxIndex= k;
	maxFrequency= ((IntegerFrequency)vect.elementAt(k)).
	  getFrequency();
      }
    }
    // single statement
    return ((IntegerFrequency)vect.elementAt(maxIndex)).getValue();
    // tally: for loop over i iterates n times, and does a maximum
    //        of log(n) work to search, and then a constant amount
    //        of work to either insert an element or update its
    //        frequency.
    //        for loop over k iterates a maximum of n times, makes
    //        a single comparison and a maximum of two assignments.
    //        In total n*log(n) plus 3*n, or O(n*log(n)) run time
  }

  /** binarySearch: return the position of the last element of list
   *  <= value, -1 if there are none.
   *  Assume each element of Vector is an IntegerFrequency object (defined
   *  in this directory).
   */
  public int binarySearch(Vector list, int value) {
    int i= - 1; int j= list.size();
    // list[0..i] <= s && list[j..list.size()-1] > value
    //      && -1 <= i < j <= list.size()
    while(i != j - 1) {
      int m= (i+j)/2;
      if(((IntegerFrequency)list.elementAt(m)).getValue() <= value) {
	i= m;
      }
      else {
	j= m;
      }
    }
    return i;
  }
      
  /** Question 5:
   *  findThreePower: return the number of  time n is divisible by 3
   */
  public int findThreePower(int n) {
    // single declaration
    int threeCount;
    // for loop has floor(log(n)) + 1 comparisons and
    // floor(log(n)) assignments
    for (threeCount= 0; n != 0; threeCount++) {
      n= n/3;
    }
    return threeCount;
    // tally: the for loop generates 2*floor(log(n)) operations,
    //        plus 2 operations, so conclude O(log(n)) operations
    //        Note: the log is to base 3 here.
  }

  /** Question 6:
   *  copyHalf: copy the first half of Vector list to a new Vector,
   *  and return it
   */
  public Vector copyHalf(Vector list) {
    // single declaration and instantiation
    Vector newList= new Vector();
    // single comparison 
    if (list.size()/2 > 0) { // otherwise do nothing
      // n/2 + 1 comparisons, n/2 assignments
      for (int i= 0; i != list.size()/2; i++) {
	newList.addElement(list.elementAt(i));
      }
    }
    return newList;
    // tally:  for loop generates n + 1 operations
    //         plus two more, gives n + 3, or
    //         O(n) run time
  }

}