[m-rev.] Proposed changes to pqueue.m

[Michael Richter]

(A colourful version may be obtained here:
https://mail.google.com/mail/?ui=2&shva=1#label/programming%2Fmercury/141c9c3b88aa059e?compose=1426a13a7f8f05fc
)

Summary of proposed changes:

   1. Add pqueue.is_empty/1 predicate.
   Rationale: Despite this effectively being the same as testing
   pqueue.length/1 for 0, it is more immediately clear what is being tested
   for.  Code using pqueue.is_empty/1 can have its intent more readily
   discerned.

   2. Add pqueue.peek/2 predicate.
   Rationale: There are many cases where it is desirable to know what is at
   the top of the priority queue without necessarily extracting it from the
   queue at that point.  This is a frequently-used operation and is supplied
   in most (all?) of the priority queue implementations I've encountered
   before.

   3. Add pqueue.det_peek/2 predicate and pqueue.det_peek/1 function.
   Rationale: Deterministic version of pqueue.peek/2.  Mirrors provision of
   pqueue.remove vs. pqueue.det_remove.  A deterministic version is required
   to make a meaningful function.

   4. Add pqueue.merge/3 predicate and pqueue.merge/2 function.
   Rationale: While not as common as peek/2 in other implementations,
   merging of priority queues is a fairly common task.

I have done basic testing of all of the above operations, but am unsure
where to place tests in the current source code hierarchy.  (There appears
to be no test suite for the existing pqueue functionality.)  The code, as
far as I can tell, works as expected.  The testing I did can be found at
http://sprunge.us/cjKe?prolog for inspection and/or expansion.

Comments and suggestions appreciated.

@@ -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.
 +    %
 +:- 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,15 @@
  :- pred pqueue.insert(K::in, V::in, pqueue(K, V)::in, pqueue(K, V)::out)
      is det.

 +    % Extract the smallest item from the priority queue without removing
it.
 +    % Fails if the priority queue is empty.
 +    %
 +:- pred pqueue.peek(pqueue(K, V)::in, V::out) is semidet.
 +
 +    % As above, but calls error/1 if the priority queue is empty.
 +:- func pqueue.det_peek(pqueue(K, V)) = V.
 +:- pred pqueue.det_peek(pqueue(K, V)::in, V::out) is det.
 +
      % Remove the smallest item from the priority queue.
      % Fails if the priority queue is empty.
      %
 @@ -58,6 +71,12 @@
  :- 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.
 +:- func pqueue.merge(pqueue(K, V), pqueue(K, V)) = pqueue(K, V).
 +:- pred pqueue.merge(pqueue(K, V)::in, pqueue(K, V)::in, pqueue(K,
V)::out)
 +    is det.
 +
      % Extract all the items from a priority queue by repeated
      % removal, and place them in an association list.
      %
 @@ -106,6 +125,26 @@


%---------------------------------------------------------------------------%

 +pqueue.is_empty(empty).
 +
 +%---------------------------------------------------------------------------%
 +
 +pqueue.peek(pqueue(_, _, V, _, _), V).
 +
 +%---------------------------------------------------------------------------%
 +
 +pqueue.det_peek(PQ) = V :-
 +    pqueue.det_peek(PQ, V).
 +
 +pqueue.det_peek(PQ, V) :-
 +    ( pqueue.peek(PQ, T) ->
 +        V = T
 +    ;
 +        error("pqueue.det_peek/2: empty priority queue")
 +    ).
 +
 +%---------------------------------------------------------------------------%
 +
  pqueue.insert(!.PQ, K, V) = !:PQ :-
      pqueue.insert(K, V, !PQ).

 @@ -150,7 +189,7 @@
          V = V0
        else
          error("pqueue.det_remove/4: empty priority queue")
 -    ).
 +    ).

  pqueue.remove(K, V, pqueue(_, K, V, L0, R0), PQ) :-
      pqueue.remove_2(L0, R0, PQ).
 @@ -177,6 +216,18 @@


%---------------------------------------------------------------------------%

 +pqueue.merge(PQ1, PQ2) = PQ3 :-
 +    pqueue.merge(PQ1, PQ2, PQ3).
 +
 +pqueue.merge(empty,                 PQ2,               PQ2).
 +pqueue.merge(PQ1 at pqueue(_,_,_,_,_), empty,             PQ1).
 +pqueue.merge(PQ1 at pqueue(_,_,_,_,_), pqueue(_,K,V,L,R), PQ3) :-
 +    pqueue.merge(PQ1, L, IPQ1),
 +    pqueue.merge(IPQ1, R, IPQ2),
 +    pqueue.insert(K, V, IPQ2, PQ3).
 +
 +%---------------------------------------------------------------------------%
 +
  pqueue.to_assoc_list(PQ) = AL :-
      pqueue.to_assoc_list(PQ, AL).



P.S. The bike shed should be cerulean.  ;-)

-- 
"Perhaps people don't believe this, but throughout all of the discussions
of entering China our focus has really been what's best for the Chinese
people. It's not been about our revenue or profit or whatnot."
--Sergey Brin, demonstrating the emptiness of the "don't be evil" mantra.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20131118/75ad471c/attachment.html>