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

[Paul Bone]

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.
---
 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.
+    %
+:- 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.
+    %
+:- 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.
+:- 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.
     %
 :- func pqueue.to_assoc_list(pqueue(K, V)) = assoc_list(K, V).
-:- pred pqueue.to_assoc_list(pqueue(K, V)::in, assoc_list(K, V)::out) is det.
+:- pred pqueue.to_assoc_list(pqueue(K, V)::in, assoc_list(K, V)::out)
+    is det.
 
     % Insert all the key-value pairs in an association list
     % into a priority queue.
@@ -106,6 +138,28 @@ pqueue.init(empty).
 
 %---------------------------------------------------------------------------%
 
+pqueue.is_empty(empty).
+
+%---------------------------------------------------------------------------%
+
+pqueue.peek(pqueue(_, K, V, _, _), K, V).
+pqueue.peek_key(pqueue(_, K, _, _, _), K).
+pqueue.peek_value(pqueue(_, _, V, _, _), V).
+
+%---------------------------------------------------------------------------%
+
+pqueue.det_peek(PQ, K, V) :-
+    ( pqueue.peek(PQ, J, T) ->
+        K = J, V = T
+    ;
+        unexpected($file, $pred, "empty priority queue")
+    ).
+
+pqueue.det_peek_key(PQ) = K :- pqueue.det_peek(PQ, K, _).
+pqueue.det_peek_value(PQ) = V :- pqueue.det_peek(PQ, _, V).
+
+%---------------------------------------------------------------------------%
+
 pqueue.insert(!.PQ, K, V) = !:PQ :-
     pqueue.insert(K, V, !PQ).
 
@@ -132,8 +186,8 @@ pqueue.insert_2(K, V, pqueue(D0, K0, V0, L0, R0), empty,
         pqueue(D0, K0, V0, L0, R0), pqueue(0, K, V, empty, empty)).
 pqueue.insert_2(K, V, empty, pqueue(D0, K0, V0, L0, R0),
         pqueue(0, K, V, empty, empty), pqueue(D0, K0, V0, L0, R0)).
-pqueue.insert_2(K, V, pqueue(D0, K0, V0, L0, R0), pqueue(D1, K1, V1, L1, R1),
-        PQ1, PQ2) :-
+pqueue.insert_2(K, V, pqueue(D0, K0, V0, L0, R0),
+                pqueue(D1, K1, V1, L1, R1), PQ1, PQ2) :-
     ( D0 > D1 ->
         pqueue.insert(K, V, pqueue(D1, K1, V1, L1, R1), PQ2),
         PQ1 = pqueue(D0, K0, V0, L0, R0)
@@ -149,8 +203,8 @@ pqueue.det_remove(K, V, !PQ) :-
         K = K0,
         V = V0
       else
-        error("pqueue.det_remove/4: empty priority queue")
-    ). 
+        unexpected($file, $pred, "empty priority queue")
+    ).
 
 pqueue.remove(K, V, pqueue(_, K, V, L0, R0), PQ) :-
     pqueue.remove_2(L0, R0, PQ).
@@ -177,6 +231,27 @@ pqueue.remove_2(pqueue(D0, K0, V0, L0, R0), pqueue(D1, K1, V1, L1, R1), PQ) :-
 
 %---------------------------------------------------------------------------%
 
+pqueue.merge(A, B) = C :-
+    pqueue.merge(A, B, C).
+
+pqueue.merge(A, B, C) :-
+  ( pqueue.length(A) =< pqueue.length(B) ->
+      pqueue.merge2(A, B, C)
+  ;
+      pqueue.merge2(B, A, C) ).
+
+:- pred pqueue.merge2(pqueue(K, V)::in, pqueue(K, V)::in, pqueue(K, V)::out)
+    is det.
+
+pqueue.merge2(empty,                   B,     B).
+pqueue.merge2(A at pqueue(_, _, _, _, _), empty, A).
+pqueue.merge2(pqueue(_, K, V, L, R),   !.PQ at pqueue(_, _, _, _, _), !:PQ) :-
+    pqueue.merge2(L, !PQ),
+    pqueue.merge2(R, !PQ),
+    pqueue.insert(K, V, !PQ).
+
+%---------------------------------------------------------------------------%
+
 pqueue.to_assoc_list(PQ) = AL :-
     pqueue.to_assoc_list(PQ, AL).
 
-- 
1.8.4.rc3