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->dataSize = dataSize;
  15     heap->array = _vector_new(sizeof(ItemValue));
  16     return heap;
  17 }
  18
  19 Heap* heap_copy(Heap* heap)
  20 {
  21     Heap* heapCopy = _heap_new(heap->dataSize, heap->hType, heap->arity);
  22     // HACK: vector_copy is not enough, since we also have to allocate ItemValue(->item)
  23     heapCopy->array->size = heap->array->size;
  24     heapCopy->array->capacity = heap->array->capacity;
  25     heapCopy->array->datas = (void**)safe_malloc(heap->array->capacity*sizeof(void*));
  26     for (UInt i=0; i<heap->array->size; i++)
  27     {
  28         heapCopy->array->datas[i] = safe_malloc(sizeof(ItemValue));
  29         ItemValue itemValueCopy = (ItemValue){
  30             .item=safe_malloc(heap->dataSize),
  31             .value=((ItemValue*)(heap->array->datas[i]))->value};
  32         memcpy(itemValueCopy.item, ((ItemValue*)(heap->array->datas[i]))->item, heap->dataSize);
  33         memcpy(heapCopy->array->datas[i], &itemValueCopy, sizeof(ItemValue));
  34     }
  35     return heapCopy;
  36 }
  37
  38 Bool heap_empty(Heap* heap)
  39 {
  40     return vector_empty(heap->array);
  41 }
  42
  43 UInt heap_size(Heap* heap)
  44 {
  45     return vector_size(heap->array);
  46 }
  47
  48 // NOTE: [perf] in two following methods, full heap[k] exchanges are not needed;
  49 // we keep track of the moving element without assigning it at every step,
  50 // thus saving array accesses and affectations + 'aux' temp. memory.
  51 // --> this is not the most natural way of writing these functions.
  52
  53 void _heap_bubble_up(Heap* heap, UInt startIndex)
  54 {
  55     UInt currentIndex = startIndex;
  56     ItemValue* startItemValue = heap->array->datas[startIndex];
  57     while (C_TRUE)
  58     {
  59         // get parent
  60         UInt nextIndex = currentIndex / heap->arity;
  61         Real nextValue = ((ItemValue*)(heap->array->datas[nextIndex]))->value;
  62         // compare to parent (if applicable)
  63         if (currentIndex == 0 ||
  64             (heap->hType == MIN_T && startItemValue->value >= nextValue) ||
  65             (heap->hType == MAX_T && startItemValue->value <= nextValue))
  66         {
  67             // moving element has landed: apply final affectation
  68             heap->array->datas[currentIndex] = startItemValue;
  69             break;
  70         }
  71         // move one level up: the parent goes one level down
  72         heap->array->datas[currentIndex] = heap->array->datas[nextIndex];
  73         currentIndex = nextIndex;
  74     }
  75 }
  76
  77 void _heap_bubble_down(Heap* heap, UInt startIndex)
  78 {
  79     UInt currentIndex = startIndex;
  80     ItemValue* startItemValue = heap->array->datas[startIndex];
  81     while (C_TRUE)
  82     {
  83         if (currentIndex * heap->arity >= heap->array->size)
  84         {
  85             // moving element has landed (in a leaf): apply final affectation
  86             heap->array->datas[currentIndex] = startItemValue;
  87             break;
  88         }
  89         // find top child (min or max)
  90         UInt topChildIndex;
  91         Real topChildValue = (heap->hType == MIN_T ? INFINITY : -INFINITY);
  92         for (Int i=0; i<heap->arity; i++)
  93         {
  94             UInt childIndex = i + currentIndex * heap->arity;
  95             if (childIndex >= heap->array->size)
  96                 break;
  97             Real childValue = ((ItemValue*)(heap->array->datas[childIndex]))->value;
  98             if ((heap->hType == MIN_T && childValue < topChildValue) ||
  99                 (heap->hType == MAX_T && childValue > topChildValue))
 100             {
 101                 topChildIndex = childIndex;
 102                 topChildValue = childValue;
 103             }
 104         }
 105         // compare to top child
 106         if ((heap->hType == MIN_T && startItemValue->value > topChildValue) ||
 107             (heap->hType == MAX_T && startItemValue->value < topChildValue))
 108         {
 109             // move one level down: the child goes one level up
 110             heap->array->datas[currentIndex] = heap->array->datas[topChildIndex];
 111         }
 112         else
 113         {
 114             // moving element has landed: apply final affectation
 115             heap->array->datas[currentIndex] = startItemValue;
 116             break;
 117         }
 118         currentIndex = topChildIndex;
 119     }
 120 }
 121
 122 void _heap_insert(Heap* heap, void* item, Real value)
 123 {
 124     ItemValue itemValue = (ItemValue){.item=safe_malloc(heap->dataSize), .value=value};
 125     memcpy(itemValue.item, item, heap->dataSize);
 126     _vector_push(heap->array, &itemValue);
 127     _heap_bubble_up(heap, heap->array->size-1);
 128 }
 129
 130 void _heap_modify(Heap* heap, UInt index, Real newValue)
 131 {
 132     double oldValue = ((ItemValue*)(heap->array->datas[index]))->value;
 133     ((ItemValue*)(heap->array->datas[index]))->value = newValue;
 134     if ((heap->hType == MIN_T && newValue > oldValue) ||
 135         (heap->hType == MAX_T && newValue < oldValue))
 136     {
 137         _heap_bubble_down(heap, index);
 138     }
 139     else
 140         _heap_bubble_up(heap, index);
 141 }
 142
 143 void _heap_remove(Heap* heap, UInt index)
 144 {
 145     safe_free(((ItemValue*)(heap->array->datas[index]))->item);
 146     ItemValue* tmp = heap->array->datas[index];
 147     heap->array->datas[index] = heap->array->datas[heap_size(heap)-1];
 148     heap->array->datas[heap_size(heap)-1] = tmp;
 149     vector_pop(heap->array);
 150     if (heap->array->size > 0)
 151         _heap_bubble_down(heap, index);
 152 }
 153
 154 ItemValue* heap_top_raw(Heap* heap)
 155 {
 156     return (ItemValue*)(heap->array->datas[0]);
 157 }
 158
 159 void heap_pop(Heap* heap)
 160 {
 161     _heap_remove(heap, 0);
 162 }
 163
 164 void heap_clear(Heap* heap)
 165 {
 166     for (UInt i = 0; i < heap->array->size; i++)
 167     {
 168         // Extra memory releases which wouldn't be done in vector_clear()
 169         safe_free(((ItemValue*)(heap->array->datas[i]))->item);
 170         //safe_free((ItemValue*)heap->array->datas[i]);
 171     }
 172     vector_clear(heap->array);
 173 }
 174
 175 void heap_destroy(Heap* heap)
 176 {
 177     heap_clear(heap);
 178     safe_free(heap->array);
 179     safe_free(heap);
 180 }