[Olsr-dev] Improving SPF with binary heaps

[Henning Rogge]

On Sat, Jul 11, 2015 at 12:43 AM, Saulo Queiroz <(spam-protected)> wrote:
> Hi Henning,
> I've supervised the work of Diogo.
> Regarding you first question, response is no. Not all procedures are used.
> Diogo just listed in .h all classical procedures of a binary heap but only
> the ones required by Dijkstra are implemented. The other are there just
> as a reminder, but he can clean .h,  No problem.

I would suggest moving everything that is "internal" to a static
function... this makes it easier for new users of the API to
understand what they need because they only have to look at the header
file.

> Regarding the second question:  heap_extract_min is the procedure you asked
> about.
> Note however that the idea is to replace AVL only for Dijkstra and keeping
> AVL there for other stuff. ok?

I would like to have this as a generic API, so I am looking which
basic functions we have, we still need or we cannot get.

Basics for both lists and AVL trees in OONF (which is the base of OLSRv2) is
- init
- insert
- remove
- get(key)
- get_first
- get_last

and a good way to iterate over the elements of the tree/list (which
would enable me to write iterator macros like the ones in
http://olsr.org/git/?p=oonf.git;a=blob;f=src-api/common/list.h;h=a6146dcc9eb4d70ef1c2ae32b382df0460d948b0;hb=master#l315
).

Can we have the same functions for a binary heap?

If yes, it makes sense to disallow AVL trees with overlapping keys
(which is a parameter in avl_init at the moment) and tell the
developers "use a binary heap instead for this case".

The heap (because its different than AVL) might of course have a few
more functions, like the "modify key later" functions you have. Its
just about the same "basic set".

Henning