core/pure/RealTimeQueue
Double-ended immutable queue with guaranteed O(1) push/pop operations (caveat: high constant factor).
For a default immutable queue implementation, see pure/Queue.
This module provides an alternative implementation with better worst-case performance for single operations, e.g. pushBack and popFront.
These operations are always constant time, O(1), which eliminates spikes in performance of pure/Queue operations
that are caused by the amortized nature of the pure/Queue implementation, which can lead to O(n) worst-case performance for a single operation.
The spikes in performance can cause a single message to take multiple more rounds to complete than most other messages.
However, the O(1) operations come at a cost of higher constant factor than the pure/Queue implementation:
- 'pop' operations are on average 3x more expensive
- 'push' operations are on average 8x more expensive
For better performance across multiple operations and when the spikes in single operations are not a problem, use pure/Queue.
For guaranteed O(1) operations, use pure/RealTimeQueue.
The interface is purely functional, not imperative, and queues are immutable values. In particular, Queue operations such as push and pop do not update their input queue but, instead, return the value of the modified Queue, alongside any other data. The input queue is left unchanged.
Examples of use-cases:
- Queue (FIFO) by using
pushBack()andpopFront(). - Stack (LIFO) by using
pushFront()andpopFront(). - Deque (double-ended queue) by using any combination of push/pop operations on either end.
A Queue is internally implemented as a real-time double-ended queue based on the paper
"Real-Time Double-Ended Queue Verified (Proof Pearl)". The implementation maintains
worst-case constant time O(1) for push/pop operations through gradual rebalancing steps.
Construction: Create a new queue with the empty<T>() function.
Note that some operations that traverse the elements of the queue (e.g. forEach, values) preserve the order of the elements,
whereas others (e.g. map, contains) do NOT guarantee that the elements are visited in any order.
The order is undefined to avoid allocations, making these operations more efficient.
import Queue "mo:core/pure/RealTimeQueue";
Type Queue
type Queue<T> = {#empty; #one : T; #two : (T, T); #three : (T, T, T); #idles : (Idle<T>, Idle<T>); #rebal : States<T>}
The real-time queue data structure can be in one of the following states:
#empty: the queue is empty#one: the queue contains a single element#two: the queue contains two elements#three: the queue contains three elements#idles: the queue is in the idle state, wherelandrare non-empty stacks of elements fulfilling the size invariant#rebal: the queue is in the rebalancing state
Function empty
func empty<T>() : Queue<T>
Create a new empty queue.
Example:
persistent actor {
let queue = Queue.empty<Nat>();
assert Queue.isEmpty(queue);
}
Runtime: O(1).
Space: O(1).
Function isEmpty
func isEmpty<T>(queue : Queue<T>) : Bool
Determine whether a queue is empty.
Returns true if queue is empty, otherwise false.
Example:
persistent actor {
let queue = Queue.empty<Nat>();
assert Queue.isEmpty(queue);
}
Runtime: O(1).
Space: O(1).
Function singleton
func singleton<T>(element : T) : Queue<T>
Create a new queue comprising a single element.
Example:
persistent actor {
let queue = Queue.singleton<Nat>(25);
assert Queue.size(queue) == 1;
assert Queue.peekFront(queue) == ?25;
}
Runtime: O(1).
Space: O(1).
Function size
func size<T>(queue : Queue<T>) : Nat
Determine the number of elements contained in a queue.
Example:
persistent actor {
let queue = Queue.singleton<Nat>(42);
assert Queue.size(queue) == 1;
}
Runtime: O(1).
Space: O(1).
Function contains
func contains<T>(queue : Queue<T>, eq : (T, T) -> Bool, item : T) : Bool
Test if a queue contains a given value. Returns true if the queue contains the item, otherwise false.
Note: The order in which elements are visited is undefined, for performance reasons.
Example:
import Nat "mo:core/Nat";
persistent actor {
let queue = Queue.pushBack(Queue.pushBack(Queue.empty<Nat>(), 1), 2);
assert Queue.contains(queue, Nat.equal, 1);
assert not Queue.contains(queue, Nat.equal, 3);
}
Runtime: O(size)
Space: O(1)
Function peekFront
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:
persistent actor {
let queue = Queue.pushFront(Queue.pushFront(Queue.empty<Nat>(), 2), 1);
assert Queue.peekFront(queue) == ?1;
}
Runtime: O(1).
Space: O(1).
Function peekBack
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:
persistent actor {
let queue = Queue.pushFront(Queue.pushFront(Queue.empty<Nat>(), 2), 1);
assert Queue.peekBack(queue) == ?2;
}
Runtime: O(1).
Space: O(1).
Function pushFront
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.
Example:
persistent actor {
let queue = Queue.pushFront(Queue.pushFront(Queue.empty<Nat>(), 2), 1);
assert Queue.peekFront(queue) == ?1;
assert Queue.peekBack(queue) == ?2;
assert Queue.size(queue) == 2;
}
Runtime: O(1) worst-case!
Space: O(1) worst-case!
Function pushBack
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.
Example:
persistent actor {
let queue = Queue.pushBack(Queue.pushBack(Queue.empty<Nat>(), 1), 2);
assert Queue.peekBack(queue) == ?2;
assert Queue.size(queue) == 2;
}
Runtime: O(1) worst-case!
Space: O(1) worst-case!
Function popFront
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.
Example:
import Runtime "mo:core/Runtime";
persistent actor {
do {
let initial = Queue.pushBack(Queue.pushBack(Queue.empty<Nat>(), 1), 2);
let ?(frontElement, remainingQueue) = Queue.popFront(initial) else Runtime.trap "Empty queue impossible";
assert frontElement == 1;
assert Queue.size(remainingQueue) == 1;
}
}
Runtime: O(1) worst-case!
Space: O(1) worst-case!
Function popBack
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.
Example:
import Runtime "mo:core/Runtime";
persistent actor {
do {
let initial = Queue.pushBack(Queue.pushBack(Queue.empty<Nat>(), 1), 2);
let ?(reducedQueue, removedElement) = Queue.popBack(initial) else Runtime.trap "Empty queue impossible";
assert removedElement == 2;
assert Queue.size(reducedQueue) == 1;
}
}
Runtime: O(1) worst-case!
Space: O(1) worst-case!
Function fromIter
func fromIter<T>(iter : Iter<T>) : Queue<T>
Turn an iterator into a queue, consuming it.
Example:
persistent actor {
let queue = Queue.fromIter<Nat>([0, 1, 2, 3, 4].values());
assert Queue.peekFront(queue) == ?0;
assert Queue.peekBack(queue) == ?4;
assert Queue.size(queue) == 5;
}
Runtime: O(size)
Space: O(size)
Function values
func values<T>(queue : Queue<T>) : Iter.Iter<T>
Create an iterator over the elements in the queue. The order of the elements is from front to back.
Example:
import Iter "mo:core/Iter";
persistent actor {
let queue = Queue.fromIter<Nat>([1, 2, 3].values());
assert Iter.toArray(Queue.values(queue)) == [1, 2, 3];
}
Runtime: O(1) to create the iterator and for each next() call.
Space: O(1) to create the iterator and for each next() call.
Function equal
func equal<T>(queue1 : Queue<T>, queue2 : Queue<T>, equality : (T, T) -> Bool) : Bool
Compare two queues for equality using a provided equality function to compare their elements. Two queues are considered equal if they contain the same elements in the same order.
Example:
import Nat "mo:core/Nat";
persistent actor {
let queue1 = Queue.fromIter<Nat>([1, 2, 3].values());
let queue2 = Queue.fromIter<Nat>([1, 2, 3].values());
let queue3 = Queue.fromIter<Nat>([1, 3, 2].values());
assert Queue.equal(queue1, queue2, Nat.equal);
assert not Queue.equal(queue1, queue3, Nat.equal);
}
Runtime: O(size)
Space: O(size)
Function compare
func compare<T>(queue1 : Queue<T>, queue2 : Queue<T>, comparison : (T, T) -> Types.Order) : Types.Order
Compare two queues lexicographically using a provided comparison function to compare their elements.
Returns #less if queue1 is lexicographically less than queue2, #equal if they are equal, and #greater otherwise.
Example:
import Nat "mo:core/Nat";
persistent actor {
let queue1 = Queue.fromIter<Nat>([1, 2, 3].values());
let queue2 = Queue.fromIter<Nat>([1, 2, 4].values());
assert Queue.compare(queue1, queue2, Nat.compare) == #less;
}
Runtime: O(size)
Space: O(size)
Function all
func all<T>(queue : Queue<T>, predicate : T -> Bool) : Bool
Return true if the given predicate is true for all queue elements.
Example:
persistent actor {
let queue = Queue.fromIter<Nat>([2, 4, 6].values());
assert Queue.all<Nat>(queue, func n = n % 2 == 0);
assert not Queue.all<Nat>(queue, func n = n > 4);
}
Runtime: O(size)
Space: O(size) as the current implementation uses values to iterate over the queue.
*Runtime and space assumes that the predicate runs in O(1) time and space.
Function any
func any<T>(queue : Queue<T>, predicate : T -> Bool) : Bool
Return true if the given predicate is true for any queue element.
Example:
persistent actor {
let queue = Queue.fromIter<Nat>([1, 2, 3].values());
assert Queue.any<Nat>(queue, func n = n > 2);
assert not Queue.any<Nat>(queue, func n = n > 3);
}
Runtime: O(size)
Space: O(size) as the current implementation uses values to iterate over the queue.
*Runtime and space assumes that the predicate runs in O(1) time and space.
Function forEach
func forEach<T>(queue : Queue<T>, f : T -> ())
Call the given function for its side effect on each queue element in order: from front to back.
Example:
import Nat "mo:core/Nat";
persistent actor {
var text = "";
let queue = Queue.fromIter<Nat>([1, 2, 3].values());
Queue.forEach<Nat>(queue, func n = text #= Nat.toText(n));
assert text == "123";
}
Runtime: O(size)
Space: O(size)
*Runtime and space assumes that f runs in O(1) time and space.
Function map
func map<T1, T2>(queue : Queue<T1>, f : T1 -> T2) : Queue<T2>
Create a new queue by applying the given function to each element of the original queue.
Note: The order of visiting elements is undefined with the current implementation.
Example:
import Nat "mo:core/Nat";
persistent actor {
let queue = Queue.fromIter<Nat>([1, 2, 3].values());
let mapped = Queue.map<Nat, Nat>(queue, func n = n * 2);
assert Queue.size(mapped) == 3;
assert Queue.peekFront(mapped) == ?2;
assert Queue.peekBack(mapped) == ?6;
}
Runtime: O(size)
Space: O(size)
*Runtime and space assumes that f runs in O(1) time and space.
Function filter
func filter<T>(queue : Queue<T>, predicate : T -> Bool) : Queue<T>
Create a new queue with only those elements of the original queue for which the given predicate returns true.
Example:
persistent actor {
let queue = Queue.fromIter<Nat>([1, 2, 3, 4].values());
let filtered = Queue.filter<Nat>(queue, func n = n % 2 == 0);
assert Queue.size(filtered) == 2;
assert Queue.peekFront(filtered) == ?2;
assert Queue.peekBack(filtered) == ?4;
}
Runtime: O(size)
Space: O(size)
*Runtime and space assumes that predicate runs in O(1) time and space.
Function filterMap
func filterMap<T, U>(queue : Queue<T>, f : T -> ?U) : Queue<U>
Create a new queue by applying the given function to each element of the original queue and collecting the results for which the function returns a non-null value.
Example:
persistent actor {
let queue = Queue.fromIter<Nat>([1, 2, 3, 4].values());
let filtered = Queue.filterMap<Nat, Nat>(queue, func n = if (n % 2 == 0) { ?n } else null);
assert Queue.size(filtered) == 2;
assert Queue.peekFront(filtered) == ?2;
assert Queue.peekBack(filtered) == ?4;
}
Runtime: O(size)
Space: O(size)
*Runtime and space assumes that f runs in O(1) time and space.
Function toText
func toText<T>(queue : Queue<T>, f : T -> Text) : Text
Create a Text representation of a queue for debugging purposes.
Example:
import Nat "mo:core/Nat";
persistent actor {
let queue = Queue.fromIter<Nat>([1, 2, 3].values());
assert Queue.toText(queue, Nat.toText) == "RealTimeQueue[1, 2, 3]";
}
Runtime: O(size)
Space: O(size)
*Runtime and space assumes that f runs in O(1) time and space.
Function reverse
func reverse<T>(queue : Queue<T>) : Queue<T>
Reverse the order of elements in a queue. This operation is cheap, it does NOT require copying the elements.
Example:
persistent actor {
let queue = Queue.fromIter<Nat>([1, 2, 3].values());
let reversed = Queue.reverse(queue);
assert Queue.peekFront(reversed) == ?3;
assert Queue.peekBack(reversed) == ?1;
}
Runtime: O(1)
Space: O(1)