50abaa43c4dec1eb1af3d08be39c51b1ceb1f042
[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 OrderType hType; ///< Type of heap: max first (MAX_T) or min first (MIN_T).
20 UInt arity; ///< Arity of the underlying tree.
21 Vector* items; ///< Vector of items (any type).
22 Vector* values; ///< Vector of items values (real numbers).
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 (shallow copy, ok for basic types).
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
68 * in O(log(n)) operations.
69 */
70 void _heap_bubble_up(
71 Heap* heap, ///< "this" pointer.
72 UInt startIndex ///< Index to bubble up.
73 );
74
75 /**
76 * @brief "Bubble down" an item-value inserted somewhere in the tree
77 * in O(log(n)) operations.
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.
98 *
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 void* item, ///< Pointer to 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.
122 *
123 * Usage: void heap_modify(Heap* heap, void item, Real newValue)
124 */
125 #define heap_modify(heap, item, newValue) \
126 { \
127 typeof(item) item_ = item; \
128 _heap_modify(heap, &item_, newValue); \
129 }
130
131 /**
132 * @brief Remove an item-value at a given index.
133 */
134 void _heap_remove(
135 Heap* heap, ///< "this" pointer.
136 void* item ///< Pointer to item to remove.
137 );
138
139 /**
140 * @brief Remove an item-value inside the heap.
141 * @param heap "this" pointer.
142 * @param item Item to remove.
143 * @note If several similar items are present, only the first is deleted.
144 *
145 * Usage: void heap_remove(Heap* heap, void item)
146 */
147 #define heap_remove(heap, item) \
148 { \
149 typeof(item) item_ = item; \
150 _heap_remove(heap, &item_); \
151 }
152
153 /**
154 * @brief Return what is at the beginning of the heap.
155 */
156 ItemValue _heap_top(
157 Heap* heap ///< "this" pointer.
158 );
159
160 /**
161 * @brief Get the top heap element in 'item'.
162 * @param heap "this" pointer.
163 * @param item_ Item to affect.
164 *
165 * Usage: void heap_top(Heap* heap, void item_)
166 */
167 #define heap_top(heap, item_) \
168 { \
169 ItemValue iv = _heap_top(heap); \
170 item_ = *((typeof(item_)*) iv.item); \
171 }
172
173 /**
174 * @brief Remove the top of the heap.
175 */
176 void heap_pop(
177 Heap* heap ///< "this" pointer.
178 );
179
180 /**
181 * @brief Clear the entire heap.
182 */
183 void heap_clear(
184 Heap* heap ///< "this" pointer.
185 );
186
187 /**
188 * @brief Destroy the heap: clear it, and free 'heap' pointer.
189 */
190 void heap_destroy(
191 Heap* heap ///< "this" pointer.
192 );
193
194 #endif