pure/Queue

type Queue<T> = Types.Pure.Queue<T>

Double-ended queue data type.

public func empty<T>() : Queue<T>

Create a new empty queue.

Example:

import Queue "mo:base/Queue";

Queue.empty<Nat>()

Runtime: O(1).

Space: O(1).

public func isEmpty<T>(queue : Queue<T>) : Bool

Determine whether a queue is empty. Returns true if queue is empty, otherwise false.

Example:

import Queue "mo:base/Queue";

let queue = Queue.empty<Nat>();
Queue.isEmpty(queue) // => true

Runtime: O(1).

Space: O(1).

public func singleton<T>(item : T) : Queue<T>

Create a new queue comprising a single element.

Example:

import Queue "mo:base/Queue";

Queue.singleton<Nat>(25)

Runtime: O(1).

Space: O(1).

public func size<T>(queue : Queue<T>) : Nat

Determine the number of elements contained in a queue.

Example:

import {singleton, size} "mo:base/Queue";

let queue = singleton<Nat>(42);
size(queue) // => 1

Runtime: O(1).

Space: O(1).

public func contains<T>(
  queue : Queue<T>,
  equal : (T, T) -> Bool,
  item : T
) : Bool

public func peekFront<T>(queue : Queue<T>) : ?T

Inspect the optional element on the front end of a queue. Returns null if queue is empty. Otherwise, the front element of queue.

Example:

import Queue "mo:base/Queue";

let queue = Queue.pushFront(Queue.pushFront(Queue.empty<Nat>(), 2), 1);
Queue.peekFront(queue) // => ?1

Runtime: O(1).

Space: O(1).

public func peekBack<T>(queue : Queue<T>) : ?T

Inspect the optional element on the back end of a queue. Returns null if queue is empty. Otherwise, the back element of queue.

Example:

import Queue "mo:base/Queue";

let queue = Queue.pushBack(Queue.pushBack(Queue.empty<Nat>(), 1), 2);
Queue.peekBack(queue) // => ?2

Runtime: O(1).

Space: O(1).

public func pushFront<T>(queue : Queue<T>, element : T) : Queue<T>

Insert a new element on the front end of a queue. Returns the new queue with element in the front followed by the elements of queue.

This may involve dynamic rebalancing of the two, internally used lists.

Example:

import Queue "mo:base/Queue";

Queue.pushFront(Queue.pushFront(Queue.empty<Nat>(), 2), 1) // queue with elements [1, 2]

Runtime: O(n) worst-case, amortized to O(1).

Space: O(n) worst-case, amortized to O(1).

n denotes the number of elements stored in the queue.

public func pushBack<T>(queue : Queue<T>, element : T) : Queue<T>

Insert a new element on the back end of a queue. Returns the new queue with all the elements of queue, followed by element on the back.

This may involve dynamic rebalancing of the two, internally used lists.

Example:

import Queue "mo:base/Queue";

Queue.pushBack(Queue.pushBack(Queue.empty<Nat>(), 1), 2) // queue with elements [1, 2]

Runtime: O(n) worst-case, amortized to O(1).

Space: O(n) worst-case, amortized to O(1).

n denotes the number of elements stored in the queue.

public func popFront<T>(queue : Queue<T>) : ?(T, Queue<T>)

Remove the element on the front end of a queue. Returns null if queue is empty. Otherwise, it returns a pair of the first element and a new queue that contains all the remaining elements of queue.

This may involve dynamic rebalancing of the two, internally used lists.

Example:

import Queue "mo:base/Queue";
import Debug "mo:base/Debug";
let initial = Queue.pushFront(Queue.pushFront(Queue.empty<Nat>(), 2), 1);
// initial queue with elements [1, 2]
let reduced = Queue.popFront(initial);
switch reduced {
  case null {
    Debug.trap "Empty queue impossible"
  };
  case (?result) {
    let removedElement = result.0; // 1
    let reducedQueue = result.1; // queue with element [2].
  }
}

Runtime: O(n) worst-case, amortized to O(1).

Space: O(n) worst-case, amortized to O(1).

n denotes the number of elements stored in the queue.

public func popBack<T>(queue : Queue<T>) : ?(Queue<T>, T)

Remove the element on the back end of a queue. Returns null if queue is empty. Otherwise, it returns a pair of a new queue that contains the remaining elements of queue and, as the second pair item, the removed back element.

This may involve dynamic rebalancing of the two, internally used lists.

Example:

import Queue "mo:base/Queue";
import Debug "mo:base/Debug";

let initial = Queue.pushBack(Queue.pushBack(Queue.empty<Nat>(), 1), 2);
// initial queue with elements [1, 2]
let reduced = Queue.popBack(initial);
switch reduced {
  case null {
    Debug.trap "Empty queue impossible"
  };
  case (?result) {
    let reducedQueue = result.0; // queue with element [1].
    let removedElement = result.1; // 2
  }
}

Runtime: O(n) worst-case, amortized to O(1).

Space: O(n) worst-case, amortized to O(1).

n denotes the number of elements stored in the queue.

public func fromIter<T>(iter : Iter.Iter<T>) : Queue<T>

Turn an iterator into a queue, consuming it. Example:

motoko include=initialize
Queue.fromIter<Nat>([0, 1, 2, 3, 4].values())
// => (?(0, ?(1, null)), 5, ?(4, ?(3, ?(2, null))))

Runtime: O(size)

Space: O(size)

public func values<T>(queue : Queue<T>) : Iter.Iter<T>

public func equal<T>(
  queue1 : Queue<T>,
  queue2 : Queue<T>,
  equal : (T, T) -> Bool
) : Bool

public func all<T>(queue : Queue<T>, predicate : T -> Bool) : Bool

Return true if the given predicate f is true for all queue elements.

Example:

motoko include=initialize

Queue.all<Nat>(
  (?(1, ?(2, ?(3, null))), 3, null),
  func n = n > 1
); // => false

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that f runs in O(1) time and space.

public func any<T>(queue : Queue<T>, predicate : T -> Bool) : Bool

Return true if there exists a queue element for which the given predicate f is true.

Example:

motoko include=initialize

Queue.any<Nat>(
  (null, 3, ?(1, ?(2, ?(3, null)))),
  func n = n > 1
) // => true

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that f runs in O(1) time and space.

public func forEach<T>(queue : Queue<T>, f : T -> ())

Call the given function for its side effect, with each queue element in turn.

Example:

motoko include=initialize
var sum = 0;
Queue.forEach<Nat>((?(0, ?(1, ?(2, null))), 3, null), func n = sum += n);
sum // => 3

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that f runs in O(1) time and space.

public func map<T1, T2>(queue : Queue<T1>, f : T1 -> T2) : Queue<T2>

Call the given function f on each queue element and collect the results in a new queue.

Example:

motoko include=initialize
import Nat = "mo:base/Nat"
Queue.map<Nat, Text>(Queue.fromIter([0, 1, 2].values()), Nat.toText) // => (?("0", null), 3, ?("2", ?("1", null)))

Runtime: O(size)

Space: O(size) *Runtime and space assumes that f runs in O(1) time and space.

public func filter<T>(queue : Queue<T>, f : T -> Bool) : Queue<T>

Create a new queue with only those elements of the original queue for which the given function (often called the predicate) returns true.

Example:

motoko include=initialize
Queue.filter<Nat>((?(0, ?(1, ?(2, null))), 4, ?(1, null)), func n = n != 1) // => ?(0, ?(2, null))

Runtime: O(size)

Space: O(size)

public func filterMap<T, U>(queue : Queue<T>, f : T -> ?U) : Queue<U>

Call the given function on each queue element, and collect the non-null results in a new queue.

Example:

motoko include=initialize
Queue.filterMap<Nat, Nat>(
  (?(1, ?(2, ?(3, null))), 3, null)
  func n = if (n > 1) ?(n * 2) else null
) // => (?(4, null), 2, ?(6, null))

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that f runs in O(1) time and space.

public func toText<T>(queue : Queue<T>, f : T -> Text) : Text

public func compare<T>(
  queue1 : Queue<T>,
  queue2 : Queue<T>,
  compareItem : (T, T) -> Order.Order
) : Order.Order

Compare two queues using lexicographic ordering specified by argument function compareItem.

Example:

motoko include=initialize
import Nat "mo:base/Nat";

Queue.compare<Nat>(
  (?(1, ?(2, null)), 2, null),
  (null, 2, ?(2, ?(1, null))),
  Nat.compare
) // => #equal

Runtime: O(size(l1))

Space: O(1)

*Runtime and space assumes that argument compare runs in O(1) time and space.