velt/collections

API reference

Containers beyond the prelude's arrays and Map, written in Velt on public APIs. Every type is exported from velt/collections itself; the files behind it are internal, and importing one (velt/collections/deque) is an error that names the module to use. For a walkthrough, read the guide.

import { Deque, PriorityQueue, SortedMap, BTreeMap, ConcurrentMap } from "velt/collections";

Exports

BTreeMapA map ordered by key, as a B+tree.ConcurrentMapA map from K keys (u64 or string; u64 when not written) to V values (u64 when not written) for many threads at once: share it (shared(ConcurrentMap.create(n))) and call its methods from any task.DequeA double-ended queue (ring buffer).PriorityQueueA priority queue (binary heap); pop returns the element that cmp orders first.SetAn insertion-ordered set of unique values.SortedMapA map ordered by key.InlineKeyThe bytes of a key that order as the keys do, for BTreeMap's node search.ReadonlySetTypeScript's ReadonlySet<T>: a Set<T> that a variable or parameter declared with this type may not change (add, delete and clear are errors through it).

class

BTreeMap

#std/collections/btree_map.vlt:22

Re-exported from velt/collections/btree_map

class BTreeMap<K extends Comparable<K>, V> implements Iterable<[K, V]>

A map ordered by key, as a B+tree.

constructor(entries: [K, V][] = [])

A map holding entries (a later entry replaces an earlier one with the same key).

get size(): usize

Number of entries.

isEmpty(): bool

Whether the map is empty.

clear()

Removes every entry.

set(key: K, value: V)

Inserts or replaces the value for key.

get(key: K): V | undefined

The value for key (shared, as Map.get returns it), or undefined.

getMany(keys: K[]): (V | undefined)[]

The values for keys, in order (undefined for a key that is not present), as get gives them. The lookups of a batch run interleaved, each one's next node loading while the others search theirs, so in a map larger than the CPU's caches a batch costs a fraction of as many gets.

has(key: K): bool

Whether key is present.

delete(key: K): bool

Removes key; returns whether it was present.

keys(): K[]

The keys, ascending.

values(): V[]

The values, in key order (shared).

entries(): [K, V][]

The [key, value] pairs, in key order.

[Symbol.iterator](): Iterator<[K, V]>

An iterator over the entries when it is made (entries()), in key order.

forEach<E>(f: (value: V, key: K) => void throws E) throws E

Visits the entries in key order (JS argument order: value, key). When the callback changes the map through another reference, the walk goes on from the first key after the one it visited last: keys added past it are visited, keys deleted before their turn are not.

first(): K | undefined

The smallest key, or undefined if empty.

last(): K | undefined

The largest key, or undefined if empty.

floorKey(key: K): K | undefined

The largest key <= key, or undefined.

ceilingKey(key: K): K | undefined

The smallest key >= key, or undefined.

range(from: K, to: K): [K, V][]

The entries with from <= key < to, in key order.

class

ConcurrentMap

#std/collections/concurrent_map.vlt:75

Re-exported from velt/collections/concurrent_map

class ConcurrentMap<K = u64, V extends Frozen = u64>

A map from K keys (u64 or string; u64 when not written) to V values (u64 when not written) for many threads at once: share it (shared(ConcurrentMap.create(n))) and call its methods from any task. A value other than a u64 is boxed once, and read in place by read; a string key is kept once, beside its leaf. Lookups write no shared memory, so readers on many cores never slow each other; writers take a latch per node. A lookup waits (spins) while a writer holds its node, so it is not lock-free. Its keys are kept in key ranges, but a leaf's are unsorted and leaves are not linked: there is no ordered walk, iteration or size yet (#1688). Its room is fixed when it is created, and given back as leaves empty.

static create(capacity: usize): ConcurrentMap<K, V>

An empty map with room for at least capacity entries (its memory, about 40 bytes an entry, and 17 more for string keys, is taken now; a string key's own copy when it is set). A set that needs more room panics with a RangeError. A deleted entry frees a slot in its leaf, and a leaf whose last entry is deleted is reused, so keys that keep moving to new ranges (ids or timestamps that only grow, old ones deleted) fit for as long as the entries present at once do. Leaves are not merged, though: entries spread thinly over many leaves (most of a large map's keys deleted at random) can hold a node each and need more room than their number. A set of a key the map holds can also need room, when its leaf is full and splits first. Panics with a RangeError above 10^11 entries, and for keys other than u64 and string.

get(key: K): V | undefined

The value of key, or undefined if the map has none (a boxed value is copied).

read<R, E>(key: K, f: (value: shared<V>) => R throws E): R | undefined throws E

Runs f on the value of key (the map's own, not a copy; for a 64-bit integer V, whose shared is an atomic integer, a box of its own) and returns what it returns, or undefined if the map has no key.

has(key: K): bool

Whether the map has key.

set(key: K, value: V)

Makes value the value of key, adding the key if the map has none (a value other than a u64 is boxed once, a string key copied once). Panics with a RangeError for the u64 key 2^64 - 1 (the one key a map cannot hold) and when the map is out of room.

add(key: K, delta: u64): u64 | undefined

Adds delta to the u64 value of key (wrapping), atomically: the value before, or undefined if the map has no key. Only for u64 values.

delete(key: K): bool

Removes key; whether the map had it (a boxed value is dropped once no reader has it).

getManyInto(keys: K[], values: V[]): u64

Looks up keys (at most 64) together into values: where bit i of the result is set, values[i] is the value of keys[i] (values grows to keys.length if shorter; its other elements are unspecified). Unlike BTreeMap.getMany, which returns a new array, it fills the caller's, so a loop of batches allocates nothing. Faster than one get per key when the map is larger than the caches: the keys descend the tree in lockstep, and each prefetches its next node while the others search theirs, so their cache misses overlap. For u64 keys and values only for now (other maps panic with a RangeError). Panics with a RangeError for more than 64 keys.

class

Deque

#std/collections/deque.vlt:18

Re-exported from velt/collections/deque

class Deque<T>

A double-ended queue (ring buffer).

static from(xs: T[]): Deque<T>

A deque holding clones of xs in order (front = xs[0]).

get length(): usize

Number of elements.

get size(): usize

Number of elements (same as length).

isEmpty(): bool

Whether the deque has no elements.

pushBack(value: T)

Appends value at the back.

pushFront(value: T)

Inserts value at the front.

popBack(): T | undefined

Removes and returns the back element, or undefined if empty.

popFront(): T | undefined

Removes and returns the front element, or undefined if empty.

peekFront(): T | undefined

A clone of the front element, or undefined if empty.

peekBack(): T | undefined

A clone of the back element, or undefined if empty.

at(i: i64): T | undefined

A clone of the element i places from the front (negative i counts from the back, like Array.prototype.at), or undefined if out of range.

clear()

Removes every element (keeps the buffer).

toArray(): T[]

Clones of the elements, front to back.

forEach<E>(f: (value: T) => void throws E) throws E

Visits the elements front to back, borrowing them.

class

PriorityQueue

#std/collections/priority_queue.vlt:12

Re-exported from velt/collections/priority_queue

class PriorityQueue<T>

A priority queue (binary heap); pop returns the element that cmp orders first.

constructor(cmp: (a: T, b: T) => i64)

An empty queue ordered by cmp (negative: a first).

get size(): usize

Number of queued elements.

get length(): usize

Number of queued elements (same as size).

isEmpty(): bool

Whether the queue is empty.

push(value: T)

Adds value (O(log n)).

pop(): T | undefined

Removes and returns the first element in cmp order, or undefined if empty (O(log n)).

peek(): T | undefined

A clone of the first element in cmp order, or undefined if empty.

clear()

Removes every element.

toSortedArray(): T[]

Clones of the elements in cmp order; the queue is unchanged. Equal elements come out in no particular order (the heap does not keep insertion order).

toArray(): T[]

Clones of the elements in heap (unspecified) order.

class

Set

#std/collections/set.vlt:16

Re-exported from velt/collections/set

class Set<T> implements Iterable<T>

An insertion-ordered set of unique values.

Used byReadonlySet

constructor(values: T[] = [])

A set holding each distinct element of values (like JS new Set(values)), in first-occurrence order. Leaves values as it is; the set shares the elements, like JS.

static from(xs: T[]): Set<T>

A set holding each distinct element of xs (shared), in first-occurrence order.

get size(): usize

Number of elements.

add(value: T)

Inserts value; a value already present keeps its position (the new copy is dropped).

has(value: T): bool

Whether value is in the set.

delete(value: T): bool

Removes value; returns whether it was present.

clear()

Removes every element.

isEmpty(): bool

Whether the set has no elements.

values(): T[]

The elements in insertion order, objects shared as in JS (for (const x of s.values())).

[Symbol.iterator](): Iterator<T>

An iterator over the elements when it is made (values()), in insertion order.

forEach<E>(f: (value: T) => void throws E) throws E

Visits the elements in insertion order, borrowing them.

union(other: Set<T>): Set<T>

Elements of this set, then those of other not in it.

intersection(other: Set<T>): Set<T>

Elements of this set that are also in other (in this set's order).

difference(other: Set<T>): Set<T>

Elements of this set that are not in other.

symmetricDifference(other: Set<T>): Set<T>

Elements in exactly one of the two sets (this set's first, then other's).

isSubsetOf(other: Set<T>): bool

Whether every element of this set is in other.

isSupersetOf(other: Set<T>): bool

Whether every element of other is in this set.

isDisjointFrom(other: Set<T>): bool

Whether the sets share no element.

class

SortedMap

#std/collections/sorted_map.vlt:20

Re-exported from velt/collections/sorted_map

class SortedMap<K extends Comparable<K>, V>

A map ordered by key.

get size(): usize

Number of entries.

isEmpty(): bool

Whether the map is empty.

set(key: K, value: V)

Inserts or replaces the value for key.

get(key: K): V | undefined

A clone of the value for key, or undefined.

has(key: K): bool

Whether key is present.

delete(key: K): bool

Removes key; returns whether it was present.

clear()

Removes every entry.

keys(): K[]

Clones of the keys, ascending.

values(): V[]

Clones of the values, in key order.

entries(): [K, V][]

Clones of the [key, value] pairs, in key order.

forEach<E>(f: (value: V, key: K) => void throws E) throws E

Visits the entries in key order, borrowing them (JS argument order: value, key).

first(): K | undefined

A clone of the smallest key, or undefined if empty.

last(): K | undefined

A clone of the largest key, or undefined if empty.

floorKey(key: K): K | undefined

The largest key <= key (a clone), or undefined.

ceilingKey(key: K): K | undefined

The smallest key >= key (a clone), or undefined.

range(from: K, to: K): [K, V][]

Clones of the entries with from <= key < to, in key order.

interface

InlineKey

#std/collections/btree/inline_key.vlt:16

Re-exported from velt/collections/btree/inline_key

The bytes of a key that order as the keys do, for BTreeMap's node search.

hasInlineKey(): bool

Whether the type has an encoding (the same for every value of it).

inlineKey(offset: usize): u64

Bytes offset .. offset + 8 of the encoding as a big-endian u64, zero past its end. For keys a < b sharing their first offset bytes, a.inlineKey(offset) <= b.inlineKey(offset).

inlineWord(offset: usize): u16

Bytes offset .. offset + 2 of the encoding: the word a node keeps for the key.

inlineWide(): bool

Whether nodes keep four bytes of each key's encoding instead of two: for keys that often share more than two bytes past what a node's keys all share (strings with common parts), where two bytes would tie and send the search to the keys themselves.

inlineQuad(offset: usize): u32

Bytes offset .. offset + 4 of the encoding: a wide word, both halves in one call.

inlineWindow(): [u64, u64]

The first 16 bytes of the encoding, [inlineKey(0), inlineKey(8)]: what an operation computes once and reads every node's word from.

type

ReadonlySet

#std/collections/set.vlt:195

Re-exported from velt/collections/set

type ReadonlySet<T> = Set<T>

TypeScript's ReadonlySet<T>: a Set<T> that a variable or parameter declared with this type may not change (add, delete and clear are errors through it).