OrderedSet

Stable ordered set implemented as a red-black tree.

A red-black tree is a balanced binary search tree ordered by the elements.

The tree data structure internally colors each of its nodes either red or black, and uses this information to balance the tree during the modifying operations.

Performance:

Credits:

The core of this implementation is derived from:

type Set<T> = { size : Nat; root : Tree<T> }

Ordered collection of unique elements of the generic type T. If type T is stable then Set<T> is also stable. To ensure that property the Set<T> does not have any methods, instead they are gathered in the functor-like class Operations (see example there).

class Operations<T>(compare : (T, T) -> O.Order)

public func fromIter(i : I.Iter<T>) : Set<T>

Returns a new Set, containing all entries given by the iterator i. If there are multiple identical entries only one is taken.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set = natSet.fromIter(Iter.fromArray([0, 2, 1]));

Debug.print(debug_show(Iter.toArray(natSet.vals(set))));
// [0, 1, 2]

Runtime: O(n * log(n)). Space: O(n) retained memory plus garbage, see the note below. where n denotes the number of elements stored in the set and assuming that the compare function implements an O(1) comparison.

Note: Creates O(n * log(n)) temporary objects that will be collected as garbage.

public func put(s : Set<T>, value : T) : Set<T>

Insert the value value into the set s. Has no effect if value is already present in the set. Returns a modified set.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
var set = natSet.empty();

set := natSet.put(set, 0);
set := natSet.put(set, 2);
set := natSet.put(set, 1);

Debug.print(debug_show(Iter.toArray(natSet.vals(set))));
// [0, 1, 2]

Runtime: O(log(n)). Space: O(log(n)). where n denotes the number of elements stored in the set and assuming that the compare function implements an O(1) comparison.

Note: The returned set shares with the s most of the tree nodes. Garbage collecting one of sets (e.g. after an assignment m := natSet.delete(m, k)) causes collecting O(log(n)) nodes.

public func delete(s : Set<T>, value : T) : Set<T>

Deletes the value value from the set s. Has no effect if value is not present in the set. Returns modified set.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set = natSet.fromIter(Iter.fromArray([0, 2, 1]));

Debug.print(debug_show(Iter.toArray(natSet.vals(natSet.delete(set, 1)))));
Debug.print(debug_show(Iter.toArray(natSet.vals(natSet.delete(set, 42)))));
// [0, 2]
// [0, 1, 2]

Runtime: O(log(n)). Space: O(log(n)). where n denotes the number of elements stored in the set and assuming that the compare function implements an O(1) comparison.

Note: The returned set shares with the s most of the tree nodes. Garbage collecting one of sets (e.g. after an assignment m := natSet.delete(m, k)) causes collecting O(log(n)) nodes.

public func contains(s : Set<T>, value : T) : Bool

Test if the set 's' contains a given element.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set = natSet.fromIter(Iter.fromArray([0, 2, 1]));

Debug.print(debug_show natSet.contains(set, 1)); // => true
Debug.print(debug_show natSet.contains(set, 42)); // => false

Runtime: O(log(n)). Space: O(1) retained memory plus garbage, see the note below. where n denotes the number of elements stored in the set and assuming that the compare function implements an O(1) comparison.

public func max(s : Set<T>) : ?T

Get a maximal element of the set s if it is not empty, otherwise returns null

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let s1 = natSet.fromIter(Iter.fromArray([0, 2, 1]));
let s2 = natSet.empty();

Debug.print(debug_show(natSet.max(s1))); // => ?2
Debug.print(debug_show(natSet.max(s2))); // => null

Runtime: O(log(n)). Space: O(1). where n denotes the number of elements in the set

public func min(s : Set<T>) : ?T

Get a minimal element of the set s if it is not empty, otherwise returns null

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let s1 = natSet.fromIter(Iter.fromArray([0, 2, 1]));
let s2 = natSet.empty();

Debug.print(debug_show(natSet.min(s1))); // => ?0
Debug.print(debug_show(natSet.min(s2))); // => null

Runtime: O(log(n)). Space: O(1). where n denotes the number of elements in the set

public func union(s1 : Set<T>, s2 : Set<T>) : Set<T>

Set union operation.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set1 = natSet.fromIter(Iter.fromArray([0, 1, 2]));
let set2 = natSet.fromIter(Iter.fromArray([2, 3, 4]));

Debug.print(debug_show Iter.toArray(natSet.vals(natSet.union(set1, set2))));
// [0, 1, 2, 3, 4]

Runtime: O(m * log(n)). Space: O(m), retained memory plus garbage, see the note below. where m and n denote the number of elements in the sets, and m <= n.

Note: Creates O(m * log(n)) temporary objects that will be collected as garbage.

public func intersect(s1 : Set<T>, s2 : Set<T>) : Set<T>

Set intersection operation.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set1 = natSet.fromIter(Iter.fromArray([0, 1, 2]));
let set2 = natSet.fromIter(Iter.fromArray([1, 2, 3]));

Debug.print(debug_show Iter.toArray(natSet.vals(natSet.intersect(set1, set2))));
// [1, 2]

Runtime: O(m * log(n)). Space: O(m), retained memory plus garbage, see the note below. where m and n denote the number of elements in the sets, and m <= n.

Note: Creates O(m) temporary objects that will be collected as garbage.

public func diff(s1 : Set<T>, s2 : Set<T>) : Set<T>

Set difference.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set1 = natSet.fromIter(Iter.fromArray([0, 1, 2]));
let set2 = natSet.fromIter(Iter.fromArray([1, 2, 3]));

Debug.print(debug_show Iter.toArray(natSet.vals(natSet.diff(set1, set2))));
// [0]

Runtime: O(m * log(n)). Space: O(m), retained memory plus garbage, see the note below. where m and n denote the number of elements in the sets, and m <= n.

Note: Creates O(m * log(n)) temporary objects that will be collected as garbage.

public func map<T1>(s : Set<T1>, f : T1 -> T) : Set<T>

Creates a new Set by applying f to each entry in the set s. Each element x in the old set is transformed into a new entry x2, where the new value x2 is created by applying f to x. The result set may be smaller than the original set due to duplicate elements.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set = natSet.fromIter(Iter.fromArray([0, 1, 2, 3]));

func f(x : Nat) : Nat = if (x < 2) { x } else { 0 };

let resSet = natSet.map(set, f);

Debug.print(debug_show(Iter.toArray(natSet.vals(resSet))));
// [0, 1]

Cost of mapping all the elements: Runtime: O(n * log(n)). Space: O(n) retained memory where n denotes the number of elements stored in the set.

Note: Creates O(n * log(n)) temporary objects that will be collected as garbage.

public func mapFilter<T1>(s : Set<T1>, f : T1 -> ?T) : Set<T>

Creates a new set by applying f to each element in the set s. For each element x in the old set, if f evaluates to null, the element is discarded. Otherwise, the entry is transformed into a new entry x2, where the new value x2 is the result of applying f to x.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set = natSet.fromIter(Iter.fromArray([0, 1, 2, 3]));

func f(x : Nat) : ?Nat {
  if(x == 0) {null}
  else { ?( x * 2 )}
};

let newRbSet = natSet.mapFilter(set, f);

Debug.print(debug_show(Iter.toArray(natSet.vals(newRbSet))));
// [2, 4, 6]

Runtime: O(n * log(n)). Space: O(n) retained memory plus garbage, see the note below. where n denotes the number of elements stored in the set and assuming that the compare function implements an O(1) comparison.

Note: Creates O(n * log(n)) temporary objects that will be collected as garbage.

public func isSubset(s1 : Set<T>, s2 : Set<T>) : Bool

Test if set1 is subset of set2.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set1 = natSet.fromIter(Iter.fromArray([1, 2]));
let set2 = natSet.fromIter(Iter.fromArray([0, 2, 1]));

Debug.print(debug_show natSet.isSubset(set1, set2)); // => true

Runtime: O(m * log(n)). Space: O(1) retained memory plus garbage, see the note below. where m and n denote the number of elements stored in the sets set1 and set2, respectively, and assuming that the compare function implements an O(1) comparison.

public func equals(s1 : Set<T>, s2 : Set<T>) : Bool

Test if two sets are equal.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set1 = natSet.fromIter(Iter.fromArray([0, 2, 1]));
let set2 = natSet.fromIter(Iter.fromArray([1, 2]));

Debug.print(debug_show natSet.equals(set1, set1)); // => true
Debug.print(debug_show natSet.equals(set1, set2)); // => false

Runtime: O(m * log(n)). Space: O(1) retained memory plus garbage, see the note below. where m and n denote the number of elements stored in the sets set1 and set2, respectively, and assuming that the compare function implements an O(1) comparison.

public func vals(s : Set<T>) : I.Iter<T>

Returns an Iterator (Iter) over the elements of the set. Iterator provides a single method next(), which returns elements in ascending order, or null when out of elements to iterate over.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set = natSet.fromIter(Iter.fromArray([0, 2, 1]));

Debug.print(debug_show(Iter.toArray(natSet.vals(set))));
// [0, 1, 2]

Cost of iteration over all elements: Runtime: O(n). Space: O(log(n)) retained memory plus garbage, see the note below. where n denotes the number of elements stored in the set.

Note: Full set iteration creates O(n) temporary objects that will be collected as garbage.

public func valsRev(s : Set<T>) : I.Iter<T>

Same as vals() but iterates over elements of the set s in the descending order.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set = natSet.fromIter(Iter.fromArray([0, 2, 1]));

Debug.print(debug_show(Iter.toArray(natSet.valsRev(set))));
// [2, 1, 0]

Cost of iteration over all elements: Runtime: O(n). Space: O(log(n)) retained memory plus garbage, see the note below. where n denotes the number of elements stored in the set.

Note: Full set iteration creates O(n) temporary objects that will be collected as garbage.

public func empty() : Set<T>

Create a new empty Set.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set = natSet.empty();

Debug.print(debug_show(natSet.size(set))); // => 0

Cost of empty set creation Runtime: O(1). Space: O(1)

public func size(s : Set<T>) : Nat

Returns the number of elements in the set.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set = natSet.fromIter(Iter.fromArray([0, 2, 1]));

Debug.print(debug_show(natSet.size(set))); // => 3

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

public func foldLeft<Accum>(
  set : Set<T>,
  base : Accum,
  combine : (Accum, T) -> Accum
) : Accum

Collapses the elements in set into a single value by starting with base and progessively combining elements into base with combine. Iteration runs left to right.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set = natSet.fromIter(Iter.fromArray([0, 2, 1]));

func folder(accum : Nat, val : Nat) : Nat = val + accum;

Debug.print(debug_show(natSet.foldLeft(set, 0, folder)));
// 3

Cost of iteration over all elements: Runtime: O(n). Space: depends on combine function plus garbage, see the note below. where n denotes the number of elements stored in the set.

Note: Full set iteration creates O(n) temporary objects that will be collected as garbage.

public func foldRight<Accum>(
  set : Set<T>,
  base : Accum,
  combine : (T, Accum) -> Accum
) : Accum

Collapses the elements in set into a single value by starting with base and progessively combining elements into base with combine. Iteration runs right to left.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set = natSet.fromIter(Iter.fromArray([0, 2, 1]));

func folder(val : Nat, accum : Nat) : Nat = val + accum;

Debug.print(debug_show(natSet.foldRight(set, 0, folder)));
// 3

Cost of iteration over all elements: Runtime: O(n). Space: depends on combine function plus garbage, see the note below. where n denotes the number of elements stored in the set.

Note: Full set iteration creates O(n) temporary objects that will be collected as garbage.

public func isEmpty(s : Set<T>) : Bool

Test if the given set s is empty.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set = natSet.empty();

Debug.print(debug_show(natSet.isEmpty(set))); // => true

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

public func all(s : Set<T>, pred : T -> Bool) : Bool

Test whether all values in the set s satisfy a given predicate pred.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set = natSet.fromIter(Iter.fromArray([0, 2, 1]));

Debug.print(debug_show(natSet.all(set, func (v) = (v < 10))));
// true
Debug.print(debug_show(natSet.all(set, func (v) = (v < 2))));
// false

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

public func some(s : Set<T>, pred : (T) -> Bool) : Bool

Test if there exists an element in the set s satisfying the given predicate pred.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

let natSet = Set.Make<Nat>(Nat.compare);
let set = natSet.fromIter(Iter.fromArray([0, 2, 1]));

Debug.print(debug_show(natSet.some(set, func (v) = (v >= 3))));
// false
Debug.print(debug_show(natSet.some(set, func (v) = (v >= 0))));
// true

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

public func validate(s : Set<T>) : ()

Test helper that check internal invariant for the given set s. Raise an error (for a stack trace) if invariants are violated.

Class that captures element type T along with its ordering function compare and provide all operations to work with a set of type Set<T>.

An instance object should be created once as a canister field to ensure that the same ordering function is used for every operation.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";

actor {
  let natSet = Set.Make<Nat>(Nat.compare); // : Operations<Nat>
  stable var usedIds : Set.Set<Nat> = natSet.empty();
  
  public func createId(id : Nat) : async () {
    usedIds := natSet.put(usedIds, id);
  };
  
  public func idIsUsed(id: Nat) : async Bool {
     natSet.contains(usedIds, id)
  }
}

public let Make : <T>(compare : (T, T) -> O.Order) -> Operations<T>

Create OrderedSet.Operations object capturing element type T and compare function. It is an alias for the Operations constructor.

Example:

import Set "mo:base/OrderedSet";
import Nat "mo:base/Nat";

actor {
  let natSet = Set.Make<Nat>(Nat.compare);
  stable var set : Set.Set<Nat> = natSet.empty();
};