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 { | |
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). | |
23 | } Heap; | |
24 | ||
25 | /** | |
26 | * @brief Return an allocated and initialized heap. | |
27 | */ | |
28 | Heap* _heap_new( | |
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. | |
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) \ | |
43 | _heap_new(sizeof(type), hType, arity) | |
44 | ||
45 | /** | |
1ff641f9 | 46 | * @brief Copy constructor (shallow copy, ok for basic types). |
a7868768 BA |
47 | */ |
48 | Heap* heap_copy( | |
49 | Heap* heap ///< "this" pointer. | |
50 | ); | |
51 | ||
52 | /** | |
53 | * @brief Check if the heap is empty. | |
54 | */ | |
1ff641f9 | 55 | bool heap_empty( |
a7868768 BA |
56 | Heap* heap ///< "this" pointer. |
57 | ); | |
58 | ||
59 | /** | |
60 | * @brief Return the size of current heap. | |
61 | */ | |
62 | UInt heap_size( | |
63 | Heap* heap ///< "this" pointer. | |
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( | |
71 | Heap* heap, ///< "this" pointer. | |
72 | UInt startIndex ///< Index to bubble up. | |
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( | |
80 | Heap* heap, ///< "this" pointer. | |
81 | UInt startIndex ///< Index to bubble down. | |
82 | ); | |
83 | ||
84 | /** | |
85 | * @brief Insert a pair (item,value) inside the heap. | |
86 | */ | |
87 | void _heap_insert( | |
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. | |
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 | { \ | |
103 | typeof((item)) tmp = item; \ | |
104 | _heap_insert(heap, &tmp, value); \ | |
105 | } | |
106 | ||
107 | /** | |
108 | * @brief Change the value of an item at a given index. | |
109 | */ | |
110 | void _heap_modify( | |
111 | Heap* heap, ///< "this" pointer. | |
112 | UInt index, ///< Index of the item to modify. | |
113 | Real newValue ///< New value for the item. | |
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 BA |
123 | * Usage: void heap_modify(Heap* heap, void item_, Real newValue) |
124 | * WARNING: does not work if items are not basic type nor pointers. | |
125 | */ | |
126 | #define heap_modify(heap, item_, newValue) \ | |
127 | { \ | |
128 | UInt index = 0; \ | |
129 | typeof((item_)) item__ = item_; \ | |
130 | for (; index<heap->array->size; index++) \ | |
131 | { \ | |
132 | void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \ | |
133 | if (*((typeof(&item__))pItem) == item__) break; \ | |
134 | } \ | |
135 | _heap_modify(heap, index, newValue); \ | |
136 | } | |
137 | ||
138 | /** | |
139 | * @brief Remove an item-value at a given index. | |
140 | */ | |
141 | void _heap_remove( | |
142 | Heap* heap, ///< "this" pointer. | |
143 | UInt index ///< Index of the item to remove. | |
144 | ); | |
145 | ||
146 | /** | |
147 | * @brief Remove an item-value inside the heap. | |
148 | * @param heap "this" pointer. | |
149 | * @param item_ Item to remove. | |
150 | * @note If several similar items are present, only the first is deleted. | |
1ff641f9 | 151 | * |
a7868768 BA |
152 | * Usage: void heap_remove(Heap* heap, void item_) |
153 | * WARNING: does not work if items are not basic type nor pointers. | |
154 | */ | |
155 | #define heap_remove(heap, item_) \ | |
156 | { \ | |
157 | UInt index = 0; \ | |
158 | typeof((item_)) item__ = item_; \ | |
159 | for (; index<heap->array->size; index++) \ | |
160 | { \ | |
161 | void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \ | |
162 | if (*((typeof(&item__))pItem) == item__) break; \ | |
163 | } \ | |
164 | _heap_remove(heap, index); \ | |
165 | } | |
166 | ||
167 | /** | |
168 | * @brief Return what is at the beginning of the heap. | |
169 | */ | |
170 | ItemValue* heap_top_raw( | |
171 | Heap* heap ///< "this" pointer. | |
172 | ); | |
173 | ||
174 | /** | |
175 | * @brief Return what is at the beginning of the heap. | |
176 | * @param heap "this" pointer. | |
177 | * @param item_ Item to be assigned. | |
1ff641f9 | 178 | * |
a7868768 BA |
179 | * Usage: void heap_top(Heap* heap, void item_) |
180 | */ | |
181 | #define heap_top(heap, item_) \ | |
182 | { \ | |
183 | void* pItem = heap_top_raw(heap)->item; \ | |
184 | item_ = *((typeof(&item_))pItem); \ | |
185 | } | |
186 | ||
187 | /** | |
188 | * @brief Remove the top of the heap. | |
189 | */ | |
190 | void heap_pop( | |
191 | Heap* heap ///< "this" pointer. | |
192 | ); | |
193 | ||
194 | /** | |
195 | * @brief Clear the entire heap. | |
196 | */ | |
197 | void heap_clear( | |
198 | Heap* heap ///< "this" pointer. | |
199 | ); | |
200 | ||
201 | /** | |
202 | * @brief Destroy the heap: clear it, and free 'heap' pointer. | |
203 | */ | |
204 | void heap_destroy( | |
205 | Heap* heap ///< "this" pointer. | |
206 | ); | |
207 | ||
208 | #endif |