[m-rev.] For review 1/2: Beefed up the pqueue implementation.

[Julien Fischer]

Hi,

On Sun, 24 Nov 2013, Paul Bone wrote:

> Branches: master
>
> For review by anyone.
>
> Submitted on behalf of Michael Richter <ttmrichter at gmail.com>
>
> ---
>
> Beefed up the pqueue implementation.
>
> library/pqueue.m:
>    Added predicates is_empty/1, peek/3, peek_key/2, peek_value/2,
>    det_peek/3, merge/3.  Added functions det_peek_key/1, det_peek_value/1.
>
>    Also reformatted code to fit within 76 columns.

Why?  The limit is 79.

> ---
> library/pqueue.m | 85 ++++++++++++++++++++++++++++++++++++++++++++++++++++----
> 1 file changed, 80 insertions(+), 5 deletions(-)
>
> diff --git a/library/pqueue.m b/library/pqueue.m
> index 99f1b13..48e2d11 100644
> --- a/library/pqueue.m
> +++ b/library/pqueue.m
> @@ -40,6 +40,10 @@
> :- func pqueue.init = pqueue(K, V).
> :- pred pqueue.init(pqueue(K, V)::out) is det.
>
> +    % Test if a priority queue is empty.

    True iff the priority queue is empty.

> +    %
> +:- pred pqueue.is_empty(pqueue(K, V)::in) is semidet.
> +
>     % Insert a value V with key K into a priority queue
>     % and return the new priority queue.
>     %
> @@ -47,6 +51,27 @@
> :- pred pqueue.insert(K::in, V::in, pqueue(K, V)::in, pqueue(K, V)::out)
>     is det.
>
> +    % Extract the smallest key/value pair from the priority queue without
> +    % removing it.  Fails if the priority queue is empty.


Use "key-value" rather than "key/value".  (That's what we use elsewhere
in the library.)

> +    %
> +:- pred pqueue.peek(pqueue(K, V)::in, K::out, V::out) is semidet.
> +
> +    % Extract the smallest key from the priority queue without removing it.
> +    % Fails if the priority queue is empty.
> +    %
> +:- pred pqueue.peek_key(pqueue(K, V)::in, K::out) is semidet.
> +
> +    % Extract the smallest value from the priority queue without removing
> +    % it.  Fails if the priority queue is empty.
> +    %
> +:- pred pqueue.peek_value(pqueue(K, V)::in, V::out) is semidet.
> +
> +    % As above, but calls error/1 if the priority queue is empty.
> +    %
> +:- pred pqueue.det_peek(pqueue(K, V)::in, K::out, V::out) is det.
> +:- func pqueue.det_peek_key(pqueue(K, V)) = K.
> +:- func pqueue.det_peek_value(pqueue(K, V)) = V.
> +
>     % Remove the smallest item from the priority queue.
>     % Fails if the priority queue is empty.
>     %
> @@ -58,11 +83,18 @@
> :- pred pqueue.det_remove(K::out, V::out, pqueue(K, V)::in, pqueue(K, V)::out)
>     is det.
>
> +    % Merges all the entries of one priority queue with another, returning
> +    % the merged list.

There should be a "%" on a separate line there.

Looks ok otherwise.

Cheers,
Julien.