pure/Set

type Set<T> = Types.Pure.Set<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).

public func fromIter<T>(iter : Iter.Iter<T>, compare : (T, T) -> Order.Order) : Set<T>

Create a set with the elements obtained from an iterator. Potential duplicate elements in the iterator are ignored, i.e. multiple occurrences of an equal element only occur once in the set.

Example:

import Set "mo:base/pure/Set";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";

persistent actor {
  transient let iterator = Iter.fromArray([3, 1, 2, 1]);
  let set = Set.fromIter<Nat>(iterator, Nat.compare); // => {1, 2, 3}
}

Runtime: O(n * log(n)). Space: O(n). where n denotes the number of elements returned by the iterator 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 add<T>(
  set : Set<T>,
  compare : (T, T) -> Order.Order,
  elem : T
) : Set<T>

Given a set ordered by compare, insert the new element, returning the new set.

Return the set unchanged if the element already exists in the set.

Example:

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

persistent actor {
  let set = Set.empty<Nat>();
  Set.add(set, Nat.compare, 1);
  Set.add(set, Nat.compare, 2);
  Set.add(set, Nat.compare, 3);
}

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 set most of the tree nodes. Garbage collecting one of the sets (e.g. after an assignment m := Set.add(m, c, e)) causes collecting O(log(n)) nodes.

public func insert<T>(
  set : Set<T>,
  compare : (T, T) -> Order.Order,
  elem : T
) : (Set<T>, Bool)

Given set ordered by compare, insert the new element, returning the set extended with element and a Boolean indicating if the element was already present in set.

Example:

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

persistent actor {
  let (set1, true) = Set.insert(Set.empty<Nat>, Nat.compare, 1);
  let (set2, true) = Set.insert(set2, Nat.compare, 2);
  let (set3, true) = Set.insert(set3, Nat.compare, 3);
  let (set4, false) = Set.insert(set3, Nat.compare, 1);
}

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 set most of the tree nodes. Garbage collecting one of the sets (e.g. after an assignment m := Set.add(m, c, e)) causes collecting O(log(n)) nodes.

public func remove<T>(
  set : Set<T>,
  compare : (T, T) -> Order.Order,
  element : T
) : Set<T>

Given set ordered by compare return the set with element removed. Return the set unchanged if the element was absent.

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

persistent actor {
  let set = Set.empty<Nat>() |>
            Set.add(_, Nat.compare, 1) |>
            Set.add(_, Nat.compare, 2) |>
            Set.add(_, Nat.compare, 3);

  let set1 = Set.remove(set, Nat.compare, 2);
  Debug.print(Set.toText(set1, Nat.toText));   // prints `{1, 3}`
  let set2 = Set.remove(set, Nat.compare, 4);
  Debug.print(Set.toText(set2, Nat.toText));   // prints `{1, 2, 3}`
}

Runtime: O(log(n)). Space: O(log(n)) including garbage, see 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(log(n)) objects that will be collected as garbage. Note: The returned set shares with set most of the tree nodes. Garbage collecting one of the sets (e.g. after an assignment m := Set.delete(m, c, e)) causes collecting O(log(n)) nodes.

public func delete<T>(
  set : Set<T>,
  compare : (T, T) -> Order.Order,
  element : T
) : (Set<T>, Bool)

Given set ordered by compare, delete element from the set, returning either the set without the element and a Boolean indicating whether whether element was contained in set.

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

persistent actor {
  let set = Set.empty<Nat>() |>
            Set.add(_, Nat.compare, 1) |>
            Set.add(_, Nat.compare, 2) |>
            Set.add(_, Nat.compare, 3);

  let (set1, contained_two) = Set.delete(set, Nat.compare, 2);
  assert contained_two;
  Debug.print(Set.toText(set1, Nat.toText));   // prints `{1, 3}`
  let (set2, contained_four) = Set.delete(set1, Nat.compare, 4);
  assert not contained_four;
}

Runtime: O(log(n)). Space: O(log(n)) including garbage, see 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(log(n)) objects that will be collected as garbage. Note: The returned set shares with set most of the tree nodes. Garbage collecting one of the sets (e.g. after an assignment m := Set.delete(m, c, e)) causes collecting O(log(n)) nodes.

public func contains<T>(
  set : Set<T>,
  compare : (T, T) -> Order.Order,
  element : T
) : Bool

Tests whether the set contains the provided element.

Example:

import Set "mo:base/pure/Set";
import Nat "mo:base/Nat";
import Bool "mo:base/Bool";
import Debug "mo:base/Debug";

persistent actor {
  let set0 = Set.empty<Nat>();
  let set1 = Set.add(set0, Nat.compare, 1);
  let set2 = Set.add(set1, Nat.compare, 2);
  let set3 = Set.add(set2, Nat.compare, 3);

  Debug.print(Bool.toText(Set.contains(set3, Nat.compare, 1))); // prints `true`
  Debug.print(Bool.toText(Set.contains(set3, Nat.compare, 4))); // prints `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<T>(s : Set<T>) : ?T

Get the maximal element of the set set 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<T>(s : Set<T>) : ?T

Retrieves the minimum element from the set. If the set is empty, returns null.

Example:

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

persistent actor {
  let set0 = Set.empty<Nat>();
  let set1 = Set.add(set0, Nat.compare, 1);
  let set2 = Set.add(set1, Nat.compare, 2);
  let set3 = Set.add(set2, Nat.compare, 3);
  Debug.print(debug_show(Set.min(set3))); // prints `?1`.
}

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

public func union<T>(
  set1 : Set<T>,
  set2 : Set<T>,
  compare : (T, T) -> Order.Order
) : Set<T>

Returns a new set that is the union of set1 and set2, i.e. a new set that all the elements that exist in at least on of the two sets. Potential duplicates are ignored, i.e. if the same element occurs in both set1 and set2, it only occurs once in the returned set.

Example:

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

persistent actor {
  let set1 = Set.fromIter(Iter.fromArray([1, 2, 3]), Nat.compare);
  let set2 = Set.fromIter(Iter.fromArray([3, 4, 5]), Nat.compare);
  let union = Set.union(set1, set2, Nat.compare);
  Debug.print(debug_show(Iter.toArray(Set.values(union))));
  // prints: `[1, 2, 3, 4, 5]`.
}

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. and assuming that the compare function implements an O(1) comparison.

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

public func intersection<T>(
  set1 : Set<T>,
  set2 : Set<T>,
  compare : (T, T) -> Order.Order
) : Set<T>

Returns a new set that is the intersection of set1 and set2, i.e. a new set that contains all the elements that exist in both sets.

Example:

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

persistent actor {
  let set1 = Set.fromIter(Iter.fromArray([0, 1, 2]), Nat.compare);
  let set2 = Set.fromIter(Iter.fromArray([1, 2, 3]), Nat.compare);
  let intersection = Set.intersection(set1, set2, Nat.compare);
  Debug.print(debug_show(Iter.toArray(Set.values(intersection))));
  // prints: `[1, 2]`.
}

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.

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

public func difference<T>(
  set1 : Set<T>,
  set2 : Set<T>,
  compare : (T, T) -> Order.Order
) : Set<T>

Returns a new set that is the difference between set1 and set2 (set1 minus set2), i.e. a new set that contains all the elements of set1 that do not exist in set2.

Example:

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

persistent actor {
  let set1 = Set.fromIter(Iter.fromArray([1, 2, 3]), Nat.compare);
  let set2 = Set.fromIter(Iter.fromArray([3, 4, 5]), Nat.compare);
  let difference = Set.difference(set1, set2, Nat.compare);
  Debug.print(debug_show(Iter.toArray(Set.values(difference))));
  // prints: `[1, 2]`.
}

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.

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

public func map<T1, T2>(
  s : Set<T1>,
  compare : (T2, T2) -> Order.Order,
  project : T1 -> T2
) : Set<T2>

Project all elements of the set in a new set. Apply a mapping function to each element in the set and collect the mapped elements in a new mutable set.

Example:

import Set "mo:base/pure/Set";
import Nat "mo:base/Nat";
import Text "mo:base/Text";
import Debug "mo:base/Debug";

persistent actor {
  let set0 = Set.empty<Nat>();
  let set1 = Set.add(set0, Nat.compare, 1);
  let set2 = Set.add(set1, Nat.compare, 2);
  let numbers = Set.add(set2, Nat.compare, 3);

  let textNumbers = Set.map<Nat, Text>(numbers, Text.compare, func (number) {
    Nat.toText(number)
  });
  for (textNumbers in Set.values(textNumbers)) {
     Debug.print(debug_show(textNumbers));
  }
  // prints:
  // `"1"`
  // `"2"`
  // `"3"`
}

Runtime: O(n * log(n)). Space: O(n) retained memory plus garbage, see 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 forEach<T>(set : Set<T>, operation : T -> ())

Apply an operation on each element contained in the set. The operation is applied in ascending order of the elements.

Example:

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

persistent actor {
  let set0 = Set.add(empty, Nat.compare, 0);
  let set1 = Set.add(set0, Nat.compare, 1);
  let set2 = Set.add(set1, Nat.compare, 2);
  let numbers = Set.add(set2, Nat.compare, 3);

  Set.forEach<Nat>(numbers, func (element) {
    Debug.print(" " # Nat.toText(element));
  })
  // prints
  //  0 1 2 3
}

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

public func filter<T>(
  set : Set<T>,
  compare : (T, T) -> Order.Order,
  criterion : T -> Bool
) : Set<T>

Filter elements in a new set. Create a copy of the mutable set that only contains the elements that fulfil the criterion function.

Example:

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

persistent actor {
  let set0 = Set.add(empty, Nat.compare, 0);
  let set1 = Set.add(set0, Nat.compare, 1);
  let set2 = Set.add(set1, Nat.compare, 2);
  let numbers = Set.add(set2, Nat.compare, 3);

  let evenNumbers = Set.filter<Nat>(numbers, Nat.compare, func (number) {
    number % 2 == 0
  });
}

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

public func filterMap<T1, T2>(
  set : Set<T1>,
  compare : (T2, T2) -> Order.Order,
  project : T1 -> ?T2
) : Set<T2>

Filter all elements in the set by also applying a projection to the elements. Apply a mapping function project to all elements in the set and collect all elements, for which the function returns a non-null new element. Collect all non-discarded new elements in a new mutable set.

Example:

import Set "mo:base/pure/Set";
import Nat "mo:base/Nat";
import Text "mo:base/Text";
import Debug "mo:base/Debug";

persistent actor {
  let empty = Set.empty<Nat>();
  let set0 = Set.add(empty, Nat.compare, 0);
  let set1 = Set.add(set0, Nat.compare, 1);
  let set2 = Set.add(set1, Nat.compare, 2);
  let numbers = Set.add(set2, Nat.compare, 3);

  let evenTextNumbers = Set.filterMap<Nat, Text>(numbers, Text.compare, func (number) {
    if (number % 2 == 0) {
       ?Nat.toText(number)
    } else {
       null // discard odd numbers
    }
  });
  for (textNumber in Set.values(evenTextNumbers)) {
     Debug.print(textNumber);
  }
  // prints:
  // `"0"`
  // `"2"`
}

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

Note: Creates O(log(n)) temporary objects that will be collected as garbage. 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<T>(
  s1 : Set<T>,
  s2 : Set<T>,
  compare : (T, T) -> Order.Order
) : Bool

Test whether set1 is a sub-set of set2, i.e. each element in set1 is also contained in set2. Returns true if both sets are equal.

Example:

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

persistent actor {
  let set1 = Set.fromIter(Iter.fromArray([1, 2]), Nat.compare);
  let set2 = Set.fromIter(Iter.fromArray([0, 1, 2]), Nat.compare);
  Debug.print(debug_show(Set.isSubset(set1, set2, Nat.compare))); // prints `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 equal<T>(
  set1 : Set<T>,
  set2 : Set<T>,
  compare : (T, T) -> Order.Order
) : Bool

Test whether two sets are equal. Both sets have to be constructed by the same comparison function.

Example:

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

persistent actor {
  let set0 = Set.empty<Nat>();
  let set1 = Set.add(set0, Nat.compare, 1);
  let set2 = Set.add(set1, Nat.compare, 2);
  assert (not Set.equal(set1, set2, Nat.compare));
}

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 compare<T>(
  set1 : Set<T>,
  set2 : Set<T>,
  compare : (T, T) -> Order.Order
) : Order.Order

Compare two sets by comparing the elements. Both sets must have been created by the same comparison function. The two sets are iterated by the ascending order of their creation and order is determined by the following rules: Less: set1 is less than set2 if:

• the pairwise iteration hits an element pair element1 and element2 where element1 is less than element2 and all preceding elements are equal, or,
• set1 is a strict prefix of set2, i.e. set2 has more elements than set1 and all elements of set1 occur at the beginning of iteration set2. Equal: set1 and set2 have same series of equal elements by pairwise iteration. Greater: set1 is neither less nor equal set2.

Example:

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

persistent actor {
  let set1 =
    Set.empty<Nat>() |>
    Set.add(_, Nat.compare, 0) |>
    Set.add(_, Nat.compare, 1);

  let set2 =
    Set.empty<Nat>() |>
    Set.add(_, Nat.compare, 0) |>
    Set.add(_, Nat.compare, 2);

  let orderLess = Set.compare(set1, set2, Nat.compare);
  // `#less`
  let orderEqual = Set.compare(set1, set1, Nat.compare);
  // `#equal`
  let orderGreater = Set.compare(set2, set1, Nat.compare);
  // `#greater`
}

Runtime: O(n). Space: O(1) retained memory plus garbage, see below. where n denotes the number of elements stored in the set and assuming that compare has runtime and space costs of O(1).

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

public func values<T>(set : Set<T>) : Iter.Iter<T>

Returns an iterator over the elements in the set, traversing the elements in the ascending order.

Example:

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

persistent actor {
  let set0 = Set.empty<Nat>();
  let set1 = Set.add(set0, Nat.compare, 1);
  let set2 = Set.add(set1, Nat.compare, 2);
  let set3 = Set.add(set2, Nat.compare, 3);

  for (number in Set.values(set3)) {
     Debug.print(debug_show(number));
  }
  // prints:
  // `1`
  // `2`
  // `3`
}

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

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

public func reverseValues<T>(set : Set<T>) : Iter.Iter<T>

Returns an iterator over the elements in the set, traversing the elements in the descending order.

Example:

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

persistent actor {
  let set0 = Set.empty<Nat>();
  let set1 = Set.add(set0, Nat.compare, 1);
  let set2 = Set.add(set1, Nat.compare, 2);
  let set3 = Set.add(set2, Nat.compare, 3);

  for (number in Set.reverseValues(set)) {
     Debug.print(debug_show(number));
  }
  // prints:
  // `3`
  // `2`
  // `1`
}

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

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

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

Create a new empty mutable set.

Example:

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

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

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

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

Create a new set with a single element.

Example:

import Set "mo:base/pure/Set";
import Debug "mo:base/Debug";

persistent actor {
  let cities = Set.singleton<Text>("Zurich");
  Debug.print(debug_show(Set.size(cities))); // prints `1`
}

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

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

Return the number of elements in a set.

Example:

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

persistent actor {
  let set = Set.empty<Nat>();
  Set.add(set, Nat.compare, 1);
  Set.add(set, Nat.compare, 2);
  Set.add(set, Nat.compare, 3);

  Debug.print(Nat.toText(Set.size(set))); // prints `3`
}

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

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

Iterate all elements in descending order, and accumulate the elements by applying the combine function, starting from a base value.

Example:

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

persistent actor {
  let set0 = Set.empty<Nat>();
  let set1 = Set.add(set0, Nat.compare, 1);
  let set2 = Set.add(set1, Nat.compare, 2);
  let set3 = Set.add(set2, Nat.compare, 3);

  let text = Set.foldRight<Nat, Text>(
     set3,
     "",
     func (element, accumulator) {
       let separator = if (accumulator != "") { ", " } else { "" };
       accumulator # separator # Nat.toText(element)
     }
  );
  Debug.print(text);
  // prints `2, 1, 0`
}

Runtime: O(n). Space: O(1) retained memory plus garbage, see below. where n denotes the number of elements stored in the set.

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

Iterate all elements in descending order, and accumulate the elements by applying the combine function, starting from a base value.

Example:

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

persistent actor {
  let set0 = Set.empty<Nat>();
  let set1 = Set.add(set0, Nat.compare, 1);
  let set2 = Set.add(set1, Nat.compare, 2);
  let set3 = Set.add(set2, Nat.compare, 3);

  let text = Set.foldRight<Nat, Text>(
     set3,
     "",
     func (element, accumulator) {
       let separator = if (accumulator != "") { ", " } else { "" };
       accumulator # separator # Nat.toText(element)
     }
  );
  Debug.print(text);
  // prints `2, 1, 0`
}

Runtime: O(n). Space: O(1) retained memory plus garbage, see below. where n denotes the number of elements stored in the set.

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

Determines whether a set is empty.

Example:

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

persistent actor {
  let set = Set.empty<Nat>();
  Set.add(set, Nat.compare, 1);
  Set.add(set, Nat.compare, 2);
  Set.add(set, Nat.compare, 3);

  Debug.print(debug_show(Set.isEmpty(set))); // prints `false`
  Set.clear(set);
  Debug.print(debug_show(Set.isEmpty(set))); // prints `true`
}

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

public func all<T>(set : Set<T>, predicate : T -> Bool) : Bool

Check whether all element in the set satisfy a predicate, i.e. the predicate function returns true for all elements in the set. Returns true for an empty set.

Example:

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

persistent actor {
  let set0 = Set.empty<Nat>();
  let set1 = Set.add(set0, Nat.compare, 1);
  let set2 = Set.add(set1, Nat.compare, 2);
  let set3 = Set.add(set3, Nat.compare, 3);

  let belowTen = Set.all<Nat>(set3, func (number) {
    number < 10
  }); // `true`
}

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

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

Check whether at least one element in the set satisfies a predicate, i.e. the predicate function returns true for at least one element in the set. Returns false for an empty set.

Example:

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

persistent actor {
  let set0 = Set.empty<Nat>();
  let set1 = Set.add(set0, Nat.compare, 1);
  let set2 = Set.add(set1, Nat.compare, 2);
  let set3 = Set.add(set2, Nat.compare, 3);

  let aboveTen = Set.any<Nat>(set3, func (number) {
    number > 10
  }); // `false`
}

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

public func assertValid<T>(set : Set<T>, compare : (T, T) -> Order.Order) : ()

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

public func toText<T>(set : Set<T>, elementFormat : T -> Text) : Text

Generate a textual representation of all the elements in the set. Primarily to be used for testing and debugging. The elements are formatted according to elementFormat.

Example:

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

persistent actor {
  let set = Set.empty<Nat>();
  let set1 = Set.add(set0, Nat.compare, 1);
  let set2 = Set.add(set1, Nat.compare, 2);
  let set3 = Set.add(set2, Nat.compare, 3);

  let text = Set.toText<Nat>(set3, Nat.toText);
  // `"{0, 1, 2}"`
}

Runtime: O(n). Space: O(n) retained memory plus garbage, see below. where n denotes the number of elements stored in the set and assuming that elementFormat has runtime and space costs of O(1).

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

public func flatten<T>(setOfSets : Set<Set<T>>, compare : (T, T) -> Order.Order) : Set<T>

Construct the union of a set of element sets, i.e. all elements of each element set are included in the result set. Any duplicates are ignored, i.e. if the same element occurs in multiple element sets, it only occurs once in the result set.

Assumes all sets are ordered by compare.

Example:

import Set "mo:base/pure/Set";
import Nat "mo:base/Nat";
import Order "mo:base/Order";
import Iter "mo:base/Iter";
import Debug "mo:base/Debug";

persistent actor {
  func setCompare(first: Set.Set<Nat>, second: Set.Set<Nat>) : Order.Order {
     Set.compare(first, second, Nat.compare)
  };

  let subSet1 = Set.fromIter(Iter.fromArray([1, 2, 3]), Nat.compare);
  let subSet2 = Set.fromIter(Iter.fromArray([3, 4, 5]), Nat.compare);
  let subSet3 = Set.fromIter(Iter.fromArray([5, 6, 7]), Nat.compare);
  let setOfSets = Set.fromIter(Iter.fromArray([subSet1, subSet2, subSet3]), setCompare);
  let flatSet = Set.flatten(setOfSets, Nat.compare);
  Debug.print(debug_show(Iter.toArray(Set.values(flatSet))));
  // prints: `[1, 2, 3, 4, 5, 6, 7]`.
}

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

public func join<T>(setIterator : Iter.Iter<Set<T>>, compare : (T, T) -> Order.Order) : Set<T>

Construct the union of a series of sets, i.e. all elements of each set are included in the result set. Any duplicates are ignored, i.e. if an element occurs in several of the iterated sets, it only occurs once in the result set.

Assumes all sets are ordered by compare.

Example:

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

persistent actor {
  let set1 = Set.fromIter(Iter.fromArray([1, 2, 3]), Nat.compare);
  let set2 = Set.fromIter(Iter.fromArray([3, 4, 5]), Nat.compare);
  let set3 = Set.fromIter(Iter.fromArray([5, 6, 7]), Nat.compare);
  transient let iterator = Iter.fromArray([set1, set2, set3]);
  let combined = Set.join(iterator, Nat.compare);
  Debug.print(debug_show(Iter.toArray(Set.values(combined))));
  // prints: `[1, 2, 3, 4, 5, 6, 7]`.
}

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