1 files changed, 109 insertions, 0 deletions
diff --git a/archive/1.vm/070table.mu b/archive/1.vm/070table.mu
new file mode 100644
index 00000000..21184084
--- /dev/null
+++ b/archive/1.vm/070table.mu
@@ -0,0 +1,109 @@
+# A table is like an array, except that you can index it with arbitrary types
+# and not just non-negative whole numbers.
+
+# incomplete; doesn't handle hash conflicts
+
+scenario table-read-write [
+  local-scope
+  tab:&:table:num:num <- new-table 30
+  run [
+    put-index tab, 12, 34
+    60:num/raw, 61:bool/raw <- index tab, 12
+  ]
+  memory-should-contain [
+    60 <- 34
+    61 <- 1  # found
+  ]
+]
+
+scenario table-read-write-non-integer [
+  local-scope
+  tab:&:table:text:num <- new-table 30
+  run [
+    put-index tab, [abc def], 34
+    1:num/raw, 2:bool/raw <- index tab, [abc def]
+  ]
+  memory-should-contain [
+    1 <- 34
+    2 <- 1  # found
+  ]
+]
+
+scenario table-read-not-found [
+  local-scope
+  tab:&:table:text:num <- new-table 30
+  run [
+    1:num/raw, 2:bool/raw <- index tab, [abc def]
+  ]
+  memory-should-contain [
+    1 <- 0
+    2 <- 0  # not found
+  ]
+]
+
+container table:_key:_value [
+  length:num
+  capacity:num
+  data:&:@:table-row:_key:_value
+]
+
+container table-row:_key:_value [
+  occupied?:bool
+  key:_key
+  value:_value
+]
+
+def new-table capacity:num -> result:&:table:_key:_value [
+  local-scope
+  load-inputs
+  result <- new {(table _key _value): type}
+  data:&:@:table-row:_key:_value <- new {(table-row _key _value): type}, capacity
+  *result <- merge 0/length, capacity, data
+]
+
+# todo: tag results as /required so that call-sites are forbidden from ignoring them
+# then we could handle conflicts simply by resizing the table
+def put-index table:&:table:_key:_value, key:_key, value:_value -> table:&:table:_key:_value [
+  local-scope
+  load-inputs
+  hash:num <- hash key
+  hash <- abs hash
+  capacity:num <- get *table, capacity:offset
+  _, hash-key:num <- divide-with-remainder hash, capacity
+  hash-key <- abs hash-key  # in case hash overflows from a double into a negative integer inside 'divide-with-remainder' above
+  table-data:&:@:table-row:_key:_value <- get *table, data:offset
+  x:table-row:_key:_value <- index *table-data, hash-key
+  occupied?:bool <- get x, occupied?:offset
+  not-occupied?:bool <- not occupied?:bool
+  assert not-occupied?, [can't handle collisions yet]
+  new-row:table-row:_key:_value <- merge true, key, value
+  *table-data <- put-index *table-data, hash-key, new-row
+]
+
+def index table:&:table:_key:_value, key:_key -> result:_value, found?:bool [
+  local-scope
+  load-inputs
+  hash:num <- hash key
+  hash <- abs hash
+  capacity:num <- get *table, capacity:offset
+  _, hash-key:num <- divide-with-remainder hash, capacity
+  hash-key <- abs hash-key  # in case hash overflows from a double into a negative integer inside 'divide-with-remainder' above
+  table-data:&:@:table-row:_key:_value <- get *table, data:offset
+  x:table-row:_key:_value <- index *table-data, hash-key
+  empty:&:_value <- new _value:type
+  result <- copy *empty
+  found?:bool <- get x, occupied?:offset
+  return-unless found?
+  key2:_key <- get x, key:offset
+  found?:bool <- equal key, key2
+  return-unless found?
+  result <- get x, value:offset
+]
+
+def abs n:num -> result:num [
+  local-scope
+  load-inputs
+  positive?:bool <- greater-or-equal n, 0
+  return-if positive?, n
+  result <- multiply n, -1
+]