/* Cesar project {{{ * * Copyright (C) 2007 Spidcom * * <<>> * * }}} */ /** * \file lib/src/leftheap.c * \brief Leftist heaps. * \ingroup lib */ #include "common/std.h" #include "lib/heap.h" void heap_node_init (heap_node_t *node) { node->father = NULL; node->left = node->right = NULL; node->null_path_length = 1; } heap_node_t * heap_node_merge (heap_node_t *root1, heap_node_t *root2, heap_node_less_t less) { heap_node_t *h, *h2, *root; dbg_assert (!root1 || !root1->father); dbg_assert (!root2 || !root2->father); dbg_assert (less); /* Trivial cases. */ if (!root1) return root2; else if (!root2) return root1; /* Initialise. */ if (less (root1, root2)) { h = root1; h2 = root2; } else { h = root2; h2 = root1; } root = h; /* Merge along the right paths. */ while (h2) { if (!h->right || less (h2, h->right)) { XCH (h2, h->right); h->right->father = h; } h = h->right; } /* Now walk up the path to fix balance. */ dbg_assert (h); for (; h; h = h->father) { uint lnpl = h->left ? h->left->null_path_length : 0; uint rnpl = h->right ? h->right->null_path_length : 0; if (lnpl < rnpl) { XCH (h->left, h->right); } h->null_path_length = 1 + MIN (lnpl, rnpl); } return root; } void heap_insert (heap_t *heap, heap_node_t *node) { dbg_assert (heap); dbg_assert (node); heap->root = heap_node_merge (heap->root, node, heap->less); } void heap_remove_root (heap_t *heap) { heap_node_t *root; dbg_assert (heap); dbg_assert (!heap_empty (heap)); root = heap->root; if (root->left) root->left->father = NULL; if (root->right) root->right->father = NULL; heap->root = heap_node_merge (root->left, root->right, heap->less); root->father = root->left = root->right = NULL; root->null_path_length = 1; } void heap_remove (heap_t *heap, heap_node_t *node) { heap_node_t **r; dbg_assert (heap); dbg_assert (!heap_empty (heap)); dbg_assert (node); /* Where to store the merged tree? */ if (!node->father) { dbg_assert (node == heap->root); r = &heap->root; } else if (node->father->right == node) { r = &node->father->right; } else { dbg_assert (node->father->left == node); r = &node->father->left; } /* Need NULL father pointer. */ if (node->left) node->left->father = NULL; if (node->right) node->right->father = NULL; /* Merge left and right subtree. */ *r = heap_node_merge (node->left, node->right, heap->less); if (*r) (*r)->father = node->father; /** * We can not just replace the removed node with a merge of its right and * left subtrees because this may change null_path_length. There is * several solutions: * - walk up the tree to fix balance, * - instead of one merge, do two merges, first with left subtree, then * right subtree, * - ignore this structure break... * * Here the first solution is chosen. */ heap_node_t *h; for (h = node->father; h; h = h->father) { uint lnpl = h->left ? h->left->null_path_length : 0; uint rnpl = h->right ? h->right->null_path_length : 0; if (lnpl < rnpl) { XCH (h->left, h->right); } uint nnpl = 1 + MIN (lnpl, rnpl); if (h->null_path_length == nnpl) break; h->null_path_length = nnpl; } /* Detach the removed node. */ node->father = node->left = node->right = NULL; node->null_path_length = 1; }