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