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) \ | |
eed1b5d2 | 43 | _heap_new(sizeof(type), hType, arity) |
a7868768 BA |
44 | |
45 | /** | |
1ff641f9 | 46 | * @brief Copy constructor (shallow copy, ok for basic types). |
a7868768 BA |
47 | */ |
48 | Heap* heap_copy( | |
e45132ac | 49 | Heap* heap ///< "this" pointer. |
a7868768 BA |
50 | ); |
51 | ||
52 | /** | |
53 | * @brief Check if the heap is empty. | |
54 | */ | |
1ff641f9 | 55 | bool heap_empty( |
e45132ac | 56 | Heap* heap ///< "this" pointer. |
a7868768 BA |
57 | ); |
58 | ||
59 | /** | |
60 | * @brief Return the size of current heap. | |
61 | */ | |
62 | UInt heap_size( | |
e45132ac | 63 | Heap* heap ///< "this" pointer. |
a7868768 BA |
64 | ); |
65 | ||
66 | /** | |
1ff641f9 BA |
67 | * @brief "Bubble up" an item-value inserted somewhere in the tree |
68 | * in O(log(n)) operations. | |
a7868768 BA |
69 | */ |
70 | void _heap_bubble_up( | |
e45132ac BA |
71 | Heap* heap, ///< "this" pointer. |
72 | UInt startIndex ///< Index to bubble up. | |
a7868768 BA |
73 | ); |
74 | ||
75 | /** | |
1ff641f9 BA |
76 | * @brief "Bubble down" an item-value inserted somewhere in the tree |
77 | * in O(log(n)) operations. | |
a7868768 BA |
78 | */ |
79 | void _heap_bubble_down( | |
e45132ac BA |
80 | Heap* heap, ///< "this" pointer. |
81 | UInt startIndex ///< Index to bubble down. | |
a7868768 BA |
82 | ); |
83 | ||
84 | /** | |
85 | * @brief Insert a pair (item,value) inside the heap. | |
86 | */ | |
87 | void _heap_insert( | |
e45132ac BA |
88 | Heap* heap, ///< "this" pointer. |
89 | void* item, ///< Pointer to an item of type as defined in the constructor. | |
90 | Real value ///< Value associated with the item. | |
a7868768 BA |
91 | ); |
92 | ||
93 | /** | |
94 | * @brief Insert a pair (item,value) inside the heap. | |
95 | * @param heap "this" pointer. | |
96 | * @param item Item of type as defined in the constructor. | |
97 | * @param value Value associated with the item. | |
1ff641f9 | 98 | * |
a7868768 BA |
99 | * Usage: void heap_insert(Heap* heap, void item, Real value) |
100 | */ | |
101 | #define heap_insert(heap, item, value) \ | |
102 | { \ | |
eed1b5d2 | 103 | typeof(item) tmp = item; \ |
e45132ac | 104 | _heap_insert(heap, &tmp, value); \ |
a7868768 BA |
105 | } |
106 | ||
107 | /** | |
108 | * @brief Change the value of an item at a given index. | |
109 | */ | |
110 | void _heap_modify( | |
e45132ac BA |
111 | Heap* heap, ///< "this" pointer. |
112 | UInt index, ///< Index of the item to modify. | |
113 | Real newValue ///< New value for the item. | |
a7868768 BA |
114 | ); |
115 | ||
116 | /** | |
117 | * @brief Change the value of an item inside the heap. | |
118 | * @param heap "this" pointer. | |
119 | * @param item_ Item to modify. | |
120 | * @param newValue New value for the item. | |
121 | * @note If several similar items are present, only the first is affected. | |
1ff641f9 | 122 | * |
a7868768 | 123 | * Usage: void heap_modify(Heap* heap, void item_, Real newValue) |
e45132ac | 124 | * |
a7868768 BA |
125 | * WARNING: does not work if items are not basic type nor pointers. |
126 | */ | |
127 | #define heap_modify(heap, item_, newValue) \ | |
128 | { \ | |
e45132ac | 129 | UInt index = 0; \ |
eed1b5d2 | 130 | typeof(item_) item__ = item_; \ |
e45132ac BA |
131 | for (; index<heap->array->size; index++) \ |
132 | { \ | |
133 | void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \ | |
134 | if (*((typeof(&item__))pItem) == item__) break; \ | |
135 | } \ | |
136 | _heap_modify(heap, index, newValue); \ | |
a7868768 BA |
137 | } |
138 | ||
139 | /** | |
140 | * @brief Remove an item-value at a given index. | |
141 | */ | |
142 | void _heap_remove( | |
e45132ac BA |
143 | Heap* heap, ///< "this" pointer. |
144 | UInt index ///< Index of the item to remove. | |
a7868768 BA |
145 | ); |
146 | ||
147 | /** | |
148 | * @brief Remove an item-value inside the heap. | |
149 | * @param heap "this" pointer. | |
150 | * @param item_ Item to remove. | |
151 | * @note If several similar items are present, only the first is deleted. | |
1ff641f9 | 152 | * |
a7868768 | 153 | * Usage: void heap_remove(Heap* heap, void item_) |
e45132ac | 154 | * |
a7868768 BA |
155 | * WARNING: does not work if items are not basic type nor pointers. |
156 | */ | |
157 | #define heap_remove(heap, item_) \ | |
158 | { \ | |
e45132ac | 159 | UInt index = 0; \ |
eed1b5d2 | 160 | typeof(item_) item__ = item_; \ |
e45132ac BA |
161 | for (; index<heap->array->size; index++) \ |
162 | { \ | |
163 | void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \ | |
164 | if (*((typeof(&item__))pItem) == item__) break; \ | |
165 | } \ | |
166 | _heap_remove(heap, index); \ | |
a7868768 BA |
167 | } |
168 | ||
169 | /** | |
170 | * @brief Return what is at the beginning of the heap. | |
171 | */ | |
172 | ItemValue* heap_top_raw( | |
e45132ac | 173 | Heap* heap ///< "this" pointer. |
a7868768 BA |
174 | ); |
175 | ||
176 | /** | |
177 | * @brief Return what is at the beginning of the heap. | |
178 | * @param heap "this" pointer. | |
179 | * @param item_ Item to be assigned. | |
1ff641f9 | 180 | * |
a7868768 BA |
181 | * Usage: void heap_top(Heap* heap, void item_) |
182 | */ | |
183 | #define heap_top(heap, item_) \ | |
184 | { \ | |
e45132ac BA |
185 | void* pItem = heap_top_raw(heap)->item; \ |
186 | item_ = *((typeof(&item_))pItem); \ | |
a7868768 BA |
187 | } |
188 | ||
189 | /** | |
190 | * @brief Remove the top of the heap. | |
191 | */ | |
192 | void heap_pop( | |
e45132ac | 193 | Heap* heap ///< "this" pointer. |
a7868768 BA |
194 | ); |
195 | ||
196 | /** | |
197 | * @brief Clear the entire heap. | |
198 | */ | |
199 | void heap_clear( | |
e45132ac | 200 | Heap* heap ///< "this" pointer. |
a7868768 BA |
201 | ); |
202 | ||
203 | /** | |
204 | * @brief Destroy the heap: clear it, and free 'heap' pointer. | |
205 | */ | |
206 | void heap_destroy( | |
e45132ac | 207 | Heap* heap ///< "this" pointer. |
a7868768 BA |
208 | ); |
209 | ||
210 | #endif |