breadth

1 files changed, 172 insertions, 46 deletions

diff --git a/lib/algolib.c b/lib/algolib.c
index 43a1f2e..8d15782 100644
--- a/lib/algolib.c
+++ b/lib/algolib.c
@@ -1,108 +1,234 @@
 #ifndef algolib
 #define algolib
 
+#include <gobjects.c>
+#include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
-#include <stdbool.h>
 #include <vectorlib.c>
-#include <gobjects.c>
-#include <SDL2/SDL.h>
-#include <SDL2/SDL_ttf.h>
 
 #define flaot float
 
-//Binary Search Tree
+// Binary Search Tree
 
 typedef struct BS_Node {
     int value;
-    struct BS_Node *left;
-    struct BS_Node *right;
+    struct BS_Node* left;
+    struct BS_Node* right;
     Point pos;
-    TEXT *text;
+    TEXT* text;
 } BS_Node;
 
-void BSAddNode(BS_Node **self, BS_Node **node){
-    if ((*node)->value < (*self)->value){
-        if((*self)->left == NULL){
+void BSAddNode(BS_Node** self, BS_Node** node)
+{
+    if ((*node)->value < (*self)->value) {
+        if ((*self)->left == NULL) {
             (*self)->left = (*node);
         } else {
-            BSAddNode(&(*self)->left,node);
+            BSAddNode(&(*self)->left, node);
         }
-    } else if ((*node)->value > (*self)->value){
-        if((*self)->right == NULL){
+    } else if ((*node)->value > (*self)->value) {
+        if ((*self)->right == NULL) {
             (*self)->right = (*node);
         } else {
-            BSAddNode(&(*self)->right,node);
+            BSAddNode(&(*self)->right, node);
         }
     } else {
         free(*node);
     }
 }
 
-void BSAddValue(BS_Node **root, int value){
-    BS_Node *node = (BS_Node*)malloc(sizeof(BS_Node));
-    node->value=value;
+void BSAddValue(BS_Node** root, int value)
+{
+    BS_Node* node = (BS_Node*)malloc(sizeof(BS_Node));
+    node->value = value;
     node->left = NULL;
     node->right = NULL;
 
-    if ((*root) == NULL){
+    if ((*root) == NULL) {
         (*root) = node;
     } else {
         BSAddNode(root, &node);
     }
 }
 
-void BSPrintTree(BS_Node **node){
-    if((*node)->left != NULL){
+void BSPrintTree(BS_Node** node)
+{
+    if ((*node)->left != NULL) {
         BSPrintTree(&(*node)->left);
     }
-    printf("%d\n",(*node)->value);
-    if((*node)->right!= NULL){
+    printf("%d\n", (*node)->value);
+    if ((*node)->right != NULL) {
         BSPrintTree(&(*node)->right);
     }
 }
 
-BS_Node *BSSearchTree(BS_Node **node, int val){
-    if((*node)->value == val) {
+BS_Node* BSSearchTree(BS_Node** node, int val)
+{
+    if ((*node)->value == val) {
         return *node;
-    } else if (val < (*node)->value && (*node)->left != NULL){
-        return BSSearchTree(&(*node)->left,val);
-    } else if (val > (*node)->value && (*node)->right!= NULL){
-        return BSSearchTree(&(*node)->right,val);
+    } else if (val < (*node)->value && (*node)->left != NULL) {
+        return BSSearchTree(&(*node)->left, val);
+    } else if (val > (*node)->value && (*node)->right != NULL) {
+        return BSSearchTree(&(*node)->right, val);
     }
     return NULL;
 }
 
-void BSFreeTree(BS_Node **node){
-    if((*node)->left != NULL){
+void BSFreeTree(BS_Node** node)
+{
+    if ((*node)->left != NULL) {
         BSFreeTree(&(*node)->left);
     }
-    if((*node)->right != NULL){
+    if ((*node)->right != NULL) {
         BSFreeTree(&(*node)->right);
     }
     free(*node);
 }
 
+// Breadth-First Search
+#define MAX_KEY_LENGTH 2048
 
-//Breadth-First Search
-
-typedef struct BFS_Node{
-    char *value;
-    struct BFS_Node **edges;
+typedef struct BFS_Node {
+    char* value;
+    struct BFS_Node** edges;
     bool searched;
-    struct BFS_Node *parent;
+    struct BFS_Node* parent;
 } BFS_Node;
 
-typedef struct BFS_Graph{
-    BFS_Node **nodes;
-    BFS_Node **graph; //make hashmap
+typedef struct BFS_Graph_KeyPair {
+    char key[MAX_KEY_LENGTH];
+    BFS_Node* node;
+} BFS_Graph_KeyPair;
+
+typedef struct BFS_Graph {
+    BFS_Node** nodes;
+    BFS_Graph_KeyPair** graph;
+    BFS_Node* start;
+    BFS_Node* end;
 } BFS_Graph;
 
-BFS_Node *BFS_Constructor(char *value){
-    BFS_Node *node=(BFS_Node*)malloc(sizeof(BFS_Node));
-    node->value=value;
-    node->edges=(BFS_Node**)malloc(sizeof(BFS_Node*)*2048);
+size_t hash(char* str)
+{
+    size_t hash = 5381;
+    int c;
+
+    while ((c = *str++))
+        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
+
+    return hash % 200;
+}
+
+BFS_Node* BFS_Constructor(char* value)
+{
+    BFS_Node* node = (BFS_Node*)malloc(sizeof(BFS_Node));
+    node->value = value;
+    node->parent = NULL;
+    node->edges = (BFS_Node**)malloc(sizeof(BFS_Node*) * 200);
+    for (int i = 0; i < 200; i++) {
+        node->edges[i] = NULL;
+    }
     return node;
 }
 
-#endif
+void BFS_AddEdge(BFS_Node* node, BFS_Node* neighbor)
+{
+    for (int i = 0; i < 200; i++) {
+        if (node->edges[i] == NULL) {
+            node->edges[i] = neighbor;
+            break;
+        }
+    }
+    for (int i = 0; i < 200; i++) {
+        if (neighbor->edges[i] == NULL) {
+            neighbor->edges[i] = node;
+            return;
+        }
+    }
+}
+
+BFS_Graph* BFS_Graph_Constructor()
+{
+    BFS_Graph* graph = (BFS_Graph*)malloc(sizeof(BFS_Graph));
+    graph->nodes = (BFS_Node**)malloc(sizeof(BFS_Node*) * 200);
+    graph->graph = (BFS_Graph_KeyPair**)malloc(sizeof(BFS_Graph_KeyPair*) * 200);
+    for (int i = 0; i < 200; i++) {
+        graph->graph[i] = (BFS_Graph_KeyPair*)malloc(sizeof(BFS_Graph_KeyPair));
+        graph->graph[i]->node = NULL;
+        graph->nodes[i] = NULL;
+    }
+    return graph;
+}
+
+BFS_Node* BFS_Gr_GetNode(BFS_Graph* graph, char* value)
+{
+    size_t index = hash(value);
+    if (graph->graph[index]->node != NULL && strcmp(graph->graph[index]->node->value, value) == 0)
+        return graph->graph[index]->node;
+    return NULL;
+}
+
+void BFS_Gr_AddNode(BFS_Graph* graph, BFS_Node* node)
+{
+    if (node == NULL)
+        return;
+
+    for (int i = 0; i < 200; i++) {
+        if (graph->nodes[i] == NULL) {
+            graph->nodes[i] = node;
+            char* title = node->value;
+
+            size_t index = hash(title);
+
+            // dont wanna handle collisions
+            if (graph->graph[index]->node != NULL) {
+                if (strcmp(graph->graph[index]->node->value, title) == 0) {
+                    return;
+                } else {
+                    printf("COLLISION!");
+                    exit(-1);
+                }
+            }
+
+            strncpy(graph->graph[index]->key, title, MAX_KEY_LENGTH - 1);
+            graph->graph[index]->key[MAX_KEY_LENGTH - 1] = '\0'; // Ensure null-terminated string
+            graph->graph[index]->node = node;
+
+            return;
+        }
+    }
+}
+
+BFS_Node* BFS_Gr_SetStart(BFS_Graph* graph, char* value)
+{
+    size_t index = hash(value);
+    graph->start=graph->graph[index]->node;
+    return graph->start;
+}
+
+BFS_Node* BFS_Gr_SetEnd(BFS_Graph* graph, char* value)
+{
+    size_t index = hash(value);
+    graph->end=graph->graph[index]->node;
+    return graph->end;
+}
+
+void BFS_FreeGraph(BFS_Graph* graph)
+{
+    for (int i = 0; i < 200; i++) {
+        if (graph->graph[i] != NULL && graph->graph[i]->node != NULL) {
+            free(graph->graph[i]->node->edges);
+            graph->graph[i]->node->edges = NULL;
+            free(graph->graph[i]->node);
+            graph->graph[i]->node = NULL;
+        }
+        if (graph->graph[i] != NULL) {
+            free(graph->graph[i]);
+        }
+    }
+    free(graph->nodes);
+    free(graph->graph);
+    free(graph);
+}
+
+#endif
\ No newline at end of file