#include "ca2.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) {
				

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

}


void writeResults(int base, int* cycleResults, int* tailResults, int* toCycleResults){
	bool primRoot = isPrimRoot(base);
	bool relPrime = isRelPrime(base);
	char* file = new char[20];
	convert<int, char*>(n, file);
	string fileStr = file;
	if (primRoot && relPrime)
		fileStr+="PRRP";
	else if (primRoot)
		fileStr+="PR";
	else if (relPrime)
		fileStr+= "RP";
	else
		fileStr += "NONE";
	fileStr += ".txt";
	ifstream in(fileStr.c_str());
	int prevC, prevT, prevToC;
	for(int i = 1; i <= n; i++){
		in>>prevC;
		in.ignore(1,0);
		in>> prevT;
		in.ignore(1,0);
		in>> prevToC;
		in.ignore(1,0);
		cycleResults[i]+= prevC;
		tailResults[i]+= prevT;
		toCycleResults[i] += prevToC;
	}
	in.close();
	ofstream out(fileStr.c_str());
	for(int i = 1; i <= n; i++)
		out<<cycleResults[i] << " " <<tailResults[i]<< " " << toCycleResults[i] << '\n';
	out.close();
	delete file;
}


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(isPrime(n1))	return m_exp(base,n_1/n1) == 1;
			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) {
  if(a== 0) return b;
  if(b==0) return a;
  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* maxTAll,
		       const int* maxCAll,
		       const int* terminalAll) {



	char* file = new char[20];
	convert<int, char*>(n, file);
	string fileStr = file;
	fileStr += "_";
	char* m_ary = new char[10];
	convert<int, char*>(M_ARY, m_ary);
	fileStr += m_ary;
	fileStr += ".dat";
	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();
	delete file;
}

void createFiles() {
	char* file = new char[20];
	convert<int, char*>(n, file);
	string fileRP = strcat(file, "RP.txt");
	convert<int, char*>(n, file);
	string filePR = strcat(file,"PR.txt");
	convert<int, char*>(n, file);
	string filePRRP = strcat(file , "PRRP.txt");
	convert<int, char*>(n, file);
	string fileNONE = strcat(file, "NONE.txt");
	ofstream outRP(fileRP.c_str());
	ofstream outPR(filePR.c_str());
	ofstream outPRRP(filePRRP.c_str());
	ofstream outNONE(fileNONE.c_str());
	for(int i = 0; i < n; i++) {
		outRP << 0 << " " << 0 << '\n';
		outPR << 0 << " " << 0 << '\n';
		outPRRP << 0 << " " << 0 << '\n';
		outNONE << 0 << " " << 0 << '\n';
	}
	outPR.close();
	outRP.close();
	outPRRP.close();
	outNONE.close();
	delete file;
}


void run() {
        ofstream status(STATUS);
	status << "Allocating...\n";
	status.close();
	bool* visit = new bool[n];
	bool* image = new bool[n];
	int* maxTAll = new int[n];
	int* maxCAll = new int[n];
	int* terminalAll = 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 next, size, loc, baseTail, cycleLength, mC, mT, terminal;
	int root, exp, base;
	LinkedList list;
	int* listArray;
  
	for(int i = 0; i <= n; i++){
	        allCResults[i] = 0;
		allTResults[i] = 0;
		allToCycleResults[i] = 0;
		if(i < n) {
		  maxTAll[i] = 0;
		  maxCAll[i] = 0;
		  terminalAll[i] = 0;
		}
	}
	status.open(STATUS, fstream::app);
	status << "Finding a PR...\n";
	status.close();
	
	for(root = 1; !isPrimRoot(root); root++);

	status.open(STATUS, fstream::app);
	status <<"Prim root is "<<root <<"...\n";
	status.close();

	for(exp = 0; exp < n; exp++) {
	  if(exp % 100 == 0) {
	    status.open(STATUS);
	    status << "Exp is " << exp << std::endl;
	    status.close();
	  }
	  if(gcd(exp,n-1) != M_ARY) continue;
	  base = m_exp(root,exp);      
	  mC = 0;
	  mT = 0;
	  setArrays(cycle, visit, toCycle, image);

		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();
		}


		terminal=0;
		for(int i = 1; i < n; i++) 
		  if(!image[i]) terminal++;
		maxTAll[base] = mT;
		maxCAll[base] = mC;
		terminalAll[base] = terminal;
		computeResults(base, cycle, toCycle, allCResults, allTResults, allToCycleResults);
				
			
	}
	status.open(STATUS, fstream::app);
	status << "Writing Results...\n";
	status.close();
	writeTotalResults(allCResults, allTResults, allToCycleResults,
			  maxTAll,
			  maxCAll,
			  terminalAll);
	status.open(STATUS, fstream::app);
	status << "Cleaning up...\n";
	status.close();
	delete [] visit;
	delete [] cycle;
	delete [] toCycle;
	delete [] allCResults;
	delete [] allTResults;
	delete [] allToCycleResults;
	delete[] maxTAll;
	delete[] maxCAll;
	delete [] terminalAll;

	status.open(STATUS, fstream::app);
	status<<"Exiting...\n";
	status.close();	

}