11 #include "cgds/types.h"
12 #include "cgds/Vector.h"
13 #include "cgds/safe_alloc.h"
16 * @brief Generic d-ary 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).
26 * @brief Return an allocated and initialized heap.
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.
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.
40 * Usage: Heap* heap_new(<Type> type, OrderType hType, UInt arity)
42 #define heap_new(type, hType, arity) \
43 _heap_new(sizeof(type), hType, arity)
46 * @brief Copy constructor (shallow copy, ok for basic types).
49 Heap
* heap
///< "this" pointer.
53 * @brief Check if the heap is empty.
56 Heap
* heap
///< "this" pointer.
60 * @brief Return the size of current heap.
63 Heap
* heap
///< "this" pointer.
67 * @brief "Bubble up" an item-value inserted somewhere in the tree
68 * in O(log(n)) operations.
71 Heap
* heap
, ///< "this" pointer.
72 UInt startIndex
///< Index to bubble up.
76 * @brief "Bubble down" an item-value inserted somewhere in the tree
77 * in O(log(n)) operations.
79 void _heap_bubble_down(
80 Heap
* heap
, ///< "this" pointer.
81 UInt startIndex
///< Index to bubble down.
85 * @brief Insert a pair (item,value) inside the heap.
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.
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.
99 * Usage: void heap_insert(Heap* heap, void item, Real value)
101 #define heap_insert(heap, item, value) \
103 typeof(item) tmp = item; \
104 _heap_insert(heap, &tmp, value); \
108 * @brief Change the value of an item at a given index.
111 Heap
* heap
, ///< "this" pointer.
112 UInt index
, ///< Index of the item to modify.
113 Real newValue
///< New value for the item.
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.
123 * Usage: void heap_modify(Heap* heap, void item_, Real newValue)
125 * WARNING: does not work if items are not basic type nor pointers.
127 #define heap_modify(heap, item_, newValue) \
130 typeof(item_) item__ = item_; \
131 for (; index<heap->array->size; index++) \
133 void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \
134 if (*((typeof(&item__))pItem) == item__) break; \
136 _heap_modify(heap, index, newValue); \
140 * @brief Remove an item-value at a given index.
143 Heap
* heap
, ///< "this" pointer.
144 UInt index
///< Index of the item to remove.
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.
153 * Usage: void heap_remove(Heap* heap, void item_)
155 * WARNING: does not work if items are not basic type nor pointers.
157 #define heap_remove(heap, item_) \
160 typeof(item_) item__ = item_; \
161 for (; index<heap->array->size; index++) \
163 void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \
164 if (*((typeof(&item__))pItem) == item__) break; \
166 _heap_remove(heap, index); \
170 * @brief Return what is at the beginning of the heap.
172 ItemValue
* heap_top_raw(
173 Heap
* heap
///< "this" pointer.
177 * @brief Return what is at the beginning of the heap.
178 * @param heap "this" pointer.
179 * @param item_ Item to be assigned.
181 * Usage: void heap_top(Heap* heap, void item_)
183 #define heap_top(heap, item_) \
185 void* pItem = heap_top_raw(heap)->item; \
186 item_ = *((typeof(&item_))pItem); \
190 * @brief Remove the top of the heap.
193 Heap
* heap
///< "this" pointer.
197 * @brief Clear the entire heap.
200 Heap
* heap
///< "this" pointer.
204 * @brief Destroy the heap: clear it, and free 'heap' pointer.
207 Heap
* heap
///< "this" pointer.