# A doubly linked list permits bidirectional traversal. container duplex-list:_elem [ value:_elem next:&:duplex-list:_elem prev:&:duplex-list:_elem ] # should I say in/contained-in:result, allow ingredients to refer to products? def push x:_elem, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [ local-scope load-ingredients result:&:duplex-list:_elem <- new {(duplex-list _elem): type} *result <- merge x, in, 0 { break-unless in *in <- put *in, prev:offset, result } return result # needed explicitly because we need to replace 'in' with 'result' ] def first in:&:duplex-list:_elem -> result:_elem [ local-scope load-ingredients return-unless in, 0 result <- get *in, value:offset ] def next in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [ local-scope load-ingredients return-unless in, 0 result <- get *in, next:offset ] def prev in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [ local-scope load-ingredients return-unless in, 0 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:char <- push 3, 0 list <- push 4, list list <- push 5, list list2:&:duplex-list:char <- copy list 20:char/raw <- first list2 list2 <- next list2 21:char/raw <- first list2 list2 <- next list2 22:char/raw <- first list2 30:&:duplex-list:char/raw <- next list2 31:char/raw <- first 30:&:duplex-list:char/raw 32:&:duplex-list:char/raw <- next 30:&:duplex-list:char/raw 33:&:duplex-list:char/raw <- prev 30:&:duplex-list:char/raw list2 <- prev list2 40:char/raw <- first list2 list2 <- prev list2 41:char/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-ingredients 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-ingredients 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:char <- push 3, 0 list <- push 4, list list <- push 5, list run [ list2:&:duplex-list:char <- next list # inside list list2 <- insert 6, list2 # check structure like before list2 <- copy list 10:char/raw <- first list2 list2 <- next list2 11:char/raw <- first list2 list2 <- next list2 12:char/raw <- first list2 list2 <- next list2 13:char/raw <- first list2 list2 <- prev list2 20:char/raw <- first list2 list2 <- prev list2 21:char/raw <- first list2 list2 <- prev list2 22:char/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:char <- push 3, 0 list <- push 4, list list <- push 5, list run [ list2:&:duplex-list:char <- next list # inside list list2 <- next list2 # now at end of list list2 <- insert 6, list2 # check structure like before list2 <- copy list 10:char/raw <- first list2 list2 <- next list2 11:char/raw <- first list2 list2 <- next list2 12:char/raw <- first list2 list2 <- next list2 13:char/raw <- first list2 list2 <- prev list2 20:char/raw <- first list2 list2 <- prev list2 21:char/raw <- first list2 list2 <- prev list2 22:char/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:char <- push 3, 0 list <- push 4, list list <- push 5, list run [ list <- insert 6, list # check structure like before list2:&:duplex-list:char <- copy list 10:char/raw <- first list2 list2 <- next list2 11:char/raw <- first list2 list2 <- next list2 12:char/raw <- first list2 list2 <- next list2 13:char/raw <- first list2 list2 <- prev list2 20:char/raw <- first list2 list2 <- prev list2 21:char/raw <- first list2 list2 <- prev list2 22:char/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-ingredients # 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, 0 *x <- put *x, prev:offset, 0 # 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:char <- push 3, 0 list <- push 4, list list <- push 5, list run [ list2:&:duplex-list:char <- next list # second element list <- remove list2, list 10:bool/raw <- equal list2, 0 # check structure like before list2 <- copy list 11:char/raw <- first list2 list2 <- next list2 12:char/raw <- first list2 20:&:duplex-list:char/raw <- next list2 list2 <- prev list2 30:char/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:char <- push 3, 0 list <- push 4, list list <- push 5, list run [ list <- remove list, list # check structure like before list2:&:duplex-list:char <- copy list 10:char/raw <- first list2 list2 <- next list2 11:char/raw <- first list2 20:&:duplex-list:char/raw <- next list2 list2 <- prev list2 30:char/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:char <- push 3, 0 list <- push 4, list list <- push 5, list run [ # delete last element list2:&:duplex-list:char <- next list list2 <- next list2 list <- remove list2, list 10:bool/raw <- equal list2, 0 # check structure like before list2 <- copy list 11:char/raw <- first list2 list2 <- next list2 12:char/raw <- first list2 20:&:duplex-list:char/raw <- next list2 list2 <- prev list2 30:char/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:char <- push 3, 0 run [ list <- remove list, list 1:num/raw <- copy list ] memory-should-contain [ 1 <- 0 # back to an empty list ] ] # 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-ingredients 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, 0 *start <- put *start, next:offset, end return-unless end # 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, 0 *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:char <- push 18, 0 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:char <- next list list2 <- next list2 list2 <- remove-between list2, 0 # now check the list 10:char/raw <- get *list, value:offset list <- next list 11:char/raw <- get *list, value:offset list <- next list 12:char/raw <- get *list, value:offset 20:&:duplex-list:char/raw <- next list ] memory-should-contain [ 10 <- 13 11 <- 14 12 <- 15 20 <- 0 ] ] scenario remove-range-to-final [ local-scope # construct a duplex list with six elements [13, 14, 15, 16, 17, 18] list:&:duplex-list:char <- push 18, 0 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:char <- next list # end pointer: to the last (sixth) element end:&:duplex-list:char <- next list2 end <- next end end <- next end end <- next end remove-between list2, end # now check the list 10:char/raw <- get *list, value:offset list <- next list 11:char/raw <- get *list, value:offset list <- next list 12:char/raw <- get *list, value:offset 20:&:duplex-list:char/raw <- next list ] memory-should-contain [ 10 <- 13 11 <- 14 12 <- 18 20 <- 0 # no more elements ] ] scenario remove-range-empty [ local-scope # construct a duplex list with three elements [13, 14, 15] list:&:duplex-list:char <- push 15, 0 list <- push 14, list list <- push 13, list run [ # delete between first and second element (i.e. nothing) list2:&:duplex-list:char <- next list remove-between list, list2 # now check the list 10:char/raw <- get *list, value:offset list <- next list 11:char/raw <- get *list, value:offset list <- next list 12:char/raw <- get *list, value:offset 20:&:duplex-list:char/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:char <- push 18, 0 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:char <- next list remove-between list2, 0 # now check the list 10:char/raw <- get *list, value:offset list <- next list 11:char/raw <- get *list, value:offset 20:&:duplex-list:char/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-ingredients 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 ] def append in:&:duplex-list:_elem, new:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [ local-scope load-ingredients 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-ingredients result <- copy in { next:&:duplex-list:_elem <- next result break-unless next result <- copy next loop } ] # helper for debugging def dump-from x:&:duplex-list:_elem [ local-scope load-ingredients $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 ]