/*
 * VectorOps.java
 *
 * Sample class methods involving vectors. 
 * Some of these will be generally useful throughout 230
 * 
 */

import java.util.Vector;
import java.util.Comparator;

public class VectorOps {
  // Utility class methods on vectors.

  //------------------------------------------------------------
  // Example accumulation idiom on vectors 

  // Concatenate the strings of all objects in v. 
  // Similar to toString, except does not introduce brackets or commas
  public static String concatStrings (Vector v) {
    StringBuffer sb = new StringBuffer(); // holds strings concatenated so far
    for (int i = 0; i < v.size(); i++) {
      // For loop invariant: sb holds string for indices [0..i-1]
      sb.append(v.get(i)); // append implicitly performs toString() on objects
    }
    // Invariant; sb holds string for indices [0..v.size-1]
    return sb.toString();
  }

  //------------------------------------------------------------
  // Examples of mapping idioms on vectors 

  // Non-destructive version of String uppercase mapper 
  // Assume v is a vector of string objects. 
  // Returns a new vector containing uppercased versions of strings in v
  public static Vector mapUpperCaseND (Vector v) {
    Vector result = new Vector(); 
    for (int i = 0; i < v.size(); i++) {
      // For loop invariant: strings at indices [0..i-1] have been uppercased.
      result.add(((String) v.get(i)).toUpperCase()); 
    }
    // Invariant: all strings in v have been uppercased.
    return result;
  }

  // Destructive version of String uppercase mapper 
  // Assume v is a vector of string objects. 
  // Replace each string by its uppercase version. 
  public static void mapUpperCaseD (Vector v) {
    for (int i = 0; i < v.size(); i++) { // Could just as well process top down
      // For loop invariant: strings at indices [0..i-1] have been uppercased.
      v.set(i, ((String) v.get(i)).toUpperCase()); // Note cast of v.get result
    }
    // Invariant: all strings in v have been uppercased.
  }

  //------------------------------------------------------------
  // Examples of filtering idioms on vectors 

  // Non-destructive version of String length filter.
  // Assume v is a vector of string objects. 
  // Returns a new vector containing (in the same relative order)
  // only those strings whose length is >= n. 
  public static Vector filterLengthND (int n, Vector v) {
    Vector result = new Vector(); 
    for (int i = 0; i < v.size(); i++) {
      // For loop invariant: strings at indices [0..i-1] have been filtered
      if (((String) v.get(i)).length() >= n) {
	result.add(v.get(i)); 
      }
    }
    // Invariant: all strings in v have been filtered
    return result;
  }

  // Destructive version of String length filter.
  // Assume v is a vector of string objects. 
  // Modifies v so it contains (in the same relative order)
  // only those strings whose length is >= n. 
  public static void filterLengthD (int n, Vector v) {
    // *CAREFUL*: perform destructive filters from top down. 
    // Will miss elements if perform from bottom up! 
    for (int i = v.size() - 1 ; i >= 0; i--) {
      // For loop invariant: strings in original vector 
      // at indices [i+1..v.size-1] have been filtered
      if (((String) v.get(i)).length() < n) {
	v.remove(i); 
     }
    }
    // Invariant: all strings in original vector have been filtered. 
  }

  //------------------------------------------------------------
  // Return a vector that is the "cartesian product" of two string vectors

  public static Vector product (Vector v1, Vector v2) {
    Vector result = new Vector();  
    for (int i = 0; i < v1.size(); i++) {
      for (int j = 0; j < v2.size(); j++) { 
	result.add(((String) v1.get(i)) + v2.get(j)); // Cast not needs on second arg. 
      }
    }
    return result; 
  }

  //------------------------------------------------------------
  // Return a vector containing all concatenations of each string
  // with following strings. 

  public static Vector concats (Vector v) {
    Vector result = new Vector();  
    for (int i = 0; i < v.size() - 1; i++) {
      for (int j = i+1; j < v.size(); j++) { 
	result.add(((String) v.get(i)) + v.get(j));
      }
    }
    return result; 
  }

  //------------------------------------------------------------
  // Insertion Sort 

  // In-place insertion sort on Vector of Comparables
  public static void isort (Vector v) {
    for (int i = 1; i < v.size(); i++) {
      // For loop invariant: elements at indices [0..i-1] are sorted via compareTo
      Comparable val = (Comparable) v.get(i); // element to insert
      int j = i; 
      // find insertion point for val by moving "hole" for val at index i downward. 
      // While loop invariant: val is less than elements at indices [j+1..i]
      while (j > 0 && val.compareTo(v.get(j-1)) < 0) { // Order of tests is crucial!
	v.set(j, v.get(j-1)); // Shift value right = shift hole left. 
	j = j - 1;
      }
      // Invariant:  
      // either (j == 0) or ((j > 1) && (val.compareTo(v.get(j-1)) >= 0))
      v.set(j, val);
    }
  }

  //------------------------------------------------------------
  // Linear search using implicit compareTo of Comparable
  
  public static int linearSearchSorted(Comparable x, Vector v) {
    // Assume v is sorted from low to high according to comp. 
    // If x is in v, returns an index at which v appears. 
    //   (There may be more than one.)
    // If x is not in v, returns the index at which x should be 
    //   inserted in v in sorted order. 
    // Use linear left-to-right search to find the index. 

    for (int i = 0; i < v.size(); i++) {
      // For loop invariant: x > all elements at indices [0..i-1]
      int compare = x.compareTo(v.get(i));
      if (compare <= 0) {
	return i;
      }
    }
    // Only reach this point if x > all elements in v
    // in which case insertion point is at end of vector. 
    return v.size(); 
  }
  
  public static int linearSearchUnsorted(Comparable x, Vector v) {
    // If x is in v, returns an index at which v appears. 
    //   (There may be more than one.)
    // If x is not in v, returns the index at which x should be 
    //   inserted in v in sorted order. 
    // Use linear left-to-right search to find the index. 

    for (int i = 0; i < v.size(); i++) {
      // For loop invariant: x != all elements at indices [0..i-1]
      int compare = x.compareTo(v.get(i));
      if (compare == 0) {
	return i;
      }
    }
    // Only reach this point if x != all elements in v
    // in which case insertion point is at end of vector. 
    return v.size(); 
  }
  
  //------------------------------------------------------------
  // Binary search using implicit compareTo of Comparables
  
  public static int binarySearch(Comparable x, Vector v) {
    // Assume v is sorted from low to high according to comp. 
    // If x is in v, returns an index at which v appears. 
    //   (There may be more than one.)
    // If x is not in v, returns the index at which x should be 
    //   inserted in v in sorted order. 
    // Use binary search to find the index. 
    return binarySearchBetween(x, v, 0, v.size()-1);
  }
  
  public static int binarySearchBetween (Comparable x, Vector v, int lo, int hi) {
    // Returns an index in the range [lo,hi] at which x could be inserted in sorted order. 		
    // Invariants:
    // * All elements at indices < lo are less than or equal to x.
    // * All elements at indices > hi are greater than or equal to x. 
    if (lo > hi) {
      // lo must be hi + 1 at this point.
      // By invariants, insertion point must be lo. 
      return lo;
    } else {
      int mid = (lo + hi) / 2;
      Object midElt = v.get(mid);
      int compare = (x.compareTo(midElt));
      if (compare == 0) {
	return mid;
      } else if (compare < 0) {
	return binarySearchBetween(x, v, lo, mid - 1);
      } else {
	return binarySearchBetween(x, v, mid + 1, hi);
      }
    }
  }

  //------------------------------------------------------------
  // fromString: 
  // Parse a string representation of a vector as a Vector of Strings.
  // A string representation of a vector is a square-bracket delimited,
  // comma-separated sequence of the string representations of the elements. 
  // * Ignores leading whitespace on elements:
  //   e.g. [foo, bar,   baz] is treated like [foo,bar,baz]
  // * Correctly handles string reps with nested brackets. 

  public static Vector fromString (String s) {
    return fromStringHelper (s, '[', ']'); 
  }

  public static Vector fromStringHelper (String s, char open, char close) {
    int last = s.length()-1; // index of last element (close bracket)
    if (s.charAt(0) != open) {
      throw new RuntimeException
	("VectorOps.fromString: string does not begin with '" + open + "': "
	 + "\"" + s + "\"");
    } else if ((s.charAt(last)) != close) {
      throw new RuntimeException
	("VectorOps.fromString: string does not end with '" + close + "': "
	 + "\"" + s + "\"");
    } else {
      Vector strings = new Vector(); // vector to hold resulting strings 
      String brackets = "[](){}"; // use string to represent set of bracket chars
      String stk = ""; // use string to represent stack of close brackets we're expecting. 
      int i = 1; // index into string s
      while (i < last) {// Go up to, but not including, terminating bracket
	// Skip initial whitespace
	while (i < last && Character.isWhitespace(s.charAt(i))) {
	  i++;
	}
	StringBuffer sb = new StringBuffer(); // buffer for next element
	while (i < last && (!stk.equals("") || s.charAt(i) != ',')) {
          // Ignores commas while have non empty bracket stack. 
	  char c = s.charAt(i); 
	  int brackind = brackets.indexOf(c); 
	  if (brackind >= 0) { // Is c a bracket? 
	    if ((brackind % 2) == 0) { // It's an open bracket
	      stk = stk + brackets.charAt(brackind + 1); // push corresponding close bracket on stack
	    } else { // It's a close bracket 
	      int stklast = stk.length() - 1; 
	      if (stklast < 0) { 
		throw new RuntimeException ("VectorOps.fromString: unmatched close bracket " + c); 
	      } else if (c == stk.charAt(stklast)) { // pop close bracket from stack
		stk = stk.substring(0,stklast);
	      } else {// Bracket mismatch
		throw new RuntimeException ("VectorOps.fromString: bracket mismatch --  "
					    + "expected: " + stk.charAt(stklast)
					    + "; got:" + c
					    );
	      }
	    }
          }
	  sb.append(s.charAt(i)); 
	  i++;
	}
	// Done reading this element; put it in strings
	strings.add(sb.toString());
	i++; // go to next char after comma/bracket
      }
      return strings; // return vector of strings
    }
  }

  //------------------------------------------------------------
  // Testing

  // Need to add tests for searches. 
  public static void main (String [] args) {
    if (args.length == 2 && args[0].equals("fromString")) {
      Vector v = fromString(args[1]);
      System.out.println("Vector with " + v.size() + " elements:\n" + v); 
    } else if (args.length == 2 && args[0].equals("concatStrings")) {
      System.out.println(concatStrings(fromString(args[1])));
    } else if (args.length == 2 && args[0].equals("mapUpperCaseND")) {
      System.out.println(mapUpperCaseND(fromString(args[1])));
    } else if (args.length == 2 && args[0].equals("mapUpperCaseD")) {
      Vector v = fromString(args[1]);
      mapUpperCaseD(v); 
      System.out.println(v); 
    } else if (args.length == 3 && args[0].equals("filterLengthND")) {
      int n = Integer.parseInt(args[1]);
      System.out.println(filterLengthND(n, fromString(args[2])));
    } else if (args.length == 3 && args[0].equals("filterLengthD")) {
      int n = Integer.parseInt(args[1]);
      Vector v = fromString(args[2]);
      filterLengthD(n, v); 
      System.out.println(v); 
    } else if (args.length == 3 && args[0].equals("product")) {
      System.out.println(product(fromString(args[1]), fromString(args[2])));
    } else if (args.length == 2 && args[0].equals("concats")) {
      System.out.println(concats(fromString(args[1])));
    } else if (args.length == 2 && args[0].equals("isort")) {
      Vector v = fromString(args[1]);
      isort(v); 
      System.out.println(v);
    } else if (args.length == 3 && args[0].equals("linearSearchSorted")) {
      System.out.println(linearSearchSorted(args[1],fromString(args[2]))); 
    } else if (args.length == 3 && args[0].equals("linearSearchUnsorted")) {
      System.out.println(linearSearchUnsorted(args[1],fromString(args[2]))); 
    } else if (args.length == 3 && args[0].equals("binarySearch")) {
      System.out.println(binarySearch(args[1],fromString(args[2]))); 
    } else {
      System.out.println("Unrecognized main option"); 
    }
  }
  
}