home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume28 / librb / part01 / main.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-02-23  |  1.8 KB  |  77 lines
  1. #include "rb.h"
  2. #include <stdio.h>
  3.  
  4. /* an example -- this allocates a red-black tree for integers.  For a 
  5.  * user-specified number of iterations, it does the following:
  6.  
  7.  * delete a random element in the tree.
  8.  * make two new random elements, and insert them into the tree
  9.  
  10.  * At the end, it prints the sorted list of elements, and then prints
  11.  * stats of the number of black nodes in any path in the tree, and 
  12.  * the minimum and maximum path lengths.
  13.   
  14.  * Rb_find_ikey and rb_inserti could have been used, but instead
  15.  * rb_find_gkey and rb_insertg were used to show how they work.
  16.   
  17.  */
  18.  
  19. int icomp(i, j)
  20. int i, j;
  21. {
  22.   if (i == j) return 0;
  23.   if (i > j) return -1; else return 1;
  24. }
  25.  
  26. main(argc, argv)
  27. int argc;
  28. char **argv;
  29. {
  30.   int i, j, tb, nb, mxp, mnp, p;
  31.   int iterations;
  32.   Rb_node argt, t;
  33.   int *a;
  34.  
  35.   if (argc != 2) {
  36.     fprintf(stderr, "usage: main #iterations\n");
  37.     exit(1);
  38.   }
  39.   argt = make_rb();
  40.   srandom(time(0));
  41.   iterations = atoi(argv[1]);
  42.   a = (int *) malloc (iterations*sizeof(int));
  43.  
  44.   for (i = 0; i < atoi(argv[1]); i++) {
  45.     if (i > 0) {
  46.       j = random()%i;
  47.       
  48.       rb_delete_node(rb_find_gkey(argt, a[j], icomp));
  49.       a[j] = random() % 1000;
  50.       rb_insertg(argt, a[j], 0, icomp);
  51.     }
  52.     a[i] = random() % 1000;
  53.     rb_insertg(argt, a[i], 0, icomp);
  54.   }
  55.   tb = 0;
  56.   mxp = 0;
  57.   mnp = 0;
  58.   for (t = rb_first(argt); t != nil(argt); t = rb_next(t)) {
  59.     printf("%d ", t->k.ikey);
  60.     nb = rb_nblack(t);
  61.     p = rb_plength(t);
  62.     if (tb == 0) {
  63.       tb = nb;
  64.     } else if (tb != nb) {
  65.       printf("Conflict: tb=%d, nb=%d\n", tb, nb);
  66.       exit(1);
  67.     }
  68.     mxp = (mxp == 0 || mxp < p) ? p : mxp;
  69.     mnp = (mnp == 0 || mxp > p) ? p : mnp;
  70.   }
  71.   printf("\n");  
  72.  
  73.   printf("Nblack = %d\n", tb);
  74.   printf("Max    = %d\n", mxp);
  75.   printf("Min    = %d\n", mnp);
  76. }
  77.