# gizlang:collections

```gizlang
import * as Collections from "gizlang:collections";
```

## Types

### `Key`

```gizlang
interface Key { hash(self: Self): u64 effects { fail }; }
```

A Map or Set key: equal keys (`===`) have equal hashes. Scalars, strings and
bytes are keys; a record becomes one by giving it `hash`.

- `hash`

### `Map`

```gizlang
type Map<K, V>
```

Keys in insertion order with their values. `_slots` is an open-addressing
table of entry index + 1 (0 empty). `_live` stays empty until the first
deletion, then marks each entry; a deleted entry stays as a hole until the
table next grows, when the entries are compacted.

Opaque: create and use it through this module's functions.

### `PageDirectory`

```gizlang
type PageDirectory<T>
```

A directory of pages that it owns, addressed by index.

Opaque: create and use it through this module's functions.

### `ManagedPageDirectory`

```gizlang
type ManagedPageDirectory<T>
```

A directory of pages that a manager owns, addressed by index.

Opaque: create and use it through this module's functions.

### `Set`

```gizlang
type Set<K>
```

Keys in insertion order: a Map whose values are unused.

Opaque: create and use it through this module's functions.

### `HashTrieNode`

```gizlang
type HashTrieNode = { bitmap: u64; kids: u64; hashes: Vec<u64>; vals: Vec<i64>; children: Vec<HashTrieNode>; }
```

A node: `bitmap` marks the slots that hold an entry (hash and location, in slot order), `kids` those that hold a
child node (in slot order). A slot holds one or the other.

- `bitmap`: `u64`
- `kids`: `u64`
- `hashes`: `Vec<u64>`
- `vals`: `Vec<i64>`
- `children`: `Vec<_gizlang_sdk_collections.HashTrieNode>`

### `HashTrie`

```gizlang
type HashTrie = { root: HashTrieNode; count: i64; }
```

A map from 64-bit hashes to locations: a trie of 32-way nodes, five hash bits a level.

- `root`: `_gizlang_sdk_collections.HashTrieNode`
- `count`: `i64`

### `HashEntry`

```gizlang
type HashEntry = { hash: u64; loc: i64; }
```

A hash and its location.

- `hash`: `u64`
- `loc`: `i64`

## Functions

### `sameItems`

```gizlang
function sameItems<T>(a: Vec<T>, b: Vec<T>): bool
```

Whether a and b have the same length and equal items (===) in the same order.

### `some`

```gizlang
function some<T, F extends(value: T) => bool>(values: Vec<T>, predicate: F): bool effects { predicate, fail }
```

Whether an item of VALUES meets PREDICATE.

### `concat`

```gizlang
function concat<T>(a: Vec<T>, b: Vec<T>): Vec<T>
```

A followed by B.

### `indices`

```gizlang
function indices(n: i64): Vec<i64>
```

The indices 0, 1, ..., N - 1.

Effects: fail.

### `includes`

```gizlang
function includes<T>(values: Vec<T>, value: T): bool
```

Whether VALUES has an item equal to VALUE.

### `indexOf`

```gizlang
function indexOf<T>(values: Vec<T>, value: T): i64
```

The index of the first item equal to VALUE, or -1.

### `at`

```gizlang
function at<T>(values: Vec<T>, index: i64): Option<T>
```

The item at INDEX, counted from the end when it is negative (-1 is the last), or none.

### `pop`

```gizlang
function pop<T>(values: mut Vec<T>): Option<T>
```

Removes the last item of VALUES and gives it, or none when VALUES is empty.

### `shift`

```gizlang
function shift<T>(values: mut Vec<T>): Option<T>
```

Removes the first item of VALUES and gives it, or none when VALUES is empty.

### `every`

```gizlang
function every<T, F extends(value: T) => bool>(values: Vec<T>, predicate: F): bool effects { predicate, fail }
```

Whether every item of VALUES meets PREDICATE.

### `count`

```gizlang
function count<T, F extends(value: T) => bool>(values: Vec<T>, predicate: F): i64 effects { predicate, fail }
```

The number of items of VALUES that meet PREDICATE.

### `reduce`

```gizlang
function reduce<T, A, F extends(accumulator: A, value: T) => A> (values: Vec<T>, combine: F, initial: A): A effects { combine, fail }
```

COMBINE applied to INITIAL and each item of VALUES in order.

### `findIndex`

```gizlang
function findIndex<T, F extends(value: T) => bool> (values: Vec<T>, predicate: F): i64 effects { predicate, fail }
```

The index of the first value the predicate accepts, or -1.

### `filter`

```gizlang
function filter<T, F extends(value: T) => bool> (values: Vec<T>, predicate: F): Vec<T> effects { predicate, fail }
```

The values the predicate accepts, in order.

### `toSorted`

```gizlang
function toSorted<T, F extends(a: T, b: T) => bool>(values: Vec<T>, before: F): Vec<T> effects { before, fail }
```

The values ordered by `before(a, b)` (a goes first), keeping the order of
values neither goes before: a copy sorted by `sort`, as TypeScript's `toSorted`. A comparator that returns a number
(`(a, b) => a - b`) means `before` when the number is negative.

### `sorted`

```gizlang
function sorted<T, F extends(a: T, b: T) => bool>(values: Vec<T>, before: F): Vec<T> effects { before, fail }
```

`toSorted`, by its former name: `giz fmt` writes `toSorted`.

### `sort`

```gizlang
function sort<T, F extends(a: T, b: T) => bool>(values: mut Vec<T>, before: F): void effects { before, fail }
```

Sorts in place by `before(a, b)`, preserving the order of ties. The typed
adapter applies an index permutation; the ordering kernel never depends on
the element representation. The original value stays immutable while the
comparator runs.

### `newMap`

```gizlang
function newMap<K extends Key, V>(entries: Vec<[K, V]> = []): Map<K, V>
```

A map of ENTRIES (`new Map([["a", 1]])`), empty by default; a later entry of a key replaces an earlier one.

### `newPageDirectory`

```gizlang
function newPageDirectory<T>(): PageDirectory<T>
```

An empty page directory.

### `newManagedPageDirectory`

```gizlang
function newManagedPageDirectory<T>(): ManagedPageDirectory<T>
```

Managed roots preserve local boxed snapshots; individual payload quotas
still apply. Bulk owned data uses newPageDirectory without a managed heap.

### `pageDirectoryReservation`

```gizlang
function pageDirectoryReservation(count: i64, slotBytes: i64): i64
```

Structural credit before constructing a directory of count entries.

Effects: fail.

### `newSet`

```gizlang
function newSet<K extends Key>(items: Vec<K> = []): Set<K>
```

A set of ITEMS (`new Set([1, 2])`), empty by default.

### `newHashTrie`

```gizlang
function newHashTrie(): HashTrie
```

An empty hash trie.

### `removeAt`

```gizlang
function removeAt<T>(v: Vec<T>, at: i64): Vec<T>
```

V without the item at AT.

### `hashTrieOfSorted`

```gizlang
function hashTrieOfSorted(hashes: Vec<u64>, locs: Vec<i64>): HashTrie
```

The trie of HASHES (ascending, none twice) and their LOCS, built at once: a node is made with its entries, as a
restart rebuilds a table's hash primary (db/core/table.giz Table.reindexHashed); a put a key copied and shifted node vectors.

Effects: fail.

### `hashOrder`

```gizlang
function hashOrder(hashes: Vec<u64>): Vec<i64>
```

The positions of HASHES in ascending hash order, equal hashes in their own order: a stable radix sort, 16 bits a pass.

Effects: fail.

### `find`

```gizlang
function find<T, F extends(value: T) => bool> (values: Vec<T>, predicate: F): Option<T> effects { predicate, fail }
```

First matching value, or none. Unlike findIndex, no sentinel is exposed.

### `findLast`

```gizlang
function findLast<T, F extends(value: T) => bool> (values: Vec<T>, predicate: F): Option<T> effects { predicate, fail }
```

The last value the predicate accepts, or none.

### `findLastIndex`

```gizlang
function findLastIndex<T, F extends(value: T) => bool> (values: Vec<T>, predicate: F): i64 effects { predicate, fail }
```

The index of the last value the predicate accepts, or -1.

### `lastIndexOf`

```gizlang
function lastIndexOf<T>(values: Vec<T>, value: T): i64
```

The index of the last item equal to VALUE, or -1.

### `flat`

```gizlang
function flat<T>(values: Vec<Vec<T>>): Vec<T>
```

The items of each inner Vec, in order: TypeScript's `flat()` of one level.

### `flatMap`

```gizlang
function flatMap<T, F extends(value: T) => Vec <_>> (values: Vec<T>, select: F): ReturnType<F> effects { select, fail }
```

The Vecs SELECT makes of each value, joined in order.

### `toReversed`

```gizlang
function toReversed<T>(values: Vec<T>): Vec<T>
```

A copy in the opposite order.

### `reverse`

```gizlang
function reverse<T>(values: mut Vec<T>): void
```

Reverses VALUES in place.

### `with`

```gizlang
function with<T>(values: Vec<T>, index: i64, value: T): Vec<T>
```

A copy with the item at INDEX (from the end when negative) replaced by VALUE; INDEX must be in range.

### `toSpliced`

```gizlang
function toSpliced<T>(values: Vec<T>, start: i64, count: i64, ...items: T[]): Vec<T>
```

A copy without COUNT items from START (from the end when negative) and with ITEMS there instead.

### `splice`

```gizlang
function splice<T>(values: mut Vec<T>, start: i64, count: i64, ...items: T[]): Vec<T>
```

Removes COUNT items from START, puts ITEMS there and gives the removed items.

### `unshift`

```gizlang
function unshift<T>(values: mut Vec<T>, ...items: T[]): i64
```

Puts ITEMS before the first item and gives the new length.

### `fill`

```gizlang
function fill<T>(values: mut Vec<T>, value: T): void
```

Sets every item to VALUE.

### `values`

```gizlang
function values<T>(values: Vec<T>): Vec<T>
```

The items of VALUES: a Vec spreads as a Set or a Map does (`[...x]` reads `x.values()`).

### `fromLength`

```gizlang
function fromLength<F extends(item: i64, index: i64) => _>(length: i64, make: F): Vec<ReturnType<F>>
```

TypeScript's `Array.from({ length }, make)`: make(i, i) for each index i from 0 to LENGTH less 1 (TypeScript passes
undefined, then the index).

### `keys`

```gizlang
function keys<T>(values: Vec<T>): Vec<i64>
```

The indexes of VALUES, 0 to its length less 1.

### `entries`

```gizlang
function entries<T>(values: Vec<T>): Vec<[i64, T]>
```

Each index of VALUES with its item.

### `sumBy`

```gizlang
function sumBy<T, F extends(value: T) => i64>(values: Vec<T>, select: F): i64 effects { select, fail }
```

Checked i64 sum of a projection.

## Methods

### `i64.hash`

```gizlang
function i64.hash(self: i64): u64
```

The key's hash.

Effects: fail.

### `u64.hash`

```gizlang
function u64.hash(self: u64): u64
```

The key's hash.

Effects: fail.

### `bool.hash`

```gizlang
function bool.hash(self: bool): u64
```

The key's hash.

Effects: fail.

### `string.hash`

```gizlang
function string.hash(self: string): u64
```

Strings and bytes hash eight bytes at a time (wyhash's folded 128-bit
product): a byte at a time serializes on the multiply.

Effects: fail.

### `bytes.hash`

```gizlang
function bytes.hash(self: bytes): u64
```

The bytes' hash, eight bytes at a time (as string.hash).

Effects: fail.

### `Map.size`

```gizlang
function Map.size<K extends Key, V>(self: Map<K, V>): i64
```

The number of entries.

### `Map.retainedBytes`

```gizlang
function Map.retainedBytes<K extends Key, V>(self: Map<K, V>, keyBytes: i64, valueBytes: i64): i64
```

Retained array content bytes, including holes, live flags and hash slots.
Supply the inline carrier widths of K and V. Referenced payloads, allocator
headers, spare capacity and separately retained snapshots are not included.
Invalid widths or overflow return the signed maximum to refuse admission.

### `Map.has`

```gizlang
function Map.has<K extends Key, V>(self: Map<K, V>, key: K): bool
```

Whether KEY has an entry.

### `Map.get`

```gizlang
function Map.get<K extends Key, V>(self: Map<K, V>, key: K): Option<V>
```

The value under KEY, or none.

### `Map.set`

```gizlang
function Map.set<K extends Key, V>(self: mut Map<K, V>, key: K, value: V): bool
```

Sets the key's value; whether the key is new.

### `Map.merge`

```gizlang
function Map.merge<K extends Key, V, F extends(old: V, value: V) => V> (self: mut Map<K, V>, key: K, value: V, combine: F): V effects { combine, fail }
```

The key's value becomes `value` when it is absent, else combine(old, value)
(Java's Map.merge; `counts.merge(word, 1, add)` counts); the new value.

### `Map.delete`

```gizlang
function Map.delete<K extends Key, V>(self: mut Map<K, V>, key: K): bool
```

Removes the key; whether it was there.

### `Map.pick`

```gizlang
function Map.pick<K extends Key, V>(self: Map<K, V>, seed: u64): Option<K>
```

A key chosen by `seed` (a random number gives a random key: Redis's SPOP and RANDOMKEY), or
none when empty. Expected O(1): holes never exceed entries.

### `Map.keys`

```gizlang
function Map.keys<K extends Key, V>(self: Map<K, V>): Vec<K>
```

The keys, values and entries in insertion order.

### `Map.values`

```gizlang
function Map.values<K extends Key, V>(self: Map<K, V>): Vec<V>
```

The values in insertion order.

### `Map.entries`

```gizlang
function Map.entries<K extends Key, V>(self: Map<K, V>): Vec<[K, V]>
```

The entries as [key, value] pairs in insertion order: what a for...of over a Map gives, as in TypeScript.

### `Map.visit`

```gizlang
function Map.visit<K extends Key, V, T, F>(self: Map<K, V>, context: mut T, visit: F): void effects { visit, fail }
```

Visits live entries in insertion order without constructing a keys/values
vector. The map is an immutable value for the visit; the callback receives
its mutable accumulator explicitly and can change a separate map value.

### `Map.visitRetained`

```gizlang
function Map.visitRetained<K extends Key, V, T, F>(self: Map<K, V>, context: mut T, visit: F): void effects { visit, fail }
```

Visits every physically retained key/value, including deleted slots awaiting
compaction. Resource admission uses this view rather than logical size; no
filtered vectors or map copies are created.

### `PageDirectory.count`

```gizlang
function PageDirectory.count<T>(self: PageDirectory<T>): i64
```

The number of entries.

### `ManagedPageDirectory.count`

```gizlang
function ManagedPageDirectory.count<T>(self: ManagedPageDirectory<T>): i64
```

The number of entries.

### `PageDirectory.capacity`

```gizlang
function PageDirectory.capacity<T>(self: PageDirectory<T>): i64
```

The number of entries that the directory holds without growing.

### `ManagedPageDirectory.capacity`

```gizlang
function ManagedPageDirectory.capacity<T>(self: ManagedPageDirectory<T>): i64
```

The number of entries that the directory holds without growing.

### `PageDirectory.reservation`

```gizlang
function PageDirectory.reservation<T>(self: PageDirectory<T>, slotBytes: i64): i64
```

The bytes that the directory structure takes for its entries, with SLOTBYTES for each slot
(pageDirectoryReservation).

### `ManagedPageDirectory.reservation`

```gizlang
function ManagedPageDirectory.reservation<T>(self: ManagedPageDirectory<T>, slotBytes: i64): i64
```

The bytes that the directory structure takes for its entries, with SLOTBYTES for each slot
(pageDirectoryReservation).

### `PageDirectory.get`

```gizlang
function PageDirectory.get<T>(self: PageDirectory<T>, at: i64): Option<T>
```

The entry at AT, or none when AT is out of range.

### `ManagedPageDirectory.get`

```gizlang
function ManagedPageDirectory.get<T>(self: ManagedPageDirectory<T>, at: i64): Option<T>
```

The entry at AT, or none when AT is out of range.

### `PageDirectory.set`

```gizlang
function PageDirectory.set<T>(self: mut PageDirectory<T>, at: i64, value: T): bool
```

Replaces the entry at AT with VALUE; false when AT is out of range.

### `ManagedPageDirectory.set`

```gizlang
function ManagedPageDirectory.set<T>(self: mut ManagedPageDirectory<T>, at: i64, value: T): bool
```

Replaces the entry at AT with VALUE; false when AT is out of range.

### `PageDirectory.append`

```gizlang
function PageDirectory.append<T>(self: mut PageDirectory<T>, value: T): i64 throws string
```

Adds VALUE at the end; its index. It fails when the directory is full.

### `ManagedPageDirectory.append`

```gizlang
function ManagedPageDirectory.append<T>(self: mut ManagedPageDirectory<T>, value: T): i64 throws string
```

Adds VALUE at the end; its index. It fails when the directory is full.

### `PageDirectory.pop`

```gizlang
function PageDirectory.pop<T>(self: mut PageDirectory<T>): Option<T>
```

Removes the last entry and gives it, or none when the directory is empty.

### `ManagedPageDirectory.pop`

```gizlang
function ManagedPageDirectory.pop<T>(self: mut ManagedPageDirectory<T>): Option<T>
```

Removes the last entry and gives it, or none when the directory is empty.

### `PageDirectory.pathWork`

```gizlang
function PageDirectory.pathWork<T>(self: PageDirectory<T>): Vec<i64>
```

The directory nodes and the slots that the writes copied so far: logical work, not malloc or RSS.

### `ManagedPageDirectory.pathWork`

```gizlang
function ManagedPageDirectory.pathWork<T>(self: ManagedPageDirectory<T>): Vec<i64>
```

The directory nodes and the slots that the writes copied so far: logical work, not malloc or RSS.

### `Set.size`

```gizlang
function Set.size<K extends Key>(self: Set<K>): i64
```

The number of keys.

### `Set.has`

```gizlang
function Set.has<K extends Key>(self: Set<K>, key: K): bool
```

Whether the set holds KEY.

### `Set.add`

```gizlang
function Set.add<K extends Key>(self: mut Set<K>, key: K): bool
```

Adds the key; whether it is new.

### `Set.delete`

```gizlang
function Set.delete<K extends Key>(self: mut Set<K>, key: K): bool
```

Removes the key; whether it was there.

### `Set.pick`

```gizlang
function Set.pick<K extends Key>(self: Set<K>, seed: u64): Option<K>
```

A key chosen by SEED (as Map.pick), or none when empty.

### `Set.values`

```gizlang
function Set.values<K extends Key>(self: Set<K>): Vec<K>
```

The keys in insertion order.

### `HashTrie.get`

```gizlang
function HashTrie.get(self: HashTrie, hash: u64): Option<i64>
```

The location of HASH, or none.

Effects: fail.

### `HashTrie.put`

```gizlang
function HashTrie.put(self: mut HashTrie, hash: u64, loc: i64): Option<i64>
```

Puts HASH at LOC; the location it had, or none.

Effects: fail.

### `HashTrie.remove`

```gizlang
function HashTrie.remove(self: mut HashTrie, hash: u64): bool
```

Removes HASH; whether it was there. A child left empty goes.

Effects: fail.

### `HashTrie.ceiling`

```gizlang
function HashTrie.ceiling(self: HashTrie, hash: u64): Option<HashEntry>
```

The entry of the least hash at or above HASH, or none.

Effects: fail.

### `HashTrie.entries`

```gizlang
function HashTrie.entries(self: HashTrie): Vec<HashEntry>
```

Every entry, in hash order.

Effects: fail.

### `HashTrie.residentBytes`

```gizlang
function HashTrie.residentBytes(self: HashTrie): i64
```

The bytes the trie holds, counted from its entries (a node a few entries): for the memory budget.

Effects: fail.

## Constants

### `HASH_COLLIDED`

```gizlang
const HASH_COLLIDED: i64 = -2
```

The location of a hash whose keys the caller keeps apart.