- 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);