/*
   testfunc17.cpp
   CIS 150
   6/9/2005
   David Klick
   
   Recursive and iterative greatest common divisor implementations.
*/

#include <iostream>
#include <cstring>
#include <climits>
using std::cin;
using std::cout;

int gcd_r(int a, int b);  // recursive gcd function
int gcd_i(int a, int b);  // iterative gcd function
int getInt(char* prompt, int min, int max);
char getChoice(char* prompt, char* allowed);

int main(void) {
   char ans;     // holds user answer for "run again?"
   int n1, n2, result;
   
   cout << "GCD calculator\n";
   do {
      // get numbers from user for GCD calc
      n1 = getInt("Enter an integer greater than 0: ", 1, INT_MAX);
      n2 = getInt("Enter another integer greater than 0: ", 1, INT_MAX);
      
      // calculate and display recursive GCD
      result = gcd_r(n1, n2);
      cout << "The GCD of " << n1 << " and " << n2 << " is "
           << result << " (recursive)\n";

      // calculate and display non-recursive GCD
      result = gcd_i(n1, n2);
      cout << "The GCD of " << n1 << " and " << n2 << " is "
           << result << " (non-recursive)\n";
      
      // find out if user wants to run gcd again
      ans = getChoice("Would you like to calculate another GCD? (Y/N) ", "YyNn");
   } while (ans == 'Y');

   // say "Goodnight" Gracie
   cout << "Normal program termination.\n";
   
   return 0;
}

/*
   Prompts user for integer, does data validation,
   and returns value entered.
*/
int getInt(char* prompt, int min, int max) {
   int num;
   do {
      cout << prompt;
      cin >> num;
      if (num < min) cout << "Error: value below minimum allowed\n";
      else if (num > max) cout << "Error: value above maximum allowed\n";
   } while (num<min || num>max);
   return num;
}

/*
   Prompts user for integer, does data validation, and
   returns the uppercase equivalent of the entered value.
*/
char getChoice(char* prompt, char* allowed) {
   char ans;
   do {
      cout << prompt;
      cin >> ans;
      ans = toupper(ans);  // convert answer to upper case
      if (strchr(allowed, ans) == NULL) cout << "Error: Invalid choice\n";
   } while (strchr(allowed, ans) == NULL);
   return ans;
}

/*
   Calculates and returns greatest common divisor of
   two integers using a recursive algorithm.
*/
int gcd_r(int a, int b) {
  if (a%b == 0) return b;
  else return gcd_r(b, a%b);
}

/*
   Calculates and returns greatest common divisor of
   two integers using a non-recursive (and quite
   inefficient) algorithm.
*/
int gcd_i(int a, int b) {
  int i = a<b ? a : b;  // set i to minimum value
  while (i >= 2) {
    if (a%i==0 && b%i==0) return i;
    else i--;
  }
  return i;
}