96 lines
2.4 KiB
Plaintext
96 lines
2.4 KiB
Plaintext
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
|