/* RecursiveAssignment.java
   requires java2 or higher */
   
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Vector;

/**
 * This class explores various recursive methods, as well as their iterative
 * counterparts.
 *
 * @author  Zach Tomaszewski
 * @version 1.0  16 Sept 2001
 *
 */
public class RecursiveAssignment {

  public static void main(String[] args) {
    int menuChoice = 9;
    StringBuffer bufferedString;
    StringTokenizer tokenedString;
    int[] arrayToSearch;
    int counter = 0;
    int answer, itemToFind, kSmallest;

    try{
      /* a rather obscene use of the main method, but what better place
      to test the methods of that class? */

      while (menuChoice != 0) {

      System.out.println("\n1. Recursive writeBackwards");
      System.out.println("2. Iterative writeBackwards");
      System.out.println("3. Recursive power");
      System.out.println("4. Iterative power");
      System.out.println("5. Recursive binarySearch");
      System.out.println("6. Iterative binarySearch");
      System.out.println("7. Recursive kthSmallest");
      System.out.println("8. Iterative kthSmallest");
      System.out.println("0. QUIT");
      System.out.print("CHOOSE A METHOD TO TEST: ");

      BufferedReader stdin = new BufferedReader(
                                new InputStreamReader(System.in));

      menuChoice = Integer.parseInt(stdin.readLine());

      switch (menuChoice) {
        case 1:
           System.out.print("\nEnter a string to reverse: ");
           bufferedString = new StringBuffer(stdin.readLine());
           writeBackwards(bufferedString);           
           break;
        case 2:
           System.out.print("\nEnter a string to reverse: ");
           bufferedString = new StringBuffer(stdin.readLine());
           iterativeWriteBackwards(bufferedString);           
           break;
        case 3:
           try{
             System.out.print("\nEnter a base number to raise: ");
             int base = Integer.parseInt(stdin.readLine());
             System.out.print("Enter an exponent: ");
             int exponent = Integer.parseInt(stdin.readLine());
             System.out.println("Answer: " + power(base, exponent));
           }catch (NumberFormatException nfe) {
             System.out.println("Invalid numerical input.");
           }catch (InvalidInputException iie) {
             System.out.println("This method does not accept"
                                + " negative exponents.");
           }  
           break;
        case 4:
           try{
             System.out.print("\nEnter a base number to raise: ");
             int base = Integer.parseInt(stdin.readLine());
             System.out.print("Enter an exponent: ");
             int exponent = Integer.parseInt(stdin.readLine());
             System.out.println("Answer: " + iterativePower(base, exponent));
           }catch (NumberFormatException nfe) {
             System.out.println("Invalid numerical input.");
           }catch (InvalidInputException iie) {
             System.out.println("This method does not accept"
                                + " negative exponents.");
           }  
           break;
        case 5:
           try{
             System.out.print("\nEnter an ORDERED sequence of numbers: ");
             tokenedString = new StringTokenizer(stdin.readLine(), " ,");
             arrayToSearch = new int[tokenedString.countTokens()];
             counter = 0;
             while (tokenedString.hasMoreTokens()){
               arrayToSearch[counter] =
                   Integer.parseInt(tokenedString.nextToken());
               counter++;
             }
             System.out.print("Enter an integer to search for: ");
             itemToFind = Integer.parseInt(stdin.readLine());
             answer = binarySearch(arrayToSearch, itemToFind);
             if (answer >= 0) {
               System.out.println("The integer is found at index "
                                  + answer + " in the array.");
             }else {
               System.out.println("The integer was not found in the array.");
             }
           }catch (NumberFormatException nfe) {
             System.out.println("Invalid numerical input.");  
           }
           break;
        case 6:
           try{
             System.out.print("\nEnter an ORDERED sequence of numbers: ");
             tokenedString = new StringTokenizer(stdin.readLine(), " ,");
             arrayToSearch = new int[tokenedString.countTokens()];
             counter = 0;
             while (tokenedString.hasMoreTokens()){
               arrayToSearch[counter] =
                   Integer.parseInt(tokenedString.nextToken());
               counter++;
             }
             System.out.print("Enter an integer to search for: ");
             itemToFind = Integer.parseInt(stdin.readLine());
             answer = iterativeBinarySearch(arrayToSearch, itemToFind);
             if (answer >= 0) {
               System.out.println("The integer is found at index "
                                  + answer + " in the array.");
             }else {
               System.out.println("The integer was not found in the array.");
             }
           }catch (NumberFormatException nfe) {
             System.out.println("Invalid numerical input.");
           }  
           break;
        case 7:
           try{
             System.out.print("\nEnter an sequence of numbers: ");
             tokenedString = new StringTokenizer(stdin.readLine(), " ,");
             arrayToSearch = new int[tokenedString.countTokens()];
             counter = 0;
             while (tokenedString.hasMoreTokens()){
               arrayToSearch[counter] =
                   Integer.parseInt(tokenedString.nextToken());
               counter++;
             }
             System.out.print("Enter the kth smallest number to search for: ");
             kSmallest = Integer.parseInt(stdin.readLine());
             answer = kthSmallest(arrayToSearch, kSmallest);
             System.out.println("The integer " + answer + " is the "
                                  + kSmallest + "th smallest in the array.");
           }catch (NumberFormatException nfe) {
             System.out.println("Invalid numerical input.");
           }catch (InvalidInputException iie) {
             System.out.println("Results could not be computed " +
                                "due to flawed input.");
           }
           break;
        case 8:
           try{
             System.out.print("\nEnter an sequence of numbers: ");
             tokenedString = new StringTokenizer(stdin.readLine(), " ,");
             arrayToSearch = new int[tokenedString.countTokens()];
             counter = 0;
             while (tokenedString.hasMoreTokens()){
               arrayToSearch[counter] =
                   Integer.parseInt(tokenedString.nextToken());
               counter++;
             }
             System.out.print("Enter the kth smallest number to search for: ");
             kSmallest = Integer.parseInt(stdin.readLine());
             answer = iterativeKthSmallest(arrayToSearch, kSmallest);
             System.out.println("The integer " + answer + " is the "
                                  + kSmallest + "th smallest in the array.");
           }catch (NumberFormatException nfe) {
             System.out.println("Invalid numerical input.");
           }catch (InvalidInputException iie) {
             System.out.println("Results could not be computed " +
                                "due to flawed input.");
           }
           break;
        default: menuChoice = 0;
      }//end switch

      }//end while
    }catch (IOException e) {
      System.out.println("I/O error!");
    }catch (NumberFormatException nfe) {
      System.out.println("Invalid menu choice.  Exiting...");
    }  
  }


  /**
   * Recursively reverses the given string and prints it to the screen.
   *
   * @param sb A StringBuffer to be reversed.
   */
  public static void writeBackwards (StringBuffer sb){
    if (sb.length() == 0) {
       return;        
    }else if (sb.length() == 1) {
       System.out.println(sb.toString());
       return;
    }else {
       System.out.print(sb.charAt(sb.length() - 1));
       sb.deleteCharAt(sb.length() - 1);
       RecursiveAssignment.writeBackwards(sb);
    }
  }


  /**
   * Iteratively reverses the given string and prints it to the screen.
   *
   * @param sb A StringBuffer to be reversed.
   */
  public static void iterativeWriteBackwards (StringBuffer sb){
    for (int i = sb.length()-1; i >= 0; i--) {
       System.out.print(sb.charAt(i));
    }
    System.out.println();     /* to end the line */
  }


  /**
   * Recursively computes the result of the
   * first number to the power of the positive second;
   * prints the result to the screen.
   *
   * @param base  The integer to be exponentially multiplied. 
   * @param exponent  The exponent to multiply by; must be zero or greater. 
   * @return result   The long result of this function.
   * @throws InvalidInputException when a negative exponent is submitted.
   */
  public static long power (int base, int exponent) throws
                                                 InvalidInputException{
    long result = 1;

    if (exponent < 0) {
      throw new InvalidInputException("Negative exponent.");
    }else if (exponent == 0) {
      return 1;
    }else {
      return (base * RecursiveAssignment.power(base, --exponent));
    }
  }


  /**
   * Iteratively computes the result of the
   * first number to the power of the second;
   * prints the result to the screen.
   *
   * @param base   The integer to be exponentially multiplied. 
   * @param exponent   The exponent to multiply by; must be zero or greater.
   * @return    A long containing the result
   * @throws  InvalidInputException when a negative exponent is submitted.
   */
  public static long iterativePower (int base, int exponent) throws
                                                 InvalidInputException{

    long result = 1;

    if (exponent < 0) {
       throw new InvalidInputException("Negative exponent.");
    }else if (exponent == 0) {
       return 1;
    }
    while (exponent > 0) {
      result *= base;
      exponent--;
    }
    return result;
  }


 /**
  * Performs a binary search through the passed, ordered int[] array
  * looking for the passed integer.  Returns the index of the
  * found integer, or else -1 (NOTFOUND) if the integer is not in
  * the array.  This version assumes that the whole array should be searched.
  *
  * @param arrayToSearch  The int[] array to search through;
  *                  must be ordred from least to greatest.
  * @param itemToFind    The int to look for in the array
  * @return        Index of found integer, or -1 if not found
  */
  public static int binarySearch (int[] arrayToSearch, int itemToFind) {
      return RecursiveAssignment.binarySearch(arrayToSearch, itemToFind, 
                                        0, arrayToSearch.length - 1);
  }
 

 /**
  * Performs a recursive binary search through the passed, ordered int[]
  * array looking for the passed integer.  Returns the index of the
  * found integer, or else -1 (NOTFOUND) if the integer is not in
  * the array. This version of the method will search only that part
  * of the array delimited by the "first" and "last" parameters.
  *
  * @param arrayToSearch  The int[] array to search through;
  *                  must be ordred from least to greatest.
  * @param itemToFind    The int to look for in the array
  * @param first         The array index to start searching at
  * @param last          The array index to end searching at
  * @return        Index of found integer, or -1 if not found
  */
  public static int binarySearch(int[] arrayToSearch, int itemToFind,
                                int first, int last){
     int NOTFOUND = -1;
     int midpoint = (last + first)/2;
 
     if (first > last) {   /* array size == 0 */ 
       return NOTFOUND; 
     }else if (first == last) {   /* array size == 1 */ 
       if (arrayToSearch[midpoint] == itemToFind) { 
         return midpoint;          
       }else { 
         return NOTFOUND; 
       }
     }else {
       if (arrayToSearch[midpoint] == itemToFind) {
          return midpoint; 
       }else if (arrayToSearch[midpoint] > itemToFind) { 
          last = midpoint - 1;    /* take lower half of array */ 
          return RecursiveAssignment.binarySearch(arrayToSearch, itemToFind, 
                                            first, last); 
       }else if (arrayToSearch[midpoint] < itemToFind) { 
           first = midpoint + 1; 
           return RecursiveAssignment.binarySearch(arrayToSearch, itemToFind,
                                                     first, last);
       }else { //should never be needed, but needed to compile
          return NOTFOUND;
       }
     }
  }


 /**
  * Performs a binary search through the passed, ordered int[] array
  * looking for the passed integer.  Returns the index of the
  * found integer, or else -1 (NOTFOUND) if the integer is not in
  * the array.  This version assumes that the whole array should be searched.
  *
  * @param arrayToSearch  The int[] array to search through;
  *                      must be ordred from least to greatest.
  * @param itemToFind    The int to look for in the array
  * @return        Index of found integer, or -1 if not found
  */
  public static int iterativeBinarySearch (int[] arrayToSearch,
                                           int itemToFind) {
      return RecursiveAssignment.binarySearch(arrayToSearch, itemToFind, 
                                        0, arrayToSearch.length - 1);
  }


 /**
  * Performs an iterative binary search through the passed, ordered int[]
  * array looking for the passed integer.  Returns the index of the
  * found integer, or else -1 (NOTFOUND) if the integer is not in
  * the array. This version of the method will search only that part
  * of the array delimited by the "first" and "last" parameters.
  *
  * @param arrayToSearch  The int[] array to search through;
  *                      must be ordred from least to greatest.
  * @param itemToFind    The int to look for in the array
  * @param first         The array index to start searching at
  * @param last          The array index to end searching at
  * @return        Index of found integer, or -1 if not found
  */
  public static int iterativeBinarySearch (int[] arrayToSearch,
                               int itemToFind, int first, int last) { 
     int NOTFOUND = -1; 
     int midpoint = (last + first)/2; 
 
     while (last > first) { 
       if (arrayToSearch[midpoint] == itemToFind) { 
          break; 
       }else if (arrayToSearch[midpoint] > itemToFind) { 
          last = midpoint - 1;    /* take lower half of array */ 
          continue;  
       }else if (arrayToSearch[midpoint] < itemToFind) { 
          first = midpoint + 1; 
          continue; 
       } 
     } 
       
     if (arrayToSearch[midpoint] == itemToFind) { 
         return midpoint;           
     }else { 
         return NOTFOUND; 
     } 
  } 


 /**
  * Searches the submitted array for the kth smallest integer therein,
  * where k is itself a positive integer.  For example, the 3rd smallest
  * integer (k=3) of the array {1,3,10,7} would be 7.  Arrays do not need
  * to be sorted.
  *
  * @param arrayToSearch  The int[] to search
  * @param kSmallest      The position to find
  * @return               The kth smallest integer in the passed array
  * @throws InvalidInputException  when k is not computable with
  *                        the passed array.
  */
  public static int kthSmallest (int[] arrayToSearch, int kSmallest)
                                          throws InvalidInputException {
     Vector vectorToSearch = new Vector(arrayToSearch.length);
     for (int i = 0; i < arrayToSearch.length; i++) {
       vectorToSearch.addElement(new Integer(arrayToSearch[i]));
     }
     return kthSmallest(vectorToSearch, kSmallest);
  }


 /**
  * Searches the submitted vector of Integer objects for the kth smallest
  * integer therein, where k is itself a positive integer.  For example,
  * the 3rd smallest integer (k=3) of the array {1,3,10,7} would be 7.
  * The vector does not need to be previously sorted.
  *
  * @param vectorToSearch  The vector of Intger objects to search
  * @param kSmallest      The position to find
  * @return               The kth smallest integer in the passed array
  * @throws InvalidInputException  when k is not computable with
  *                        the passed vector.
  */
  public static int kthSmallest (Vector vectorToSearch, int kSmallest)
                                          throws InvalidInputException {
     int midrange = 0; //number of items that duplicate pivot value
     Integer intObject;
     int pivot, currentInt;

     if (kSmallest <= 0 || vectorToSearch.size() < kSmallest) {
        throw new InvalidInputException("k is <= 0 or exceeds the number" 
                                        + " of elements in array.");
     }else if (vectorToSearch.size() == 1) {
        //from above, kSmallest must equal 1 here
        intObject = (Integer) vectorToSearch.elementAt(0);
        return intObject.intValue();
     }else if (vectorToSearch.size() == 0) {
        throw new InvalidInputException("Cannot search an empty array.");
     }

     int pivotIndex = vectorToSearch.size() / 2; //pick a pivot number
     intObject = (Integer) vectorToSearch.elementAt(pivotIndex);
     pivot = intObject.intValue();
     vectorToSearch.add(0, vectorToSearch.remove(pivotIndex));
     pivotIndex = 0;

     for(int i=1; i < vectorToSearch.size(); i++) {
       intObject = (Integer) vectorToSearch.elementAt(i);
       currentInt = intObject.intValue();
       if (currentInt < pivot) {
         vectorToSearch.add(0, vectorToSearch.remove(i));
         pivotIndex++;
       }else if (currentInt > pivot) {
         //don't move bigger items, let them get pushed along
       }else {                            //then i == pivot duplicate
         vectorToSearch.add(pivotIndex + 1, vectorToSearch.remove(i));
         midrange++;
       }
     }

     /* remember that pivotIndex is an index, while kSmallest is a count */
     /* Hence, pivotCount */
     int pivotCount = pivotIndex + 1;
     if (pivotCount <= kSmallest && kSmallest <= pivotCount + midrange){
          //kSmallest is somewhere in the range of duplicate pivot values
          intObject = (Integer) vectorToSearch.elementAt(pivotIndex);
          return intObject.intValue();
     }else if (pivotCount + midrange < kSmallest) { 
        for (int i = 0; i<= pivotIndex + midrange; i++) {
           vectorToSearch.remove(0);
        }
        return kthSmallest(vectorToSearch,
                            (kSmallest - (pivotCount + midrange)));
     }else if (pivotCount > kSmallest) {
        int i = 0;
        while(pivotIndex <= vectorToSearch.size() - 1) {
           vectorToSearch.remove(vectorToSearch.size() - 1);
        }
        return kthSmallest(vectorToSearch, kSmallest);
     }else{
        throw new InvalidInputException();  //should never happen
     }
  
  }


 /**
  * Searches the submitted array for the kth smallest integer therein,
  * where k is itself a positive integer.  For example, the 3rd smallest
  * integer (k=3) of the array {1,3,10,7} would be 7.  Arrays do not need
  * to be sorted.
  *
  * @param arrayToSearch  The int[] to search
  * @param kSmallest      The position to find
  * @return               The kth smallest integer in the passed array
  * @throws InvalidInputException  when k is not computable with
  *                        the passed array.
  */
  public static int iterativeKthSmallest (int[] arrayToSearch, int kSmallest)
                                          throws InvalidInputException {
     Vector vectorToSearch = new Vector(arrayToSearch.length);
     for (int i = 0; i < arrayToSearch.length; i++) {
       vectorToSearch.addElement(new Integer(arrayToSearch[i]));
     }
     return iterativeKthSmallest(vectorToSearch, kSmallest);
  }


 /**
  * Searches the submitted vector of Integer objects for the kth smallest
  * integer therein, where k is itself a positive integer.  For example,
  * the 3rd smallest integer (k=3) of the array {1,3,10,7} would be 7.
  * The vector does not need to be previously sorted.
  *
  * @param vectorToSearch  The vector of Intger objects to search
  * @param kSmallest      The position to find
  * @return               The kth smallest integer in the passed array
  * @throws InvalidInputException  when k is not computable with
  *                        the passed vector.
  */
  public static int iterativeKthSmallest (Vector vectorToSearch,
                           int kSmallest) throws InvalidInputException {

   boolean notDone = true;

   while (notDone) {

     int midrange = 0; //number of items that duplicate pivot value
     Integer intObject;
     int pivot, currentInt;

     if (kSmallest <= 0 || vectorToSearch.size() < kSmallest) {
        throw new InvalidInputException("k is <= 0 or exceeds the number" 
                                        + " of elements in array.");
     }else if (vectorToSearch.size() == 1) {
        //from above, kSmallest must equal 1 here
        intObject = (Integer) vectorToSearch.elementAt(0);
        return intObject.intValue();
     }else if (vectorToSearch.size() == 0) {
        throw new InvalidInputException("Cannot search an empty array.");
     }

     int pivotIndex = vectorToSearch.size() / 2; //pick a pivot number
     intObject = (Integer) vectorToSearch.elementAt(pivotIndex);
     pivot = intObject.intValue();
     vectorToSearch.add(0, vectorToSearch.remove(pivotIndex));
     pivotIndex = 0;

     for(int i=1; i < vectorToSearch.size(); i++) {
       intObject = (Integer) vectorToSearch.elementAt(i);
       currentInt = intObject.intValue();
       if (currentInt < pivot) {
         vectorToSearch.add(0, vectorToSearch.remove(i));
         pivotIndex++;
       }else if (currentInt > pivot) {
         //don't move bigger items, let them get pushed along
       }else {                            //then i == pivot duplicate
         vectorToSearch.add(pivotIndex + 1, vectorToSearch.remove(i));
         midrange++;
       }
     }

     /* remember that pivotIndex is an index, while kSmallest is a count */
     /* Hence, pivotCount */
     int pivotCount = pivotIndex + 1;
     if (pivotCount <= kSmallest && kSmallest <= pivotCount + midrange){
          //kSmallest is somewhere in the range of duplicate pivot values
          intObject = (Integer) vectorToSearch.elementAt(pivotIndex);
          return intObject.intValue();
     }else if (pivotCount + midrange < kSmallest) { 
        for (int i = 0; i<= pivotIndex + midrange; i++) {
           vectorToSearch.remove(0);
        }
        kSmallest -= (pivotCount + midrange);
     }else if (pivotCount > kSmallest) {
        int i = 0;
        while(pivotIndex <= vectorToSearch.size() - 1) {
           vectorToSearch.remove(vectorToSearch.size() - 1);
        }
     }
   }//end while
  throw new InvalidInputException();  //should never happen
  }

}//end class




/**
 * An exception convenient for when a method recieved parameters it can't
 * handle, especially when those parameters are documented in the method's
 * description.
 */
class InvalidInputException extends Exception {

   public InvalidInputException() {
     super();
   }

   public InvalidInputException(String s) {
     super(s);
   }
}//end class