ucw/binheap-test.c

   1 /*
   2  *      UCW Library -- Binomial Heaps: Testing
   3  *
   4  *      (c) 2003 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #include "ucw/lib.h"
  11
  12 #include <stdio.h>
  13 #include <string.h>
  14
  15 #define BH_PREFIX(x) bht_##x
  16 #define BH_WANT_INSERT
  17 #define BH_WANT_FINDMIN
  18 #define BH_WANT_DELETEMIN
  19 #include "ucw/binheap-node.h"
  20
  21 struct item {
  22   struct bh_node n;
  23   uns key;
  24 };
  25
  26 static inline uns bht_key(struct bh_node *n)
  27 {
  28   return ((struct item *)n)->key;
  29 }
  30
  31 static inline uns bht_less(struct bh_node *a, struct bh_node *b)
  32 {
  33   return bht_key(a) < bht_key(b);
  34 }
  35
  36 static void
  37 bht_do_dump(struct bh_node *a, struct bh_node *expected_last, uns offset)
  38 {
  39   if (!a)
  40     return;
  41   printf("%*s", offset, "");
  42   printf("[%d](%d)%s\n", a->order, bht_key(a), a == expected_last ? " L" : "");
  43   for (struct bh_node *b=a->first_son; b; b=b->next_sibling)
  44     bht_do_dump(b, a->last_son, offset+1);
  45 }
  46
  47 static void
  48 bht_dump(struct bh_heap *h)
  49 {
  50   printf("root\n");
  51   for (struct bh_node *b=h->root.first_son; b; b=b->next_sibling)
  52     bht_do_dump(b, b->last_son, 1);
  53 }
  54
  55 #include "ucw/binheap.h"
  56
  57 int main(void)
  58 {
  59   uns i;
  60   struct bh_heap h;
  61 #define N 1048576
  62 #define K(i) ((259309*i+1009)%N)
  63
  64   bht_init(&h);
  65
  66   for (i=0; i<N; i++)
  67     {
  68       struct item *a = xmalloc_zero(sizeof(*a));
  69       a->key = K(i);
  70       // printf("Insert %d\n", a->key);
  71       bht_insert(&h, &a->n);
  72       // bht_dump(&h);
  73     }
  74   // bht_dump(&h);
  75   ASSERT(bht_key(bht_findmin(&h)) == 0);
  76   uns cnt = 0;
  77   BH_FOR_ALL(bht_, &h, a)
  78     {
  79       cnt++;
  80     }
  81   BH_END_FOR;
  82   printf("cnt=%d\n", cnt);
  83   ASSERT(cnt == N);
  84   for (i=0; i<N; i++)
  85     {
  86       struct item *a = (struct item *) bht_deletemin(&h);
  87       // printf("\nDeleted %d:\n", a->key);
  88       ASSERT(a->key == i);
  89       // bht_dump(&h);
  90     }
  91   bht_dump(&h);
  92
  93   return 0;
  94 }