std.collections

Indexable interface

pub interface Indexable<T>

What can be read and written with [i].

The same model as Iterator<T> for for-in: the compiler knows one built-in form — the array — and binds everything else to an interface from the standard library, so there is no special case per container type.

get and set are O(1). That is a requirement, not a description: an implementation with O(n) access must not satisfy this interface, or an index loop would be quadratic without showing it. string has no index operator for the same reason.

fn get(index: int): T

The value at index.

mut fn set(index: int, value: T): void

Replaces the value at index.

stdlib/std/collections.lyr:19

List class

pub class List<T> :: [Indexable<T>, Iterable<T>]

A growing list; a T[] has a fixed length, this does not.

Growing doubles and shrinking halves at a quarter, so push is amortized O(1) and a list oscillating around a boundary does not copy on every step.

data: (?T)[]

The backing slots; optional so a popped slot can actually release its value.

count: int

How many slots are filled.

pub fn length(): int

How many values are in it.

pub static fn empty(): List<T>

An empty list.

pub fn iter(): Iterator<T>

A fresh cursor on every call, so two loops over the same list do not disturb each other.

pub fn isEmpty(): bool

Whether nothing is in it.

pub fn capacity(): int

How many slots are allocated, empty ones included. For tests and for anyone measuring what the list costs; length is the truth for everything else.

pub mut fn push(value: T): void

Appends at the end; amortized O(1).

pub mut fn pop(): ?T

Removes and returns the last value, or null for an empty list — an ordinary state, unlike an index out of range.

pub fn get(index: int): T

The value at index. Out of range is a panic, as for an array: a programming error rather than a state.

pub mut fn set(index: int, value: T): void

Replaces the value at index. Out of range is a panic, as in get.

pub mut fn clear(): void

Empties the list and releases every slot.

pub fn toArray(): T[]

A copy as a real array.

stdlib/std/collections.lyr:41

emptyList function

pub fn emptyList<T>(): List<T>

An empty list.

stdlib/std/collections.lyr:170

ListIterator class

pub class ListIterator<T> :: [Iterator<T>]

Walks a list; each loop holds its own cursor.

source: List<T>

The list being walked.

index: int

The next slot to look at.

pub mut fn next(): ?T

The next value, or null at the end.

stdlib/std/collections.lyr:176

collect function

pub fn collect<T>(source: Iterator<T>): List<T>

Collects an iterator into a List<T>.

Here rather than in std.iter, because the dependency runs this way: std.collections imports std.iter, not the reverse. std.iter.collectArray is the variant without that dependency, and it is quadratic because a T[] copies on every append. This one doubles and is linear.

stdlib/std/collections.lyr:198

Map class

pub class Map<K :: [Hashable<K>, Equatable<K>], V>

A hash map: open addressing, linear probing, load factor 3/4. The key type says how to hash and how to compare — [Hashable<K>, Equatable<K>] — and the iteration order is UNSPECIFIED.

keys: (?K)[]

The key column; states says which slots are real.

values: (?V)[]

The value column, parallel to keys.

states: int[]

Per slot: 0 empty, 1 occupied, 2 tombstone.

count: int

The occupied slots alone.

used: int

Occupied plus tombstones — what the load factor is measured over.

pub fn length(): int

How many values are in it.

pub fn isEmpty(): bool

Whether nothing is in it.

pub static fn empty(): Map<K, V>

An empty map, with room for the first insertions before a growth.

pub fn containsKey(key: K): bool

Whether the key is in the map.

pub fn get(key: K): ?V

The value for the key, or null when the key is absent.

pub mut fn set(key: K, value: V): void

Inserts, or overwrites the existing entry for an equal key.

pub mut fn remove(key: K): ?V

Removes and returns the old value, or null when the key was absent.

stdlib/std/collections.lyr:224

emptyMap function

pub fn emptyMap<K :: [Hashable<K>, Equatable<K>], V>(): Map<K, V>

An empty map.

stdlib/std/collections.lyr:390

sortList function

pub fn sortList<T :: [Ordered<T>]>(xs: List<T>): void

Sorts in place by the natural order of the type.

stdlib/std/collections.lyr:411

sortListBy function

pub fn sortListBy<T>(xs: List<T>, less: fn(T, T) -> bool): void

Sorts in place with a comparison of your own.

less(a, b) must return true when a comes STRICTLY before b. A less returning true for equal elements destroys stability; a contradictory less makes the output arbitrary but crashes nothing, because the algorithm only compares.

stdlib/std/collections.lyr:420

Set class

pub class Set<T :: [Hashable<T>, Equatable<T>]>

A hash set: the same probing as Map, without the value column. Iteration order is UNSPECIFIED.

items: (?T)[]

The element column; states says which slots are real.

states: int[]

Per slot: 0 empty, 1 occupied, 2 tombstone.

count: int

The occupied slots alone.

used: int

Occupied plus tombstones — what the load factor is measured over.

pub fn length(): int

How many values are in it.

pub fn isEmpty(): bool

Whether nothing is in it.

pub static fn empty(): Set<T>

An empty set.

pub fn contains(value: T): bool

Whether the value is in the set.

pub mut fn add(value: T): bool

Adds and returns true when the value was NEW.

The return value saves a preceding contains, which would probe twice.

pub mut fn remove(value: T): bool

Removes and returns true when the value was present.

pub fn iter(): Iterator<T>

A fresh cursor on every call.

stdlib/std/collections.lyr:511

SetIterator class

pub class SetIterator<T :: [Hashable<T>, Equatable<T>]> :: [Iterator<T>]

Walks the occupied slots. The order follows the hashes and is therefore UNSPECIFIED; a caller that needs one sorts.

source: Set<T>

The set being walked.

index: int

The next slot to look at.

pub mut fn next(): ?T

The next value, or null at the end.

stdlib/std/collections.lyr:648

emptySet function

pub fn emptySet<T :: [Hashable<T>, Equatable<T>]>(): Set<T>

An empty set.

stdlib/std/collections.lyr:668

union function

pub fn union<T :: [Hashable<T>, Equatable<T>]>(a: Set<T>, b: Set<T>): Set<T>

Everything in either set, as a NEW set; neither argument changes.

stdlib/std/collections.lyr:676

intersect function

pub fn intersect<T :: [Hashable<T>, Equatable<T>]>(a: Set<T>, b: Set<T>): Set<T>

Everything in both sets, as a NEW set; neither argument changes.

stdlib/std/collections.lyr:688

difference function

pub fn difference<T :: [Hashable<T>, Equatable<T>]>(a: Set<T>, b: Set<T>): Set<T>

Everything in a that is not in b, as a NEW set; neither argument changes.

stdlib/std/collections.lyr:702

isSubset function

pub fn isSubset<T :: [Hashable<T>, Equatable<T>]>(a: Set<T>, b: Set<T>): bool

Whether every element of a is in b.

stdlib/std/collections.lyr:713

MapKeyIterator class

pub class MapKeyIterator<K :: [Hashable<K>, Equatable<K>], V> :: [Iterator<K>]

Walks the keys; the order follows the hashes and is UNSPECIFIED.

source: Map<K, V>

The map being walked.

index: int

The next slot to look at.

pub mut fn next(): ?K

The next key, or null at the end.

stdlib/std/collections.lyr:734

MapValueIterator class

pub class MapValueIterator<K :: [Hashable<K>, Equatable<K>], V> :: [Iterator<V>]

Walks the values; the order follows the hashes and is UNSPECIFIED.

source: Map<K, V>

The map being walked.

index: int

The next slot to look at.

pub mut fn next(): ?V

The next value, or null at the end.

stdlib/std/collections.lyr:754

keys function

pub fn keys<K :: [Hashable<K>, Equatable<K>], V>(m: Map<K, V>): Iterator<K>

A fresh cursor over the keys.

stdlib/std/collections.lyr:774

values function

pub fn values<K :: [Hashable<K>, Equatable<K>], V>(m: Map<K, V>): Iterator<V>

A fresh cursor over the values.

stdlib/std/collections.lyr:779

listContains function

pub fn listContains<T :: [Equatable<T>]>(xs: List<T>, value: T): bool

Whether the value occurs, by equals; O(n).

stdlib/std/collections.lyr:790

listIndexOf function

pub fn listIndexOf<T :: [Equatable<T>]>(xs: List<T>, value: T): ?int

The position of the first occurrence, or null when there is none.

stdlib/std/collections.lyr:802