1 # A doubly linked list permits bidirectional traversal.
  2 
  3 container duplex-list:_elem [
  4   value:_elem
  5   next:&:duplex-list:_elem
  6   prev:&:duplex-list:_elem
  7 ]
  8 
  9 # should I say in/contained-in:result, allow ingredients to refer to products?
 10 def push x:_elem, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
 11   local-scope
 12   load-ingredients
 13   result:&:duplex-list:_elem <- new {(duplex-list _elem): type}
 14   *result <- merge x, in, 0
 15   {
 16   ¦ break-unless in
 17   ¦ *in <- put *in, prev:offset, result
 18   }
 19   return result  # needed explicitly because we need to replace 'in' with 'result'
 20 ]
 21 
 22 def first in:&:duplex-list:_elem -> result:_elem [
 23   local-scope
 24   load-ingredients
 25   return-unless in, 0
 26   result <- get *in, value:offset
 27 ]
 28 
 29 def next in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [
 30   local-scope
 31   load-ingredients
 32   return-unless in, 0
 33   result <- get *in, next:offset
 34 ]
 35 
 36 def prev in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [
 37   local-scope
 38   load-ingredients
 39   return-unless in, 0
 40   result <- get *in, prev:offset
 41   return result
 42 ]
 43 
 44 scenario duplex-list-handling [
 45   run [
 46   ¦ local-scope
 47   ¦ # reserve locations 0-9 to check for missing null check
 48   ¦ 10:num/raw <- copy 34
 49   ¦ 11:num/raw <- copy 35
 50   ¦ list:&:duplex-list:char <- push 3, 0
 51   ¦ list <- push 4, list
 52   ¦ list <- push 5, list
 53   ¦ list2:&:duplex-list:char <- copy list
 54   ¦ 20:char/raw <- first list2
 55   ¦ list2 <- next list2
 56   ¦ 21:char/raw <- first list2
 57   ¦ list2 <- next list2
 58   ¦ 22:char/raw <- first list2
 59   ¦ 30:&:duplex-list:char/raw <- next list2
 60   ¦ 31:char/raw <- first 30:&:duplex-list:char/raw
 61   ¦ 32:&:duplex-list:char/raw <- next 30:&:duplex-list:char/raw
 62   ¦ 33:&:duplex-list:char/raw <- prev 30:&:duplex-list:char/raw
 63   ¦ list2 <- prev list2
 64   ¦ 40:char/raw <- first list2
 65   ¦ list2 <- prev list2
 66   ¦ 41:char/raw <- first list2
 67   ¦ 50:bool/raw <- equal list, list2
 68   ]
 69   memory-should-contain [
 70   ¦ 0 <- 0  # no modifications to null pointers
 71   ¦ 10 <- 34
 72   ¦ 11 <- 35
 73   ¦ 20 <- 5  # scanning next
 74   ¦ 21 <- 4
 75   ¦ 22 <- 3
 76   ¦ 30 <- 0  # null
 77   ¦ 31 <- 0  # first of null
 78   ¦ 32 <- 0  # next of null
 79   ¦ 33 <- 0  # prev of null
 80   ¦ 40 <- 4  # then start scanning prev
 81   ¦ 41 <- 5
 82   ¦ 50 <- 1  # list back at start
 83   ]
 84 ]
 85 
 86 # insert 'x' after 'in'
 87 def insert x:_elem, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
 88   local-scope
 89   load-ingredients
 90   new-node:&:duplex-list:_elem <- new {(duplex-list _elem): type}
 91   *new-node <- put *new-node, value:offset, x
 92   # save old next before changing it
 93   next-node:&:duplex-list:_elem <- get *in, next:offset
 94   *in <- put *in, next:offset, new-node
 95   *new-node <- put *new-node, prev:offset, in
 96   *new-node <- put *new-node, next:offset, next-node
 97   return-unless next-node
 98   *next-node <- put *next-node, prev:offset, new-node
 99 ]
100 
101 scenario inserting-into-duplex-list [
102   local-scope
103   list:&:duplex-list:char <- push 3, 0
104   list <- push 4, list
105   list <- push 5, list
106   run [
107   ¦ list2:&:duplex-list:char <- next list  # inside list
108   ¦ list2 <- insert 6, list2
109   ¦ # check structure like before
110   ¦ list2 <- copy list
111   ¦ 10:char/raw <- first list2
112   ¦ list2 <- next list2
113   ¦ 11:char/raw <- first list2
114   ¦ list2 <- next list2
115   ¦ 12:char/raw <- first list2
116   ¦ list2 <- next list2
117   ¦ 13:char/raw <- first list2
118   ¦ list2 <- prev list2
119   ¦ 20:char/raw <- first list2
120   ¦ list2 <- prev list2
121   ¦ 21:char/raw <- first list2
122   ¦ list2 <- prev list2
123   ¦ 22:char/raw <- first list2
124   ¦ 30:bool/raw <- equal list, list2
125   ]
126   memory-should-contain [
127   ¦ 10 <- 5  # scanning next
128   ¦ 11 <- 4
129   ¦ 12 <- 6  # inserted element
130   ¦ 13 <- 3
131   ¦ 20 <- 6  # then prev
132   ¦ 21 <- 4
133   ¦ 22 <- 5
134   ¦ 30 <- 1  # list back at start
135   ]
136 ]
137 
138 scenario inserting-at-end-of-duplex-list [
139   local-scope
140   list:&:duplex-list:char <- push 3, 0
141   list <- push 4, list
142   list <- push 5, list
143   run [
144   ¦ list2:&:duplex-list:char <- next list  # inside list
145   ¦ list2 <- next list2  # now at end of list
146   ¦ list2 <- insert 6, list2
147   ¦ # check structure like before
148   ¦ list2 <- copy list
149   ¦ 10:char/raw <- first list2
150   ¦ list2 <- next list2
151   ¦ 11:char/raw <- first list2
152   ¦ list2 <- next list2
153   ¦ 12:char/raw <- first list2
154   ¦ list2 <- next list2
155   ¦ 13:char/raw <- first list2
156   ¦ list2 <- prev list2
157   ¦ 20:char/raw <- first list2
158   ¦ list2 <- prev list2
159   ¦ 21:char/raw <- first list2
160   ¦ list2 <- prev list2
161   ¦ 22:char/raw <- first list2
162   ¦ 30:bool/raw <- equal list, list2
163   ]
164   memory-should-contain [
165   ¦ 10 <- 5  # scanning next
166   ¦ 11 <- 4
167   ¦ 12 <- 3
168   ¦ 13 <- 6  # inserted element
169   ¦ 20 <- 3  # then prev
170   ¦ 21 <- 4
171   ¦ 22 <- 5
172   ¦ 30 <- 1  # list back at start
173   ]
174 ]
175 
176 scenario inserting-after-start-of-duplex-list [
177   local-scope
178   list:&:duplex-list:char <- push 3, 0
179   list <- push 4, list
180   list <- push 5, list
181   run [
182   ¦ list <- insert 6, list
183   ¦ # check structure like before
184   ¦ list2:&:duplex-list:char <- copy list
185   ¦ 10:char/raw <- first list2
186   ¦ list2 <- next list2
187   ¦ 11:char/raw <- first list2
188   ¦ list2 <- next list2
189   ¦ 12:char/raw <- first list2
190   ¦ list2 <- next list2
191   ¦ 13:char/raw <- first list2
192   ¦ list2 <- prev list2
193   ¦ 20:char/raw <- first list2
194   ¦ list2 <- prev list2
195   ¦ 21:char/raw <- first list2
196   ¦ list2 <- prev list2
197   ¦ 22:char/raw <- first list2
198   ¦ 30:bool/raw <- equal list, list2
199   ]
200   memory-should-contain [
201   ¦ 10 <- 5  # scanning next
202   ¦ 11 <- 6  # inserted element
203   ¦ 12 <- 4
204   ¦ 13 <- 3
205   ¦ 20 <- 4  # then prev
206   ¦ 21 <- 6
207   ¦ 22 <- 5
208   ¦ 30 <- 1  # list back at start
209   ]
210 ]
211 
212 # remove 'x' from its surrounding list 'in'
213 #
214 # Returns null if and only if list is empty. Beware: in that case any other
215 # pointers to the head are now invalid.
216 def remove x:&:duplex-list:_elem/contained-in:in, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
217   local-scope
218   load-ingredients
219   # if 'x' is null, return
220   return-unless x
221   next-node:&:duplex-list:_elem <- get *x, next:offset
222   prev-node:&:duplex-list:_elem <- get *x, prev:offset
223   # null x's pointers
224   *x <- put *x, next:offset, 0
225   *x <- put *x, prev:offset, 0
226   # if next-node is not null, set its prev pointer
227   {
228   ¦ break-unless next-node
229   ¦ *next-node <- put *next-node, prev:offset, prev-node
230   }
231   # if prev-node is not null, set its next pointer and return
232   {
233   ¦ break-unless prev-node
234   ¦ *prev-node <- put *prev-node, next:offset, next-node
235   ¦ return
236   }
237   # if prev-node is null, then we removed the head node at 'in'
238   # return the new head rather than the old 'in'
239   return next-node
240 ]
241 
242 scenario removing-from-duplex-list [
243   local-scope
244   list:&:duplex-list:char <- push 3, 0
245   list <- push 4, list
246   list <- push 5, list
247   run [
248   ¦ list2:&:duplex-list:char <- next list  # second element
249   ¦ list <- remove list2, list
250   ¦ 10:bool/raw <- equal list2, 0
251   ¦ # check structure like before
252   ¦ list2 <- copy list
253   ¦ 11:char/raw <- first list2
254   ¦ list2 <- next list2
255   ¦ 12:char/raw <- first list2
256   ¦ 20:&:duplex-list:char/raw <- next list2
257   ¦ list2 <- prev list2
258   ¦ 30:char/raw <- first list2
259   ¦ 40:bool/raw <- equal list, list2
260   ]
261   memory-should-contain [
262   ¦ 10 <- 0  # remove returned non-null
263   ¦ 11 <- 5  # scanning next, skipping deleted element
264   ¦ 12 <- 3
265   ¦ 20 <- 0  # no more elements
266   ¦ 30 <- 5  # prev of final element
267   ¦ 40 <- 1  # list back at start
268   ]
269 ]
270 
271 scenario removing-from-start-of-duplex-list [
272   local-scope
273   list:&:duplex-list:char <- push 3, 0
274   list <- push 4, list
275   list <- push 5, list
276   run [
277   ¦ list <- remove list, list
278   ¦ # check structure like before
279   ¦ list2:&:duplex-list:char <- copy list
280   ¦ 10:char/raw <- first list2
281   ¦ list2 <- next list2
282   ¦ 11:char/raw <- first list2
283   ¦ 20:&:duplex-list:char/raw <- next list2
284   ¦ list2 <- prev list2
285   ¦ 30:char/raw <- first list2
286   ¦ 40:bool/raw <- equal list, list2
287   ]
288   memory-should-contain [
289   ¦ 10 <- 4  # scanning next, skipping deleted element
290   ¦ 11 <- 3
291   ¦ 20 <- 0  # no more elements
292   ¦ 30 <- 4  # prev of final element
293   ¦ 40 <- 1  # list back at start
294   ]
295 ]
296 
297 scenario removing-from-end-of-duplex-list [
298   local-scope
299   list:&:duplex-list:char <- push 3, 0
300   list <- push 4, list
301   list <- push 5, list
302   run [
303   ¦ # delete last element
304   ¦ list2:&:duplex-list:char <- next list
305   ¦ list2 <- next list2
306   ¦ list <- remove list2, list
307   ¦ 10:bool/raw <- equal list2, 0
308   ¦ # check structure like before
309   ¦ list2 <- copy list
310   ¦ 11:char/raw <- first list2
311   ¦ list2 <- next list2
312   ¦ 12:char/raw <- first list2
313   ¦ 20:&:duplex-list:char/raw <- next list2
314   ¦ list2 <- prev list2
315   ¦ 30:char/raw <- first list2
316   ¦ 40:bool/raw <- equal list, list2
317   ]
318   memory-should-contain [
319   ¦ 10 <- 0  # remove returned non-null
320   ¦ 11 <- 5  # scanning next, skipping deleted element
321   ¦ 12 <- 4
322   ¦ 20 <- 0  # no more elements
323   ¦ 30 <- 5  # prev of final element
324   ¦ 40 <- 1  # list back at start
325   ]
326 ]
327 
328 scenario removing-from-singleton-duplex-list [
329   local-scope
330   list:&:duplex-list:char <- push 3, 0
331   run [
332   ¦ list <- remove list, list
333   ¦ 1:num/raw <- copy list
334   ]
335   memory-should-contain [
336   ¦ 1 <- 0  # back to an empty list
337   ]
338 ]
339 
340 # remove values between 'start' and 'end' (both exclusive).
341 # also clear pointers back out from start/end for hygiene.
342 # set end to 0 to delete everything past start.
343 # can't set start to 0 to delete everything before end, because there's no
344 # clean way to return the new head pointer.
345 def remove-between start:&:duplex-list:_elem, end:&:duplex-list:_elem/contained-in:start -> start:&:duplex-list:_elem [
346   local-scope
347   load-ingredients
348   next:&:duplex-list:_elem <- get *start, next:offset
349   nothing-to-delete?:bool <- equal next, end
350   return-if nothing-to-delete?
351   assert next, [malformed duplex list]
352   # start->next->prev = 0
353   # start->next = end
354   *next <- put *next, prev:offset, 0
355   *start <- put *start, next:offset, end
356   return-unless end
357   # end->prev->next = 0
358   # end->prev = start
359   prev:&:duplex-list:_elem <- get *end, prev:offset
360   assert prev, [malformed duplex list - 2]
361   *prev <- put *prev, next:offset, 0
362   *end <- put *end, prev:offset, start
363 ]
364 
365 scenario remove-range [
366   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
367   local-scope
368   list:&:duplex-list:char <- push 18, 0
369   list <- push 17, list
370   list <- push 16, list
371   list <- push 15, list
372   list <- push 14, list
373   list <- push 13, list
374   run [
375   ¦ # delete 16 onwards
376   ¦ # first pointer: to the third element
377   ¦ list2:&:duplex-list:char <- next list
378   ¦ list2 <- next list2
379   ¦ list2 <- remove-between list2, 0
380   ¦ # now check the list
381   ¦ 10:char/raw <- get *list, value:offset
382   ¦ list <- next list
383   ¦ 11:char/raw <- get *list, value:offset
384   ¦ list <- next list
385   ¦ 12:char/raw <- get *list, value:offset
386   ¦ 20:&:duplex-list:char/raw <- next list
387   ]
388   memory-should-contain [
389   ¦ 10 <- 13
390   ¦ 11 <- 14
391   ¦ 12 <- 15
392   ¦ 20 <- 0
393   ]
394 ]
395 
396 scenario remove-range-to-final [
397   local-scope
398   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
399   list:&:duplex-list:char <- push 18, 0
400   list <- push 17, list
401   list <- push 16, list
402   list <- push 15, list
403   list <- push 14, list
404   list <- push 13, list
405   run [
406   ¦ # delete 15, 16 and 17
407   ¦ # start pointer: to the second element
408   ¦ list2:&:duplex-list:char <- next list
409   ¦ # end pointer: to the last (sixth) element
410   ¦ end:&:duplex-list:char <- next list2
411   ¦ end <- next end
412   ¦ end <- next end
413   ¦ end <- next end
414   ¦ remove-between list2, end
415   ¦ # now check the list
416   ¦ 10:char/raw <- get *list, value:offset
417   ¦ list <- next list
418   ¦ 11:char/raw <- get *list, value:offset
419   ¦ list <- next list
420   ¦ 12:char/raw <- get *list, value:offset
421   ¦ 20:&:duplex-list:char/raw <- next list
422   ]
423   memory-should-contain [
424   ¦ 10 <- 13
425   ¦ 11 <- 14
426   ¦ 12 <- 18
427   ¦ 20 <- 0  # no more elements
428   ]
429 ]
430 
431 scenario remove-range-empty [
432   local-scope
433   # construct a duplex list with three elements [13, 14, 15]
434   list:&:duplex-list:char <- push 15, 0
435   list <- push 14, list
436   list <- push 13, list
437   run [
438   ¦ # delete between first and second element (i.e. nothing)
439   ¦ list2:&:duplex-list:char <- next list
440   ¦ remove-between list, list2
441   ¦ # now check the list
442   ¦ 10:char/raw <- get *list, value:offset
443   ¦ list <- next list
444   ¦ 11:char/raw <- get *list, value:offset
445   ¦ list <- next list
446   ¦ 12:char/raw <- get *list, value:offset
447   ¦ 20:&:duplex-list:char/raw <- next list
448   ]
449   # no change
450   memory-should-contain [
451   ¦ 10 <- 13
452   ¦ 11 <- 14
453   ¦ 12 <- 15
454   ¦ 20 <- 0
455   ]
456 ]
457 
458 scenario remove-range-to-end [
459   local-scope
460   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
461   list:&:duplex-list:char <- push 18, 0
462   list <- push 17, list
463   list <- push 16, list
464   list <- push 15, list
465   list <- push 14, list
466   list <- push 13, list
467   run [
468   ¦ # remove the third element and beyond
469   ¦ list2:&:duplex-list:char <- next list
470   ¦ remove-between list2, 0
471   ¦ # now check the list
472   ¦ 10:char/raw <- get *list, value:offset
473   ¦ list <- next list
474   ¦ 11:char/raw <- get *list, value:offset
475   ¦ 20:&:duplex-list:char/raw <- next list
476   ]
477   memory-should-contain [
478   ¦ 10 <- 13
479   ¦ 11 <- 14
480   ¦ 20 <- 0
481   ]
482 ]
483 
484 # insert list beginning at 'new' after 'in'
485 def insert-range in:&:duplex-list:_elem, start:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [
486   local-scope
487   load-ingredients
488   return-unless in
489   return-unless start
490   end:&:duplex-list:_elem <- copy start
491   {
492   ¦ next:&:duplex-list:_elem <- next end/insert-range
493   ¦ break-unless next
494   ¦ end <- copy next
495   ¦ loop
496   }
497   next:&:duplex-list:_elem <- next in
498   *end <- put *end, next:offset, next
499   {
500   ¦ break-unless next
501   ¦ *next <- put *next, prev:offset, end
502   }
503   *in <- put *in, next:offset, start
504   *start <- put *start, prev:offset, in
505 ]
506 
507 def append in:&:duplex-list:_elem, new:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [
508   local-scope
509   load-ingredients
510   last:&:duplex-list:_elem <- last in
511   *last <- put *last, next:offset, new
512   return-unless new
513   *new <- put *new, prev:offset, last
514 ]
515 
516 def last in:&:duplex-list:_elem -> result:&:duplex-list:_elem [
517   local-scope
518   load-ingredients
519   result <- copy in
520   {
521   ¦ next:&:duplex-list:_elem <- next result
522   ¦ break-unless next
523   ¦ result <- copy next
524   ¦ loop
525   }
526 ]
527 
528 # helper for debugging
529 def dump-from x:&:duplex-list:_elem [
530   local-scope
531   load-ingredients
532   $print x, [: ]
533   {
534   ¦ break-unless x
535   ¦ c:_elem <- get *x, value:offset
536   ¦ $print c, [ ]
537   ¦ x <- next x
538   ¦ {
539   ¦ ¦ is-newline?:bool <- equal c, 10/newline
540   ¦ ¦ break-unless is-newline?
541   ¦ ¦ $print 10/newline
542   ¦ ¦ $print x, [: ]
543   ¦ }
544   ¦ loop
545   }
546   $print 10/newline, [---], 10/newline
547 ]