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 def push x:_elem, in:&:duplex-list:_elem/contained-in:result -> result:&:duplex-list:_elem [
 10   local-scope
 11   load-inputs
 12   result:&:duplex-list:_elem <- new {(duplex-list _elem): type}
 13   *result <- merge x, in, 0
 14   return-unless in
 15   put *in, prev:offset, result
 16 ]
 17 
 18 def first in:&:duplex-list:_elem -> result:_elem [
 19   local-scope
 20   load-inputs
 21   return-unless in, 0
 22   result <- get *in, value:offset
 23 ]
 24 
 25 def next in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [
 26   local-scope
 27   load-inputs
 28   return-unless in, 0
 29   result <- get *in, next:offset
 30 ]
 31 
 32 def prev in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [
 33   local-scope
 34   load-inputs
 35   return-unless in, 0
 36   result <- get *in, prev:offset
 37   return result
 38 ]
 39 
 40 scenario duplex-list-handling [
 41   run [
 42     local-scope
 43     # reserve locations 0-9 to check for missing null check
 44     10:num/raw <- copy 34
 45     11:num/raw <- copy 35
 46     list:&:duplex-list:num <- push 3, 0
 47     list <- push 4, list
 48     list <- push 5, list
 49     list2:&:duplex-list:num <- copy list
 50     20:num/raw <- first list2
 51     list2 <- next list2
 52     21:num/raw <- first list2
 53     list2 <- next list2
 54     22:num/raw <- first list2
 55     30:&:duplex-list:num/raw <- next list2
 56     31:num/raw <- first 30:&:duplex-list:num/raw
 57     32:&:duplex-list:num/raw <- next 30:&:duplex-list:num/raw
 58     33:&:duplex-list:num/raw <- prev 30:&:duplex-list:num/raw
 59     list2 <- prev list2
 60     40:num/raw <- first list2
 61     list2 <- prev list2
 62     41:num/raw <- first list2
 63     50:bool/raw <- equal list, list2
 64   ]
 65   memory-should-contain [
 66     0 <- 0  # no modifications to null pointers
 67     10 <- 34
 68     11 <- 35
 69     20 <- 5  # scanning next
 70     21 <- 4
 71     22 <- 3
 72     30 <- 0  # null
 73     31 <- 0  # first of null
 74     32 <- 0  # next of null
 75     33 <- 0  # prev of null
 76     40 <- 4  # then start scanning prev
 77     41 <- 5
 78     50 <- 1  # list back at start
 79   ]
 80 ]
 81 
 82 def length l:&:duplex-list:_elem -> result:num [
 83   local-scope
 84   load-inputs
 85   result <- copy 0
 86   {
 87     break-unless l
 88     result <- add result, 1
 89     l <- next l
 90     loop
 91   }
 92 ]
 93 
 94 # insert 'x' after 'in'
 95 def insert x:_elem, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
 96   local-scope
 97   load-inputs
 98   new-node:&:duplex-list:_elem <- new {(duplex-list _elem): type}
 99   *new-node <- put *new-node, value:offset, x
100   # save old next before changing it
101   next-node:&:duplex-list:_elem <- get *in, next:offset
102   *in <- put *in, next:offset, new-node
103   *new-node <- put *new-node, prev:offset, in
104   *new-node <- put *new-node, next:offset, next-node
105   return-unless next-node
106   *next-node <- put *next-node, prev:offset, new-node
107 ]
108 
109 scenario inserting-into-duplex-list [
110   local-scope
111   list:&:duplex-list:num <- push 3, 0
112   list <- push 4, list
113   list <- push 5, list
114   run [
115     list2:&:duplex-list:num <- next list  # inside list
116     list2 <- insert 6, list2
117     # check structure like before
118     list2 <- copy list
119     10:num/raw <- first list2
120     list2 <- next list2
121     11:num/raw <- first list2
122     list2 <- next list2
123     12:num/raw <- first list2
124     list2 <- next list2
125     13:num/raw <- first list2
126     list2 <- prev list2
127     20:num/raw <- first list2
128     list2 <- prev list2
129     21:num/raw <- first list2
130     list2 <- prev list2
131     22:num/raw <- first list2
132     30:bool/raw <- equal list, list2
133   ]
134   memory-should-contain [
135     10 <- 5  # scanning next
136     11 <- 4
137     12 <- 6  # inserted element
138     13 <- 3
139     20 <- 6  # then prev
140     21 <- 4
141     22 <- 5
142     30 <- 1  # list back at start
143   ]
144 ]
145 
146 scenario inserting-at-end-of-duplex-list [
147   local-scope
148   list:&:duplex-list:num <- push 3, 0
149   list <- push 4, list
150   list <- push 5, list
151   run [
152     list2:&:duplex-list:num <- next list  # inside list
153     list2 <- next list2  # now at end of list
154     list2 <- insert 6, list2
155     # check structure like before
156     list2 <- copy list
157     10:num/raw <- first list2
158     list2 <- next list2
159     11:num/raw <- first list2
160     list2 <- next list2
161     12:num/raw <- first list2
162     list2 <- next list2
163     13:num/raw <- first list2
164     list2 <- prev list2
165     20:num/raw <- first list2
166     list2 <- prev list2
167     21:num/raw <- first list2
168     list2 <- prev list2
169     22:num/raw <- first list2
170     30:bool/raw <- equal list, list2
171   ]
172   memory-should-contain [
173     10 <- 5  # scanning next
174     11 <- 4
175     12 <- 3
176     13 <- 6  # inserted element
177     20 <- 3  # then prev
178     21 <- 4
179     22 <- 5
180     30 <- 1  # list back at start
181   ]
182 ]
183 
184 scenario inserting-after-start-of-duplex-list [
185   local-scope
186   list:&:duplex-list:num <- push 3, 0
187   list <- push 4, list
188   list <- push 5, list
189   run [
190     list <- insert 6, list
191     # check structure like before
192     list2:&:duplex-list:num <- copy list
193     10:num/raw <- first list2
194     list2 <- next list2
195     11:num/raw <- first list2
196     list2 <- next list2
197     12:num/raw <- first list2
198     list2 <- next list2
199     13:num/raw <- first list2
200     list2 <- prev list2
201     20:num/raw <- first list2
202     list2 <- prev list2
203     21:num/raw <- first list2
204     list2 <- prev list2
205     22:num/raw <- first list2
206     30:bool/raw <- equal list, list2
207   ]
208   memory-should-contain [
209     10 <- 5  # scanning next
210     11 <- 6  # inserted element
211     12 <- 4
212     13 <- 3
213     20 <- 4  # then prev
214     21 <- 6
215     22 <- 5
216     30 <- 1  # list back at start
217   ]
218 ]
219 
220 # remove 'x' from its surrounding list 'in'
221 #
222 # Returns null if and only if list is empty. Beware: in that case any other
223 # pointers to the head are now invalid.
224 def remove x:&:duplex-list:_elem/contained-in:in, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
225   local-scope
226   load-inputs
227   # if 'x' is null, return
228   return-unless x
229   next-node:&:duplex-list:_elem <- get *x, next:offset
230   prev-node:&:duplex-list:_elem <- get *x, prev:offset
231   # null x's pointers
232   *x <- put *x, next:offset, 0
233   *x <- put *x, prev:offset, 0
234   # if next-node is not null, set its prev pointer
235   {
236     break-unless next-node
237     *next-node <- put *next-node, prev:offset, prev-node
238   }
239   # if prev-node is not null, set its next pointer and return
240   {
241     break-unless prev-node
242     *prev-node <- put *prev-node, next:offset, next-node
243     return
244   }
245   # if prev-node is null, then we removed the head node at 'in'
246   # return the new head rather than the old 'in'
247   return next-node
248 ]
249 
250 scenario removing-from-duplex-list [
251   local-scope
252   list:&:duplex-list:num <- push 3, 0
253   list <- push 4, list
254   list <- push 5, list
255   run [
256     list2:&:duplex-list:num <- next list  # second element
257     list <- remove list2, list
258     10:bool/raw <- equal list2, 0
259     # check structure like before
260     list2 <- copy list
261     11:num/raw <- first list2
262     list2 <- next list2
263     12:num/raw <- first list2
264     20:&:duplex-list:num/raw <- next list2
265     list2 <- prev list2
266     30:num/raw <- first list2
267     40:bool/raw <- equal list, list2
268   ]
269   memory-should-contain [
270     10 <- 0  # remove returned non-null
271     11 <- 5  # scanning next, skipping deleted element
272     12 <- 3
273     20 <- 0  # no more elements
274     30 <- 5  # prev of final element
275     40 <- 1  # list back at start
276   ]
277 ]
278 
279 scenario removing-from-start-of-duplex-list [
280   local-scope
281   list:&:duplex-list:num <- push 3, 0
282   list <- push 4, list
283   list <- push 5, list
284   run [
285     list <- remove list, list
286     # check structure like before
287     list2:&:duplex-list:num <- copy list
288     10:num/raw <- first list2
289     list2 <- next list2
290     11:num/raw <- first list2
291     20:&:duplex-list:num/raw <- next list2
292     list2 <- prev list2
293     30:num/raw <- first list2
294     40:bool/raw <- equal list, list2
295   ]
296   memory-should-contain [
297     10 <- 4  # scanning next, skipping deleted element
298     11 <- 3
299     20 <- 0  # no more elements
300     30 <- 4  # prev of final element
301     40 <- 1  # list back at start
302   ]
303 ]
304 
305 scenario removing-from-end-of-duplex-list [
306   local-scope
307   list:&:duplex-list:num <- push 3, 0
308   list <- push 4, list
309   list <- push 5, list
310   run [
311     # delete last element
312     list2:&:duplex-list:num <- next list
313     list2 <- next list2
314     list <- remove list2, list
315     10:bool/raw <- equal list2, 0
316     # check structure like before
317     list2 <- copy list
318     11:num/raw <- first list2
319     list2 <- next list2
320     12:num/raw <- first list2
321     20:&:duplex-list:num/raw <- next list2
322     list2 <- prev list2
323     30:num/raw <- first list2
324     40:bool/raw <- equal list, list2
325   ]
326   memory-should-contain [
327     10 <- 0  # remove returned non-null
328     11 <- 5  # scanning next, skipping deleted element
329     12 <- 4
330     20 <- 0  # no more elements
331     30 <- 5  # prev of final element
332     40 <- 1  # list back at start
333   ]
334 ]
335 
336 scenario removing-from-singleton-duplex-list [
337   local-scope
338   list:&:duplex-list:num <- push 3, 0
339   run [
340     list <- remove list, list
341     1:num/raw <- copy list
342   ]
343   memory-should-contain [
344     1 <- 0  # back to an empty list
345   ]
346 ]
347 
348 def remove x:&:duplex-list:_elem/contained-in:in, n:num, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
349   local-scope
350   load-inputs
351   i:num <- copy 0
352   curr:&:duplex-list:_elem <- copy x
353   {
354     done?:bool <- greater-or-equal i, n
355     break-if done?
356     break-unless curr
357     next:&:duplex-list:_elem <- next curr
358     in <- remove curr, in
359     curr <- copy next
360     i <- add i, 1
361     loop
362   }
363 ]
364 
365 scenario removing-multiple-from-duplex-list [
366   local-scope
367   list:&:duplex-list:num <- push 3, 0
368   list <- push 4, list
369   list <- push 5, list
370   run [
371     list2:&:duplex-list:num <- next list  # second element
372     list <- remove list2, 2, list
373     stash list
374   ]
375   trace-should-contain [
376     app: 5
377   ]
378 ]
379 
380 # remove values between 'start' and 'end' (both exclusive).
381 # also clear pointers back out from start/end for hygiene.
382 # set end to 0 to delete everything past start.
383 # can't set start to 0 to delete everything before end, because there's no
384 # clean way to return the new head pointer.
385 def remove-between start:&:duplex-list:_elem, end:&:duplex-list:_elem/contained-in:start -> start:&:duplex-list:_elem [
386   local-scope
387   load-inputs
388   next:&:duplex-list:_elem <- get *start, next:offset
389   nothing-to-delete?:bool <- equal next, end
390   return-if nothing-to-delete?
391   assert next, [malformed duplex list]
392   # start->next->prev = 0
393   # start->next = end
394   *next <- put *next, prev:offset, 0
395   *start <- put *start, next:offset, end
396   return-unless end
397   # end->prev->next = 0
398   # end->prev = start
399   prev:&:duplex-list:_elem <- get *end, prev:offset
400   assert prev, [malformed duplex list - 2]
401   *prev <- put *prev, next:offset, 0
402   *end <- put *end, prev:offset, start
403 ]
404 
405 scenario remove-range [
406   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
407   local-scope
408   list:&:duplex-list:num <- push 18, 0
409   list <- push 17, list
410   list <- push 16, list
411   list <- push 15, list
412   list <- push 14, list
413   list <- push 13, list
414   run [
415     # delete 16 onwards
416     # first pointer: to the third element
417     list2:&:duplex-list:num <- next list
418     list2 <- next list2
419     list2 <- remove-between list2, 0
420     # now check the list
421     10:num/raw <- get *list, value:offset
422     list <- next list
423     11:num/raw <- get *list, value:offset
424     list <- next list
425     12:num/raw <- get *list, value:offset
426     20:&:duplex-list:num/raw <- next list
427   ]
428   memory-should-contain [
429     10 <- 13
430     11 <- 14
431     12 <- 15
432     20 <- 0
433   ]
434 ]
435 
436 scenario remove-range-to-final [
437   local-scope
438   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
439   list:&:duplex-list:num <- push 18, 0
440   list <- push 17, list
441   list <- push 16, list
442   list <- push 15, list
443   list <- push 14, list
444   list <- push 13, list
445   run [
446     # delete 15, 16 and 17
447     # start pointer: to the second element
448     list2:&:duplex-list:num <- next list
449     # end pointer: to the last (sixth) element
450     end:&:duplex-list:num <- next list2
451     end <- next end
452     end <- next end
453     end <- next end
454     remove-between list2, end
455     # now check the list
456     10:num/raw <- get *list, value:offset
457     list <- next list
458     11:num/raw <- get *list, value:offset
459     list <- next list
460     12:num/raw <- get *list, value:offset
461     20:&:duplex-list:num/raw <- next list
462   ]
463   memory-should-contain [
464     10 <- 13
465     11 <- 14
466     12 <- 18
467     20 <- 0  # no more elements
468   ]
469 ]
470 
471 scenario remove-range-empty [
472   local-scope
473   # construct a duplex list with three elements [13, 14, 15]
474   list:&:duplex-list:num <- push 15, 0
475   list <- push 14, list
476   list <- push 13, list
477   run [
478     # delete between first and second element (i.e. nothing)
479     list2:&:duplex-list:num <- next list
480     remove-between list, list2
481     # now check the list
482     10:num/raw <- get *list, value:offset
483     list <- next list
484     11:num/raw <- get *list, value:offset
485     list <- next list
486     12:num/raw <- get *list, value:offset
487     20:&:duplex-list:num/raw <- next list
488   ]
489   # no change
490   memory-should-contain [
491     10 <- 13
492     11 <- 14
493     12 <- 15
494     20 <- 0
495   ]
496 ]
497 
498 scenario remove-range-to-end [
499   local-scope
500   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
501   list:&:duplex-list:num <- push 18, 0
502   list <- push 17, list
503   list <- push 16, list
504   list <- push 15, list
505   list <- push 14, list
506   list <- push 13, list
507   run [
508     # remove the third element and beyond
509     list2:&:duplex-list:num <- next list
510     remove-between list2, 0
511     # now check the list
512     10:num/raw <- get *list, value:offset
513     list <- next list
514     11:num/raw <- get *list, value:offset
515     20:&:duplex-list:num/raw <- next list
516   ]
517   memory-should-contain [
518     10 <- 13
519     11 <- 14
520     20 <- 0
521   ]
522 ]
523 
524 # insert list beginning at 'start' after 'in'
525 def splice in:&:duplex-list:_elem, start:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [
526   local-scope
527   load-inputs
528   return-unless in
529   return-unless start
530   end:&:duplex-list:_elem <- last start
531   next:&:duplex-list:_elem <- next in
532   {
533     break-unless next
534     *end <- put *end, next:offset, next
535     *next <- put *next, prev:offset, end
536   }
537   *in <- put *in, next:offset, start
538   *start <- put *start, prev:offset, in
539 ]
540 
541 # insert contents of 'new' after 'in'
542 def insert in:&:duplex-list:_elem, new:&:@:_elem -> in:&:duplex-list:_elem [
543   local-scope
544   load-inputs
545   return-unless in
546   return-unless new
547   len:num <- length *new
548   return-unless len
549   curr:&:duplex-list:_elem <- copy in
550   idx:num <- copy 0
551   {
552     done?:bool <- greater-or-equal idx, len
553     break-if done?
554     c:_elem <- index *new, idx
555     insert c, curr
556     # next iter
557     curr <- next curr
558     idx <- add idx, 1
559     loop
560   }
561 ]
562 
563 def append in:&:duplex-list:_elem, new:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [
564   local-scope
565   load-inputs
566   last:&:duplex-list:_elem <- last in
567   *last <- put *last, next:offset, new
568   return-unless new
569   *new <- put *new, prev:offset, last
570 ]
571 
572 def last in:&:duplex-list:_elem -> result:&:duplex-list:_elem [
573   local-scope
574   load-inputs
575   result <- copy in
576   {
577     next:&:duplex-list:_elem <- next result
578     break-unless next
579     result <- copy next
580     loop
581   }
582 ]
583 
584 # does a duplex list start with a certain sequence of elements?
585 def match x:&:duplex-list:_elem, y:&:@:_elem -> result:bool [
586   local-scope
587   load-inputs
588   i:num <- copy 0
589   max:num <- length *y
590   {
591     done?:bool <- greater-or-equal i, max
592     break-if done?
593     expected:_elem <- index *y, i
594     return-unless x, 0/no-match
595     curr:_elem <- first x
596     curr-matches?:bool <- equal curr, expected
597     return-unless curr-matches?, 0/no-match
598     x <- next x
599     i <- add i, 1
600     loop
601   }
602   return 1/successful-match
603 ]
604 
605 scenario duplex-list-match [
606   local-scope
607   list:&:duplex-list:char <- push 97/a, 0
608   list <- push 98/b, list
609   list <- push 99/c, list
610   list <- push 100/d, list
611   run [
612     10:bool/raw <- match list, []
613     11:bool/raw <- match list, [d]
614     12:bool/raw <- match list, [dc]
615     13:bool/raw <- match list, [dcba]
616     14:bool/raw <- match list, [dd]
617     15:bool/raw <- match list, [dcbax]
618   ]
619   memory-should-contain [
620     10 <- 1  # matches []
621     11 <- 1  # matches [d]
622     12 <- 1  # matches [dc]
623     13 <- 1  # matches [dcba]
624     14 <- 0  # does not match [dd]
625     15 <- 0  # does not match [dcbax]
626   ]
627 ]
628 
629 # helper for debugging
630 def dump-from x:&:duplex-list:_elem [
631   local-scope
632   load-inputs
633   $print x, [: ]
634   {
635     break-unless x
636     c:_elem <- get *x, value:offset
637     $print c, [ ]
638     x <- next x
639     {
640       is-newline?:bool <- equal c, 10/newline
641       break-unless is-newline?
642       $print 10/newline
643       $print x, [: ]
644     }
645     loop
646   }
647   $print 10/newline, [---], 10/newline
648 ]
649 
650 scenario stash-duplex-list [
651   local-scope
652   list:&:duplex-list:num <- push 1, 0
653   list <- push 2, list
654   list <- push 3, list
655   run [
656     stash [list:], list
657   ]
658   trace-should-contain [
659     app: list: 3 <-> 2 <-> 1
660   ]
661 ]
662 
663 def to-text in:&:duplex-list:_elem -> result:text [
664   local-scope
665   load-inputs
666   buf:&:buffer:char <- new-buffer 80
667   buf <- to-buffer in, buf
668   result <- buffer-to-array buf
669 ]
670 
671 # variant of 'to-text' which stops printing after a few elements (and so is robust to cycles)
672 def to-text-line in:&:duplex-list:_elem -> result:text [
673   local-scope
674   load-inputs
675   buf:&:buffer:char <- new-buffer 80
676   buf <- to-buffer in, buf, 6  # max elements to display
677   result <- buffer-to-array buf
678 ]
679 
680 def to-buffer in:&:duplex-list:_elem, buf:&:buffer:char -> buf:&:buffer:char [
681   local-scope
682   load-inputs
683   {
684     break-if in
685     buf <- append buf, [[]]
686     return
687   }
688   # append in.value to buf
689   val:_elem <- get *in, value:offset
690   buf <- append buf, val
691   # now prepare next
692   next:&:duplex-list:_elem <- next in
693   nextn:num <- copy next
694   return-unless next
695   buf <- append buf, [ <-> ]
696   # and recurse
697   remaining:num, optional-input-found?:bool <- next-input
698   {
699     break-if optional-input-found?
700     # unlimited recursion
701     buf <- to-buffer next, buf
702     return
703   }
704   {
705     break-unless remaining
706     # limited recursion
707     remaining <- subtract remaining, 1
708     buf <- to-buffer next, buf, remaining
709     return
710   }
711   # past recursion depth; insert ellipses and stop
712   append buf, [...]
713 ]
714 
715 scenario stash-empty-duplex-list [
716   local-scope
717   x:&:duplex-list:num <- copy 0
718   run [
719     stash x
720   ]
721   trace-should-contain [
722     app: []
723   ]
724 ]