// main.c
// Copyright (C) 2023 Mark Bowron

// Figure 6 is complete and no Table 10 counterexamples are found.

// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.


#include    <stdio.h>
#include    <stdlib.h>
#include    <inttypes.h>
#include    <stdbool.h>
#include    <string.h>
#include    "set_operators.h"
#include    "set_families.h"
#include    "set_relations.h"
#include    "collapses.h"
#include    "topologies.h"


int main(int argc, const char * argv[])
{
    FILE       *input;
    uint32_t   *point_closures, set;
    int         j, k, psi, spacesize = 8, space = 0;
    int       **psi_implications, **figure_six;
    int       **psi_reduced, **figure_six_reduced;
    int        *psi_in_space;

// canon[n] maps 0,...,41 to the least psi-number in each box in Figure 6 in
// increasing order.

    static const int canon[42] = {1,2,3,5,6,7,8,9,10,11,12,13,21,23,24,26,
                                    27,28,30,31,32,34,35,38,39,40,41,42,45,
                                    46,49,53,54,57,58,59,61,62,64,65,68,69};

// Allocate memory for the structs that store KFZ(A) and KF(A) for all A in X.

    KFZ        *kfz = CreateKFZ(spacesize);
    KF         *kf = CreateKF(spacesize);

    psi_implications = (int **)malloc(71 * sizeof(int *));
    if (psi_implications==0)
    {
        printf("\nCould not allocate space for psi_implications.\n");
        exit(0);
    }
    figure_six = (int **)malloc(71 * sizeof(int *));
    if (figure_six==0)
    {
        printf("\nCould not allocate space for figure_six.\n");
        exit(0);
    }
    for (j=0; j<71; j++)
    {
        psi_implications[j] = (int *)malloc(71 * sizeof(int));
        if (psi_implications[j]==0)
        {
            printf("\nCould not allocate space for psi_implications[%d].\n", j);
            exit(0);
        }

        figure_six[j] = (int *)malloc(71 * sizeof(int));
        if (figure_six[j]==0)
        {
            printf("\nCould not allocate space for figure_six[%d].\n", j);
            exit(0);
        }
        for (k=0; k<71; k++)
        {

// We initially assume every psi-number's presence implies that of every other
// psi-number, then falsify the implications that don't hold in general.

            psi_implications[j][k] = 1;

// figure_six[j][k] is the adjacency matrix of the partial order in Figure 6.
// We initialize it to 0, add every edge in the poset diagram, then apply Warshall's
// algorithm to get the transitive closure.

            figure_six[j][k] = 0;
        }
    }

// The 72 edges below were obtained from the LaTeX source for Figure 6.

    figure_six[1][7] = 1;
    figure_six[2][11] = 1;
    figure_six[2][39] = 1;
    figure_six[3][8] = 1;
    figure_six[3][10] = 1;
    figure_six[5][12] = 1;
    figure_six[5][39] = 1;
    figure_six[6][13] = 1;
    figure_six[6][39] = 1;
    figure_six[7][35] = 1;
    figure_six[7][39] = 1;
    figure_six[7][57] = 1;
    figure_six[8][28] = 1;
    figure_six[8][35] = 1;
    figure_six[8][39] = 1;
    figure_six[9][24] = 1;
    figure_six[10][28] = 1;
    figure_six[10][35] = 1;
    figure_six[11][26] = 1;
    figure_six[12][30] = 1;
    figure_six[12][35] = 1;
    figure_six[13][31] = 1;
    figure_six[13][49] = 1;
    figure_six[21][32] = 1;
    figure_six[21][34] = 1;
    figure_six[21][39] = 1;
    figure_six[23][35] = 1;
    figure_six[23][57] = 1;
    figure_six[24][35] = 1;
    figure_six[24][57] = 1;
    figure_six[26][35] = 1;
    figure_six[26][57] = 1;
    figure_six[27][42] = 1;
    figure_six[27][49] = 1;
    figure_six[27][57] = 1;
    figure_six[28][42] = 1;
    figure_six[28][49] = 1;
    figure_six[28][57] = 1;
    figure_six[30][42] = 1;
    figure_six[31][46] = 1;
    figure_six[31][62] = 1;
    figure_six[32][35] = 1;
    figure_six[32][40] = 1;
    figure_six[32][41] = 1;
    figure_six[34][35] = 1;
    figure_six[34][41] = 1;
    figure_six[35][42] = 1;
    figure_six[35][49] = 1;
    figure_six[38][40] = 1;
    figure_six[38][45] = 1;
    figure_six[39][49] = 1;
    figure_six[40][64] = 1;
    figure_six[41][42] = 1;
    figure_six[41][64] = 1;
    figure_six[42][62] = 1;
    figure_six[45][46] = 1;
    figure_six[45][58] = 1;
    figure_six[46][59] = 1;
    figure_six[46][64] = 1;
    figure_six[49][62] = 1;
    figure_six[53][54] = 1;
    figure_six[53][64] = 1;
    figure_six[54][65] = 1;
    figure_six[57][62] = 1;
    figure_six[58][59] = 1;
    figure_six[59][68] = 1;
    figure_six[61][69] = 1;
    figure_six[62][65] = 1;
    figure_six[64][65] = 1;
    figure_six[64][68] = 1;
    figure_six[65][69] = 1;
    figure_six[68][69] = 1;

// There are 43 dual classes of psi-numbers but Figure 6 only contains 42 boxes
// since one of them contains two dual classes.

    psi_reduced = (int **)malloc(42 * sizeof(int *));
    if (psi_reduced==0)
    {
        printf("\nCould not allocate space for psi_reduced.\n");
        exit(0);
    }
    figure_six_reduced = (int **)malloc(42 * sizeof(int *));
    if (figure_six_reduced==0)
    {
        printf("\nCould not allocate space for figure_six_reduced.\n");
        exit(0);
    }
    for (j=0; j<42; j++)
    {
        psi_reduced[j] = (int *)malloc(42 * sizeof(int));
        if (psi_reduced[j]==0)
        {
            printf("\nCould not allocate space for psi_reduced[%d].\n", j);
            exit(0);
        }
        figure_six_reduced[j] = (int *)malloc(42 * sizeof(int));
        if (figure_six_reduced[j]==0)
        {
            printf("\nCould not allocate space for figure_six_reduced[%d].\n", j);
            exit(0);
        }
        for (k=0; k<42; k++)
        {
            psi_reduced[j][k] = 0;
            figure_six_reduced[j][k] = 0;
        }
    }

    psi_in_space = (int *)malloc(71 * sizeof(int));
    if (psi_in_space==0)
    {
        printf("\nCould not allocate space for psi_in_space.\n");
        exit(0);
    }
    for (k=0; k<71; k++) psi_in_space[k] = 0;

// The input file contains all spaces up to homeomorphism.

    input = fopen("8-spaces.txt", "r");
    if (input==0)
    {
        printf("\nCould not open file 8-spaces.txt.\n");
        exit(0);
    }

// Sets are represented by unsigned 32-bit binary integers with leading zeros.
// Assuming X = {0,1,...,n-1} the element k is in A iff the coefficient of 2^k in the
// binary integer representing A is 1 (i.e., the bits of the binary integer representing
// A are in reverse order compared to X).

    point_closures = (uint32_t *)malloc(spacesize * sizeof(uint32_t));
    if (point_closures==0)
    {
        printf("\nCould not allocate space for point_closures.\n");
        exit(0);
    }

    while (space < spaces[spacesize])
    {

// This program interprets each line of input as closures of singletons.
// Alternatively, we could interpret each line as smallest open neighborhoods.
// Either interpretation yields all nonhomeomorphic 8-spaces, but any given line
// does not in general produce homeomorphic spaces under the two interpretations.

// Read the current line of input into the point_closures array.

        for (j=0; j<spacesize; j++) fscanf(input, "%" PRIu32, &point_closures[j]);

// Compute KFZ(A) and store the result in kfz.

        ComputeKF(kf,spacesize,point_closures);
        CopyKFZfromKF(kfz,kf,spacesize);

        for (set=0; set<(one<<spacesize); set++)
        {
            psi = Psi(set,spacesize,kfz);

// Set psi_in_space[n] equal to 1 iff X has a subset A such that psi(A) = n.

            psi_in_space[psi] = 1;

// Confirm that every entry with Boolean set operators in Table 10 holds.

            switch (psi)
            {
                case 1:

// Just one of the following equations needs to hold.

                    if (Psi(kf->_id[set] & kf->_aff[set],spacesize,kfz) == 7) break;
                    if (Psi(kf->_a[set] & kf->_aff[set],spacesize,kfz) == 7) break;
                    printf("Error: 1 => 7 failed.\n");
                    exit(0);
                case 2:
                    if (Psi(kf->_id[set] & kf->_ib[set],spacesize,kfz) != 11)
                    {
                        printf("Error: 2 => 11 failed.\n");
                        exit(0);
                    }
                    if (Psi(kf->_id[set] | kf->_if[set],spacesize,kfz) != 39)
                    {
                        printf("Error: 2 => 39 failed.\n");
                        exit(0);
                    }
                    break;
                case 3:
                    if (Psi(kf->_id[set] & kf->_ib[set],spacesize,kfz) != 8)
                    {
                        printf("Error: 3 => 8 failed.\n");
                        exit(0);
                    }
                    if (Psi((kf->_id[set] & kf->_if[set]) | kf->_ab[set],spacesize,kfz) != 10)
                    {
                        printf("Error: 3 => 10 failed.\n");
                        exit(0);
                    }
                    break;
                case 5:
                    if (Psi(kf->_id[set] & kf->_ib[set],spacesize,kfz) != 12)
                    {
                        printf("Error: 5 => 12 failed.\n");
                        exit(0);
                    }
                    if (Psi(kf->_id[set] | kf->_if[set],spacesize,kfz) != 39)
                    {
                        printf("Error: 5 => 39 failed.\n");
                        exit(0);
                    }
                    break;
                case 6:
                    if (Psi(kf->_id[set] & kf->_ib[set],spacesize,kfz) != 13)
                    {
                        printf("Error: 6 => 13 failed.\n");
                        exit(0);
                    }
                    if (Psi(kf->_id[set] | kf->_if[set],spacesize,kfz) != 39)
                    {
                        printf("Error: 6 => 39 failed.\n");
                        exit(0);
                    }
                    break;
                case 7:
                    if (Psi(kf->_i[set] | kf->_fb[set],spacesize,kfz) != 39)
                    {
                        printf("Error: 7 => 39 failed.\n");
                        exit(0);
                    }

// Just one of the following equations needs to hold.

                    if (Psi(kf->_ib[set] & kf->_bif[set],spacesize,kfz) == 57) break;
                    if (Psi(kf->_ib[set] | kf->_bif[set],spacesize,kfz) == 57) break;
                    if (Psi(kf->_abi[set] | kf->_bif[set],spacesize,kfz) == 57) break;
                    printf("Error: 7 => 57 failed.\n");
                    exit(0);
                case 8:
                    if (Psi(kf->_id[set] | kf->_bi[set],spacesize,kfz) != 28)
                    {
                        printf("Error: 8 => 28 failed.\n");
                        exit(0);
                    }
                    if (Psi(kf->_i[set] | kf->_fib[set],spacesize,kfz) != 39)
                    {
                        printf("Error: 8 => 39 failed.\n");
                        exit(0);
                    }
                    break;
                case 9:
                    if (Psi((kf->_id[set] & kf->_if[set]) | kf->_ab[set],spacesize,kfz) != 24)
                    {
                        printf("Error: 9 => 24 failed.\n");
                        exit(0);
                    }
                    break;
                case 10:
                    if (Psi((kf->_id[set] & kf->_if[set]) | kf->_ab[set],spacesize,kfz) != 28)
                    {
                        printf("Error: 10 => 28 failed.\n");
                        exit(0);
                    }
                    break;
                case 11:
                    if (Psi(kf->_id[set] | kf->_bi[set],spacesize,kfz) != 26)
                    {
                        printf("Error: 11 => 26 failed.\n");
                        exit(0);
                    }
                    break;
                case 12:
                    if (Psi(kf->_id[set] | kf->_bi[set],spacesize,kfz) != 30)
                    {
                        printf("Error: 12 => 30 failed.\n");
                        exit(0);
                    }
                    break;
                case 13:
                    if (Psi(kf->_id[set] | kf->_bi[set],spacesize,kfz) != 31)
                    {
                        printf("Error: 13 => 31 failed.\n");
                        exit(0);
                    }
                    break;
                case 21:
                    if (Psi(kf->_id[set] | kf->_bi[set],spacesize,kfz) != 32)
                    {
                        printf("Error: 21 => 32 failed.\n");
                        exit(0);
                    }
                    if (Psi(kf->_id[set] & kf->_ib[set],spacesize,kfz) != 34)
                    {
                        printf("Error: 21 => 34 failed.\n");
                        exit(0);
                    }
                    if (Psi(kf->_i[set] | kf->_fb[set],spacesize,kfz) != 39)
                    {
                        printf("Error: 21 => 39 failed.\n");
                        exit(0);
                    }
                    break;
                case 23:
                case 24:
                    if (Psi((kf->_id[set] & kf->_ib[set]) | kf->_ab[set],spacesize,kfz) != 35)
                    {
                        printf("Error: 23,24 => 35 failed.\n");
                        exit(0);
                    }
                    if (Psi(kf->_ib[set] | kf->_bi[set],spacesize,kfz) != 57)
                    {
                        printf("Error: 23,24 => 57 failed.\n");
                        exit(0);
                    }
                    break;
                case 26:
                    if (Psi((kf->_id[set] & kf->_ib[set]) | kf->_ab[set],spacesize,kfz) != 35)
                    {
                        printf("Error: 26 => 35 failed.\n");
                        exit(0);
                    }
                    if (Psi(kf->_ib[set] | kf->_bif[set],spacesize,kfz) != 57)
                    {
                        printf("Error: 26 => 57 failed.\n");
                        exit(0);
                    }
                    break;
                case 27:
                    if (Psi(kf->_i[set] | kf->_if[set],spacesize,kfz) != 51)
                    {
                        printf("Error: 27 => 51 failed.\n");
                        exit(0);
                    }
                    if (Psi(kf->_if[set] | kf->_fi[set],spacesize,kfz) != 57)
                    {
                        printf("Error: 27 => 57 failed.\n");
                        exit(0);
                    }
                    break;
                case 28:
                    if (Psi((kf->_if[set] | kf->_ab[set]) | kf->_ab[set],spacesize,kfz) != 51)
                    {
                        printf("Error: 28 => 51 failed.\n");
                        exit(0);
                    }
                    if (Psi(kf->_ib[set] | kf->_bi[set],spacesize,kfz) != 57)
                    {
                        printf("Error: 28 => 57 failed.\n");
                        exit(0);
                    }
                    break;
                case 31:
                    if (Psi((kf->_id[set] & kf->_ib[set]) | kf->_ab[set],spacesize,kfz) != 46)
                    {
                        printf("Error: 31 => 46 failed.\n");
                        exit(0);
                    }
                    break;
                case 32:
                    if (Psi(kf->_fi[set] | kf->_ab[set],spacesize,kfz) != 40)
                    {
                        printf("Error: 32 => 40 failed.\n");
                        exit(0);
                    }
                    if (Psi(kf->_id[set] & kf->_ib[set],spacesize,kfz) != 41)
                    {
                        printf("Error: 32 => 41 failed.\n");
                        exit(0);
                    }
                    break;
                case 34:
                    if (Psi(kf->_id[set] | kf->_bi[set],spacesize,kfz) != 41)
                    {
                        printf("Error: 34 => 41 failed.\n");
                        exit(0);
                    }
                    break;
                case 38:
                    if (Psi(kf->_id[set] | kf->_if[set],spacesize,kfz) != 40)
                    {
                        printf("Error: 38 => 40 failed.\n");
                        exit(0);
                    }
                    if (Psi(kf->_id[set] & kf->_ib[set],spacesize,kfz) != 45)
                    {
                        printf("Error: 38 => 45 failed.\n");
                        exit(0);
                    }
                    break;
                case 41:
                    if (Psi((kf->_i[set] | kf->_if[set]),spacesize,kfz) != 64)
                    {
                        printf("Error: 41 => 64 failed.\n");
                        exit(0);
                    }
                    break;
                case 45:
                    if (Psi(kf->_id[set] | kf->_bi[set],spacesize,kfz) != 58)
                    {
                        printf("Error: 45 => 58 failed.\n");
                        exit(0);
                    }
                    break;
                case 46:
                    if (Psi(kf->_id[set] & kf->_if[set],spacesize,kfz) != 60)
                    {
                        printf("Error: 46 => 60 failed.\n");
                        exit(0);
                    }
            }
        }

// For every implication (psi(A)=j) => (some B satisfies psi(B)=k) that X falsifies,
// we set psi_implications[j][k] = 0.

        for (j=1; j<71; j++)
            for (k=0; k<j; k++)
            {
                if (psi_in_space[j] && !psi_in_space[k]) psi_implications[j][k] = 0;
                if (psi_in_space[k] && !psi_in_space[j]) psi_implications[k][j] = 0;
            }

// Reset the psi_in_space[] array to zero then go to next space.

        for (j=1; j<71; j++) psi_in_space[j] = 0;
        space++;
    }

// For simplicity we choose to work directly with the boxes in Figure 6 rather than
// indirectly with psi-numbers.  The canon[] array makes this easy.

    for (j=0; j<42; j++)
        for (k=0; k<42; k++)
        {
            psi_reduced[j][k] = psi_implications[canon[j]][canon[k]];
            if (figure_six[canon[j]][canon[k]]) figure_six_reduced[j][k] = 1;
        }

// Apply Warshall's algorithm to get the transitive closure of the edges in Figure 6.

    Warshall(figure_six_reduced,42);

// If equality holds, then Figure 6 shows all possible psi-number implications within a
// given space.

    if (matrixEqual(psi_reduced,figure_six_reduced,42))
    {
        printf("\nNo further edges hold in Figure 6 and\nno Table 10 counterexamples were found.\n\n");
    }

    fclose(input);
    for (j=0; j<71; j++)
    {
        free(psi_implications[j]);
        free(figure_six[j]);
    }
    free(psi_implications);
    free(figure_six);
    for (j=0; j<42; j++)
    {
        free(psi_reduced[j]);
        free(figure_six_reduced[j]);
    }
    free(psi_reduced);
    free(figure_six_reduced);
    free(psi_in_space);
    free(point_closures);
    FreeKFZ(kfz);
    FreeKF(kf);
}