50 lines
1.3 KiB
Plaintext
50 lines
1.3 KiB
Plaintext
# In the following, pq stands for "priority queue".
|
|
|
|
# Add an item with the given priority (an integer,
|
|
# or a string representing an integer)
|
|
# Input: a pq
|
|
def pq_add(priority; item):
|
|
(priority|tostring) as $p
|
|
| if .priorities|index($p) then
|
|
if (.[$p] | index(item)) then . else .[$p] += [item] end
|
|
else .[$p] = [item] | .priorities = (.priorities + [$p] | sort)
|
|
end ;
|
|
|
|
# emit [ item, pq ]
|
|
# Input: a pq
|
|
def pq_pop:
|
|
.priorities as $keys
|
|
| if ($keys|length) == 0 then [ null, . ]
|
|
else
|
|
if (.[$keys[0]] | length) == 1
|
|
then .priorities = .priorities[1:]
|
|
else .
|
|
end
|
|
| [ (.[$keys[0]])[0], (.[$keys[0]] = .[$keys[0]][1:]) ]
|
|
end ;
|
|
|
|
# Emit the item that would be popped, or null if there is none
|
|
# Input: a pq
|
|
def pq_peep:
|
|
.priorities as $keys
|
|
| if ($keys|length) == 0 then null
|
|
else (.[$keys[0]])[0]
|
|
end ;
|
|
|
|
# Add a bunch of tasks, presented as an array of arrays
|
|
# Input: a pq
|
|
def pq_add_tasks(list):
|
|
reduce list[] as $pair (.; . + pq_add( $pair[0]; $pair[1]) ) ;
|
|
|
|
# Pop all the tasks, producing a stream
|
|
# Input: a pq
|
|
def pq_pop_tasks:
|
|
pq_pop as $pair
|
|
| if $pair[0] == null then empty
|
|
else $pair[0], ( $pair[1] | pq_pop_tasks )
|
|
end ;
|
|
|
|
# Input: a bunch of tasks, presented as an array of arrays
|
|
def prioritize:
|
|
. as $list | {} | pq_add_tasks($list) | pq_pop_tasks ;
|