/** INSTRUCTIONS FOR ALL TASKS
 ** 
 ** Rewrite every function so that they no longer use ANY of the following
 ** constructs: { try, catch, throw, goto, continue, break } and each function
 ** may have only *one* use of the return form, at the end of the function
 ** definition, e.g.:
 ** 
 ** int abs(int x) {
 **   z = x;
 **   if (x < 0) 
 **     z = -x;
 **   return z;
 **  }
 ** 
 **/

class MP7 { 

/* Task 1: return */

/* usage: roots( a, b, c ) returns number of roots of
 * quadratic equation ax^2 + bx + c.
 */

static int roots( int a, int b, int c ) {
  int discrim = (b*b - 4*a*c);
  if (discrim > 0) {
    return 2;
  }
  else if (discrim == 0) {
    return 1;
  }
  else { 
    return 0;
  }
}

/* Task 2: break */

/* requires: array has length k
 * usage: prod( A, k ) returns the product A[0] * A[1] * ... * A[k-1].
 */

static int prod( int array[], int k ) {
  int index = 0;
  int product = 1;
  while ( index < k ) {
    if (array[index] == 0) {
      product = 0;
      break;
    }
    else {
      product = product * array[index];
      index = index + 1;
    }
  }

  return product;
}

/* Task 3: break (again) */

/* requires: array has length k
 * usage: find( A, k, j ) returns the index of the first occurrence 
 *    of j in A.  If j does not occur in A, then returns k.
 */

static int find( int array[], int k, int j ) {
  int index = 0;
  while ( index < k ) {
    if (array[index] == j) {
      break;
    }
    index = index + 1;
  }
 
  return index;
}

/* Task 4: continue */

/* requires: array has length k
 * usage: mystery(A, k) returns a mysterious sum of some elements in A.
 */

static int mystery( int array[], int k ) {
  int i, j;
  int sum = 0;
  i = 0;
  while ( i < k ) {
    j = i;
    i = i + 1;
    while ( j < k ) {
      j = j + 1;
      if (array[j-1] == 1) {
        continue;
      }
      sum = sum + array[j-1];
    }
  }

  return sum;
}

/* Task 5: FakeGoto */

static class FakeGoto extends Exception {} 

/* requires: a or b is non-zero.
 * usage: gcd(a,b) returns the greatest common divisor of a and b
 */

static int gcd( int a, int b ) {
  int t;
  FakeGoto theFakeGoto = new FakeGoto();
  while (true) {
      try {
	  if (b != 0) {
	      t = b;
	      b = a % b;
	      a = t;
	      throw theFakeGoto;
	  }
	  return a;
      }
      catch (FakeGoto ignore_arg) { }
  }
}

/* Task 6: FakeJmp */

static class FakeJmp extends Exception {}

/* Let P = k * k-1 * k-2 * ... * 1.
 * If P fits in a Java integer, returns P.  Else returns k.
 */ 

static int fact_like( int k ) {
  /* The try special form saves its continuation, Kappa, and within
   * the body of the try, throws of Exceptions that "match" the
   * catch clause will jump to the catch's body. */
  try {
      FakeJmp exn = new FakeJmp();
      return fact_core( k, exn );
  }
  catch (FakeJmp ignore_the_exn) {
      return k;
  }
}

/* Helper for fact_like.  Computes factorial, but escapes through 
 * continuation stored in env if we encounter overflow.
 */

static int fact_core( int k, FakeJmp env ) throws FakeJmp {
  if (k == 1) {
    return 1;
  }
  else {
    int factprev = fact_core( k-1, env );
    int retval = k * factprev;
    int orig   = retval / k;

    /* How could orig != factprev? */

    if ( orig != factprev ) {
      /* longjmp( env, X ) abandons its continuation and returns X
       * through the continuation Kappa saved in env.  */
      throw env;
    }
    else {
      return retval;
    }
  }
}

/**
 ** 
 ** START OF TESTING CODE (both test procedures and example input data). 
 ** 
 ** 
 **/

static int four_twos[]        = { 2, 2, 2, 2 };
static int nine_to_zero[]     = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
static int ten_to_one[]       = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
static int ten_to_one_twice[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 
                                  10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
static int four_twoones[]     = { 2, 1, 2, 1, 
                                  2, 1, 2, 1 };

static int test( int task_num, String test_name, int actual, int expected ) {
  int test_failure;
  if (actual == expected) {
    System.out.print( "test success task "+task_num+" "+test_name+"\n");
    test_failure = 0;
  }
  else {
    System.out.print( "TEST FAILURE TASK " + task_num
                      + "\"" + test_name + "\" expected: "
                      + expected + " actual: " + actual + "\n");
    test_failure = 1;
  }
  return test_failure;
}

/* usage: returns number of test failures for Task 1. */
static int test_task1() {
  int c = 0;
  c = c + test( 1, "roots 4x^2",          roots( 4, 0, 0 ), 1 );
  c = c + test( 1, "roots 4x^2 + 1",      roots( 4, 0, 1 ), 0 );
  c = c + test( 1, "roots  x^2 - 4x",     roots( 1,-4, 0 ), 2 );
  c = c + test( 1, "roots  x^2 + 4",      roots( 1, 0, 4 ), 0 );
  c = c + test( 1, "roots  x^2 + 2x + 1", roots( 1, 2, 1 ), 1 );
  c = c + test( 1, "roots 2x^2 + 6x + 4", roots( 2, 6, 4 ), 2 );
  c = c + test( 1, "roots 2x^2 + 6x + 5", roots( 2, 6, 5 ), 0 );
  return c;
}

/* usage: returns number of test failures for Task 2. */
static int test_task2() {
  int c = 0;
  c = c + test( 2, "prod [2,2,2,2]",     prod( four_twos,     4 ), 16 );
  c = c + test( 2, "prod [9,8,...,0])",  prod( nine_to_zero, 10 ), 0 );
  c = c + test( 2, "prod [10,9,...,1])", prod( ten_to_one,   10 ), 3628800 );
  return c;
}

/* usage: returns number of test failures for Task 3. */
static int test_task3() {
  int c = 0;
  c = c + test( 3, "find 2 in [2,2,2,2]",    find( four_twos,    4,  2 ), 0 );
  c = c + test( 3, "find 8 in [9,8,...,0]",  find( nine_to_zero, 10, 8 ), 1 );
  c = c + test( 3, "find 7 in [9,8,...,0]",  find( nine_to_zero, 10, 7 ), 2 );
  c = c + test( 3, "find 7 in [9,8,...,0]",  find( nine_to_zero, 10, 7 ), 2 );
  c = c + test( 3, "find 1 in [10,9,...,1]", find( ten_to_one,   10, 1 ), 9 );
  c = c + test( 3, "find 1 in [10,9,...,1,10,9,...,1]", 
                find( ten_to_one_twice, 10, 1 ), 9 );
  c = c + test( 3, "find 0 in [10,9,...,1]", find( ten_to_one,   10, 0 ), 10);
  return c;
}

/* usage: returns number of test failures for Task 4. */
static int test_task4() {
  int c = 0;
  c += test( 4, "mystery [2,2,2,2]",         mystery( four_twos, 4 ), 20);
  c += test( 4, "mystery [2,1,2,1,2,1,2,1]", mystery( four_twoones, 8 ), 32);
  return c;
}

/* usage: returns number of test failures for Task 5. */
static int test_task5() {
  int c = 0;
  c = c + test( 5, "gcd(42,56)",     gcd( 42, 56 ), 14);
  c = c + test( 5, "gcd(1071,1029)", gcd( 1071, 1029 ), 21);
  return c;
}

/* usage: returns number of test failures for Task 6. */
static int test_task6() {
  int c = 0;
  c = c + test( 6, "10!",             fact_like( 10 ), 3628800);
  c = c + test( 6, "12!",             fact_like( 12 ), 479001600);
  c = c + test( 6, "fact_like(1000)", fact_like( 1000 ), 1000);
  return c;
}

/* usage: runs test suite for MP7; returns number of test failures.
 * Optional argument indicates individual task to test. */
public static void main( String argv[] ) {
  int failure_count = 0;

  if (argv.length == 0) {
    failure_count = failure_count + test_task1();
    failure_count = failure_count + test_task2();
    failure_count = failure_count + test_task3();
    failure_count = failure_count + test_task4();
    failure_count = failure_count + test_task5();
    failure_count = failure_count + test_task6();
  }
  else {
    if (argv[1].equals("1")) {
      failure_count = failure_count + test_task1();
    }
    else if (argv[1].equals("2")) {
      failure_count = failure_count + test_task2();
    }
    else if (argv[1].equals("3")) {
      failure_count = failure_count + test_task3();
    }
    else if (argv[1].equals("4")) {
      failure_count = failure_count + test_task4();
    }
    else if (argv[1].equals("5")) {
      failure_count = failure_count + test_task5();
    }
    else if (argv[1].equals("6")) {
      failure_count = failure_count + test_task6();
    }
    else {
      System.out.print("warning: argument was \"%s\","
                       + " expected 1 2 3 4 5 or 6.\n");
    }
  }
  System.out.println("Testing complete; " + failure_count + " test failures.");

  if (failure_count != 0) {
    System.exit(1);
  }
  else {
    System.exit(0);
  }
}
}