Queue

A mutable double-ended queue of elements. The queue has two ends, front and back. Elements can be added and removed at the two ends.

This can be used for different use cases, such as:

Example:

import Queue "Queue";
import Debug "Debug";

persistent actor {
  let orders = Queue.empty<Text>();
  Queue.pushBack(orders, "Antipasta");
  Queue.pushBack(orders, "Spaghetti");
  Queue.pushBack(orders, "Bistecca");
  Queue.pushBack(orders, "Dolce");
  label iteration loop {
    switch (Queue.popFront(orders)) {
      case null { break iteration };
      case (?description) {
        Debug.print(description)
      }
    }
  }
  // prints:
  // `Antipasta`
  // `Spaghetti`
  // `Bistecca`
  // `Dolce`
}

The internal implementation is a doubly-linked list.

Performance:

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

public func toPure<T>(queue : Queue<T>) : PureQueue.Queue<T>

Converts a mutable queue to an immutable, purely functional queue.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  let pureQueue = Queue.toPure<Nat>(queue);
}

Runtime: O(n) Space: O(n) n denotes the number of elements stored in the queue.

public func fromPure<T>(pureQueue : PureQueue.Queue<T>) : Queue<T>

Converts an immutable, purely functional queue to a mutable queue.

Example:

import Queue "mo:base/Queue";
import PureQueue "mo:base/pure/Queue";

persistent actor {
  let pureQueue = PureQueue.fromIter<Nat>([1, 2, 3].values());
  let queue = Queue.fromPure<Nat>(pureQueue);
}

Runtime: O(n) Space: O(n) n denotes the number of elements stored in the queue.

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

Create a new empty mutable double-ended queue.

Example:

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

persistent actor {
  let queue = Queue.empty<Text>();
  Debug.print(Nat.toText(Queue.size(queue))); // prints `0`
}

Runtime: O(1). Space: O(1).

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

Creates a new queue with a single element.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.singleton<Nat>(123);
  assert (Queue.size(queue) == 1);
}

Runtime: O(1) Space: O(1)

public func clear<T>(queue : Queue<T>)

Removes all elements from the queue.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  Queue.clear(queue);
  assert (Queue.isEmpty(queue));
}

Runtime: O(1) Space: O(1)

public func clone<T>(queue : Queue<T>) : Queue<T>

Creates a deep copy of the queue.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let original = Queue.fromIter<Nat>([1, 2, 3].values());
  let copy = Queue.clone(original);
  Queue.clear(original);
  assert (Queue.size(copy) == 3);
}

Runtime: O(n) Space: O(n) n denotes the number of elements stored in the queue.

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

Returns the number of elements in the queue.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.fromIter<Text>(["A", "B", "C"].values());
  assert (Queue.size(queue) == 3);
}

Runtime: O(1) Space: O(1)

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

Returns true if the queue contains no elements.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.empty<Nat>();
  assert (Queue.isEmpty(queue));
}

Runtime: O(1) Space: O(1)

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

Checks if an element exists in the queue using the provided equality function.

Example:

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

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  assert (Queue.contains(queue, Nat.equal, 2));
}

Runtime: O(n) Space: O(1) n denotes the number of elements stored in the queue.

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

Returns the first element in the queue without removing it. Returns null if the queue is empty.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  assert (Queue.peekFront(queue) == ?1);
}

Runtime: O(1) Space: O(1)

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

Returns the last element in the queue without removing it. Returns null if the queue is empty.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  assert (Queue.peekBack(queue) == ?3);
}

Runtime: O(1) Space: O(1)

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

Adds an element to the front of the queue.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.empty<Nat>();
  Queue.pushFront(queue, 1);
  assert (Queue.peekFront(queue) == ?1);
}

Runtime: O(1) Space: O(1)

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

Adds an element to the back of the queue.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.empty<Nat>();
  Queue.pushBack(queue, 1);
  assert (Queue.peekBack(queue) == ?1);
}

Runtime: O(1) Space: O(1)

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

Removes and returns the first element in the queue. Returns null if the queue is empty.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  assert (Queue.popFront(queue) == ?1);
  assert (Queue.size(queue) == 2);
}

Runtime: O(1) Space: O(1)

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

Removes and returns the last element in the queue. Returns null if the queue is empty.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  assert (Queue.popBack(queue) == ?3);
  assert (Queue.size(queue) == 2);
}

Runtime: O(1) Space: O(1)

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

Creates a new queue from an iterator.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.fromIter<Text>(["A", "B", "C"].values());
  assert (Queue.size(queue) == 3);
}

Runtime: O(n) Space: O(n) n denotes the number of elements stored in the queue.

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

Returns an iterator over the elements in the queue. Iterates from front to back.

Example:

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

persistent actor {
  let queue = Queue.fromIter<Text>(["A", "B", "C"].values());
  for (element in Queue.values(queue)) {
    Debug.print(element);
  }
  // prints:
  // `"A"`
  // `"B"`
  // `"C"`
}

Runtime: O(1) for iterator creation, O(n) for full iteration Space: O(1)

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

Tests whether all elements in the queue satisfy the given predicate.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([2, 4, 6].values());
  assert (Queue.all<Nat>(queue, func(x) { x % 2 == 0 }));
}

Runtime: O(n) Space: O(1)

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

Tests whether any element in the queue satisfies the given predicate.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  assert (Queue.any<Nat>(queue, func (x) { x > 2 }));
}

Runtime: O(n) Space: O(1) n denotes the number of elements stored in the queue.

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

Applies the given operation to all elements in the queue.

Example:

import Queue "mo:base/Queue";

persistent actor {
  var sum = 0;
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  Queue.forEach<Nat>(queue, func(x) { sum += x });
  assert (sum == 6);
}

Runtime: O(n) Space: O(1) n denotes the number of elements stored in the queue.

public func map<T, U>(queue : Queue<T>, project : T -> U) : Queue<U>

Creates a new queue by applying the given function to all elements.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  let doubled = Queue.map<Nat, Nat>(queue, func(x) { x * 2 });
  assert (Queue.peekFront(doubled) == ?2);
}

Runtime: O(n) Space: O(n) n denotes the number of elements stored in the queue.

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

Creates a new queue containing only elements that satisfy the given predicate.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3, 4].values());
  let evens = Queue.filter<Nat>(queue, func(x) { x % 2 == 0 });
  assert (Queue.size(evens) == 2);
}

Runtime: O(n) Space: O(n) n denotes the number of elements stored in the queue.

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

Creates a new queue by applying the given function to all elements and keeping only the non-null results.

Example:

import Queue "mo:base/Queue";

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3, 4].values());
  let evenDoubled = Queue.filterMap<Nat, Nat>(
    queue,
    func(x) {
      if (x % 2 == 0) { ?(x * 2) } else  { null }
    }
  );
  assert (Queue.size(evenDoubled) == 2);
}

Runtime: O(n) Space: O(n) n denotes the number of elements stored in the queue.

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

Compares two queues for equality using the provided equality function.

Example:

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

persistent actor {
  let queue1 = Queue.fromIter<Nat>([1, 2, 3].values());
  let queue2 = Queue.fromIter<Nat>([1, 2, 3].values());
  assert (Queue.equal(queue1, queue2, Nat.equal));
}

Runtime: O(n) Space: O(1) n denotes the number of elements stored in the queue.

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

Converts a queue to its string representation using the provided element formatter.

Example:

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

persistent actor {
  let queue = Queue.fromIter<Nat>([1, 2, 3].values());
  assert (Queue.toText(queue, Nat.toText) == "Queue[1, 2, 3]");
}

Runtime: O(n) Space: O(n) n denotes the number of elements stored in the queue.

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

Compares two queues using the provided comparison function. Returns #less, #equal, or #greater.

Example:

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

persistent actor {
  let queue1 = Queue.fromIter<Nat>([1, 2].values());
  let queue2 = Queue.fromIter<Nat>([1, 2, 3].values());
  assert (Queue.compare(queue1, queue2, Nat.compare) == #less);
}

Runtime: O(n) Space: O(1) n denotes the number of elements stored in the queue.