Reference

std/collections/queue

std/collections/src/queue.trb

FIFO: Queue, with ArrayQueue as its default implementation and BankersQueue for a queue kept in many versions.

enqueue puts an item at the back, dequeue takes the one at the front, and peek looks at the front without taking it. There is no index: the only way to see an item behind the front is to dequeue up to it or to iterate the whole queue.

Related

trait Queue

trait Queue<Item> with Iterate<Item>, Length

FIFO queue. Iterates from front to back, which is the order it hands items out in.

The words everybody knows for a queue: enqueue puts an item at the back, dequeue takes the one at the front off, and peek looks at the front without taking it.

Examples

var pending = Queue.of 1, 2, 3
pending.enqueue 4
print pending.dequeue()
print pending.peek()
print pending.toList()

Related

  • Stack - the LIFO sibling.
  • Iterate - the pipeline vocabulary (map, filter, fold, ...), from the front to the back.

fn of

static fn of(...items: Item): Self where Self: From<Iterate<Item>>

Builds a queue from its arguments. The first item ends up at the front. Answers Self.

fn enqueue

var fn enqueue(value: Item)

Puts value at the back, in place.

fn dequeue

var fn dequeue(): Item?

Takes the item at the front off and answers it, or None if the queue is empty.

fn clear

var fn clear()

Removes every item, in place.

fn compact

var fn compact()

Hands back storage held beyond the length. The default does nothing: a storage without spare room has none.

fn peek

fn peek(): Item?

The item dequeue would take, without taking it, or None if the queue is empty.

fn count

fn count(): Int

How many items there are. A queue knows its size, so counting it does not walk it.

extend Queue<Item> with From<Iterate<Item>>

extend<Item> Queue<Item> with From<Iterate<Item>>

The factory picks the default implementation: what Queue.of and a pipeline's to<Queue<Item>>() build.

fn from

static fn from(items: Iterate<Item>): Self

extend Queue<Item> with Equals

extend<Item: Equals> Queue<Item> with Equals

Equal when they hold the same items in the same order, which for a queue is the order of dequeue.

A collection is Equals when its items are, exactly as a tuple is: values compare structurally, and which implementation carries the items is nobody's business.

fn equals

fn equals(other: Self): Bool

extend Queue<Item> with Hash

extend<Item: Hash> Queue<Item> with Hash

Order-dependent, like List.hash and unlike Set.hash: two queues with the same items in a different order are not equal, so they need not hash alike.

Hash requires Equals, and the Equals implementation above satisfies that: Item: Hash implies Item: Equals.

fn hash

fn hash(): Int

type ArrayQueue

type ArrayQueue<Item> with Queue<Item>, From<Iterate<Item>>

Ring buffer on top of a List. An empty queue holds no slots at all; the first enqueue makes 16 of them, and a full buffer doubles. Nothing is moved and nothing is allocated between two of those steps.

fn from

static fn from(items: Iterate<Item>): Self

Builds the queue from items, with the first one at the front.

fn enqueue

var fn enqueue(value: Item)

Puts value at the back, in place; grows the buffer first if it is full.

fn dequeue

var fn dequeue(): Item?

Takes the item at the front off and answers it, or None if empty.

fn peek

fn peek(): Item?

The item at the front, or None if empty: one slot, without walking the ring.

fn clear

var fn clear()

Removes every item, in place, and gives the slots back.

fn length

fn length(): Int

How many items there are.

fn iterate

fn iterate(): Iterator<Item>

A cursor from front to back: the order the queue hands items out in.

fn compact

var fn compact()

Shrinks the ring to the items it holds, to no slots at all when it is empty; see Queue.compact.

type BankersQueue

type BankersQueue<Item> with Queue<Item>, From<Iterate<Item>>

A persistent queue: two cons lists, the front in the order dequeue hands items out and the rear reversed, so an enqueue is one new node in front of the rear. Copies share their nodes and an operation allocates or releases one node, so a copy is O(1) and a queue kept in many versions costs what the versions differ by, where ArrayQueue copies its whole ring on the first write.

enqueue and peek are O(1). dequeue is O(1) except for the one that finds the front empty: that reverses the rear into the front, once for every item it holds, so a run of operations on one queue is amortised O(1). The queue keeps its front non-empty whenever it holds anything, which is what lets peek answer without walking. iterate and toList are O(n), and length is a field.

The amortised bound is for one history: a version that is dequeued from twice reverses the shared rear twice, which is the price of persistence without laziness. A queue that is never copied is better in an ArrayQueue.

Examples

var pending = BankersQueue.of 1, 2, 3
const before = pending
pending.enqueue 4
print pending.dequeue()
print before.toList()

fn from

static fn from(items: Iterate<Item>): Self

Builds the queue from items, with the first one at the front.

fn enqueue

var fn enqueue(value: Item)

Puts value at the back, in place: one node, on the front when the queue is empty and on the rear otherwise.

fn dequeue

var fn dequeue(): Item?

Takes the item at the front off and answers it, or None if empty. Reverses the rear when the front runs out.

fn peek

fn peek(): Item?

The item at the front, or None if empty: the front is never empty while there are items.

fn clear

var fn clear()

Removes every item, in place.

fn length

fn length(): Int

How many items there are.

fn iterate

fn iterate(): Iterator<Item>

A cursor from front to back: the front as it is, then the rear from its far end.