Source src/silo:std.collections.vecdeque

1##! VecDeque — double-ended queue with O(1) push/pop at both ends.
2##!
3##! `VecDeque elem` is a newtype over `(Vec elem)` — runtime layout
4##! matches `Vec`, but dispatch treats it as a nominally distinct type.
5##! `.from-vec` / `.to-vec` are identity casts at the cell level; the
6##! checker still rejects Vec-only methods on a `VecDeque`.
7##!
8##! Most methods (`.len`, `.is-empty`, `.front`, `.back`, `.push-back`,
9##! `.push-front`, `.pop-front`, `.pop-back`, `.reverse`, `.to-vec`,
10##! `vecdeque-from-vec`) have real bodies backed by host intrinsics.
11##! Front-side ops run in O(n) under the current Vec-backed layout;
12##! the O(1) guarantee returns with a real ring-buffer runtime.
13##!
14##! `.rotate-left`, `.rotate-right`, `vecdeque-contains`, and
15##! `vecdeque-retain` remain panicking stubs until Result-returning
16##! intrinsics, `(Eq elem elem)` constraint resolution inside
17##! intrinsics, and host-side quotation dispatch land. Seq-hierarchy
18##! impls arrive alongside the `Bytes` follow-ups.
19##!
20##! Not re-exported by the prelude — use
21##! `:use :open silo:std.collections.vecdeque ...`.
22
23:use
24  :open core AnyInt Bool Option Vec
25  :open effects.panic panic
26:end
27
28## Double-ended queue. Runtime layout shares `(Vec elem)` but `VecDeque`
29## is a distinct type for dispatch — Vec methods like `.push` do NOT
30## resolve through `VecDeque`.
31:type(pub) VecDeque elem (Vec elem)
32
33:impl (VecDeque elem)
34  # si[impl coll.vecdeque.len]
35  ## Number of elements in O(1).
36  .len ( (VecDeque elem) -> AnyInt )
37    vecdeque-len-intrinsic ;
38
39  # si[impl coll.vecdeque.is-empty]
40  ## True iff the deque contains zero elements.
41  .is-empty ( (VecDeque elem) -> Bool )
42    vecdeque-is-empty-intrinsic ;
43
44  # si[impl coll.vecdeque.front]
45  ## `.front` returns `Some` with the front element or `None` if empty. O(1).
46  .front ( (VecDeque elem) -> (Option elem) )
47    vecdeque-front-intrinsic ;
48
49  # si[impl coll.vecdeque.back]
50  ## `.back` returns `Some` with the back element or `None` if empty. O(1).
51  .back ( (VecDeque elem) -> (Option elem) )
52    vecdeque-back-intrinsic ;
53
54  # si[impl coll.vecdeque.push-front]
55  ## Prepend an element to the front. Spec-guaranteed O(1); on the
56  ## Vec-layout stub this rebuilds the backing Vec so it is O(n) until
57  ## the ring-buffer runtime lands.
58  .push-front ( elem (VecDeque elem) -> (VecDeque elem) )
59    vecdeque-push-front-intrinsic ;
60
61  # si[impl coll.vecdeque.push-back]
62  ## Append an element to the back. Amortised O(1).
63  .push-back ( elem (VecDeque elem) -> (VecDeque elem) )
64    vecdeque-push-back-intrinsic ;
65
66  # si[impl coll.vecdeque.pop-front]
67  ## Remove and return the front element. Spec-guaranteed O(1); O(n) on
68  ## the Vec-layout stub. Returns the modified deque then the
69  ## `(Option elem)` — `Some` when non-empty, `None` otherwise.
70  .pop-front ( (VecDeque elem) -> (VecDeque elem) (Option elem) )
71    vecdeque-pop-front-intrinsic ;
72
73  # si[impl coll.vecdeque.pop-back]
74  ## Remove and return the back element. O(1).
75  .pop-back ( (VecDeque elem) -> (VecDeque elem) (Option elem) )
76    vecdeque-pop-back-intrinsic ;
77
78  # si[impl coll.vecdeque.reverse]
79  ## Return a new `VecDeque` with elements in reverse order. O(n).
80  .reverse ( (VecDeque elem) -> (VecDeque elem) )
81    vecdeque-reverse-intrinsic ;
82
83  # si[impl coll.vecdeque.rotate-left]
84  ## Rotate left by `n` positions; first `n` elements move to the back.
85  ## `n` is taken modulo `.len`; negative `n` is a runtime error. Stub.
86  .rotate-left ( AnyInt (VecDeque elem) -> (VecDeque elem) )
87    :todo "awaits host ring-buffer intrinsics" ;
88
89  # si[impl coll.vecdeque.rotate-right+1]
90  ## Rotate right by `n` positions; last `n` elements move to the front.
91  ## `n` is taken modulo `.len`; negative `n` is a runtime error. Stub.
92  .rotate-right ( AnyInt (VecDeque elem) -> (VecDeque elem) )
93    :todo "awaits host ring-buffer intrinsics" ;
94
95  # si[impl coll.vecdeque.to-vec]
96  ## Convert a `(VecDeque elem)` to a `(Vec elem)` in front-to-back
97  ## order. Runtime identity cast — the underlying cell is already a Vec.
98  .to-vec ( (VecDeque elem) -> (Vec elem) )
99    vecdeque-to-vec-intrinsic ;
100:end
101
102# si[impl coll.vecdeque.from-vec]
103## Convert a `(Vec elem)` to a `(VecDeque elem)`, preserving element order.
104## Runtime identity cast — see `.to-vec`.
105:fn(pub) vecdeque-from-vec ( (Vec elem) -> (VecDeque elem) )
106  vecdeque-from-vec-intrinsic
107:end
108
109# si[impl coll.vecdeque.contains]
110## `.contains` — free-fn form, takes `(Eq elem elem)` by trait constraint.
111## Stub — awaits host-side trait resolution for `(Eq elem elem)`.
112:fn(pub) vecdeque-contains ( elem (VecDeque elem) -> Bool ) { (Eq elem elem) }
113  :todo "awaits host ring-buffer intrinsics"
114:end
115
116# si[impl coll.vecdeque.retain]
117## `.retain` — free-fn form, keeps elements for which the predicate is
118## true. Stub — awaits host-side quotation invocation.
119:fn(pub) vecdeque-retain ( [ elem -> Bool ] (VecDeque elem) -> (VecDeque elem) )
120  :todo "awaits host ring-buffer intrinsics"
121:end