Map Module¶

Creating maps¶

An empty map can be created with map() or with an empty brace expression:

a = map();
b = {};

The map() function creates a map whose arguments are added as values with automatic integer keys starting at 0:

// Equivalent to: {0 : 2, 1 : 3, 2 : 5, 3 : 7}
primes = map(2, 3, 5, 7);

The brace syntax can declare either a list of values or explicit key-value pairs:

a = {10, 20, 30};
b = {
    "name" : "truck",
    "capacity" : 12,
    5 : "manual key",
    "automatic key"
};

Values without an explicit key receive an automatic integer key. The automatic key is the largest integer key currently present in the map plus one, or 0 if the map contains no integer key:

// "first" is stored at key 0 because no integer key existed yet.
m = {
    "name" : "alpha",
    "first"
};

// "eleven" is stored at key 11.
n = {
    10 : "ten",
    "eleven"
};

If the same key is set several times, the last non-nil value is retained. If the last assignment for a key is nil, the key is removed.

The brace syntax accepts string keys, identifier keys, integer keys, and negative integer keys. Other key types can still be used by assigning through the bracket notation.

Keys¶

All values except nil can be used as map keys. Integer keys are used for array-like maps. String keys can be written either with bracket notation or, for identifier-like names, with member notation:

m = {};
m[12] = "integer key";
m[-41.3] = "double key";
m["color"] = "red";
m.color = "orange"; // Equivalent to: m["color"] = "orange"

Member notation is resolved as a string key first. If the string key is absent, normal Map members such as count(), keys(), values(), add(), sort(), set() and unset() can be found:

m = {};
n = m.count(); // Calls the `count` method.

m.count = 7; // Stores 7 at key "count".
v = m.count; // Reads key "count".

Prefer bracket notation for entries whose names can conflict with map methods.

Boolean keys follow the same ordering and lookup behavior as integer keys: false behaves as key 0 and true behaves as key 1.

Get and set values¶

The bracket notation gets and sets entries:

m = {};
m[0] = "zero";
m["name"] = "warehouse";

x = m[0]; // "zero"
y = m[1]; // nil

The set() and unset() methods provide the same update behavior:

m.set("name", "depot");
m.unset("name");

Assigning nil is equivalent to unsetting the key:

m["name"] = nil; // Removes key "name".

Using nil as a key is an error:

m[nil] = 1; // Error.

Implicit map creation¶

Maps are implicitly created when an assignment needs to insert a first element. If the left-hand side of an assignment starts from a variable whose value is nil, and that variable is indexed or accessed with member notation, the modeler first creates an empty map and then performs the assignment:

a["foo"] = 12; // Creates a map `a` and stores 12 at key "foo".
b.color = "red"; // Creates a map `b` and stores "red" at key "color".

This also applies to iterated assignments. The following statement creates the map a if it does not already exist, then fills it with the values produced by the iteration:

a[i in 1..100] = i;

This compact syntax is equivalent to:

for [i in 1..100]
    a[i] = i;

The same mechanism applies to missing intermediate entries in chained assignments. Whenever an intermediate entry is nil, it is replaced by a new empty map so that the assignment can continue:

// Creates `data`, `data["customer"]` and `data["customer"]["address"]`
// if they are missing.
data.customer.address.city = "Paris";

Implicit creation only happens in assignment contexts. A normal read of a missing entry still returns nil. Existing non-nil values are not silently replaced by maps: if an intermediate value cannot be indexed or accessed as a member, the assignment raises an error.

Automatic integer keys¶

add(value) appends a value and receives an automatic integer key. The automatic key is the largest integer key currently present in the map plus one, or 0 if the map contains no integer key:

m = {};
m.add("a"); // key 0
m.add("b"); // key 1

m[10] = "ten";
m.add("eleven"); // key 11

Only integer keys are considered when choosing the next automatic key. Non-integer keys do not affect it:

m = {};
m["name"] = "alpha";
m.add("first"); // key 0

Removing the largest integer key can change the next automatic key:

m = {"am", "stram", "gram"};
m.unset(2);
m.add(4); // key 2

Iterating throught maps¶

Maps can be iterated with for loops. The syntax for [v in m] iterates over the values of the map. The syntax for [k, v in m] iterates over the key-value pairs:

m = {"a", "b", "c"};

for [v in m] {
    println(v);
}

for [k, v in m] {
    println(k, ":", v);
}

Maps are iterated by key order, not insertion order. The key order is described below. This key order is also used by keys() and values().

Iterators detect concurrent modification. If a map is modified after an iterator has been created, the next iterator step raises an error.

Default Order¶

The map module uses the concept of default sort order in two places:

• For map keys. A map can contain any type of key. Internally, maps are organized in ascending key order. The order of the keys is determined by the rules specified below.
• In the sort() function when no comparator is specified.

Integers are ordered before doubles. Integer values are ordered by increasing numeric value. Boolean values behave as integer values for ordering purposes: false is ordered as 0 and true as 1.

Doubles are ordered by increasing numeric value. nan values are ordered after non-nan doubles. Two nan values compare as equal.

Other values, such as strings, ranges, maps, dates, expressions, or other objects, are ordered after integers and doubles. When both values have the same type and that type defines a comparator, the type comparator is used. For example, strings are ordered lexicographically and ranges are ordered by their bounds.

When values have different types, or when their type does not define a value comparator, the implementation falls back to a stable internal order based on runtime type objects and object addresses. This order remains stable during one execution, but it should not be relied on across executions.

String Representation¶

When a map is converted to a string (in a println for instance), entries are printed in iteration order between braces. Consecutive integer keys are omitted when the key is exactly the previous integer key plus one. Other keys are printed with the key : value form:

{10, 20, 30} // Printed without explicit keys.
{2 : "c"} // Key 2 is printed because keys 0 and 1 are absent.

Recursive maps are protected from infinite stringification. A nested reference to a map that is already being printed is displayed as {...}.

Internal representation¶

The map implementation chooses an internal representation lazily.

An empty map starts with no storage.

When a map contains non-negative integer keys exclusively and that keys are dense enough, the implementation can use a generic contiguous memory block, which is traditionnally called an array in other languages. Lookups by integer key are then O(1).

When keys are negative, non-integer, or integer keys become too sparse, the implementation uses a red-black tree. Tree lookups, insertions, and removals are O(log(n)) after the key has been compared.

Changing a map can promote it from a compact representation to a more general one. For example, inserting a non-integer key into an array-like map promotes it to the tree representation.

Read-only Maps¶

Some maps returned by the modeler or by standard-library modules can be marked read-only. Attempting to modify a read-only map raises an error. Read-only maps can still be read, iterated, sorted, and queried with count(), keys() and values().

Classes¶

class Map¶

This is the base type for maps.

count()¶

Returns the number of entries stored in the map.

Return type:	int

values()¶

Returns the values of the map in a new map. Original keys are ignored. Values are returned in iteration order and indexed from 0 to n - 1.

Return type:	map

keys()¶

Returns the keys of the map in a new map. Original values are ignored. Keys are treated as values in the returned map and indexed from 0 to n - 1.

Return type:	map

add(value)¶

Adds value with an automatic integer key. The key is the largest integer key currently present in the map plus one, or 0 if the map contains no integer key. Adding nil has no effect.

The complexity of this operation is O(1) or O(log(n)), depending on the internal representation currently used for the map (array or red-black tree).

set(key, value)¶

Sets the value associated with key. This is equivalent to map[key] = value. The key cannot be nil. If value is nil, the key is removed.

The complexity of this operation is amortized O(1) or O(log(n)), depending on the internal representation currently used for the map (array or red-black tree).

unset(key)¶

Removes key from the map if it is present. The key cannot be nil. Removing an absent key has no effect.

Note: This operation has no effect on the keys of other elements. In particular, unset does not reindex elements that come after the unset element.

The complexity of this operation is O(1) or O(log(n)), depending on the internal representation currently used for the map (array or red-black tree).

sort()¶

sort(cmpFunc)

Returns a new map containing the values of the original map in sorted order. Original keys are ignored, and the resulting map is indexed from 0 to n - 1.

If cmpFunc is provided, it is used as the comparison function. The function receives two values a and b and must return a number: a negative number if a is ordered before b, a positive number if a is ordered after b, and zero if they are equal for this sort.

If no comparison function is provided, values are sorted according to the default order described above.

This sort is stable: values that compare as equal keep their relative iteration order from the original map. The complexity is O(n log(n)).

Return type:	map