![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to heap.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / lib|
Return to heap.h CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / lib |
1.1 misho 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 { \
75: uint _i = num; \
76: uint _j, _l; \
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 { \
92: uint _j, _l; \
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 { \
105: uint _j, _u; \
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 { \
118: uint _j, _l; \
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 { \
131: uint _j, _u; \
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 { \
142: uint _j, _l, _u; \
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)