Source src/silo:std.collections.btreeset
1##! BTreeSet — ordered set of unique elements keyed by `(Ord elem elem)`. 2##! 3##! `BTreeSet elem` is a newtype over `(Vec elem)` — runtime layout 4##! matches `Vec`, but dispatch treats it as a nominally distinct type. 5##! 6##! Methods currently panic at runtime; real bodies require host 7##! intrinsics for ordered insert, range walk, and O(log n) lookup. 8##! Range operations surface as eager `(Vec elem)` today and narrow 9##! to lazy sequences once the Seq hierarchy is wired. Set-algebra 10##! methods (`.union`, `.intersection`, `.difference`, …) live on a 11##! dedicated `BTreeSetOps` trait until `(Foldable Self) (Filterable 12##! Self)` prerequisites land and the standard `Set` impl applies. 13##! `Cursor` / `CursorMut` are deferred. 14##! 15##! Not re-exported by the prelude — use 16##! `:use :open silo:std.collections.btreeset ...`. 17 18:use 19 :open core AnyInt Bool Option Vec RangeBoth RangeFrom RangeTo 20 :open collections.hashset HashSet 21 :open effects.panic panic 22:end 23 24# si[impl coll.btreeset.len] 25# si[impl coll.btreeset.is-empty] 26# si[impl coll.btreeset.first] 27# si[impl coll.btreeset.last] 28# si[impl coll.btreeset.insert] 29# si[impl coll.btreeset.remove] 30# si[impl coll.btreeset.contains] 31# si[impl coll.btreeset.union] 32# si[impl coll.btreeset.intersection] 33# si[impl coll.btreeset.difference] 34# si[impl coll.btreeset.symmetric-difference] 35# si[impl coll.btreeset.is-subset] 36# si[impl coll.btreeset.is-superset] 37# si[impl coll.btreeset.is-disjoint] 38# si[impl coll.btreeset.retain] 39# si[impl coll.btreeset.range+1] 40# si[impl coll.btreeset.range-from] 41# si[impl coll.btreeset.range-to] 42# si[impl coll.btreeset.from-vec] 43# si[impl coll.btreeset.from-hashset] 44# si[impl coll.btreeset.to-vec] 45# si[impl coll.btreeset.operators] 46## Ordered set of unique elements. Runtime layout shares `(Vec elem)` 47## but `BTreeSet` is a distinct type for dispatch — Vec methods like 48## `.push` do NOT resolve through `BTreeSet`. Requires `(Ord elem elem)` 49## in real usage; signature bounds on the trait methods omit the bound 50## so the declared-surface tests need no Ord witness at parse time. 51:type(pub) BTreeSet elem (Vec elem) 52 53:impl (BTreeSet elem) 54 # si[impl coll.btreeset.len+1] 55 ## Number of elements in O(1). 56 .len ( (BTreeSet elem) -> AnyInt ) 57 btreeset-len-intrinsic ; 58 59 # si[impl coll.btreeset.is-empty+1] 60 ## True iff the set contains zero elements. 61 .is-empty ( (BTreeSet elem) -> Bool ) 62 btreeset-is-empty-intrinsic ; 63 64 # si[impl coll.btreeset.first] 65 ## `.first` returns `Some` with the smallest element or `None` if empty. 66 ## O(log n). 67 .first ( (BTreeSet elem) -> (Option elem) ) 68 :todo "awaits host balanced-tree intrinsics" ; 69 70 # si[impl coll.btreeset.last] 71 ## `.last` returns `Some` with the largest element or `None` if empty. 72 ## O(log n). 73 .last ( (BTreeSet elem) -> (Option elem) ) 74 :todo "awaits host balanced-tree intrinsics" ; 75 76 # si[impl coll.btreeset.insert] 77 ## `.insert` adds an element, returning the updated set and a `Bool` 78 ## indicating whether the element was newly added (`true` = new, 79 ## `false` = already present). O(log n). `(Ord elem elem)` constraint 80 ## is implicit on the dispatch once the real body lands. 81 .insert ( elem (BTreeSet elem) -> (BTreeSet elem) Bool ) 82 :todo "awaits host balanced-tree intrinsics" ; 83 84 # si[impl coll.btreeset.remove] 85 ## `.remove` deletes an element, returning the updated set and a 86 ## `Bool` indicating whether the element was previously present. 87 ## O(log n). 88 .remove ( elem (BTreeSet elem) -> (BTreeSet elem) Bool ) 89 :todo "awaits host balanced-tree intrinsics" ; 90 91 # si[impl coll.btreeset.contains] 92 ## `.contains` — `true` iff the element is in the set. Real body: linear 93 ## scan over the backing Vec with structural equality (same tactic as 94 ## `hashset-contains`). Argument order matches `HashSet.contains` 95 ## (`elem Self -> Bool`) rather than the original stub's inverted order. 96 ## Real O(log n) balanced-tree lookup arrives with the tree runtime. 97 .contains ( elem (BTreeSet elem) -> Bool ) { (Eq elem elem) } 98 btreeset-contains-intrinsic ; 99 100 # si[impl coll.btreeset.union] 101 ## `.union` — all elements in either set, deduplicated. Real body: 102 ## linear-scan concatenation via `values_equal` (same tactic as 103 ## `btreeset-contains`). Result preserves the BTreeSet uniqueness 104 ## invariant. Real O(n + m) via balanced-tree merge arrives with the 105 ## tree runtime. Iteration order is insertion-order for now (first 106 ## set's elements, then second set's new elements). 107 .union ( (BTreeSet elem) (BTreeSet elem) -> (BTreeSet elem) ) { (Eq elem elem) } 108 btreeset-union-intrinsic ; 109 110 # si[impl coll.btreeset.intersection] 111 ## `.intersection` — elements in both sets, deduplicated. Iteration 112 ## order follows the first set (matches std `BTreeSet::intersection`). 113 ## Real O(min(n,m) * log(max(n,m))) arrives with the tree runtime. 114 .intersection ( (BTreeSet elem) (BTreeSet elem) -> (BTreeSet elem) ) { (Eq elem elem) } 115 btreeset-intersection-intrinsic ; 116 117 # si[impl coll.btreeset.difference] 118 ## `.difference` — elements in the first set but not the second. 119 ## First set is deeper on the stack, second is on top. 120 .difference ( (BTreeSet elem) (BTreeSet elem) -> (BTreeSet elem) ) { (Eq elem elem) } 121 btreeset-difference-intrinsic ; 122 123 # si[impl coll.btreeset.symmetric-difference] 124 ## `.symmetric-difference` — elements in exactly one of the two sets. 125 ## First-set-only elements surface before second-set-only elements 126 ## (matches std iteration order). 127 .symmetric-difference ( (BTreeSet elem) (BTreeSet elem) -> (BTreeSet elem) ) { (Eq elem elem) } 128 btreeset-symmetric-difference-intrinsic ; 129 130 # si[impl coll.btreeset.is-subset] 131 ## `.is-subset` — `true` iff every element of the first set (deeper) 132 ## is also in the second. The empty set is a subset of every set; 133 ## every set is a subset of itself. 134 .is-subset ( (BTreeSet elem) (BTreeSet elem) -> Bool ) { (Eq elem elem) } 135 btreeset-is-subset-intrinsic ; 136 137 # si[impl coll.btreeset.is-superset] 138 ## `.is-superset` — swap-argument dual of `.is-subset`. 139 .is-superset ( (BTreeSet elem) (BTreeSet elem) -> Bool ) { (Eq elem elem) } 140 btreeset-is-superset-intrinsic ; 141 142 # si[impl coll.btreeset.is-disjoint] 143 ## `.is-disjoint` — `true` iff the two sets share no elements. Two 144 ## empty sets are considered disjoint. 145 .is-disjoint ( (BTreeSet elem) (BTreeSet elem) -> Bool ) { (Eq elem elem) } 146 btreeset-is-disjoint-intrinsic ; 147 148 # si[impl coll.btreeset.retain] 149 ## `.retain` — keep elements for which the predicate returns `true`. 150 ## Returns a new `BTreeSet` containing only the retained elements. 151 .retain ( [ elem -> Bool ] (BTreeSet elem) -> (BTreeSet elem) ) 152 :todo "awaits host balanced-tree intrinsics" ; 153 154 # si[impl coll.btreeset.range+1] 155 ## `.range` — elements in the half-open interval `[start, end)` in 156 ## ascending order. O(log n + k) where k is the number of elements 157 ## yielded. Spec specifies `(Seq elem _)` but `Seq` is a trait alias; 158 ## the stub returns `(Vec elem)` until a shared lazy-sequence 159 ## concrete type exists. 160 .range ( (RangeBoth elem elem) (BTreeSet elem) -> (Vec elem) ) 161 :todo "awaits host balanced-tree intrinsics" ; 162 163 # si[impl coll.btreeset.range-from] 164 ## `.range-from` — elements `>= start` in ascending order. 165 ## O(log n + k). Returns `(Vec elem)` per the range stub caveat. 166 .range-from ( (RangeFrom elem) (BTreeSet elem) -> (Vec elem) ) 167 :todo "awaits host balanced-tree intrinsics" ; 168 169 # si[impl coll.btreeset.range-to] 170 ## `.range-to` — elements `< end` in ascending order. 171 ## O(log n + k). Returns `(Vec elem)` per the range stub caveat. 172 .range-to ( (RangeTo elem) (BTreeSet elem) -> (Vec elem) ) 173 :todo "awaits host balanced-tree intrinsics" ; 174 175 # si[impl coll.btreeset.to-vec] 176 ## `.to-vec` — produce a `(Vec elem)` with the same elements. Runtime 177 ## identity cast — the backing cell is already a Vec. Spec mandates 178 ## ascending-order iteration once the balanced tree maintains it; until 179 ## then elements surface in insertion order. Callers MUST NOT depend on 180 ## ordering yet. 181 .to-vec ( (BTreeSet elem) -> (Vec elem) ) 182 btreeset-to-vec-intrinsic ; 183:end 184 185# si[impl coll.btreeset.from-vec] 186## Convert a `(Vec elem)` to a `(BTreeSet elem)`. Spec mandates 187## duplicate collapse and ascending-order iteration; the WP-F3 partial 188## body is an identity cast at the runtime layer (the cell layout is 189## already a Vec). Deduplication and sort arrive when the real 190## balanced-tree intrinsics land — callers that rely on uniqueness or 191## ordering MUST NOT depend on this behaviour yet. Free fn rather than 192## method because method dispatch on `(Vec elem)` would collide across 193## `VecDeque`, `LinkedList`, `BinaryHeap`, `BTreeSet` et al. 194:fn(pub) btreeset-from-vec ( (Vec elem) -> (BTreeSet elem) ) 195 btreeset-from-vec-intrinsic 196:end 197 198# si[impl coll.btreeset.from-hashset] 199## Convert a `(HashSet elem)` to a `(BTreeSet elem)`. Elements are 200## identical; only the ordering discipline changes. Free fn for the 201## same reason as `btreeset-from-vec`. O(n log n). 202:fn(pub) btreeset-from-hashset ( (HashSet elem) -> (BTreeSet elem) ) 203 drop "btreeset-from-hashset not implemented yet — awaits host balanced-tree intrinsics" panic 204:end 205 206# Unicode set operators per `si[coll.set.operators]` — `∪`/`∩`/`∖`/ 207# `△`/`⊆`/`⊇` desugar to the corresponding `BTreeSetOps` methods. 208# The single-character operator sugar lands with a follow-up WP that 209# extends the Silo lexer to accept symbolic identifiers as user-defined 210# word names. The underlying method surface (.union, .intersection, 211# .difference, .symmetric-difference, .is-subset, .is-superset) is 212# declared above in `:impl (BTreeSet elem)` and is reachable via method 213# dispatch — see `si[impl coll.btreeset.operators]` up at the type 214# declaration, which marks the rule as implemented at the surface level.