#include "prioq.h"
-flxPrioQueue* flx_prio_queue_new(gint (*compare) (gpointer a, gpointer b)) {
+flxPrioQueue* flx_prio_queue_new(gint (*compare) (gconstpointer a, gconstpointer b)) {
flxPrioQueue *q;
g_assert(compare);
}
static void exchange_nodes(flxPrioQueue *q, flxPrioQueueNode *a, flxPrioQueueNode *b) {
- flxPrioQueueNode *l, *r, *p, *ap, *an, *bp, *bn;
+ flxPrioQueueNode *l, *r, *p, *ap, *an, *bp, *bn, *apl, *bpl;
gint t;
g_assert(q);
g_assert(a);
}
} else {
/* Swap parents */
- p = a->parent;
+ ap = a->parent;
+ bp = b->parent;
+
+ if (ap)
+ apl = ap->left;
+ if (bp)
+ bpl = bp->left;
- if ((a->parent = b->parent)) {
- if (a->parent->left == b)
- a->parent->left = a;
- else
- a->parent->right = a;
+ if ((a->parent = bp)) {
+ if (bpl == b)
+ bp->left = a;
+ else
+ bp->right = a;
} else
q->root = a;
- if ((b->parent = p)) {
- if (b->parent->left == a)
- b->parent->left = b;
+ if ((b->parent = ap)) {
+ if (apl == a)
+ ap->left = b;
else
- b->parent->right = b;
+ ap->right = b;
} else
q->root = b;
}
/* Move a node to the correct position */
-static void shuffle_node(flxPrioQueue *q, flxPrioQueueNode *n) {
+void flx_prio_queue_shuffle(flxPrioQueue *q, flxPrioQueueNode *n) {
g_assert(q);
g_assert(n);
if (q->last) {
g_assert(q->root);
g_assert(q->n_nodes);
-
+
n->y = q->last->y;
n->x = q->last->x+1;
q->last = n;
q->n_nodes++;
- shuffle_node(q, n);
+ flx_prio_queue_shuffle(q, n);
return n;
}
if (n != q->last) {
flxPrioQueueNode *replacement = q->last;
exchange_nodes(q, replacement, n);
- flx_prio_queue_remove(q, q->last);
- shuffle_node(q, replacement);
+ flx_prio_queue_remove(q, n);
+ flx_prio_queue_shuffle(q, replacement);
return;
}
q->last = n->prev;
- if (n->prev)
+ if (n->prev) {
n->prev->next = NULL;
- else
+ g_assert(n->parent);
+ } else
g_assert(!n->parent);
if (n->parent) {
g_assert(n->prev);
if (n->parent->left == n) {
+ if (n->parent->right != NULL) {
+ g_message("fuck");
+ for (;;);
+
+ }
+
g_assert(n->parent->right == NULL);
n->parent->left = NULL;
} else {
} else {
g_assert(q->root == n);
g_assert(!n->prev);
+ g_assert(q->n_nodes == 1);
q->root = NULL;
}
- q->n_nodes--;
-
g_free(n);
+
+ g_assert(q->n_nodes > 0);
+ q->n_nodes--;
}
+