Maps and sets

The standard library has three kinds of map, which differ in the order they keep their keys in:

All of them share one API: m[key] reads (a missing key reads as the default of V, and is not inserted) and m[key] = value writes; insert, get, try_get (an optional, Empty when the key is absent), contains, remove, count, is_empty and clear. A for loop visits a map’s entries as (key, value) tuples and a set’s members one by one. Adding or removing an entry while a loop iterates the map panics (“Map modified during iteration”), as it does for Array and HashMap; changing the value of a key that is present is allowed.

Sorted: Map and Set

Map<K, V> keeps its entries sorted by key, on a red-black tree. Besides iterating in order, it answers questions about the order:

• first() and last(): the entries with the smallest and largest key.
• lower_bound(key): the first entry whose key is at least key; upper_bound(key): the first whose key is greater.
• reversed(): iterates from the largest key down.
• range(from, to): iterates the keys from from up to, not including, to.

Each of the four queries returns an optional (key, value) tuple, Empty when there is no such entry. Set<K> is the same tree without values, and its queries return an optional member. An array converts to a Set, so an array literal can initialize one.

main(): int {
    var scores = Map<String, int>();
    scores["carol"] = 91;
    scores["alice"] = 84;
    scores["bob"] = 77;

    # Entries come out sorted by key.
    var names = "";
    for (var (name, score) in scores) {
        names = names + name + " ";
    }
    assert(names == "alice bob carol ", "key order");

    # Order queries return an optional (key, value) tuple.
    assert(scores.first().value().0 == "alice", "smallest key");
    assert(scores.lower_bound("b").value().0 == "bob", "first key >= b");
    assert(scores.upper_bound("carol").is_empty(), "nothing after carol");

    # A key range: from "a" up to, not including, "c".
    var in_range = 0;
    for (var (name, score) in scores.range("a", "c")) {
        in_range += 1;
    }
    assert(in_range == 2, "alice and bob");

    # A Set keeps sorted members; an array converts to one.
    Set<int> primes = [7, 2, 5, 3];
    var digits = 0;
    for (var p in primes.reversed()) {
        digits = digits * 10 + p;
    }
    assert(digits == 7532, "descending");
    return 0;
}

How keys are ordered

Map and Set order keys with the generic function compare<K>(a, b), which returns a negative number, zero or a positive number as a sorts before, equal to or after b. Two keys that compare equal are the same key.

• Numbers and char compare by value, and String by content (the same order as String.compare).
• A struct that declares a < operator sorts by it: the generic compare asks a < b and b < a.
• Any other struct overrides compare<T> for itself, as a hashed key overrides hash<T> (see Overriding a generic function for one type).

# A struct with a `<` operator sorts by it.
struct Version {
    int major;
    int minor;

    construct(this.major = 0, this.minor = 0) {}

    <(other: Version): bool {
        return major < other.major or (major == other.major and minor < other.minor);
    }
}

# A struct without one overrides `compare<T>` for itself.
struct Point {
    int x;
    int y;

    construct(this.x = 0, this.y = 0) {}
}

compare<Point>(a: Point, b: Point): int {
    return a.x != b.x ? a.x - b.x : a.y - b.y;
}

main(): int {
    var releases = Map<Version, String>();
    releases[Version(1, 10)] = "third";
    releases[Version(0, 9)] = "first";
    releases[Version(1, 2)] = "second";
    assert(releases.first().value().1 == "first", "0.9 sorts first");
    assert(releases.last().value().1 == "third", "1.10 sorts last");

    var points = Set<Point>();
    points.insert(Point(2, 1));
    points.insert(Point(1, 5));
    # An equal point (compare returns 0) is the same member.
    assert(!points.insert(Point(1, 5)), "already a member");
    assert(points.first().value().x == 1, "sorted by x");
    return 0;
}

The order must be consistent: the same two keys must always compare the same way, and if a sorts before b and b before c, a sorts before c. A struct key whose fields change while it is in a map breaks that promise.

Insertion order: OrderedMap

OrderedMap<K, V> hashes its keys like HashMap, and iterates its entries in the order their keys were first inserted, like a Python dict. Setting the value of a key that is present keeps its place; removing a key and inserting it again moves it to the end. The other entries keep their order when one is removed.

main(): int {
    var config = OrderedMap<String, String>();
    config["name"] = "pepper";
    config["version"] = "0.2";
    config["license"] = "MIT";

    # Setting a key that is present keeps its place.
    config["name"] = "Pepper";

    # Removing a key and adding it again moves it to the end.
    config.remove("version");
    config["version"] = "0.3";

    var keys = "";
    for (var (key, value) in config) {
        keys = keys + key + " ";
    }
    assert(keys == "name license version ", "insertion order");

    if (config.try_get("license") is Value(license)) {
        assert(license == "MIT", "found");
    }
    assert(config.try_get("author").is_empty(), "absent");
    return 0;
}

Use it where the order of the input matters, such as the keys of a configuration file that should be written back as they were read.