// Program for computing types in T_5 \ T_4 and the embeddability ordering of these types
// William D. Gillam 2004.

#include <iostream.h>
#include <string.h>

bool validtype(int b[]); // Checks that b[] is actually a type
void printtype(int b[]); // Prints the type b[] in the human readable form from "Computability of a topological poset" Section 3.
bool isleq(int b[], int n); // Returns true if the type b[] is <= cannonical type number n (0 <= n <= 30)
bool isgeq(int b[], int n); // Returns true if the type b[] is >= cannonical type number n (0 <= n <= 30)

int main() {

bool printtypes=1;
bool calcemb=1;
cout << endl << "Do you want to print the types? (0/1): ";
cin >> printtypes;
cout << "Calculate Embeddability Equivalence Classes? (0/1): ";
cin >> calcemb;

if (printtypes) cout << endl << "$(1_0 2_0 3_0 , " << "\\" << "emptyset)$ (The Locally Compact Type)" << endl;

int total=1; // Count the number of types... start with 1 for the locally-compact type
// We won't generate the locally-compact type below... we only generate the types with 1_0 in B;
// the locally-compact type is the only type (A,B) without 1_0 in B

int totalclass[31]={1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
// Count the number of types in each embeddability equiv class
// Start with 1 element in the locally-compact class since we won't generate that element below
// These classes are numbered according to Section 3 of "Computability of a topological poset"


int f[11]={0,0,0,0,0,0,0,0,0,0,0};  //Candidate for an element of T_5\T_4
// We interpret this as follows:
// f will represent the type (A,B) where:
// If f[i]=0 then i is in neither A nor B
// If f[i]=1 then i is in A but not B
// If f(i)=2 then i is in A and B
// (We need only check types of this form)
// Our convention on numbering the types is:
//
// 0 = 2_0
// 1 = 2_1
// 2 = 3_0 
// 3 = 3_1
// 4 = 3_2
// 5 = 3_3
// 6 = 3_4
// 7 = 3_5
// 8 = 3_6
// 9 = 3_7
// 10 = 3_8 (see Section 3 of "Computability of a topological poset")

int a[11]={0,0,0,0,0,0,0,0,0,0,0};

//Generate all elements of 3^11:

for (a[10]=0; a[10]<3; a[10]++) {
f[10]=a[10];
for (a[9]=0; a[9]<3; a[9]++) {
f[9]=a[9];
for (a[8]=0; a[8]<3; a[8]++) {
f[8]=a[8];
for (a[7]=0; a[7]<3; a[7]++) {
f[7]=a[7];
for (a[6]=0; a[6]<3; a[6]++) {
f[6]=a[6];
for (a[5]=0; a[5]<3; a[5]++) {
f[5]=a[5];
for (a[4]=0; a[4]<3; a[4]++) {
f[4]=a[4];
for (a[3]=0; a[3]<3; a[3]++) {
f[3]=a[3];
for (a[2]=0; a[2]<3; a[2]++) {
f[2]=a[2];
for (a[1]=0; a[1]<3; a[1]++) {
f[1]=a[1];
for (a[0]=0; a[0]<3; a[0]++) {
f[0]=a[0];

//Test the element we generated to see if it is okay.  If desired, print it.

if (validtype(f)) {
	total++;
	if (printtypes) printtype(f);
	if (calcemb) {
		int c=0;
		int numequivtypes=0; //Number of embeddability equiv classes f is in.  Should be 1!!
		for (c=0; c<31; c++) {
			if (isleq(f,c) and isgeq(f,c)) {
				numequivtypes++;
				totalclass[c]++;
				if (printtypes) cout << "Is in embeddability equivalence class " << c << endl;
			}
		}
		if (!(numequivtypes==1)) { //Something is wrong.  Give an error message and abort the whole program
			cout << "There was an error with the type:" << endl;
			printtype(f);
			if (numequivtypes==0) cout << "It isn't embeddability equivalent to anything!" << endl;
			if (numequivtypes>1) {
				cout << "It appears to be embeddability equivalent to the following types: ";
				int d=0;
				for (d=0; d<31; d++) {
					if (isleq(f,d) and isgeq(f,d)) cout << d << " ";
				}
				cout << endl;
			}
			return -1;
		}
	}
}

}}}}}}}}}}}

cout << endl << "|T_5" << "\\" << "T_4| = " << total << endl;

//Print the number of types in each embeddability equivalence class:

int e=0;
for (e=0; e<31; e++) if (calcemb) cout << "Embeddability class " << e << " has " << totalclass[e] << " types." << endl;

//Double check to make sure totalclass[0] + totalclass[1] + ... + totalclass[30] = total.

int checktotal=0;
int l=0;
for (l=0; l<31; l++) checktotal+=totalclass[l];

if (!(checktotal==total) and (calcemb)) cout << "Error: Totals don't match!!" << endl;

return 0;
}

bool validtype(int b[]) {

//First check Condition (i):
if (b[2]==0 and b[3]==0 and b[4]==0 and b[5]==0 and b[6]==0 and b[7]==0 and b[8]==0 and b[9]==0 and b[10]==0) return 0;

//Next check Condition (iii)
if (b[2]>0 and b[0]==0) return 0;
if (b[3]>0 and b[0]==0) return 0;
if (b[4]>0 and b[0]<2) return 0; 
if (b[5]>0 and b[1]==0) return 0;
if (b[6]>0 and b[1]<2) return 0;
if (b[7]>0 and (b[0]==0 or b[1]==0)) return 0;
if (b[8]>0 and (b[0]<2 or b[1]==0)) return 0;
if (b[9]>0 and (b[0]==0 or b[1]<2)) return 0;
if (b[10]>0 and (b[0]<2 or b[1]<2)) return 0;

//And Finally, Condition (iv)
if ((b[2]==2 or b[3]==2 or b[4]==2) and b[0]<2) return 0;
if ((b[5]==2 or b[6]==2) and b[1]<2) return 0;
if ((b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[0]<2 or b[1]<2)) return 0;


return 1;
}

void printtype(int b[]) {

cout << "$( 1_0";

if (b[0]>0) cout << " 2_0";
if (b[1]>0) cout << " 2_1";
if (b[2]>0) cout << " 3_0";
if (b[3]>0) cout << " 3_1";
if (b[4]>0) cout << " 3_2";
if (b[5]>0) cout << " 3_3";
if (b[6]>0) cout << " 3_4";
if (b[7]>0) cout << " 3_5";
if (b[8]>0) cout << " 3_6";
if (b[9]>0) cout << " 3_7";
if (b[10]>0) cout << " 3_8";

cout << " , 1_0";

if (b[0]==2) cout << " 2_0";
if (b[1]==2) cout << " 2_1";
if (b[2]==2) cout << " 3_0";
if (b[3]==2) cout << " 3_1";
if (b[4]==2) cout << " 3_2";
if (b[5]==2) cout << " 3_3";
if (b[6]==2) cout << " 3_4";
if (b[7]==2) cout << " 3_5";
if (b[8]==2) cout << " 3_6";
if (b[9]==2) cout << " 3_7";
if (b[10]==2) cout << " 3_8";

cout << " \\" << "})$" << endl;

return;
}

bool isleq(int b[], int n) {

// Check if the class of the type represented by f is <= embeddability class number n
// Assumes that b[] is actually a valid type

//Error check:
if (n<0 or n>30) cout << "Error: Function isleq called with unacceptable value: " << n << endl; 

switch (n) {
case 0: if (b[4]>0 or b[5]>0 or b[6]>0 or b[7]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[1]==2 or b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 1: if (b[5]>0 or b[6]>0 or b[7]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[1]==2 or b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 2: if (b[4]>0 or b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[1]==2 or b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 3: if (b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[1]==2 or b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 4: if (b[6]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[1]==2 or b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 5: if (b[4]>0 or b[5]>0 or b[6]>0 or b[7]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 6: if (b[5]>0 or b[6]>0 or b[7]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 7: if (b[4]>0 or b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 8: if (b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 9: if (b[6]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 10: if (b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 11: if (b[4]>0 or b[5]>0 or b[6]>0 or b[7]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 12: if (b[5]>0 or b[6]>0 or b[7]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 13: if (b[4]>0 or b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 14: if (b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 15: if (b[6]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 16: if (b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 17: if (b[5]>0 or b[6]>0 or b[7]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 18: if (b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 19: if (b[6]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 20: if (b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 21: if (b[4]>0 or b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[4]==2 or b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 22: if (b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[4]==2 or b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 23: if (b[6]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[4]==2 or b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 24: if (b[4]==2 or b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 25: if (b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 26: if (b[6]>0 or b[9]>0 or b[10]>0) return 0;
	if (b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 27: if (b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 28: if (b[6]>0 or b[9]>0 or b[10]>0) return 0;
	return 1;
case 29: if (b[6]==2 or b[9]==2 or b[10]==2) return 0;
	return 1;
case 30: return 1;
}
}

bool isgeq(int b[], int n) {

// Check if the class of the type represented by f is >= embeddability class n
// Assumes that b[] is actually a valid type

//Error check:
if (n<0 or n>30) cout << "Error: isgeq called with an invalid number: " << n << endl;

switch (n) {
case 0: return 1;
case 1: if (b[4]>0 or b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 1; return 0;
case 2: if (b[5]>0 or b[6]>0 or b[7]>0 or b[8]>0 or b[9]>0 or b[10]>0) return 1; return 0;
case 3: if ((b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0) or (b[4]>0 and (b[5]>0 or b[7]>0))) return 1; return 0;
case 4: if (b[8]>0 or b[6]>0 or b[9]>0 or b[10]>0) return 1; return 0;
case 5: if (b[1]==2 or b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 1; return 0;
case 6: if ((b[1]==2 or b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[4]>0 or b[6]>0 or b[8]>0 or 		b[9]>0 or b[10]>0)) return 1; return 0;
case 7: if ((b[1]==2 or b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[5]>0 or b[6]>0 or b[7]>0 or 		b[8]>0 or b[9]>0 or b[10]>0)) return 1; return 0;
case 8: if ((b[1]==2 or b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) and ((b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0) or ((b[4]>0) and (b[5]>0 or b[7]>0)))) return 1; return 0;
case 9: if ((b[1]==2 or b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[6]>0 or b[8]>0 or b[9]>0 or 		b[10]>0)) return 1; return 0;
case 10: if ((b[1]==2 or b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[6]>0 or b[9]>0 or b[10]>0)) 		return 1; return 0;
case 11: if (b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 1; return 0;
case 12:  if ((b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[4]>0 or b[6]>0 or b[8]>0 or 			b[9]>0 or b[10]>0)) return 1; return 0;
case 13: if ((b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[5]>0 or b[6]>0 or b[7]>0 or 			b[8]>0 or b[9]>0 or b[10]>0)) return 1; return 0;
case 14: if ((b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) and ((b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0) or ((b[4]>0) and (b[5]>0 or b[7]>0)))) return 1; return 0;
case 15: if ((b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[6]>0 or b[8]>0 or b[9]>0 or 			b[10]>0)) return 1; return 0;
case 16:  if ((b[2]==2 or b[3]==2 or b[4]==2 or b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[6]>0 or b[9]>0 or b[10]>0)) 			return 1; return 0;
case 17: if (b[4]==2 or b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 1; return 0;
case 18: if ((b[4]==2 or b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[5]>0 or b[6]>0 or b[7]>0 or b[8]>0 or b[9]>0 or b[10]>0)) return 1; return 0;
case 19: if ((b[4]==2 or b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0)) return 1; return 0;
case 20: if ((b[4]==2 or b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[6]>0 or b[9]>0 or b[10]>0)) return 1; return 0;
case 21: if (b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 1; return 0;
case 22: if ((b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[4]>0 or b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0)) return 1; return 0;
case 23: if ((b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0)) return 1; return 0;
case 24: if ((b[5]==2 or b[6]==2 or b[7]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[6]>0 or b[9]>0 or b[10]>0)) return 1; return 0;
case 25: if ((b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) or (b[4]==2 and (b[5]==2 or b[7]==2))) return 1; return 0;
case 26: if (((b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) or (b[4]==2 and (b[5]==2 or b[7]==2))) and (b[6]>0 or b[8]>0 or b[9]>0 or b[10]>0)) return 1; return 0;
case 27: if (((b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) or (b[4]==2 and (b[5]==2 or b[7]==2))) and (b[6]>0 or b[9]>0 or b[10]>0)) return 1; return 0;
case 28: if (b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) return 1; return 0;
case 29: if ((b[6]==2 or b[8]==2 or b[9]==2 or b[10]==2) and (b[6]>0 or b[9]>0 or b[10]>0)) return 1; return 0;
case 30: if (b[6]==2 or b[9]==2 or b[10]==2) return 1; return 0;
}
}