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   OrderType hType; ///< Type of heap: max first (MAX_T) or min first (MIN_T).
  20   UInt arity; ///< Arity of the underlying tree.
  21   Vector* items; ///< Vector of items (any type).
  22   Vector* values; ///< Vector of items values (real numbers).
  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   void* item, ///< Pointer to 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 #define heap_modify(heap, item, newValue) \
 126 { \
 127   typeof(item) item_ = item; \
 128   _heap_modify(heap, &item_, newValue); \
 129 }
 130
 131 /**
 132  * @brief Remove an item-value at a given index.
 133  */
 134 void _heap_remove(
 135   Heap* heap, ///< "this" pointer.
 136   void* item ///< Pointer to item to remove.
 137 );
 138
 139 /**
 140  * @brief Remove an item-value inside the heap.
 141  * @param heap "this" pointer.
 142  * @param item Item to remove.
 143  * @note If several similar items are present, only the first is deleted.
 144  *
 145  * Usage: void heap_remove(Heap* heap, void item)
 146  */
 147 #define heap_remove(heap, item) \
 148 { \
 149   typeof(item) item_ = item; \
 150   _heap_remove(heap, &item_); \
 151 }
 152
 153 /**
 154  * @brief Return what is at the beginning of the heap.
 155  */
 156 ItemValue _heap_top(
 157   Heap* heap ///< "this" pointer.
 158 );
 159
 160 /**
 161  * @brief Get the top heap element in 'item'.
 162  * @param heap "this" pointer.
 163  * @param item_ Item to affect.
 164  *
 165  * Usage: void heap_top(Heap* heap, void item_)
 166  */
 167 #define heap_top(heap, item_) \
 168 { \
 169   ItemValue iv = _heap_top(heap); \
 170   item_ = *((typeof(item_)*) iv.item); \
 171 }
 172
 173 /**
 174  * @brief Remove the top of the heap.
 175  */
 176 void heap_pop(
 177   Heap* heap ///< "this" pointer.
 178 );
 179
 180 /**
 181  * @brief Clear the entire heap.
 182  */
 183 void heap_clear(
 184   Heap* heap ///< "this" pointer.
 185 );
 186
 187 /**
 188  * @brief Destroy the heap: clear it, and free 'heap' pointer.
 189  */
 190 void heap_destroy(
 191   Heap* heap ///< "this" pointer.
 192 );
 193
 194 #endif