417a4d0b409511e85209bf032435f4a30726707e
[cgds.git] / src / Heap.c
1 /**
2 * @file Heap.c
3 */
4
5 #include "cgds/Heap.h"
6
7 // NOTE: no init() method here, since Heap has no specific initialization
8
9 Heap* _heap_new(size_t dataSize, OrderType hType, UInt arity)
10 {
11 Heap* heap = (Heap*) safe_malloc(sizeof(Heap));
12 heap->arity = arity;
13 heap->hType = hType;
14 heap->items = _vector_new(dataSize);
15 heap->values = _vector_new(sizeof(Real));
16 return heap;
17 }
18
19 Heap* heap_copy(Heap* heap)
20 {
21 Heap* heapCopy = (Heap*) safe_malloc(sizeof(Heap));
22 heapCopy->arity = heap->arity;
23 heapCopy->hType = heap->hType;
24 heapCopy->items = vector_copy(heap->items);
25 heapCopy->values = vector_copy(heap->values);
26 return heapCopy;
27 }
28
29 bool heap_empty(Heap* heap)
30 {
31 return vector_empty(heap->items);
32 }
33
34 UInt heap_size(Heap* heap)
35 {
36 return vector_size(heap->items);
37 }
38
39 // NOTE: [perf] in two following methods, full heap[k] exchanges are
40 // not needed; we keep track of the moving element without assigning it at
41 // every step, thus saving array accesses and affectations + 'aux' tmp memory.
42 // --> this is not the most natural way of writing these functions.
43
44 void _heap_bubble_up(Heap* heap, UInt startIndex)
45 {
46 if (startIndex == 0)
47 // Nothing to do in this case
48 return;
49 UInt currentIndex = startIndex;
50 void* startItem = _vector_get(heap->items, startIndex);
51 Real startValue = *((Real*)(_vector_get(heap->values, startIndex)));
52 bool startItemReallocated = false;
53 while (true)
54 {
55 bool land = (currentIndex == 0), //at root: can't go up
56 applyExchange = true;
57 if (!land)
58 {
59 // Get parent and compare to it
60 UInt nextIndex = (currentIndex - 1) / heap->arity;
61 Real nextValue = *((Real*)(_vector_get(heap->values, nextIndex)));
62 land = (
63 (heap->hType == MIN_T && startValue >= nextValue) ||
64 (heap->hType == MAX_T && startValue <= nextValue)
65 );
66 if (!land)
67 {
68 // Move one level up: the parent goes one level down
69 if (currentIndex == startIndex)
70 {
71 // Save startItem (because *startItem is about to be changed)
72 void* newStartItem = safe_malloc(heap->items->dataSize);
73 memcpy(newStartItem, startItem, heap->items->dataSize);
74 startItem = newStartItem;
75 startItemReallocated = true;
76 }
77 void* nextItem = _vector_get(heap->items, nextIndex);
78 _vector_set(heap->items, currentIndex, nextItem);
79 _vector_set(heap->values, currentIndex, &nextValue);
80 currentIndex = nextIndex;
81 continue;
82 }
83 // At correct relative place: will now land
84 if (currentIndex == startIndex)
85 applyExchange = false;
86 }
87 if (applyExchange)
88 {
89 _vector_set(heap->items, currentIndex, startItem);
90 _vector_set(heap->values, currentIndex, &startValue);
91 }
92 break;
93 }
94 if (startItemReallocated)
95 safe_free(startItem);
96 }
97
98 void _heap_bubble_down(Heap* heap, UInt startIndex)
99 {
100 if (startIndex * heap->arity + 1 >= heap->items->size)
101 // Nothing to do: already in a leaf
102 return;
103 UInt currentIndex = startIndex;
104 void* startItem = _vector_get(heap->items, startIndex);
105 Real startValue = *((Real*)(_vector_get(heap->values, startIndex)));
106 bool startItemReallocated = false;
107 while (true)
108 {
109 bool land = (currentIndex * heap->arity + 1 >= heap->items->size),
110 applyExchange = true;
111 if (!land)
112 {
113 // Find top child (min or max)
114 UInt topChildIndex;
115 Real topChildValue = (heap->hType == MIN_T ? INFINITY : -INFINITY);
116 for (UInt i = 1; i <= heap->arity; i++)
117 {
118 UInt childIndex = currentIndex * heap->arity + i;
119 if (childIndex >= heap->items->size)
120 break;
121 Real childValue = *((Real*)(_vector_get(heap->values, childIndex)));
122 if (
123 (heap->hType == MIN_T && childValue < topChildValue) ||
124 (heap->hType == MAX_T && childValue > topChildValue)
125 ) {
126 topChildIndex = childIndex;
127 topChildValue = childValue;
128 }
129 }
130 // Compare to top child
131 land = (
132 (heap->hType == MIN_T && startValue <= topChildValue) ||
133 (heap->hType == MAX_T && startValue >= topChildValue)
134 );
135 if (!land)
136 {
137 // Move one level down: the child goes one level up
138 if (currentIndex == startIndex)
139 {
140 // Save startItem (because *startItem is about to be changed)
141 void* newStartItem = safe_malloc(heap->items->dataSize);
142 memcpy(newStartItem, startItem, heap->items->dataSize);
143 startItem = newStartItem;
144 startItemReallocated = true;
145 }
146 void* topChildItem = _vector_get(heap->items, topChildIndex);
147 _vector_set(heap->items, currentIndex, topChildItem);
148 _vector_set(heap->values, currentIndex, &topChildValue);
149 currentIndex = topChildIndex;
150 continue;
151 }
152 // At correct relative place: will now land
153 if (currentIndex == startIndex)
154 applyExchange = false;
155 }
156 if (applyExchange)
157 {
158 // Moving element has landed (in a leaf): apply final affectation
159 _vector_set(heap->items, currentIndex, startItem);
160 _vector_set(heap->values, currentIndex, &startValue);
161 }
162 break;
163 }
164 if (startItemReallocated)
165 safe_free(startItem);
166 }
167
168 void _heap_insert(Heap* heap, void* item, Real value)
169 {
170 _vector_push(heap->items, item);
171 _vector_push(heap->values, &value);
172 _heap_bubble_up(heap, heap->items->size - 1);
173 }
174
175 Int _heap_get_index(Heap* heap, void* item)
176 {
177 for (Int index = 0; index < heap->items->size; index++)
178 {
179 if (
180 memcmp(
181 heap->items->datas + index * heap->items->dataSize,
182 item,
183 heap->items->dataSize
184 ) == 0
185 ) {
186 return index;
187 }
188 }
189 return -1;
190 }
191
192 void _heap_modify(Heap* heap, void* item, Real newValue)
193 {
194 // First, find index of the item:
195 const Int index = _heap_get_index(heap, item);
196 if (index < 0)
197 // Element not found
198 return;
199 Real oldValue = *((Real*)_vector_get(heap->values, index));
200 _vector_set(heap->values, index, &newValue);
201 if (
202 (heap->hType == MIN_T && newValue > oldValue) ||
203 (heap->hType == MAX_T && newValue < oldValue)
204 ) {
205 _heap_bubble_down(heap, index);
206 }
207 else
208 _heap_bubble_up(heap, index);
209 }
210
211 void _heap_remove_at_index(Heap* heap, Int index)
212 {
213 const bool removeLast = (index == heap->items->size - 1);
214 if (!removeLast)
215 {
216 _vector_set(
217 heap->items,
218 index,
219 _vector_get(heap->items, heap->items->size - 1));
220 _vector_set(
221 heap->values,
222 index,
223 _vector_get(heap->values, heap->values->size - 1));
224 }
225 vector_pop(heap->items);
226 vector_pop(heap->values);
227 if (!removeLast && heap->items->size > 0)
228 _heap_bubble_down(heap, index);
229 }
230
231 void _heap_remove(Heap* heap, void* item)
232 {
233 // First, find index of the item:
234 const Int index = _heap_get_index(heap, item);
235 if (index >= 0)
236 _heap_remove_at_index(heap, index);
237 }
238
239 ItemValue _heap_top(Heap* heap)
240 {
241 ItemValue top;
242 top.item = _vector_get(heap->items, 0);
243 vector_get(heap->values, 0, top.value);
244 return top;
245 }
246
247 void heap_pop(Heap* heap)
248 {
249 _heap_remove_at_index(heap, 0);
250 }
251
252 void heap_clear(Heap* heap)
253 {
254 vector_clear(heap->items);
255 vector_clear(heap->values);
256 }
257
258 void heap_destroy(Heap* heap)
259 {
260 vector_destroy(heap->items);
261 vector_destroy(heap->values);
262 safe_free(heap);
263 }