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
        #
        private min_size i32,

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

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

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

        # factor by which the allocated_size is increased if load reaches upper_load_factor
        #
        resize_factor f32 ) ref : 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

  # 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 (option (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) =>
    (at + 1) % allocated_size.get.as_i64  # NYI: dumb collision function, check literature and improve!


  # 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 (option (tuple HK V)) allocated_size.get.as_i64 nil
    for tup in (old_contents.filter o->o??) do
      ok, ov := tup.get
      store (idx ok) ok ov false


  # 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) =>
    match contents.get[at]
      nil     =>
        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


  # 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

    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) option V =>
      match contents.get[at]
        nil     => nil
        t tuple =>
          ek, v := t
          if ek = k
            v
          else
            retrieve (collision at)

    retrieve (idx k)


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


    del(del_idx i64) 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
            fill_hole del_idx (collision del_idx)
            v
          else
            del (collision del_idx)


    # move elements if they should be in the position of the removed element
    # recursively filles new holes
    #
    fill_hole(cur_idx, next_idx i64) =>
      match contents.get[next_idx]
        nil     => # done
        t tuple =>
          ek, _ := t

          if (
            # not having passed array end: move elements saved at a larger index
            (next_idx >= cur_idx && idx ek <= cur_idx) ||

            # element index is larger then array index (collision moved it beyond end):
            #   - always move to left
            #   - move to right (beyond beginning into the end) if it can normally be saved at that index
            (idx ek > next_idx && (cur_idx < next_idx || idx ek <= cur_idx)) ||

            # having passed array end: move elements saved at a larger index only if they get moved left (i.e. not beyond the beginning into the end)
            (cur_idx < cur_idx && next_idx < cur_idx && idx ek <= cur_idx))
          then
            contents.get[cur_idx] := t
            contents.get[next_idx] := nil
            fill_hole next_idx (collision next_idx)
          else
            fill_hole cur_idx (collision next_idx)

    return_val := del (idx k)

    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??
      .map (o -> o.get (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