Added BinaryHeap

[bogdanm]

Implementation of an implicit binary heap with a user defined comparison function, see BinaryHeap.h for more details.

[bogdanm]

@0xc0170 , @autopulated , this is (finally) the last major thing I need for MINAR

[autopulated]

Looks good, tests look like they cover everything so I haven't looked at the actual logic.

Apart from the size_t/unsigned question – do you think a get_and_remove_root/pop_root function would make sense?

[bogdanm]

Yup, I'll implement that too. Also, I find that I really miss a compare function that keeps a sort of state and I was thinking how to implement that in the absence of std::function. My first take was this:

template <typename T>
class BinaryHeap {
public:
    class ICompare {
        virtual bool operator ()(const T& e1, const T& e2) const = 0;
    };

    bool init(size_t initial_capacity, size_t grow_capacity, UAllocTraits_t alloc_traits, const ICompare* comparator, unsigned alignment = MBED_UTIL_POOL_ALLOC_DEFAULT_ALIGN);
    ...
}

That'll work, but now something needs to derive from ICompare for elementary data types, which isn't convenient. Thoughts?

[autopulated]

The standard container classes have a template parameter that can be the type of a functor object to be used to compare (which is then passed in in the constructor), this defaults to std::less<Key_T>. This type must implement bool operator()(Key_T const& a, Key_T const& b);

[bogdanm]

Thanks, but I'm looking for a much 'lighter' solution here. I'll come up with something :)

[autopulated]

Depending on how you look at it, an additional template parameter might be lighter than a virtual method call for each comparison, but yeah point taken, it could lead to significant ballooning of instantiated template code.

[bogdanm]

So, you have a single change to guess what I came up with after desperately trying to avoid templates ... :D Turns out there's simply no sane enough way to do this kind of thing without using templates and/or std::function and friends, or if it is, it's completely outside my reach.

[bogdanm]

So, meanwhile, I realized that a heap is not really the best data structure for MINAR :D But at least I've implemented it :)

[autopulated]

Oh because we insert a lot?

[bogdanm]

Not necessarily, mainly because of this loop:

https://github.com/ARMmbed/minar/blob/master/source/minar.cpp#L415

That would've been better suited to a sorted array. With a heap, I always have to iterate through the whole thing. But there's no such thing as a lighting fast data structure that takes no memory at all :), so I think this will do for now. Unless you think that's a critical operation for the main loop, in which case I'll resort to implementing a sorted array.

[autopulated]

That loop is no longer required now that resources aren't in the picture though, no? (The only reason a callback would trigger that warning would be if it were lagging because it needed resources that were not available)

[bogdanm]

You are quicker than me :) Yes, sorry, I was just going to go back and say that's a non-issue now. Sorry for the noise.

[autopulated]

np :stuck_out_tongue_winking_eye: