lib/heap.h

   1 /*
   2  *      Sherlock Library -- Universal Heap Macros
   3  *
   4  *      (c) 2001 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 #define HEAP_BUBBLE_DOWN_J(heap,num,less,swap)                                          \
   8   for (;;)                                                                              \
   9     {                                                                                   \
  10       l = 2*j;                                                                          \
  11       if (l > num)                                                                      \
  12         break;                                                                          \
  13       if (less(heap[j],heap[l]) && (l == num || less(heap[j],heap[l+1])))               \
  14         break;                                                                          \
  15       if (l != num && less(heap[l+1],heap[l]))                                          \
  16         l++;                                                                            \
  17       swap(heap,j,l,x);                                                                 \
  18       j = l;                                                                            \
  19     }
  20
  21 #define HEAP_BUBBLE_UP_J(heap,num,less,swap)                                            \
  22   while (j > 1)                                                                         \
  23     {                                                                                   \
  24       u = j/2;                                                                          \
  25       if (less(heap[u], heap[j]))                                                       \
  26         break;                                                                          \
  27       swap(heap,u,j,x);                                                                 \
  28       j = u;                                                                            \
  29     }
  30
  31 #define HEAP_INIT(type,heap,num,less,swap)                                              \
  32   do {                                                                                  \
  33     uns i = num;                                                                        \
  34     uns j, l;                                                                           \
  35     type x;                                                                             \
  36     while (i >= 1)                                                                      \
  37       {                                                                                 \
  38         j = i;                                                                          \
  39         HEAP_BUBBLE_DOWN_J(heap,num,less,swap)                                          \
  40         i--;                                                                            \
  41       }                                                                                 \
  42   } while(0)
  43
  44 #define HEAP_DELMIN(type,heap,num,less,swap)                                            \
  45   do {                                                                                  \
  46     uns j, l;                                                                           \
  47     type x;                                                                             \
  48     swap(heap,1,num,x);                                                                 \
  49     num--;                                                                              \
  50     j = 1;                                                                              \
  51     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                             \
  52   } while(0)
  53
  54 #define HEAP_INSERT(type,heap,num,less,swap)                                            \
  55   do {                                                                                  \
  56     uns j, u;                                                                           \
  57     type x;                                                                             \
  58     j = num;                                                                            \
  59     HEAP_BUBBLE_UP_J(heap,num,less,swap);                                               \
  60   } while(0)
  61
  62 #define HEAP_INCREASE(type,heap,num,less,swap)                                          \
  63   do {                                                                                  \
  64     uns j, l;                                                                           \
  65     type x;                                                                             \
  66     j = 1;                                                                              \
  67     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                             \
  68   } while(0)
  69
  70 #define HEAP_DELETE(type,heap,num,less,swap,pos)                                        \
  71   do {                                                                                  \
  72     uns j, l, u;                                                                        \
  73     type x;                                                                             \
  74     j = pos;                                                                            \
  75     swap(heap,j,num,x);                                                                 \
  76     num--;                                                                              \
  77     if (less(heap[j], heap[num+1]))                                                     \
  78       HEAP_BUBBLE_UP_J(heap,num,less,swap)                                              \
  79     else                                                                                \
  80       HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                           \
  81   } while(0)