From 204dae921abff0c70e017215bb3c91fa6ca11aff Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Mon, 26 Dec 2016 11:44:14 -0800 Subject: 3710 Turns out we don't need to explicitly add anchors for each line. Vim's TOhtml has magic for that out of the box. --- html/065duplex_list.mu.html | 1094 +++++++++++++++++++++---------------------- 1 file changed, 547 insertions(+), 547 deletions(-) (limited to 'html/065duplex_list.mu.html') diff --git a/html/065duplex_list.mu.html b/html/065duplex_list.mu.html index d21807e2..cfd81f35 100644 --- a/html/065duplex_list.mu.html +++ b/html/065duplex_list.mu.html @@ -56,553 +56,553 @@ if ('onhashchange' in window) { 
-  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 ]
+  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 ]
-- cgit 1.4.1-2-gfad0