3 flxPrioQueue* flx_prio_queue_new(gint (*compare) (gconstpointer a, gconstpointer b)) {
7 q = g_new(flxPrioQueue, 1);
8 q->root = q->last = NULL;
14 void flx_prio_queue_free(flxPrioQueue *q) {
18 flx_prio_queue_remove(q, q->last);
20 g_assert(!q->n_nodes);
24 static flxPrioQueueNode* get_node_at_xy(flxPrioQueue *q, guint x, guint y) {
32 for (r = 0; r < y; r++) {
35 if ((x >> (y-r-1)) & 1)
47 static void exchange_nodes(flxPrioQueue *q, flxPrioQueueNode *a, flxPrioQueueNode *b) {
48 flxPrioQueueNode *l, *r, *p, *ap, *an, *bp, *bn;
56 t = a->x; a->x = b->x; b->x = t;
57 t = a->y; a->y = b->y; b->y = t;
60 /* B is parent of A */
65 if ((a->parent = p)) {
66 if (a->parent->left == b)
74 if ((b->left = a->left))
79 if ((a->right = b->right))
85 if ((b->right = a->right))
90 if ((a->left = b->left))
95 } else if (b->parent == a) {
96 /* A ist parent of B */
101 if ((b->parent = p)) {
102 if (b->parent->left == a)
105 b->parent->right = b;
110 if ((a->left = b->left))
115 if ((a->right = b->right))
116 a->right->parent = a;
118 b->right->parent = b;
120 if ((a->right = b->right))
121 a->right->parent = a;
125 if ((a->left = b->left))
134 if ((a->parent = b->parent)) {
135 if (a->parent->left == b)
138 a->parent->right = a;
142 if ((b->parent = p)) {
143 if (b->parent->left == a)
146 b->parent->right = b;
154 if ((a->left = b->left))
160 if ((a->right = b->right))
161 a->right->parent = a;
164 b->right->parent = b;
168 ap = a->prev; an = a->next;
169 bp = b->prev; bn = b->next;
172 /* A is predecessor of B */
184 } else if (b->next == a) {
185 /* B is predecessor of A */
198 /* A is no neighbour of B */
218 /* Move a node to the correct position */
219 void flx_prio_queue_shuffle(flxPrioQueue *q, flxPrioQueueNode *n) {
223 /* Move up until the position is OK */
224 while (n->parent && q->compare(n->parent->data, n->data) > 0)
225 exchange_nodes(q, n, n->parent);
227 /* Move down until the position is OK */
229 flxPrioQueueNode *min;
231 if (!(min = n->left)) {
237 if (n->right && q->compare(n->right->data, min->data) < 0)
240 /* min now contains the smaller one of our two children */
242 if (q->compare(n->data, min->data) <= 0)
246 exchange_nodes(q, n, min);
250 flxPrioQueueNode* flx_prio_queue_put(flxPrioQueue *q, gpointer data) {
254 n = g_new(flxPrioQueueNode, 1);
260 g_assert(q->n_nodes);
265 if (n->x >= ((guint) 1 << n->y)) {
274 n->parent = get_node_at_xy(q, n->x/2, n->y-1);
277 n->parent->right = n;
282 g_assert(!q->n_nodes);
286 n->prev = n->parent = NULL;
289 n->next = n->left = n->right = NULL;
293 flx_prio_queue_shuffle(q, n);
298 void flx_prio_queue_remove(flxPrioQueue *q, flxPrioQueueNode *n) {
303 flxPrioQueueNode *replacement = q->last;
304 exchange_nodes(q, replacement, n);
305 flx_prio_queue_remove(q, q->last);
306 flx_prio_queue_shuffle(q, replacement);
310 g_assert(n == q->last);
318 n->prev->next = NULL;
320 g_assert(!n->parent);
324 if (n->parent->left == n) {
325 g_assert(n->parent->right == NULL);
326 n->parent->left = NULL;
328 g_assert(n->parent->right == n);
329 g_assert(n->parent->left != NULL);
330 n->parent->right = NULL;
333 g_assert(q->root == n);