[m-users.] priority search queue ADT

[Paul Bone]

On Thu, Oct 23, 2014 at 09:59:14PM +0200, 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?

I'm not sure, I'd lean towards putting only the most commonly used
datastructures in the standard library.

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

LGPL is fine for the standard library.  I think it can have any (Free/Open)
license for extras.

Although the contributions page refers to copyright assignment as a problem.
In practice over the last one and a half years we've simply assigned the
copyright to "The Mercury Team".  By contributing code you would be included
in "The Mercury Team".  I think this is already true because you contributed
to integer.m.

THe contributions page also talks about relicencing.  I don't think
relicencing is very likely and I don't see any problems with the current
licensing.  Mercury can be used commercially without any unreasonable
restrictions.  In fact I suggest that we remove this text from the website.

Thanks.

-- 
Paul Bone