summaryrefslogtreecommitdiff
path: root/cesar/lib/src/skewheap.c
blob: 6da16d597ef5c35053af26a66816b962171d7fd7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/* Cesar project {{{
 *
 * Copyright (C) 2007 Spidcom
 *
 * <<<Licence>>>
 *
 * }}} */
/**
 * \file    lib/src/skewheap.c
 * \brief   Skew 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;
}

heap_node_t *
heap_node_merge (heap_node_t *root1, heap_node_t *root2,
                 heap_node_less_t less)
{
    heap_node_t *h1, *h2, *h, *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;
    h1 = root1;
    h2 = root2;
    /* Skew merge root.
     * h1 and h2: current "read" node.
     * h: current "write" node.
     * h->left: where the next node will be put. */
    if (less (h1, h2))
    {
        h = h1;
        h1 = h1->right;
    }
    else
    {
        h = h2;
        h2 = h2->right;
    }
    root = h;
    h->right = h->left;
    /* Skew merge loop. */
    while (h1 || h2)
    {
        if (!h2 || (h1 && less (h1, h2)))
        {
            h1->father = h;
            h->left = h1;
            h = h1;
            h1 = h1->right;
        }
        else
        {
            h2->father = h;
            h->left = h2;
            h = h2;
            h2 = h2->right;
        }
        h->right = h->left;
    }
    h->left = NULL;
    return root;
}

void
heap_insert (heap_t *heap, heap_node_t *node)
{
    dbg_assert (heap && heap->less);
    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;
}

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;
    /* Swap father children. */
    if (node->father)
        XCH (node->father->left, node->father->right);
    /* Detach the removed node. */
    node->father = node->left = node->right = NULL;
}