1 # A list links up multiple objects together to make them easier to manage.
  2 #
  3 # The objects must be of the same type. If you want to store multiple types in
  4 # a single list, use an exclusive-container.
  5 
  6 container list:_elem [
  7   value:_elem
  8   next:&:list:_elem
  9 ]
 10 
 11 def push x:_elem, l:&:list:_elem -> result:&:list:_elem/contained-in:l [
 12   local-scope
 13   load-inputs
 14   result <- new {(list _elem): type}
 15   *result <- merge x, l
 16 ]
 17 
 18 def first in:&:list:_elem -> result:_elem [
 19   local-scope
 20   load-inputs
 21   result <- get *in, value:offset
 22 ]
 23 
 24 def rest in:&:list:_elem -> result:&:list:_elem/contained-in:in [
 25   local-scope
 26   load-inputs
 27   result <- get *in, next:offset
 28 ]
 29 
 30 scenario list-handling [
 31   run [
 32     local-scope
 33     x:&:list:num <- push 3, null
 34     x <- push 4, x
 35     x <- push 5, x
 36     10:num/raw <- first x
 37     x <- rest x
 38     11:num/raw <- first x
 39     x <- rest x
 40     12:num/raw <- first x
 41     20:&:list:num/raw <- rest x
 42   ]
 43   memory-should-contain [
 44     10 <- 5
 45     11 <- 4
 46     12 <- 3
 47     20 <- 0  # nothing left
 48   ]
 49 ]
 50 
 51 def length l:&:list:_elem -> result:num [
 52   local-scope
 53   load-inputs
 54   result <- copy 0
 55   {
 56     break-unless l
 57     result <- add result, 1
 58     l <- rest l
 59     loop
 60   }
 61 ]
 62 
 63 # insert 'x' after 'in'
 64 def insert x:_elem, in:&:list:_elem -> in:&:list:_elem [
 65   local-scope
 66   load-inputs
 67   new-node:&:list:_elem <- new {(list _elem): type}
 68   *new-node <- put *new-node, value:offset, x
 69   next-node:&:list:_elem <- get *in, next:offset
 70   *in <- put *in, next:offset, new-node
 71   *new-node <- put *new-node, next:offset, next-node
 72 ]
 73 
 74 scenario inserting-into-list [
 75   local-scope
 76   list:&:list:num <- push 3, null
 77   list <- push 4, list
 78   list <- push 5, list
 79   run [
 80     list2:&:list:num <- rest list  # inside list
 81     list2 <- insert 6, list2
 82     # check structure
 83     list2 <- copy list
 84     10:num/raw <- first list2
 85     list2 <- rest list2
 86     11:num/raw <- first list2
 87     list2 <- rest list2
 88     12:num/raw <- first list2
 89     list2 <- rest list2
 90     13:num/raw <- first list2
 91   ]
 92   memory-should-contain [
 93     10 <- 5  # scanning next
 94     11 <- 4
 95     12 <- 6  # inserted element
 96     13 <- 3
 97   ]
 98 ]
 99 
100 scenario inserting-at-end-of-list [
101   local-scope
102   list:&:list:num <- push 3, null
103   list <- push 4, list
104   list <- push 5, list
105   run [
106     list2:&:list:num <- rest list  # inside list
107     list2 <- rest list2  # now at end of list
108     list2 <- insert 6, list2
109     # check structure like before
110     list2 <- copy list
111     10:num/raw <- first list2
112     list2 <- rest list2
113     11:num/raw <- first list2
114     list2 <- rest list2
115     12:num/raw <- first list2
116     list2 <- rest list2
117     13:num/raw <- first list2
118   ]
119   memory-should-contain [
120     10 <- 5  # scanning next
121     11 <- 4
122     12 <- 3
123     13 <- 6  # inserted element
124   ]
125 ]
126 
127 scenario inserting-after-start-of-list [
128   local-scope
129   list:&:list:num <- push 3, null
130   list <- push 4, list
131   list <- push 5, list
132   run [
133     list <- insert 6, list
134     # check structure like before
135     list2:&:list:num <- copy list
136     10:num/raw <- first list2
137     list2 <- rest list2
138     11:num/raw <- first list2
139     list2 <- rest list2
140     12:num/raw <- first list2
141     list2 <- rest list2
142     13:num/raw <- first list2
143   ]
144   memory-should-contain [
145     10 <- 5  # scanning next
146     11 <- 6  # inserted element
147     12 <- 4
148     13 <- 3
149   ]
150 ]
151 
152 # remove 'x' from its surrounding list 'in'
153 #
154 # Returns null if and only if list is empty. Beware: in that case any other
155 # pointers to the head are now invalid.
156 def remove x:&:list:_elem/contained-in:in, in:&:list:_elem -> in:&:list:_elem [
157   local-scope
158   load-inputs
159   # if 'x' is null, return
160   return-unless x
161   next-node:&:list:_elem <- rest x
162   # clear next pointer of 'x'
163   *x <- put *x, next:offset, null
164   # if 'x' is at the head of 'in', return the new head
165   at-head?:bool <- equal x, in
166   return-if at-head?, next-node
167   # compute prev-node
168   prev-node:&:list:_elem <- copy in
169   curr:&:list:_elem <- rest prev-node
170   {
171     return-unless curr
172     found?:bool <- equal curr, x
173     break-if found?
174     prev-node <- copy curr
175     curr <- rest curr
176   }
177   # set its next pointer to skip 'x'
178   *prev-node <- put *prev-node, next:offset, next-node
179 ]
180 
181 scenario removing-from-list [
182   local-scope
183   list:&:list:num <- push 3, null
184   list <- push 4, list
185   list <- push 5, list
186   run [
187     list2:&:list:num <- rest list  # second element
188     list <- remove list2, list
189     10:bool/raw <- equal list2, null
190     # check structure like before
191     list2 <- copy list
192     11:num/raw <- first list2
193     list2 <- rest list2
194     12:num/raw <- first list2
195     20:&:list:num/raw <- rest list2
196   ]
197   memory-should-contain [
198     10 <- 0  # remove returned non-null
199     11 <- 5  # scanning next, skipping deleted element
200     12 <- 3
201     20 <- 0  # no more elements
202   ]
203 ]
204 
205 scenario removing-from-start-of-list [
206   local-scope
207   list:&:list:num <- push 3, null
208   list <- push 4, list
209   list <- push 5, list
210   run [
211     list <- remove list, list
212     # check structure like before
213     list2:&:list:num <- copy list
214     10:num/raw <- first list2
215     list2 <- rest list2
216     11:num/raw <- first list2
217     20:&:list:num/raw <- rest list2
218   ]
219   memory-should-contain [
220     10 <- 4  # scanning next, skipping deleted element
221     11 <- 3
222     20 <- 0  # no more elements
223   ]
224 ]
225 
226 scenario removing-from-end-of-list [
227   local-scope
228   list:&:list:num <- push 3, null
229   list <- push 4, list
230   list <- push 5, list
231   run [
232     # delete last element
233     list2:&:list:num <- rest list
234     list2 <- rest list2
235     list <- remove list2, list
236     10:bool/raw <- equal list2, null
237     # check structure like before
238     list2 <- copy list
239     11:num/raw <- first list2
240     list2 <- rest list2
241     12:num/raw <- first list2
242     20:&:list:num/raw <- rest list2
243   ]
244   memory-should-contain [
245     10 <- 0  # remove returned non-null
246     11 <- 5  # scanning next, skipping deleted element
247     12 <- 4
248     20 <- 0  # no more elements
249   ]
250 ]
251 
252 scenario removing-from-singleton-list [
253   local-scope
254   list:&:list:num <- push 3, null
255   run [
256     list <- remove list, list
257     1:num/raw <- deaddress list
258   ]
259   memory-should-contain [
260     1 <- 0  # back to an empty list
261   ]
262 ]
263 
264 # reverse the elements of a list
265 # (contributed by Caleb Couch)
266 def reverse list:&:list:_elem temp:&:list:_elem/contained-in:result -> result:&:list:_elem [
267   local-scope
268   load-inputs
269   return-unless list, temp
270   object:_elem <- first, list
271   list <- rest list
272   temp <- push object, temp
273   result <- reverse list, temp
274 ]
275 
276 scenario reverse-list [
277   local-scope
278   list:&:list:num <- push 1, null
279   list <- push 2, list
280   list <- push 3, list
281   run [
282     stash [list:], list
283     list <- reverse list
284     stash [reversed:], list
285   ]
286   trace-should-contain [
287     app: list: 3 -> 2 -> 1
288     app: reversed: 1 -> 2 -> 3
289   ]
290 ]
291 
292 scenario stash-list [
293   local-scope
294   list:&:list:num <- push 1, null
295   list <- push 2, list
296   list <- push 3, list
297   run [
298     stash [list:], list
299   ]
300   trace-should-contain [
301     app: list: 3 -> 2 -> 1
302   ]
303 ]
304 
305 def to-text in:&:list:_elem -> result:text [
306   local-scope
307   load-inputs
308   buf:&:buffer:char <- new-buffer 80
309   buf <- to-buffer in, buf
310   result <- buffer-to-array buf
311 ]
312 
313 # variant of 'to-text' which stops printing after a few elements (and so is robust to cycles)
314 def to-text-line in:&:list:_elem -> result:text [
315   local-scope
316   load-inputs
317   buf:&:buffer:char <- new-buffer 80
318   buf <- to-buffer in, buf, 6  # max elements to display
319   result <- buffer-to-array buf
320 ]
321 
322 def to-buffer in:&:list:_elem, buf:&:buffer:char -> buf:&:buffer:char [
323   local-scope
324   load-inputs
325   {
326     break-if in
327     buf <- append buf, [[]]
328     return
329   }
330   # append in.value to buf
331   val:_elem <- get *in, value:offset
332   buf <- append buf, val
333   # now prepare next
334   next:&:list:_elem <- rest in
335   nextn:num <- deaddress next
336   return-unless next
337   buf <- append buf, [ -> ]
338   # and recurse
339   remaining:num, optional-input-found?:bool <- next-input
340   {
341     break-if optional-input-found?
342     # unlimited recursion
343     buf <- to-buffer next, buf
344     return
345   }
346   {
347     break-unless remaining
348     # limited recursion
349     remaining <- subtract remaining, 1
350     buf <- to-buffer next, buf, remaining
351     return
352   }
353   # past recursion depth; insert ellipses and stop
354   append buf, [...]
355 ]
356 
357 scenario stash-empty-list [
358   local-scope
359   x:&:list:num <- copy null
360   run [
361     stash x
362   ]
363   trace-should-contain [
364     app: []
365   ]
366 ]