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