Source src/silo:std.collections.btreemap

1##! BTreeMap — ordered key-value collection.
2##!
3##! `BTreeMap k v` is a newtype over `(HashMap k v)` so it has a
4##! dispatch identity distinct from `HashMap` while borrowing the hash
5##! runtime. `(Ord k k)` constraints are elided from the current
6##! signatures; they return once the real B-tree representation lands.
7##!
8##! Methods currently panic at runtime; real bodies require either
9##! host B-tree intrinsics or a working BTreeMap↔HashMap coercion
10##! surface. Range and drain operations surface as eager `(Vec (Pair k
11##! v))` today and narrow to lazy sequences once the Seq hierarchy is
12##! wired. `Cursor` / `CursorMut` are deferred.
13##!
14##! Not re-exported by the prelude — use
15##! `:use :open silo:std.collections.btreemap ...`.
16
17:use
18  :open core AnyInt Bool Option Pair Range Vec
19  :open collections.hashmap HashMap
20  :open effects.panic panic
21:end
22
23# si[impl coll.btreemap.entry]
24## Result of an entry lookup on a `BTreeMap`. `Occupied` carries both
25## the key and the current value; `Vacant` carries only the key. Real
26## implementation requires `(Ord k k)`; the stub union omits the bound
27## for the same reason the method stubs do (see file-header note 2).
28:union(pub) BTreeEntry k v
29  | Occupied k v
30  | Vacant k
31:end
32
33# si[impl coll.btreemap.len]
34# si[impl coll.btreemap.is-empty]
35# si[impl coll.btreemap.first]
36# si[impl coll.btreemap.last]
37# si[impl coll.btreemap.insert]
38# si[impl coll.btreemap.remove]
39# si[impl coll.btreemap.get]
40# si[impl coll.btreemap.contains-key]
41# si[impl coll.btreemap.drain]
42# si[impl coll.btreemap.extend]
43# si[impl coll.btreemap.filter-keys]
44# si[impl coll.btreemap.range+1]
45# si[impl coll.btreemap.range-from]
46# si[impl coll.btreemap.range-to]
47# si[impl coll.btreemap.merge]
48# si[impl coll.btreemap.retain]
49# si[impl coll.btreemap.map-values]
50# si[impl coll.btreemap.entry.lookup]
51# si[impl coll.btreemap.entry.or-insert]
52# si[impl coll.btreemap.from-hashmap]
53# si[impl coll.btreemap.to-hashmap]
54## Ordered key-value collection. Runtime layout shares `(HashMap k v)`
55## but `BTreeMap` is a distinct type for dispatch — HashMap methods
56## like `.insert` do NOT resolve through `BTreeMap`.
57:type(pub) BTreeMap k v (HashMap k v)
58
59:impl (BTreeMap k v)
60  # si[impl coll.btreemap.len+1]
61  ## Number of entries in O(1).
62  .len ( (BTreeMap k v) -> AnyInt )
63    btreemap-len-intrinsic ;
64
65  # si[impl coll.btreemap.is-empty+1]
66  ## True iff the map contains zero entries. Equivalent to `.len 0 eq`.
67  .is-empty ( (BTreeMap k v) -> Bool )
68    btreemap-is-empty-intrinsic ;
69
70  # si[impl coll.btreemap.first]
71  ## `.first` returns `Some` with the (key, value) pair having the
72  ## smallest key, or `None` if the map is empty. O(log n).
73  .first ( (BTreeMap k v) -> (Option (Pair k v)) )
74    :todo "awaits host B-tree intrinsics" ;
75
76  # si[impl coll.btreemap.last]
77  ## `.last` returns `Some` with the (key, value) pair having the
78  ## largest key, or `None` if the map is empty. O(log n).
79  .last ( (BTreeMap k v) -> (Option (Pair k v)) )
80    :todo "awaits host B-tree intrinsics" ;
81
82  # si[impl coll.btreemap.insert]
83  ## `.insert` inserts a key-value pair; returns the updated map and
84  ## `(Option v)` carrying the displaced prior value (`None` if the
85  ## key was absent). O(log n).
86  .insert ( k v (BTreeMap k v) -> (BTreeMap k v) (Option v) )
87    :todo "awaits host B-tree intrinsics" ;
88
89  # si[impl coll.btreemap.remove]
90  ## `.remove` removes an entry by key; returns the updated map and
91  ## `(Option v)` carrying the removed value (`None` if the key was
92  ## absent). O(log n).
93  .remove ( k (BTreeMap k v) -> (BTreeMap k v) (Option v) )
94    :todo "awaits host B-tree intrinsics" ;
95
96  # si[impl coll.btreemap.get]
97  ## `.get` returns `(Option v)` for a given key: `Some v` when
98  ## present, `None` otherwise. Conforms to `(Keyed .lookup)` once
99  ## `BTreeMap` joins the `Keyed` impl surface. Real body uses linear
100  ## scan with structural equality over the backing HashMap cell; real
101  ## O(log n) balanced-tree lookup arrives with the tree runtime.
102  .get ( k (BTreeMap k v) -> (Option v) )
103    btreemap-get-intrinsic ;
104
105  # si[impl coll.btreemap.contains-key]
106  ## `.contains-key` — true iff the given key is present. Conforms to
107  ## `(Keyed .contains-key)` once `BTreeMap` joins that impl surface.
108  ## Real body uses linear scan over the backing HashMap cell.
109  .contains-key ( k (BTreeMap k v) -> Bool )
110    btreemap-contains-key-intrinsic ;
111
112  # si[impl coll.btreemap.drain]
113  ## `.drain` consumes the map and returns a `(Vec (Pair k v))` of
114  ## every entry in ascending key order, plus a fresh empty
115  ## `(BTreeMap k v)`. Spec says `unique` input mode and `(Seq ...)`
116  ## output — see file-header notes 3 and 5 for the stub's
117  ## simplifications.
118  .drain ( (BTreeMap k v) -> (Vec (Pair k v)) (BTreeMap k v) )
119    :todo "awaits host B-tree intrinsics" ;
120
121  # si[impl coll.btreemap.extend]
122  ## `.extend` inserts every `(Pair k v)` from a `(Vec (Pair k v))`
123  ## source into the map. Incoming values overwrite existing ones.
124  ## Spec says `(Foldable (Pair k v))` source; the stub pins to
125  ## `Vec` to avoid the trait-constraint-on-quotation surface while
126  ## the impl is stubbed.
127  .extend ( (BTreeMap k v) (Vec (Pair k v)) -> (BTreeMap k v) )
128    :todo "awaits host B-tree intrinsics" ;
129
130  # si[impl coll.btreemap.filter-keys]
131  ## `.filter-keys` keeps only entries whose key satisfies the
132  ## predicate. Key order is preserved.
133  .filter-keys ( (BTreeMap k v) [ k -> Bool ] -> (BTreeMap k v) )
134    :todo "awaits host B-tree intrinsics" ;
135
136  # si[impl coll.btreemap.range+1]
137  ## `.range` returns a `(Vec (Pair k v))` of entries whose key falls
138  ## within `[start, end)` — half-open — in ascending key order.
139  ## Spec surface is `(Seq (Pair k v))`; see file-header note 3.
140  ## O(log n + k).
141  .range ( (RangeBoth k k) (BTreeMap k v) -> (Vec (Pair k v)) )
142    :todo "awaits host B-tree intrinsics" ;
143
144  # si[impl coll.btreemap.range-from]
145  ## `.range-from` returns a `(Vec (Pair k v))` of entries whose key
146  ## is >= `start`, in ascending key order. O(log n + k).
147  .range-from ( (RangeFrom k) (BTreeMap k v) -> (Vec (Pair k v)) )
148    :todo "awaits host B-tree intrinsics" ;
149
150  # si[impl coll.btreemap.range-to]
151  ## `.range-to` returns a `(Vec (Pair k v))` of entries whose key
152  ## is < `end`, in ascending key order. O(log n + k).
153  .range-to ( (RangeTo k) (BTreeMap k v) -> (Vec (Pair k v)) )
154    :todo "awaits host B-tree intrinsics" ;
155
156  # si[impl coll.btreemap.merge]
157  ## `.merge` combines two maps. On duplicate keys, the second (top of
158  ## stack) map's value wins.
159  .merge ( (BTreeMap k v) (BTreeMap k v) -> (BTreeMap k v) )
160    :todo "awaits host B-tree intrinsics" ;
161
162  # si[impl coll.btreemap.retain]
163  ## `.retain` keeps only entries for which the `[k v -> Bool]`
164  ## predicate returns `true`.
165  .retain ( [ k v -> Bool ] (BTreeMap k v) -> (BTreeMap k v) )
166    :todo "awaits host B-tree intrinsics" ;
167
168  # si[impl coll.btreemap.map-values]
169  ## `.map-values` transforms every value via the quotation; keys and
170  ## key order are preserved. Note the resulting `v` type may differ.
171  .map-values ( [ v -> w ] (BTreeMap k v) -> (BTreeMap k w) )
172    :todo "awaits host B-tree intrinsics" ;
173
174  # si[impl coll.btreemap.entry.lookup]
175  ## `.entry` returns `(BTreeEntry k v)`: `Occupied` when the key is
176  ## present, `Vacant` otherwise.
177  .entry ( k (BTreeMap k v) -> (BTreeEntry k v) )
178    :todo "awaits host B-tree intrinsics" ;
179
180  # si[impl coll.btreemap.to-hashmap]
181  ## `.to-hashmap` — runtime identity cast. The backing cell is already a
182  ## HashMap; the ordering discipline is dropped. Spec mandates element
183  ## contents are identical.
184  .to-hashmap ( (BTreeMap k v) -> (HashMap k v) )
185    btreemap-to-hashmap-intrinsic ;
186:end
187
188# si[impl coll.btreemap.entry.or-insert]
189## `.or-insert` — free fn rather than method because dispatch would
190## need to pick between `BTreeEntry` and `BTreeMap` as Self. If the
191## entry is `Occupied`, the existing value surfaces; if `Vacant`,
192## the default inserts. Stack effect matches the spec: default and
193## entry pop, updated value and map push.
194:fn(pub) btreemap-or-insert ( v (BTreeEntry k v) (BTreeMap k v) -> v (BTreeMap k v) )
195  :todo "awaits host B-tree intrinsics" :ret
196:end
197
198# si[impl coll.btreemap.from-hashmap]
199## `.from-hashmap` converts a `(HashMap k v)` into a `(BTreeMap k v)`.
200## Contents are identical; only the ordering discipline changes. The
201## WP-F3 partial body is an identity cast at the runtime layer (the
202## cell layout is already a HashMap). Ordered-iteration semantics
203## arrive when the real B-tree intrinsics land — callers that rely on
204## ordered traversal MUST NOT depend on this behaviour yet. Free fn
205## rather than method because method dispatch on `(HashMap k v)` would
206## collide with other HashMap-wrapping newtypes in the future.
207:fn(pub) btreemap-from-hashmap ( (HashMap k v) -> (BTreeMap k v) )
208  btreemap-from-hashmap-intrinsic
209:end