Reference

std/collections/queue

std/collections/src/queue.trb

FIFO: Queue, with ArrayQueue as its only implementation.

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>): Queue<Item>

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>): ArrayQueue<Item>

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.