/*
 * This is a solution to the Affine_Cipher.cpp program you were asked to write for this week. It is
 * very much like the Add_Cipher.cpp and Mult_Cipher.cpp programs you have already written.
 *
 */

#include<iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include "Translator.h"
using namespace std;

class Affine_Cipher {
private:
	int mod;
	Translator tran;

public:
	//Note in the encode and decode functions we once again need multiple keys.
	Affine_Cipher() {mod = 26;}	
	void encode(string *str, int multkey, int addkey);
	void encode_rand(string *str, int range);
	void decode(string *str, int multkey, int addkey);

private:
	int rand_0toN1(int n);
	int inverse(int b);
	int gcf(int a, int b);
};

//Main funcion can test some of the methods.
int main() {

	string a = "dogcatmousefroggy";
	
	Affine_Cipher affine;
	
	affine.encode(&a, 5, 12);
	cout << "After encoding: " << a << "\n";

	affine.decode(&a, 5, 12);
	cout << "After decoding: " << a << "\n";
	
	return 0;
}

//This is essentially the encode function that you have already written in previous weeks except 
//that it now also tests to ensure that the multkey and addkeys are valid ones by the same tests 
//that were used in the Add_Cipher.cpp and Mult_Cipher.cpp programs.
void Affine_Cipher::encode(string *str, int multkey, int addkey) {
	
	//Make sure that the multkey and addkey are positive. If not, prompt the use to reenter them.
	while(multkey < 0) {
		cout << "Please enter a posiitve multkey: ";
		cin >> multkey;
	}
	while(addkey < 0) {
		cout << "Please enter a posiitve addkey: ";
		cin >> addkey;
	}	
	
	//Make sure that the multkey is reduced so that they are between 0 and the mod-1. Otherwise it 
	//may be coprime, but its value in the mod ring may not be.
	if(multkey > mod) {
		multkey = multkey % mod;
	}
	
	//Get the greatest common factor and test to see if it is 1. If not stop since a new multkey
	//is needed.
	int test = gcf(multkey, mod);
	
	if(test != 1) {
		cout << "Could not encode please try a key that is coprime to the modulus. \n";
		return;
	}
	
	//The rest of the program is very much like the Mult and Add cipher programs.
	int len = (*str).size();
	int A[len];
	
	tran.string_to_num(str, A, len);

	for(int i = 0; i < len; i++) {
		A[i] = ((A[i] * multkey) + addkey) % mod;
	}
	
	tran.num_to_string(str, A, len);
}

//Random encode gets random values, but makes sure the multkey value is coprime to the modulus. If 
//not it gets another value. Also first ensures that the range from which the values are drawn is
//positive. This does mean that we will not be able to get 0 as an addkey even though it is valid,
//but that is the consequence of drawing both keys from the same range.
void Affine_Cipher::encode_rand(string *str, int range) {

	while(range <= 0) {
		cout << "Please enter a positive range value: ";
		cin >> range;
	}
	
	srand(time(NULL));
	int numMult = rand_0toN1(range) % mod;
	int numAdd = rand_0toN1(range) % mod;
	int test = gcf(numMult, mod);
	
	//While our prospective multKey is not coprime to mod go back and get another value.
	while(test != 1) {
		numMult = rand_0toN1(range) % mod;
		test = gcf(numMult, mod);
	}
	encode(str, numMult, numAdd);
}

//Standard decode method. Ensures that the multkey and adkey are proper.
void Affine_Cipher::decode(string *str, int multkey, int addkey) {

	//Make sure that the multkey and addkey are positive. If not, prompt the use to reenter them.
	while(multkey < 0) {
		cout << "Please enter a posiitve multkey: ";
		cin >> multkey;
	}
	while(addkey < 0) {
		cout << "Please enter a posiitve addkey: ";
		cin >> addkey;
	}	
	
	//Make sure that the multkey is reduced so that they are between 0 and the mod-1. Otherwise it 
	//may be coprime, but its value in the mod ring may not be.
	if(multkey > mod) {
		multkey = multkey % mod;
	}	
	
	//Calculate the inerse of multkey if it exists. If the function returns 0, then it must not be
	//a valid multkey and therefore exit the program.
	int inv = inverse(multkey);
		
	if(inv == 0) {
		cout << "Could not decode please try a multkey that is coprime to the modulus. \n";
		return;
	}

	int len = (*str).size();
	int A[len];
	
	//The remainder is like the decode methods in the other functions.
	tran.string_to_num(str, A, len);
	
	for(int i = 0; i < len; i++) {
		A[i] = ((A[i] - addkey) * inv) % mod;
		
		while(A[i] < 0) {
			A[i] += 26;
		}
	}
	
	tran.num_to_string(str, A, len);
}

//Standard random number generating function.
int Affine_Cipher::rand_0toN1(int n) {
	return rand() % n;
}

//Finds the multiplicative inverse using the Extended Euclidean algorithm that you read about for 
//this week.
int Affine_Cipher::inverse(int b) {
	
	//Before we do anything reduce b (mod n) in case it isn't already. 	
	if(b > mod) {
		b = b % mod;
	}

	//Now check our special cases to avoid complications in the Euclidean algorithm. Since 1
	//is it's own multiplicative inverse for any modulus, return 1 if b = 1. Similiarly, if b = 0
	//or is not coprime to the modulus then it does not have a multiplicative inverse (mod n) 
	//(why?) so return 0 as a default.
	
	if(b == 1) {
		return 1;
	}
	
	if(b == 0) {
		return 0;
	}

	//Now set up all th necessary variables for the extended Euclidean algorithm and run it. This 
	//follows the algorithm prsented in Stinson almost identically.
	int temp;
	int a_zero = mod;
	int b_zero = b;
	int t_zero = 0;
	int t = 1;
	int r = a_zero % b_zero;
	int q = (a_zero - r) / b_zero;
		
	while(r > 0) {
		temp = (t_zero - q*t) % mod;
		t_zero = t;
		t = temp;
		a_zero = b_zero;
		b_zero = r;
		if(a_zero % b_zero <= 0) {
			break;
		}
		else {
			r = a_zero % b_zero;
			q = (a_zero - r) / b_zero;
		}
	}
	
	if(r != 1) {
		return 0;
	}
	else{
		while(t < 0) {
			t += mod;
		}
		return t;
	}
}

//Simple recursive greatest common factor function that implements the Euclidean algorithm.
int Affine_Cipher::gcf(int a, int b) {

	//If either of our inputs is 0 then it doesn't make much sense to talk about gcf's so return 0.
	
	if(a == 0 || b == 0) {
		return 0;
	}

	//Otherwise run the algorithm.	
	if(a % b == 0) {
		return b;
	}
	else {
		return gcf(b, a % b);
	}
}