lib/heap.h

   1 /*
   2  *      Sherlock Library -- Universal Heap Macros
   3  *
   4  *      (c) 2001 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #define HEAP_BUBBLE_DOWN_J(heap,num,less,swap)                                          \
  11   for (;;)                                                                              \
  12     {                                                                                   \
  13       l = 2*j;                                                                          \
  14       if (l > num)                                                                      \
  15         break;                                                                          \
  16       if (less(heap[j],heap[l]) && (l == num || less(heap[j],heap[l+1])))               \
  17         break;                                                                          \
  18       if (l != num && less(heap[l+1],heap[l]))                                          \
  19         l++;                                                                            \
  20       swap(heap,j,l,x);                                                                 \
  21       j = l;                                                                            \
  22     }
  23
  24 #define HEAP_BUBBLE_UP_J(heap,num,less,swap)                                            \
  25   while (j > 1)                                                                         \
  26     {                                                                                   \
  27       u = j/2;                                                                          \
  28       if (less(heap[u], heap[j]))                                                       \
  29         break;                                                                          \
  30       swap(heap,u,j,x);                                                                 \
  31       j = u;                                                                            \
  32     }
  33
  34 #define HEAP_INIT(type,heap,num,less,swap)                                              \
  35   do {                                                                                  \
  36     uns i = num;                                                                        \
  37     uns j, l;                                                                           \
  38     type x;                                                                             \
  39     while (i >= 1)                                                                      \
  40       {                                                                                 \
  41         j = i;                                                                          \
  42         HEAP_BUBBLE_DOWN_J(heap,num,less,swap)                                          \
  43         i--;                                                                            \
  44       }                                                                                 \
  45   } while(0)
  46
  47 #define HEAP_DELMIN(type,heap,num,less,swap)                                            \
  48   do {                                                                                  \
  49     uns j, l;                                                                           \
  50     type x;                                                                             \
  51     swap(heap,1,num,x);                                                                 \
  52     num--;                                                                              \
  53     j = 1;                                                                              \
  54     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                             \
  55   } while(0)
  56
  57 #define HEAP_INSERT(type,heap,num,less,swap)                                            \
  58   do {                                                                                  \
  59     uns j, u;                                                                           \
  60     type x;                                                                             \
  61     j = num;                                                                            \
  62     HEAP_BUBBLE_UP_J(heap,num,less,swap);                                               \
  63   } while(0)
  64
  65 #define HEAP_INCREASE(type,heap,num,less,swap,pos)                                      \
  66   do {                                                                                  \
  67     uns j, l;                                                                           \
  68     type x;                                                                             \
  69     j = pos;                                                                            \
  70     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                             \
  71   } while(0)
  72
  73 #define HEAP_DECREASE(type,heap,num,less,swap,pos)                                      \
  74   do {                                                                                  \
  75     uns j, l;                                                                           \
  76     type x;                                                                             \
  77     j = pos;                                                                            \
  78     HEAP_BUBBLE_UP_J(heap,num,less,swap);                                               \
  79   } while(0)
  80
  81 #define HEAP_CHANGE(type,heap,num,less,swap,pos)                                        \
  82   do {                                                                                  \
  83     uns j, l, u;                                                                        \
  84     type x;                                                                             \
  85     j = pos;                                                                            \
  86     if (j == 1)                                                                         \
  87       ;                                                                                 \
  88     else if (less(heap[j], heap[j/2]))                                                  \
  89       HEAP_BUBBLE_UP_J(heap,num,less,swap)                                              \
  90     else                                                                                \
  91       HEAP_BUBBLE_DOWN_J(heap,num,less,swap)                                            \
  92   } while(0)
  93
  94 #define HEAP_DELETE(type,heap,num,less,swap,pos)                                        \
  95   do {                                                                                  \
  96     uns j, l, u;                                                                        \
  97     type x;                                                                             \
  98     j = pos;                                                                            \
  99     swap(heap,j,num,x);                                                                 \
 100     num--;                                                                              \
 101     if (less(heap[j], heap[num+1]))                                                     \
 102       HEAP_BUBBLE_UP_J(heap,num,less,swap)                                              \
 103     else                                                                                \
 104       HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                           \
 105   } while(0)