aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/algolib.c218
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
generated by cgit v1.3 (git 2.53.0) at 2026-07-28 11:41:39 +0000