began work on merging terms in turn

5 files changed, 253 insertions, 151 deletions

diff --git a/Makefile b/Makefile
index dd56f43..2688893 100644
--- a/Makefile
+++ b/Makefile
@@ -1,5 +1,5 @@
-./quineMcCluskey : qm.c
-	gcc qm.c -o ./quineMcCluskey
+./quineMcCluskey : src/qm.c
+	gcc src/qm.c -o ./quineMcCluskey
 
 clean :
 	rm -f ./quineMcCluskey
diff --git a/qm.c b/qm.c
deleted file mode 100644
index 9c66f8a..0000000
--- a/qm.c
+++ /dev/null
@@ -1,122 +0,0 @@
-#include <stdio.h>
-#include <stdlib.h>
-#include <limits.h>
-#include <stdbool.h>
-#include <string.h>
-#include "qm.h"
-
-#define VALID_VARIABLES "ABCDEFGHIJKLMNOPQRSTUVXYZ"
-
-int main(int argc, char* argv[]) {
-    if (argc != 2) {
-        fprintf(stderr, "Incorrect number of arguments provided.\n");
-    }
-
-    parseDNFStr(argv[1]);
-}
-
-DNF parseDNFStr(const char* inpStr) {
-    //remove whitespace
-    char inpBfr[strlen(inpStr)];
-    int i = 0,  j = 0;
-    while (inpStr[i] != '\0') {
-        if (inpStr[i] != ' ') {
-            inpBfr[j++] = inpStr[i];
-        }
-        i++;
-    }
-    inpBfr[j] = '\0';
-
-    DNF dnf;
-    dnf.numTerms = strcnt(inpBfr, '+') + 1;
-
-    //split up, by '+'s
-    const char* delim = "+";
-    char* subStr = strtok(inpBfr, delim);
-    i = 0;
-    while (subStr != NULL) {
-        dnf.terms[i++] = parseDNFTerm(subStr);
-        // printf("term %i: '%s'\n", i, subStr);
-        subStr = strtok(NULL, delim);
-    }
-
-    // printf("%i terms\n", dnf.numTerms);
-    printForm(dnf);
-    printForm2(dnf);
-    return dnf;
-}
-
-DNFTerm parseDNFTerm(const char* termStr) {
-    DNFTerm term;
-    term.numVars = 0;
-    char c;
-    for (int i = 0; i < INT_MAX; i++) {
-        c = termStr[i];
-        if (c == '\0') {
-            break;
-        }
-        if (strcnt(VALID_VARIABLES, c) == 1) {
-            term.vars[term.numVars] = (Variable){c, termStr[i - 1] == '-'};
-            // printf("%i %c\n", term.numVars, term.vars[term.numVars]);
-            term.numVars++;
-        }
-    }
-    return term;
-}
-
-// returns an integer of how many times a char was found in a char
-// array
-unsigned int strcnt(const char* str, const char cnt) {
-    int count = 0;
-    for (int i = 0; i < INT_MAX; i++) {
-        char c = str[i];
-        if (c == '\0') {
-            break;
-        }
-        if (c == cnt) {
-            count++;
-        }
-    }
-    return count;
-}
-
-void printForm(const DNF form) {
-    for (int i = 0; i < form.numTerms; i++) {
-        printf("(");
-        DNFTerm term = form.terms[i];
-
-        for (int j = 0; j < term.numVars; j++) {
-            if (term.vars[j].not_) {
-                printf("¬");
-            }
-            printf("%c", term.vars[j].var);
-            if (term.numVars - 1 != j) {
-                printf("∧");
-            }
-        }
-
-        if (form.numTerms - 1 != i) {
-            printf(") ∨ ");
-        }
-    }
-    printf(")\n");
-}
-
-void printForm2(const DNF form) {
-    for (int i = 0; i < form.numTerms; i++) {
-        DNFTerm term = form.terms[i];
-
-        for (int j = 0; j < term.numVars; j++) {
-            printf("%c", term.vars[j].var);
-            if (term.vars[j].not_) {
-                printf("'");
-            }
-        }
-
-        if (form.numTerms - 1 != i) {
-            printf(" + ");
-        }
-    }
-    printf("\n");
-}
-
diff --git a/qm.h b/qm.h
deleted file mode 100644
index 173dd4c..0000000
--- a/qm.h
+++ /dev/null
@@ -1,27 +0,0 @@
-#ifndef QM_C
-#define QM_C
-
-#include <string.h>
-
-typedef struct {
-    char var;
-    bool not_;
-} Variable;
-
-typedef struct {
-    unsigned int numVars;
-    Variable vars[26];
-} DNFTerm;
-
-typedef struct {
-    unsigned int numTerms;
-    DNFTerm terms[100];
-} DNF;
-
-unsigned int strcnt(const char* str, const char cnt);
-DNF parseDNFStr(const char* inpStr);
-DNFTerm parseDNFTerm(const char* termStr);
-void printForm(const DNF form);
-void printForm2(const DNF form);
-
-#endif
\ No newline at end of file
diff --git a/src/qm.c b/src/qm.c
new file mode 100644
index 0000000..2b3677a
--- /dev/null
+++ b/src/qm.c
@@ -0,0 +1,212 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+#include <stdbool.h>
+#include <string.h>
+#include "qm.h"
+
+#define VALID_VARIABLES "ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz"
+
+int main(int argc, char* argv[]) {
+    if (argc != 2) {
+        fprintf(stderr, "Incorrect number of arguments provided.\n");
+    }
+
+    DNF startDNF = parseDNFStr(argv[1]);
+    SimplifiedTableItem simplifiedTable[startDNF.numTerms];
+    unsigned int simplifiedTableLength = startDNF.numTerms;
+    setupMergeTable(simplifiedTable, &startDNF);
+
+    mergeTermsInTurn(simplifiedTable, &startDNF.numTerms);
+}
+
+void setupMergeTable(SimplifiedTableItem simplifiedTable[], DNF* dnf) {
+    for (int i = 0; i < dnf->numTerms; i++) {
+        simplifiedTable[i].term = dnf->terms[i];
+        simplifiedTable[i].simplifiedIndexes[0] = i;
+        simplifiedTable[i].numIndexes = 1;
+    }
+}
+
+void mergeTermsInTurn(SimplifiedTableItem simplifiedTable[], unsigned int* length) {
+    SimplifiedTableItem nextIteration[*length];
+    for (int i = 0; i < *length; i++) {
+        for (int j = 0; j < *length; j++) {
+            if (i == j) {
+                continue;
+            }
+
+            if (canMergeTerms(&simplifiedTable[i].term, &simplifiedTable[j].term)) {
+                // printDNFTerm(&simplifiedTable[i].term);
+                // printf(" + ");
+                // printDNFTerm(&simplifiedTable[j].term);
+                // printf(" = ");
+                DNFTerm mergedTerm = mergeTerms(&simplifiedTable[i].term, &simplifiedTable[j].term);
+                // printDNFTerm(&mergedTerm);
+                // printf("\n------\n");
+            }
+        }
+    }
+}
+
+bool canMergeTerms(const DNFTerm* term1, const DNFTerm* term2) {
+    unsigned int sameTerms = 0;
+    for (int i = 0; i < term1->numVars; i++) {
+        for (int j = 0; j < term2->numVars; j++) {
+            if (term1->vars[i].not_ == term2->vars[j].not_ && term1->vars[i].var == term2->vars[j].var) {
+                sameTerms++;
+            }
+        }
+    }
+    return term1->numVars - sameTerms == 1;
+}
+
+DNFTerm mergeTerms(const DNFTerm* term1, const DNFTerm* term2) {
+    DNFTerm mergedTerm;
+    mergedTerm.numVars = 0;
+    for (int i = 0; i < term1->numVars; i++) {
+        for (int j = 0; j < term2->numVars; j++) {
+            if (term1->vars[i].not_ == term2->vars[j].not_ && term1->vars[i].var == term2->vars[j].var) {
+                mergedTerm.vars[mergedTerm.numVars++] = (Variable){term1->vars[i].var, term1->vars[i].not_};
+            }
+        }
+    }
+    return mergedTerm;
+}
+
+bool termInTable(const SimplifiedTableItem simplifiedTable[], const unsigned int* length, const DNFTerm* term) {
+    for (int i = 0; i < *length; i++) {
+        if (termsAreEqual(&simplifiedTable[i].term, term)) {
+            return true;
+        }
+    }
+    return false;
+}
+
+bool termsAreEqual(const DNFTerm* term1, const DNFTerm* term2) {
+    if (term1->numVars != term2->numVars) {
+        return false;
+    }
+
+    //TODO
+}
+
+DNF parseDNFStr(const char* inpStr) {
+    //remove whitespace
+    char inpBfr[strlen(inpStr)];
+    int i = 0,  j = 0;
+    while (inpStr[i] != '\0') {
+        if (inpStr[i] != ' ') {
+            inpBfr[j++] = inpStr[i];
+        }
+        i++;
+    }
+    inpBfr[j] = '\0';
+
+    DNF dnf;
+    dnf.numTerms = strcnt(inpBfr, '+') + 1;
+
+    char notChar;
+    int relIndex;
+    if (strcnt(inpBfr, "'"[0]) > 0) {
+        dnf.notChar = "'"[0];
+        relIndex = 1;
+    } else if (strcnt(inpBfr, '-') > 0) {
+        dnf.notChar = '-';
+        relIndex = -1;
+    }
+    if (strcnt(inpBfr, "'"[0]) > 0 && strcnt(inpBfr, '-') > 0) {
+        fprintf(stderr, "Inconsistent notation used for not.\n");
+        exit(EXIT_FAILURE);
+    }
+
+    //split up, by '+'s
+    const char* delim = "+";
+    char* subStr = strtok(inpBfr, delim);
+    i = 0;
+    while (subStr != NULL) {
+        dnf.terms[i++] = parseDNFTerm(subStr, dnf.notChar, relIndex);
+        // printf("term %i: '%s'\n", i, subStr);
+        subStr = strtok(NULL, delim);
+    }
+
+    return dnf;
+}
+
+DNFTerm parseDNFTerm(const char* termStr, const char notChar, const int relIndex) {
+    DNFTerm term;
+    term.numVars = 0;
+    char c;
+    for (int i = 0; i < INT_MAX; i++) {
+        c = termStr[i];
+        if (c == '\0') {
+            break;
+        }
+        if (strcnt(VALID_VARIABLES, c) == 1) {
+            term.vars[term.numVars++] = (Variable){c, termStr[i + relIndex] == notChar};
+        }
+    }
+    return term;
+}
+
+unsigned int strcnt(const char* str, const char cnt) {
+    // returns an integer of how many times a char was found in a char
+    // array
+    int count = 0;
+    for (int i = 0; i < INT_MAX; i++) {
+        char c = str[i];
+        if (c == '\0') {
+            break;
+        }
+        if (c == cnt) {
+            count++;
+        }
+    }
+    return count;
+}
+
+void printForm(const DNF* form) {
+    for (int i = 0; i < form->numTerms; i++) {
+        printf("(");
+        DNFTerm term = form->terms[i];
+        printDNFTerm(&term);
+
+        if (form->numTerms - 1 != i) {
+            printf(") ∨ ");
+        }
+    }
+    printf(")\n");
+}
+
+void printDNFTerm(const DNFTerm* term) {
+    for (int j = 0; j < term->numVars; j++) {
+            if (term->vars[j].not_) {
+                printf("¬");
+            }
+            printf("%c", term->vars[j].var);
+            if (term->numVars - 1 != j) {
+                printf("∧");
+            }
+        }
+}
+
+void printForm2(const DNF* form) {
+    for (int i = 0; i < form->numTerms; i++) {
+        DNFTerm term = form->terms[i];
+
+        for (int j = 0; j < term.numVars; j++) {
+            if (term.vars[j].not_ && form->notChar == '-') {
+                printf("-");
+            }
+            printf("%c", term.vars[j].var);
+            if (term.vars[j].not_ && form->notChar == "'"[0]) {
+                printf("'");
+            }
+        }
+
+        if (form->numTerms - 1 != i) {
+            printf(" + ");
+        }
+    }
+    printf("\n");
+}
\ No newline at end of file
diff --git a/src/qm.h b/src/qm.h
new file mode 100644
index 0000000..2b001bb
--- /dev/null
+++ b/src/qm.h
@@ -0,0 +1,39 @@
+#ifndef QM_C
+#define QM_C
+
+typedef struct {
+    char var;
+    bool not_;
+} Variable;
+
+typedef struct {
+    unsigned int numVars;
+    Variable vars[26];
+} DNFTerm;
+
+typedef struct {
+    unsigned int numTerms;
+    DNFTerm terms[100];
+    char notChar;
+} DNF;
+
+typedef struct {
+    DNFTerm term;
+    unsigned int simplifiedIndexes[100];
+    unsigned int numIndexes;
+} SimplifiedTableItem;
+
+unsigned int strcnt(const char* str, const char cnt);
+void setupMergeTable(SimplifiedTableItem simplifiedTable[], DNF* dnf);
+void mergeTermsInTurn(SimplifiedTableItem simplifiedTable[], unsigned int* length);
+bool canMergeTerms(const DNFTerm* term1, const DNFTerm* term2);
+DNFTerm mergeTerms(const DNFTerm* term1, const DNFTerm* term2);
+bool termInTable(const SimplifiedTableItem simplifiedTable[], const unsigned int* length, const DNFTerm* term);
+bool termsAreEqual(const DNFTerm* term1, const DNFTerm* term2);
+DNF parseDNFStr(const char* inpStr);
+DNFTerm parseDNFTerm(const char* termStr, const char notChar, const int relIndex);
+void printDNFTerm(const DNFTerm* term);
+void printForm(const DNF* form);
+void printForm2(const DNF* form);
+
+#endif
\ No newline at end of file