* @brief Generic d-ary heap.
*/
typedef struct Heap {
- size_t dataSize; ///< Size of a heap item in bytes.
OrderType hType; ///< Type of heap: max first (MAX_T) or min first (MIN_T).
UInt arity; ///< Arity of the underlying tree.
- Vector* array; ///< Vector of ItemValue* (internal representation).
+ Vector* items; ///< Vector of items (any type).
+ Vector* values; ///< Vector of items values (real numbers).
} Heap;
/**
*/
void _heap_modify(
Heap* heap, ///< "this" pointer.
- UInt index, ///< Index of the item to modify.
+ void* item, ///< Pointer to item to modify.
Real newValue ///< New value for the item.
);
/**
* @brief Change the value of an item inside the heap.
* @param heap "this" pointer.
- * @param item_ Item to modify.
+ * @param item Item to modify.
* @param newValue New value for the item.
* @note If several similar items are present, only the first is affected.
*
- * Usage: void heap_modify(Heap* heap, void item_, Real newValue)
- *
- * WARNING: does not work if items are not basic type nor pointers.
+ * Usage: void heap_modify(Heap* heap, void item, Real newValue)
*/
-#define heap_modify(heap, item_, newValue) \
+#define heap_modify(heap, item, newValue) \
{ \
- UInt index = 0; \
- typeof(item_) item__ = item_; \
- for (; index<heap->array->size; index++) \
- { \
- void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \
- if (*((typeof(&item__))pItem) == item__) break; \
- } \
- _heap_modify(heap, index, newValue); \
+ typeof(item) item_ = item; \
+ _heap_modify(heap, &item_, newValue); \
}
/**
*/
void _heap_remove(
Heap* heap, ///< "this" pointer.
- UInt index ///< Index of the item to remove.
+ void* item ///< Pointer to item to remove.
);
/**
* @brief Remove an item-value inside the heap.
* @param heap "this" pointer.
- * @param item_ Item to remove.
+ * @param item Item to remove.
* @note If several similar items are present, only the first is deleted.
*
- * Usage: void heap_remove(Heap* heap, void item_)
- *
- * WARNING: does not work if items are not basic type nor pointers.
+ * Usage: void heap_remove(Heap* heap, void item)
*/
-#define heap_remove(heap, item_) \
+#define heap_remove(heap, item) \
{ \
- UInt index = 0; \
- typeof(item_) item__ = item_; \
- for (; index<heap->array->size; index++) \
- { \
- void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \
- if (*((typeof(&item__))pItem) == item__) break; \
- } \
- _heap_remove(heap, index); \
+ typeof(item) item_ = item; \
+ _heap_remove(heap, &item_); \
}
/**
* @brief Return what is at the beginning of the heap.
*/
-ItemValue* heap_top_raw(
+ItemValue _heap_top(
Heap* heap ///< "this" pointer.
);
/**
- * @brief Return what is at the beginning of the heap.
+ * @brief Get the top heap element in 'item'.
* @param heap "this" pointer.
- * @param item_ Item to be assigned.
+ * @param item_ Item to affect.
*
* Usage: void heap_top(Heap* heap, void item_)
*/
#define heap_top(heap, item_) \
{ \
- void* pItem = heap_top_raw(heap)->item; \
- item_ = *((typeof(&item_))pItem); \
+ ItemValue iv = _heap_top(heap); \
+ item_ = *((typeof(item_)*) iv.item); \
}
/**