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, *apl, *bpl;
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))
140 if ((a->parent = bp)) {
148 if ((b->parent = ap)) {
160 if ((a->left = b->left))
166 if ((a->right = b->right))
167 a->right->parent = a;
170 b->right->parent = b;
174 ap = a->prev; an = a->next;
175 bp = b->prev; bn = b->next;
178 /* A is predecessor of B */
190 } else if (b->next == a) {
191 /* B is predecessor of A */
204 /* A is no neighbour of B */
224 /* Move a node to the correct position */
225 void flx_prio_queue_shuffle(flxPrioQueue *q, flxPrioQueueNode *n) {
229 /* Move up until the position is OK */
230 while (n->parent && q->compare(n->parent->data, n->data) > 0)
231 exchange_nodes(q, n, n->parent);
233 /* Move down until the position is OK */
235 flxPrioQueueNode *min;
237 if (!(min = n->left)) {
243 if (n->right && q->compare(n->right->data, min->data) < 0)
246 /* min now contains the smaller one of our two children */
248 if (q->compare(n->data, min->data) <= 0)
252 exchange_nodes(q, n, min);
256 flxPrioQueueNode* flx_prio_queue_put(flxPrioQueue *q, gpointer data) {
260 n = g_new(flxPrioQueueNode, 1);
266 g_assert(q->n_nodes);
271 if (n->x >= ((guint) 1 << n->y)) {
280 n->parent = get_node_at_xy(q, n->x/2, n->y-1);
283 n->parent->right = n;
288 g_assert(!q->n_nodes);
292 n->prev = n->parent = NULL;
295 n->next = n->left = n->right = NULL;
299 flx_prio_queue_shuffle(q, n);
304 void flx_prio_queue_remove(flxPrioQueue *q, flxPrioQueueNode *n) {
309 flxPrioQueueNode *replacement = q->last;
310 exchange_nodes(q, replacement, n);
311 flx_prio_queue_remove(q, n);
312 flx_prio_queue_shuffle(q, replacement);
316 g_assert(n == q->last);
324 n->prev->next = NULL;
327 g_assert(!n->parent);
331 if (n->parent->left == n) {
332 if (n->parent->right != NULL) {
338 g_assert(n->parent->right == NULL);
339 n->parent->left = NULL;
341 g_assert(n->parent->right == n);
342 g_assert(n->parent->left != NULL);
343 n->parent->right = NULL;
346 g_assert(q->root == n);
348 g_assert(q->n_nodes == 1);
354 g_assert(q->n_nodes > 0);