container/Mutable_Hash_Map.fz

# This file is part of the Fuzion language implementation.
#
# The Fuzion language implementation is free software: you can redistribute it
# and/or modify it under the terms of the GNU General Public License as published
# by the Free Software Foundation, version 3 of the License.
#
# The Fuzion language implementation is distributed in the hope that it will be
# useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
# License for more details.
#
# You should have received a copy of the GNU General Public License along with The
# Fuzion language implementation.  If not, see <https://www.gnu.org/licenses/>.


# -----------------------------------------------------------------------
#
#  Tokiwa Software GmbH, Germany
#
#  Source code of Fuzion standard library feature Mutable_Hash_Map
#
# -----------------------------------------------------------------------



# Mutable_Hash_Map -- a mutable hash map from keys HK to values V
#
# Uses a mutable array internally, when upper_load_factor is reached size is multiplied
# by resize_factor (doubled, tripled, etc.) and elements are copied to new array of this size.
# If lower_load_factor is reached size is divided by resize_factor.
# Insert and retrieve operations on this map are therefore in amortized O(1).
#
module:public Mutable_Hash_Map(
        # the mutate effect
        #
        public LM type : mutate,

        # type of the keys
        #
        public HK type : property.hashable,

        # type of the values
        #
        public V  type,

        # initial size, also the size of the hash map will not decrease below this
        #
        min_size i32,

        # NYI: use fractions instead of floats (3x)

        # lower boundary at which the size of the internal array is decreased
        #
        lower_load_factor f32,

        # upper boundary at which the size of the internal array is increased
        #
        upper_load_factor f32,

        # factor by which the allocated_size is increased if load reaches upper_load_factor
        #
        resize_factor f32 ) ref : container.Mutable_Map HK V
pre
  debug: min_size > 0
  debug: 0.0 < lower_load_factor < upper_load_factor
  debug: lower_load_factor < upper_load_factor < 1.0
  debug: resize_factor >= 2.0

is

  # element at this index was deleted, this index should be treated as occupied when looking up elements
  # to not cause unexpected gaps that could lead to lost elements
  # for insertions it is treated the same as an empty index
  universe.del is

  # number of entries currently in this map
  #
  load := mut 0

  # maximum number of pairs before size is increased
  #
  max_elem => (allocated_size.get.as_f32 * upper_load_factor).ceil.as_i32

  # minimum number of pairs before size is decreased
  #
  min_elem => (allocated_size.get.as_f32 * lower_load_factor).floor.as_i32

  # size of allocated contents array, allows for some empty slots
  #
  allocated_size := mut (min_size.as_f32 / upper_load_factor).ceil.as_i32

  # the contents
  #
  contents := mut (LM.env.new_array (choice nil del (tuple HK V)) allocated_size.get.as_i64 nil)


  # calculate the index of k within contents array in case of no conflict
  #
  idx (k HK) =>
    h1 := hash k
    h  := ((h1 << 17) ^ (h1 << 3) ^ h1).cast_to_i64 & i64.max
    h % allocated_size.get.as_i64


  # in case of a collision at given position,
  # return the next alternative position to check
  #
  collision (at i64) =>
    # large prime number, generated using https://bigprimes.org/
    (at + 904644503766293287) % allocated_size.get.as_i64


  # increase internal allocation if upper_load_factor is reached
  #
  increase_if_necessary =>
    if size > max_elem
      change_allocated_size (allocated_size.get.as_f32 * resize_factor).ceil.as_i32


  # decrease internal allocation if lower_load_factor is reached
  #
  decrease_if_necessary =>
    if size < min_elem && max_elem > min_size
      change_allocated_size (allocated_size.get.as_f32 / resize_factor).ceil.as_i32


  # change size of internal allocation to new_alloc_size
  #
  change_allocated_size(new_alloc_size i32)
    pre
      debug: size <= (new_alloc_size.as_f32 * upper_load_factor).ceil.as_i32
      debug: max size min_size >= (new_alloc_size.as_f32 * lower_load_factor).floor.as_i32
  =>
    allocated_size <- new_alloc_size
    old_contents := contents.get.as_array
    contents <- LM.env.new_array (choice nil del (tuple HK V)) allocated_size.get.as_i64 nil
    for elem in old_contents do
      match elem
        t tuple HK V =>
          ok, ov := t
          store (idx ok) ok ov false false
        * => # noting to add


  # store key value pair at given index
  # updates value for existing key, does conflict resolution
  #
  store (at i64, k HK, v V, update_size bool, is_update bool) =>

    match contents.get[at]
      nil     =>
        if is_update
          store (idx k) k v update_size false
        else
          contents.get[at] := (k, v) # insert new key value pair
          if update_size then load <- load.get + 1

      t tuple =>
        ek, _ := t
        if ek = k                 # no conflict, but remapping of k
          contents.get[at] := (k, v)
        else                      # conflict
          store (collision at) k v update_size is_update
      del =>
        if is_update
          # Treat `del` as occupied since we don't yet know if this is an update;
          # the same key could still exist at a later index.
          store (collision at) k v update_size is_update
        else
          contents.get[at] := (k, v) # insert new key value pair
          if update_size then load <- load.get + 1


  # number of entries in this map
  #
  public redef size i32 =>
    load.get


  # add key-value pair to this map
  # if key already exists, existing value gets updated
  #
  public redef put(k HK, v V) unit =>

    store (idx k) k v true true

    increase_if_necessary


  # get the value k is mapped to or nil if it does not exist
  #
  public redef get(k HK) option V =>

    retrieve (at i64, stop_at_start bool) option V =>
      match contents.get[at]
        nil     => nil
        t tuple =>
          ek, v := t
          if ek = k
            v
          else
            retrieve (collision at) true
        del =>
          (at = start_idx && stop_at_start) ? nil : retrieve (collision at) true

    start_idx := idx k
    retrieve start_idx false


  # remove key from map, returns the removed value
  #
  public redef remove(k HK) option V ! LM =>


    delete(del_idx i64, stop_at_start bool) option V =>
      match contents.get[del_idx]
        nil => nil
        t tuple =>
          ek, v := t
          if ek = k
            contents.get[del_idx] := nil
            load <- load.get - 1
            contents.get[del_idx] := del
            v
          else
            delete (collision del_idx) true
        del =>
          (stop_at_start && del_idx = del_start_idx) ? nil : delete (collision del_idx) true

    del_start_idx := idx k

    return_val := delete del_start_idx false

    decrease_if_necessary

    return_val


  # get a list of all key/value pairs in this map
  #
  public redef items Sequence (tuple HK V) =>
    contents.get.as_array
      .filter (o -> o ? tuple => true | * => false)
      .map (x -> x ? t tuple => t | * => panic "filter failed" )


  # create an immutable map from this
  #
  public redef as_map container.Map HK V =>
    pairs := items
    container.hash_map HK V (pairs.map (.0) ).as_array (pairs.map (.1)).as_array


  # create an empty instance of Mutable_Hash_Map
  #
  public fixed redef type.empty container.Mutable_Hash_Map LM HK V => container.Mutable_Hash_Map LM HK V 11 0.25 0.5 2