c_cpp/lib/klib/test/krmq_test.c

   1 #include <stdio.h>
   2 #include <assert.h>
   3 #include <stdlib.h>
   4 #include <stdint.h>
   5 #include <string.h>
   6 #include <limits.h>
   7 #include "krmq.h"
   8
   9 #define CALLOC(type, num) ((type*)calloc(num, sizeof(type)))
  10
  11 struct my_node {
  12         int key;
  13         int val;
  14         KRMQ_HEAD(struct my_node) head;
  15 };
  16
  17 #define my_cmp(p, q) (((p)->key > (q)->key) - ((p)->key < (q)->key))
  18 #define my_lt2(p, q) ((p)->val < (q)->val)
  19 KRMQ_INIT(my, struct my_node, head, my_cmp, my_lt2)
  20
  21 int check(struct my_node *p, int *hh, int *min)
  22 {
  23         *hh = 0, *min = INT_MAX;
  24         if (p) {
  25                 int c = 1, h[2] = {0, 0}, m[2] = {INT_MAX, INT_MAX};
  26                 *min = p->val;
  27                 if (p->head.p[0]) c += check(p->head.p[0], &h[0], &m[0]);
  28                 if (p->head.p[1]) c += check(p->head.p[1], &h[1], &m[1]);
  29                 *min = *min < m[0]? *min : m[0];
  30                 *min = *min < m[1]? *min : m[1];
  31                 *hh = (h[0] > h[1]? h[0] : h[1]) + 1;
  32                 if (*min != p->head.s->val)
  33                         fprintf(stderr, "min %d != %d at %c\n", *min, p->head.s->val, p->key);
  34                 if (h[1] - h[0] != (int)p->head.balance)
  35                         fprintf(stderr, "%d - %d != %d at %c\n", h[1], h[0], p->head.balance, p->key);
  36                 if (c != (int)p->head.size)
  37                         fprintf(stderr, "%d != %d at %c\n", p->head.size, c, p->key);
  38                 return c;
  39         } else return 0;
  40 }
  41
  42 int check_rmq(const struct my_node *root, int lo, int hi)
  43 {
  44         struct my_node s, t, *p, *q;
  45         krmq_itr_t(my) itr;
  46         int min = INT_MAX;
  47         s.key = lo, t.key = hi;
  48         p = krmq_rmq(my, root, &s, &t);
  49         krmq_interval(my, root, &s, 0, &q);
  50         if (p == 0) return -1;
  51         krmq_itr_find(my, root, q, &itr);
  52         do {
  53                 const struct my_node *r = krmq_at(&itr);
  54                 if (r->key > hi) break;
  55                 //fprintf(stderr, "%c\t%d\n", r->key, r->val);
  56                 if (r->val < min) min = r->val;
  57         } while (krmq_itr_next(my, &itr));
  58         assert((min == INT_MAX && p == 0) || (min < INT_MAX && p));
  59         if (min != p->val) fprintf(stderr, "rmq_min %d != %d\n", p->val, min);
  60         return min;
  61 }
  62
  63 int print_tree(const struct my_node *p)
  64 {
  65         int c = 1;
  66         if (p == 0) return 0;
  67         if (p->head.p[0] || p->head.p[1]) {
  68                 putchar('(');
  69                 if (p->head.p[0]) c += print_tree(p->head.p[0]);
  70                 else putchar('.');
  71                 putchar(',');
  72                 if (p->head.p[1]) c += print_tree(p->head.p[1]);
  73                 else putchar('.');
  74                 putchar(')');
  75         }
  76         printf("%c:%d/%d", p->key, p->val, p->head.s->val);
  77         return c;
  78 }
  79
  80 void check_and_print(struct my_node *root)
  81 {
  82         int h, min;
  83         check(root, &h, &min);
  84         print_tree(root);
  85         putchar('\n');
  86 }
  87
  88 void shuffle(int n, char a[])
  89 {
  90         int i, j;
  91         for (i = n; i > 1; --i) {
  92                 char tmp;
  93                 j = (int)(drand48() * i);
  94                 tmp = a[j]; a[j] = a[i-1]; a[i-1] = tmp;
  95         }
  96 }
  97
  98 int main(void)
  99 {
 100         char buf[256];
 101         int i, n, h, min;
 102         struct my_node *root = 0;
 103         struct my_node *p, *q, t;
 104         krmq_itr_t(my) itr;
 105         unsigned cnt;
 106
 107         srand48(123);
 108         for (i = 33, n = 0; i <= 126; ++i)
 109                 if (i != '(' && i != ')' && i != '.' && i != ';')
 110                         buf[n++] = i;
 111         shuffle(n, buf);
 112         for (i = 0; i < n; ++i) {
 113                 p = CALLOC(struct my_node, 1);
 114                 p->key = buf[i];
 115                 p->val = i;
 116                 q = krmq_insert(my, &root, p, &cnt);
 117                 if (p != q) free(p);
 118                 check(root, &h, &min);
 119         }
 120
 121         shuffle(n, buf);
 122         for (i = 0; i < n/2; ++i) {
 123                 t.key = buf[i];
 124                 //fprintf(stderr, "i=%d, key=%c, n/2=%d\n", i, t.key, n/2);
 125                 q = krmq_erase(my, &root, &t, 0);
 126                 if (q) free(q);
 127                 check(root, &h, &min);
 128         }
 129         check_and_print(root);
 130
 131         check_rmq(root, '0', '9');
 132         check_rmq(root, '!', '~');
 133         check_rmq(root, 'A', 'Z');
 134         check_rmq(root, 'F', 'G');
 135         check_rmq(root, 'a', 'z');
 136         for (i = 0; i < n; ++i) {
 137                 int lo, hi;
 138                 lo = (int)(drand48() * n);
 139                 hi = (int)(drand48() * n);
 140                 check_rmq(root, lo, hi);
 141         }
 142
 143         krmq_itr_first(my, root, &itr);
 144         do {
 145                 const struct my_node *r = krmq_at(&itr);
 146                 putchar(r->key);
 147         } while (krmq_itr_next(my, &itr));
 148         putchar('\n');
 149         krmq_free(struct my_node, head, root, free);
 150         return 0;
 151 }