breadth

3 files changed, 332 insertions, 47 deletions

diff --git a/.gitignore b/.gitignore
index 6685dd8..9c03190 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,2 @@
 bin/**
-**/.clangd
 .clangd
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
diff --git a/src/2-1-breadth-first-search.c b/src/2-1-breadth-first-search.c
new file mode 100644
index 0000000..0b232c5
--- /dev/null
+++ b/src/2-1-breadth-first-search.c
@@ -0,0 +1,160 @@
+#include <algolib.c>
+#include <stdbool.h>
+#include <stdio.h>
+#include <vectorlib.c>
+
+#define PROJECT_NAME "algorithms-breadth first search"
+
+typedef struct DATASET {
+    char* title;
+    char** cast;
+} DATASET;
+
+void bfs(BFS_Graph* graph, char** argv)
+{
+    printf("\nsearching %s - %s\n",argv[1],argv[2]);
+    BFS_Node* start = BFS_Gr_SetStart(graph, argv[1]);
+    BFS_Node* end = BFS_Gr_SetEnd(graph, argv[2]);
+
+    if (!start || !end)
+        return;
+
+    BFS_Node* queue[200];
+    int queue_len = 0;
+
+    start->searched = true;
+    queue[++queue_len] = start;
+
+    printf("\n");
+    while (queue_len > 0) {
+        BFS_Node* current = queue[queue_len--];
+        if (current == end) {
+            printf("found %s\n", current->value);
+            break;
+        }
+        for (int i = 0; i < 200; i++) {
+            if (current->edges[i] != NULL) {
+                BFS_Node* neighbor = current->edges[i];
+                if (neighbor->searched == false) {
+                    neighbor->searched = true;
+                    neighbor->parent = current;
+                    queue[++queue_len] = neighbor;
+                }
+            }
+        }
+    }
+
+    BFS_Node* path[200];
+    int path_len = 0;
+
+    path[path_len++] = end;
+    BFS_Node* next = end->parent;
+
+    while (next != NULL) {
+        path[path_len++] = next;
+        if (next->parent != NULL) {
+            next = next->parent;
+        } else {
+            break;
+        }
+    }
+
+    for (int i = path_len - 1; i >= 0; i--) {
+        printf("%s", path[i]->value);
+        if (i != 0)
+            printf(" --> ");
+    }
+}
+
+int main(int argc, char** argv)
+{
+    BFS_Graph* graph = BFS_Graph_Constructor();
+    DATASET** movies = (DATASET**)malloc(sizeof(DATASET*) * 5);
+    for (int i = 0; i < 5; i++) {
+        movies[i] = (DATASET*)malloc(sizeof(DATASET));
+        movies[i]->cast = (char**)malloc(sizeof(char*) * 3);
+    }
+
+    // cant be bothered to parse or add a lib to parse json.
+    // just doing it manually
+    movies[0]->title = "Me!";
+    movies[0]->cast[0] = "garry";
+    movies[0]->cast[1] = "jesus";
+    movies[0]->cast[2] = "niles";
+
+    movies[1]->title = "That Guy.";
+    movies[1]->cast[0] = "garry";
+    movies[1]->cast[1] = "neilman";
+    movies[1]->cast[2] = NULL;
+
+    movies[2]->title = "Some Stuff";
+    movies[2]->cast[0] = "cole";
+    movies[2]->cast[1] = "faux";
+    movies[2]->cast[2] = NULL;
+
+    movies[3]->title = "dogs";
+    movies[3]->cast[0] = "cole";
+    movies[3]->cast[1] = "niles";
+    movies[3]->cast[2] = "jales";
+
+    movies[4]->title = "Cats";
+    movies[4]->cast[0] = "james";
+    movies[4]->cast[1] = "jesus";
+    movies[4]->cast[2] = NULL;
+
+    for (int i = 0; i < 5; i++) {
+        char* movie = movies[i]->title;
+        BFS_Node* movieNode = BFS_Constructor(movie);
+        BFS_Gr_AddNode(graph, movieNode);
+        for (int j = 0; j < 3; j++) {
+            char* actor = movies[i]->cast[j];
+            if (actor == NULL)
+                break;
+
+            BFS_Node* actorNode = BFS_Gr_GetNode(graph, actor);
+            if (actorNode == NULL) {
+                actorNode = BFS_Constructor(actor);
+            }
+            BFS_Gr_AddNode(graph, actorNode);
+            BFS_AddEdge(movieNode, actorNode);
+        }
+    }
+
+    printf("nodes::\n");
+    for (int i = 0; i < 200; i++) {
+        if (graph->nodes[i] != NULL) {
+            printf("%s\n", graph->nodes[i]->value);
+        }
+    }
+
+    printf("\ngraph::\n");
+    for (int i = 0; i < 200; i++) {
+        if (graph->graph[i]->node != NULL) {
+            printf("%s\n", graph->graph[i]->node->value);
+            for (int j = 0; j < 20; j++) {
+                if (graph->graph[i]->node->edges[j] != NULL) {
+                    printf("    %s\n", graph->graph[i]->node->edges[j]->value);
+                }
+            }
+        }
+    }
+
+    if (argv[1] && argv[2]) {
+        bfs(graph, argv);
+    }
+
+    BFS_FreeGraph(graph);
+
+    for (int i = 0; i < 5; i++) {
+        free(movies[i]->cast);
+        free(movies[i]);
+    }
+    free(movies);
+
+    printf("\nEND\n");
+}
+
+/* Challanges
+ *
+ * make a prettier visualization
+ */