aboutsummaryrefslogtreecommitdiff
path: root/lib/algo
diff options
context:
space:
mode:
Diffstat (limited to 'lib/algo')
-rw-r--r--lib/algo/avl_tree.c77
-rw-r--r--lib/algo/flood_fill.c23
2 files changed, 47 insertions, 53 deletions
diff --git a/lib/algo/avl_tree.c b/lib/algo/avl_tree.c
index 7b86bab..cc06254 100644
--- a/lib/algo/avl_tree.c
+++ b/lib/algo/avl_tree.c
@@ -5,8 +5,7 @@
#include <stdio.h>
// Get the height of an AVL node
-AvlHeight_t get_height(AVLNode* node)
-{
+AvlHeight_t get_height(AVLNode *node) {
if (node == NULL) {
return 0;
}
@@ -14,14 +13,10 @@ AvlHeight_t get_height(AVLNode* node)
}
// Get the Maximum Height between two
-AvlHeight_t max_height(AvlHeight_t a, AvlHeight_t b)
-{
- return (a > b) ? a : b;
-}
+AvlHeight_t max_height(AvlHeight_t a, AvlHeight_t b) { return (a > b) ? a : b; }
// Get the balance factor of a node
-ssize_t get_balance_factor(AVLNode* node)
-{
+ssize_t get_balance_factor(AVLNode *node) {
if (node == NULL) {
return 0;
}
@@ -29,37 +24,38 @@ ssize_t get_balance_factor(AVLNode* node)
}
// Rotate an AVL node right
-AVLNode* right_rotate(AVLNode* parent)
-{
- AVLNode* child1 = parent->left;
- AVLNode* child2 = child1->right;
+AVLNode *right_rotate(AVLNode *parent) {
+ AVLNode *child1 = parent->left;
+ AVLNode *child2 = child1->right;
child1->right = parent;
parent->left = child2;
- parent->height = max_height(get_height(parent->left), get_height(parent->right)) + 1;
- child1->height = max_height(get_height(child1->left), get_height(child1->right)) + 1;
+ parent->height =
+ max_height(get_height(parent->left), get_height(parent->right)) + 1;
+ child1->height =
+ max_height(get_height(child1->left), get_height(child1->right)) + 1;
return child1;
}
// Rotate an AVL node left
-AVLNode* left_rotate(AVLNode* parent)
-{
- AVLNode* child1 = parent->right;
- AVLNode* child2 = child1->left;
+AVLNode *left_rotate(AVLNode *parent) {
+ AVLNode *child1 = parent->right;
+ AVLNode *child2 = child1->left;
child1->left = parent;
parent->right = child2;
- parent->height = max_height(get_height(parent->left), get_height(parent->right)) + 1;
- child1->height = max_height(get_height(child1->left), get_height(child1->right)) + 1;
+ parent->height =
+ max_height(get_height(parent->left), get_height(parent->right)) + 1;
+ child1->height =
+ max_height(get_height(child1->left), get_height(child1->right)) + 1;
return child1;
}
// Create AVL node
-AVLNode* create_avl_node(void* data, AvlComparator compare)
-{
- AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
+AVLNode *create_avl_node(void *data, AvlComparator compare) {
+ AVLNode *node = (AVLNode *)malloc(sizeof(AVLNode));
if (node == NULL) {
return NULL;
}
@@ -72,12 +68,11 @@ AVLNode* create_avl_node(void* data, AvlComparator compare)
}
// Insert data into AVL tree
-Result avl_insert(AVLNode* node, void* data, AvlComparator compare)
-{
+Result avl_insert(AVLNode *node, void *data, AvlComparator compare) {
Result result;
// 1. Standard BST insertion
if (node == NULL) {
- return (Result) {create_avl_node(data, compare), TRUE};
+ return (Result){create_avl_node(data, compare), TRUE};
}
if (node->compare(data, node->data)) {
@@ -86,20 +81,21 @@ Result avl_insert(AVLNode* node, void* data, AvlComparator compare)
fprintf(stderr, "Failed to insert!");
return result;
}
- node->left = (AVLNode*)result.data;
+ node->left = (AVLNode *)result.data;
} else if (node->compare(node->data, data)) {
result = avl_insert(node->right, data, compare);
if (!result.success) {
fprintf(stderr, "Failed to insert!");
return result;
}
- node->right = (AVLNode*)result.data;
+ node->right = (AVLNode *)result.data;
} else {
- return (Result) {node, FALSE};
+ return (Result){node, FALSE};
}
// 2. Update height of the ancestor node
- node->height = 1 + max_height(get_height(node->left), get_height(node->right));
+ node->height =
+ 1 + max_height(get_height(node->left), get_height(node->right));
ssize_t balance = get_balance_factor(node);
@@ -107,26 +103,25 @@ Result avl_insert(AVLNode* node, void* data, AvlComparator compare)
// LeftLeft
if ((balance > 1) && node->compare(data, node->left->data)) {
- return (Result) {right_rotate(node), TRUE};
+ return (Result){right_rotate(node), TRUE};
}
// RightRight
if ((balance < -1) && node->compare(node->right->data, data)) {
- return (Result) {left_rotate(node), TRUE};
+ return (Result){left_rotate(node), TRUE};
}
// LeftRight
if ((balance > 1) && node->compare(node->left->data, data)) {
- return (Result) {right_rotate(node), TRUE};
+ return (Result){right_rotate(node), TRUE};
}
// RightLeft
- if ((balance < -1) && node->compare(data,node->right->data)) {
- return (Result) {left_rotate(node), TRUE};
+ if ((balance < -1) && node->compare(data, node->right->data)) {
+ return (Result){left_rotate(node), TRUE};
}
- return (Result) {node, TRUE};
+ return (Result){node, TRUE};
}
// In-order traversal print pointer
-void print_in_order(AVLNode* root)
-{
+void print_in_order(AVLNode *root) {
if (root != NULL) {
print_in_order(root->left);
printf("%p ", root->data);
@@ -135,8 +130,7 @@ void print_in_order(AVLNode* root)
}
// Free avl tree nodes starting at root
-void free_avl_tree(AVLNode* root)
-{
+void free_avl_tree(AVLNode *root) {
if (root != NULL) {
free_avl_tree(root->left);
free_avl_tree(root->right);
@@ -145,8 +139,7 @@ void free_avl_tree(AVLNode* root)
}
// Free avl tree and their data starting at root
-void free_avl_tree_nodes(AVLNode* root)
-{
+void free_avl_tree_nodes(AVLNode *root) {
if (root != NULL) {
free_avl_tree_nodes(root->left);
free_avl_tree_nodes(root->right);
diff --git a/lib/algo/flood_fill.c b/lib/algo/flood_fill.c
index d11b5aa..e2ee870 100644
--- a/lib/algo/flood_fill.c
+++ b/lib/algo/flood_fill.c
@@ -5,29 +5,30 @@
// 1. Check that the (x,y) is within the picture
// 2. Check if the (x,y) coordinate in the mask is unused
// 3. Check if the (x,y) coordinate in the image is non-background
-// 4. Check if the (x,y) coordinate in the image is the same color as the fill color
+// 4. Check if the (x,y) coordinate in the image is the same color as the fill
+// color
// 5. If all hold, set the label for the pixel, and check each neighbor
// Otherwise, stop flooding
-bool_t flood(ImageData_t* image, MaskData_t* mask, size_t width, size_t height, size_t channels, size_t x, size_t y, ImageData_t* fill_color, MaskData_t label)
-{
+bool_t flood(ImageData_t *image, MaskData_t *mask, size_t width, size_t height,
+ size_t channels, size_t x, size_t y, ImageData_t *fill_color,
+ MaskData_t label) {
if ((x >= width) | (y >= height)) {
return FALSE;
}
- size_t coord = x + y*width;
+ size_t coord = x + y * width;
if (mask[coord] != 0) {
return FALSE;
}
- if (color_zero(&(image[coord*channels]), channels)) {
+ if (color_zero(&(image[coord * channels]), channels)) {
return FALSE;
}
- if (color_equal(&(image[coord*channels]), fill_color, channels)) {
+ if (color_equal(&(image[coord * channels]), fill_color, channels)) {
mask[coord] = label;
- flood(image, mask, width, height, channels, x, y+1, fill_color, label);
- flood(image, mask, width, height, channels, x, y-1, fill_color, label);
- flood(image, mask, width, height, channels, x+1, y, fill_color, label);
- flood(image, mask, width, height, channels, x-1, y, fill_color, label);
+ flood(image, mask, width, height, channels, x, y + 1, fill_color, label);
+ flood(image, mask, width, height, channels, x, y - 1, fill_color, label);
+ flood(image, mask, width, height, channels, x + 1, y, fill_color, label);
+ flood(image, mask, width, height, channels, x - 1, y, fill_color, label);
return TRUE;
}
return FALSE;
}
-
generated by cgit v1.2.1 (git 2.18.0) at 2025-10-31 02:19:33 +0000