# 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
