git.maemo.org Git - navit-package/blob - navit/fib-1.1/use.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <time.h>
   4
   5 #include "fib.h"
   6
   7 #define TESTCASE        1
   8
   9 #define COUNT   100000
  10 #define DIF     1000
  11 #define MAXEXT  10
  12 #define VERBOSE 1
  13
  14 int cmp(void *, void *);
  15
  16 int
  17 cmp(void *x, void *y)
  18 {
  19         int a, b;
  20         a = (int)x;
  21         b = (int)y;
  22
  23         if (a < b)
  24                 return -1;
  25         if (a == b)
  26                 return 0;
  27         return 1;
  28 }
  29
  30 int
  31 main(void)
  32 {
  33 #if !TESTCASE
  34         struct fibheap_el *w;
  35 #else
  36         int e, j, k;
  37 #endif
  38         struct fibheap *a;
  39         int i, x;
  40
  41         a = fh_makeheap();
  42         fh_setcmp(a, cmp);
  43
  44         srandom(time(NULL));
  45 #if TESTCASE
  46 #if VERBOSE
  47         printf("inserting: ");
  48 #endif
  49         e = 0;
  50         for (i = 0; i < COUNT; i++) {
  51 #if VERBOSE
  52                 if (i)
  53                         printf(", ");
  54 #endif
  55                 fh_insert(a, (void *)(x = random()/10));
  56 #if VERBOSE
  57                 printf("%d", x);
  58 #endif
  59                 if (i - e > DIF) {
  60                         k = random() % MAXEXT;
  61                         for (j = 0; j < k; j++, e++)
  62                                 printf("throwing: %d\n", (int)fh_extractmin(a));
  63                 }
  64         }
  65
  66 #if VERBOSE
  67         printf("\nremaining: %d\n", COUNT - e);
  68         printf("extracting: ");
  69 #endif
  70         for (i = 0; i < COUNT - e; i++) {
  71 #if VERBOSE
  72                 if (i)
  73                         printf(", ");
  74                 printf("%d", (int)fh_extractmin(a));
  75 #else
  76                 fh_extractmin(a);
  77 #endif
  78         }
  79 #if VERBOSE
  80         printf("\n");
  81 #endif
  82         if ((int)fh_extractmin(a) == 0)
  83                 printf("heap empty!\n");
  84         else {
  85                 printf("heap not empty! ERROR!\n");
  86                 exit(1);
  87         }
  88 #else
  89         w = fh_insert(a, (void *)6);
  90         printf("adding: %d\n", 6);
  91         fh_insert(a, (void *)9);
  92         printf("adding: %d\n", 9);
  93         fh_insert(a, (void *)1);
  94         printf("adding: %d\n", 1);
  95         for(i = 0; i < 5; i++) {
  96                 x = random()/10000;
  97                 printf("adding: %d\n", x);
  98                 fh_insert(a, (void *)x);
  99         }
 100         fh_insert(a, (void *)4);
 101         printf("adding: %d\n", 4);
 102         fh_insert(a, (void *)8);
 103         printf("adding: %d\n", 8);
 104         printf("first: %d\n", (int)fh_extractmin(a));
 105         printf("deleting: %d\n", (int)fh_delete(a, w));
 106         printf("first: %d\n", (int)fh_extractmin(a));
 107         printf("first: %d\n", (int)fh_extractmin(a));
 108         printf("first: %d\n", (int)fh_extractmin(a));
 109         printf("first: %d\n", (int)fh_extractmin(a));
 110         printf("first: %d\n", (int)fh_extractmin(a));
 111         for(i = 0; i < 5; i++) {
 112                 x = random()/10000;
 113                 printf("adding: %d\n", x);
 114                 fh_insert(a, (void *)x);
 115         }
 116         printf("first: %d\n", (int)fh_extractmin(a));
 117         printf("first: %d\n", (int)fh_extractmin(a));
 118         printf("first: %d\n", (int)fh_extractmin(a));
 119         printf("first: %d\n", (int)fh_extractmin(a));
 120         printf("first: %d\n", (int)fh_extractmin(a));
 121 #endif
 122
 123         fh_deleteheap(a);
 124
 125         return 0;
 126 }