util/redblack_test.c

   1 /* Copyright (c) 2007-2008 Massachusetts Institute of Technology
   2  *
   3  * Permission is hereby granted, free of charge, to any person obtaining
   4  * a copy of this software and associated documentation files (the
   5  * "Software"), to deal in the Software without restriction, including
   6  * without limitation the rights to use, copy, modify, merge, publish,
   7  * distribute, sublicense, and/or sell copies of the Software, and to
   8  * permit persons to whom the Software is furnished to do so, subject to
   9  * the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be
  12  * included in all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  15  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  16  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  17  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  18  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  19  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  20  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  21  */
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <math.h>
  26 #include <time.h>
  27 #include "redblack.h"
  28
  29 static int comp(rb_key k1, rb_key k2)
  30 {
  31      if (*k1 < *k2) return -1;
  32      if (*k1 > *k2) return +1;
  33      return 0;
  34 }
  35
  36 int main(int argc, char **argv)
  37 {
  38      int N, M;
  39      int *k;
  40      double kd;
  41      rb_tree t;
  42      rb_node *n;
  43      int i, j;
  44
  45      if (argc < 2) {
  46           fprintf(stderr, "Usage: redblack_test Ntest [rand seed]\n");
  47           return 1;
  48      }
  49
  50      N = atoi(argv[1]);
  51      k = (int *) malloc(N * sizeof(int));
  52      rb_tree_init(&t, comp);
  53
  54      srand((unsigned) (argc > 2 ? atoi(argv[2]) : time(NULL)));
  55      for (i = 0; i < N; ++i) {
  56           double *newk = (double *) malloc(sizeof(double));
  57           *newk = (k[i] = rand() % N);
  58           if (!rb_tree_insert(&t, newk)) {
  59                fprintf(stderr, "error in rb_tree_insert\n");
  60                return 1;
  61           }
  62           if (!rb_tree_check(&t)) {
  63                fprintf(stderr, "rb_tree_check_failed after insert!\n");
  64                return 1;
  65           }
  66      }
  67
  68      if (t.N != N) {
  69           fprintf(stderr, "incorrect N (%d) in tree (vs. %d)\n", t.N, N);
  70           return 1;
  71      }
  72
  73      for (i = 0; i < N; ++i) {
  74           kd = k[i];
  75           if (!rb_tree_find(&t, &kd)) {
  76                fprintf(stderr, "rb_tree_find lost %d!\n", k[i]);
  77                return 1;
  78           }
  79      }
  80
  81      n = rb_tree_min(&t);
  82      for (i = 0; i < N; ++i) {
  83           if (!n) {
  84                fprintf(stderr, "not enough successors %d\n!", i);
  85                return 1;
  86           }
  87           printf("%d: %g\n", i, n->k[0]);
  88           n = rb_tree_succ(n);
  89      }
  90      if (n) {
  91           fprintf(stderr, "too many successors!\n");
  92           return 1;
  93      }
  94
  95      n = rb_tree_max(&t);
  96      for (i = 0; i < N; ++i) {
  97           if (!n) {
  98                fprintf(stderr, "not enough predecessors %d\n!", i);
  99                return 1;
 100           }
 101           printf("%d: %g\n", i, n->k[0]);
 102           n = rb_tree_pred(n);
 103      }
 104      if (n) {
 105           fprintf(stderr, "too many predecessors!\n");
 106           return 1;
 107      }
 108
 109      for (M = N; M > 0; --M) {
 110           int knew = rand() % N; /* random new key */
 111           j = rand() % M; /* random original key to replace */
 112           for (i = 0; i < N; ++i)
 113                if (k[i] >= 0)
 114                     if (j-- == 0)
 115                          break;
 116           if (i >= N) abort();
 117           kd = k[i];
 118           if (!(n = rb_tree_find(&t, &kd))) {
 119                fprintf(stderr, "rb_tree_find lost %d!\n", k[i]);
 120                return 1;
 121           }
 122           n->k[0] = knew;
 123           if (!rb_tree_resort(&t, n)) {
 124                fprintf(stderr, "error in rb_tree_resort\n");
 125                return 1;
 126           }
 127           if (!rb_tree_check(&t)) {
 128                fprintf(stderr, "rb_tree_check_failed after change %d!\n",
 129                        N - M + 1);
 130                return 1;
 131           }
 132           k[i] = -1 - knew;
 133      }
 134
 135      if (t.N != N) {
 136           fprintf(stderr, "incorrect N (%d) in tree (vs. %d)\n", t.N, N);
 137           return 1;
 138      }
 139
 140      for (i = 0; i < N; ++i)
 141           k[i] = -1 - k[i]; /* undo negation above */
 142
 143      for (i = 0; i < N; ++i) {
 144           rb_node *le, *gt;
 145           kd = 0.01 * (rand() % (N * 150) - N*25);
 146           le = rb_tree_find_le(&t, &kd);
 147           gt = rb_tree_find_gt(&t, &kd);
 148           n = rb_tree_min(&t);
 149           double lek = le ? le->k[0] : -HUGE_VAL;
 150           double gtk = gt ? gt->k[0] : +HUGE_VAL;
 151           printf("%g <= %g < %g\n", lek, kd, gtk);
 152           if (n->k[0] > kd) {
 153                if (le) {
 154                     fprintf(stderr, "found invalid le %g for %g\n", lek, kd);
 155                     return 1;
 156                }
 157                if (gt != n) {
 158                     fprintf(stderr, "gt is not first node for k=%g\n", kd);
 159                     return 1;
 160                }
 161           }
 162           else {
 163                rb_node *succ = n;
 164                do {
 165                     n = succ;
 166                     succ = rb_tree_succ(n);
 167                } while (succ && succ->k[0] <= kd);
 168                if (n != le) {
 169                     fprintf(stderr,
 170                             "rb_tree_find_le gave wrong result for k=%g\n",kd);
 171                     return 1;
 172                }
 173                if (succ != gt) {
 174                     fprintf(stderr,
 175                             "rb_tree_find_gt gave wrong result for k=%g\n",kd);
 176                     return 1;
 177                }
 178           }
 179      }
 180
 181      for (M = N; M > 0; --M) {
 182           j = rand() % M;
 183           for (i = 0; i < N; ++i)
 184                if (k[i] >= 0)
 185                     if (j-- == 0)
 186                          break;
 187           if (i >= N) abort();
 188           kd = k[i];
 189           if (!(n = rb_tree_find(&t, &kd))) {
 190                fprintf(stderr, "rb_tree_find lost %d!\n", k[i]);
 191                return 1;
 192           }
 193           n = rb_tree_remove(&t, n);
 194           free(n->k);
 195           free(n);
 196           if (!rb_tree_check(&t)) {
 197                fprintf(stderr, "rb_tree_check_failed after remove!\n");
 198                return 1;
 199           }
 200           k[i] = -1 - k[i];
 201      }
 202
 203      if (t.N != 0) {
 204           fprintf(stderr, "nonzero N (%d) in tree at end\n", t.N);
 205           return 1;
 206      }
 207
 208      rb_tree_destroy(&t);
 209      free(k);
 210
 211      printf("SUCCESS.\n");
 212      return 0;
 213 }