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 (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   UInt index, ///< Index of the 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  * WARNING: does not work if items are not basic type nor pointers.
 126  */
 127 #define heap_modify(heap, item_, newValue) \
 128 { \
 129   UInt index = 0; \
 130   typeof(item_) item__ = item_; \
 131   for (; index<heap->array->size; index++) \
 132   { \
 133     void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \
 134     if (*((typeof(&item__))pItem) == item__) break; \
 135   } \
 136   _heap_modify(heap, index, newValue); \
 137 }
 138
 139 /**
 140  * @brief Remove an item-value at a given index.
 141  */
 142 void _heap_remove(
 143   Heap* heap, ///< "this" pointer.
 144   UInt index  ///< Index of the item to remove.
 145 );
 146
 147 /**
 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.
 152  *
 153  * Usage: void heap_remove(Heap* heap, void item_)
 154  *
 155  * WARNING: does not work if items are not basic type nor pointers.
 156  */
 157 #define heap_remove(heap, item_) \
 158 { \
 159   UInt index = 0; \
 160   typeof(item_) item__ = item_; \
 161   for (; index<heap->array->size; index++) \
 162   { \
 163     void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \
 164     if (*((typeof(&item__))pItem) == item__) break; \
 165   } \
 166   _heap_remove(heap, index); \
 167 }
 168
 169 /**
 170  * @brief Return what is at the beginning of the heap.
 171  */
 172 ItemValue* heap_top_raw(
 173   Heap* heap ///< "this" pointer.
 174 );
 175
 176 /**
 177  * @brief Return what is at the beginning of the heap.
 178  * @param heap "this" pointer.
 179  * @param item_ Item to be assigned.
 180  *
 181  * Usage: void heap_top(Heap* heap, void item_)
 182  */
 183 #define heap_top(heap, item_) \
 184 { \
 185   void* pItem = heap_top_raw(heap)->item; \
 186   item_ = *((typeof(&item_))pItem); \
 187 }
 188
 189 /**
 190  * @brief Remove the top of the heap.
 191  */
 192 void heap_pop(
 193   Heap* heap ///< "this" pointer.
 194 );
 195
 196 /**
 197  * @brief Clear the entire heap.
 198  */
 199 void heap_clear(
 200   Heap* heap ///< "this" pointer.
 201 );
 202
 203 /**
 204  * @brief Destroy the heap: clear it, and free 'heap' pointer.
 205  */
 206 void heap_destroy(
 207   Heap* heap ///< "this" pointer.
 208 );
 209
 210 #endif