PriorityQueue

Module std.collections

import std.collections;

Public declaration contracts and authored examples. A page can document several related symbols. Implementation bodies are excluded.

PriorityQueue

pub final class PriorityQueue<T, C = PriorityComparison<T>, A = DefaultAllocator>
    where T: Movable, MoveAssignable
    where C: BinaryCallable<readonly T&, readonly T&, i32>, Movable
    where A: Allocator, Defaultable, Movable

Owns an allocator-aware binary heap and one safe comparison policy.

Positive comparison ranks the first element higher. Ties are unstable. Insertion/removal perform O(log n) comparisons and safe lifecycle moves; growth additionally moves O(n) items. Empty construction allocates nothing. Peek is readonly: writable element access could destroy the heap invariant. Every mutation, move or destruction invalidates borrowed views and cursors. External synchronization is required; captured policy backing must remain live. Moved-from queues are empty and destructible. Insertion into a moved-from queue requires its moved-from policy to support invocation; assigning a new queue replaces that policy and its storage together. T: Movable and MoveAssignable element type. C: Owned safe readonly comparator, defaulting to a stored safe function. A: Allocator owner, defaulting to DefaultAllocator.

Example

module example.priority_queue;
from std.collections import CreatePriorityQueue, PriorityComparison;
from std.memory import DefaultAllocator;
fn Compare(Left: readonly i32&, Right: readonly i32&) -> i32 {
    if Left < Right { return -1; }
    if Left > Right { return 1; }
    return 0;
}
fn Main() -> i32 {
    let Policy = PriorityComparison<i32>(Compare);
    var DefaultQueue = CreatePriorityQueue<i32>(Policy);
    var FunctionQueue = CreatePriorityQueue<i32>(Compare);
    if !DefaultQueue.IsEmpty || !FunctionQueue.IsEmpty { return 1; }
    var Queue = CreatePriorityQueue<i32>(Compare, default(DefaultAllocator));
    if !Queue.IsEmpty { return 1; }
    if Queue.Peek() is .Some { Value = _ } { return 1; }
    if Queue.TryReserve(4) is .Err { Error = _ } { return 2; }
    if Queue.TryPush(20) is .Err { Error = _ } { return 3; }
    if Queue.TryPush(42) is .Err { Error = _ } { return 4; }
    if Queue.TryPush(2) is .Err { Error = _ } { return 5; }
    {
        let Highest = Queue.Peek();
        if Highest is .None || Highest.Unwrap() != 42 { return 6; }
        var Cursor = Queue.CreateIterator();
        var Sum: i32 = 0;
        while Cursor.Next() is .Some { Value = Item } { Sum += Item; }
        if Sum != 64 { return 7; }
    }
    if Queue.Pop().Unwrap() != 42 { return 8; }
    var Moved = move(Queue);
    if !Queue.IsEmpty || Moved.Length != 2 { return 9; }
    Queue = move(Moved);
    if !Moved.IsEmpty || Queue.Pop().Unwrap() != 20 { return 10; }
    if Queue.Pop().Unwrap() != 2 { return 11; }
    if Queue.Pop() is .Some { Value = _ } { return 11; }
    Queue.Clear();
    if Queue.TryShrinkToFit() is .Err { Error = _ } { return 12; }
    return 0;
}

PriorityQueue.init

pub init(mut Compare: C)

Creates an empty queue by transferring its comparison policy. Compare: Concrete safe policy, moved into queue storage.

PriorityQueue.init

pub init(mut Compare: C, mut AllocatorValue: A)

Creates an empty queue with explicit policy and allocator owners. Compare: Safe policy moved into queue storage. AllocatorValue: Allocator moved into contiguous heap storage.

PriorityQueue.init

pub init(Source: readonly Self&) = delete;

Rejects copying heap ownership. Source: Noncopy source.

PriorityQueue.init

pub init(Source: mut Self&&)

Transfers heap storage and policy, leaving the source empty. Source: Writable queue whose allocator, elements and policy are moved.

PriorityQueue.operator

pub fn operator =(Source: readonly Self&) -> void = delete;

Rejects copying into live heap ownership. Source: Noncopy source. Return: No value; deleted.

PriorityQueue.operator

pub fn operator =(Source: mut Self&&) -> void

Releases previous storage and transfers heap and policy ownership. Source: Writable queue left empty; exact self-assignment is unchanged. Return: No value; old policy and storage are deterministically released.

PriorityQueue.Length

pub Length: usize;

Observes live heap length in O(1).

PriorityQueue.IsEmpty

pub IsEmpty: bool;

Observes emptiness in O(1).

PriorityQueue.TryReserve

pub fn TryReserve(MinimumCapacity: usize) -> Result<void, AllocationError>

Reserves raw heap capacity without changing ordering or length. MinimumCapacity: Desired item capacity. Return: Ok or AllocationError; failure preserves items and their ordering. Warning: May allocate and relocate O(n) elements; invalidates borrowed views on relocation.

PriorityQueue.TryPush

pub fn TryPush(mut Item: T) -> Result<void, VectorInsertionError<T>>

Inserts one owned item and restores the heap in O(log n). Item: Value transferred on success and returned in the error on failure. Return: Ok, or failure owning the original Item with unchanged logical heap. Warning: May allocate; invalidates borrowed views. Comparator/lifecycle traps have no rollback.

PriorityQueue.Peek

pub readonly fn Peek() -> readonly T&?

Borrows the highest-priority item without modifying heap order. Return: Optional readonly reference, or none when empty; no allocation. Warning: Borrow is invalidated by mutation, move or destruction. Writable root access is unavailable.

PriorityQueue.Pop

pub fn Pop() -> T?

Removes the highest-priority item and restores order in O(log n). Return: Owned item, or none when empty; no allocation. Warning: Invalidates borrowed views; comparator/lifecycle traps have no rollback.

PriorityQueue.CreateIterator

pub readonly fn CreateIterator() -> SliceIterator<T>

Borrows elements for readonly iteration in heap-storage order. Return: Allocation-free cursor; this order is not a sorted traversal. Warning: Mutation, move or destruction invalidates every cursor/reference.

PriorityQueue.Clear

pub fn Clear() -> void

Destroys all live items while retaining the policy and capacity. Return: No value; invalidates borrowed views and allocates nothing.

PriorityQueue.TryShrinkToFit

pub fn TryShrinkToFit() -> Result<void, AllocationError>

Releases excess capacity without changing ordering. Return: Ok or AllocationError; failure preserves logical contents. Warning: May allocate and relocate O(n) elements; invalidates borrowed views on relocation.