#include "cgds/Heap.h"
-// NOTE: no _init() method here, since Heap has no specific initialization
+// NOTE: no init() method here, since Heap has no specific initialization
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->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));
- }
- return heapCopy;
+ 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
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;
- }
+ if (startIndex == 0)
+ // Nothing to do in this case
+ return;
+ UInt currentIndex = startIndex;
+ void* startItem = _vector_get(heap->items, startIndex);
+ Real startValue = *((Real*)(_vector_get(heap->values, startIndex)));
+ bool startItemReallocated = false;
+ while (true)
+ {
+ 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)
+ {
+ _vector_set(heap->items, currentIndex, startItem);
+ _vector_set(heap->values, currentIndex, &startValue);
+ }
+ break;
+ }
+ if (startItemReallocated)
+ safe_free(startItem);
}
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;
- }
+ if (startIndex * heap->arity + 1 >= heap->items->size)
+ // Nothing to do: already in a leaf
+ return;
+ UInt currentIndex = startIndex;
+ void* startItem = _vector_get(heap->items, startIndex);
+ Real startValue = *((Real*)(_vector_get(heap->values, startIndex)));
+ bool startItemReallocated = false;
+ while (true)
+ {
+ bool land = (currentIndex * heap->arity + 1 >= heap->items->size),
+ applyExchange = true;
+ if (!land)
+ {
+ // Find top child (min or max)
+ UInt topChildIndex;
+ Real topChildValue = (heap->hType == MIN_T ? INFINITY : -INFINITY);
+ for (UInt i = 1; i <= heap->arity; i++)
+ {
+ 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;
+ }
+ if (applyExchange)
+ {
+ // Moving element has landed (in a leaf): apply final affectation
+ _vector_set(heap->items, currentIndex, startItem);
+ _vector_set(heap->values, currentIndex, &startValue);
+ }
+ 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))
- {
- _heap_bubble_down(heap, index);
- }
- else
- _heap_bubble_up(heap, index);
+ 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_remove(Heap* heap, UInt index)
+void _heap_modify(Heap* heap, void* item, Real newValue)
{
- 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);
+ // 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);
}
-ItemValue* heap_top_raw(Heap* heap)
+void _heap_remove_at_index(Heap* heap, Int index)
{
- return (ItemValue*)(heap->array->datas[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);
+}
+
+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)
+{
+ 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);
- //safe_free((ItemValue*)heap->array->datas[i]);
- }
- vector_clear(heap->array);
+ vector_clear(heap->items);
+ vector_clear(heap->values);
}
void heap_destroy(Heap* heap)
{
- heap_clear(heap);
- safe_free(heap->array);
- safe_free(heap);
+ vector_destroy(heap->items);
+ vector_destroy(heap->values);
+ safe_free(heap);
}
projects / cgds.git / blobdiff