Reference

std/collections/list

std/collections/src/list.trb

The ordered, indexable sequence: List, its default implementation ArrayList, and the trie-backed TrieList.

List<Item> is the type of the literal [1, 2, 3]. Every change has a verb that needs a var path plus a participle that answers a changed copy and works on a const list too, so the same operation is written the same way regardless of which kind of binding holds the list.

Related

trait List

trait List<Item> with Iterate<Item>, Length, MutableIndexed<Int, Item>, MutableSlice

An ordered sequence, addressable by index. This is the type of the literal [1, 2, 3].

Every change has a verb that changes the list in place through a var path, and a participle that answers a changed copy and works on a const list too: append/appended, insert/inserted, remove/removed, removeAt/removedAt, sort/sorted, reverse/reversed.

Examples

var numbers = [3, 1, 2]
numbers.append 4
numbers[0] = 5
for number in numbers {
  print number
}

A verb needs a var path; its participle answers a changed copy and works on a const list too:

const numbers = [3, 1, 2]
const more = numbers.appended 6
print more

list[index] is itself a var path, so an element is changed in place without reading it out first:

type Counter {
  var count: Int = 0
  var fn increment() {
    count = count + 1
  }
}

var counters = [Counter(), Counter()]
counters[0].increment()
print counters[0].count

Pitfalls

  • A binding read out of the list copies the value there and then: var first = counters[0] takes a copy of the element above, so changing first afterward never touches counters. See MutableIndexed for the rule.

Related

  • Iterate - the pipeline vocabulary (map, filter, fold, ...) every list has.
  • Slice and MutableSlice - list[from..to], a List again, as a value and as a var path.

fn of

static fn of(...items: Item): Self where Self: From<Iterate<Item>>

Builds a list from its arguments: List.of(1, 2, 3), or with a spread, List.of(...anyIterate).

It answers Self, so TrieList.of(1, 2) is a TrieList and not somebody else's list. The requirement is on the member and not on the trait, because an implementation may need more of Item than List does.

fn filled

static fn filled(count: Int, value: Item): Self where Self: From<Iterate<Item>>

Builds a list of count copies of value: List.filled(3, "-") is ["-", "-", "-"].

fn append

var fn append(value: Item)

Appends value at the end, in place.

fn appendAll

var fn appendAll(values: Iterate<Item>)

Appends every value of values, in order, in place.

fn insert

var fn insert(index: Int, value: Item)

Inserts value at index, in place; shifts everything at or after it one position on.

fn removeAt

var fn removeAt(index: Int): Item?

Removes the item at index and answers it, or None if index is out of range.

fn reverse

var fn reverse()

Reverses the order, in place.

fn clear

var fn clear()

Removes every item, in place.

fn compact

var fn compact()

Gives the list storage of its own, sized exactly to its length. For the small part of something big that is kept for a long time: var header = file[0..64], then header.compact().

The default does nothing, which is the honest answer for a storage that keeps no spare room; an implementation that holds capacity beyond its length hands it back here.

fn sort

var fn sort<Key: Compare>(by: Transform<Item, Key>)

Sorts in place, by a key: names.sort { _.length() }. Stable - two values with the same key keep their order.

It is a default and not a required member, and it is written here and not in an implementation, because the comparison is a closure of the program: a C function cannot call one, so torb_list_sort could only be reached with a convention for handing a closure to the runtime - and one implementation of a sort that every list shares is worth more than that convention. A member with generic parameters of its own is no slot of a witness table either (its witnesses would have to be appended), so writing it as a default is also what makes sort reachable on a List<Item> value at all: a default nothing overrides is dispatched with Self bound to the trait type.

Bottom-up merge sort: n log n comparisons, stable, no recursion, and one buffer that is copied once.

Examples

var names = ["Grace", "Ada", "Alan"]
names.sort { name => name.byteLength() }
print names

fn sorted

fn sorted<Key: Compare>(by: Transform<Item, Key>): Self

The participle of List.sort: a list of the same kind, sorted by the key, with this one left alone.

It overrides Iterate.sorted, which is a lazy stage answering Iterate<Item>. A participle answers Self, so on a list it answers a list and const ordered: List<Int> = numbers.sorted({ _ }) needs no toList() after it.

Examples

const names = ["Grace", "Ada", "Alan"]
print names.sorted({ name => name.byteLength() })

fn remove

var fn remove(value: Item): Bool where Item: Equals

Removes the first value and answers whether one was found, in place.

Examples

var numbers = [1, 2, 3, 2]
numbers.remove 2
print numbers

fn slice

fn slice(range: Bounds<Int>): Self

numbers[1..3]: the items of that part, as a list of the same kind.

ArrayList answers it natively, where it is O(1) and shares the storage - which is what a slice of a concrete list is - and a trait-typed List<Item> reaches that answer too: a member that answers exactly Self has a slot in the witness table, whose function boxes the implementation's answer with the table, and the call site puts it into the receiver's own tables (docs/PERFORMANCE.md, F16). This default is what a list that does not answer it itself runs, and it costs one copy of the part.

Examples

const numbers = [1, 2, 3, 4, 5]
print numbers[1..3]

Panics

When the range reaches outside the list, or starts after it ends. The two messages are the runtime's, word for word: a back end may not disagree with the other about them.

fn part

fn part(range: Bounds<Int>): Self?

The items the range covers, as a list of the same kind, or None where the range reaches outside the list or starts after it ends: the total twin of numbers[1..3], which panics there instead.

Examples

const numbers = [1, 2, 3]
print numbers.part(1..3)
print numbers.part(2..5)

fn windows

fn windows(size: Int): Iterate<Self>

Every run of size neighbouring items, in order, each a list of the same kind: [1, 2, 3].windows(2) is [1, 2] and [2, 3]. A list shorter than size has no window, and neither has a size below one - so it never panics, and a loop over pairs of neighbours needs no index.

Examples

const readings = [3, 5, 4, 8]
const rises = readings.windows(2).filter({ pair => pair[1] > pair[0] }).count()
print rises

fn chunks

fn chunks(size: Int): Iterate<Self>

The items cut into consecutive lists of size items, in order; the last one holds what is left and may be shorter. [1, 2, 3, 4, 5].chunks(2) is [1, 2], [3, 4] and [5]. A size below one cuts nothing and answers no chunk at all, so it never panics.

Examples

const cells = ["a", "b", "c", "d", "e"]
for row in cells.chunks(2) {
  print row
}

fn splitAt

fn splitAt(index: Int): (before: Self, after: Self)?

The list cut in two at index: the items before it and the items from it on, or None where index is outside 0..=length(). The total form of (list[..index], list[index..]), as List.part is of one slice.

Examples

const line = [1, 2, 3, 4]
if const Some((head, rest)) = line.splitAt(1) {
  print "{head} {rest}"
}

fn replace

var fn replace(range: Bounds<Int>, values: Self)

numbers[1..3] = values: the items of that part replaced by values, in place. The two need not be the same length, so the list grows or shrinks by the difference.

It is also what puts a window back: numbers[1..4].sort() sorts the slice and then writes it back through this member, which is how a var path goes through a[from..to] (MutableSlice).

ArrayList answers it natively. This default is what a trait-typed List<Item> reaches, for the reason List.slice gives: values is a Self, so the member is in no witness table. It writes the overlapping items in place and inserts or removes the rest.

Examples

var numbers = [5, 3, 9, 1, 7]
numbers[1..3] = [0]
print numbers

Panics

When the range reaches outside the list, or starts after it ends, with the messages of List.slice.

fn swapAt

var fn swapAt(first: Int, second: Int)

Swaps the items at first and second, in place.

fn update

var fn update(index: Int, change: (var element: Item) => Void)

Changes one element in place: enemies.update(0) { enemy => enemy.health = 0 }

fn appended

fn appended(value: Item): Self

The participle of List.append: a changed copy with value at the end, for a const binding.

fn appendedAll

fn appendedAll(values: Iterate<Item>): Self

The participle of List.appendAll: a changed copy with every value of values at the end.

fn inserted

fn inserted(index: Int, value: Item): Self

The participle of List.insert: a changed copy with value inserted at index.

fn updated

fn updated(index: Int, value: Item): Self

The participle of list[index] = value: a changed copy with the item at index replaced.

fn removedAt

fn removedAt(index: Int): Self

The participle of List.removeAt: a changed copy with the item at index gone.

fn removed

fn removed(value: Item): Self where Item: Equals

The participle of List.remove: a changed copy with the first value gone.

fn reversed

fn reversed(): Self

The participle of List.reverse: a reversed copy.

fn count

fn count(): Int

How many items there are. A list knows its length, so counting it does not walk it.

fn contains

fn contains(value: Item): Bool where Item: Equals

Whether value is present: a scan of every item.

fn first

fn first(): Item?

The first item, or None if the list is empty.

fn last

fn last(): Item?

The last item, or None if the list is empty.

fn indexOf

fn indexOf(value: Item): Int? where Item: Equals

The index of the first value, or None if it is not present.

extend List<Item> with From<Iterate<Item>>

extend<Item> List<Item> with From<Iterate<Item>>

The factory picks the default implementation. This is also what makes toList() and to<List<Item>>() work.

fn from

static fn from(items: Iterate<Item>): List<Item>

extend List<Item> with Show

extend<Item: Show> List<Item> with Show

[1, 2, 3], and [] when it is empty - the format of the literal.

fn show

fn show(): String

extend List<Item> with Equals

extend<Item: Equals> List<Item> with Equals

Equal when they have the same length and equal items in the same order.

fn equals

fn equals(other: Self): Bool

extend List<Item> with Hash

extend<Item: Hash> List<Item> with Hash

Order-dependent, unlike Set.hash and Map.hash: two lists with the same items in a different order differ.

Hash requires Equals, and the Equals implementation above satisfies that: Item: Hash implies Item: Equals.

fn hash

fn hash(): Int

type ArrayList

native type ArrayList<Item> with List<Item>, From<Iterate<Item>>

Contiguous, growable buffer - the default. The buffer is shared between copies and slices and only copied when somebody writes to it while it is shared. Nobody can observe the difference.

fn from

static fn from(items: Iterate<Item>): ArrayList<Item>

Ordinary TorbScript, and it cannot be a function of the runtime: items is a trait-typed value of the program, so reading it means calling iterate and next through a witness table, which C code cannot do. withCapacity is what builds the empty buffer, and it is the one native the lowering answers itself - the element descriptor a buffer needs is a function of the language and no declaration can name one.

fn withCapacity

native static fn withCapacity(capacity: Int): ArrayList<Item>

An empty list, with room for capacity items before it has to grow again.

fn length

native fn length(): Int

How many items there are.

fn get

native fn get(index: Int): Item?

The item at index, or None if it is out of bounds. list[index] panics instead; see ArrayList.at.

fn at

fn at(index: Int): Item

The item at index. This is list[index].

Panics

When index is out of bounds, with index <index> is out of bounds for a length of <count> - the message every slice, set and insert of a list answers the same mistake with. ArrayList.get is the same question with an Option for an answer.

fn slice

fn slice(range: Bounds<Int>): ArrayList<Item>

The O(1) slice: it shares storage with the receiver until one of the two is written, whether the list is reached as an ArrayList or as a trait-typed List (see List.slice).

A list whose items may hold an object with a destructor gets a copy instead, so that an item the slice left out closes when the list it came from is gone (docs/design/DESTRUCTORS.md 2a).

Panics

When the range reaches outside the list, or starts after it ends, with the messages of List.slice.

fn iterate

fn iterate(): Iterator<Item>

Ordinary TorbScript over get: see ListIterator.

fn append

native var fn append(value: Item)

Appends an item at the end, in place.

fn set

native var fn set(index: Int, value: Item)

Changes the item at index in place. list[index] = value goes through this; see MutableIndexed.set.

fn insert

native var fn insert(index: Int, value: Item)

Inserts value at index, in place; shifts everything at or after it one position on.

fn removeAt

native var fn removeAt(index: Int): Item?

Removes the item at index and answers it, or None if index is out of range.

fn replace

var fn replace(range: Bounds<Int>, values: ArrayList<Item>)

Replaces the items of range with values, in place; the two need not be the same length. What list[from..to] = values goes through, and what puts a window back after list[1..4].sort(); see MutableSlice.replace.

Panics

When the range reaches outside the list, or starts after it ends, with the messages of List.slice.

fn reverse

native var fn reverse()

Reverses the order, in place.

fn clear

native var fn clear()

Removes every item, in place.

fn compact

native var fn compact()

Gives the list storage of its own, sized exactly to its length; see List.compact.

type TrieList

native type TrieList<Item> with List<Item>, From<Iterate<Item>>

Bit-partitioned trie. A write to a shared list copies one path (O(log n)) instead of the whole buffer: the one for big lists that are kept in many versions (undo, history, snapshots).

Until the trie exists, this name is a documented alias of ArrayList. Only performance differs: iteration order and Show are the same either way.

fn from

static fn from(items: Iterate<Item>): TrieList<Item>

Ordinary TorbScript, for the reason ArrayList.from gives: items is a trait-typed value of the program.

fn withCapacity

native static fn withCapacity(capacity: Int): TrieList<Item>

An empty list, with room for capacity items before it has to grow again.

fn length

native fn length(): Int

Same as ArrayList.length.

fn get

native fn get(index: Int): Item?

Same as ArrayList.get.

fn at

fn at(index: Int): Item

Same as ArrayList.at.

Panics

When index is out of bounds, with the message of ArrayList.at.

fn iterate

fn iterate(): Iterator<Item>

Ordinary TorbScript over get, exactly as ArrayList.iterate is: see TrieListIterator.

fn slice

fn slice(range: Bounds<Int>): TrieList<Item>

Same as ArrayList.slice.

Panics

When the range reaches outside the list, or starts after it ends, with the messages of List.slice.

fn append

native var fn append(value: Item)

Same as ArrayList.append.

fn set

native var fn set(index: Int, value: Item)

Same as ArrayList.set.

fn insert

native var fn insert(index: Int, value: Item)

Same as ArrayList.insert.

fn removeAt

native var fn removeAt(index: Int): Item?

Same as ArrayList.removeAt.

fn replace

var fn replace(range: Bounds<Int>, values: TrieList<Item>)

Same as ArrayList.replace.

Panics

When the range reaches outside the list, or starts after it ends, with the messages of List.slice.

fn reverse

native var fn reverse()

Same as ArrayList.reverse.

fn clear

native var fn clear()

Same as ArrayList.clear.

fn compact

native var fn compact()

Same as ArrayList.compact.