#include <stdlib.h>
#include <stdio.h>
#include <setjmp.h>

/** INSTRUCTIONS FOR ALL TASKS
 ** 
 ** Rewrite every function so that they no longer use ANY of the following
 ** constructs: { setjmp, longjmp, 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;
 **  }
 ** 
 **/

/* Task 1: return */

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

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].
 */

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.
 */

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.
 */

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: goto */

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

int gcd( int a, int b ) {
  int t;
 restart: 
  if (b != 0) {
    t = b;
    b = a % b;
    a = t;
    goto restart;
  }

  return a;
}

/* Task 6: setjmp/longjmp */

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

int fact_like( int k ) {
  jmp_buf env;

  /* setjmp saves its continuation, Kappa, in env, and then returns 0
   * to Kappa.  So if setjmp returns 0 to Kappa, why the if statement
   * here?  See longjmp below. */

  if (0 == setjmp(env)) {
    return fact_core( k, env );
  }
  else {
    return k;
  }
}

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

int fact_core( int k, jmp_buf env ) {
  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.  */
      longjmp( env, 1 );
    }
    else {
      return retval;
    }
  }
}

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

int four_twos[]        = { 2, 2, 2, 2 };
int nine_to_zero[]     = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
int ten_to_one[]       = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
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 };
int four_twoones[]     = { 2, 1, 2, 1, 
                           2, 1, 2, 1 };

int test( int task_num, char* test_name, int actual, int expected ) {
  int test_failure;
  if (actual == expected) {
    printf( "test success task %d \"%s\"\n", 
            task_num, test_name );
    test_failure = 0;
  }
  else {
    printf( "TEST FAILURE TASK %d \"%s\" expected: %d actual: %d\n", 
            task_num, test_name, expected, actual );
    test_failure = 1;
  }
  return test_failure;
}

/* usage: returns number of test failures for Task 1. */
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. */
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. */
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. */
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. */
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. */
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. */
int main( int argc, char** argv ) {
  int failure_count = 0;

  if (argc == 1) {
    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        (0 == strcmp(argv[1],"1")) {
      failure_count = failure_count + test_task1();
    }
    else if (0 == strcmp(argv[1],"2")) {
      failure_count = failure_count + test_task2();
    }
    else if (0 == strcmp(argv[1],"3")) {
      failure_count = failure_count + test_task3();
    }
    else if (0 == strcmp(argv[1],"4")) {
      failure_count = failure_count + test_task4();
    }
    else if (0 == strcmp(argv[1],"5")) {
      failure_count = failure_count + test_task5();
    }
    else if (0 == strcmp(argv[1],"6")) {
      failure_count = failure_count + test_task6();
    }
    else {
      printf("warning: argument was \"%s\", expected 1 2 3 4 5 or 6.\n");
    }
  }
  printf("Testing complete; %d test failures.\n", failure_count);

  if (failure_count != 0) {
    return 1;
  }
  else {
    return 0;
  }
}