Source src/silo:std.collections.linkedlist

1##! LinkedList — doubly-linked list with O(1) push/pop at both ends.
2##!
3##! `LinkedList 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 a
7##! doubly-linked node allocation surface for O(1) splice and O(n)
8##! walks. `Cursor` / `CursorMut` are deferred; Seq-hierarchy impls
9##! (`Foldable`, `Mappable`, `Filterable`, `Chainable`, `Indexed`,
10##! `Zippable`) arrive alongside that wiring.
11##!
12##! Not re-exported by the prelude — use
13##! `:use :open silo:std.collections.linkedlist ...`.
14
15:use
16  :open core AnyInt Bool Option Vec Pair
17  :open effects.panic panic
18:end
19
20# si[impl coll.linkedlist.len]
21# si[impl coll.linkedlist.is-empty]
22# si[impl coll.linkedlist.push-front]
23# si[impl coll.linkedlist.push-back]
24# si[impl coll.linkedlist.pop-front]
25# si[impl coll.linkedlist.pop-back]
26# si[impl coll.linkedlist.front]
27# si[impl coll.linkedlist.back]
28# si[impl coll.linkedlist.append]
29# si[impl coll.linkedlist.prepend]
30# si[impl coll.linkedlist.split-at]
31# si[impl coll.linkedlist.reverse]
32# si[impl coll.linkedlist.get]
33# si[impl coll.linkedlist.zip]
34# si[impl coll.linkedlist.from-vec]
35# si[impl coll.linkedlist.to-vec]
36## Doubly-linked list. Runtime layout shares `(Vec elem)` but
37## `LinkedList` is a distinct type for dispatch — Vec methods like
38## `.push` do NOT resolve through `LinkedList`.
39:type(pub) LinkedList elem (Vec elem)
40
41:impl (LinkedList elem)
42  # si[impl coll.linkedlist.len+1]
43  ## Number of elements in O(1). Implementations MUST cache length.
44  .len ( (LinkedList elem) -> AnyInt )
45    linkedlist-len-intrinsic ;
46
47  # si[impl coll.linkedlist.is-empty+1]
48  ## True iff the list contains zero elements.
49  .is-empty ( (LinkedList elem) -> Bool )
50    linkedlist-is-empty-intrinsic ;
51
52  # si[impl coll.linkedlist.front]
53  ## `.front` returns `Some` with the first element or `None` if empty. O(1).
54  ## Real body: reads the first element of the backing Vec cell (LinkedList
55  ## is a newtype over `(Vec elem)`), wraps it in `Some`, or returns `None`
56  ## on an empty list. Real doubly-linked-node semantics arrive with a
57  ## follow-up WP; this body is correct for the Vec-layout stub.
58  .front ( (LinkedList elem) -> (Option elem) )
59    linkedlist-front-intrinsic ;
60
61  # si[impl coll.linkedlist.back]
62  ## `.back` returns `Some` with the last element or `None` if empty. O(1).
63  ## Real body: reads the last element of the backing Vec cell.
64  .back ( (LinkedList elem) -> (Option elem) )
65    linkedlist-back-intrinsic ;
66
67  # si[impl coll.linkedlist.push-front]
68  ## Prepend an element to the front. Spec-guaranteed O(1); on the
69  ## Vec-layout stub this rebuilds the backing Vec so it is O(n) until
70  ## the doubly-linked-node runtime lands.
71  .push-front ( elem (LinkedList elem) -> (LinkedList elem) )
72    linkedlist-push-front-intrinsic ;
73
74  # si[impl coll.linkedlist.push-back]
75  ## Append an element to the back. O(1).
76  .push-back ( elem (LinkedList elem) -> (LinkedList elem) )
77    :todo "awaits host doubly-linked-node intrinsics" ;
78
79  # si[impl coll.linkedlist.pop-front]
80  ## Remove and return the front element. O(1).
81  .pop-front ( (LinkedList elem) -> (LinkedList elem) (Option elem) )
82    :todo "awaits host doubly-linked-node intrinsics" ;
83
84  # si[impl coll.linkedlist.pop-back]
85  ## Remove and return the back element. O(1).
86  .pop-back ( (LinkedList elem) -> (LinkedList elem) (Option elem) )
87    :todo "awaits host doubly-linked-node intrinsics" ;
88
89  # si[impl coll.linkedlist.append]
90  ## Move all elements of the second list onto the back of the first.
91  ## Spec-guaranteed O(1); on the Vec-layout stub this copies both Vecs.
92  .append ( (LinkedList elem) (LinkedList elem) -> (LinkedList elem) )
93    linkedlist-append-intrinsic ;
94
95  # si[impl coll.linkedlist.prepend]
96  ## Move all elements of the second list onto the front of the first.
97  ## Spec-guaranteed O(1); on the Vec-layout stub this copies both Vecs.
98  .prepend ( (LinkedList elem) (LinkedList elem) -> (LinkedList elem) )
99    linkedlist-prepend-intrinsic ;
100
101  # si[impl coll.linkedlist.split-at]
102  ## Split the list at the given 0-based index, returning prefix + suffix.
103  ## Complexity O(min(n, len - n)); negative `n` is a runtime error.
104  .split-at ( AnyInt (LinkedList elem) -> (LinkedList elem) (LinkedList elem) )
105    :todo "awaits host doubly-linked-node intrinsics" ;
106
107  # si[impl coll.linkedlist.reverse]
108  ## Return a new list with elements in reverse order. O(n).
109  .reverse ( (LinkedList elem) -> (LinkedList elem) )
110    linkedlist-reverse-intrinsic ;
111
112  # si[impl coll.linkedlist.get]
113  ## Return `Some` with the element at the given 0-based index, or `None`
114  ## if out of bounds. O(n) — walks from nearer end.
115  .get ( AnyInt (LinkedList elem) -> (Option elem) )
116    :todo "awaits host doubly-linked-node intrinsics" ;
117
118  # si[impl coll.linkedlist.to-vec]
119  ## Convert a `(LinkedList elem)` to a `(Vec elem)` in front-to-back order.
120  ## Runtime identity cast — the backing cell is already a Vec.
121  .to-vec ( (LinkedList elem) -> (Vec elem) )
122    linkedlist-to-vec-intrinsic ;
123:end
124
125# si[impl coll.linkedlist.zip]
126## `.zip` — free-fn form. Methods dispatch on Self and `.zip` would
127## collide with `Zippable` once that trait is wired onto `LinkedList`;
128## until then the free fn keeps the surface reachable without deciding
129## the Zippable question. Pairs elements positionally; result length is
130## `min(a.len, b.len)`.
131:fn(pub) linkedlist-zip ( (LinkedList a) (LinkedList b) -> (LinkedList (Pair a b)) )
132  :todo "awaits host doubly-linked-node intrinsics"
133:end
134
135# si[impl coll.linkedlist.from-vec]
136## Convert a `(Vec elem)` to a `(LinkedList elem)`, preserving order.
137## Free fn rather than method because method dispatch on `(Vec elem)`
138## would collide across `VecDeque`, `LinkedList`, `BinaryHeap` et al.
139## Runtime identity cast — the underlying cell is already a Vec.
140:fn(pub) linkedlist-from-vec ( (Vec elem) -> (LinkedList elem) )
141  linkedlist-from-vec-intrinsic
142:end