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. Every slot is released — nothing inserted stays alive — but the backing array is KEPT: a buffer emptied once per frame must not reallocate on every refill.

pub fn first(): ?T

The first value, or null for an empty list.

pub fn last(): ?T

The last value, or null for an empty list.

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

Inserts at index, shifting everything from there one to the right. index == length() appends. Out of range is a panic, as in get.

pub mut fn removeAt(index: int): T

Removes and returns the value at index, shifting the rest left. Out of range is a panic, as in get.

pub mut fn reverse(): void

Reverses in place.

pub mut fn swap(a: int, b: int): void

Exchanges two positions. Out of range is a panic, as in get.

pub fn toArray(): T[]

A copy as a real array.

stdlib/std/collections.lyr:41

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:253

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:275

Deque class

pub class Deque<T>

A double-ended queue: push and pop are O(1) at BOTH ends.

Deliberately without iteration for now: a run queue is drained, not walked, and popFront in a loop IS its walk. null from a pop or peek means "empty" — an ordinary state, like a List pop, and the whole truth, so there is no throwing twin.

data: (?T)[]

The backing ring; optional so a popped slot releases its value.

head: int

The index of the front value, meaningful while count > 0.

count: int

How many slots are filled.

pub static fn empty(): Deque<T>

An empty deque.

pub fn length(): int

How many values are in it.

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 deque costs; length is the truth for everything else.

pub mut fn pushBack(value: T): void

Appends at the back; amortized O(1).

pub mut fn pushFront(value: T): void

Prepends at the front; amortized O(1) — the ring is the reason no slot moves.

pub mut fn popFront(): ?T

Removes and returns the front value, or null when empty.

pub mut fn popBack(): ?T

Removes and returns the back value, or null when empty.

pub fn peekFront(): ?T

The front value without removing it, or null when empty.

pub fn peekBack(): ?T

The back value without removing it, or null when empty.

pub mut fn clear(): void

Empties the deque; the backing stays allocated, as List.clear keeps its.

stdlib/std/collections.lyr:301

Map class

pub class Map<K :: [Hashable<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>] — 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 fn getOr(key: K, fallback: V): V

The value for the key, or fallback when the key is absent — one probe instead of a containsKey before every get.

pub mut fn clear(): void

Empties the map. The backing arrays are KEPT, as in List.clear; the tombstones vanish with everything else.

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

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

stdlib/std/collections.lyr:436

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:638

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:647

Set class

pub class Set<T :: [Hashable<T>]> :: [Iterable<T>]

A hash set: the same probing as Map, without the value column. Iteration order is UNSPECIFIED. Iterable, so for (v in set) walks it directly.

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 mut fn clear(): void

Empties the set. The backing arrays are KEPT, as in List.clear; the tombstones vanish with everything else.

pub fn iter(): Iterator<T>

A fresh cursor on every call.

stdlib/std/collections.lyr:738

SetIterator class

pub class SetIterator<T :: [Hashable<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:888

union function

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

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

stdlib/std/collections.lyr:910

intersect function

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

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

stdlib/std/collections.lyr:922

difference function

pub fn difference<T :: [Hashable<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:936

isSubset function

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

Whether every element of a is in b.

stdlib/std/collections.lyr:947

MapKeyIterator class

pub class MapKeyIterator<K :: [Hashable<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:968

MapValueIterator class

pub class MapValueIterator<K :: [Hashable<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:988

MapEntryIterator class

pub class MapEntryIterator<K :: [Hashable<K>], V> :: [Iterator<(K, V)>]

Walks key and value TOGETHER; the order follows the hashes and is UNSPECIFIED.

Without this, walking both meant iterating keys and paying a second probe per key through get.

source: Map<K, V>

The map being walked.

index: int

The next slot to look at.

pub mut fn next(): ?(K, V)

The next (key, value) pair, or null at the end.

stdlib/std/collections.lyr:1011

keys function

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

A fresh cursor over the keys.

stdlib/std/collections.lyr:1035

values function

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

A fresh cursor over the values.

stdlib/std/collections.lyr:1040

entries function

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

A fresh cursor over (key, value) pairs:

for (entry in entries(m)) { let (k, v) = entry; … }

stdlib/std/collections.lyr:1047

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:1058

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:1070