Now using 2 spaces instead of tabs. Fix copyright years. Improve documentation

[cgds.git] / src / Heap.c

diff --git a/src/Heap.c b/src/Heap.c
index fd41a09..e1cb8ce 100644 (file)
--- a/src/Heap.c
+++ b/src/Heap.c
@@ -8,46 +8,46 @@
 
 Heap* _heap_new(size_t dataSize, OrderType hType, UInt arity)
 {
-       Heap* heap = (Heap*)safe_malloc(sizeof(Heap));
-       heap->arity = arity;
-       heap->hType = hType;
-       heap->dataSize = dataSize;
-       heap->array = _vector_new(sizeof(ItemValue));
-       return heap;
+  Heap* heap = (Heap*)safe_malloc(sizeof(Heap));
+  heap->arity = arity;
+  heap->hType = hType;
+  heap->dataSize = dataSize;
+  heap->array = _vector_new(sizeof(ItemValue));
+  return heap;
 }
 
 Heap* heap_copy(Heap* heap)
 {
-       Heap* heapCopy = _heap_new(heap->dataSize, heap->hType, heap->arity);
-       // HACK: vector_copy is not enough,
+  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 =
+  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(
+  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));
-       }
-       return heapCopy;
+    memcpy(heapCopy->array->datas[i], &itemValueCopy, sizeof(ItemValue));
+  }
+  return heapCopy;
 }
 
 bool heap_empty(Heap* heap)
 {
-       return vector_empty(heap->array);
+  return vector_empty(heap->array);
 }
 
 UInt heap_size(Heap* heap)
 {
-       return vector_size(heap->array);
+  return vector_size(heap->array);
 }
 
 // NOTE: [perf] in two following methods, full heap[k] exchanges are
@@ -57,130 +57,130 @@ UInt heap_size(Heap* heap)
 
 void _heap_bubble_up(Heap* heap, UInt startIndex)
 {
-       UInt currentIndex = startIndex;
-       ItemValue* startItemValue = heap->array->datas[startIndex];
-       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))
-               {
-                       // moving element has landed: apply final affectation
-                       heap->array->datas[currentIndex] = startItemValue;
-                       break;
-               }
-               // move one level up: the parent goes one level down
-               heap->array->datas[currentIndex] = heap->array->datas[nextIndex];
-               currentIndex = nextIndex;
-       }
+  UInt currentIndex = startIndex;
+  ItemValue* startItemValue = heap->array->datas[startIndex];
+  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))
+    {
+      // moving element has landed: apply final affectation
+      heap->array->datas[currentIndex] = startItemValue;
+      break;
+    }
+    // move one level up: the parent goes one level down
+    heap->array->datas[currentIndex] = heap->array->datas[nextIndex];
+    currentIndex = nextIndex;
+  }
 }
 
 void _heap_bubble_down(Heap* heap, UInt startIndex)
 {
-       UInt currentIndex = startIndex;
-       ItemValue* startItemValue = heap->array->datas[startIndex];
-       while (true)
-       {
-               if (currentIndex * heap->arity >= heap->array->size)
-               {
-                       // 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 (Int 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))
-                       {
-                               topChildIndex = childIndex;
-                               topChildValue = childValue;
-                       }
-               }
-               // 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
-               {
-                       // moving element has landed: apply final affectation
-                       heap->array->datas[currentIndex] = startItemValue;
-                       break;
-               }
-               currentIndex = topChildIndex;
-       }
+  UInt currentIndex = startIndex;
+  ItemValue* startItemValue = heap->array->datas[startIndex];
+  while (true)
+  {
+    if (currentIndex * heap->arity >= heap->array->size)
+    {
+      // 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 (Int 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))
+      {
+        topChildIndex = childIndex;
+        topChildValue = childValue;
+      }
+    }
+    // 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
+    {
+      // moving element has landed: apply final affectation
+      heap->array->datas[currentIndex] = startItemValue;
+      break;
+    }
+    currentIndex = topChildIndex;
+  }
 }
 
 void _heap_insert(Heap* heap, void* item, Real value)
 {
-       ItemValue itemValue =
+  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);
+  memcpy(itemValue.item, item, heap->dataSize);
+  _vector_push(heap->array, &itemValue);
+  _heap_bubble_up(heap, heap->array->size-1);
 }
 
 void _heap_modify(Heap* heap, UInt index, Real newValue)
 {
-       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))
-       {
-               _heap_bubble_down(heap, index);
-       }
-       else
-               _heap_bubble_up(heap, index);
+  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))
+  {
+    _heap_bubble_down(heap, index);
+  }
+  else
+    _heap_bubble_up(heap, index);
 }
 
 void _heap_remove(Heap* heap, UInt 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)
-               _heap_bubble_down(heap, 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)
+    _heap_bubble_down(heap, index);
 }
 
 ItemValue* heap_top_raw(Heap* heap)
 {
-       return (ItemValue*)(heap->array->datas[0]);
+  return (ItemValue*)(heap->array->datas[0]);
 }
 
 void heap_pop(Heap* heap)
 {
-       _heap_remove(heap, 0);
+  _heap_remove(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);
-               //safe_free((ItemValue*)heap->array->datas[i]);
-       }
-       vector_clear(heap->array);
+  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);
+    //safe_free((ItemValue*)heap->array->datas[i]);
+  }
+  vector_clear(heap->array);
 }
 
 void heap_destroy(Heap* heap)
 {
-       heap_clear(heap);
-       safe_free(heap->array);
-       safe_free(heap);
+  heap_clear(heap);
+  safe_free(heap->array);
+  safe_free(heap);
 }