Commit | Line | Data |
---|---|---|
a7868768 BA |
1 | /** |
2 | * @file Heap.h | |
3 | */ | |
4 | ||
5 | #ifndef CGDS_HEAP_H | |
6 | #define CGDS_HEAP_H | |
7 | ||
8 | #include <stdlib.h> | |
9 | #include <string.h> | |
10 | #include <math.h> | |
11 | #include "cgds/types.h" | |
12 | #include "cgds/Vector.h" | |
13 | #include "cgds/safe_alloc.h" | |
14 | ||
15 | /** | |
16 | * @brief Generic d-ary heap. | |
17 | */ | |
18 | typedef struct Heap { | |
e45132ac BA |
19 | size_t dataSize; ///< Size of a heap item in bytes. |
20 | OrderType hType; ///< Type of heap: max first (MAX_T) or min first (MIN_T). | |
21 | UInt arity; ///< Arity of the underlying tree. | |
22 | Vector* array; ///< Vector of ItemValue* (internal representation). | |
a7868768 BA |
23 | } Heap; |
24 | ||
25 | /** | |
26 | * @brief Return an allocated and initialized heap. | |
27 | */ | |
28 | Heap* _heap_new( | |
e45132ac BA |
29 | size_t dataSize, ///< Size in bytes of a heap element. |
30 | OrderType hType, ///< Type of heap: max first (MAX_T) or min first (MIN_T). | |
31 | UInt arity ///< Arity of the underlying tree. | |
a7868768 BA |
32 | ); |
33 | ||
34 | /** | |
35 | * @brief Return an allocated and initialized heap. | |
36 | * @param type Type of a buffer item (int, char*, ...). | |
37 | * @param hType Type of heap: max first (MAX_T) or min first (MIN_T). | |
38 | * @param arity Arity of the underlying tree. | |
1ff641f9 | 39 | * |
a7868768 BA |
40 | * Usage: Heap* heap_new(<Type> type, OrderType hType, UInt arity) |
41 | */ | |
42 | #define heap_new(type, hType, arity) \ | |
e45132ac BA |
43 | { \ |
44 | _heap_new(sizeof(type), hType, arity); \ | |
45 | } | |
a7868768 BA |
46 | |
47 | /** | |
1ff641f9 | 48 | * @brief Copy constructor (shallow copy, ok for basic types). |
a7868768 BA |
49 | */ |
50 | Heap* heap_copy( | |
e45132ac | 51 | Heap* heap ///< "this" pointer. |
a7868768 BA |
52 | ); |
53 | ||
54 | /** | |
55 | * @brief Check if the heap is empty. | |
56 | */ | |
1ff641f9 | 57 | bool heap_empty( |
e45132ac | 58 | Heap* heap ///< "this" pointer. |
a7868768 BA |
59 | ); |
60 | ||
61 | /** | |
62 | * @brief Return the size of current heap. | |
63 | */ | |
64 | UInt heap_size( | |
e45132ac | 65 | Heap* heap ///< "this" pointer. |
a7868768 BA |
66 | ); |
67 | ||
68 | /** | |
1ff641f9 BA |
69 | * @brief "Bubble up" an item-value inserted somewhere in the tree |
70 | * in O(log(n)) operations. | |
a7868768 BA |
71 | */ |
72 | void _heap_bubble_up( | |
e45132ac BA |
73 | Heap* heap, ///< "this" pointer. |
74 | UInt startIndex ///< Index to bubble up. | |
a7868768 BA |
75 | ); |
76 | ||
77 | /** | |
1ff641f9 BA |
78 | * @brief "Bubble down" an item-value inserted somewhere in the tree |
79 | * in O(log(n)) operations. | |
a7868768 BA |
80 | */ |
81 | void _heap_bubble_down( | |
e45132ac BA |
82 | Heap* heap, ///< "this" pointer. |
83 | UInt startIndex ///< Index to bubble down. | |
a7868768 BA |
84 | ); |
85 | ||
86 | /** | |
87 | * @brief Insert a pair (item,value) inside the heap. | |
88 | */ | |
89 | void _heap_insert( | |
e45132ac BA |
90 | Heap* heap, ///< "this" pointer. |
91 | void* item, ///< Pointer to an item of type as defined in the constructor. | |
92 | Real value ///< Value associated with the item. | |
a7868768 BA |
93 | ); |
94 | ||
95 | /** | |
96 | * @brief Insert a pair (item,value) inside the heap. | |
97 | * @param heap "this" pointer. | |
98 | * @param item Item of type as defined in the constructor. | |
99 | * @param value Value associated with the item. | |
1ff641f9 | 100 | * |
a7868768 BA |
101 | * Usage: void heap_insert(Heap* heap, void item, Real value) |
102 | */ | |
103 | #define heap_insert(heap, item, value) \ | |
104 | { \ | |
e45132ac BA |
105 | typeof((item)) tmp = item; \ |
106 | _heap_insert(heap, &tmp, value); \ | |
a7868768 BA |
107 | } |
108 | ||
109 | /** | |
110 | * @brief Change the value of an item at a given index. | |
111 | */ | |
112 | void _heap_modify( | |
e45132ac BA |
113 | Heap* heap, ///< "this" pointer. |
114 | UInt index, ///< Index of the item to modify. | |
115 | Real newValue ///< New value for the item. | |
a7868768 BA |
116 | ); |
117 | ||
118 | /** | |
119 | * @brief Change the value of an item inside the heap. | |
120 | * @param heap "this" pointer. | |
121 | * @param item_ Item to modify. | |
122 | * @param newValue New value for the item. | |
123 | * @note If several similar items are present, only the first is affected. | |
1ff641f9 | 124 | * |
a7868768 | 125 | * Usage: void heap_modify(Heap* heap, void item_, Real newValue) |
e45132ac | 126 | * |
a7868768 BA |
127 | * WARNING: does not work if items are not basic type nor pointers. |
128 | */ | |
129 | #define heap_modify(heap, item_, newValue) \ | |
130 | { \ | |
e45132ac BA |
131 | UInt index = 0; \ |
132 | typeof((item_)) item__ = item_; \ | |
133 | for (; index<heap->array->size; index++) \ | |
134 | { \ | |
135 | void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \ | |
136 | if (*((typeof(&item__))pItem) == item__) break; \ | |
137 | } \ | |
138 | _heap_modify(heap, index, newValue); \ | |
a7868768 BA |
139 | } |
140 | ||
141 | /** | |
142 | * @brief Remove an item-value at a given index. | |
143 | */ | |
144 | void _heap_remove( | |
e45132ac BA |
145 | Heap* heap, ///< "this" pointer. |
146 | UInt index ///< Index of the item to remove. | |
a7868768 BA |
147 | ); |
148 | ||
149 | /** | |
150 | * @brief Remove an item-value inside the heap. | |
151 | * @param heap "this" pointer. | |
152 | * @param item_ Item to remove. | |
153 | * @note If several similar items are present, only the first is deleted. | |
1ff641f9 | 154 | * |
a7868768 | 155 | * Usage: void heap_remove(Heap* heap, void item_) |
e45132ac | 156 | * |
a7868768 BA |
157 | * WARNING: does not work if items are not basic type nor pointers. |
158 | */ | |
159 | #define heap_remove(heap, item_) \ | |
160 | { \ | |
e45132ac BA |
161 | UInt index = 0; \ |
162 | typeof((item_)) item__ = item_; \ | |
163 | for (; index<heap->array->size; index++) \ | |
164 | { \ | |
165 | void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \ | |
166 | if (*((typeof(&item__))pItem) == item__) break; \ | |
167 | } \ | |
168 | _heap_remove(heap, index); \ | |
a7868768 BA |
169 | } |
170 | ||
171 | /** | |
172 | * @brief Return what is at the beginning of the heap. | |
173 | */ | |
174 | ItemValue* heap_top_raw( | |
e45132ac | 175 | Heap* heap ///< "this" pointer. |
a7868768 BA |
176 | ); |
177 | ||
178 | /** | |
179 | * @brief Return what is at the beginning of the heap. | |
180 | * @param heap "this" pointer. | |
181 | * @param item_ Item to be assigned. | |
1ff641f9 | 182 | * |
a7868768 BA |
183 | * Usage: void heap_top(Heap* heap, void item_) |
184 | */ | |
185 | #define heap_top(heap, item_) \ | |
186 | { \ | |
e45132ac BA |
187 | void* pItem = heap_top_raw(heap)->item; \ |
188 | item_ = *((typeof(&item_))pItem); \ | |
a7868768 BA |
189 | } |
190 | ||
191 | /** | |
192 | * @brief Remove the top of the heap. | |
193 | */ | |
194 | void heap_pop( | |
e45132ac | 195 | Heap* heap ///< "this" pointer. |
a7868768 BA |
196 | ); |
197 | ||
198 | /** | |
199 | * @brief Clear the entire heap. | |
200 | */ | |
201 | void heap_clear( | |
e45132ac | 202 | Heap* heap ///< "this" pointer. |
a7868768 BA |
203 | ); |
204 | ||
205 | /** | |
206 | * @brief Destroy the heap: clear it, and free 'heap' pointer. | |
207 | */ | |
208 | void heap_destroy( | |
e45132ac | 209 | Heap* heap ///< "this" pointer. |
a7868768 BA |
210 | ); |
211 | ||
212 | #endif |