fix problems in Queue.c / Stack.c ; still issues: to investigate
[cgds.git] / src / Heap.c
... / ...
CommitLineData
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
9Heap* _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->dataSize = dataSize;
15 heap->array = _vector_new(sizeof(ItemValue));
16 return heap;
17}
18
19Heap* heap_copy(Heap* heap)
20{
21 Heap* heapCopy = _heap_new(heap->dataSize, heap->hType, heap->arity);
22 // HACK: vector_copy is not enough, since we also have to allocate ItemValue(->item)
23 heapCopy->array->size = heap->array->size;
24 heapCopy->array->capacity = heap->array->capacity;
25 heapCopy->array->datas = (void**)safe_malloc(heap->array->capacity*sizeof(void*));
26 for (UInt i=0; i<heap->array->size; i++)
27 {
28 heapCopy->array->datas[i] = safe_malloc(sizeof(ItemValue));
29 ItemValue itemValueCopy = (ItemValue){
30 .item=safe_malloc(heap->dataSize),
31 .value=((ItemValue*)(heap->array->datas[i]))->value};
32 memcpy(itemValueCopy.item, ((ItemValue*)(heap->array->datas[i]))->item, heap->dataSize);
33 memcpy(heapCopy->array->datas[i], &itemValueCopy, sizeof(ItemValue));
34 }
35 return heapCopy;
36}
37
38Bool heap_empty(Heap* heap)
39{
40 return vector_empty(heap->array);
41}
42
43UInt heap_size(Heap* heap)
44{
45 return vector_size(heap->array);
46}
47
48// NOTE: [perf] in two following methods, full heap[k] exchanges are not needed;
49// we keep track of the moving element without assigning it at every step,
50// thus saving array accesses and affectations + 'aux' temp. memory.
51// --> this is not the most natural way of writing these functions.
52
53void _heap_bubble_up(Heap* heap, UInt startIndex)
54{
55 UInt currentIndex = startIndex;
56 ItemValue* startItemValue = heap->array->datas[startIndex];
57 while (C_TRUE)
58 {
59 // get parent
60 UInt nextIndex = currentIndex / heap->arity;
61 Real nextValue = ((ItemValue*)(heap->array->datas[nextIndex]))->value;
62 // compare to parent (if applicable)
63 if (currentIndex == 0 ||
64 (heap->hType == MIN_T && startItemValue->value >= nextValue) ||
65 (heap->hType == MAX_T && startItemValue->value <= nextValue))
66 {
67 // moving element has landed: apply final affectation
68 heap->array->datas[currentIndex] = startItemValue;
69 break;
70 }
71 // move one level up: the parent goes one level down
72 heap->array->datas[currentIndex] = heap->array->datas[nextIndex];
73 currentIndex = nextIndex;
74 }
75}
76
77void _heap_bubble_down(Heap* heap, UInt startIndex)
78{
79 UInt currentIndex = startIndex;
80 ItemValue* startItemValue = heap->array->datas[startIndex];
81 while (C_TRUE)
82 {
83 if (currentIndex * heap->arity >= heap->array->size)
84 {
85 // moving element has landed (in a leaf): apply final affectation
86 heap->array->datas[currentIndex] = startItemValue;
87 break;
88 }
89 // find top child (min or max)
90 UInt topChildIndex;
91 Real topChildValue = (heap->hType == MIN_T ? INFINITY : -INFINITY);
92 for (Int i=0; i<heap->arity; i++)
93 {
94 UInt childIndex = i + currentIndex * heap->arity;
95 if (childIndex >= heap->array->size)
96 break;
97 Real childValue = ((ItemValue*)(heap->array->datas[childIndex]))->value;
98 if ((heap->hType == MIN_T && childValue < topChildValue) ||
99 (heap->hType == MAX_T && childValue > topChildValue))
100 {
101 topChildIndex = childIndex;
102 topChildValue = childValue;
103 }
104 }
105 // compare to top child
106 if ((heap->hType == MIN_T && startItemValue->value > topChildValue) ||
107 (heap->hType == MAX_T && startItemValue->value < topChildValue))
108 {
109 // move one level down: the child goes one level up
110 heap->array->datas[currentIndex] = heap->array->datas[topChildIndex];
111 }
112 else
113 {
114 // moving element has landed: apply final affectation
115 heap->array->datas[currentIndex] = startItemValue;
116 break;
117 }
118 currentIndex = topChildIndex;
119 }
120}
121
122void _heap_insert(Heap* heap, void* item, Real value)
123{
124 ItemValue itemValue = (ItemValue){.item=safe_malloc(heap->dataSize), .value=value};
125 memcpy(itemValue.item, item, heap->dataSize);
126 _vector_push(heap->array, &itemValue);
127 _heap_bubble_up(heap, heap->array->size-1);
128}
129
130void _heap_modify(Heap* heap, UInt index, Real newValue)
131{
132 double oldValue = ((ItemValue*)(heap->array->datas[index]))->value;
133 ((ItemValue*)(heap->array->datas[index]))->value = newValue;
134 if ((heap->hType == MIN_T && newValue > oldValue) ||
135 (heap->hType == MAX_T && newValue < oldValue))
136 {
137 _heap_bubble_down(heap, index);
138 }
139 else
140 _heap_bubble_up(heap, index);
141}
142
143void _heap_remove(Heap* heap, UInt index)
144{
145 safe_free(((ItemValue*)(heap->array->datas[index]))->item);
146 ItemValue* tmp = heap->array->datas[index];
147 heap->array->datas[index] = heap->array->datas[heap_size(heap)-1];
148 heap->array->datas[heap_size(heap)-1] = tmp;
149 vector_pop(heap->array);
150 if (heap->array->size > 0)
151 _heap_bubble_down(heap, index);
152}
153
154ItemValue* heap_top_raw(Heap* heap)
155{
156 return (ItemValue*)(heap->array->datas[0]);
157}
158
159void heap_pop(Heap* heap)
160{
161 _heap_remove(heap, 0);
162}
163
164void heap_clear(Heap* heap)
165{
166 for (UInt i = 0; i < heap->array->size; i++)
167 {
168 // Extra memory releases which wouldn't be done in vector_clear()
169 safe_free(((ItemValue*)(heap->array->datas[i]))->item);
170 //safe_free((ItemValue*)heap->array->datas[i]);
171 }
172 vector_clear(heap->array);
173}
174
175void heap_destroy(Heap* heap)
176{
177 heap_clear(heap);
178 safe_free(heap->array);
179 safe_free(heap);
180}