From c842d90bbc5ab8f4fb88fb89ebb02c0c12051396 Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Wed, 27 Jul 2016 22:51:11 -0700 Subject: 3158 --- html/065duplex_list.mu.html | 597 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 597 insertions(+) create mode 100644 html/065duplex_list.mu.html (limited to 'html/065duplex_list.mu.html') diff --git a/html/065duplex_list.mu.html b/html/065duplex_list.mu.html new file mode 100644 index 00000000..8dad9fc4 --- /dev/null +++ b/html/065duplex_list.mu.html @@ -0,0 +1,597 @@ + + + + +Mu - 065duplex_list.mu + + + + + + + + + + +
+# A doubly linked list permits bidirectional traversal.
+
+container duplex-list:_elem [
+  value:_elem
+  next:address:duplex-list:_elem
+  prev:address:duplex-list:_elem
+]
+
+# should I say in/contained-in:result, allow ingredients to refer to products?
+def push x:_elem, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [
+  local-scope
+  load-ingredients
+  result:address: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:address:duplex-list:_elem -> result:_elem [
+  local-scope
+  load-ingredients
+  return-unless in, 0
+  result <- get *in, value:offset
+]
+
+def next in:address:duplex-list:_elem -> result:address:duplex-list:_elem/contained-in:in [
+  local-scope
+  load-ingredients
+  return-unless in, 0
+  result <- get *in, next:offset
+]
+
+def prev in:address:duplex-list:_elem -> result:address: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:number/raw <- copy 34
+    11:number/raw <- copy 35
+    list:address:duplex-list:character <- push 3, 0
+    list <- push 4, list
+    list <- push 5, list
+    list2:address:duplex-list:character <- copy list
+    20:character/raw <- first list2
+    list2 <- next list2
+    21:character/raw <- first list2
+    list2 <- next list2
+    22:character/raw <- first list2
+    30:address:duplex-list:character/raw <- next list2
+    31:character/raw <- first 30:address:duplex-list:character/raw
+    32:address:duplex-list:character/raw <- next 30:address:duplex-list:character/raw
+    33:address:duplex-list:character/raw <- prev 30:address:duplex-list:character/raw
+    list2 <- prev list2
+    40:character/raw <- first list2
+    list2 <- prev list2
+    41:character/raw <- first list2
+    50:boolean/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
+  ]
+]
+
+# insert 'x' after 'in'
+def insert x:_elem, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [
+  local-scope
+  load-ingredients
+  new-node:address:duplex-list:_elem <- new {(duplex-list _elem): type}
+  *new-node <- put *new-node, value:offset, x
+  # save old next before changing it
+  next-node:address: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 [
+  run [
+    local-scope
+    list:address:duplex-list:character <- push 3, 0
+    list <- push 4, list
+    list <- push 5, list
+    list2:address:duplex-list:character <- next list  # inside list
+    list2 <- insert 6, list2
+    # check structure like before
+    list2 <- copy list
+    10:character/raw <- first list2
+    list2 <- next list2
+    11:character/raw <- first list2
+    list2 <- next list2
+    12:character/raw <- first list2
+    list2 <- next list2
+    13:character/raw <- first list2
+    list2 <- prev list2
+    20:character/raw <- first list2
+    list2 <- prev list2
+    21:character/raw <- first list2
+    list2 <- prev list2
+    22:character/raw <- first list2
+    30:boolean/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 [
+  run [
+    local-scope
+    list:address:duplex-list:character <- push 3, 0
+    list <- push 4, list
+    list <- push 5, list
+    list2:address:duplex-list:character <- next list  # inside list
+    list2 <- next list2  # now at end of list
+    list2 <- insert 6, list2
+    # check structure like before
+    list2 <- copy list
+    10:character/raw <- first list2
+    list2 <- next list2
+    11:character/raw <- first list2
+    list2 <- next list2
+    12:character/raw <- first list2
+    list2 <- next list2
+    13:character/raw <- first list2
+    list2 <- prev list2
+    20:character/raw <- first list2
+    list2 <- prev list2
+    21:character/raw <- first list2
+    list2 <- prev list2
+    22:character/raw <- first list2
+    30:boolean/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 [
+  run [
+    local-scope
+    list:address:duplex-list:character <- push 3, 0
+    list <- push 4, list
+    list <- push 5, list
+    list <- insert 6, list
+    # check structure like before
+    list2:address:duplex-list:character <- copy list
+    10:character/raw <- first list2
+    list2 <- next list2
+    11:character/raw <- first list2
+    list2 <- next list2
+    12:character/raw <- first list2
+    list2 <- next list2
+    13:character/raw <- first list2
+    list2 <- prev list2
+    20:character/raw <- first list2
+    list2 <- prev list2
+    21:character/raw <- first list2
+    list2 <- prev list2
+    22:character/raw <- first list2
+    30:boolean/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:address:duplex-list:_elem/contained-in:in, in:address:duplex-list:_elem -> in:address:duplex-list:_elem [
+  local-scope
+  load-ingredients
+  # if 'x' is null, return
+  return-unless x
+  next-node:address:duplex-list:_elem <- get *x, next:offset
+  prev-node:address: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 [
+  run [
+    local-scope
+    list:address:duplex-list:character <- push 3, 0
+    list <- push 4, list
+    list <- push 5, list
+    list2:address:duplex-list:character <- next list  # second element
+    list <- remove list2, list
+    10:boolean/raw <- equal list2, 0
+    # check structure like before
+    list2 <- copy list
+    11:character/raw <- first list2
+    list2 <- next list2
+    12:character/raw <- first list2
+    20:address:duplex-list:character/raw <- next list2
+    list2 <- prev list2
+    30:character/raw <- first list2
+    40:boolean/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 [
+  run [
+    local-scope
+    list:address:duplex-list:character <- push 3, 0
+    list <- push 4, list
+    list <- push 5, list
+    list <- remove list, list
+    # check structure like before
+    list2:address:duplex-list:character <- copy list
+    10:character/raw <- first list2
+    list2 <- next list2
+    11:character/raw <- first list2
+    20:address:duplex-list:character/raw <- next list2
+    list2 <- prev list2
+    30:character/raw <- first list2
+    40:boolean/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 [
+  run [
+    local-scope
+    list:address:duplex-list:character <- push 3, 0
+    list <- push 4, list
+    list <- push 5, list
+    # delete last element
+    list2:address:duplex-list:character <- next list
+    list2 <- next list2
+    list <- remove list2, list
+    10:boolean/raw <- equal list2, 0
+    # check structure like before
+    list2 <- copy list
+    11:character/raw <- first list2
+    list2 <- next list2
+    12:character/raw <- first list2
+    20:address:duplex-list:character/raw <- next list2
+    list2 <- prev list2
+    30:character/raw <- first list2
+    40:boolean/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 [
+  run [
+    local-scope
+    list:address:duplex-list:character <- push 3, 0
+    list <- remove list, list
+    1:number/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:address:duplex-list:_elem, end:address:duplex-list:_elem/contained-in:start -> start:address:duplex-list:_elem [
+  local-scope
+  load-ingredients
+  next:address:duplex-list:_elem <- get *start, next:offset
+  nothing-to-delete?:boolean <- 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:address: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:address:duplex-list:character <- push 18, 0
+  list <- push 17, list
+  list <- push 16, list
+  list <- push 15, list
+  list <- push 14, list
+  list <- push 13, list
+  1:address:duplex-list:character/raw <- copy list  # save list
+  run [
+    local-scope
+    list:address:duplex-list:character <- copy 1:address:duplex-list:character/raw  # restore list
+    # delete 16 onwards
+    # first pointer: to the third element
+    list2:address:duplex-list:character <- next list
+    list2 <- next list2
+    list2 <- remove-between list2, 0
+    # now check the list
+    10:character/raw <- get *list, value:offset
+    list <- next list
+    11:character/raw <- get *list, value:offset
+    list <- next list
+    12:character/raw <- get *list, value:offset
+    20:address:duplex-list:character/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:address:duplex-list:character <- push 18, 0
+  list <- push 17, list
+  list <- push 16, list
+  list <- push 15, list
+  list <- push 14, list
+  list <- push 13, list
+  1:address:duplex-list:character/raw <- copy list  # save list
+  run [
+    local-scope
+    list:address:duplex-list:character <- copy 1:address:duplex-list:character/raw  # restore list
+    # delete 15, 16 and 17
+    # start pointer: to the second element
+    list2:address:duplex-list:character <- next list
+    # end pointer: to the last (sixth) element
+    end:address:duplex-list:character <- next list2
+    end <- next end
+    end <- next end
+    end <- next end
+    remove-between list2, end
+    # now check the list
+    10:character/raw <- get *list, value:offset
+    list <- next list
+    11:character/raw <- get *list, value:offset
+    list <- next list
+    12:character/raw <- get *list, value:offset
+    20:address:duplex-list:character/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:address:duplex-list:character <- push 15, 0
+  list <- push 14, list
+  list <- push 13, list
+  1:address:duplex-list:character/raw <- copy list  # save list
+  run [
+    local-scope
+    list:address:duplex-list:character <- copy 1:address:duplex-list:character/raw  # restore list
+    # delete between first and second element (i.e. nothing)
+    list2:address:duplex-list:character <- next list
+    remove-between list, list2
+    # now check the list
+    10:character/raw <- get *list, value:offset
+    list <- next list
+    11:character/raw <- get *list, value:offset
+    list <- next list
+    12:character/raw <- get *list, value:offset
+    20:address:duplex-list:character/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:address:duplex-list:character <- push 18, 0
+  list <- push 17, list
+  list <- push 16, list
+  list <- push 15, list
+  list <- push 14, list
+  list <- push 13, list
+  1:address:duplex-list:character/raw <- copy list  # save list
+  run [
+    local-scope
+    list:address:duplex-list:character <- copy 1:address:duplex-list:character/raw  # restore list
+    # remove the third element and beyond
+    list2:address:duplex-list:character <- next list
+    remove-between list2, 0
+    # now check the list
+    10:character/raw <- get *list, value:offset
+    list <- next list
+    11:character/raw <- get *list, value:offset
+    20:address:duplex-list:character/raw <- next list
+  ]
+  memory-should-contain [
+    10 <- 13
+    11 <- 14
+    20 <- 0
+  ]
+]
+
+# insert list beginning at 'new' after 'in'
+def insert-range in:address:duplex-list:_elem, start:address:duplex-list:_elem/contained-in:in -> in:address:duplex-list:_elem [
+  local-scope
+  load-ingredients
+  return-unless in
+  return-unless start
+  end:address:duplex-list:_elem <- copy start
+  {
+    next:address:duplex-list:_elem <- next end/insert-range
+    break-unless next
+    end <- copy next
+    loop
+  }
+  next:address:duplex-list:_elem <- next in
+  *end <- put *end, next:offset, next
+  {
+    break-unless next
+    *next <- put *next, prev:offset, end
+  }
+  *in <- put *in, next:offset, start
+  *start <- put *start, prev:offset, in
+]
+
+def append in:address:duplex-list:_elem, new:address:duplex-list:_elem/contained-in:in -> in:address:duplex-list:_elem [
+  local-scope
+  load-ingredients
+  last:address:duplex-list:_elem <- last in
+  *last <- put *last, next:offset, new
+  return-unless new
+  *new <- put *new, prev:offset, last
+]
+
+def last in:address:duplex-list:_elem -> result:address:duplex-list:_elem [
+  local-scope
+  load-ingredients
+  result <- copy in
+  {
+    next:address:duplex-list:_elem <- next result
+    break-unless next
+    result <- copy next
+    loop
+  }
+]
+
+# helper for debugging
+def dump-from x:address: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?:boolean <- equal c, 10/newline
+      break-unless is-newline?
+      $print 10/newline
+      $print x, [: ]
+    }
+    loop
+  }
+  $print 10/newline, [---], 10/newline
+]
+
+ + + -- cgit 1.4.1-2-gfad0