[m-users.] priority search queue ADT

[Julien Fischer]

Hi Matthias,

On Thu, 23 Oct 2014, Matthias Güdemann wrote:

> Hello @all,
>
> I implemented a priority search queue in Mercury. This is similar to
> pqueue.m (priority queue), but also allows to look up keys, delete keys
> and adjust the priorities of keys.
>
> It follows closely the implementation described by Ralf Hinze in his
> ICFP 2001 paper "A Simple Implementation Technique for Priority Search
> Queues". Peeking at the element with highest priority is in O(1),
> inserting, deletion, key look-up and adjusting a priority is in
> O(log(n)). In contrast to the 234-trees of pqueue.m, it uses
> weight-balanced trees, so it might have slightly larger constants for
> the same operations.
>
> I did this to implement an efficient, fully declarative Dijkstra's
> single source, shortest path search on digraphs. The current test cases
> are the example in the paper and 3 project Euler problems
> (81/82/83). Currently, I have not yet decided on any license, in general
> I'd lean towards BSD, but it would be no problem to put into public
> domain if necessary[1]. I'd be happy to see this as a standard ADT in
> Mercury.
>
> - Are you interested in this?

Certainly.

> - What is necessary to have it integrated in the library or as an
>   extra?

As part of the extras not a lot ;-)  (The bar for entry for the extras
has never been terribly high.)

As part of the standard library you would need to ensure that it follows the
conventions used in the library for things like procedure names, argument
ordering and documentation.  There are some notes regarding the later at the
end of <http://www.mercurylang.org/development/developers/coding_standards.html>.

If you want to post the code for review, we'd be happy to look over it
and suggest any changes that could be made with respect to the above.

Cheers,
Julien.