ARMmbed / core-util

DEPRECATED: Mbed 3 utilities library
Other
12 stars 17 forks source link

Fixed problem with BinaryHeap::remove() #109

Open antevir opened 8 years ago

antevir commented 8 years ago

When last element was swapped with the removed element it was only propagated downwards. Depending if the swapped value is greater or smaller than its parent it may instead need to propagate upwards.

Fixes #108

antevir commented 8 years ago

I have tested the modification with the function below:

#include "core-util/BinaryHeap.h"

void testHeap()
{
    UAllocTraits_t traits = { 0 };
    mbed::util::BinaryHeap<int, mbed::util::MinCompare<int>> heap;
    heap.init(40, 40, traits);

    while (true) {
        int values[40];
        int cnt = 10 + (rand() % 30);

        for (int i = 0; i < cnt; i++) {
            int value = rand() % 100;
            values[i] = value;
            heap.insert(values[i]);
        }

        int remCnt = rand() % 5;
        for (int i = 0; i < remCnt; i++) {
            int remValue = values[rand() % cnt];
            heap.remove(remValue);
        }

        int lastValue = -1;
        while (!heap.is_empty()) {
            int value = heap.pop_root();
            if (value < lastValue)
                printf("ERROR\n");
            lastValue = value;
        }
    }
}
0xc0170 commented 8 years ago

Thanks for providing the fix and the test case

cc @bogdanm