RBTree

public func share() : Tree<K, V>

Return a snapshot of the internal functional tree representation as sharable data. The returned tree representation is not affected by subsequent changes of the RBTree instance.

Example:

motoko include=initialize

tree.put(1, "one");
let treeSnapshot = tree.share();
tree.put(2, "second");
RBTree.size(treeSnapshot) // => 1 (Only the first insertion is part of the snapshot.)

Useful for storing the state of a tree object as a stable variable, determining its size, pretty-printing, and sharing it across async function calls, i.e. passing it in async arguments or async results.

Runtime: O(1). Heap space: O(1). Stack space: O(1).

public func unshare(t : Tree<K, V>) : ()

Reset the current state of the tree object from a functional tree representation.

Example:

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

tree.put(1, "one");
let snapshot = tree.share(); // save the current state of the tree object in a snapshot
tree.put(2, "two");
tree.unshare(snapshot); // restore the tree object from the snapshot
Iter.toArray(tree.entries()) // => [(1, "one")]

Useful for restoring the state of a tree object from stable data, saved, for example, in a stable variable.

Runtime: O(1). Heap space: O(1). Stack space: O(1).

public func get(key : K) : ?V

Retrieve the value associated with a given key, if present. Returns null, if the key is absent. The key is searched according to the compare function defined on the class instantiation.

Example:

motoko include=initialize

tree.put(1, "one");
tree.put(2, "two");

tree.get(1) // => ?"one"

Runtime: O(log(n)). Heap space: O(1). Stack space: O(log(n)). where n denotes the number of key-value entries stored in the tree and assuming that the compare function implements an O(1) comparison.

public func replace(key : K, value : V) : ?V

Replace the value associated with a given key, if the key is present. Otherwise, if the key does not yet exist, insert the key-value entry.

Returns the previous value of the key, if the key already existed. Otherwise, null, if the key did not yet exist before.

Example:

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

tree.put(1, "old one");
tree.put(2, "two");

ignore tree.replace(1, "new one");
Iter.toArray(tree.entries()) // => [(1, "new one"), (2, "two")]

Runtime: O(log(n)). Heap space: O(1) retained memory plus garbage, see the note below. Stack space: O(log(n)). where n denotes the number of key-value entries stored in the tree and assuming that the compare function implements an O(1) comparison.

Note: Creates O(log(n)) garbage objects.

public func put(key : K, value : V)

Insert a key-value entry in the tree. If the key already exists, it overwrites the associated value.

Example:

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

tree.put(1, "one");
tree.put(2, "two");
tree.put(3, "three");
Iter.toArray(tree.entries()) // now contains three entries

Runtime: O(log(n)). Heap space: O(1) retained memory plus garbage, see the note below. Stack space: O(log(n)). where n denotes the number of key-value entries stored in the tree and assuming that the compare function implements an O(1) comparison.

Note: Creates O(log(n)) garbage objects.

public func delete(key : K)

Delete the entry associated with a given key, if the key exists. No effect if the key is absent. Same as remove(key) except that it does not have a return value.

Example:

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

tree.put(1, "one");
tree.put(2, "two");

tree.delete(1);
Iter.toArray(tree.entries()) // => [(2, "two")].

Runtime: O(log(n)). Heap space: O(1) retained memory plus garbage, see the note below. Stack space: O(log(n)). where n denotes the number of key-value entries stored in the tree and assuming that the compare function implements an O(1) comparison.

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

public func remove(key : K) : ?V

Remove the entry associated with a given key, if the key exists, and return the associated value. Returns null without any other effect if the key is absent.

Example:

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

tree.put(1, "one");
tree.put(2, "two");

ignore tree.remove(1);
Iter.toArray(tree.entries()) // => [(2, "two")].

Runtime: O(log(n)). Heap space: O(1) retained memory plus garbage, see the note below. Stack space: O(log(n)). where n denotes the number of key-value entries stored in the tree and assuming that the compare function implements an O(1) comparison.

Note: Creates O(log(n)) garbage objects.

public func entries() : I.Iter<(K, V)>

An iterator for the key-value entries of the map, in ascending key order. The iterator takes a snapshot view of the tree and is not affected by concurrent modifications.

Example:

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

tree.put(1, "one");
tree.put(2, "two");
tree.put(3, "two");

for (entry in tree.entries()) {
  Debug.print("Entry key=" # debug_show(entry.0) # " value=\"" # entry.1 #"\"");
}

// Entry key=1 value="one"
// Entry key=2 value="two"
// Entry key=3 value="three"

Cost of iteration over all elements: Runtime: O(n). Heap space: O(log(n)) retained memory plus garbage, see the note below. Stack space: O(log(n)). where n denotes the number of key-value entries stored in the tree.

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

public func entriesRev() : I.Iter<(K, V)>

An iterator for the key-value entries of the map, in descending key order. The iterator takes a snapshot view of the tree and is not affected by concurrent modifications.

Example:

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

let tree = RBTree.RBTree<Nat, Text>(Nat.compare);
tree.put(1, "one");
tree.put(2, "two");
tree.put(3, "two");

for (entry in tree.entriesRev()) {
  Debug.print("Entry key=" # debug_show(entry.0) # " value=\"" # entry.1 #"\"");
}

// Entry key=3 value="three"
// Entry key=2 value="two"
// Entry key=1 value="one"

Cost of iteration over all elements: Runtime: O(n). Heap space: O(log(n)) retained memory plus garbage, see the note below. Stack space: O(log(n)). where n denotes the number of key-value entries stored in the tree.

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