summaryrefslogtreecommitdiff
path: root/cesar/lib/src/leftheap.c
diff options
context:
space:
mode:
Diffstat (limited to 'cesar/lib/src/leftheap.c')
-rw-r--r--cesar/lib/src/leftheap.c159
1 files changed, 159 insertions, 0 deletions
diff --git a/cesar/lib/src/leftheap.c b/cesar/lib/src/leftheap.c
new file mode 100644
index 0000000000..8f7c6d3ad8
--- /dev/null
+++ b/cesar/lib/src/leftheap.c
@@ -0,0 +1,159 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \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;
+}
+