1 # A table is like an array, except that you can index it with arbitrary types
  2 # and not just non-negative whole numbers.
  3 
  4 # incomplete; doesn't handle hash conflicts
  5 
  6 scenario table-read-write [
  7   local-scope
  8   tab:&:table:num:num <- new-table 30
  9   run [
 10     put-index tab, 12, 34
 11     60:num/raw, 61:bool/raw <- index tab, 12
 12   ]
 13   memory-should-contain [
 14     60 <- 34
 15     61 <- 1  # found
 16   ]
 17 ]
 18 
 19 scenario table-read-write-non-integer [
 20   local-scope
 21   tab:&:table:text:num <- new-table 30
 22   run [
 23     put-index tab, [abc def], 34
 24     1:num/raw, 2:bool/raw <- index tab, [abc def]
 25   ]
 26   memory-should-contain [
 27     1 <- 34
 28     2 <- 1  # found
 29   ]
 30 ]
 31 
 32 scenario table-read-not-found [
 33   local-scope
 34   tab:&:table:text:num <- new-table 30
 35   run [
 36     1:num/raw, 2:bool/raw <- index tab, [abc def]
 37   ]
 38   memory-should-contain [
 39     1 <- 0
 40     2 <- 0  # not found
 41   ]
 42 ]
 43 
 44 container table:_key:_value [
 45   length:num
 46   capacity:num
 47   data:&:@:table-row:_key:_value
 48 ]
 49 
 50 container table-row:_key:_value [
 51   occupied?:bool
 52   key:_key
 53   value:_value
 54 ]
 55 
 56 def new-table capacity:num -> result:&:table:_key:_value [
 57   local-scope
 58   load-ingredients
 59   result <- new {(table _key _value): type}
 60   data:&:@:table-row:_key:_value <- new {(table-row _key _value): type}, capacity
 61   *result <- merge 0/length, capacity, data
 62 ]
 63 
 64 # todo: tag results as /required so that call-sites are forbidden from ignoring them
 65 # then we could handle conflicts simply by resizing the table
 66 def put-index table:&:table:_key:_value, key:_key, value:_value -> table:&:table:_key:_value [
 67   local-scope
 68   load-ingredients
 69   hash:num <- hash key
 70   hash <- abs hash
 71   capacity:num <- get *table, capacity:offset
 72   _, hash-key:num <- divide-with-remainder hash, capacity
 73   hash-key <- abs hash-key  # in case hash overflows from a double into a negative integer inside 'divide-with-remainder' above
 74   table-data:&:@:table-row:_key:_value <- get *table, data:offset
 75   x:table-row:_key:_value <- index *table-data, hash-key
 76   occupied?:bool <- get x, occupied?:offset
 77   not-occupied?:bool <- not occupied?:bool
 78   assert not-occupied?, [can't handle collisions yet]
 79   new-row:table-row:_key:_value <- merge 1/true, key, value
 80   *table-data <- put-index *table-data, hash-key, new-row
 81 ]
 82 
 83 def index table:&:table:_key:_value, key:_key -> result:_value, found?:bool [
 84   local-scope
 85   load-ingredients
 86   hash:num <- hash key
 87   hash <- abs hash
 88   capacity:num <- get *table, capacity:offset
 89   _, hash-key:num <- divide-with-remainder hash, capacity
 90   hash-key <- abs hash-key  # in case hash overflows from a double into a negative integer inside 'divide-with-remainder' above
 91   table-data:&:@:table-row:_key:_value <- get *table, data:offset
 92   x:table-row:_key:_value <- index *table-data, hash-key
 93   empty:&:_value <- new _value:type
 94   result <- copy *empty
 95   found?:bool <- get x, occupied?:offset
 96   return-unless found?
 97   key2:_key <- get x, key:offset
 98   found?:bool <- equal key, key2
 99   return-unless found?
100   result <- get x, value:offset
101 ]
102 
103 def abs n:num -> result:num [
104   local-scope
105   load-ingredients
106   positive?:bool <- greater-or-equal n, 0
107   return-if positive?, n
108   result <- multiply n, -1
109 ]