<div dir="ltr">(A colourful version may be obtained here: <a href="https://mail.google.com/mail/?ui=2&shva=1#label/programming%2Fmercury/141c9c3b88aa059e?compose=1426a13a7f8f05fc">https://mail.google.com/mail/?ui=2&shva=1#label/programming%2Fmercury/141c9c3b88aa059e?compose=1426a13a7f8f05fc</a>)<div>
<br></div><div>Summary of proposed changes:</div><div><ol><li>Add pqueue.is_empty/1 predicate.<br>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.<br>
<br></li><li>Add pqueue.peek/2 predicate.<br>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.<br>
<br></li><li>Add pqueue.det_peek/2 predicate and pqueue.det_peek/1 function.<br>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.<br>
<br></li><li>Add pqueue.merge/3 predicate and pqueue.merge/2 function.<br>Rationale: While not as common as peek/2 in other implementations, merging of priority queues is a fairly common task.</li></ol><div>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 <a href="http://sprunge.us/cjKe?prolog">http://sprunge.us/cjKe?prolog</a> for inspection and/or expansion.</div>
</div><div><br></div><div>Comments and suggestions appreciated.</div><div><br></div><div><div><font face="courier new, monospace">@@ -40,6 +40,10 @@</font></div><div><font face="courier new, monospace"> :- func pqueue.init = pqueue(K, V).</font></div>
<div><font face="courier new, monospace"> :- pred pqueue.init(pqueue(K, V)::out) is det.</font></div><div><font face="courier new, monospace"> </font></div><div><font face="courier new, monospace"> + % Test if a priority queue is empty.</font></div>
<div><font face="courier new, monospace"> + %</font></div><div><font face="courier new, monospace"> +:- pred pqueue.is_empty(pqueue(K,V)::in) is semidet.</font></div><div><font face="courier new, monospace"> +</font></div>
<div><font face="courier new, monospace"> % Insert a value V with key K into a priority queue</font></div><div><font face="courier new, monospace"> % and return the new priority queue.</font></div><div><font face="courier new, monospace"> %</font></div>
<div><font face="courier new, monospace"> @@ -47,6 +51,15 @@</font></div><div><font face="courier new, monospace"> :- pred pqueue.insert(K::in, V::in, pqueue(K, V)::in, pqueue(K, V)::out)</font></div><div><font face="courier new, monospace"> is det.</font></div>
<div><font face="courier new, monospace"> </font></div><div><font face="courier new, monospace"> + % Extract the smallest item from the priority queue without removing it.</font></div><div><font face="courier new, monospace"> + % Fails if the priority queue is empty.</font></div>
<div><font face="courier new, monospace"> + %</font></div><div><font face="courier new, monospace"> +:- pred pqueue.peek(pqueue(K, V)::in, V::out) is semidet.</font></div><div><font face="courier new, monospace"> +</font></div>
<div><font face="courier new, monospace"> + % As above, but calls error/1 if the priority queue is empty.</font></div><div><font face="courier new, monospace"> +:- func pqueue.det_peek(pqueue(K, V)) = V.</font></div><div>
<font face="courier new, monospace"> +:- pred pqueue.det_peek(pqueue(K, V)::in, V::out) is det.</font></div><div><font face="courier new, monospace"> +</font></div><div><font face="courier new, monospace"> % Remove the smallest item from the priority queue.</font></div>
<div><font face="courier new, monospace"> % Fails if the priority queue is empty.</font></div><div><font face="courier new, monospace"> %</font></div><div><font face="courier new, monospace"> @@ -58,6 +71,12 @@</font></div>
<div><font face="courier new, monospace"> :- pred pqueue.det_remove(K::out, V::out, pqueue(K, V)::in, pqueue(K, V)::out)</font></div><div><font face="courier new, monospace"> is det.</font></div><div><font face="courier new, monospace"> </font></div>
<div><font face="courier new, monospace"> + % Merges all the entries of one priority queue with another, returning the</font></div><div><font face="courier new, monospace"> + % merged list.</font></div><div><font face="courier new, monospace"> +:- func pqueue.merge(pqueue(K, V), pqueue(K, V)) = pqueue(K, V).</font></div>
<div><font face="courier new, monospace"> +:- pred pqueue.merge(pqueue(K, V)::in, pqueue(K, V)::in, pqueue(K, V)::out)</font></div><div><font face="courier new, monospace"> + is det.</font></div><div><font face="courier new, monospace"> +</font></div>
<div><font face="courier new, monospace"> % Extract all the items from a priority queue by repeated</font></div><div><font face="courier new, monospace"> % removal, and place them in an association list.</font></div>
<div><font face="courier new, monospace"> %</font></div><div><font face="courier new, monospace"> @@ -106,6 +125,26 @@</font></div><div><font face="courier new, monospace"> </font></div><div><font face="courier new, monospace"> %---------------------------------------------------------------------------%</font></div>
<div><font face="courier new, monospace"> </font></div><div><font face="courier new, monospace"> +pqueue.is_empty(empty).</font></div><div><font face="courier new, monospace"> +</font></div><div><font face="courier new, monospace"> +%---------------------------------------------------------------------------%</font></div>
<div><font face="courier new, monospace"> +</font></div><div><font face="courier new, monospace"> +pqueue.peek(pqueue(_, _, V, _, _), V).</font></div><div><font face="courier new, monospace"> +</font></div><div><font face="courier new, monospace"> +%---------------------------------------------------------------------------%</font></div>
<div><font face="courier new, monospace"> +</font></div><div><font face="courier new, monospace"> +pqueue.det_peek(PQ) = V :-</font></div><div><font face="courier new, monospace"> + pqueue.det_peek(PQ, V).</font></div>
<div><font face="courier new, monospace"> +</font></div><div><font face="courier new, monospace"> +pqueue.det_peek(PQ, V) :-</font></div><div><font face="courier new, monospace"> + ( pqueue.peek(PQ, T) -></font></div>
<div><font face="courier new, monospace"> + V = T</font></div><div><font face="courier new, monospace"> + ;</font></div><div><font face="courier new, monospace"> + error("pqueue.det_peek/2: empty priority queue")</font></div>
<div><font face="courier new, monospace"> + ).</font></div><div><font face="courier new, monospace"> +</font></div><div><font face="courier new, monospace"> +%---------------------------------------------------------------------------%</font></div>
<div><font face="courier new, monospace"> +</font></div><div><font face="courier new, monospace"> pqueue.insert(!.PQ, K, V) = !:PQ :-</font></div><div><font face="courier new, monospace"> pqueue.insert(K, V, !PQ).</font></div>
<div><font face="courier new, monospace"> </font></div><div><font face="courier new, monospace"> @@ -150,7 +189,7 @@</font></div><div><font face="courier new, monospace"> V = V0</font></div><div><font face="courier new, monospace"> else</font></div>
<div><font face="courier new, monospace"> error("pqueue.det_remove/4: empty priority queue")</font></div><div><font face="courier new, monospace"> - ). </font></div><div><font face="courier new, monospace"> + ).</font></div>
<div><font face="courier new, monospace"> </font></div><div><font face="courier new, monospace"> pqueue.remove(K, V, pqueue(_, K, V, L0, R0), PQ) :-</font></div><div><font face="courier new, monospace"> pqueue.remove_2(L0, R0, PQ).</font></div>
<div><font face="courier new, monospace"> @@ -177,6 +216,18 @@</font></div><div><font face="courier new, monospace"> </font></div><div><font face="courier new, monospace"> %---------------------------------------------------------------------------%</font></div>
<div><font face="courier new, monospace"> </font></div><div><font face="courier new, monospace"> +pqueue.merge(PQ1, PQ2) = PQ3 :-</font></div><div><font face="courier new, monospace"> + pqueue.merge(PQ1, PQ2, PQ3).</font></div>
<div><font face="courier new, monospace"> +</font></div><div><font face="courier new, monospace"> +pqueue.merge(empty, PQ2, PQ2).</font></div><div><font face="courier new, monospace"> +pqueue.merge(PQ1@pqueue(_,_,_,_,_), empty, PQ1).</font></div>
<div><font face="courier new, monospace"> +pqueue.merge(PQ1@pqueue(_,_,_,_,_), pqueue(_,K,V,L,R), PQ3) :-</font></div><div><font face="courier new, monospace"> + pqueue.merge(PQ1, L, IPQ1),</font></div><div><font face="courier new, monospace"> + pqueue.merge(IPQ1, R, IPQ2),</font></div>
<div><font face="courier new, monospace"> + pqueue.insert(K, V, IPQ2, PQ3).</font></div><div><font face="courier new, monospace"> +</font></div><div><font face="courier new, monospace"> +%---------------------------------------------------------------------------%</font></div>
<div><font face="courier new, monospace"> +</font></div><div><font face="courier new, monospace"> pqueue.to_assoc_list(PQ) = AL :-</font></div><div><font face="courier new, monospace"> pqueue.to_assoc_list(PQ, AL).</font></div>
<div><font face="courier new, monospace"> </font></div><div><br></div><div><br></div><div>P.S. The bike shed should be cerulean. ;-)</div><div><br>-- </div>"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."<br>
--Sergey Brin, demonstrating the emptiness of the "don't be evil" mantra.
</div></div>