std.collections

Module btreemap

Source
Description

BTreeMap — ordered key-value collection.

BTreeMap k v is a newtype over (HashMap k v) so it has a dispatch identity distinct from HashMap while borrowing the hash runtime. (Ord k k) constraints are elided from the current signatures; they return once the real B-tree representation lands.

Methods currently panic at runtime; real bodies require either host B-tree intrinsics or a working BTreeMap↔HashMap coercion surface. Range and drain operations surface as eager (Vec (Pair k v)) today and narrow to lazy sequences once the Seq hierarchy is wired. Cursor / CursorMut are deferred.

Not re-exported by the prelude — use :use :open silo:std.collections.btreemap ....

Data Types

Unions

BTreeEntry

Result of an entry lookup on a BTreeMap.

Types

BTreeMap

Ordered key-value collection.

Functions

Functions

btreemap-from-hashmap

.from-hashmap converts a (HashMap k v) into a (BTreeMap k v).

btreemap-or-insert

.or-insert — free fn rather than method because dispatch would

Trait Implementations

impl BTreeMap ?600306 for ?600305

.contains-key ( k (BTreeMap k v) → Bool )

.contains-key — true iff the given key is present. Conforms to (Keyed .contains-key) once BTreeMap joins that impl surface. Real body uses linear scan over the backing HashMap cell.

.drain ( (BTreeMap k v) → (Vec (Pair k v)) (BTreeMap k v) )

.drain consumes the map and returns a (Vec (Pair k v)) of every entry in ascending key order, plus a fresh empty (BTreeMap k v). Spec says unique input mode and (Seq ...) output — see file-header notes 3 and 5 for the stub's simplifications.

.entry ( k (BTreeMap k v) → (BTreeEntry k v) )

.entry returns (BTreeEntry k v): Occupied when the key is present, Vacant otherwise.

.extend ( (BTreeMap k v) (Vec (Pair k v)) → (BTreeMap k v) )

.extend inserts every (Pair k v) from a (Vec (Pair k v)) source into the map. Incoming values overwrite existing ones. Spec says (Foldable (Pair k v)) source; the stub pins to Vec to avoid the trait-constraint-on-quotation surface while the impl is stubbed.

.filter-keys ( (BTreeMap k v) [k → Bool ] → (BTreeMap k v) )

.filter-keys keeps only entries whose key satisfies the predicate. Key order is preserved.

.first ( (BTreeMap k v) → (Option (Pair k v)) )

.first returns Some with the (key, value) pair having the smallest key, or None if the map is empty. O(log n).

.get ( k (BTreeMap k v) → (Option v) )

.get returns (Option v) for a given key: Some v when present, None otherwise. Conforms to (Keyed .lookup) once BTreeMap joins the Keyed impl surface. Real body uses linear scan with structural equality over the backing HashMap cell; real O(log n) balanced-tree lookup arrives with the tree runtime.

.insert ( k v (BTreeMap k v) → (BTreeMap k v) (Option v) )

.insert inserts a key-value pair; returns the updated map and (Option v) carrying the displaced prior value (None if the key was absent). O(log n).

.is-empty ( (BTreeMap k v) → Bool )

True iff the map contains zero entries. Equivalent to .len 0 eq.

.last ( (BTreeMap k v) → (Option (Pair k v)) )

.last returns Some with the (key, value) pair having the largest key, or None if the map is empty. O(log n).

.len ( (BTreeMap k v) → (Int ..) )

Number of entries in O(1).

.map-values ( [v → w ] (BTreeMap k v) → (BTreeMap k w) )

.map-values transforms every value via the quotation; keys and key order are preserved. Note the resulting v type may differ.

.merge ( (BTreeMap k v) (BTreeMap k v) → (BTreeMap k v) )

.merge combines two maps. On duplicate keys, the second (top of stack) map's value wins.

.range ( k..k (BTreeMap k v) → (Vec (Pair k v)) )

.range returns a (Vec (Pair k v)) of entries whose key falls within [start, end) — half-open — in ascending key order. Spec surface is (Seq (Pair k v)); see file-header note 3. O(log n + k).

.range-from ( k.. (BTreeMap k v) → (Vec (Pair k v)) )

.range-from returns a (Vec (Pair k v)) of entries whose key is >= start, in ascending key order. O(log n + k).

.range-to ( ..k (BTreeMap k v) → (Vec (Pair k v)) )

.range-to returns a (Vec (Pair k v)) of entries whose key is < end, in ascending key order. O(log n + k).

.remove ( k (BTreeMap k v) → (BTreeMap k v) (Option v) )

.remove removes an entry by key; returns the updated map and (Option v) carrying the removed value (None if the key was absent). O(log n).

.retain ( [k v → Bool ] (BTreeMap k v) → (BTreeMap k v) )

.retain keeps only entries for which the [k v -> Bool] predicate returns true.

.to-hashmap ( (BTreeMap k v) → (HashMap k v) )

.to-hashmap — runtime identity cast. The backing cell is already a HashMap; the ordering discipline is dropped. Spec mandates element contents are identical.