#include <iostream>
#include <string>
#include <vector>

//Logic for determining canonical orientation
uint64_t reverse_bytes(uint64_t i){
	//Some 0x00000000FFFFFFFFuLLy 0xFFFFFFFF00000000uLL uint64_t literals.
	i = (i&0xFF00FF00FF00FF00uLL) >> 8 | (i&0x00FF00FF00FF00FFuLL) << 8;
	i = (i&0xFFFF0000FFFF0000uLL) >> 16 | (i&0x0000FFFF0000FFFFuLL) << 16;
	i = (i&0xFFFFFFFF00000000uLL) >> 32 | (i&0x00000000FFFFFFFFuLL) << 32;
	return i;
}

uint64_t reverse_bits(uint64_t i){
	i = (i&0xF0F0F0F0F0F0F0F0uLL) >> 4 | (i&0x0F0F0F0F0F0F0F0FuLL) << 4;
	//Some 0xCCCCCCCCCCCCCCCCuLLt magic going on here.
	i = (i&0xCCCCCCCCCCCCCCCCuLL) >> 2 | (i&0x3333333333333333uLL) << 2;
	i = (i&0xAAAAAAAAAAAAAAAAuLL) >> 1 | (i&0x5555555555555555uLL) << 1;
	return reverse_bytes(i);
}

uint64_t rotate_bits(uint64_t i){
	return i; //Will implement this if and when I stop being lazy.
}

bool orient_first(uint64_t i){
	return i <= reverse_bytes(i)               && i <= reverse_bits(i)              && i <= rotate_bits(i)
	    && i <= reverse_bytes(reverse_bits(i)) && i <= reverse_bits(rotate_bits(i)) && i <= reverse_bytes(rotate_bits(i))
	    && i <= reverse_bits(reverse_bytes(rotate_bits(i)));
}

//Convert a 36-bit integer (6x6 grid) into a 64-bit one (8x8 with padding).
uint64_t _36264(uint64_t i){
	return ((i&0x3FuLL)<<9)        | ((i&0xFC0uLL)<<11) |
	       ((i&0x3F000uLL)<<13)    | ((i&0xFC0000uLL)<<15) |
	       ((i&0x3F000000uLL)<<17) | ((i&0xFC0000000uLL)<<19);
}

const uint64_t m = _36264(0xFE186187FuLL), m2 = _36264(0xFFFFFFFFFuLL); //6x6 frame

//Represents the 8x8 grid of cells as an unsigned 64-bit integer. CGoL currently hardcoded, but that could be changed (although it would significantly slow down the enumeration due to a prefiltering step being removed).
class Cells{
	private:
	uint64_t cells;
	uint16_t gen;
	
	public:
	Cells(){cells = 0ull; gen = 0;}
	Cells(Cells& b){cells = b.cells; gen = b.gen;}
	Cells(uint64_t c){cells = c; gen = 0;}
	Cells(uint64_t c, uint16_t g){cells = c; gen = g;}
	
	uint64_t getcells(){return cells;}
	void setcells(uint64_t c){cells = c;}
	
	//0 <= x < 8, 0 <= y < 8
	bool getcell(uint8_t x, uint8_t y){return (cells>>((y<<3)|x))&1;}
	void setcell(uint8_t x, uint8_t y, bool s){if(s) cells |= 1uLL<<((y<<3)|x); else cells &= ~(1uLL<<((y<<3)|x));}
	uint16_t getgen(){return gen;}
	
	void step(){
		uint64_t b1, b2, b4, b8;
		b1 = b2 = b4 = b8 = 0;
		b1 = (cells<<8)>>1; //This is all out of order but oh well.
		
		b2 ^= cells>>1 & b1;
		b1 ^= cells>>1;
		
		b2 ^= cells<<1 & b1;
		b1 ^= cells<<1;
		
		b4 ^= (cells>>8) & b2 & b1;
		b2 ^= (cells>>8) & b1;
		b1 ^= (cells>>8);
		
		b4 ^= (cells>>8)>>1 & b2 & b1;
		b2 ^= (cells>>8)>>1 & b1;
		b1 ^= (cells>>8)>>1;
		
		b4 ^= (cells>>8)<<1 & b2 & b1;
		b2 ^= (cells>>8)<<1 & b1;
		b1 ^= (cells>>8)<<1;
		
		b4 ^= (cells<<8) & b2 & b1;
		b2 ^= (cells<<8) & b1;
		b1 ^= (cells<<8);
		
		b8 ^= (cells<<8)<<1 & b4 & b2 & b1;
		b4 ^= (cells<<8)<<1 & b2 & b1;
		b2 ^= (cells<<8)<<1 & b1;
		b1 ^= (cells<<8)<<1;
		cells = ((cells & ~b4 & b2) | (~cells & ~b4 & b2 & b1) | (cells & m) | (cells & ~m2)) & (cells | ~m) & (cells | m2); //CGoL evolution, minus stator
	    gen++;
	}
	
	void masked_step(uint64_t mask){
		uint64_t b1, b2, b4, b8;
		b1 = b2 = b4 = b8 = 0;
		b1 = (cells<<8)>>1; //This is all out of order but oh well.
		
		b2 ^= cells>>1 & b1;
		b1 ^= cells>>1;
		
		b2 ^= cells<<1 & b1;
		b1 ^= cells<<1;
		
		b4 ^= (cells>>8) & b2 & b1;
		b2 ^= (cells>>8) & b1;
		b1 ^= (cells>>8);
		
		b4 ^= (cells>>8)>>1 & b2 & b1;
		b2 ^= (cells>>8)>>1 & b1;
		b1 ^= (cells>>8)>>1;
		
		b4 ^= (cells>>8)<<1 & b2 & b1;
		b2 ^= (cells>>8)<<1 & b1;
		b1 ^= (cells>>8)<<1;
		
		b4 ^= (cells<<8) & b2 & b1;
		b2 ^= (cells<<8) & b1;
		b1 ^= (cells<<8);
		
		b8 ^= (cells<<8)<<1 & b4 & b2 & b1;
		b4 ^= (cells<<8)<<1 & b2 & b1;
		b2 ^= (cells<<8)<<1 & b1;
		b1 ^= (cells<<8)<<1;
		cells = ((cells & ~b4 & b2) | (~cells & ~b4 & b2 & b1) | (cells & (mask ^ m)) | (cells & ~m2)) & (cells | ~(mask ^ m)) & (cells | m2); //CGoL evolution, partially including stator
	    gen++;
	}
};

//To make things a bit easier in stator_test_1():

struct Pair{
	uint16_t x;
	uint16_t y;
	inline Pair(){}
	inline Pair(uint16_t xx, uint16_t yy){
		x = xx;
		y = yy;
	}
	inline friend Pair operator+(Pair a, Pair b){
		return Pair(a.x+b.x, a.y+b.y);
	}
};

Pair nbhd[9] = {Pair(-1,-1), Pair(-1,0), Pair(-1,1),
                Pair(0,-1) ,             Pair(0,1) ,
                Pair(1,-1) , Pair(1,0) , Pair(1,1)  },* stator;

void gen_stator(){
	Cells c(m);
	int ctr = 0;
	stator = new Pair[20];
	for(int i = 0; i < 8; i++){
		for(int j = 0; j < 8; j++){
			if(c.getcell(i, j)){
				stator[ctr] = Pair(i, j);
				ctr++;
			}
		}
	}
}

void delete_stator(){
	delete[] stator;
}

//Currently unimplemented
std::string canonize_osc(uint64_t cs, int16_t pd){
	return "#";
}

//A prefiltering step that performs sanity checks on preliminary results. CGoL is currently assumed -- this step would probably have to be removed in order to change that.
bool stator_test_1(uint64_t cs, int16_t pd){
	uint16_t min[20], max[20], tempsum;
	Cells c(cs);
	Pair temploc;
	//for(int i = 0; i < 20; i++) min[i] = max[i] = 0;
	for(int i = 0; i < pd; i++){
		for(int j = 0; j < 20; j++){
			tempsum = 0;
			for(int k = 0; k < 8; k++){
				temploc = stator[j] + nbhd[k];
				tempsum += c.getcell(temploc.x, temploc.y);
				//std::cout << "K " << k << " " << temploc.x << " " << temploc.y << " " << tempsum << std::endl;
			}
			if(c.getcell(stator[j].x, stator[j].y) && (tempsum > 3)) return false;
			if(i){
				//std::cout << tempsum << " " << min[j] << " " << max[j] << std::endl;
				if(c.getcell(stator[j].x, stator[j].y) && ((tempsum - min[j]) > 1 || (max[j] - tempsum) > 1)) return false;
				if(tempsum < min[j]) min[j] = tempsum;
				if(tempsum > max[j]) max[j] = tempsum;
			}
			else min[j] = max[j] = tempsum;
		}
		c.step();
	}
	return true;
}

void print_state(uint64_t q){
	Cells c(q);
	for(int i = 0; i < 8; i++){
		for(int j = 0; j < 8; j++){
			std::cout << c.getcell(i, j);
		}
		std::cout << std::endl;
	}
}

//Currently unused:
Pair sides[4][14] = {{Pair(0,0), Pair(0,1), Pair(0,2), Pair(0,3), Pair(0,4), Pair(0,5), Pair(0,6), Pair(0,7),
                      Pair(1,0),                                                                   Pair(1,7),
                      Pair(2,0),                                                                   Pair(2,7),
                      Pair(3,0),                                                                   Pair(3,7)},
                     
                     {Pair(4,0),                                                                   Pair(4,7),
                      Pair(5,0),                                                                   Pair(5,7),
                      Pair(6,0),                                                                   Pair(6,7),
                      Pair(7,0), Pair(7,1), Pair(7,2), Pair(7,3), Pair(7,4), Pair(7,5), Pair(7,6), Pair(7,7)},
                      
                     {Pair(0,0), Pair(0,1), Pair(0,2), Pair(0,3),
                      Pair(1,0),
                      Pair(2,0),
                      Pair(3,0),
                      Pair(4,0),
                      Pair(5,0),
                      Pair(6,0),
                      Pair(7,0), Pair(7,1), Pair(7,2), Pair(7,3)},
                      
                     {Pair(0,4), Pair(0,5), Pair(0,6), Pair(0,7),
                                                       Pair(1,7),
                                                       Pair(2,7),
                                                       Pair(3,7),
                                                       Pair(4,7),
                                                       Pair(5,7),
                                                       Pair(6,7),
                      Pair(7,4), Pair(7,5), Pair(7,6), Pair(7,7)}
};

Pair sides2[4][8] = {{Pair(1,1), Pair(1,2), Pair(1,3), Pair(1,4), Pair(1,5), Pair(1,6),
                      Pair(2,1),                                             Pair(2,6)},
                      
                     {Pair(5,1),                                             Pair(5,6),
                      Pair(6,1), Pair(6,2), Pair(6,3), Pair(6,4), Pair(6,5), Pair(6,6)},
                      
                     {Pair(1,1), Pair(1,2),
                      Pair(2,1),
                      Pair(3,1),
                      Pair(4,1),
                      Pair(5,1),
                      Pair(6,1), Pair(6,2)},
                      
                     {Pair(1,5), Pair(1,6),
                                 Pair(2,6),
                                 Pair(3,6),
                                 Pair(4,6),
                                 Pair(5,6),
                      Pair(6,5), Pair(6,6)}
};

//These two functions were originally my more advanced stator tests, but they proved too hard to debug, so I switched to a simpler approach for stator_test_2c

/*bool stator_test_2a(uint64_t cs, int16_t pd, int s){
	uint16_t tempsum;
	Cells c(cs);
	Pair temploc;
	//print_state(cs);
	//for(int i = 0; i < 20; i++) min[i] = max[i] = 0;
	for(int i = 0; i < pd; i++){
		for(int j = 0; j < 8; j++){
			tempsum = 0;
			for(int k = 0; k < 8; k++){
				temploc = sides2[s][j] + nbhd[k];
				tempsum += (cs>>((temploc.y<<3)|temploc.x))&1;//"tempsum += c.getcell(temploc.x, temploc.y);" isn't working for some reason.
				print_state(cs);
				std::cout << c.getcell(sides2[s][j].x, sides2[s][j].y) << " " << c.getcell(temploc.x, temploc.y) << " K " << k << " " << temploc.x << " " << temploc.y << " " << tempsum << " " << s << std::endl;
			}
			if((c.getcell(sides2[s][j].x, sides2[s][j].y) && !(tempsum == 3 || tempsum == 2)) || (!c.getcell(sides2[s][j].x, sides2[s][j].y) && tempsum == 3)) return false;
		}
		c.step();
	}
	//std::cout << "\nSuccess\n";
	return true;
}

bool stator_test_2b(uint64_t cs, int16_t pd, int s){
	uint16_t tempsum;
	Cells c(cs);
	Pair temploc;
	//for(int i = 0; i < 20; i++) min[i] = max[i] = 0;
	for(int j = 0; j < 14; j++){
		tempsum = 0;
		for(int k = 0; k < 8; k++){
			temploc = sides[s][j] + nbhd[k];
			tempsum += c.getcell(temploc.x, temploc.y);
			//std::cout << "K " << k << " " << temploc.x << " " << temploc.y << " " << tempsum << std::endl;
		}
		if(c.getcell(sides[s][j].x, sides[s][j].y) && (tempsum > 3)) return false;
	}
	return true;
}*/

//Evolve oscillators through a full period to make sure stator really is stator
bool stator_test_2c(uint64_t cs, uint64_t mask, int16_t pd){
	Cells c(cs), c0(cs);
	/*std::cout << "\nQ\n";
	print_state(c.getcells());
	std::cout << "\n";*/
	for(int16_t i = 0; i < pd; i++){
		c.step();
		c0.masked_step(mask);
	}
	/*print_state(c.getcells());
	std::cout << "\n";
	print_state(c0.getcells());
	std::cout << "\nR\n";*/
	return c.getcells() == c0.getcells();
}

//Used in stator_test_2c to focus on single areas of stator
uint64_t masks[4] = {0x6020202020600uLL, 0x60404040406000uLL, 0x427E00uLL, 0x7E420000000000uLL};

//Test four overlapping regions of stator to ensure that they can be supported by adequate casing
bool stator_test_2(uint64_t cs, int16_t pd){
	Cells c(cs);
	uint16_t j;
	//int16_t l;
	//for(int i = 0; i < 4; i++) print_state(masks[i]);
	for(int i = 0; i < 4; i++){
		for(j = 0; j < 1<<14; j++){
			for(int k = 0; k < 14; k++){
				c.setcell(sides[i][k].x, sides[i][k].y, (j>>k)&1);
			}
			//std::cout << j;
			if(stator_test_2c(c.getcells(), masks[i], pd)) break;
			//if(l == pd) break;
			//if(stator_test_2a(c.getcells(), pd, i)) if(stator_test_2b(c.getcells(), pd, i)) break;
		}
		if(j == 1<<14) return false;
		//print_state(c.getcells());
		//std::cout << i << "\n";
		for(int k = 0; k < 14; k++){
			c.setcell(sides[i][k].x, sides[i][k].y, 0);
		}
	}
	return true;
}

//Filter periodic from eventually-periodic
int16_t test_cells(uint64_t cs){
	Cells c(_36264(cs));
	std::vector<uint64_t> prevstates;
	
	prevstates.push_back(c.getcells());
	
	for(;;){
		//Advance
		c.step();
		prevstates.push_back(c.getcells());
		//print_state(c.getcells());
		
		//Check for periodicity
		for(uint16_t i = 0; i < c.getgen(); i++){
			if(prevstates[c.getgen()] == prevstates[i]){
				if(i) return -1; //Only track oscillators, not their predecessors
				return c.getgen();
			}
		}
	}
}

int main(int argc, char** argv){
	int16_t pd;
	int32_t oct = 0, pdcts[32768];
	gen_stator();
	for(int16_t i = 0; i >= 0; pdcts[i++] = 0);
	for(uint64_t i = 0; i < 1uLL<<36; i++){
		//print_state(_36264(i));
		if(orient_first(_36264(i))){
			pd = test_cells(i);
			if(pd > 1) if(stator_test_1(_36264(i), pd)) if(stator_test_2(_36264(i), pd)){
				print_state(_36264(i));
				std::cout << "Oscillator found (p" << pd << ")\n\n";
				pdcts[pd]++;
				oct++;
			}
		}
		if(!(i % 16384)){
			std::cout << i << " patterns tested, " << oct << " oscillators found:";
			for(int16_t i = 0; i >= 0; i++){
				if(pdcts[i]) std::cout << "\n\t" << pdcts[i] << " period " << i;
			}
			std::cout << std::endl;
		}
	}
	delete_stator();
	return 0;
}