std/collections

The collection traits every signature talks about, and the implementations that only show up where one is built.

The generated reference of std/collections has every public construct with its signature, its doc comment and its examples.

std/collections is one trait per kind of collection - List, Map, Set, Stack, Queue - and the implementations behind them. A signature, a field or a binding names the trait; the implementation (ArrayList, HashMap, ...) only shows up where something is constructed. Every name below is already in scope through the prelude.

An Array is not a collection, and it is not here: it is the inline storage primitive a data structure is written on top of, so it lives in std/core next to the other types the language itself refers to.

Import#

use List, ArrayList, RingList, Map, TrieMap, Set, TrieSet from "std/collections"
use Stack, ArrayStack, Queue, ArrayQueue from "std/collections"

var numbers: List<Int> = [3, 1, 2]
numbers.append 4
print numbers.reversed()

Declarations#

Every kind comes with Iterate<Item>, Length directly and spends the words everybody knows for its structure: a list appends, a set inserts, a map sets, a stack pushes and pops, a queue enqueues and dequeues. There is no shared Collection trait and no shared add. clear, compact, contains and count are declared by each kind that has them, and count() answers length() rather than walking. A collection is not an Accumulator: what gathers a pipeline into one is a type beside it (ListAccumulator, into<Target>() - see std/iteration).

List#

trait List<Item> with Iterate<Item>, Length, MutableIndex<Int, Item>, MutableSlice {
  static fn of(...items: Item): Self where Self: From<Iterate<Item>>
  static fn filled(count: Int, value: Item): Self where Self: From<Iterate<Item>>
  fn keys(): Iterate<Int>
  var fn append(value: Item)
  var fn appendAll(values: Iterate<Item>)
  var fn insert(index: Int, value: Item)
  var fn removeAt(index: Int): Item?
  var fn reverse()
  var fn clear()
  var fn compact()
  var fn sort<Key: Compare>(by: Transform<Item, Key>)
  fn sorted<Key: Compare>(by: Transform<Item, Key>): Self
  var fn remove(value: Item): Bool where Item: Equals
  fn slice(range: Bounds<Int>): Self
  fn part(range: Bounds<Int>): Self?
  fn windows(size: Int): Iterate<Self>
  fn chunks(size: Int): Iterate<Self>
  fn splitAt(index: Int): (before: Self, after: Self)?
  var fn replace(range: Bounds<Int>, values: Self)
  var fn swapAt(first: Int, second: Int)
  var fn update(index: Int, change: (var element: Item) => Void)
  fn appended(value: Item): Self
  fn appendedAll(values: Iterate<Item>): Self
  fn inserted(index: Int, value: Item): Self
  fn updated(index: Int, value: Item): Self
  fn removedAt(index: Int): Self
  fn removed(value: Item): Self where Item: Equals
  fn reversed(): Self
  fn count(): Int
  fn contains(value: Item): Bool where Item: Equals
  fn first(): Item?
  fn last(): Item?
  fn indexOf(value: Item): Int? where Item: Equals
}
extend<Item> List<Item> with From<Iterate<Item>>
extend<Item: Show> List<Item> with Show
extend<Item: Equals> List<Item> with Equals
extend<Item: Hash> List<Item> with Hash

An ordered sequence, addressable by index - the type of the literal [1, 2, 3]. Every verb (append, insert, removeAt, reverse, sort, remove, swapAt, update) needs a var path and has a participle that returns a changed copy (appended, inserted, removed, reversed, ...). sorted is one of them: it overrides the lazy Iterate.sorted stage and answers a list of the same kind. compact() hands back whatever storage the list holds beyond its length. ArrayList is the default implementation, a contiguous growable buffer shared between copies and slices until one of them is written to; TrieList is a bit-partitioned trie for a list kept in many versions at once, and is a documented alias of ArrayList until the trie exists. RingList is a ring buffer behind the same vocabulary: append, insert(0, ...) and removeAt(0) are O(1) amortised, which is what a deque needs, and a slice of it is a copy. There is no Deque trait: every signature that says List<Item> takes a RingList.

list[index] panics with index 9 is out of bounds for a length of 3 where get(index) answers None, and list[from..to] panics where part(from..to) answers None: every partial read has its total twin beside it. keys() is 0..length(), the indices for var item in items walks to change every item in place (Changing elements in place).

ArrayList.withCapacity(capacity) builds an empty list with room for capacity items before it has to grow again - what to reach for ahead of a loop of appends whose count is already known, instead of the default empty list that grows as it goes. TrieList, TrieMap, HashMap, TrieSet and HashSet each have the same static member, for the same reason.

Map#

trait Map<Key, Value> with Iterate<(key: Key, value: Value)>, Length, MutableIndex<Key, Value> {
  static fn of(...entries: (Key, Value)): Self where Self: From<Iterate<(Key, Value)>>, Key: Hash
  var fn remove(key: Key): Value?
  var fn clear()
  var fn getOrInsert(key: Key, fallback: lazy Value): Value
  var fn update(key: Key, fallback: lazy Value, change: (var Value) => Void)
  fn updated(key: Key, value: Value): Self
  fn removed(key: Key): Self
  fn count(): Int
  fn containsKey(key: Key): Bool
  fn keys(): Iterate<Key>
  fn values(): Iterate<Value>
  fn mapValues<Output>(transform: Transform<Value, Output>): Map<Key, Output> where Key: Hash
}
extend<Key: Hash, Value> Map<Key, Value> with From<Iterate<(Key, Value)>>
extend<Key: Show, Value: Show> Map<Key, Value> with Show
extend<Key, Value: Equals> Map<Key, Value> with Equals
extend<Key: Hash, Value: Hash> Map<Key, Value> with Hash

map[key] of a missing key panics with the key "Alan" is not in the map - the key as it shows inside of another value, cut after 60 characters, or the key alone where its type has no Show - and get(key) answers None.

Mapping from keys to values, iterated as (key, value) tuples. Its verb is set (map[key] = value), whose participle is updated, and for (key, var value) in map changes every value in place. The trait asks nothing of Key; what a key has to be able to do is a matter of the implementation (TrieMap and HashMap need Hash). Every implementation iterates in insertion order, and removing an entry does not reorder the rest; an empty map shows as [:]. TrieMap is the default (a hash array mapped trie, cheap to keep in many versions); HashMap is a flat hash table with the fastest lookups and writes, at the cost of copying all of a shared table on a write.

Set#

trait Set<Item> with Iterate<Item>, Length {
  static fn of(...items: Item): Self where Self: From<Iterate<Item>>, Item: Hash
  fn contains(value: Item): Bool
  fn count(): Int
  var fn insert(value: Item)
  var fn insertAll(values: Iterate<Item>)
  var fn remove(value: Item): Bool
  var fn removeAll(values: Iterate<Item>)
  var fn retainAll(values: Set<Item>)
  var fn clear()
  fn inserted(value: Item): Self
  fn insertedAll(values: Iterate<Item>): Self
  fn removed(value: Item): Self
  static fn union(first: Self, second: Self): Self
  static fn intersection(first: Self, second: Self): Self
  static fn difference(first: Self, second: Self): Self
}
extend<Item: Hash> Set<Item> with From<Iterate<Item>>
extend<Item: Show> Set<Item> with Show
extend<Item: Equals> Set<Item> with Equals
extend<Item: Hash> Set<Item> with Hash

A collection without duplicates; insert of a value already present does nothing. The set operations (union, intersection, difference) are nouns and never change anything, unlike the verbs above them. {a, b} is how a set shows - braces, so a set is never mistaken for a list, and {} is empty. TrieSet and HashSet mirror TrieMap and HashMap.

Stack and Queue#

trait Stack<Item> with Iterate<Item>, Length {
  static fn of(...items: Item): Self where Self: From<Iterate<Item>>
  var fn push(value: Item)
  var fn pop(): Item?
  var fn clear()
  var fn compact()
  fn peek(): Item?
  fn count(): Int
}
extend<Item> Stack<Item> with From<Iterate<Item>>
extend<Item: Equals> Stack<Item> with Equals
extend<Item: Hash> Stack<Item> with Hash
trait Queue<Item> with Iterate<Item>, Length {
  static fn of(...items: Item): Self where Self: From<Iterate<Item>>
  var fn enqueue(value: Item)
  var fn dequeue(): Item?
  var fn clear()
  var fn compact()
  fn peek(): Item?
  fn count(): Int
}
extend<Item> Queue<Item> with From<Iterate<Item>>
extend<Item: Equals> Queue<Item> with Equals
extend<Item: Hash> Queue<Item> with Hash

Stack is LIFO and iterates from top to bottom: push puts an item on top, pop takes it off, peek looks at it without taking it. Queue is FIFO and iterates front to back: enqueue puts an item at the back, dequeue takes the one at the front, peek looks at the front. Neither has participles - a stack or a queue is a value, so a var copy is taken from while the original keeps every item. ArrayStack is a List underneath; ConsStack is a persistent cons list whose copies share their tail, with push and pop in O(1); ArrayQueue is a ring buffer that grows only when it is full; BankersQueue is two linked lists that copies share, for a queue kept in many versions. Each of the four types is Equals and Hash wherever Item is, order-dependent like a List. BankersQueue.iterate copies both lists into a List, so iterating a large queue again and again allocates O(n) each time.

Heap<Item> is the priority structure and is not a Queue: a binary heap over a List that carries its order as a function, Heap.by { job => job.priority }. insert(value) and removeSmallest(): Item? are O(log n), peekSmallest(): Item? is O(1), clear, length and isEmpty come as for a stack. It iterates smallest key first over a sorted copy (O(n log n)) and leaves the heap as it was; items with equal keys come out in no promised order.

Flags#

type Flags<Case: RawValue> with Iterate<Case>, Length, From<Iterate<Case>>, TryFrom<UInt64, FlagsError> {
  static fn of(...cases: Case): Self
  static fn from(cases: Iterate<Case>): Self
  static fn fromBits(mask: UInt64): Result<Self, FlagsError>
  static fn tryFrom(value: UInt64): Result<Self, FlagsError>
  fn bits(): UInt64
  fn contains(flag: Case): Bool
  fn length(): Int
  var fn insert(flag: Case)
  var fn insertAll(flags: Iterate<Case>)
  var fn remove(flag: Case): Bool
  var fn removeAll(flags: Iterate<Case>)
  var fn clear()
  fn inserted(flag: Case): Self
  fn removed(flag: Case): Self
  static fn union(first: Self, second: Self): Self
  static fn intersection(first: Self, second: Self): Self
  static fn difference(first: Self, second: Self): Self
  fn iterate(): Iterator<Case>
}
extend<Case: RawValue & Show> Flags<Case> with Show

A set of the cases of a type whose cases stand for powers of two (case Read = 1, Cases that stand for numbers), stored as one bit mask: the flags of a C API, a file format or a protocol. A list literal builds one, it has the words of a Set, and it iterates over the cases that are set in the order of their bits - which is why it is no Set, whose order is the insertion order. The checker holds every case of the type argument to be a power of two wherever Flags<Case> is written or inferred. bits() and UInt64.from(flags) write the mask, fromBits and tryFrom read one back and answer FlagsError for a bit no case stands for, and that pair is how a value is encoded: as the number, or, where the format asks for names (Json(flagsAsNames: true)), as the list of the case names (["Read","Write"]). Not in the prelude: use Flags from "std/collections".

Mutation and var paths - what has to be var for a verb like append or sort.
std/iteration - Iterate, the lazy stages and the collectors every collection works with.
The standard library - the other packages.