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

Michael Richter ttmrichter at gmail.com
Mon Nov 18 18:32:25 AEDT 2013

```(A colourful version may be obtained here:
)

Summary of proposed changes:

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.

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.

@@ -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...