core/Map
An imperative key-value map based on order/comparison of the keys. The map data structure type is stable and can be used for orthogonal persistence.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
// creation
let map = Map.empty<Nat, Text>();
// insertion
Map.add(map, Nat.compare, 0, "Zero");
// retrieval
assert Map.get(map, Nat.compare, 0) == ?"Zero";
assert Map.get(map, Nat.compare, 1) == null;
// removal
Map.remove(map, Nat.compare, 0);
assert Map.isEmpty(map);
}
The internal implementation is a B-tree with order 32.
Performance:
- Runtime:
O(log(n))
worst case cost per insertion, removal, and retrieval operation. - Space:
O(n)
for storing the entire map.n
denotes the number of key-value entries stored in the map.
Type Map
type Map<K, V> = Types.Map<K, V>
Function toPure
func toPure<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order) : PureMap.Map<K, V>
Convert the mutable key-value map to an immutable key-value map.
Example:
import Map "mo:core/Map";
import PureMap "mo:core/pure/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.fromIter<Nat, Text>(
[(0, "Zero"), (1, "One"), (2, "Two")].values(), Nat.compare);
let pureMap = Map.toPure(map, Nat.compare);
assert Iter.toArray(PureMap.entries(pureMap)) == Iter.toArray(Map.entries(map))
}
Runtime: O(n * log(n))
.
Space: O(n)
retained memory plus garbage, see the note below.
where n
denotes the number of key-value entries stored in the map 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.
Function fromPure
func fromPure<K, V>(map : PureMap.Map<K, V>, compare : (K, K) -> Order.Order) : Map<K, V>
Convert an immutable key-value map to a mutable key-value map.
Example:
import Map "mo:core/Map";
import PureMap "mo:core/pure/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let pureMap = PureMap.fromIter(
[(0, "Zero"), (1, "One"), (2, "Two")].values(), Nat.compare);
let map = Map.fromPure<Nat, Text>(pureMap, Nat.compare);
assert Iter.toArray(Map.entries(map)) == Iter.toArray(PureMap.entries(pureMap))
}
Runtime: O(n * log(n))
.
Space: O(n)
.
where n
denotes the number of key-value entries stored in the map and
assuming that the compare
function implements an O(1)
comparison.
Function clone
func clone<K, V>(map : Map<K, V>) : Map<K, V>
Create a copy of the mutable key-value map.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let originalMap = Map.fromIter<Nat, Text>(
[(1, "One"), (2, "Two"), (3, "Three")].values(), Nat.compare);
let clonedMap = Map.clone(originalMap);
Map.add(originalMap, Nat.compare, 4, "Four");
assert Map.size(clonedMap) == 3;
assert Map.size(originalMap) == 4;
}
Runtime: O(n)
.
Space: O(n)
.
where n
denotes the number of key-value entries stored in the map.
Function empty
func empty<K, V>() : Map<K, V>
Create a new empty mutable key-value map.
Example:
import Map "mo:core/Map";
persistent actor {
let map = Map.empty<Nat, Text>();
assert Map.size(map) == 0;
}
Runtime: O(1)
.
Space: O(1)
.
Function singleton
func singleton<K, V>(key : K, value : V) : Map<K, V>
Create a new mutable key-value map with a single entry.
Example:
import Map "mo:core/Map";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.singleton<Nat, Text>(0, "Zero");
assert Iter.toArray(Map.entries(map)) == [(0, "Zero")];
}
Runtime: O(1)
.
Space: O(1)
.
Function clear
func clear<K, V>(map : Map<K, V>)
Delete all the entries in the key-value map.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let map = Map.fromIter<Nat, Text>(
[(0, "Zero"), (1, "One"), (2, "Two")].values(),
Nat.compare);
assert Map.size(map) == 3;
Map.clear(map);
assert Map.size(map) == 0;
}
Runtime: O(1)
.
Space: O(1)
.
Function isEmpty
func isEmpty<K, V>(map : Map<K, V>) : Bool
Determines whether a key-value map is empty.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let map = Map.fromIter<Nat, Text>(
[(0, "Zero"), (1, "One"), (2, "Two")].values(),
Nat.compare);
assert not Map.isEmpty(map);
Map.clear(map);
assert Map.isEmpty(map);
}
Runtime: O(1)
.
Space: O(1)
.
Function size
func size<K, V>(map : Map<K, V>) : Nat
Return the number of entries in a key-value map.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let map = Map.fromIter<Nat, Text>(
[(0, "Zero"), (1, "One"), (2, "Two")].values(),
Nat.compare);
assert Map.size(map) == 3;
Map.clear(map);
assert Map.size(map) == 0;
}
Runtime: O(1)
.
Space: O(1)
.
Function equal
func equal<K, V>(map1 : Map<K, V>, map2 : Map<K, V>, compareKeys : (K, K) -> Types.Order, equalValues : (V, V) -> Bool) : Bool
Test whether two imperative maps have equal entries. Both maps have to be constructed by the same comparison function.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Text "mo:core/Text";
persistent actor {
let map1 = Map.fromIter<Nat, Text>(
[(0, "Zero"), (1, "One"), (2, "Two")].values(),
Nat.compare);
let map2 = Map.clone(map1);
assert Map.equal(map1, map2, Nat.compare, Text.equal);
Map.clear(map2);
assert not Map.equal(map1, map2, Nat.compare, Text.equal);
}
Runtime: O(n)
.
Space: O(1)
.
Function containsKey
func containsKey<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order, key : K) : Bool
Tests whether the map contains the provided key.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let map = Map.fromIter<Nat, Text>(
[(0, "Zero"), (1, "One"), (2, "Two")].values(),
Nat.compare);
assert Map.containsKey(map, Nat.compare, 1);
assert not Map.containsKey(map, Nat.compare, 3);
}
Runtime: O(log(n))
.
Space: O(1)
.
where n
denotes the number of key-value entries stored in the map and
assuming that the compare
function implements an O(1)
comparison.
Function get
func get<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order, key : K) : ?V
Get the value associated with key in the given map if present and null
otherwise.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let map = Map.fromIter<Nat, Text>(
[(0, "Zero"), (1, "One"), (2, "Two")].values(),
Nat.compare);
assert Map.get(map, Nat.compare, 1) == ?"One";
assert Map.get(map, Nat.compare, 3) == null;
}
Runtime: O(log(n))
.
Space: O(1)
.
where n
denotes the number of key-value entries stored in the map and
assuming that the compare
function implements an O(1)
comparison.
Function insert
func insert<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order, key : K, value : V) : Bool
Given map
ordered by compare
, insert a new mapping from key
to value
.
Replaces any existing entry under key
.
Returns true if the key is new to the map, otherwise false.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.empty<Nat, Text>();
assert Map.insert(map, Nat.compare, 0, "Zero");
assert Map.insert(map, Nat.compare, 1, "One");
assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (1, "One")];
assert not Map.insert(map, Nat.compare, 0, "Nil");
assert Iter.toArray(Map.entries(map)) == [(0, "Nil"), (1, "One")]
}
Runtime: O(log(n))
.
Space: O(log(n))
.
where n
denotes the number of key-value entries stored in the map and
assuming that the compare
function implements an O(1)
comparison.
Function add
func add<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order, key : K, value : V)
Given map
ordered by compare
, add a mapping from key
to value
to map
.
Replaces any existing entry for key
.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.empty<Nat, Text>();
Map.add(map, Nat.compare, 0, "Zero");
Map.add(map, Nat.compare, 1, "One");
Map.add(map, Nat.compare, 0, "Nil");
assert Iter.toArray(Map.entries(map)) == [(0, "Nil"), (1, "One")]
}
Runtime: O(log(n))
.
Space: O(log(n))
.
where n
denotes the number of key-value entries stored in the map and
assuming that the compare
function implements an O(1)
comparison.
Function swap
func swap<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order, key : K, value : V) : ?V
Associates the value with the key in the map.
If the key is not yet present in the map, a new key-value pair is added and null
is returned.
Otherwise, if the key is already present, the value is overwritten and the previous value is returned.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.singleton<Nat, Text>(1, "One");
assert Map.swap(map, Nat.compare, 0, "Zero") == null;
assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (1, "One")];
assert Map.swap(map, Nat.compare, 0, "Nil") == ?"Zero";
assert Iter.toArray(Map.entries(map)) == [(0, "Nil"), (1, "One")];
}
Runtime: O(log(n))
.
Space: O(log(n))
.
where n
denotes the number of key-value entries stored in the map and
assuming that the compare
function implements an O(1)
comparison.
Function replace
func replace<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order, key : K, value : V) : ?V
Overwrites the value of an existing key and returns the previous value.
If the key does not exist, it has no effect and returns null
.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let map = Map.singleton<Nat, Text>(0, "Zero");
let prev1 = Map.replace(map, Nat.compare, 0, "Nil"); // overwrites the value for existing key.
assert prev1 == ?"Zero";
assert Map.get(map, Nat.compare, 0) == ?"Nil";
let prev2 = Map.replace(map, Nat.compare, 1, "One"); // no effect, key is absent
assert prev2 == null;
assert Map.get(map, Nat.compare, 1) == null;
}
Runtime: O(log(n))
.
Space: O(log(n))
.
where n
denotes the number of key-value entries stored in the map and
assuming that the compare
function implements an O(1)
comparison.
Function remove
func remove<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order, key : K)
Delete an entry by its key in the map. No effect if the key is not present.
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.fromIter<Nat, Text>(
[(0, "Zero"), (2, "Two"), (1, "One")].values(),
Nat.compare);
Map.remove(map, Nat.compare, 1);
assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (2, "Two")];
Map.remove(map, Nat.compare, 42);
assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (2, "Two")];
}
Runtime: O(log(n))
.
Space: O(log(n))
including garbage, see below.
where n
denotes the number of key-value entries stored in the map and
assuming that the compare
function implements an O(1)
comparison.
Note: Creates O(log(n))
objects that will be collected as garbage.
Function delete
func delete<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order, key : K) : Bool
Delete an existing entry by its key in the map.
Returns true
if the key was present in the map, otherwise false
.
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.fromIter<Nat, Text>(
[(0, "Zero"), (2, "Two"), (1, "One")].values(),
Nat.compare);
assert Map.delete(map, Nat.compare, 1); // present, returns true
assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (2, "Two")];
assert not Map.delete(map, Nat.compare, 42); // absent, returns false
assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (2, "Two")];
}
Runtime: O(log(n))
.
Space: O(log(n))
including garbage, see below.
where n
denotes the number of key-value entries stored in the map and
assuming that the compare
function implements an O(1)
comparison.
Note: Creates O(log(n))
objects that will be collected as garbage.
Function take
func take<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order, key : K) : ?V
Removes any existing entry by its key in the map.
Returns the previous value of the key or null
if the key was absent.
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.fromIter<Nat, Text>(
[(0, "Zero"), (2, "Two"), (1, "One")].values(),
Nat.compare);
assert Map.take(map, Nat.compare, 0) == ?"Zero";
assert Iter.toArray(Map.entries(map)) == [(1, "One"), (2, "Two")];
assert Map.take(map, Nat.compare, 3) == null;
assert Iter.toArray(Map.entries(map)) == [(1, "One"), (2, "Two")];
}
Runtime: O(log(n))
.
Space: O(log(n))
including garbage, see below.
where n
denotes the number of key-value entries stored in the map and
assuming that the compare
function implements an O(1)
comparison.
Note: Creates O(log(n))
objects that will be collected as garbage.
Function maxEntry
func maxEntry<K, V>(map : Map<K, V>) : ?(K, V)
Retrieves the key-value pair from the map with the maximum key.
If the map is empty, returns null
.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let map = Map.empty<Nat, Text>();
assert Map.maxEntry(map) == null;
Map.add(map, Nat.compare, 0, "Zero");
Map.add(map, Nat.compare, 2, "Two");
Map.add(map, Nat.compare, 1, "One");
assert Map.maxEntry(map) == ?(2, "Two")
}
Runtime: O(log(n))
.
Space: O(1)
.
where n
denotes the number of key-value entries stored in the map.
Function minEntry
func minEntry<K, V>(map : Map<K, V>) : ?(K, V)
Retrieves the key-value pair from the map with the minimum key.
If the map is empty, returns null
.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let map = Map.empty<Nat, Text>();
assert Map.minEntry(map) == null;
Map.add(map, Nat.compare, 2, "Two");
Map.add(map, Nat.compare, 0, "Zero");
Map.add(map, Nat.compare, 1, "One");
assert Map.minEntry(map) == ?(0, "Zero")
}
Runtime: O(log(n))
.
Space: O(1)
.
where n
denotes the number of key-value entries stored in the map.
Function entries
func entries<K, V>(map : Map<K, V>) : Types.Iter<(K, V)>
Returns an iterator over the key-value pairs in the map, traversing the entries in the ascending order of the keys.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.fromIter<Nat, Text>([(0, "Zero"), (2, "Two"), (1, "One")].values(), Nat.compare);
assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (1, "One"), (2, "Two")];
var sum = 0;
var text = "";
for ((k, v) in Map.entries(map)) { sum += k; text #= v };
assert sum == 3;
assert text == "ZeroOneTwo"
}
Cost of iteration over all elements:
Runtime: O(n)
.
Space: O(1)
retained memory plus garbage, see below.
where n
denotes the number of key-value entries stored in the map.
Note: Creates O(log(n))
temporary objects that will be collected as garbage.
Function entriesFrom
func entriesFrom<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order, key : K) : Types.Iter<(K, V)>
Returns an iterator over the key-value pairs in the map, starting from a given key in ascending order.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.fromIter<Nat, Text>([(0, "Zero"), (3, "Three"), (1, "One")].values(), Nat.compare);
assert Iter.toArray(Map.entriesFrom(map, Nat.compare, 1)) == [(1, "One"), (3, "Three")];
assert Iter.toArray(Map.entriesFrom(map, Nat.compare, 2)) == [(3, "Three")];
}
Cost of iteration over all elements:
Runtime: O(n)
.
Space: O(1)
retained memory plus garbage, see below.
where n
denotes the number of key-value entries stored in the map.
Note: Creates O(log(n))
temporary objects that will be collected as garbage.
Function reverseEntries
func reverseEntries<K, V>(map : Map<K, V>) : Types.Iter<(K, V)>
Returns an iterator over the key-value pairs in the map, traversing the entries in the descending order of the keys.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.fromIter<Nat, Text>([(0, "Zero"), (2, "Two"), (1, "One")].values(), Nat.compare);
assert Iter.toArray(Map.reverseEntries(map)) == [(2, "Two"), (1, "One"), (0, "Zero")];
var sum = 0;
var text = "";
for ((k, v) in Map.reverseEntries(map)) { sum += k; text #= v };
assert sum == 3;
assert text == "TwoOneZero"
}
Cost of iteration over all elements:
Runtime: O(n)
.
Space: O(1)
retained memory plus garbage, see below.
where n
denotes the number of key-value entries stored in the map.
Note: Creates O(log(n))
temporary objects that will be collected as garbage.
Function reverseEntriesFrom
func reverseEntriesFrom<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order, key : K) : Types.Iter<(K, V)>
Returns an iterator over the key-value pairs in the map, starting from a given key in descending order.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.fromIter<Nat, Text>([(0, "Zero"), (1, "One"), (3, "Three")].values(), Nat.compare);
assert Iter.toArray(Map.reverseEntriesFrom(map, Nat.compare, 0)) == [(0, "Zero")];
assert Iter.toArray(Map.reverseEntriesFrom(map, Nat.compare, 2)) == [(1, "One"), (0, "Zero")];
}
Cost of iteration over all elements:
Runtime: O(n)
.
Space: O(1)
retained memory plus garbage, see below.
where n
denotes the number of key-value entries stored in the map.
Note: Creates O(log(n))
temporary objects that will be collected as garbage.
Function keys
func keys<K, V>(map : Map<K, V>) : Types.Iter<K>
Returns an iterator over the keys in the map, traversing all keys in ascending order.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.fromIter<Nat, Text>([(0, "Zero"), (2, "Two"), (1, "One")].values(), Nat.compare);
assert Iter.toArray(Map.keys(map)) == [0, 1, 2];
}
Cost of iteration over all elements:
Runtime: O(n)
.
Space: O(1)
.
Function values
func values<K, V>(map : Map<K, V>) : Types.Iter<V>
Returns an iterator over the values in the map, traversing the values in the ascending order of the keys to which they are associated.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.fromIter<Nat, Text>([(0, "Zero"), (2, "Two"), (1, "One")].values(), Nat.compare);
assert Iter.toArray(Map.values(map)) == ["Zero", "One", "Two"];
}
Cost of iteration over all elements:
Runtime: O(n)
.
Space: O(1)
.
Function fromIter
func fromIter<K, V>(iter : Types.Iter<(K, V)>, compare : (K, K) -> Order.Order) : Map<K, V>
Create a mutable key-value map with the entries obtained from an iterator.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
transient let iter =
Iter.fromArray([(0, "Zero"), (2, "Two"), (1, "One")]);
let map = Map.fromIter<Nat, Text>(iter, Nat.compare);
assert Iter.toArray(Map.entries(map)) == [(0, "Zero"), (1, "One"), (2, "Two")];
}
Runtime: O(n * log(n))
.
Space: O(n)
.
where n
denotes the number of key-value entries returned by the iterator and
assuming that the compare
function implements an O(1)
comparison.
Function forEach
func forEach<K, V>(map : Map<K, V>, operation : (K, V) -> ())
Apply an operation on each key-value pair contained in the map. The operation is applied in ascending order of the keys.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let map = Map.fromIter<Nat, Text>([(0, "Zero"), (2, "Two"), (1, "One")].values(), Nat.compare);
var sum = 0;
var text = "";
Map.forEach<Nat, Text>(map, func (key, value) {
sum += key;
text #= value;
});
assert sum == 3;
assert text == "ZeroOneTwo";
}
Runtime: O(n)
.
Space: O(1)
retained memory plus garbage, see below.
where n
denotes the number of key-value entries stored in the map.
Note: Creates O(log(n))
temporary objects that will be collected as garbage.
Function filter
func filter<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order, criterion : (K, V) -> Bool) : Map<K, V>
Filter entries in a new map. Create a copy of the mutable map that only contains the key-value pairs that fulfil the criterion function.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let numberNames = Map.fromIter<Nat, Text>([(0, "Zero"), (2, "Two"), (1, "One")].values(), Nat.compare);
let evenNames = Map.filter<Nat, Text>(numberNames, Nat.compare, func (key, value) {
key % 2 == 0
});
assert Iter.toArray(Map.entries(evenNames)) == [(0, "Zero"), (2, "Two")];
}
Runtime: O(n)
.
Space: O(n)
.
where n
denotes the number of key-value entries stored in the map and
assuming that the compare
function implements an O(1)
comparison.
Function map
func map<K, V1, V2>(map : Map<K, V1>, project : (K, V1) -> V2) : Map<K, V2>
Project all values of the map in a new map. Apply a mapping function to the values of each entry in the map and collect the mapped entries in a new mutable key-value map.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.fromIter<Nat, Text>([(0, "Zero"), (2, "Two"), (1, "One")].values(), Nat.compare);
func f(key : Nat, _val : Text) : Nat = key * 2;
let resMap = Map.map<Nat, Text, Nat>(map, f);
assert Iter.toArray(Map.entries(resMap)) == [(0, 0), (1, 2), (2, 4)];
}
Runtime: O(n * log(n))
.
Space: O(n)
retained memory plus garbage, see below.
where n
denotes the number of key-value entries stored in the map and
assuming that the compare
function implements an O(1)
comparison.
Note: Creates O(log(n))
temporary objects that will be collected as garbage.
Function foldLeft
func foldLeft<K, V, A>(map : Map<K, V>, base : A, combine : (A, K, V) -> A) : A
Iterate all entries in ascending order of the keys, and accumulate the entries by applying the combine function, starting from a base value.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let map = Map.fromIter<Nat, Text>([(0, "Zero"), (2, "Two"), (1, "One")].values(), Nat.compare);
func folder(accum : (Nat, Text), key : Nat, val : Text) : ((Nat, Text))
= (key + accum.0, accum.1 # val);
assert Map.foldLeft(map, (0, ""), folder) == (3, "ZeroOneTwo");
}
Runtime: O(n)
.
Space: O(1)
retained memory plus garbage, see below.
where n
denotes the number of key-value entries stored in the map.
Note: Creates O(log(n))
temporary objects that will be collected as garbage.
Function foldRight
func foldRight<K, V, A>(map : Map<K, V>, base : A, combine : (K, V, A) -> A) : A
Iterate all entries in descending order of the keys, and accumulate the entries by applying the combine function, starting from a base value.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let map = Map.fromIter<Nat, Text>([(0, "Zero"), (2, "Two"), (1, "One")].values(), Nat.compare);
func folder(key : Nat, val : Text, accum : (Nat, Text)) : ((Nat, Text))
= (key + accum.0, accum.1 # val);
assert Map.foldRight(map, (0, ""), folder) == (3, "TwoOneZero");
}
Runtime: O(n)
.
Space: O(1)
retained memory plus garbage, see below.
where n
denotes the number of key-value entries stored in the map.
Note: Creates O(log(n))
temporary objects that will be collected as garbage.
Function all
func all<K, V>(map : Map<K, V>, predicate : (K, V) -> Bool) : Bool
Check whether all entries in the map fulfil a predicate function, i.e.
the predicate function returns true
for all entries in the map.
Returns true
for an empty map.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let map = Map.fromIter<Nat, Text>([(0, "0"), (2, "2"), (1, "1")].values(), Nat.compare);
assert Map.all<Nat, Text>(map, func (k, v) = v == Nat.toText(k));
assert not Map.all<Nat, Text>(map, func (k, v) = k < 2);
}
Runtime: O(n)
.
Space: O(1)
retained memory plus garbage, see below.
where n
denotes the number of key-value entries stored in the map.
Note: Creates O(log(n))
temporary objects that will be collected as garbage.
Function any
func any<K, V>(map : Map<K, V>, predicate : (K, V) -> Bool) : Bool
Test if any key-value pair in map
satisfies the given predicate pred
.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let map = Map.fromIter<Nat, Text>([(0, "0"), (2, "2"), (1, "1")].values(), Nat.compare);
assert Map.any<Nat, Text>(map, func (k, v) = (k >= 0));
assert not Map.any<Nat, Text>(map, func (k, v) = (k >= 3));
}
Runtime: O(n)
.
Space: O(1)
retained memory plus garbage, see below.
where n
denotes the number of key-value entries stored in the map.
Note: Creates O(log(n))
temporary objects that will be collected as garbage.
Function filterMap
func filterMap<K, V1, V2>(map : Map<K, V1>, compare : (K, K) -> Order.Order, project : (K, V1) -> ?V2) : Map<K, V2>
Filter all entries in the map by also applying a projection to the value.
Apply a mapping function project
to all entries in the map and collect all
entries, for which the function returns a non-null new value. Collect all
non-discarded entries with the key and new value in a new mutable map.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Iter "mo:core/Iter";
persistent actor {
let map = Map.fromIter<Nat, Text>([(0, "Zero"), (2, "Two"), (1, "One")].values(), Nat.compare);
func f(key : Nat, val : Text) : ?Text {
if(key == 0) {null}
else { ?("Twenty " # val)}
};
let newMap = Map.filterMap<Nat, Text, Text>(map, Nat.compare, f);
assert Iter.toArray(Map.entries(newMap)) == [(1, "Twenty One"), (2, "Twenty Two")];
}
Runtime: O(n * log(n))
.
Space: O(n)
retained memory plus garbage, see below.
where n
denotes the number of key-value entries stored in the map.
Note: Creates O(log(n))
temporary objects that will be collected as garbage.
Function assertValid
func assertValid<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order)
Internal sanity check function. Can be used to check that key/value pairs have been inserted with a consistent key comparison function. Traps if the internal map structure is invalid.
Function toText
func toText<K, V>(map : Map<K, V>, keyFormat : K -> Text, valueFormat : V -> Text) : Text
Generate a textual representation of all the entries in the map.
Primarily to be used for testing and debugging.
The keys and values are formatted according to keyFormat
and valueFormat
.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
persistent actor {
let map = Map.fromIter<Nat, Text>([(0, "Zero"), (2, "Two"), (1, "One")].values(), Nat.compare);
assert Map.toText<Nat, Text>(map, Nat.toText, func t { t }) == "Map{(0, Zero), (1, One), (2, Two)}";
}
Runtime: O(n)
.
Space: O(n)
retained memory plus garbage, see below.
where n
denotes the number of key-value entries stored in the map and
assuming that keyFormat
and valueFormat
have runtime and space costs of O(1)
.
Note: Creates O(log(n))
temporary objects that will be collected as garbage.
Function compare
func compare<K, V>(map1 : Map<K, V>, map2 : Map<K, V>, compareKey : (K, K) -> Order.Order, compareValue : (V, V) -> Order.Order) : Order.Order
Compare two maps by primarily comparing keys and secondarily values.
Both maps must have been created by the same key comparison function.
The two maps are iterated by the ascending order of their creation and
order is determined by the following rules:
Less:
map1
is less than map2
if:
- the pairwise iteration hits a entry pair
entry1
andentry2
whereentry1
is less thanentry2
and all preceding entry pairs are equal, or, map1
is a strict prefix ofmap2
, i.e.map2
has more entries thanmap1
and all entries ofmap1
occur at the beginning of iterationmap2
.entry1
is less thanentry2
if:- the key of
entry1
is less than the key ofentry2
, or entry1
andentry2
have equal keys and the value ofentry1
is less than the value ofentry2
. Equal:map1
andmap2
have same series of equal entries by pairwise iteration. Greater:map1
is neither less nor equalmap2
.
Example:
import Map "mo:core/Map";
import Nat "mo:core/Nat";
import Text "mo:core/Text";
persistent actor {
let map1 = Map.fromIter<Nat, Text>([(0, "Zero"), (1, "One")].values(), Nat.compare);
let map2 = Map.fromIter<Nat, Text>([(0, "Zero"), (2, "Two")].values(), Nat.compare);
assert Map.compare(map1, map2, Nat.compare, Text.compare) == #less;
assert Map.compare(map1, map1, Nat.compare, Text.compare) == #equal;
assert Map.compare(map2, map1, Nat.compare, Text.compare) == #greater
}
Runtime: O(n)
.
Space: O(1)
retained memory plus garbage, see below.
where n
denotes the number of key-value entries stored in the map and
assuming that compareKey
and compareValue
have runtime and space costs of O(1)
.
Note: Creates O(log(n))
temporary objects that will be collected as garbage.