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