COP 3337
  Section U05
  Spring 2016


                          A PROGRAM FOR HW# 3
                          ===================



  I. The Program:
  ---------------


  import java.util.ArrayList;
  public class Recursion 
  {
      // method 1
      public static boolean isDavis(String in)
      {
          if (in.equals("ab") || in.equals("cbac") || in.equals("baccba"))
              return true; // the basic cases
          int len = in.length();
          if ( len < 6 || len % 2 == 1)
              return false;
          // check case 3
          if (in.charAt(len-1) == 'a') // last letter is a
          {
              int mid = len / 2;
              if (in.charAt(mid-1) == 'b')
              {
                  String s1 = in.substring(0,mid-1);
                  String s2 = in.substring(mid,len-1);
                  if (s1.equals(s2) && isDavis(s1))
                      return true;
              }    
          }    
        
          // check case 4
          if (in.charAt(0) == 'a')
          {
              for (int i = 3; i < len - 3; i = i + 2)
              {    
                  if ( in.charAt(i) == 'b')
                  {
                      // extract u and v
                      String u = in.substring(1,i);
                      String v = in.substring(i+1);
                      if (isDavis(u) && isDavis(v))
                          return true;
                  }    
              }    
          }    
          // all tests failed
          return false;                
      }        

      // method 2
      // a method that recognizes if a string is Huyn
      // this method recognizes if a string is Clarke
      public static boolean isHuyn(String in)
      {
          // reject the null string
          if (in == null)
              return false;
          // accept the 2 base cases
          if (in.equals("acb") || in.equals("bca"))
              return true;
          // reject all other strings of length < 9,
          // the string whose length is not divisible by 3,
          // the strings that don't start with a or b and all strings
          // that don't end in a or b
          int len = in.length();
          if (len < 9 || len % 3 != 0)
              return false;
          if (in.charAt(0) != 'a' && in.charAt(0) != 'b')
              return false;
          if (in.charAt(len -1) != 'a' && in.charAt(len -1 ) != 'b')
              return false;
        
          // check rule 3
          if (in.charAt(0) == 'a' && in.substring(len-2).equals("cb")
                  && (len -3) % 2 == 0 )
          {
              // extract the 2 S's
              int sLength = (len - 3) / 2 ;
              String s1 = in.substring(1,sLength + 1);
              String s2 = in.substring(sLength + 1, len -2);
              if (s1.equals(s2) && isHuyn(s1))
                  return true;
          }    
          // Check rule 4
          if (in.substring(0,2).equals("bc") && in.charAt(len-1) == 'a')
        
              for (int i = 5; i < len - 4; i += 6)
              {
                  //extract u and v
                  String u = in.substring(2,i);
                  String v = in.substring(i,len-1);
                  if (isHuyn(u) && isHuyn(v))
                      return true;
              }    
          // in is not Huyn
          return false;
      }        
        
       // method 3
      // find the largest value of an array slice using recursion
      public static double getLargest(double[] a, int low, int high)
      {
          // check for null and empty
          if (a == null || a.length == 0 || low < 0 || high >= a.length ||
                  low > high)
              throw new IllegalArgumentException();
          if ( low == high)
              return a[low];
          // divide the array ino 2 halves
          // compute the largest of each half
          // and return the biggest of the 2 largest values
          int mid = (low + high) / 2;
          double large1 = getLargest(a,low,mid);
          double large2 = getLargest(a,mid+1,high);
          return Math.max(large1,large2);
      }        
    
      // method 4
      // a short recursive program
      public static void sort(String[] a)
      {        
          if ( a == null || a.length <= 1)
              return; // no sorting 
          for (int i = 0; i < a.length -1; i++)
          {
              // looking for a consecutive pair that is out of order
              if ( a[i].compareTo(a[i+1]) > 0)
              {
                  // swap them and repeat
                  String temp = a[i];
                  a[i] = a[i+1];
                  a[i+1] = temp;
                  sort(a);
              }    
          }                
      }
      // method 5
      // the recursive program for recognizing if
      // a string of parentheses is balanced
      public static boolean isBalanced(String in)
      {
          if (in == null || in.length() == 0 || in.length() % 2 == 1)
               return false;

          // apply the 3 reductions
          String out1 = in.replace("()", "");
          String out2 = out1.replace("[]", "");
          String out3 = out2.replace("{}", "");

          if (in.equals(out3)) // no reduction took place
              return false;
          if (out3.equals("") )
              return true;
          else
              return isBalanced(out3);

      }

      // method 6
      final static int NOT_FOUND = -1;
      // return an index where inq occurs in the array a
      // if  inq occurs in a.
      // if inq is not in a return -1
      // a is sorted in increasing order
      public static int binarySearch(double[] a, double inq)
      {
          // check 
          if (a == null || a.length == 0)
              return NOT_FOUND;
          // a helper method that searches the slice a[0:a.length-1]
          // for an occurrence of inq
          return binarySearch(a, 0, a.length -1, inq);
      }        
    
      // a helper method that searches the array slice a[low:high] 
      // for an occurrence of inq using the binary search method
      private static int binarySearch(double[] a, int low, int high, double inq)
      {
          if (low > high) // the slice is empty
              return NOT_FOUND;
          int mid = (low + high) / 2;
          if (a[mid] == inq)
              return mid;
          else if (a[mid] < inq) // search the upper half
              return binarySearch(a,mid + 1, high, inq);
          else // search the lower half
              return binarySearch(a, low, mid -1, inq);
      }
    
      // method 7
      private static ArrayList<String> sets;
      // print all the subsets of strings in arr
      // assume that a has no duplications
      public static void printThePowerSet(String[] arr)
      {
          System.out.println("The subsets of the array");
          System.out.println("========================\n");
        
          // check for empty array
          if (arr == null || arr.length == 0)
          {
              System.out.println("{}");
              return;
          }
        
          // start processing the items of the array starting with arr[0]
          powerSet(arr, 0);
          // print the items in sets
          for (String item: sets)
              System.out.println(item);
            
      }   
    
      // private method that puts the subsets of arr in sets
      private static void powerSet(String[] arr, int i)
      {
       
          if (i == 0) // initialize
          {
              // put the null set
              sets = new ArrayList<>();
              sets.add("{}");
              powerSet(arr, i+1); // process item i
          }
          else if (i > arr.length )
              return; 
          else // process item i-1
          {
              int count = sets.size();
              for (int j = 0; j < count; j++)
              {
                  // add arr[i-1] at the end of sets[j]
                  String item = sets.get(j);
                  if (item.equals("{}"))
                  {
                      sets.add("{" + arr[i-1] + "}");
                  }
                  else
                  {
                      int len = item.length();
                      String newSet = item.substring(0,len-1) + ", " + arr[i-1] +
                          "}";
                      sets.add(newSet); 
                  }        
              }   
              // process the next item
              powerSet(arr,i+1);
          }    
      }        
    
      // method 8
      // this method prints the last items of a, starting with a[i]
      // if a is null, or i >= a.length the method returns
      // if i < 0 it executes with i = 0
      public static void printArray(int[] a, int i)
      {
          if (a == null || i >= a.length)
              return;
          if (i < 0)
              printArray(a,0);
          else
          {
              System.out.println(a[i]);
              printArray(a,i+1);
          }   
      } // end method
    
      // method 9
      // return the sum of all items in arr
      // if arr is null or empty throw an illegal argument exception
      public static double sum(double[] arr)
      {
          if (arr == null || arr.length == 0)
              throw new IllegalArgumentException("no items");
          return sum(arr,0, arr.length-1);
      }        
    
      // return the sum arr[low] + ... + arr[high]
      private static double sum(double[] arr, int low, int high)
      {
          if (low == high)
              return arr[low];
          // low < high
          int mid = (low + high) / 2;
          return sum(arr,low,mid) + sum(arr,mid+1,high);
      }        
    
      // method 10
      // compute Math.pow(x,n) using the smallest number of 
      // multiplications
      // if n < 0 throw an illegalargument exception 
      public static double powerOf(double x, int n)
      {
          if (n < 0)
              throw new IllegalArgumentException("negative exponent");
          if (n == 0)
              return 1;
          if (n == 1)
              return x;
          // compute x to the power n/2
          double y = powerOf(x,n/2);
          // check if n is even
          if (n % 2 == 0 )
              return y*y;
          else
              return y * y * x; 
      }        
  } // end recursion


  II. The Driver:
  ---------------
    
    public static void main(String[] args) 
    {
        System.out.println("Test Hw #3");
        System.out.println("==========\n\n");
     
      
        System.out.println("Testing method 1:");
        System.out.println("-----------------");
        boolean test;
        try
        {
            test = Recursion.isDavis("abbaba");
            System.out.println(test);
            if (test)
               System.out.println("You passed test 1.");
            else
               System.out.println("You failed test 1.");
        }
        catch(Exception e)
        {
            System.out.println("Test 1 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 1 produced the error " +  e.toString());
        }    
        try
        {
            test = Recursion.isDavis("acbacbabbacbacbaba");
            System.out.println(test);
            if (! test)
               System.out.println("You passed test 2.");
            else
               System.out.println("You failed test 2.");
        }
        catch(Exception e)
        {
            System.out.println("Test 2 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 2 produced the error " +  e.toString());
        }    
        
        try
        {
            test = Recursion.isDavis("baccbababa");
            System.out.println(test);
            if ( ! test)
               System.out.println("You passed test 3.");
            else
               System.out.println("You failed test 3.");
        }
        catch(Exception e)
        {
            System.out.println("Test 3 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 3 produced the error " +  e.toString());
        }    
        
        try
        {
            test = Recursion.isDavis("aacbacbbaccbababbaba");
            System.out.println(test);
            if (test)
               System.out.println("You passed test 4.");
            else
               System.out.println("You failed test 4.");
        }
        catch(Exception e)
        {
            System.out.println("Test 4 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 4 produced the error " +  e.toString());
        }    
       
        System.out.println("\nTesting method 2:");
        System.out.println("-----------------");
        try
        {
            test = Recursion.isHuyn("abcabcacb");
            System.out.println(test);
            if (test)
               System.out.println("You passed test 5.");
            else
               System.out.println("You failed test 5.");
        }
        catch(Exception e)
        {
            System.out.println("Test 5 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 5 produced the error " +  e.toString());
        }    
        try
        {
            test = Recursion.isHuyn("bcbcaacba");
            System.out.println(test);
            if (! test)
               System.out.println("You passed test 6.");
            else
               System.out.println("You failed test 6.");
        }
        catch(Exception e)
        {
            System.out.println("Test 6 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 6 produced the error " +  e.toString());
        }    
        
        try
        {
            test = Recursion.isHuyn("abcacbacbabcacbbcaacb");
            System.out.println(test);
            if ( ! test)
               System.out.println("You passed test 7.");
            else
               System.out.println("You failed test 7.");
        }
        catch(Exception e)
        {
            System.out.println("Test 7 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 7 produced the error " +  e.toString());
        }    
        
        try
        {
            test = Recursion.isHuyn("abcacbacbabcacbacbacb");
            System.out.println(test);
            if (!test)
               System.out.println("You passed test 8.");
            else
               System.out.println("You failed test 8.");
        }
        catch(Exception e)
        {
            System.out.println("Test 8 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 8 produced the error " +  e.toString());
        }    
       
        System.out.println("\nWe test method 3.");
        System.out.println("-----------------");
        System.out.println("We have the array { 2.5, -1.3, 5.9, -3.8, 2.7,"
                + " -8.9, 2.5}");
        double[] test5 = {2.5, -1.3, 5.9, -3.8, 2.7, -8.9, 2.5};
        double big;
        try
        {
            big = Recursion.getLargest(test5, 1,6);
            if (big == 5.9)
                System.out.println("You passed test 9.");
            else
                System.out.println("You failed test 9.");
        }    
        catch(Exception e)
        {
            System.out.println("Test 9 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 9 produced the error " +  e.toString());
        }    
        try
        {
            big = Recursion.getLargest(test5, 3,6);
            if (big == 2.7)
                System.out.println("You passed test 10.");
            else
                System.out.println("You failed test 10.");
        }    
        catch(Exception e)
        {
            System.out.println("Test 10 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 10 produced the error " +  e.toString());
        }    
        
        try
        {
            big = Recursion.getLargest(test5, 5, 4);
            System.out.println("You failed test 11.");
        }    
        catch(Exception e)
        {
            if (e instanceof IllegalArgumentException)
                System.out.println("You passed test 11.");
            else
                System.out.println("You failed test 11.");
        }    
        catch(Error e)
        {
            System.out.println("Test 11 produced the error " +  e.toString());
        }    
        
        System.out.println("\nWe test method 4.");
        System.out.println("-----------------");
        System.out.println("We try to sort the array { \"Papa Bill\", \"Mark\","
            + "\"Angela\", \"Carolina\", \"Gargamel\"} ");
        String[] a1 = { "Papa Bill", "Mark", "Angela", "Carolina", "Gargamel"};
        try
        {
            Recursion.sort(a1);
            System.out.println("The sorted array:");
            for (String s: a1)
                System.out.println(s);
        }
        catch(Exception e)
        {
            System.out.println("Test 12 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 12 produced the error " +  e.toString());
        }               
        // test 13
        String[] a2 = null;
        try
        {
            Recursion.sort(a2);
            System.out.println("You passed test 13.");
        }
        catch(Exception e)
        {
            System.out.println("Test 13 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 13 produced the error " +  e.toString());
        }        
        
        // method 5
        System.out.println("\nWe test method 5.");
        System.out.println("-----------------");
        try
        {
            test = Recursion.isBalanced("");
            System.out.println(test);
            if ( ! test)
               System.out.println("You passed test 14.");
            else
               System.out.println("You failed test 14.");
        }
        catch(Exception e)
        {
            System.out.println("Test 14 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 14 produced the error " +  e.toString());
        }    
        try
        {
            test = Recursion.isBalanced("{[]}(([]))");
            System.out.println(test);
            if (test)
               System.out.println("You passed test 15.");
            else
               System.out.println("You failed test 15.");
        }
        catch(Exception e)
        {
            System.out.println("Test 15 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 15 produced the error " +  e.toString());
        }    
                
        try
        {
            test = Recursion.isBalanced("{[({{}}))}");
            System.out.println(test);
            if (!test)
               System.out.println("You passed test 16.");
            else
               System.out.println("You failed test 16.");
        }
        catch(Exception e)
        {
            System.out.println("Test 16 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 16 produced the error " +  e.toString());
        }    
        
        try
        {
            test = Recursion.isBalanced("{{[[(({}))]]}}");
            System.out.println(test);
            if (test)
               System.out.println("You passed test 17.");
            else
               System.out.println("You failed test 17.");
        }
        catch(Exception e)
        {
            System.out.println("Test 17 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 17 produced the error " +  e.toString());
        }    
        
        System.out.println("\nWe test method 6.");
        System.out.println("-----------------");
        System.out.println("We have the array { 2.0, 3.0, 5.6, 7.5, 8.3, 9.7"
            + ", 10.6}");
        double[] testArray = {2.0 , 3.0, 5.6, 7.5, 8.3, 9.7, 10.6};
        int ind;
        try
        {
            ind = Recursion.binarySearch(testArray,2.0);
            if (ind == 0)
               System.out.println("You passed test 18.");
            else
               System.out.println("You failed test 18.");
        }
        catch(Exception e)
        {
            System.out.println("Test 18 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 18 produced the error " +  e.toString());
        }    
        try
        {
            ind = Recursion.binarySearch(testArray, 4.0);
            if (ind == -1)
               System.out.println("You passed test 19.");
            else
               System.out.println("You failed test 19.");
        }
        catch(Exception e)
        {
            System.out.println("Test 19 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 19 produced the error " +  e.toString());
        }    
        
        double[] testArray2 = null;
        try
        {
            ind = Recursion.binarySearch(testArray2, 4.0);
            if (ind == -1)
               System.out.println("You passed test 20.");
            else
               System.out.println("You failed test 20.");
        }
        catch(Exception e)
        {
            System.out.println("Test 20 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 20 produced the error " +  e.toString());
        }    
        
        System.out.println("\nWe test method 7.");
        System.out.println("-----------------");
        System.out.println("We have the array {\"Papa Smurf\", \"Bazari\"} ");
        String[] names1 = {"Papa Smurf", "Bazari"};
        try
        {
            Recursion.printThePowerSet(names1);
        }    
        catch(Exception e)
        {
            System.out.println("Test 21 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 21 produced the error " +  e.toString());
        }    
        
        System.out.println("\nWe have the null array.");
        String[] names2 = null;
        try
        {
            Recursion.printThePowerSet(names2);
        }    
        catch(Exception e)
        {
            System.out.println("Test 22 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 22 produced the error " +  e.toString());
        }    
        
        String[] names3 = {"Ali Baba", "Shrek", "Poco Pelo"};
        System.out.println("We have the array {\"Ali Baba\", \"Shrek\", "
              +  "\"Poco Pelo\"}");
        try
        {
            Recursion.printThePowerSet(names3);
        }    
        catch(Exception e)
        {
            System.out.println("Test 23 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 23 produced the error " +  e.toString());
        }    
        
        System.out.println("\nWe test method 8.");
        System.out.println("-----------------");
        int[] testArray3 = { 0, 1, 2, 3, 4, 5, 6};
        System.out.println("The array is { 1, 2, 3, 4, 5, 6} .");
        try
        {    
            System.out.println("We print the items starting with index 4.");
            Recursion.printArray(testArray3,4);
        }    
        catch(Exception e)
        {
            System.out.println("Test 24 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 24 produced the error " +  e.toString());
        }    
        try
        {
            System.out.println("We print the items starting with index -3.");         
            Recursion.printArray(testArray3,-3);
        }    
        catch(Exception e)
        {
            System.out.println("Test 25 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 25 produced the error " +  e.toString());
        }    
        
        try
        {
            System.out.println("We print the items starting with index 7.");
            Recursion.printArray(testArray3,7);
        }    
        catch(Exception e)
        {
            System.out.println("Test 26 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 26 produced the error " +  e.toString());
        }    
        int[] testArray4 = {};
        System.out.println("The array is empty.");
        try
        {
            System.out.println("We print the items starting with index 0.");
            Recursion.printArray(testArray4,0);
        }    
        catch(Exception e)
        {
            System.out.println("Test 27 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 27 produced the error " +  e.toString());
        }    
        
        System.out.println("\nWe test method 9.");
        System.out.println("-----------------");
        System.out.println("The array is { 1.0, 2.0, 3.0, 4.0}");
        double[] testArray5 = { 1.0,  2.0, 3.0, 4.0};
        try
        {
            double sum = Recursion.sum(testArray5);
            if (sum == 10.0)
                System.out.println("You passed test 28.");
            else
                System.out.println("You failed test 28.");
        }    
        catch(Exception e)
        {
            System.out.println("Test 28 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 28 produced the error " +  e.toString());
        }    
        double[] testArray6 = null;
        try
        {
            double sum = Recursion.sum(testArray6);
            System.out.println("You failed test 29.");
        }    
        catch(IllegalArgumentException e)
        {
            System.out.println("You passed test 29.");
        }    
        catch(Exception e)
        {
            System.out.println("Test 29 produced the exception " + e.toString());
        }    
        catch(Error e)
        {
            System.out.println("Test 29 produced the error " +  e.toString());
        }    
        
        System.out.println("\nWe test method 10.");
        System.out.println("------------------");
        
        System.out.println("2.0 to 6 is " + Recursion.powerOf(2.0,6));
        System.out.println("2.0 to 1 is " + Recursion.powerOf(2.0,1));
        System.out.println("10.0 to 0 is " + Recursion.powerOf(10.0,0));
        System.out.println("2.0 to 9 is " + Recursion.powerOf(2.0,9));
    }
    
  III. The Output:
  ----------------

  run:
  Test Hw #3
  ==========


  Testing method 1:
  -----------------
  true
  You passed test 1.
  false
  You passed test 2.
  false
  You passed test 3.
  true
  You passed test 4.

  Testing method 2:
  -----------------
  true
  You passed test 5.
  false
  You passed test 6.
  false
  You passed test 7.
  false
  You passed test 8.

  We test method 3.
  -----------------
  We have the array { 2.5, -1.3, 5.9, -3.8, 2.7, -8.9, 2.5}
  You passed test 9.
  You passed test 10.
  You passed test 11.

  We test method 4.
  -----------------
  We try to sort the array { "Papa Bill", "Mark","Angela", "Carolina", "Gargamel"} 
  The sorted array:
  Angela
  Carolina
  Gargamel
  Mark
  Papa Bill
  You passed test 13.

  We test method 5.
  -----------------
  false
  You passed test 14.
  true
  You passed test 15.
  false
  You passed test 16.
  true
  You passed test 17.

  We test method 6.
  -----------------
  We have the array { 2.0, 3.0, 5.6, 7.5, 8.3, 9.7, 10.6}
  You passed test 18.
  You passed test 19.
  You passed test 20.

  We test method 7.
  -----------------
  We have the array {"Papa Smurf", "Bazari"} 
  The subsets of the array
  ========================

  {}
  {Papa Smurf}
  {Bazari}
  {Papa Smurf, Bazari}

  We have the null array.
  The subsets of the array
  ========================

  {}
  We have the array {"Ali Baba", "Shrek", "Poco Pelo"}
  The subsets of the array
  ========================

  {}
  {Ali Baba}
  {Shrek}
  {Ali Baba, Shrek}
  {Poco Pelo}
  {Ali Baba, Poco Pelo}
  {Shrek, Poco Pelo}
  {Ali Baba, Shrek, Poco Pelo}

  We test method 8.
  -----------------
  The array is { 1, 2, 3, 4, 5, 6} .
  We print the items starting with index 4.
  4
  5
  6
  We print the items starting with index -3.
  0
  1
  2
  3
  4
  5
  6
  We print the items starting with index 7.
  The array is empty.
  We print the items starting with index 0.

  We test method 9.
  -----------------
  The array is { 1.0, 2.0, 3.0, 4.0}
  You passed test 28.
  You passed test 29.

  We test method 10.
  ------------------
  2.0 to 6 is 64.0
  2.0 to 1 is 2.0
  10.0 to 0 is 1.0
  2.0 to 9 is 512.0
  BUILD SUCCESSFUL (total time: 0 seconds)