X-Git-Url: https://git.auder.net/?p=cgds.git;a=blobdiff_plain;f=src%2FHeap.c;fp=src%2FHeap.c;h=e1cb8cea4694f421325808543525d18fe62125e3;hp=fd41a0969a1f3c61d08e95cb60d464e69af1d725;hb=e45132acdb58c076d5e06849fa51c26de9a7486d;hpb=1ff641f9960fa6c6081817a5641afb22fad91dcd

diff --git a/src/Heap.c b/src/Heap.c
index fd41a09..e1cb8ce 100644
--- 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);
 }