diff options
| -rw-r--r-- | src/main.c | 173 |
1 files changed, 173 insertions, 0 deletions
@@ -16,8 +16,181 @@ #define N_DILATIONS 3 +struct Result { + void* data; + bool_t success; +}; + +struct MaskData { + uint16_t label; + size_t area; + size_t perimeter; +}; + +struct MaskData* create_mask_data(uint16_t label) { + struct MaskData *data = (struct MaskData*)malloc(sizeof(struct MaskData)); + data->label = label; + data->area = 0; + data->perimeter = 0; + return data; +} + +struct AVLNode { + void* data; + bool_t (*compare)(void*, void*); + struct AVLNode* left; + struct AVLNode* right; + uint8_t height; +}; + +uint8_t get_height(struct AVLNode* node) +{ + if (node == NULL) { + return 0; + } + return node->height; +} + +bool_t compare_labels(struct MaskData* left, struct MaskData* right) +{ + return left->label < right->label; +} + +struct AVLNode* create_avl_mask_node(struct MaskData* data) +{ + struct AVLNode* node = (struct AVLNode*)malloc(sizeof(struct AVLNode)); + if (node == NULL) { + return NULL; + } + node->data = data; + node->compare = (bool_t (*)(void*,void*))&compare_labels; + node->left = NULL; + node->right = NULL; + node->height = 1; // Leaf initially + return node; +} + +uint8_t max_height(uint8_t a, uint8_t b) +{ + return (a > b) ? a : b; +} + +ssize_t get_balance_factor(struct AVLNode* node) +{ + if (node == NULL) { + return 0; + } + return get_height(node->left) - get_height(node->right); +} + +struct AVLNode* right_rotate(struct AVLNode* parent) +{ + struct AVLNode* child1 = parent->left; + struct 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; + return child1; +} + +struct AVLNode* left_rotate(struct AVLNode* parent) +{ + struct AVLNode* child1 = parent->right; + struct 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; + return child1; +} + +struct AVLNode* insert_mask(struct AVLNode* node, struct MaskData* data) +{ + // 1. Standard BST insertion + if (node == NULL) { + return create_avl_mask_node(data); + } + + struct MaskData *node_data = (struct MaskData*)node->data; + if (node->compare(data, node_data)) { + node->left = insert_mask(node->left, data); + } else if (node->compare(node->data, data)) { + node->right = insert_mask(node->right, data); + } else { + return node; + } + + // 2. Update height of the ancestor node + node->height = 1 + max_height(get_height(node->left), get_height(node->right)); + + ssize_t balance = get_balance_factor(node); + + // 4. If the node becomes unbalanced + + // LeftLeft + if ((balance > 1) && node->compare(data, node->left->data)) { + return right_rotate(node); + } + // RightRight + if ((balance < -1) && node->compare(node->right->data, data)) { + return left_rotate(node); + } + // LeftRight + if ((balance > 1) && node->compare(node->left->data, data)) { + return right_rotate(node); + } + // RightLeft + if ((balance < -1) && node->compare(data,node->right->data)) { + return left_rotate(node); + } + return node; +} + +void print_label(struct AVLNode* root) { + if (root != NULL) { + print_label(root->left); + struct MaskData* data = root->data; + printf("%d: (%zu, %zu) ", data->label, data->area, data->perimeter); + print_label(root->right); + } +} + +void free_avl_tree(struct AVLNode* root) { + if (root != NULL) { + free_avl_tree(root->left); + free_avl_tree(root->right); + free(root); + } +} + +void free_avl_tree_nodes(struct AVLNode* root) { + if (root != NULL) { + free_avl_tree_nodes(root->left); + free_avl_tree_nodes(root->right); + if (root->data != NULL) { + free(root->data); + } + free(root); + } +} + int main(int argc, char** argv) { + struct AVLNode* root = NULL; + root = insert_mask(root, create_mask_data(2)); + root = insert_mask(root, create_mask_data(5)); + root = insert_mask(root, create_mask_data(1)); + root = insert_mask(root, create_mask_data(3)); + root = insert_mask(root, create_mask_data(4)); + printf("Inorder traversal of AVL tree: "); + print_label(root); + printf("\n"); + free_avl_tree_nodes(root); //----------------------------------------------- //-LIST-FILES-IN-DIRECTORY----------------------- //----------------------------------------------- |