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.
  • comparator has stack effect (item0 item1 -- cond), receives immutable views of two items, and returns TRUE when item0 is less than item1. 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

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, or Index 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


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

See also