#include "ca1.h"


int m_exp(int b, int r, int num = n) {
	return (int) ml_exp((long long) b, r, (long long) num);
}

long long ml_exp(long long b, int r, long long num) {
	if (r == 0) return 1;
	if(r % 2 == 0) {
		long long result = ml_exp(b,r/2,num);
		return result * result % num;
	}
	long long result = ml_exp(b,r/2,num);
	return (b * result % num) * result % num;
}

void computeResults(int base, const int* cycle, const int* toCycle, 
					int* allCResults, int* allTResults, int* allToCycleResults,
					int* allSplitCResults, int* allSplitTResults, int* allSplitToCResults) {
	
	for(int i = 0; i < n; i++) {
		allSplitToCResults[toCycle[i]]++;
		allToCycleResults[toCycle[i]]++;//and doesn't get written to file
		if(cycle[i] < 0) {			// it isn't worth checking, just let it increment
			allSplitTResults[-1*cycle[i]]++;
			allTResults[-1*cycle[i]]++;
		}
		else if (cycle[i] > 0) {
			allSplitCResults[cycle[i]]++;
			allCResults[cycle[i]]++;
		}
	}
	
}




bool isPrimRoot(int base) {
	if(!isPrime(n)) return false;
	
	int n_1 = n-1;

	if ((unsigned)n_1 > (primes[NUMPRIMES-1]*primes[NUMPRIMES-1]))
		std::cerr<<"Error in Primitive Root Testing, n could "
		<<"have prime factor too large for testing."<<std::endl;
	int n1 = n_1;
	int index = 0;
	int p;
	while(n1 > 1 && index < NUMPRIMES) {
		if((n1 % primes[index]) == 0) {
			p = primes[index];
			while((n1 % primes[index] == 0)) n1/=primes[index];
			if(m_exp(base,n_1/p) == 1) return false;
			if(n1 == 50021) return (m_exp(base,n_1/50021) != 1);
		}
		index++;
	}
	return true;
}

bool isPrime(int num) {
	for(int i = 0; i < 50;i++) {
		if(primes[i] > (unsigned)num) return true;
		if((num % primes[i] == 0) && (num!=primes[i])) return false;
	}
	
	int k = 0;
	int q = num-1;
	while(q % 2 == 0) {
		k++;
		q >>= 1;
	}
	srand(time(0));
	int a;
	for(int i = 0; i < 10; i++) {
		a = (rand() % (num-2)) + 1;
		if(!MillerRabin(num, k, q, a)) return false;
	}

	return true;
}


bool MillerRabin(int num, int k, int q, int a) {
	int n1 = num-1;
	if(m_exp(a,q, num) == 1) return true;
	for(int i = 0; i < k; i++)
		if(m_exp(a,(int)pow(2,i)*q, num) == n1) return true;
	return false;
}


bool isRelPrime(int base) {
	return gcd(base, n-1) == 1;
}

int gcd(int a, int b) {
	int r = a % b;
	int d = b;
	int c;
	while (r > 0) {
		c = d;
		d = r;
		r = c % d;
	}
	return d;
}

void setArrays(int * cycle, bool* visit, int* toCycle, bool* image){
	for(int i = 0; i < n; i++){
		visit[i] = false;
		cycle[i] = 0;
		toCycle[i] = 0;
		image[i] = false;
	}
}


void writeTotalResults(const int* allCResults, const int* allTResults, const int* allToCycleResults,
		       const int* allPRCResults, const int* allPRTResults, const int* allPRToCResults,
		       const int* allNONECResults, const int* allNONETResults, const int* allNONEToCResults,
		       const int* maxTAll, const int* maxTPR,  const int* maxTNone,
		       const int* maxCAll, const int* maxCPR,  const int* maxCNone,
		       const int* terminalAll, const int* terminalPR,
		       const int* terminalNone) {



	char* file = new char[20];
	convert<int, char*>(n, file);
	string fileStr = file;
	fileStr += "all.txt";
	ofstream out(fileStr.c_str());
	for(int i = 1; i <= n; i++) {
	  if(i == 1 || i == n)
	    out << allCResults[i]/i << " " << allTResults[i] << " " << allToCycleResults[i] << " " << 0 <<" " << 0 << " " 
		<< 0 <<'\n';
	  else
	    out << allCResults[i]/i << " " << allTResults[i] << " " << allToCycleResults[i] << " " << terminalAll[i] << " " 
		<< maxCAll[i] << " " << maxTAll[i] << '\n';
	}
	out.close();
	convert<int, char*>(n, file);
	string filePR = strcat(file,"PR.txt");
	convert<int, char*>(n, file);
	string fileNotPR = strcat(file, "NotPR.txt");
	ofstream outPR(filePR.c_str());
	ofstream outNotPR(fileNotPR.c_str());
	for(int i = 1; i <= n; i++) {
	  if(i == 1 || i == n) {
	    outPR << allPRCResults[i]/i << " " << allPRTResults[i] 
		  << " " << allPRToCResults[i] << " " << 0 << " " << 0 << " "
		  << 0 << '\n';
	    outNotPR << allNONECResults[i]/i << " " << allNONETResults[i] << " " << allNONEToCResults[i] << " " << 0 << " "
		    << 0 << " " << 0 << '\n';
	  } else {
	    outPR << allPRCResults[i]/i << " " << allPRTResults[i] << " " << allPRToCResults[i] << " " << terminalPR[i] <<
	      " " << maxCPR[i] << " " << maxTPR[i] << '\n';
	    outNotPR << allNONECResults[i]/i << " " << allNONETResults[i] << " " << allNONEToCResults[i] << " " << 
	      terminalNone[i] << " " << maxCNone[i] << " " << maxTNone[i] << '\n';
	  }
	}
	outPR.close();
	outNotPR.close();
	delete file;
}



void run() {
        ofstream status("status2.txt");
	status << "Allocating...\n";
	status.close();
	bool* visit = new bool[n];
	bool* image = new bool[n];
	int* maxTAll = new int[n];
	int* maxTPR = new int[n];
	int* maxTNone = new int[n];
	int* maxCAll = new int[n];
	int* maxCPR = new int[n];
	int* maxCNone = new int[n];
	int* terminalAll = new int[n];
	int* terminalPR = new int[n];
	int* terminalNone = new int[n];
	int *cycle= new int[n];
	int *toCycle = new int[n];
	int *allCResults = new int[n+1];
	int *allTResults = new int[n+1];
	int *allToCycleResults = new int[n+1];
	int *allPRCResults = new int[n+1];
	int *allNONECResults = new int[n+1];
	int *allPRTResults = new int[n+1];
	int *allNONETResults = new int[n+1];
	int *allPRToCResults = new int[n+1];
	int *allNONEToCResults = new int[n+1];
	
	int next, size, loc, baseTail, cycleLength, mC, mT, terminal;
	LinkedList list;
	int* listArray;
	bool PR;
	for(int i = 0; i <= n; i++){
	        allCResults[i] = 0;
		allTResults[i] = 0;
		allToCycleResults[i] = 0;
		allPRCResults[i] = 0;
		allNONECResults[i] = 0;
		allPRTResults[i] = 0;
		allNONETResults[i] = 0;
		allPRToCResults[i] = 0;
		allNONEToCResults[i] = 0;
		if(i < n) {
		  maxTAll[i] = 0;
		  maxTPR[i] = 0;
		  maxTNone[i] = 0;
		  maxCAll[i] = 0;
		  maxCPR[i] = 0;
		  maxCNone[i] = 0;
		  terminalAll[i] = 0;
		  terminalPR[i] = 0;
		  terminalNone[i] = 0;
		}
	}
	status.open("status2.txt", fstream::app);
	status << "Starting...\n";
	status.close();
	for(int base = 2; base < n-1; base++) {
	        mC = 0;
		mT = 0;
		setArrays(cycle, visit, toCycle, image);
		if(base % 100 == 0) {
		  status.open("status2.txt");
		  status << "Base is " << base << std::endl;
		  status.close();
		}
		for(int i = 1; i < n; i++) {
			list.makeEmpty();
			next = i;
			list.insert(next);
			while(!visit[next]){
				visit[next] = true;
				next = m_exp(base,next);
				image[next] = true;
				list.insert(next);
			}
			if(cycle[next] != 0) {
				if(cycle[next] > 0) {//all tail into cycle
					listArray = list.toArray();
					size = list.length();
					loc = list.find(next);
					cycleLength = cycle[listArray[size-1]];
					if(size - 1 > mT) mT = size - 1;
					for(int j = 0; j < loc; j++){
						cycle[listArray[j]] = 1+j-size;
						toCycle[listArray[j]] = cycleLength;
					}	
				} else {//extension of tail
					listArray = list.toArray();
					size = list.length();
					baseTail = cycle[listArray[size-1]];
					cycleLength = toCycle[listArray[size-1]];
					if(size-1-baseTail > mT) mT = size-1-baseTail;
					for(int j = 0; j < size-1; j++) {
						cycle[listArray[j]] = j+1-size+baseTail;
						toCycle[listArray[j]] = cycleLength;
					}
				}
			} else {//new cycle found
				listArray = list.toArray();
				loc = list.find(next);
				size = list.length();
				cycleLength = size - loc - 1;
				if(cycleLength > mC) mC = cycleLength;
				if(loc > mT) mT = loc;
				for(int j = 0; j <= loc - 1; j++) {
					cycle[listArray[j]] = -loc+j;
					toCycle[listArray[j]] = cycleLength;
				}
				for(int j = loc; j < size - 1; j++)
					cycle[listArray[j]] = cycleLength;
			}
			list.destroyArray();
		}

		PR = isPrimRoot(base);
		terminal=0;
		for(int i = 1; i < n; i++) 
		  if(!image[i]) terminal++;
		maxTAll[base] = mT;
		maxCAll[base] = mC;
		terminalAll[base] = terminal;
		if(!PR) {
		  maxTNone[base]=mT;
		  maxCNone[base] = mC;
		  terminalNone[base] = terminal;
		  computeResults(base, cycle, toCycle, allCResults, allTResults, allToCycleResults,
				 allNONECResults, allNONETResults, allNONEToCResults);
		  
		} else {
		  maxTPR[base] = mT;
		  maxCPR[base] = mC;
		  terminalPR[base] = terminal;
		  computeResults(base, cycle, toCycle, allCResults, allTResults, allToCycleResults,
			 allPRCResults, allPRTResults, allPRToCResults);
		  
		}
			
	}
	status.open("status2.txt", fstream::app);
	status << "Writing Results...\n";
	status.close();
	writeTotalResults(allCResults, allTResults, allToCycleResults,
		allPRCResults, allPRTResults, allPRToCResults,
		allNONECResults, allNONETResults, allNONEToCResults,
			  maxTAll,  maxTPR,  maxTNone,
			  maxCAll,  maxCPR,  maxCNone,
			  terminalAll,  terminalPR,  terminalNone);
	status.open("status2.txt", fstream::app);
	status << "Cleaning up...\n";
	status.close();
	delete [] visit;
	delete [] cycle;
	delete [] toCycle;
	delete [] allCResults;
	delete [] allTResults;
	delete [] allToCycleResults;
	delete [] allPRCResults;
	delete [] allNONECResults;
	delete [] allPRTResults;
	delete [] allNONETResults;
	delete [] allPRToCResults;
	delete [] allNONEToCResults;
	delete[] maxTAll;
	delete[] maxTPR;
	delete[] maxTNone;
	delete[] maxCAll;
	delete[] maxCPR;
	delete[] maxCNone;
	delete [] terminalAll;
	delete [] terminalPR;
	delete [] terminalNone;

}