]> mj.ucw.cz Git - libucw.git/blob - lib/heap.h
Added license notices to all library files which are not specific
[libucw.git] / 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)                                          \
66   do {                                                                                  \
67     uns j, l;                                                                           \
68     type x;                                                                             \
69     j = 1;                                                                              \
70     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                             \
71   } while(0)
72
73 #define HEAP_DELETE(type,heap,num,less,swap,pos)                                        \
74   do {                                                                                  \
75     uns j, l, u;                                                                        \
76     type x;                                                                             \
77     j = pos;                                                                            \
78     swap(heap,j,num,x);                                                                 \
79     num--;                                                                              \
80     if (less(heap[j], heap[num+1]))                                                     \
81       HEAP_BUBBLE_UP_J(heap,num,less,swap)                                              \
82     else                                                                                \
83       HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                           \
84   } while(0)