include/c++/util/tests/heap.cc

   1 #include <util/heap.h>
   2 #include <stdlib.h>
   3 #include <stdio.h>
   4 #include <time.h>
   5
   6 using Util::Heap;
   7
   8 struct Data {
   9         unsigned int magic;
  10         unsigned int data;
  11         Heap<Data>::Node heap_node;
  12
  13         bool operator < (Data &d)
  14         {
  15                 return data < d.data;
  16         }
  17
  18         Data()
  19         {
  20                 magic = 0xdeadbeef;
  21         }
  22 };
  23
  24 static const int heap_size = 10000;
  25
  26 Data data[heap_size];
  27
  28 int main(void)
  29 {
  30         Heap<Data> heap;
  31         srandom(1);
  32
  33         for (int i = 0; i < heap_size; i++) {
  34                 Data *d = &data[i];
  35                 d->data = random() & 0x7fffffff;
  36                 heap.add(d);
  37         }
  38
  39         unsigned int last = 0;
  40
  41         for (int i = 0; i < heap_size; i++) {
  42                 Data *d = heap.get_top();
  43                 if (d == NULL) {
  44                         printf("FAILED: returned NULL early\n");
  45                         exit(1);
  46                 }
  47
  48                 if (d->magic != 0xdeadbeef) {
  49                         printf("FAILED: garbage data returned\n");
  50                         exit(1);
  51                 }
  52
  53                 if (d->data >= 0x80000000) {
  54                         printf("FAILED: duplicate or garbage data returned\n");
  55                         exit(1);
  56                 }
  57
  58                 heap.del(d);
  59
  60                 if (d->data < last) {
  61                         printf("FAILED: not monotonically increasing\n");
  62                         exit(1);
  63                 }
  64
  65                 last = d->data;
  66                 d->data = 0x80000000;
  67         }
  68
  69         for (int i = 0; i < heap_size; i++) {
  70                 Data *d = &data[i];
  71                 d->data = random() & 0x7fffffff;
  72                 heap.add(d);
  73         }
  74
  75         last = 0;
  76
  77         for (int i = 0; i < heap_size; i++) {
  78                 Data *d = heap.get_top();
  79                 if (d == NULL) {
  80                         printf("FAILED: with requeue: returned NULL early\n");
  81                         exit(1);
  82                 }
  83
  84                 if (d->magic != 0xdeadbeef) {
  85                         printf("FAILED: with requeue: garbage data returned\n");
  86                         exit(1);
  87                 }
  88
  89                 if (d->data >= 0x80000000) {
  90                         printf("FAILED: with requeue: duplicate or garbage data returned\n");
  91                         exit(1);
  92                 }
  93
  94                 heap.del(d);
  95
  96                 if (d->data < last) {
  97                         printf("FAILED: with requeue: not monotonically increasing\n");
  98                         exit(1);
  99                 }
 100
 101                 last = d->data;
 102                 d->data = 0x80000000;
 103
 104                 for (int j = 0; j < 10; j++) {
 105                         d = &data[random() % heap_size];
 106
 107                         if (d->data == 0x80000000)
 108                                 continue;
 109
 110                         d->data = random() & 0x7fffffff;
 111                         heap.requeue(d);
 112
 113                         if (d->data < last)
 114                                 last = d->data;
 115                 }
 116         }
 117
 118         printf("PASSED\n");
 119 }