Anonymous user
Priority queue: Difference between revisions
m
Remove DYNAM compiler option from PROCESS compiler directives leading each program.
imported>Pjfarley3 |
imported>Pjfarley3 m (Remove DYNAM compiler option from PROCESS compiler directives leading each program.) |
||
| (6 intermediate revisions by the same user not shown) | |||
Line 2,260:
1, Solve RC tasks
</pre>
=={{header|Clojure}}==
<syntaxhighlight lang="clojure">user=> (use 'clojure.data.priority-map)
; priority-map can be used as a priority queue
user=> (def p (priority-map "Clear drains" 3, "Feed cat" 4, "Make tea" 5, "Solve RC tasks" 1))
#'user/p
user=> p
{"Solve RC tasks" 1, "Clear drains" 3, "Feed cat" 4, "Make tea" 5}
; You can use assoc or conj to add items
user=> (assoc p "Tax return" 2)
{"Solve RC tasks" 1, "Tax return" 2, "Clear drains" 3, "Feed cat" 4, "Make tea" 5}
; peek to get first item, pop to give you back the priority-map with the first item removed
user=> (peek p)
["Solve RC tasks" 1]
; Merge priority-maps together
user=> (into p [["Wax Car" 4]["Paint Fence" 1]["Sand Floor" 3]])
{"Solve RC tasks" 1, "Paint Fence" 1, "Clear drains" 3, "Sand Floor" 3, "Wax Car" 4, "Feed cat" 4, "Make tea" 5}</syntaxhighlight>
=={{header|CLU}}==
This is a priority queue based on a binary heap. It uses CLU's dynamic
array to store the data.
There are no intrinsic limits on what kind of data can be used for the
priority or the values themselves, except that the priority datatype
must support the less-than operator.
<syntaxhighlight lang="clu">prio_queue = cluster [P, T: type] is new, empty, push, pop
where P has lt: proctype (P,P) returns (bool)
item = struct[prio: P, val: T]
rep = array[item]
new = proc () returns (cvt)
return (rep$create(0))
end new
empty = proc (pq: cvt) returns (bool)
return (rep$empty(pq))
end empty
parent = proc (k: int) returns (int)
return ((k-1)/2)
end parent
left = proc (k: int) returns (int)
return (2*k + 1)
end left
right = proc (k: int) returns (int)
return (2*k + 2)
end right
swap = proc (pq: rep, a: int, b: int)
temp: item := pq[a]
pq[a] := pq[b]
pq[b] := temp
end swap
min_heapify = proc (pq: rep, k: int)
l: int := left(k)
r: int := right(k)
smallest: int := k
if l < rep$size(pq) cand pq[l].prio < pq[smallest].prio then
smallest := l
end
if r < rep$size(pq) cand pq[r].prio < pq[smallest].prio then
smallest := r
end
if smallest ~= k then
swap(pq, k, smallest)
min_heapify(pq, smallest)
end
end min_heapify
push = proc (pq: cvt, prio: P, val: T)
rep$addh(pq, item${prio: prio, val: val})
i: int := rep$high(pq)
while i ~= 0 cand pq[i].prio < pq[parent(i)].prio do
swap(pq, i, parent(i))
i := parent(i)
end
end push
pop = proc (pq: cvt) returns (P, T) signals (empty)
if empty(up(pq)) then signal empty end
if rep$size(pq) = 1 then
i: item := rep$remh(pq)
return (i.prio, i.val)
end
root: item := pq[0]
pq[0] := rep$remh(pq)
min_heapify(pq, 0)
return (root.prio, root.val)
end pop
end prio_queue
start_up = proc ()
% use ints for priority and strings for data
prioq = prio_queue[int,string]
% make the priority queue
pq: prioq := prioq$new()
% add some tasks
prioq$push(pq, 3, "Clear drains")
prioq$push(pq, 4, "Feed cat")
prioq$push(pq, 5, "Make tea")
prioq$push(pq, 1, "Solve RC tasks")
prioq$push(pq, 2, "Tax return")
% print them all out in order
po: stream := stream$primary_output()
while ~prioq$empty(pq) do
prio: int task: string
prio, task := prioq$pop(pq)
stream$putl(po, int$unparse(prio) || ": " || task)
end
end start_up</syntaxhighlight>
{{out}}
<pre>1: Solve RC tasks
2: Tax return
3: Clear drains
4: Feed cat
5: Make tea</pre>
=={{header|COBOL}}==
Line 2,269 ⟶ 2,401:
Note also that each subroutine is declared RECURSIVE though they do not all need it.
The subroutines each pass back a return value in their last parameter. The most recent release of the IBM Enterprise COBOL compiler (V6.4 as of the date of this contribution) does, in fact, support user-defined functions, which would make some of this implementation a little easier to write and read, but since many IBM shops are not yet up to the most recent level, this version is offered as one that will work with down-level compiler versions.
In the "two pass merge" subroutine (PTYQ2PMG), the final three lines are needed because the COBOL CALL statement does not allow for expressions as arguments, so the arguments to the outer call to the "merge" subroutine must be executed first, and the results of those two calls become the arguments to the final "merge" call.
Note also that the subroutines call each other using "PIC X(8)" pseudonyms because the actually recursive subroutines cannot use the "same name" as both the PROGRAM-ID and as a variable name. This could be resolved by simply using "constant" calls (like <code>CALL "PTYQ2PMG" USING . . . </code> but using the pseudonyms allows each of the subroutines to also be separately compiled into an executable module and then dynamically loaded at run time. Many IBM shops will prefer that method to this purely "static" solution.
<syntaxhighlight lang="COBOL">
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQTEST
Line 2,310 ⟶ 2,444:
10 TASK-DOWN POINTER.
05 TASK-NAME PIC X(40).
PROCEDURE DIVISION.
Line 2,368 ⟶ 2,492:
GOBACK.
END PROGRAM PTYQTEST.
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQMERG RECURSIVE.
Line 2,423 ⟶ 2,547:
GOBACK.
END PROGRAM PTYQMERG.
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQ2PMG RECURSIVE.
Line 2,497 ⟶ 2,621:
GOBACK.
END PROGRAM PTYQ2PMG.
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQPUSH RECURSIVE.
Line 2,540 ⟶ 2,664:
GOBACK.
END PROGRAM PTY2PUSH.
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQPOP RECURSIVE.
Line 2,581 ⟶ 2,705:
+0000000006 EAT SCONES.
</pre>
=={{header|CoffeeScript}}==
| |||