[m-rev.] for review: priority search queue ADT

Matthias Güdemann matthias.guedemann at googlemail.com
Thu Nov 20 04:15:01 AEDT 2014


Hi Julien,

> W.r.t to license all standard library modules are currently licensed
> under the LGPL.

no problem, I am ok with that.

> I will post a review of the code at a later date (hoepfully soon).

While using the code as a direct replacement for pqueue in an
implementation of a minimal spanning tree algorithm, I made the
following observations:

 - it is slower (no big surprise, using 234-trees as in pqueue should be faster)
 - there should be a "from_assoc_list" predicate
 - the order of arguments is different, pqueue(K, V) uses Key as
priorites, psqueue(K, P) uses P as priorities and Keys for the
underlying balanced trees. This means that one has to switch the
arguments when going from psqueue to pqueue, this should therefore
better be psqueue(P, K)
 - for the extraction of the highest priority element pqueue uses the
argument order "remove(K::out, V::out, pqueue(K, V)::in, pqueue(K,
V)::out)" and psqueue uses "del_min(psqueue(K, P)::in, K::out, P::out,
psqueue(K, P)::out)", i.e., one cannot use psqueue.del_min using state
variable threading. I think that every predicate in question should
have be the psqueue::in, psqueue:out pair as last arguments.

I will integrate the changes and provide a newer version soon.

Best regards,
Matthias



More information about the reviews mailing list