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