path: root/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
]