#include <cstdint>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;

enum {RESET, SET, DONTCARE};

char *printTable[12] = {"!D", "D", "X", "!C", "C", "X", "!B", "B", "X", "!A", "A", "X"};

string variables[8] = {"((i % 2) ^ 0x01)", "(i % 2)", "(((i >> 1) % 2) ^ 0x01)", "((i >> 1) % 2)", "(((i >> 2) % 2) ^ 0x01)", "((i >> 2) % 2)", "(((i >> 3) % 2) ^ 0x01)", "((i >> 3) % 2)"};

string finalOutput = "#include <cstdio>\nint main(){for(int i=0;i<16;i++)printf(\"%c\", char(", codeEnd = "));printf(\"\\n\");}";

struct term
{
	bool beenMerged = false;
	uint8_t vals[4] = {0};
};

vector<vector<term>> sop, ret;

vector<term> reset;		// empty SOP expression used to "reset" the vector of terms before searching for overlapping terms, the optimiztion routine ends if none are found and this remains empty
term emptyTerm;

uint8_t flip;

void populate(char* in)
{
	int offset;

	sop.push_back(reset); sop.push_back(reset);

	for (int m = 0; m < 8; m++) ret.push_back(reset);

	for (int k = 0; k < 16; k++)		// iterate through 16 characters at a time...
	{
		for (int i = 0; i < 8; i++)		// generate 8 truth tables, one for each bit position in an ascii character (even if the MSB is always zero)
		{
			if ((in[k] >> i) & 0x01 == 1)		// the ith bit of the kth character is one, the boolean product representing it is appended to the return SOP
			{
				ret.at(i).push_back(emptyTerm);
				offset = ret.at(i).size() - 1;

				ret.at(i).at(offset).vals[0] = k & 0x01;		// LSB
				ret.at(i).at(offset).vals[1] = (k >> 1) & 0x01;
				ret.at(i).at(offset).vals[2] = (k >> 2) & 0x01;
				ret.at(i).at(offset).vals[3] = (k >> 3) & 0x01;		//MSB	
			}
		}
	}
}

vector<term> check_merge ()
{
	int diffTerms; uint8_t dupCache[3][3][3][3] = {0}; term temp; // eh, the dupe cache will only end up being 81 bytes...
	bool neverGonnaMergeYouDown = true;
 
	sop.at(flip) = reset;

	for (int i = 0; i < sop.at(flip ^ 1).size(); i++) // iterate through every term in the current SOP 
	{
		for (int j = i + 1; j < sop.at(flip ^ 1).size(); j++) // iterate through every term this one hasn't been compared against yet
		{
			diffTerms = 0;

			for (int k = 0; k < 4; k++) // iterate through each operand of this term's boolean product
			{
				if (sop.at(flip ^ 1).at(i).vals[k] != sop.at(flip ^ 1).at(j).vals[k]) 
				{
					diffTerms++;
					temp.vals[k] = DONTCARE;
				}
				else
					temp.vals[k] = sop.at(flip ^ 1).at(i).vals[k];
			}

			if (diffTerms == 1)	// these two terms are only one bit flip apart, merge them together
			{
				sop.at(flip ^ 1).at(i).beenMerged = true;
				sop.at(flip ^ 1).at(j).beenMerged = true;	
				neverGonnaMergeYouDown = false;	// At least one merge has taken place during this iteration  

				if (dupCache[temp.vals[3]][temp.vals[2]][temp.vals[1]][temp.vals[0]] == 0) // we keep track of terms already formed this iteration as duplicates arise in the merging process  
				{								           // the starting set of terms do not contain duplicates
					sop.at(flip).push_back(temp);
					dupCache[temp.vals[3]][temp.vals[2]][temp.vals[1]][temp.vals[0]] = 1;
				}
			}
		}

		if (sop.at(flip ^ 1).at(i).beenMerged == false)	// awww, you didn't find any terms to merge with... here honey you get to go straight into the return vector!
		{
			sop.at(flip).push_back(sop.at(flip ^ 1).at(i));
		}
	}

	if (!neverGonnaMergeYouDown)		// This version of the SOP could be optimized? Report back with any ADDITIONAL optimizations you find and remove duplicates while you're at it!
	{
		flip ^= 1;
		return check_merge();
	}
	else					// base case; this is the end of road...
		return sop.at(flip);		// since we don't want isolated terms to get dropped in the event that a merge DOES take place and the function calls itself we always append the lonely terms to sop.at(flip)
}						// in that case we might as well return it here

void print_bool(vector <term> input)
{
	if (input.size() == 0)
		printf("Ain't nothin' here except this SOPhomoric comment.");

	for (int i = 0; i < input.size(); i++)
	{
		printf("%s %s %s %s", printTable[input.at(i).vals[3] + 9], 
				      printTable[input.at(i).vals[2] + 6], 
				      printTable[input.at(i).vals[1] + 3], 
				      printTable[input.at(i).vals[0] + 0]);
		if (i != input.size() - 1)
			printf(" + ");
	}
	printf("\n\n");
}

void gen_file()
{
	bool firstChar, allOnes;

	for (int i = 0; i < 8; i++)
	{
		finalOutput += "(( ";
		allOnes = true;

		if (ret.at(i).size() == 0)
			finalOutput += "0";

		for (int j = 0; j < ret.at(i).size(); j++)
		{
			finalOutput += "( ";
			firstChar = true;
	
			for (int k = 0; k < 4; k++)
			{
				if (ret.at(i).at(j).vals[k] != 2)
				{
					if (!firstChar)
						finalOutput += " & ";
					
					finalOutput += variables[(k * 2) + ret.at(i).at(j).vals[k]]; 
					firstChar = false;
					allOnes = false;
				}
			}

			if (allOnes)
				finalOutput += "1";
		
			finalOutput += " )";

			if (j != ret.at(i).size() - 1)
				finalOutput += " | ";
		}
		
		finalOutput += " ) << "; finalOutput += char(48 + i); finalOutput += ") ";

		if (i != 7)
			finalOutput += "| ";
	}

	finalOutput += codeEnd;

	FILE* handle;
	handle = fopen("out.cpp", "wb");
	fwrite(finalOutput.c_str(), sizeof(char), finalOutput.length(), handle);
	fclose(handle);
}

int main (int iVar, char **cVar)
{
	if (iVar < 2)
	{
		printf("A string please...\n");
		return 0;
	}
	
	populate(cVar[1]);

	printf("\nSOP expressions prior to optimization:\n\n\n");
	for (int i = 0; i < 8; i++)
	{
		printf("Expression for bit #%d", i);
		if (i == 0) printf(" (LSB)"); else if (i == 7) printf(" (MSB)");
		printf("\n\n");
		print_bool(ret.at(i));
	}
	printf("\n---------------------------------------------------------------------\n\n\n");

	for (int i = 0; i < 8; i++)
	{
		flip = 0;		// this needs to be initialized to zero so that the current SOP doesn't get immediately overwritten
		sop.at(1) = ret.at(i);	
		ret.at(i) = check_merge();;
	}

	printf("SOP expressions after optimization:\n\n\n");
	for (int i = 0; i < 8; i++)
	{
		printf("Expression for bit #%d", i);
		if (i == 0) printf(" (LSB)"); else if (i == 7) printf(" (MSB)");
		printf("\n\n");
		print_bool(ret.at(i));
	}

	gen_file();
}
