/*
 * This is the updated version of the Mult_Cipher.cpp program you were asked to write in Week 7. It
 * incorporates the ability to find multiplicative inverses and therefore decode messages as well 
 * as encode them. It also incorporates a modified GCF function that returns 0 if one of the
 * numbers entered into it is 0.
 *
 */

//All the necessary include directives.
#include<iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include<string>
#include "Translator.h"
using namespace std;

//Declares the Mult_Cipher class.
class Mult_Cipher {
private:
	int mod;
	Translator tran;

public:
	Mult_Cipher() {mod = 26; }	
	void encode(string *str, int key);
	void encode_rand(string *str, int range);
	void decode(string *str, int key);

private:
	//These functions are decalred private since they are only called from the public functions.
	int rand_0toN1(int n);
	int inverse(int b, int n);
	int gcf(int a, int b);

};

//Testing for encode and decode functions.
int main() {

	string a = "thequickbronfoxjumpedoverthelazydog";
	
	Mult_Cipher mult;
	
	mult.encode(&a, 17);
	
	cout << "After encoding: " << a << "\n";
	
	mult.decode(&a, 17);
	
	cout << "After decoding: " << a << "\n";
	
	return 0;
}

//Enocde method is similar to the one from last week except that it also incorporates the gcf 
//function to ensure the key is a valid encoding key in a multiplicative cipher.
void Mult_Cipher::encode(string *str, int key) {

	//First ensure that the key is greater than 0. If not, prompt the user to enter another key.
	while(key < 0) {
		cout << "Please enter a positive key value: ";
		cin >> key;
	}
	
	//Check that the key is between 0 and mod-1 before checking its gcf with the mod since it is 
	//possible for the key enter to be coprime, but the encoding key (the key entered modulo mod)
	//to not be.
	if(key > mod) {
		key = key % mod;
	}
	
	//Test to see that the key is coprime to the modulus. If it is not, or if the key is 0 the 
	//function will return 0, and we will exit the program.
	int test = gcf(key, mod);
	
	if(test != 1) {
		cout << "Could not encode please try a key that is coprime to the modulus. \n";
		return;
	}
	
	//The rest of the function should be identical to last week.
	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] * key) % mod;
	}
	
	tran.num_to_string(str, A, len);
}

//Random encoding method ensures that the key passed onto the encode function is coprime to mod.
//If it is not, it generates another random number. It also checks that the range is greater than
//0. If not it prompts the user to enter another key until this is the case.
void Mult_Cipher::encode_rand(string *str, int range) {

	while(range <= 0) {
		cout << "Please enter a positive range value: ";
		cin >> range;
	}
	srand(time(NULL));
	int num = rand_0toN1(range) % mod;
	int test = gcf(num, mod);
	
	while(test != 1) {
		num = rand_0toN1(range) % mod;
		test = gcf(num, mod);
	}
	encode(str, num);
}

//Standard decode method. It first checks if the key is less than 0. If so it prompts the user to 
//enter another key value. We don't worry about the key being greater than the modulus since the 
//inverse function takes care of that.
void Mult_Cipher::decode(string *str, int key) {

	//First make sure the key is positive. If not, prompt the user to renenter it until it is.
	while(key < 0) {
		cout << "Please enter a positive key value: ";
		cin >> key;
	}

	int len = (*str).size();
	int A[len];
	
	//Compute the inverse of key using the inverse function. If the key does nto have a valid
	//inverse the function will return 0, and we will exit the program.
	int inv = inverse(key, mod);
		
	if(inv == 0) {
		cout << "Could not decode please try a key that is coprime to the modulus. \n";
		return;
	}
	
	tran.string_to_num(str, A, len);
	
	for(int i = 0; i < len; i++) {
		A[i] = (A[i] * inv) % mod;
		
		while(A[i] < 0) {
			A[i] += 26;
		}
	}
	
	tran.num_to_string(str, A, len);
}

//Usual rand function to get a random number between 0 and n-1.
int Mult_Cipher::rand_0toN1(int n) {
	return rand() % n;
}

//This function uses the Extended Euclidean algorithm to find the multiplicative inverse of a 
//number n given a modulus n. 
int Mult_Cipher::inverse(int b, int n) {
	
	//Before we do anything reduce b (mod n) in case it isn't already.
	if(b > n) {
		b = b % n;
	}
	
	//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 || gcf(b, n) != 1) {
		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 = n;
	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) % n;
		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 += n;
		}
		return t;
	}
}

//Simple recursive greatest common factor function that implements the Euclidean algorithm.
int Mult_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.
	//This also helps in the encode(), encode_rand(), and decode() functions. 
	if(a == 0 || b == 0) {
		return 0;
	}
	//Otherwise run the algorithm.
	if(a % b == 0) {
		return b;
	}
	else {
		return gcf(b, a % b);
	}
}