]>
Commit | Line | Data |
---|---|---|
bf139664 OZ |
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 | /** | |
12 | * [[intro]] | |
13 | * Introduction | |
14 | * ------------ | |
15 | * | |
16 | * Binary heap is a simple data structure, which for example supports efficient insertions, deletions | |
17 | * and access to the minimal inserted item. We define several macros for such operations. | |
18 | * Note that because of simplicity of heaps, we have decided to define direct macros instead | |
19 | * of a <<generic:,macro generator>> as for several other data structures in the Libucw. | |
20 | * | |
21 | * A heap is represented by a number of elements and by an array of values. Beware that we | |
22 | * index this array from one, not from zero as do the standard C arrays. | |
23 | * | |
24 | * Most macros use these parameters: | |
25 | * | |
26 | * - @type - the type of elements | |
27 | * - @num - a variable (signed or unsigned integer) with the number of elements | |
28 | * - @heap - a C array of type @type; the heap is stored in `heap[1] .. heap[num]`; `heap[0]` is unused | |
29 | * - @less - a callback to compare two element values; `less(x, y)` shall return a non-zero value iff @x is lower than @y | |
30 | * - @swap - a callback to swap two array elements; `swap(heap, i, j, t)` must swap `heap[i]` with `heap[j]` with possible help of temporary variable @t (type @type). | |
31 | * | |
32 | * A valid heap must follow these rules: | |
33 | * | |
34 | * - `num >= 0` | |
35 | * - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]` | |
36 | * | |
37 | * The first element `heap[1]` is always lower or equal to all other elements. | |
38 | * | |
39 | * [[macros]] | |
40 | * Macros | |
41 | * ------ | |
42 | */ | |
43 | ||
44 | /* For internal usage. */ | |
45 | #define HEAP_BUBBLE_DOWN_J(heap,num,less,swap) \ | |
46 | for (;;) \ | |
47 | { \ | |
48 | _l = 2*_j; \ | |
49 | if (_l > num) \ | |
50 | break; \ | |
51 | if (less(heap[_j],heap[_l]) && (_l == num || less(heap[_j],heap[_l+1]))) \ | |
52 | break; \ | |
53 | if (_l != num && less(heap[_l+1],heap[_l])) \ | |
54 | _l++; \ | |
55 | swap(heap,_j,_l,x); \ | |
56 | _j = _l; \ | |
57 | } | |
58 | ||
59 | /* For internal usage. */ | |
60 | #define HEAP_BUBBLE_UP_J(heap,num,less,swap) \ | |
61 | while (_j > 1) \ | |
62 | { \ | |
63 | _u = _j/2; \ | |
64 | if (less(heap[_u], heap[_j])) \ | |
65 | break; \ | |
66 | swap(heap,_u,_j,x); \ | |
67 | _j = _u; \ | |
68 | } | |
69 | ||
70 | /** | |
71 | * Shuffle the unordered array @heap of @num elements to become a valid heap. The time complexity is linear. | |
72 | **/ | |
73 | #define HEAP_INIT(heap,num,type,less,swap) \ | |
74 | do { \ | |
6a8d3f1c OZ |
75 | uint _i = num; \ |
76 | uint _j, _l; \ | |
bf139664 OZ |
77 | type x; \ |
78 | while (_i >= 1) \ | |
79 | { \ | |
80 | _j = _i; \ | |
81 | HEAP_BUBBLE_DOWN_J(heap,num,less,swap) \ | |
82 | _i--; \ | |
83 | } \ | |
84 | } while(0) | |
85 | ||
86 | /** | |
87 | * Delete the minimum element `heap[1]` in `O(log(n))` time. | |
88 | * The removed value is moved just after the resulting heap (`heap[num + 1]`). | |
89 | **/ | |
90 | #define HEAP_DELMIN(heap,num,type,less,swap) \ | |
91 | do { \ | |
6a8d3f1c | 92 | uint _j, _l; \ |
bf139664 OZ |
93 | type x; \ |
94 | swap(heap,1,num,x); \ | |
95 | num--; \ | |
96 | _j = 1; \ | |
97 | HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ | |
98 | } while(0) | |
99 | ||
100 | /** | |
101 | * Insert `heap[num]` in `O(log(n))` time. The value of @num must be increased before. | |
102 | **/ | |
103 | #define HEAP_INSERT(heap,num,type,less,swap) \ | |
104 | do { \ | |
6a8d3f1c | 105 | uint _j, _u; \ |
bf139664 OZ |
106 | type x; \ |
107 | _j = num; \ | |
108 | HEAP_BUBBLE_UP_J(heap,num,less,swap); \ | |
109 | } while(0) | |
110 | ||
111 | /** | |
112 | * If you need to increase the value of `heap[pos]`, just do it and then call this macro to rebuild the heap. | |
113 | * Only `heap[pos]` can be changed, the rest of the array must form a valid heap. | |
114 | * The time complexity is `O(log(n))`. | |
115 | **/ | |
116 | #define HEAP_INCREASE(heap,num,type,less,swap,pos) \ | |
117 | do { \ | |
6a8d3f1c | 118 | uint _j, _l; \ |
bf139664 OZ |
119 | type x; \ |
120 | _j = pos; \ | |
121 | HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ | |
122 | } while(0) | |
123 | ||
124 | /** | |
125 | * If you need to decrease the value of `heap[pos]`, just do it and then call this macro to rebuild the heap. | |
126 | * Only `heap[pos]` can be changed, the rest of the array must form a valid heap. | |
127 | * The time complexity is `O(log(n))`. | |
128 | **/ | |
129 | #define HEAP_DECREASE(heap,num,type,less,swap,pos) \ | |
130 | do { \ | |
6a8d3f1c | 131 | uint _j, _u; \ |
bf139664 OZ |
132 | type x; \ |
133 | _j = pos; \ | |
134 | HEAP_BUBBLE_UP_J(heap,num,less,swap); \ | |
135 | } while(0) | |
136 | ||
137 | /** | |
138 | * Delete `heap[pos]` in `O(log(n))` time. | |
139 | **/ | |
140 | #define HEAP_DELETE(heap,num,type,less,swap,pos) \ | |
141 | do { \ | |
6a8d3f1c | 142 | uint _j, _l, _u; \ |
bf139664 OZ |
143 | type x; \ |
144 | _j = pos; \ | |
145 | swap(heap,_j,num,x); \ | |
146 | num--; \ | |
147 | if (less(heap[_j], heap[num+1])) \ | |
148 | HEAP_BUBBLE_UP_J(heap,num,less,swap) \ | |
149 | else \ | |
150 | HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ | |
151 | } while(0) | |
152 | ||
153 | /** | |
154 | * Default swapping macro. | |
155 | **/ | |
156 | #define HEAP_SWAP(heap,a,b,t) (t=heap[a], heap[a]=heap[b], heap[b]=t) |