Maps and sets

The standard library has three kinds of map, which differ in the order they keep their keys in, and a compact set of small integers, BitSet:

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 NaN float or double key sorts after every number (see Ordering with Comparable).
• A Comparable struct, or one that declares a < operator, sorts by it: the generic compare asks a < b and b < a.
• Any other struct declares Comparable, or 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.

Small integers: BitSet

BitSet is a set of non-negative ints that stores one bit per possible member, so a set whose largest member is m takes about m / 8 bytes however many members it holds. It suits visited flags, masks, and sieve or liveness tables over small integers; for sparse or large integers, use a HashSet<int>.

It has the set API above (insert, contains, remove, count, is_empty, clear) and iterates its members in ascending order. insert grows the set as needed and reserve(n) makes room for 0 to n - 1 ahead of time; it never shrinks. Inserting a negative number panics, while contains and remove of one return false. Changing the set while a loop iterates it is allowed: the loop sees the members above its position as they are when it reaches them.

The set operations come in two forms: union, intersection, difference and symmetric_difference return a new set, and union_with, intersect_with, difference_with and symmetric_difference_with change the set in place. is_subset and is_disjoint compare two sets. Two sets are ==, and hash equally, when they hold the same members whatever their capacity, so a BitSet works as a HashMap or HashSet key. An array converts to a BitSet, so an array literal can initialize one.

main(): int {
    # A sieve: every number below 50 starts out as a candidate.
    var composite = BitSet(50);
    var primes = BitSet();
    for (var n in 2..50) {
        if (composite.contains(n)) {
            continue;
        }
        primes.insert(n);
        var multiple = n * n;
        while (multiple < 50) {
            composite.insert(multiple);
            multiple = multiple + n;
        }
    }
    assert(primes.count == 15, "15 primes below 50");

    # Members come out in ascending order.
    var first = "";
    for (var p in primes) {
        if (p > 11) {
            break;
        }
        first = $"{first}{p} ";
    }
    assert(first == "2 3 5 7 11 ", "ascending");

    # Set operations, by value or in place.
    BitSet odd = [1, 3, 5, 7, 9, 11];
    var odd_primes = primes.intersection(odd);
    assert(odd_primes.count == 4, "3, 5, 7 and 11");
    assert(odd_primes.is_subset(primes), "a subset");
    odd.difference_with(primes);
    assert(odd == BitSet([1, 9]), "1 and 9 are odd but not prime");
    return 0;
}