tests/test_adt_smallheap.cpp

   1 #include "jitcs_int_adt_smallheap.h"
   2 #include "unittest.h"
   3
   4 #include <stdio.h>
   5
   6 using namespace jitcs;
   7
   8 template <unsigned N, bool B>
   9 void dump(const char* msg, SmallTopHeap<u32, N, B>& th) {
  10   printf("%s: SmallTopHeap:\n", msg);
  11   printf("  heap:");
  12   for (size_t i = 0; i < th.size; ++i) {
  13     if (B) {
  14       printf(" %d:%d(%d)", i, th.heap[i], th.values[i]);
  15     } else {
  16       printf(" %d:%d", i, th.heap[i]);
  17     }
  18   }
  19   printf("\n");
  20   printf("  hpos:");
  21   for (size_t i = 0; i < th.NUM; ++i) {
  22     if (th.hpos[i] >= th.size) continue;
  23     if (th.heap[th.hpos[i]] != i) continue;
  24     if (B) {
  25       printf(" %d->%d", i, th.hpos[i]);
  26     } else {
  27       printf(" %d(%d)->%d", i, th.values[i], th.hpos[i]);
  28     }
  29   }
  30   printf("\n");
  31 }
  32
  33 static void test(UnitTest& t) {
  34   SmallTopHeap<u32, 32, false> h1;
  35   t.check("unordered val/empty", h1.isEmpty());
  36   h1.push(5, 1000);
  37   h1.push(1, 2000);
  38   h1.push(7, 1500);
  39   h1.push(3, 1800);
  40   h1.push(9,  800);
  41   h1.push(13, 900);
  42   h1.push(14, 900);
  43   h1.push(15, 900);
  44   t.check("unordered val/check 1", h1.check());
  45   t.check("unordered val/top",
  46           h1.peekTop() == 1 && h1.peekTopValue() == 2000);
  47   h1.dropTop();
  48   t.check("unordered val/check after droptop", h1.check());
  49   t.check("unordered val/top 2",
  50           h1.peekTop() == 3 && h1.peekTopValue() == 1800);
  51   h1.drop(7);
  52   t.check("unordered val/check after drop", h1.check());
  53   t.check("unordered val/top 3",
  54           h1.peekTop() == 3 && h1.peekTopValue() == 1800);
  55   h1.dropTop();
  56   h1.dropTop();
  57   h1.dropTop();
  58   h1.dropTop();
  59   h1.dropTop();
  60   t.check("unordered val/check after drop 5", h1.check());
  61   t.check("unordered val/top last",
  62           h1.peekTop() == 9 && h1.peekTopValue() == 800);
  63   h1.dropTop();
  64   t.check("unordered val/check empty", h1.isEmpty());
  65
  66   SmallTopHeap<u32, 32, true> h2;
  67   t.check("ordered val/empty", h2.isEmpty());
  68   h2.push(5, 1000);
  69   h2.push(1, 2000);
  70   h2.push(7, 1500);
  71   h2.push(3, 1800);
  72   h2.push(9,  800);
  73   h2.push(13, 900);
  74   h2.push(14, 900);
  75   h2.push(15, 900);
  76   t.check("ordered val/check 1", h2.check());
  77   t.check("ordered val/top",
  78           h2.peekTop() == 1 && h2.peekTopValue() == 2000);
  79   h2.dropTop();
  80   t.check("ordered val/check after droptop", h2.check());
  81   t.check("ordered val/top 2",
  82           h2.peekTop() == 3 && h2.peekTopValue() == 1800);
  83   h2.drop(7);
  84   t.check("ordered val/check after drop", h2.check());
  85   t.check("ordered val/top 3",
  86           h2.peekTop() == 3 && h2.peekTopValue() == 1800);
  87   h2.dropTop();
  88   h2.dropTop();
  89   h2.dropTop();
  90   h2.dropTop();
  91   h2.dropTop();
  92   t.check("ordered val/check after drop 5", h2.check());
  93   t.check("ordered val/top last",
  94           h2.peekTop() == 9 && h2.peekTopValue() == 800);
  95   h2.dropTop();
  96   t.check("ordered val/check empty", h2.isEmpty());
  97 }
  98
  99 static UnitTestRun _1("ADT/SmallTopHeap", test);