lib/heap.h

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