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 { \
  44   _heap_new(sizeof(type), hType, arity); \
  45 }
  46
  47 /**
  48  * @brief Copy constructor (shallow copy, ok for basic types).
  49  */
  50 Heap* heap_copy(
  51   Heap* heap ///< "this" pointer.
  52 );
  53
  54 /**
  55  * @brief Check if the heap is empty.
  56  */
  57 bool heap_empty(
  58   Heap* heap ///< "this" pointer.
  59 );
  60
  61 /**
  62  * @brief Return the size of current heap.
  63  */
  64 UInt heap_size(
  65   Heap* heap ///< "this" pointer.
  66 );
  67
  68 /**
  69  * @brief "Bubble up" an item-value inserted somewhere in the tree
  70  * in O(log(n)) operations.
  71  */
  72 void _heap_bubble_up(
  73   Heap* heap, ///< "this" pointer.
  74   UInt startIndex ///< Index to bubble up.
  75 );
  76
  77 /**
  78  * @brief "Bubble down" an item-value inserted somewhere in the tree
  79  * in O(log(n)) operations.
  80  */
  81 void _heap_bubble_down(
  82   Heap* heap, ///< "this" pointer.
  83   UInt startIndex ///< Index to bubble down.
  84 );
  85
  86 /**
  87  * @brief Insert a pair (item,value) inside the heap.
  88  */
  89 void _heap_insert(
  90   Heap* heap, ///< "this" pointer.
  91   void* item, ///< Pointer to an item of type as defined in the constructor.
  92   Real value ///< Value associated with the item.
  93 );
  94
  95 /**
  96  * @brief Insert a pair (item,value) inside the heap.
  97  * @param heap "this" pointer.
  98  * @param item Item of type as defined in the constructor.
  99  * @param value Value associated with the item.
 100  *
 101  * Usage: void heap_insert(Heap* heap, void item, Real value)
 102  */
 103 #define heap_insert(heap, item, value) \
 104 { \
 105   typeof((item)) tmp = item; \
 106   _heap_insert(heap, &tmp, value); \
 107 }
 108
 109 /**
 110  * @brief Change the value of an item at a given index.
 111  */
 112 void _heap_modify(
 113   Heap* heap, ///< "this" pointer.
 114   UInt index, ///< Index of the item to modify.
 115   Real newValue ///< New value for the item.
 116 );
 117
 118 /**
 119  * @brief Change the value of an item inside the heap.
 120  * @param heap "this" pointer.
 121  * @param item_ Item to modify.
 122  * @param newValue New value for the item.
 123  * @note If several similar items are present, only the first is affected.
 124  *
 125  * Usage: void heap_modify(Heap* heap, void item_, Real newValue)
 126  *
 127  * WARNING: does not work if items are not basic type nor pointers.
 128  */
 129 #define heap_modify(heap, item_, newValue) \
 130 { \
 131   UInt index = 0; \
 132   typeof((item_)) item__ = item_; \
 133   for (; index<heap->array->size; index++) \
 134   { \
 135     void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \
 136     if (*((typeof(&item__))pItem) == item__) break; \
 137   } \
 138   _heap_modify(heap, index, newValue); \
 139 }
 140
 141 /**
 142  * @brief Remove an item-value at a given index.
 143  */
 144 void _heap_remove(
 145   Heap* heap, ///< "this" pointer.
 146   UInt index  ///< Index of the item to remove.
 147 );
 148
 149 /**
 150  * @brief Remove an item-value inside the heap.
 151  * @param heap "this" pointer.
 152  * @param item_ Item to remove.
 153  * @note If several similar items are present, only the first is deleted.
 154  *
 155  * Usage: void heap_remove(Heap* heap, void item_)
 156  *
 157  * WARNING: does not work if items are not basic type nor pointers.
 158  */
 159 #define heap_remove(heap, item_) \
 160 { \
 161   UInt index = 0; \
 162   typeof((item_)) item__ = item_; \
 163   for (; index<heap->array->size; index++) \
 164   { \
 165     void* pItem = ((ItemValue*)(heap->array->datas[index]))->item; \
 166     if (*((typeof(&item__))pItem) == item__) break; \
 167   } \
 168   _heap_remove(heap, index); \
 169 }
 170
 171 /**
 172  * @brief Return what is at the beginning of the heap.
 173  */
 174 ItemValue* heap_top_raw(
 175   Heap* heap ///< "this" pointer.
 176 );
 177
 178 /**
 179  * @brief Return what is at the beginning of the heap.
 180  * @param heap "this" pointer.
 181  * @param item_ Item to be assigned.
 182  *
 183  * Usage: void heap_top(Heap* heap, void item_)
 184  */
 185 #define heap_top(heap, item_) \
 186 { \
 187   void* pItem = heap_top_raw(heap)->item; \
 188   item_ = *((typeof(&item_))pItem); \
 189 }
 190
 191 /**
 192  * @brief Remove the top of the heap.
 193  */
 194 void heap_pop(
 195   Heap* heap ///< "this" pointer.
 196 );
 197
 198 /**
 199  * @brief Clear the entire heap.
 200  */
 201 void heap_clear(
 202   Heap* heap ///< "this" pointer.
 203 );
 204
 205 /**
 206  * @brief Destroy the heap: clear it, and free 'heap' pointer.
 207  */
 208 void heap_destroy(
 209   Heap* heap ///< "this" pointer.
 210 );
 211
 212 #endif