diff options
Diffstat (limited to 'archive/1.vm/065duplex_list.mu')
| -rw-r--r-- | archive/1.vm/065duplex_list.mu | 781 |
1 files changed, 781 insertions, 0 deletions
diff --git a/archive/1.vm/065duplex_list.mu b/archive/1.vm/065duplex_list.mu new file mode 100644 index 00000000..3a7de8f6 --- /dev/null +++ b/archive/1.vm/065duplex_list.mu @@ -0,0 +1,781 @@ +# A doubly linked list permits bidirectional traversal. + +container duplex-list:_elem [ + value:_elem + next:&:duplex-list:_elem + prev:&:duplex-list:_elem +] + +def push x:_elem, in:&:duplex-list:_elem/contained-in:result -> result:&:duplex-list:_elem [ + local-scope + load-inputs + result:&:duplex-list:_elem <- new {(duplex-list _elem): type} + *result <- merge x, in, null + return-unless in + put *in, prev:offset, result +] + +def first in:&:duplex-list:_elem -> result:_elem [ + local-scope + load-inputs + { + break-if in + zero:&:_elem <- new _elem:type + zero-result:_elem <- copy *zero + abandon zero + return zero-result + } + result <- get *in, value:offset +] + +def next in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [ + local-scope + load-inputs + return-unless in, null + result <- get *in, next:offset +] + +def prev in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [ + local-scope + load-inputs + return-unless in, null + result <- get *in, prev:offset + return result +] + +scenario duplex-list-handling [ + run [ + local-scope + # reserve locations 0-9 to check for missing null check + 10:num/raw <- copy 34 + 11:num/raw <- copy 35 + list:&:duplex-list:num <- push 3, null + list <- push 4, list + list <- push 5, list + list2:&:duplex-list:num <- copy list + 20:num/raw <- first list2 + list2 <- next list2 + 21:num/raw <- first list2 + list2 <- next list2 + 22:num/raw <- first list2 + 30:&:duplex-list:num/raw <- next list2 + 31:num/raw <- first 30:&:duplex-list:num/raw + 32:&:duplex-list:num/raw <- next 30:&:duplex-list:num/raw + 33:&:duplex-list:num/raw <- prev 30:&:duplex-list:num/raw + list2 <- prev list2 + 40:num/raw <- first list2 + list2 <- prev list2 + 41:num/raw <- first list2 + 50:bool/raw <- equal list, list2 + ] + memory-should-contain [ + 0 <- 0 # no modifications to null pointers + 10 <- 34 + 11 <- 35 + 20 <- 5 # scanning next + 21 <- 4 + 22 <- 3 + 30 <- 0 # null + 31 <- 0 # first of null + 32 <- 0 # next of null + 33 <- 0 # prev of null + 40 <- 4 # then start scanning prev + 41 <- 5 + 50 <- 1 # list back at start + ] +] + +def length l:&:duplex-list:_elem -> result:num [ + local-scope + load-inputs + result <- copy 0 + { + break-unless l + result <- add result, 1 + l <- next l + loop + } +] + +# insert 'x' after 'in' +def insert x:_elem, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [ + local-scope + load-inputs + new-node:&:duplex-list:_elem <- new {(duplex-list _elem): type} + *new-node <- put *new-node, value:offset, x + # save old next before changing it + next-node:&:duplex-list:_elem <- get *in, next:offset + *in <- put *in, next:offset, new-node + *new-node <- put *new-node, prev:offset, in + *new-node <- put *new-node, next:offset, next-node + return-unless next-node + *next-node <- put *next-node, prev:offset, new-node +] + +scenario inserting-into-duplex-list [ + local-scope + list:&:duplex-list:num <- push 3, null + list <- push 4, list + list <- push 5, list + run [ + list2:&:duplex-list:num <- next list # inside list + list2 <- insert 6, list2 + # check structure like before + list2 <- copy list + 10:num/raw <- first list2 + list2 <- next list2 + 11:num/raw <- first list2 + list2 <- next list2 + 12:num/raw <- first list2 + list2 <- next list2 + 13:num/raw <- first list2 + list2 <- prev list2 + 20:num/raw <- first list2 + list2 <- prev list2 + 21:num/raw <- first list2 + list2 <- prev list2 + 22:num/raw <- first list2 + 30:bool/raw <- equal list, list2 + ] + memory-should-contain [ + 10 <- 5 # scanning next + 11 <- 4 + 12 <- 6 # inserted element + 13 <- 3 + 20 <- 6 # then prev + 21 <- 4 + 22 <- 5 + 30 <- 1 # list back at start + ] +] + +scenario inserting-at-end-of-duplex-list [ + local-scope + list:&:duplex-list:num <- push 3, null + list <- push 4, list + list <- push 5, list + run [ + list2:&:duplex-list:num <- next list # inside list + list2 <- next list2 # now at end of list + list2 <- insert 6, list2 + # check structure like before + list2 <- copy list + 10:num/raw <- first list2 + list2 <- next list2 + 11:num/raw <- first list2 + list2 <- next list2 + 12:num/raw <- first list2 + list2 <- next list2 + 13:num/raw <- first list2 + list2 <- prev list2 + 20:num/raw <- first list2 + list2 <- prev list2 + 21:num/raw <- first list2 + list2 <- prev list2 + 22:num/raw <- first list2 + 30:bool/raw <- equal list, list2 + ] + memory-should-contain [ + 10 <- 5 # scanning next + 11 <- 4 + 12 <- 3 + 13 <- 6 # inserted element + 20 <- 3 # then prev + 21 <- 4 + 22 <- 5 + 30 <- 1 # list back at start + ] +] + +scenario inserting-after-start-of-duplex-list [ + local-scope + list:&:duplex-list:num <- push 3, null + list <- push 4, list + list <- push 5, list + run [ + list <- insert 6, list + # check structure like before + list2:&:duplex-list:num <- copy list + 10:num/raw <- first list2 + list2 <- next list2 + 11:num/raw <- first list2 + list2 <- next list2 + 12:num/raw <- first list2 + list2 <- next list2 + 13:num/raw <- first list2 + list2 <- prev list2 + 20:num/raw <- first list2 + list2 <- prev list2 + 21:num/raw <- first list2 + list2 <- prev list2 + 22:num/raw <- first list2 + 30:bool/raw <- equal list, list2 + ] + memory-should-contain [ + 10 <- 5 # scanning next + 11 <- 6 # inserted element + 12 <- 4 + 13 <- 3 + 20 <- 4 # then prev + 21 <- 6 + 22 <- 5 + 30 <- 1 # list back at start + ] +] + +# remove 'x' from its surrounding list 'in' +# +# Returns null if and only if list is empty. Beware: in that case any other +# pointers to the head are now invalid. +def remove x:&:duplex-list:_elem/contained-in:in, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [ + local-scope + load-inputs + # if 'x' is null, return + return-unless x + next-node:&:duplex-list:_elem <- get *x, next:offset + prev-node:&:duplex-list:_elem <- get *x, prev:offset + # null x's pointers + *x <- put *x, next:offset, null + *x <- put *x, prev:offset, null + # if next-node is not null, set its prev pointer + { + break-unless next-node + *next-node <- put *next-node, prev:offset, prev-node + } + # if prev-node is not null, set its next pointer and return + { + break-unless prev-node + *prev-node <- put *prev-node, next:offset, next-node + return + } + # if prev-node is null, then we removed the head node at 'in' + # return the new head rather than the old 'in' + return next-node +] + +scenario removing-from-duplex-list [ + local-scope + list:&:duplex-list:num <- push 3, null + list <- push 4, list + list <- push 5, list + run [ + list2:&:duplex-list:num <- next list # second element + list <- remove list2, list + 10:bool/raw <- equal list2, null + # check structure like before + list2 <- copy list + 11:num/raw <- first list2 + list2 <- next list2 + 12:num/raw <- first list2 + 20:&:duplex-list:num/raw <- next list2 + list2 <- prev list2 + 30:num/raw <- first list2 + 40:bool/raw <- equal list, list2 + ] + memory-should-contain [ + 10 <- 0 # remove returned non-null + 11 <- 5 # scanning next, skipping deleted element + 12 <- 3 + 20 <- 0 # no more elements + 30 <- 5 # prev of final element + 40 <- 1 # list back at start + ] +] + +scenario removing-from-start-of-duplex-list [ + local-scope + list:&:duplex-list:num <- push 3, null + list <- push 4, list + list <- push 5, list + run [ + list <- remove list, list + # check structure like before + list2:&:duplex-list:num <- copy list + 10:num/raw <- first list2 + list2 <- next list2 + 11:num/raw <- first list2 + 20:&:duplex-list:num/raw <- next list2 + list2 <- prev list2 + 30:num/raw <- first list2 + 40:bool/raw <- equal list, list2 + ] + memory-should-contain [ + 10 <- 4 # scanning next, skipping deleted element + 11 <- 3 + 20 <- 0 # no more elements + 30 <- 4 # prev of final element + 40 <- 1 # list back at start + ] +] + +scenario removing-from-end-of-duplex-list [ + local-scope + list:&:duplex-list:num <- push 3, null + list <- push 4, list + list <- push 5, list + run [ + # delete last element + list2:&:duplex-list:num <- next list + list2 <- next list2 + list <- remove list2, list + 10:bool/raw <- equal list2, null + # check structure like before + list2 <- copy list + 11:num/raw <- first list2 + list2 <- next list2 + 12:num/raw <- first list2 + 20:&:duplex-list:num/raw <- next list2 + list2 <- prev list2 + 30:num/raw <- first list2 + 40:bool/raw <- equal list, list2 + ] + memory-should-contain [ + 10 <- 0 # remove returned non-null + 11 <- 5 # scanning next, skipping deleted element + 12 <- 4 + 20 <- 0 # no more elements + 30 <- 5 # prev of final element + 40 <- 1 # list back at start + ] +] + +scenario removing-from-singleton-duplex-list [ + local-scope + list:&:duplex-list:num <- push 3, null + run [ + list <- remove list, list + 1:num/raw <- deaddress list + ] + memory-should-contain [ + 1 <- 0 # back to an empty list + ] +] + +def remove x:&:duplex-list:_elem/contained-in:in, n:num, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [ + local-scope + load-inputs + i:num <- copy 0 + curr:&:duplex-list:_elem <- copy x + { + done?:bool <- greater-or-equal i, n + break-if done? + break-unless curr + next:&:duplex-list:_elem <- next curr + in <- remove curr, in + curr <- copy next + i <- add i, 1 + loop + } +] + +scenario removing-multiple-from-duplex-list [ + local-scope + list:&:duplex-list:num <- push 3, null + list <- push 4, list + list <- push 5, list + run [ + list2:&:duplex-list:num <- next list # second element + list <- remove list2, 2, list + stash list + ] + trace-should-contain [ + app: 5 + ] +] + +# remove values between 'start' and 'end' (both exclusive). +# also clear pointers back out from start/end for hygiene. +# set end to 0 to delete everything past start. +# can't set start to 0 to delete everything before end, because there's no +# clean way to return the new head pointer. +def remove-between start:&:duplex-list:_elem, end:&:duplex-list:_elem/contained-in:start -> start:&:duplex-list:_elem [ + local-scope + load-inputs + next:&:duplex-list:_elem <- get *start, next:offset + nothing-to-delete?:bool <- equal next, end + return-if nothing-to-delete? + assert next, [malformed duplex list] + # start->next->prev = 0 + # start->next = end + *next <- put *next, prev:offset, null + *start <- put *start, next:offset, end + { + break-if end + stash [spliced:] next + return + } + # end->prev->next = 0 + # end->prev = start + prev:&:duplex-list:_elem <- get *end, prev:offset + assert prev, [malformed duplex list - 2] + *prev <- put *prev, next:offset, null + stash [spliced:] next + *end <- put *end, prev:offset, start +] + +scenario remove-range [ + # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] + local-scope + list:&:duplex-list:num <- push 18, null + list <- push 17, list + list <- push 16, list + list <- push 15, list + list <- push 14, list + list <- push 13, list + run [ + # delete 16 onwards + # first pointer: to the third element + list2:&:duplex-list:num <- next list + list2 <- next list2 + list2 <- remove-between list2, null + # now check the list + 10:num/raw <- get *list, value:offset + list <- next list + 11:num/raw <- get *list, value:offset + list <- next list + 12:num/raw <- get *list, value:offset + 20:&:duplex-list:num/raw <- next list + ] + memory-should-contain [ + 10 <- 13 + 11 <- 14 + 12 <- 15 + 20 <- 0 + ] + trace-should-contain [ + app: spliced: 16 <-> 17 <-> 18 + ] +] + +scenario remove-range-to-final [ + local-scope + # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] + list:&:duplex-list:num <- push 18, null + list <- push 17, list + list <- push 16, list + list <- push 15, list + list <- push 14, list + list <- push 13, list + run [ + # delete 15, 16 and 17 + # start pointer: to the second element + list2:&:duplex-list:num <- next list + # end pointer: to the last (sixth) element + end:&:duplex-list:num <- next list2 + end <- next end + end <- next end + end <- next end + remove-between list2, end + # now check the list + 10:num/raw <- get *list, value:offset + list <- next list + 11:num/raw <- get *list, value:offset + list <- next list + 12:num/raw <- get *list, value:offset + 20:&:duplex-list:num/raw <- next list + ] + memory-should-contain [ + 10 <- 13 + 11 <- 14 + 12 <- 18 + 20 <- 0 # no more elements + ] + trace-should-contain [ + app: spliced: 15 <-> 16 <-> 17 + ] +] + +scenario remove-range-to-penultimate [ + local-scope + # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] + list:&:duplex-list:num <- push 18, null + list <- push 17, list + list <- push 16, list + list <- push 15, list + list <- push 14, list + list <- push 13, list + run [ + # delete 15 and 16 + # start pointer: to the second element + list2:&:duplex-list:num <- next list + # end pointer: to the last (sixth) element + end:&:duplex-list:num <- next list2 + end <- next end + end <- next end + remove-between list2, end + # now check the list + 10:num/raw <- get *list, value:offset + list <- next list + 11:num/raw <- get *list, value:offset + list <- next list + 12:num/raw <- get *list, value:offset + list <- next list + 13:num/raw <- get *list, value:offset + 20:&:duplex-list:num/raw <- next list + ] + memory-should-contain [ + 10 <- 13 + 11 <- 14 + 12 <- 17 + 13 <- 18 + 20 <- 0 # no more elements + ] + trace-should-contain [ + app: spliced: 15 <-> 16 + ] +] + +scenario remove-range-empty [ + local-scope + # construct a duplex list with three elements [13, 14, 15] + list:&:duplex-list:num <- push 15, null + list <- push 14, list + list <- push 13, list + run [ + # delete between first and second element (i.e. nothing) + list2:&:duplex-list:num <- next list + remove-between list, list2 + # now check the list + 10:num/raw <- get *list, value:offset + list <- next list + 11:num/raw <- get *list, value:offset + list <- next list + 12:num/raw <- get *list, value:offset + 20:&:duplex-list:num/raw <- next list + ] + # no change + memory-should-contain [ + 10 <- 13 + 11 <- 14 + 12 <- 15 + 20 <- 0 + ] +] + +scenario remove-range-to-end [ + local-scope + # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] + list:&:duplex-list:num <- push 18, null + list <- push 17, list + list <- push 16, list + list <- push 15, list + list <- push 14, list + list <- push 13, list + run [ + # remove the third element and beyond + list2:&:duplex-list:num <- next list + remove-between list2, null + # now check the list + 10:num/raw <- get *list, value:offset + list <- next list + 11:num/raw <- get *list, value:offset + 20:&:duplex-list:num/raw <- next list + ] + memory-should-contain [ + 10 <- 13 + 11 <- 14 + 20 <- 0 + ] +] + +# insert list beginning at 'start' after 'in' +def splice in:&:duplex-list:_elem, start:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [ + local-scope + load-inputs + return-unless in + return-unless start + end:&:duplex-list:_elem <- last start + next:&:duplex-list:_elem <- next in + { + break-unless next + *end <- put *end, next:offset, next + *next <- put *next, prev:offset, end + } + *in <- put *in, next:offset, start + *start <- put *start, prev:offset, in +] + +# insert contents of 'new' after 'in' +def insert in:&:duplex-list:_elem, new:&:@:_elem -> in:&:duplex-list:_elem [ + local-scope + load-inputs + return-unless in + return-unless new + len:num <- length *new + return-unless len + curr:&:duplex-list:_elem <- copy in + idx:num <- copy 0 + { + done?:bool <- greater-or-equal idx, len + break-if done? + c:_elem <- index *new, idx + insert c, curr + # next iter + curr <- next curr + idx <- add idx, 1 + loop + } +] + +def append in:&:duplex-list:_elem, new:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [ + local-scope + load-inputs + last:&:duplex-list:_elem <- last in + *last <- put *last, next:offset, new + return-unless new + *new <- put *new, prev:offset, last +] + +def last in:&:duplex-list:_elem -> result:&:duplex-list:_elem [ + local-scope + load-inputs + result <- copy in + { + next:&:duplex-list:_elem <- next result + break-unless next + result <- copy next + loop + } +] + +# does a duplex list start with a certain sequence of elements? +def match x:&:duplex-list:_elem, y:&:@:_elem -> result:bool [ + local-scope + load-inputs + i:num <- copy 0 + max:num <- length *y + { + done?:bool <- greater-or-equal i, max + break-if done? + expected:_elem <- index *y, i + return-unless x, false/no-match + curr:_elem <- first x + curr-matches?:bool <- equal curr, expected + return-unless curr-matches?, false/no-match + x <- next x + i <- add i, 1 + loop + } + return true/successful-match +] + +scenario duplex-list-match [ + local-scope + list:&:duplex-list:char <- push 97/a, null + list <- push 98/b, list + list <- push 99/c, list + list <- push 100/d, list + run [ + 10:bool/raw <- match list, [] + 11:bool/raw <- match list, [d] + 12:bool/raw <- match list, [dc] + 13:bool/raw <- match list, [dcba] + 14:bool/raw <- match list, [dd] + 15:bool/raw <- match list, [dcbax] + ] + memory-should-contain [ + 10 <- 1 # matches [] + 11 <- 1 # matches [d] + 12 <- 1 # matches [dc] + 13 <- 1 # matches [dcba] + 14 <- 0 # does not match [dd] + 15 <- 0 # does not match [dcbax] + ] +] + +# helper for debugging +def dump-from x:&:duplex-list:_elem [ + local-scope + load-inputs + $print x, [: ] + { + break-unless x + c:_elem <- get *x, value:offset + $print c, [ ] + x <- next x + { + is-newline?:bool <- equal c, 10/newline + break-unless is-newline? + $print 10/newline + $print x, [: ] + } + loop + } + $print 10/newline, [---], 10/newline +] + +scenario stash-duplex-list [ + local-scope + list:&:duplex-list:num <- push 1, null + list <- push 2, list + list <- push 3, list + run [ + stash [list:], list + ] + trace-should-contain [ + app: list: 3 <-> 2 <-> 1 + ] +] + +def to-text in:&:duplex-list:_elem -> result:text [ + local-scope + load-inputs + buf:&:buffer:char <- new-buffer 80 + buf <- to-buffer in, buf + result <- buffer-to-array buf +] + +# variant of 'to-text' which stops printing after a few elements (and so is robust to cycles) +def to-text-line in:&:duplex-list:_elem -> result:text [ + local-scope + load-inputs + buf:&:buffer:char <- new-buffer 80 + buf <- to-buffer in, buf, 6 # max elements to display + result <- buffer-to-array buf +] + +def to-buffer in:&:duplex-list:_elem, buf:&:buffer:char -> buf:&:buffer:char [ + local-scope + load-inputs + { + break-if in + buf <- append buf, [[]] + return + } + # append in.value to buf + val:_elem <- get *in, value:offset + buf <- append buf, val + # now prepare next + next:&:duplex-list:_elem <- next in + nextn:num <- deaddress next + return-unless next + buf <- append buf, [ <-> ] + # and recurse + remaining:num, optional-input-found?:bool <- next-input + { + break-if optional-input-found? + # unlimited recursion + buf <- to-buffer next, buf + return + } + { + break-unless remaining + # limited recursion + remaining <- subtract remaining, 1 + buf <- to-buffer next, buf, remaining + return + } + # past recursion depth; insert ellipses and stop + append buf, [...] +] + +scenario stash-empty-duplex-list [ + local-scope + x:&:duplex-list:num <- copy null + run [ + stash x + ] + trace-should-contain [ + app: [] + ] +] |