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

// Verify Figure 7.

// 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"
#include    "relations_408.h"
#include    "local_orderings_496.h"


int main(int argc, const char * argv[])
{
    int   **implications, equiv, flag, j, k, m;
    int   **copy, **tc, **ab, **tr; // For transitive reduction only.
    REL    *canon = CreateREL(74);

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

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

// Find one representative for each equivalence class in Table 11.

    for (equiv=0; equiv<74; equiv++)
    {
        flag = 0;
        for (j=0; j<34; j++)
        {
            for (k=0; k<34; k++)
            {
                if (inequality_classes[j][k] == equiv+1)
                {
                    canon->_type[equiv] = 1;
                    canon->_x[equiv] = j;
                    canon->_y[equiv] = k;
                    flag = 1;
                    break;
                }
            }
            if (flag) break;
        }
        if (!flag)
        {
            for (j=0; j<34; j++)
            {
                for (k=0; k<34; k++)
                {
                    if (equation_classes[j][k] == equiv+1)
                    {
                        canon->_type[equiv] = 2;
                        canon->_x[equiv] = j;
                        canon->_y[equiv] = k;
                        flag = 1;
                        break;
                    }
                }
                if (flag) break;
            }
        }
    }

// We now test for each of the 74*73 = 5472 nontrivial implications that can hold among
// the 74 equivalence classes of relations in Table 11.  Such an implication holds in
// general if and only if it holds for each of the 496 local orderings on KF.

    for (j=0; j<74; j++)
        for (k=0; k<74; k++)
        {
            if (j == k) continue;
            if (canon->_type[j] == 1)
            {
                for (m=0; m<496; m++)
                {
                    if (local_orderings_on_kf[m][canon->_x[j]][canon->_y[j]])
                    {
                        if (!local_orderings_on_kf[m][canon->_x[k]][canon->_y[k]])
                        {
                            implications[j][k] = 0;
                            break;
                        }
                        if (canon->_type[k] == 2)
                        {
                            if (!local_orderings_on_kf[m][canon->_y[k]][canon->_x[k]])
                            {
                                implications[j][k] = 0;
                                break;
                            }
                        }
                    }
                }
            }
            else // canon[j] is an equation
            {
                for (m=0; m<496; m++)
                {
                    if (local_orderings_on_kf[m][canon->_x[j]][canon->_y[j]]*
                        local_orderings_on_kf[m][canon->_y[j]][canon->_x[j]])
                    {
                        if (!local_orderings_on_kf[m][canon->_x[k]][canon->_y[k]])
                        {
                            implications[j][k] = 0;
                            break;
                        }
                        if (canon->_type[k] == 2)
                        {
                            if (!local_orderings_on_kf[m][canon->_y[k]][canon->_x[k]])
                            {
                                implications[j][k] = 0;
                                break;
                            }
                        }
                    }
                }
            }
        }

// Our final task is to compute the transitive reduction of the implications[][] matrix.

    getTransitiveReduction(implications,copy,tc,ab,tr,74);

// Print all edges in Figure 7.

    for (j=74; j>0; j--)
    {
        for (k=0; k<74; k++)
            if (tr[j-1][k]) printf("\n%2d < %2d", j, k+1);
        if (j>8) printf("\n");
    }

    for (j=0; j<74; j++) free(implications[j]);
    free(implications);
    for (j=0; j<74; j++)
    {
        free(copy[j]);
        free(tc[j]);
        free(ab[j]);
        free(tr[j]);
    }
    free(copy);
    free(tc);
    free(ab);
    free(tr);
    FreeREL(canon);
    return EXIT_SUCCESS;
}