Source src/silo:std.collections.binaryheap

1##! BinaryHeap — max-heap priority queue.
2##!
3##! `BinaryHeap 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 land once host
7##! intrinsics for sift-up / sift-down and heapify arrive. The spec
8##! has `BinaryHeap` implementing `Foldable` but not `Seq`, `Map`,
9##! `Set`, or `Indexed`, and that wiring is sequenced with the Seq
10##! hierarchy work.
11##!
12##! Not re-exported by the prelude — use
13##! `:use :open silo:std.collections.binaryheap ...`.
14
15:use
16  :open core AnyInt Bool Option Vec
17  :open effects.panic panic
18:end
19
20# si[impl coll.binaryheap.len]
21# si[impl coll.binaryheap.is-empty]
22# si[impl coll.binaryheap.push]
23# si[impl coll.binaryheap.pop-max]
24# si[impl coll.binaryheap.peek-max]
25# si[impl coll.binaryheap.from-vec]
26# si[impl coll.binaryheap.into-sorted-vec]
27# si[impl coll.binaryheap.to-vec]
28# si[impl coll.binaryheap.merge]
29## Max-heap priority queue. Runtime layout shares `(Vec elem)` but
30## `BinaryHeap` is a distinct type for dispatch — Vec methods like
31## `.push` do NOT resolve through `BinaryHeap`.
32:type(pub) BinaryHeap elem (Vec elem)
33
34:impl (BinaryHeap elem)
35  # si[impl coll.binaryheap.len+1]
36  ## Number of elements in O(1).
37  .len ( (BinaryHeap elem) -> AnyInt )
38    binaryheap-len-intrinsic ;
39
40  # si[impl coll.binaryheap.is-empty+1]
41  ## True iff the heap contains zero elements.
42  .is-empty ( (BinaryHeap elem) -> Bool )
43    binaryheap-is-empty-intrinsic ;
44
45  # si[impl coll.binaryheap.push]
46  ## `.push` inserts an element, sift-up restores heap invariant. O(log n).
47  ## `(Ord elem elem)` constraint is implicit on the dispatch once the
48  ## real body lands; stubs skip the bound so the declared-surface
49  ## tests need no Ord witness.
50  .push ( elem (BinaryHeap elem) -> (BinaryHeap elem) )
51    :todo "awaits host sift-up/sift-down intrinsics" ;
52
53  # si[impl coll.binaryheap.pop-max]
54  ## `.pop-max` removes and returns the largest element, sift-down
55  ## restores heap invariant. O(log n).
56  .pop-max ( (BinaryHeap elem) -> (BinaryHeap elem) (Option elem) )
57    :todo "awaits host sift-up/sift-down intrinsics" ;
58
59  # si[impl coll.binaryheap.peek-max]
60  ## `.peek-max` returns the largest element without removing it. O(1).
61  .peek-max ( (BinaryHeap elem) -> (Option elem) )
62    :todo "awaits host sift-up/sift-down intrinsics" ;
63
64  # si[impl coll.binaryheap.into-sorted-vec]
65  ## Consume the heap and return a `(Vec elem)` in ascending order.
66  ## O(n log n).
67  .into-sorted-vec ( (BinaryHeap elem) -> (Vec elem) )
68    :todo "awaits host sift-up/sift-down intrinsics" ;
69
70  # si[impl coll.binaryheap.to-vec]
71  ## Return a `(Vec elem)` containing every element without consuming
72  ## the heap. Order unspecified — in particular, the stub runtime does
73  ## NOT maintain the max-heap invariant on the backing Vec, so the
74  ## ordering reflects insertion order rather than heap structure.
75  ## Callers MUST NOT depend on either heap or sorted ordering here.
76  ## Runtime identity cast — the backing cell is already a Vec. O(1).
77  .to-vec ( (BinaryHeap elem) -> (Vec elem) )
78    binaryheap-to-vec-intrinsic ;
79
80  # si[impl coll.binaryheap.merge]
81  ## `.merge` combines two heaps into a new heap containing every
82  ## element of both. Duplicates preserved. O(n + m).
83  .merge ( (BinaryHeap elem) (BinaryHeap elem) -> (BinaryHeap elem) )
84    :todo "awaits host sift-up/sift-down intrinsics" ;
85:end
86
87# si[impl coll.binaryheap.from-vec]
88## Convert a `(Vec elem)` to a `(BinaryHeap elem)`. Spec mandates
89## linear-time heapify; the WP-F3 partial body is an identity cast at
90## the runtime layer (the cell layout is already a Vec). Heap-invariant
91## restoration arrives when the real sift-up/sift-down intrinsics land —
92## callers that rely on the max-heap invariant MUST NOT depend on this
93## behaviour yet. Free fn rather than method because method dispatch on
94## `(Vec elem)` would collide across `VecDeque`, `LinkedList`,
95## `BinaryHeap` et al.
96:fn(pub) binaryheap-from-vec ( (Vec elem) -> (BinaryHeap elem) )
97  binaryheap-from-vec-intrinsic
98:end