Priority queue over comparable items with heap-style insertion, top-element access, and removal.
PriorityQueue
PriorityQueue
(Item comparator -- queue) Creates an empty priority queue using the schema of Item, ordered by comparator.- The element schema must be a non-Meta In-place schema supported by Array and permit default initialization for insertion. For an existing prototype, supply a mutable view; an immutable prototype makes insertion fail. Direct Text and Code elements are unsupported; wrap them in an In-place Struct when needed.
comparatorhas stack effect(item0 item1 -- cond), receives immutable views of two items, and returnsTRUEwhenitem0is less thanitem1. The queue keeps it, so queues with comparator Blocks written in different places, such as two[<], have different schemas.
Known issue: the queue calls a comparator Block as one of its methods, so the queue's names, such as data, swap, comparator and self, hide those the comparator would otherwise see: [swap <] fails to compile, and a comparator that reads a local named data reads the queue's backing array instead. Avoid the queue's names in every Block of the comparator's module processed during its call; for example, write [x: y:;; y x <] instead of [swap <].
- The queue owns its backing array. Copying copies the backing array's items when their schema is copyable. Moving transfers the array and leaves the source empty. Destruction destroys remaining items and releases the allocation.
Fields
data: backing array containing the heap elements.
Methods
swap
(ordinal0 ordinal1 --) Swaps two backing-array positions.- Both ordinals must identify existing elements. Out-of-range access reports
Index is out of range!when checked. This low-level operation exchanges slots without repairing heap order.
parent
(ordinal -- parentOrdinal) Returns the parent ordinal for one heap ordinal.- Ordinal 0 has no parent; the formula returns 0 there. Other inputs use (ordinal - 1) / 2. The arithmetic does not check whether the computed parent exists.
lchild
(ordinal -- childOrdinal) Returns the left-child ordinal.- The formula is ordinal * 2 + 1. The arithmetic does not check whether the computed child exists.
rchild
(ordinal -- childOrdinal) Returns the right-child ordinal.- The formula is ordinal * 2 + 2. The arithmetic does not check whether the computed child exists.
lift
(ordinal --) Moves one item upward while it is greater than its parent.- Requires an existing ordinal; out-of-range access reports
Index is out of range!when checked. Repairs only an upward violation, and does not repair an item lowered beneath its children.
push
(item --) Appends one item and restores the heap ordering upward.- An immutable item view is copied; a mutable item view is moved. The item schema must support the selected transfer.
- Supply exactly one Item.
- If insertion can grow the backing allocation referenced by the input, copy or move the item to a separate object before insertion. See the Array.append known-issue note.
Known issue: with [<], aggregate input (1 100 2) @q.push leaves top 2 because only the last element is lifted; insert items one at a time.
top
(-- ref) Returns a reference to the greatest current item.- The reference is mutable through a mutable receiver and immutable through an immutable receiver; push, pop, swap, lift, and growth can move items. A nonempty queue is required; an empty queue reports
Index is out of range!when checked.
pop
(--) Removes and destroys the greatest item without returning it.- A nonempty queue is required; an empty queue reports
Pop from empty array!when checked, orIndex is out of range!at compile time when known to be empty.
getSize
(-- count) Returns the number of queued items.empty
(-- cond) Reports whether the queue contains no items.Ordering and empty state
- The greatest item according to the comparator is at
top;[<]resolves<where push, pop and lift process it, within the module where it is written (see Block and Code), and[>]puts the smallest item attop. Do not change an ordering key through a returned reference without separately restoring the heap invariant; writes do not automatically reorder the queue. - No stable order is guaranteed among equal items.
- Ordinals are
Int32values. Slot access requires0 <= ordinal < size; out-of-range access reportsIndex is out of range!when checked. - Run-time checks require DEBUG; disabling DEBUG does not make an invalid operation safe.
- Known violations of these assertions are rejected at compile time even with DEBUG disabled.
Examples
Runtime example: empty state, size, top, and pop
"PriorityQueue" use
"String" use
"control" use
{} Int32 {} [
q: Int32 [<] PriorityQueue;
("empty0=" q.empty LF) printList
10 @q.push
3 @q.push
20 @q.push
("size=" q.getSize LF
"top=" @q.top new LF
"empty1=" q.empty LF) printList
@q.pop
("top=" @q.top new LF) printList
0
] "main" exportFunction
Expected Output
empty0=TRUE
size=3
top=20
empty1=FALSE
top=10