# 64-bit murmur OOAT hash
[FUNC @HASH [[PARAM !m $STRING] [RETURNS [INT]]] [
  [DEFINE !h 525201411107845655]
  [DEFINE !i 0]
  [WHILE [< !i [LEN !m]] [
    [DEFINE !h [XOR !h [TOI [GET !m !i]]]]
    [DEFINE !h [* !h 6616326155283851669]]
    [DEFINE !h [SHIFT !h -47]]
    [DEFINE !i [+ !i 1]]
  ]]
  [RETURN !h]
]]

[TYPE $MAP_NODE [STRUCT 
  [FIELD .key $STRING]
  [FIELD .val [BX]]
  [FIELD .psl [INT]]
]]

[FUNC @EMPTY_MAP_NODE [[RETURNS $MAP_NODE]] [
  [RETURN [NEW $MAP_NODE [: .key [NEW $STRING]] [: .val [BOX [NEW $MAP_NONE]]] [: .psl 0]]]
]]

[TYPE $MAP [STRUCT 
  [FIELD .buckets [ARRAY $MAP_NODE]]
  [FIELD .cnt [INT]]
]]

[FUNC @MAP_NEW [[RETURNS $MAP]] [
  [DEFINE !m [NEW $MAP [: .buckets [ARR [@EMPTY_MAP_NODE]]] [: .cnt 0]]]
  [RETURN !m]
]]

[FUNC @MAP_INSERT [[PARAM !m $MAP] [PARAM !k $STRING] [PARAM !v [BX]]] [
  # MAX LOAD FACTOR: 0.9
  [IF [> [/ [TOF [GET !m .cnt]] [TOF [LEN [GET !m .buckets]]]] 0.9] [
    [@MAP_RESIZE !m]
  ] []]

  # Hash
  [DEFINE !h [% [@HASH !k] [LEN [GET !m .buckets]]]]
  [DEFINE !curr [NEW $MAP_NODE [: .key !k] [: .val !v] [: .psl 0]]]

  # Loop until inserted
  [WHILE [@TRUE] [
    [IF [PEEK [GET [GET [GET !m .buckets] !h] .val] $MAP_NONE] [
      # Insert, empty bucket
      [SET [GET !m .buckets] !h !curr]
      [SET !m [: .cnt [+ [GET !m .cnt] 1]]]
      [RETURN]
    ] []]

    [IF [> [GET !curr .psl] [GET [GET [GET !m .buckets] !h] .psl]] [
      # Swap, PSL greater
      [DEFINE !tmp [GET [GET !m .buckets] !h]]
      [SET [GET !m .buckets] !h !curr]
    ] []]

    [SET !curr [: .psl [+ [GET !curr .psl] 1]]] # Increment PSL
    [DEFINE !h [+ !h 1]]
  ]]
]]

[FUNC @MAP_SET  [[PARAM !m $MAP] [PARAM !k $STRING] [PARAM !v [BX]]] [
  # Insert or update
  [DEFINE !ind [@MAP_KEYIND !m !k]]
  [IF [< !ind 0] [
    # Insert
    [@MAP_INSERT !m !k !v]
  ] [
    # Update
    [SET [GET [GET !m .buckets] !ind] [: .val !v]]
  ]]
]]

[FUNC @MAP_KEYIND [[PARAM !m $MAP] [PARAM !k $STRING] [RETURNS [INT]]] [ # TODO: Perhaps in the future implement smart search? Unsure on performance gains, but relatively simple to implement
  [DEFINE !h [% [@HASH !k] [LEN [GET !m .buckets]]]]
  [DEFINE !psl 0]
  [WHILE [< !h [LEN [GET !m .buckets]]] [
    [DEFINE !n [GET [GET !m .buckets] !h]]

    [IF [@STREQ !k [GET !n .key]] [ # Found key, return
      [RETURN !h]
    ] []]


    [IF [PEEK [GET !n .val] $MAP_NONE] [ # If the value is empty, it is not in the map
      [RETURN -1]
    ] []]

    [IF [> [GET !n .psl] !psl] [ # If the PSL at the spot is greater than it would have been for the real key, it is not in the map
      [RETURN -1]
    ] []]

    [DEFINE !h [+ !h 1]]
    [DEFINE !psl [+ !psl 1]]
  ]]
  [RETURN -1]
]]


# Returns [BOX [NEW $MAP_NONE]] if key not found
[TYPE $MAP_NONE [STRUCT]]
[FUNC @MAP_GET [[PARAM !m $MAP] [PARAM !k $STRING] [RETURNS [BX]]] [
  [DEFINE !ind [@MAP_KEYIND !m !k]]
  [IF [= !ind -1] [RETURN [BOX [NEW $MAP_NONE]]] [RETURN [GET [GET [GET !m .buckets] !ind] .val]]]
]]

[FUNC @MAP_CONTAINS [[PARAM !m $MAP] [PARAM !k $STRING] [RETURNS [BOOL]]] [
  [DEFINE !ind [@MAP_KEYIND !m !k]]
  [RETURN [NEQ !ind -1]]
]]

[FUNC @MAP_DEL [[PARAM !m $MAP] [PARAM !k $STRING]] [
  [DEFINE !h [@MAP_KEYIND !m !k]]
  [IF [= !h -1] [RETURN] []] # if not in map, return
  
  # Clear slot
  [SET [GET !m .buckets] !h [@EMPTY_MAP_NODE]]

  # Backshifting algorithm
  [WHILE [& [< !h [- [LEN [GET !m .buckets]] 1]] [> [GET [GET [GET !m .buckets] [+ !h 1]] .psl] 0]] [ # Loop until PSL of key is 0 or out of range
    # Backshift
    [SET [GET !m .buckets] !h [GET [GET !m .buckets] [+ !h 1]]]
    [SET [GET [GET !m .buckets] !h] [: .psl [- [GET [GET [GET !m .buckets] !h] .psl] 1]]] # Decrement PSL
    [DEFINE !h [+ !h 1]]
  ]]
  [SET [GET !m .buckets] !h [@EMPTY_MAP_NODE]]

  # Update count
  [SET !m [: .cnt [- [GET !m .cnt] 1]]]
]]

[FUNC @MAP_LIST [[PARAM !m $MAP] [RETURNS [ARRAY [TUPLE $STRING [BX]]]]] [
  [DEFINE !out [NEW [ARRAY [TUPLE $STRING [BX]]] [GET !m .cnt]]]
  [DEFINE !i 0]
  [DEFINE !ins 0]
  [WHILE [< !ins [GET !m .cnt]] [
    [IF [NOT [PEEK [GET [GET [GET !m .buckets] !i] .val] $MAP_NONE]] [
      [DEFINE !n [GET [GET !m .buckets] !i]]
      [APPEND !out [NEW [TUPLE $STRING [BX]] [GET !n .key] [GET !n .val]]]
      [DEFINE !ins [+ !ins 1]]
    ] []]
    [DEFINE !i [+ !i 1]]
  ]]
  [RETURN !out]
]]

[FUNC @MAP_RESIZE [[PARAM !m $MAP]] [
  [DEFINE !old [GET !m .buckets]]
  [SET !m [: .buckets [NEW [ARRAY $MAP_NODE] [* 2 [LEN !old]]]]]

  # Fill with empty map nodes
  [DEFINE !i 0]
  [WHILE [< !i [* 2 [LEN !old]]] [
    [APPEND [GET !m .buckets] [@EMPTY_MAP_NODE]]
    [DEFINE !i [+ !i 1]]
  ]]


  [SET !m [: .cnt 0]]
  [DEFINE !i 0]
  [WHILE [< !i [LEN !old]] [
    [DEFINE !n [GET !old !i]]
    [IF [NOT [PEEK [GET !n .val] $MAP_NONE]] [
      # Insert
      [DEFINE !k [GET !n .key]]
      [DEFINE !v [GET !n .val]]
      [@MAP_INSERT !m !k !v]
    ] []]
    [DEFINE !i [+ !i 1]]
  ]]
]]