#include "quine_mccluskey.h"

bool checkDashesAlign(char minterm1[MAX_LENGTH], char minterm2[MAX_LENGTH])
{
    // TODO 1: implement the function
    for (int i = 0; minterm1[i] != '\0' && minterm2[i] != '\0'; ++i)
    {
        if (minterm1[i] == 'x' && minterm2[i] != 'x' || minterm1[i] != 'x' && minterm2[i] == 'x')
            return false;
    }

    return true;
}

bool checkMintermDifference(char minterm1[MAX_LENGTH], char minterm2[MAX_LENGTH])
{
    // TODO 1: implement the function

    // Hint: think about using C's bitwise operators. This may require converting
    // the minterms to integers.
    int a = 0;
    int b = 0;

    for (int i = 0; minterm1[i] != '\0'; ++i)
    {
        if (minterm1[i] != 'x')
        {
            a <<= 1;
            a += minterm1[i] - '0';
        }
    }
    for (int i = 0; minterm2[i] != '\0'; ++i)
    {
        if (minterm2[i] != 'x')
        {
            b <<= 1;
            b += minterm2[i] - '0';
        }
    }

    int minterm_difference = a ^ b;
    // find out whether minterm difference contains
    if (minterm_difference == 0 || (minterm_difference & (minterm_difference - 1)) != 0)
    {
        return false;
    }

    return true;
}

char *mergeMinterms(char minterm1[MAX_LENGTH], char minterm2[MAX_LENGTH])
{
    // TODO 1: implement the function
    // mergedMinterm should contain the result at the end of computation.
    static char mergedMinterm[MAX_LENGTH]; // Return this value
    memset(mergedMinterm, '\0', MAX_LENGTH);

    if (!checkDashesAlign(minterm1, minterm2) || !checkMintermDifference(minterm1, minterm2))
    {
        return NULL;
    }
    int i;
    for (i = 0; minterm1[i] != '\0' && minterm2[i] != '\0'; ++i)
    {
        if (minterm1[i] != minterm2[i])
        {
            mergedMinterm[i] = 'x';
        }
        else
        {
            mergedMinterm[i] = minterm1[i];
        }
    }
    mergedMinterm[i] = '\0';
    return mergedMinterm;
}

void addMinterm(char minterms[MAX_TERMS][MAX_LENGTH], char minterm[MAX_LENGTH])
{
    // TODO 1: implement the function
    int i = 0;
    for (i = 0; i < MAX_TERMS && minterms[i][0] != '\0'; ++i)
    {
        if (strcmp(minterms[i], minterm) == 0)
        {
            return;
        }
    }
    if (i >= MAX_TERMS)
    {
        // cannot add minterm
        return;
    }
    // append minterm
    strcpy(minterms[i], minterm);
    return;
}

void getPrimeImplicants(char minterms[MAX_TERMS][MAX_LENGTH], char primeImplicants[MAX_TERMS][MAX_LENGTH])
{
    bool mergeFound = true;
    bool mergedArr[MAX_TERMS] = {false};
    char temp[MAX_TERMS][MAX_LENGTH] = {0};
    char mintermsCpy[MAX_TERMS][MAX_LENGTH] = {0};

    for (int i = 0; i < MAX_TERMS; ++i)
    {
        strcpy(mintermsCpy[i], minterms[i]);
    }

    while (mergeFound)
    {
        bool iterFound = false;
        memset(mergedArr, false, sizeof(mergedArr));

        for (int i = 0; i < MAX_TERMS; ++i)
        {
            for (int j = i + 1; j < MAX_TERMS; ++j)
            {   
                if (mintermsCpy[i][0] != '\0' && mintermsCpy[j][0] != '\0' && strlen(mintermsCpy[i]) == strlen(mintermsCpy[j]))
                {
                    char *merged = mergeMinterms(mintermsCpy[i], mintermsCpy[j]);
                    if (merged != NULL)
                    {
                        printf(merged);
                        iterFound = true;
                        mergedArr[i] = true;
                        mergedArr[j] = true;
                        addMinterm(temp, merged);
                    }
                }
            }

            if (mintermsCpy[i][0] != '\0' && !mergedArr[i])
            {
                addMinterm(primeImplicants, mintermsCpy[i]);
            }
        }

        int idx = 0;
        for (int i = 0; i < MAX_TERMS; ++i)
        {
            if (temp[i][0] != '\0')
            {
                strcpy(mintermsCpy[idx++], temp[i]);
            }
        }
        mintermsCpy[idx][0] = '\0';
        memset(temp, '\0', sizeof(temp));
        printf("hello\n");
        mergeFound = iterFound;
    }

    for (int i = 0; i < MAX_TERMS; ++i)
    {
        if (mintermsCpy[i][0] != '\0' && !mergedArr[i])
        {
            addMinterm(primeImplicants, mintermsCpy[i]);
        }
    }
    return;
}

void findMinimizedPrimeImplicants(char minterms[MAX_TERMS][MAX_LENGTH], char primeImplicants[MAX_TERMS][MAX_LENGTH], char selectedPrimeImplicants[MAX_TERMS][MAX_LENGTH])
{
    bool chart[MAX_TERMS][MAX_TERMS] = {false};

    for (int i = 0; i < MAX_TERMS; ++i)
    {
        if (primeImplicants[i][0] == '\0')
            continue;
        for (int j = 0; j < MAX_TERMS; ++j)
        {
            if (minterms[j][0] == '\0')
                continue;
            bool chartVal = true;
            for (int k = 0; minterms[j][k] != '\0'; ++k)
            {
                if (primeImplicants[i][k] != 'x' && primeImplicants[i][k] != minterms[j][k])
                {
                    chartVal = false;
                    break;
                }
            }
            chart[i][j] = chartVal;
        }
    }

    int index = 0;
    int selectedPrimeImplicantIndices[MAX_TERMS] = {-1};

    for (int c = 0; c < MAX_TERMS; ++c)
    {
        int primeImplicantRow = -1;
        int colSum = 0;
        for (int r = 0; r < MAX_TERMS; ++r)
        {
            if (chart[r][c])
            {
                colSum++;
                primeImplicantRow = r;
            }
        }
        if (colSum == 1)
        {
            strcpy(selectedPrimeImplicants[index], primeImplicants[primeImplicantRow]);
            selectedPrimeImplicantIndices[index] = primeImplicantRow;
            index++;
        }
    }

    int uncoveredMinterms[MAX_TERMS] = {-1};
    int idx = 0;

    for (int i = 0; i < MAX_TERMS; ++i)
    {
        if (minterms[i][0] == '\0')
            continue;
        bool covered = false;
        for (int j = 0; j < index; ++j)
        {
            int implicantRow = selectedPrimeImplicantIndices[j];
            if (chart[implicantRow][i])
            {
                covered = true;
                break;
            }
        }
        if (!covered)
        {
            uncoveredMinterms[idx] = i;
            idx++;
        }
    }

    int numUncovered = idx;
    while (numUncovered > 0)
    {
        int firstUncoveredIdx = -1;
        int i = 0;
        while (i < idx && uncoveredMinterms[i] == -1)
        {
            i++;
        }
        firstUncoveredIdx = uncoveredMinterms[i];
        uncoveredMinterms[i] = -1;
        numUncovered--;

        int newPrimeImplicantIdx = -1;

        for (int i = 0; i < MAX_TERMS; ++i)
        {
            if (chart[i][firstUncoveredIdx])
            {
                newPrimeImplicantIdx = i;
                break;
            }
        }

        strcpy(selectedPrimeImplicants[index], primeImplicants[newPrimeImplicantIdx]);
        index++;

        for (int i = 0; i < MAX_TERMS; ++i)
        {
            if (chart[newPrimeImplicantIdx][i])
            {
                for (int j = 0; j < MAX_TERMS; ++j)
                {
                    if (uncoveredMinterms[j] == i)
                    {
                        uncoveredMinterms[j] = -1;
                    }
                }
                numUncovered--;
            }
        }
    }

    return;
}

void readMintermsFromFile(const char *filename, char minterms[MAX_TERMS][MAX_LENGTH])
{
    FILE *file = fopen(filename, "r");
    if (!file)
    {
        printf("Error opening file!\n");
        return;
    }

    char line[MAX_LENGTH];
    int index = 0;
    while (fgets(line, sizeof(line), file) && index < MAX_TERMS)
    {
        line[strcspn(line, "\n")] = '\0'; // Remove newline character from fgets input
        strcpy(minterms[index++], line);
    }
    minterms[index][0] = '\0'; // Null-terminate the array

    fclose(file);
}

int main(int argc, char *argv[])
{
    if (argc < 2)
    {
        fprintf(stderr, "Usage: %s <minterm_file>\n", argv[0]);
        return 1;
    }

    char minterms[MAX_TERMS][MAX_LENGTH] = {0};
    readMintermsFromFile(argv[1], minterms);

    char primeImplicants[MAX_TERMS][MAX_LENGTH] = {0};
    getPrimeImplicants(minterms, primeImplicants);

    printf("Prime Implicants:\n");
    for (int i = 0; primeImplicants[i][0] != '\0'; i++)
    {
        printf("%s\n", primeImplicants[i]);
    }

    char selectedPrimeImplicants[MAX_TERMS][MAX_LENGTH] = {0};
    findMinimizedPrimeImplicants(minterms, primeImplicants, selectedPrimeImplicants);

    // Output the selected prime implicants to output.txt
    FILE *f = fopen("output.txt", "w");
    if (f == NULL)
    {
        printf("Error opening file!\n");
        return 1;
    }

    for (int i = 0; selectedPrimeImplicants[i][0] != '\0'; i++)
    {
        fprintf(f, "%s\n", selectedPrimeImplicants[i]);
    }
    fclose(f);

    printf("\nSelected Prime Implicants:\n");
    for (int i = 0; selectedPrimeImplicants[i][0] != '\0'; i++)
    {
        printf("%s\n", selectedPrimeImplicants[i]);
    }

    printf("Selected prime implicants written to output.txt\n");

    return 0;
}


there is on certain inputs for getPrimeImplicants, an infinite loop in the while loop - fix this