X-Git-Url: https://git.auder.net/?p=cgds.git;a=blobdiff_plain;f=src%2FHeap.c;h=417a4d0b409511e85209bf032435f4a30726707e;hp=6bdbc0ee8818125b30ff2cdf898666f260ffe942;hb=1d60b10a9482afc28f4ac027b21edf930d48440c;hpb=588a2232cf24183218d88c85003f2e6093f942ed

diff --git a/src/Heap.c b/src/Heap.c
index 6bdbc0e..417a4d0 100644
--- a/src/Heap.c
+++ b/src/Heap.c
@@ -8,46 +8,32 @@
 
 Heap* _heap_new(size_t dataSize, OrderType hType, UInt arity)
 {
-  Heap* heap = (Heap*)safe_malloc(sizeof(Heap));
+  Heap* heap = (Heap*) safe_malloc(sizeof(Heap));
   heap->arity = arity;
   heap->hType = hType;
-  heap->dataSize = dataSize;
-  heap->array = _vector_new(sizeof(ItemValue));
+  heap->items = _vector_new(dataSize);
+  heap->values = _vector_new(sizeof(Real));
   return heap;
 }
 
 Heap* heap_copy(Heap* heap)
 {
-  Heap* heapCopy = _heap_new(heap->dataSize, heap->hType, heap->arity);
-  // HACK: vector_copy is not enough,
-  // since we also have to allocate ItemValue(->item)
-  heapCopy->array->size = heap->array->size;
-  heapCopy->array->capacity = heap->array->capacity;
-  heapCopy->array->datas =
-    (void**)safe_malloc(heap->array->capacity*sizeof(void*));
-  for (UInt i = 0; i < heap->array->size; i++)
-  {
-    heapCopy->array->datas[i] = safe_malloc(sizeof(ItemValue));
-    ItemValue itemValueCopy = (ItemValue){
-      .item=safe_malloc(heap->dataSize),
-      .value=((ItemValue*)(heap->array->datas[i]))->value};
-    memcpy(
-      itemValueCopy.item,
-      ((ItemValue*)(heap->array->datas[i]))->item,
-      heap->dataSize);
-    memcpy(heapCopy->array->datas[i], &itemValueCopy, sizeof(ItemValue));
-  }
+  Heap* heapCopy = (Heap*) safe_malloc(sizeof(Heap));
+  heapCopy->arity = heap->arity;
+  heapCopy->hType = heap->hType;
+  heapCopy->items = vector_copy(heap->items);
+  heapCopy->values = vector_copy(heap->values);
   return heapCopy;
 }
 
 bool heap_empty(Heap* heap)
 {
-  return vector_empty(heap->array);
+  return vector_empty(heap->items);
 }
 
 UInt heap_size(Heap* heap)
 {
-  return vector_size(heap->array);
+  return vector_size(heap->items);
 }
 
 // NOTE: [perf] in two following methods, full heap[k] exchanges are
@@ -57,127 +43,221 @@ UInt heap_size(Heap* heap)
 
 void _heap_bubble_up(Heap* heap, UInt startIndex)
 {
+  if (startIndex == 0)
+    // Nothing to do in this case
+    return;
   UInt currentIndex = startIndex;
-  ItemValue* startItemValue = heap->array->datas[startIndex];
+  void* startItem = _vector_get(heap->items, startIndex);
+  Real startValue = *((Real*)(_vector_get(heap->values, startIndex)));
+  bool startItemReallocated = false;
   while (true)
   {
-    // get parent
-    UInt nextIndex = currentIndex / heap->arity;
-    Real nextValue = ((ItemValue*)(heap->array->datas[nextIndex]))->value;
-    // compare to parent (if applicable)
-    if (currentIndex == 0 ||
-      (heap->hType == MIN_T && startItemValue->value >= nextValue) ||
-      (heap->hType == MAX_T && startItemValue->value <= nextValue))
+    bool land = (currentIndex == 0), //at root: can't go up
+         applyExchange = true;
+    if (!land)
+    {
+      // Get parent and compare to it
+      UInt nextIndex = (currentIndex - 1) / heap->arity;
+      Real nextValue = *((Real*)(_vector_get(heap->values, nextIndex)));
+      land = (
+        (heap->hType == MIN_T && startValue >= nextValue) ||
+        (heap->hType == MAX_T && startValue <= nextValue)
+      );
+      if (!land)
+      {
+        // Move one level up: the parent goes one level down
+        if (currentIndex == startIndex)
+        {
+          // Save startItem (because *startItem is about to be changed)
+          void* newStartItem = safe_malloc(heap->items->dataSize);
+          memcpy(newStartItem, startItem, heap->items->dataSize);
+          startItem = newStartItem;
+          startItemReallocated = true;
+        }
+        void* nextItem = _vector_get(heap->items, nextIndex);
+        _vector_set(heap->items, currentIndex, nextItem);
+        _vector_set(heap->values, currentIndex, &nextValue);
+        currentIndex = nextIndex;
+        continue;
+      }
+      // At correct relative place: will now land
+      if (currentIndex == startIndex)
+        applyExchange = false;
+    }
+    if (applyExchange)
     {
-      // moving element has landed: apply final affectation
-      heap->array->datas[currentIndex] = startItemValue;
-      break;
+      _vector_set(heap->items, currentIndex, startItem);
+      _vector_set(heap->values, currentIndex, &startValue);
     }
-    // move one level up: the parent goes one level down
-    heap->array->datas[currentIndex] = heap->array->datas[nextIndex];
-    currentIndex = nextIndex;
+    break;
   }
+  if (startItemReallocated)
+    safe_free(startItem);
 }
 
 void _heap_bubble_down(Heap* heap, UInt startIndex)
 {
+  if (startIndex * heap->arity + 1 >= heap->items->size)
+    // Nothing to do: already in a leaf
+    return;
   UInt currentIndex = startIndex;
-  ItemValue* startItemValue = heap->array->datas[startIndex];
+  void* startItem = _vector_get(heap->items, startIndex);
+  Real startValue = *((Real*)(_vector_get(heap->values, startIndex)));
+  bool startItemReallocated = false;
   while (true)
   {
-    if (currentIndex * heap->arity >= heap->array->size)
+    bool land = (currentIndex * heap->arity + 1 >= heap->items->size),
+         applyExchange = true;
+    if (!land)
     {
-      // moving element has landed (in a leaf): apply final affectation
-      heap->array->datas[currentIndex] = startItemValue;
-      break;
-    }
-    // find top child (min or max)
-    UInt topChildIndex;
-    Real topChildValue = (heap->hType == MIN_T ? INFINITY : -INFINITY);
-    for (UInt i = 0; i < heap->arity; i++)
-    {
-      UInt childIndex = i + currentIndex * heap->arity;
-      if (childIndex >= heap->array->size)
-        break;
-      Real childValue = ((ItemValue*)(heap->array->datas[childIndex]))->value;
-      if ((heap->hType == MIN_T && childValue < topChildValue) ||
-        (heap->hType == MAX_T && childValue > topChildValue))
+      // Find top child (min or max)
+      UInt topChildIndex;
+      Real topChildValue = (heap->hType == MIN_T ? INFINITY : -INFINITY);
+      for (UInt i = 1; i <= heap->arity; i++)
       {
-        topChildIndex = childIndex;
-        topChildValue = childValue;
+        UInt childIndex = currentIndex * heap->arity + i;
+        if (childIndex >= heap->items->size)
+          break;
+        Real childValue = *((Real*)(_vector_get(heap->values, childIndex)));
+        if (
+          (heap->hType == MIN_T && childValue < topChildValue) ||
+          (heap->hType == MAX_T && childValue > topChildValue)
+        ) {
+          topChildIndex = childIndex;
+          topChildValue = childValue;
+        }
       }
+      // Compare to top child
+      land = (
+        (heap->hType == MIN_T && startValue <= topChildValue) ||
+        (heap->hType == MAX_T && startValue >= topChildValue)
+      );
+      if (!land)
+      {
+        // Move one level down: the child goes one level up
+        if (currentIndex == startIndex)
+        {
+          // Save startItem (because *startItem is about to be changed)
+          void* newStartItem = safe_malloc(heap->items->dataSize);
+          memcpy(newStartItem, startItem, heap->items->dataSize);
+          startItem = newStartItem;
+          startItemReallocated = true;
+        }
+        void* topChildItem = _vector_get(heap->items, topChildIndex);
+        _vector_set(heap->items, currentIndex, topChildItem);
+        _vector_set(heap->values, currentIndex, &topChildValue);
+        currentIndex = topChildIndex;
+        continue;
+      }
+      // At correct relative place: will now land
+      if (currentIndex == startIndex)
+        applyExchange = false;
     }
-    // compare to top child
-    if ((heap->hType == MIN_T && startItemValue->value > topChildValue) ||
-      (heap->hType == MAX_T && startItemValue->value < topChildValue))
-    {
-      // move one level down: the child goes one level up
-      heap->array->datas[currentIndex] = heap->array->datas[topChildIndex];
-    }
-    else
+    if (applyExchange)
     {
-      // moving element has landed: apply final affectation
-      heap->array->datas[currentIndex] = startItemValue;
-      break;
+      // Moving element has landed (in a leaf): apply final affectation
+      _vector_set(heap->items, currentIndex, startItem);
+      _vector_set(heap->values, currentIndex, &startValue);
     }
-    currentIndex = topChildIndex;
+    break;
   }
+  if (startItemReallocated)
+    safe_free(startItem);
 }
 
 void _heap_insert(Heap* heap, void* item, Real value)
 {
-  ItemValue itemValue =
-    (ItemValue){.item=safe_malloc(heap->dataSize), .value=value};
-  memcpy(itemValue.item, item, heap->dataSize);
-  _vector_push(heap->array, &itemValue);
-  _heap_bubble_up(heap, heap->array->size-1);
+  _vector_push(heap->items, item);
+  _vector_push(heap->values, &value);
+  _heap_bubble_up(heap, heap->items->size - 1);
 }
 
-void _heap_modify(Heap* heap, UInt index, Real newValue)
+Int _heap_get_index(Heap* heap, void* item)
 {
-  double oldValue = ((ItemValue*)(heap->array->datas[index]))->value;
-  ((ItemValue*)(heap->array->datas[index]))->value = newValue;
-  if ((heap->hType == MIN_T && newValue > oldValue) ||
-    (heap->hType == MAX_T && newValue < oldValue))
+  for (Int index = 0; index < heap->items->size; index++)
   {
+    if (
+      memcmp(
+        heap->items->datas + index * heap->items->dataSize,
+        item,
+        heap->items->dataSize
+      ) == 0
+    ) {
+      return index;
+    }
+  }
+  return -1;
+}
+
+void _heap_modify(Heap* heap, void* item, Real newValue)
+{
+  // First, find index of the item:
+  const Int index = _heap_get_index(heap, item);
+  if (index < 0)
+    // Element not found
+    return;
+  Real oldValue = *((Real*)_vector_get(heap->values, index));
+  _vector_set(heap->values, index, &newValue);
+  if (
+    (heap->hType == MIN_T && newValue > oldValue) ||
+    (heap->hType == MAX_T && newValue < oldValue)
+  ) {
     _heap_bubble_down(heap, index);
   }
   else
     _heap_bubble_up(heap, index);
 }
 
-void _heap_remove(Heap* heap, UInt index)
+void _heap_remove_at_index(Heap* heap, Int index)
 {
-  safe_free(((ItemValue*)(heap->array->datas[index]))->item);
-  ItemValue* tmp = heap->array->datas[index];
-  heap->array->datas[index] = heap->array->datas[heap_size(heap)-1];
-  heap->array->datas[heap_size(heap)-1] = tmp;
-  vector_pop(heap->array);
-  if (heap->array->size > 0)
+  const bool removeLast = (index == heap->items->size - 1);
+  if (!removeLast)
+  {
+    _vector_set(
+      heap->items,
+      index,
+      _vector_get(heap->items, heap->items->size - 1));
+    _vector_set(
+      heap->values,
+      index,
+      _vector_get(heap->values, heap->values->size - 1));
+  }
+  vector_pop(heap->items);
+  vector_pop(heap->values);
+  if (!removeLast && heap->items->size > 0)
     _heap_bubble_down(heap, index);
 }
 
-ItemValue* heap_top_raw(Heap* heap)
+void _heap_remove(Heap* heap, void* item)
+{
+  // First, find index of the item:
+  const Int index = _heap_get_index(heap, item);
+  if (index >= 0)
+    _heap_remove_at_index(heap, index);
+}
+
+ItemValue _heap_top(Heap* heap)
 {
-  return (ItemValue*)(heap->array->datas[0]);
+  ItemValue top;
+  top.item = _vector_get(heap->items, 0);
+  vector_get(heap->values, 0, top.value);
+  return top;
 }
 
 void heap_pop(Heap* heap)
 {
-  _heap_remove(heap, 0);
+  _heap_remove_at_index(heap, 0);
 }
 
 void heap_clear(Heap* heap)
 {
-  for (UInt i = 0; i < heap->array->size; i++)
-    // Extra memory releases which wouldn't be done in vector_clear()
-    safe_free(((ItemValue*)(heap->array->datas[i]))->item);
-  vector_clear(heap->array);
+  vector_clear(heap->items);
+  vector_clear(heap->values);
 }
 
 void heap_destroy(Heap* heap)
 {
-  heap_clear(heap);
-  safe_free(heap->array);
+  vector_destroy(heap->items);
+  vector_destroy(heap->values);
   safe_free(heap);
 }