NAME

prioq — Priority queue.

synopsis

::wyrm::prioq new [ [ -id task-id ] priority task ] ...

::wyrm::vprioq new queue-variable [ [ -id task-id ] priority task ] ...

::wyrm::prioq empty queue

::wyrm::vprioq empty queue-variable

::wyrm::prioq task queue

::wyrm::vprioq task queue-variable

::wyrm::prioq enqueue|enqueuebefore queue [ -id task-id ] [ priority ] task

::wyrm::vprioq enqueue|enqueuebefore queue-variable [ -id task-id ] [ priority ] task

::wyrm::prioq dequeue queue task-variable [ existsvar ]

::wyrm::vprioq dequeue queue-variable task-variable [ existsvar ]

description

Splay trees are the most efficient way to implement priority queues as well as a general self-organising tree. To simplify using a splay tree as a priority queue, these additional interfaces are added to sort on priorities and to allow multiple nodes with the same priority. These splay trees are associative maps and priority queues. The prioq manipulates them as queues, and assoc as mappings. The enqueued task is a string which is interpretted by the caller; it is the same as the mapping data.

The priorities are recorded as keys but they are marked such that tasks cannot be sought. A list of all queued tasks can be is returned by prioq task.

Task are queued according to their priority. If the priority is not specified, it is assumed to be zero; priorities can be any integer, positive, negative or zero. A task can be added before or after all other tasks with the same priority.

A task can also be given an id; only one task with a particular id will be added to the queue; subsequent attempts to enqueue the same task id will be silently ignored: these are do once (with respect to the queue) tasks. A task does not have to have an id, in which case in can be enqueued as often as desired. The task id is any string which is unique for each task.

prioq will not modify the given queue, but return a new queue for prioq enqueue, prioq enqueuebefore, and prioq dequeue. vprioq is given the name of a variable holding the queue, and it will modify the variable value, whether it shared or not.

wyrm::prioq new
Create a new priority queue and initialise it with some tasks, their priorities, and optional ids. (Actually to initialize an empty queue, it suffices to start with an empty list.)
wyrm::prioq empty
Return true if the queue has no more tasks. It may still have some other mappings.
wyrm::prioq task
Return a list of each queued task proceeded by its priority.
wyrm::prioq enqueue
Add the task to the queue. If the priority is omitted, the priority is zero. If the task-id is given and a previous task had used the same id, the enqueue is ignored: the task is not added again, whether it has yet been dequeued or no. The new queue is returned.
wyrm::prioq enqueuebefore
Add the task to the queue. If the priority is omitted, the priority is zero. The task is added before all other tasks queued with the same priority. If the task-id is given and a previous task had used the same id, the enqueue is ignored: the task is not added again, whether it has yet been dequeued or no. The new queue is returned.
wyrm::prioq dequeue
Return the queue with the least priority task removed; if the queue is empty, and the existsvar is omitted, an error is returned. If the existsvar is specified, it is set to whether the queue existed (was nonempty) when called; dequeueing an empty queue with existsvar is not an error. The task with the least priority is assigned to task-variable and removed from the queue. Non-queue mappings are ignored.

SEE ALSO

assoc (1WY).