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