Commit | Line | Data |
---|---|---|
a7868768 BA |
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, 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 | ||
38 | Bool heap_empty(Heap* heap) | |
39 | { | |
40 | return vector_empty(heap->array); | |
41 | } | |
42 | ||
43 | UInt 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 | ||
53 | void _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 | ||
77 | void _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 | ||
122 | void _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 | ||
130 | void _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 | ||
143 | void _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 | ||
154 | ItemValue* heap_top_raw(Heap* heap) | |
155 | { | |
156 | return (ItemValue*)(heap->array->datas[0]); | |
157 | } | |
158 | ||
159 | void heap_pop(Heap* heap) | |
160 | { | |
161 | _heap_remove(heap, 0); | |
162 | } | |
163 | ||
164 | void 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 | ||
175 | void heap_destroy(Heap* heap) | |
176 | { | |
177 | heap_clear(heap); | |
178 | safe_free(heap->array); | |
179 | safe_free(heap); | |
180 | } |