git.meshlink.io Git - catta/blob - prioq-test.c

   1 #include <time.h>
   2 #include <stdlib.h>
   3 #include <stdio.h>
   4
   5 #include "prioq.h"
   6
   7 static gint compare_int(gconstpointer a, gconstpointer b) {
   8     gint i = GPOINTER_TO_INT(a), j = GPOINTER_TO_INT(b);
   9
  10     return i < j ? -1 : (i > j ? 1 : 0);
  11 }
  12
  13 static int compare_ptr(gconstpointer a, gconstpointer b) {
  14     return a < b ? -1 : (a > b ? 1 : 0);
  15 }
  16
  17 static void rec(flxPrioQueueNode *n) {
  18     if (!n)
  19         return;
  20
  21     if (n->left)
  22         g_assert(n->left->parent == n);
  23
  24     if (n->right)
  25         g_assert(n->right->parent == n);
  26
  27     if (n->parent) {
  28         g_assert(n->parent->left == n || n->parent->right == n);
  29
  30         if (n->parent->left == n)
  31             g_assert(n->next == n->parent->right);
  32     }
  33
  34     if (!n->next) {
  35         g_assert(n->queue->last == n);
  36
  37         if (n->parent && n->parent->left == n)
  38             g_assert(n->parent->right == NULL);
  39     }
  40
  41
  42     if (n->parent) {
  43         int a = GPOINTER_TO_INT(n->parent->data), b = GPOINTER_TO_INT(n->data);
  44         if (a > b) {
  45             printf("%i <= %i: NO\n", a, b);
  46             abort();
  47         }
  48     }
  49
  50     rec(n->left);
  51     rec(n->right);
  52 }
  53
  54 int main(int argc, char *argv[]) {
  55     flxPrioQueue *q, *q2;
  56     gint i, prev;
  57
  58     q = flx_prio_queue_new(compare_int);
  59     q2 = flx_prio_queue_new(compare_ptr);
  60
  61     srand(time(NULL));
  62
  63     for (i = 0; i < 10000; i++)
  64         flx_prio_queue_put(q2, flx_prio_queue_put(q, GINT_TO_POINTER(random() & 0xFFFF)));
  65
  66     while (q2->root) {
  67         rec(q->root);
  68         rec(q2->root);
  69
  70         g_assert(q->n_nodes == q2->n_nodes);
  71
  72         printf("%i\n", GPOINTER_TO_INT(((flxPrioQueueNode*)q2->root->data)->data));
  73
  74         flx_prio_queue_remove(q, q2->root->data);
  75         flx_prio_queue_remove(q2, q2->root);
  76     }
  77
  78
  79 /*     prev = 0; */
  80 /*     while (q->root) { */
  81 /*         gint v = GPOINTER_TO_INT(q->root->data); */
  82 /*         rec(q->root); */
  83 /*         printf("%i\n", v); */
  84 /*         flx_prio_queue_remove(q, q->root); */
  85 /*         g_assert(v >= prev); */
  86 /*         prev = v; */
  87 /*     } */
  88
  89     flx_prio_queue_free(q);
  90     return 0;
  91 }