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