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

// Order psi-numbers by occurrence for a given cardinality.

// 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"

// We store both a psi-number and its count in one place with a struct.

typedef struct
{
    int psi;
    int count;
} PsiCount;

// comparRtn() is used by qsort() to sort psi-numbers in increasing order of frequency.

int comparRtn(const void *a, const void *b);


int main(int argc, const char * argv[])
{
    FILE       *input;
    uint32_t   *point_closures, set;
    int         j, spacesize = 8, space = 0;
    PsiCount  **psi_count;

// Allocate memory for the struct that stores KFZ(A) for all A in X.

    KFZ        *kfz = CreateKFZ(spacesize);

// Allocate memory for the array of pointers to a PsiCount struct
// that will be used to count the occurrences of each psi-number.

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

// The value of psi_count[j]->psi just keeps track of which psi-number
// we are counting so it never changes.

        psi_count[j]->psi = j;
        psi_count[j]->count = 0;
    }

// The input file contains all nonhomeomorphic spaces on 8 points.

    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])
    {

// Each line of input has the closure of every singleton.  These can alternatively be
// regarded as smallest open neighborhoods.  Either interpretation yields all
// nonhomeomorphic spaces of cardinality = spacesize, but any given line does not
// in general produce the same space under the two.

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

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

// We need KFZ(A) to get psi(A), so we compute it for every A in X.

        ComputeKFZ(kfz,spacesize,point_closures);

// We can now count how many times each psi-number occurs in X.

        for (set=0; set<(one<<spacesize); set++)
        {
            (psi_count[Psi(set,spacesize,kfz)]->count)++;
        }

// Advance the while counter.

        space++;
    }

// Sort and print the results in increasing order of relative frequency.

    qsort(psi_count, (size_t)(71), sizeof(PsiCount *), comparRtn);

    printf("\nPsi-number counts in all nonhomeomorphic 8-spaces:\n");

    for (j=1; j<71; j++)
    {
        printf("\n%d\t%d", psi_count[j]->psi, psi_count[j]->count);
    }
    printf("\n");

// Print the results for cardinalities 9, 10, 11.

    printf("\nPsi-number counts in all nonhomeomorphic 9-spaces:\n\n");

    printf("3\t8960\n");
    printf("4\t8960\n");
    printf("21\t9700\n");
    printf("22\t9700\n");
    printf("1\t15248\n");
    printf("38\t15536\n");
    printf("2\t19824\n");
    printf("6\t28912\n");
    printf("5\t31784\n");
    printf("32\t36844\n");
    printf("33\t36844\n");
    printf("23\t57088\n");
    printf("8\t65872\n");
    printf("15\t65872\n");
    printf("45\t66608\n");
    printf("47\t66608\n");
    printf("7\t91296\n");
    printf("14\t91296\n");
    printf("58\t94092\n");
    printf("9\t106144\n");
    printf("16\t106144\n");
    printf("68\t141642\n");
    printf("34\t142276\n");
    printf("36\t142276\n");
    printf("13\t147168\n");
    printf("20\t147168\n");
    printf("10\t150120\n");
    printf("17\t150120\n");
    printf("11\t157816\n");
    printf("18\t157816\n");
    printf("12\t179248\n");
    printf("19\t179248\n");
    printf("41\t244832\n");
    printf("43\t244832\n");
    printf("59\t257640\n");
    printf("60\t257640\n");
    printf("27\t297168\n");
    printf("31\t302440\n");
    printf("24\t313256\n");
    printf("25\t313256\n");
    printf("46\t461804\n");
    printf("48\t461804\n");
    printf("28\t480264\n");
    printf("29\t480264\n");
    printf("30\t534912\n");
    printf("64\t673164\n");
    printf("66\t673164\n");
    printf("40\t688524\n");
    printf("26\t695904\n");
    printf("53\t1764914\n");
    printf("55\t1764914\n");
    printf("61\t1829406\n");
    printf("62\t2004092\n");
    printf("63\t2004092\n");
    printf("35\t2507120\n");
    printf("37\t2507120\n");
    printf("42\t2851252\n");
    printf("44\t2851252\n");
    printf("51\t3136650\n");
    printf("52\t3136650\n");
    printf("65\t6432934\n");
    printf("67\t6432934\n");
    printf("39\t9779700\n");
    printf("57\t20315344\n");
    printf("49\t26041722\n");
    printf("50\t26041722\n");
    printf("54\t26830707\n");
    printf("56\t26830707\n");

    printf("\nPsi-number counts in all nonhomeomorphic 10-spaces:\n\n");

    printf("38\t194464\n");
    printf("21\t221116\n");
    printf("22\t221116\n");
    printf("3\t472672\n");
    printf("4\t472672\n");
    printf("32\t552416\n");
    printf("33\t552416\n");
    printf("45\t729220\n");
    printf("47\t729220\n");
    printf("58\t753252\n");
    printf("6\t807712\n");
    printf("5\t933576\n");
    printf("1\t970400\n");
    printf("2\t1123696\n");
    printf("68\t1223404\n");
    printf("8\t2182496\n");
    printf("15\t2182496\n");
    printf("23\t2250592\n");
    printf("59\t2716172\n");
    printf("60\t2716172\n");
    printf("34\t3053968\n");
    printf("36\t3053968\n");
    printf("13\t3117640\n");
    printf("20\t3117640\n");
    printf("41\t3777152\n");
    printf("43\t3777152\n");
    printf("7\t3833568\n");
    printf("14\t3833568\n");
    printf("12\t4074592\n");
    printf("19\t4074592\n");
    printf("31\t4220072\n");
    printf("9\t4714560\n");
    printf("16\t4714560\n");
    printf("10\t5797632\n");
    printf("17\t5797632\n");
    printf("11\t6131792\n");
    printf("18\t6131792\n");
    printf("46\t6134108\n");
    printf("48\t6134108\n");
    printf("27\t8742192\n");
    printf("30\t8922560\n");
    printf("64\t9005048\n");
    printf("66\t9005048\n");
    printf("40\t9517598\n");
    printf("24\t9628688\n");
    printf("25\t9628688\n");
    printf("28\t12863680\n");
    printf("29\t12863680\n");
    printf("26\t17627648\n");
    printf("61\t27171170\n");
    printf("62\t31696752\n");
    printf("63\t31696752\n");
    printf("53\t33552276\n");
    printf("55\t33552276\n");
    printf("42\t55240000\n");
    printf("44\t55240000\n");
    printf("35\t61736300\n");
    printf("37\t61736300\n");
    printf("51\t65101614\n");
    printf("52\t65101614\n");
    printf("65\t120603005\n");
    printf("67\t120603005\n");
    printf("39\t336705808\n");
    printf("57\t521532200\n");
    printf("54\t678799114\n");
    printf("56\t678799114\n");
    printf("49\t813654304\n");
    printf("50\t813654304\n");

    printf("\nPsi-number counts in all nonhomeomorphic 11-spaces:\n\n");

    printf("38\t2424064\n");
    printf("21\t4864716\n");
    printf("22\t4864716\n");
    printf("58\t7303200\n");
    printf("32\t8566264\n");
    printf("33\t8566264\n");
    printf("45\t9092468\n");
    printf("47\t9092468\n");
    printf("68\t13893350\n");
    printf("3\t22631424\n");
    printf("4\t22631424\n");
    printf("6\t23707368\n");
    printf("5\t28907632\n");
    printf("59\t36485472\n");
    printf("60\t36485472\n");
    printf("1\t58353264\n");
    printf("2\t60246112\n");
    printf("41\t69617804\n");
    printf("43\t69617804\n");
    printf("31\t71506280\n");
    printf("34\t73490216\n");
    printf("36\t73490216\n");
    printf("13\t74524072\n");
    printf("20\t74524072\n");
    printf("8\t75295144\n");
    printf("15\t75295144\n");
    printf("23\t98456256\n");
    printf("46\t101230162\n");
    printf("48\t101230162\n");
    printf("12\t104324132\n");
    printf("19\t104324132\n");
    printf("40\t154395790\n");
    printf("64\t155290195\n");
    printf("66\t155290195\n");
    printf("7\t172336512\n");
    printf("14\t172336512\n");
    printf("30\t179403728\n");
    printf("9\t222335472\n");
    printf("16\t222335472\n");
    printf("10\t234391368\n");
    printf("17\t234391368\n");
    printf("11\t249969048\n");
    printf("18\t249969048\n");
    printf("27\t299603440\n");
    printf("24\t339733032\n");
    printf("25\t339733032\n");
    printf("28\t392684144\n");
    printf("29\t392684144\n");
    printf("26\t515749440\n");
    printf("61\t516051930\n");
    printf("62\t637801826\n");
    printf("63\t637801826\n");
    printf("53\t807561172\n");
    printf("55\t807561172\n");
    printf("42\t1329495128\n");
    printf("44\t1329495128\n");
    printf("51\t1665411036\n");
    printf("52\t1665411036\n");
    printf("35\t1820718192\n");
    printf("37\t1820718192\n");
    printf("65\t2896037343\n");
    printf("67\t2896037343\n");
    printf("39\t14082029164\n");
    printf("57\t16956658628\n");
    printf("54\t21906726761\n");
    printf("56\t21906726761\n");
    printf("49\t31385234116\n");
    printf("50\t31385234116\n");

    printf("\n");

    fclose(input);
    for (j=0; j<71; j++) free(psi_count[j]);
    free(psi_count);
    free(point_closures);
    FreeKFZ(kfz);
}


int comparRtn(const void *a, const void *b)
{
    PsiCount    *Ya, *Yb;
    int          Xa, Xb;

    Ya = *(PsiCount **)a;
    Yb = *(PsiCount **)b;
    Xa = Ya->count;
    Xb = Yb->count;

    return Xa<Xb ? -1 : Xa==Xb ? 0 : 1;
}