src/Heap.c

   1 /**
   2  * @file Heap.c
   3  */
   4
   5 #include "cgds/Heap.h"
   6
   7 // NOTE: no init() method here, since Heap has no specific initialization
   8
   9 Heap* _heap_new(size_t dataSize, OrderType hType, UInt arity)
  10 {
  11   Heap* heap = (Heap*) safe_malloc(sizeof(Heap));
  12   heap->arity = arity;
  13   heap->hType = hType;
  14   heap->items = _vector_new(dataSize);
  15   heap->values = _vector_new(sizeof(Real));
  16   return heap;
  17 }
  18
  19 Heap* heap_copy(Heap* heap)
  20 {
  21   Heap* heapCopy = (Heap*) safe_malloc(sizeof(Heap));
  22   heapCopy->arity = heap->arity;
  23   heapCopy->hType = heap->hType;
  24   heapCopy->items = vector_copy(heap->items);
  25   heapCopy->values = vector_copy(heap->values);
  26   return heapCopy;
  27 }
  28
  29 bool heap_empty(Heap* heap)
  30 {
  31   return vector_empty(heap->items);
  32 }
  33
  34 UInt heap_size(Heap* heap)
  35 {
  36   return vector_size(heap->items);
  37 }
  38
  39 // NOTE: [perf] in two following methods, full heap[k] exchanges are
  40 // not needed; we keep track of the moving element without assigning it at
  41 // every step, thus saving array accesses and affectations + 'aux' tmp memory.
  42 // --> this is not the most natural way of writing these functions.
  43
  44 void _heap_bubble_up(Heap* heap, UInt startIndex)
  45 {
  46   if (startIndex == 0)
  47     // Nothing to do in this case
  48     return;
  49   UInt currentIndex = startIndex;
  50   void* startItem = _vector_get(heap->items, startIndex);
  51   Real startValue = *((Real*)(_vector_get(heap->values, startIndex)));
  52   bool startItemReallocated = false;
  53   while (true)
  54   {
  55     bool land = (currentIndex == 0), //at root: can't go up
  56          applyExchange = true;
  57     if (!land)
  58     {
  59       // Get parent and compare to it
  60       UInt nextIndex = (currentIndex - 1) / heap->arity;
  61       Real nextValue = *((Real*)(_vector_get(heap->values, nextIndex)));
  62       land = (
  63         (heap->hType == MIN_T && startValue >= nextValue) ||
  64         (heap->hType == MAX_T && startValue <= nextValue)
  65       );
  66       if (!land)
  67       {
  68         // Move one level up: the parent goes one level down
  69         if (currentIndex == startIndex)
  70         {
  71           // Save startItem (because *startItem is about to be changed)
  72           void* newStartItem = safe_malloc(heap->items->dataSize);
  73           memcpy(newStartItem, startItem, heap->items->dataSize);
  74           startItem = newStartItem;
  75           startItemReallocated = true;
  76         }
  77         void* nextItem = _vector_get(heap->items, nextIndex);
  78         _vector_set(heap->items, currentIndex, nextItem);
  79         _vector_set(heap->values, currentIndex, &nextValue);
  80         currentIndex = nextIndex;
  81         continue;
  82       }
  83       // At correct relative place: will now land
  84       if (currentIndex == startIndex)
  85         applyExchange = false;
  86     }
  87     if (applyExchange)
  88     {
  89       _vector_set(heap->items, currentIndex, startItem);
  90       _vector_set(heap->values, currentIndex, &startValue);
  91     }
  92     break;
  93   }
  94   if (startItemReallocated)
  95     safe_free(startItem);
  96 }
  97
  98 void _heap_bubble_down(Heap* heap, UInt startIndex)
  99 {
 100   if (startIndex * heap->arity + 1 >= heap->items->size)
 101     // Nothing to do: already in a leaf
 102     return;
 103   UInt currentIndex = startIndex;
 104   void* startItem = _vector_get(heap->items, startIndex);
 105   Real startValue = *((Real*)(_vector_get(heap->values, startIndex)));
 106   bool startItemReallocated = false;
 107   while (true)
 108   {
 109     bool land = (currentIndex * heap->arity + 1 >= heap->items->size),
 110          applyExchange = true;
 111     if (!land)
 112     {
 113       // Find top child (min or max)
 114       UInt topChildIndex;
 115       Real topChildValue = (heap->hType == MIN_T ? INFINITY : -INFINITY);
 116       for (UInt i = 1; i <= heap->arity; i++)
 117       {
 118         UInt childIndex = currentIndex * heap->arity + i;
 119         if (childIndex >= heap->items->size)
 120           break;
 121         Real childValue = *((Real*)(_vector_get(heap->values, childIndex)));
 122         if (
 123           (heap->hType == MIN_T && childValue < topChildValue) ||
 124           (heap->hType == MAX_T && childValue > topChildValue)
 125         ) {
 126           topChildIndex = childIndex;
 127           topChildValue = childValue;
 128         }
 129       }
 130       // Compare to top child
 131       land = (
 132         (heap->hType == MIN_T && startValue <= topChildValue) ||
 133         (heap->hType == MAX_T && startValue >= topChildValue)
 134       );
 135       if (!land)
 136       {
 137         // Move one level down: the child goes one level up
 138         if (currentIndex == startIndex)
 139         {
 140           // Save startItem (because *startItem is about to be changed)
 141           void* newStartItem = safe_malloc(heap->items->dataSize);
 142           memcpy(newStartItem, startItem, heap->items->dataSize);
 143           startItem = newStartItem;
 144           startItemReallocated = true;
 145         }
 146         void* topChildItem = _vector_get(heap->items, topChildIndex);
 147         _vector_set(heap->items, currentIndex, topChildItem);
 148         _vector_set(heap->values, currentIndex, &topChildValue);
 149         currentIndex = topChildIndex;
 150         continue;
 151       }
 152       // At correct relative place: will now land
 153       if (currentIndex == startIndex)
 154         applyExchange = false;
 155     }
 156     if (applyExchange)
 157     {
 158       // Moving element has landed (in a leaf): apply final affectation
 159       _vector_set(heap->items, currentIndex, startItem);
 160       _vector_set(heap->values, currentIndex, &startValue);
 161     }
 162     break;
 163   }
 164   if (startItemReallocated)
 165     safe_free(startItem);
 166 }
 167
 168 void _heap_insert(Heap* heap, void* item, Real value)
 169 {
 170   _vector_push(heap->items, item);
 171   _vector_push(heap->values, &value);
 172   _heap_bubble_up(heap, heap->items->size - 1);
 173 }
 174
 175 Int _heap_get_index(Heap* heap, void* item)
 176 {
 177   for (Int index = 0; index < heap->items->size; index++)
 178   {
 179     if (
 180       memcmp(
 181         heap->items->datas + index * heap->items->dataSize,
 182         item,
 183         heap->items->dataSize
 184       ) == 0
 185     ) {
 186       return index;
 187     }
 188   }
 189   return -1;
 190 }
 191
 192 void _heap_modify(Heap* heap, void* item, Real newValue)
 193 {
 194   // First, find index of the item:
 195   const Int index = _heap_get_index(heap, item);
 196   if (index < 0)
 197     // Element not found
 198     return;
 199   Real oldValue = *((Real*)_vector_get(heap->values, index));
 200   _vector_set(heap->values, index, &newValue);
 201   if (
 202     (heap->hType == MIN_T && newValue > oldValue) ||
 203     (heap->hType == MAX_T && newValue < oldValue)
 204   ) {
 205     _heap_bubble_down(heap, index);
 206   }
 207   else
 208     _heap_bubble_up(heap, index);
 209 }
 210
 211 void _heap_remove_at_index(Heap* heap, Int index)
 212 {
 213   const bool removeLast = (index == heap->items->size - 1);
 214   if (!removeLast)
 215   {
 216     _vector_set(
 217       heap->items,
 218       index,
 219       _vector_get(heap->items, heap->items->size - 1));
 220     _vector_set(
 221       heap->values,
 222       index,
 223       _vector_get(heap->values, heap->values->size - 1));
 224   }
 225   vector_pop(heap->items);
 226   vector_pop(heap->values);
 227   if (!removeLast && heap->items->size > 0)
 228     _heap_bubble_down(heap, index);
 229 }
 230
 231 void _heap_remove(Heap* heap, void* item)
 232 {
 233   // First, find index of the item:
 234   const Int index = _heap_get_index(heap, item);
 235   if (index >= 0)
 236     _heap_remove_at_index(heap, index);
 237 }
 238
 239 ItemValue _heap_top(Heap* heap)
 240 {
 241   ItemValue top;
 242   top.item = _vector_get(heap->items, 0);
 243   vector_get(heap->values, 0, top.value);
 244   return top;
 245 }
 246
 247 void heap_pop(Heap* heap)
 248 {
 249   _heap_remove_at_index(heap, 0);
 250 }
 251
 252 void heap_clear(Heap* heap)
 253 {
 254   vector_clear(heap->items);
 255   vector_clear(heap->values);
 256 }
 257
 258 void heap_destroy(Heap* heap)
 259 {
 260   vector_destroy(heap->items);
 261   vector_destroy(heap->values);
 262   safe_free(heap);
 263 }