container/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 hash_map
#
# Author: Fridtjof Siebert (siebert@tokiwa.software)
#
# -----------------------------------------------------------------------
# hash_map -- an immutable hash map from keys HK to values V
#
public hash_map(
public HK type : property.hashable,
public V type,
ks array HK,
vs array V) : Map HK V
pre
ks.length = vs.length
is
# number of entries in this map
#
size => ks.length
# size of allocated contents array, allows for some empty slots
#
allocated_size => size * 2
# calculate the index of k within contents array in case of no conflict
#
at (k HK) => ((hash k).low32bits.cast_to_i32 & i32.max) % allocated_size
# in case of a collision at given position,
# return the next alternative position to check
#
collision (at i32) =>
(at + 1) % allocated_size # NYI: dumb collision function, check literature and improve!
mi : mutate is
# the contents
#
contents := mi.go ()->
for
mcontents := (mutate.array (option (tuple HK V))).new mi allocated_size nil, mcontents
k in ks
v in vs
do
store (at k)
# store k,v for index at,
store (at i32) unit =>
match mcontents[at]
nil => # slot is free, so use it:
mcontents[at] := (k, v)
t tuple => # we have a conflict
(ek, _) := t
if ek = k # no conflict, but remapping of k
mcontents[at] := (k, v)
else # conflict
store (collision at)
/* NYI: With better pattern matching, this could be:
match mcontents[at]
nil,
(k, _) => mcontent[at] := (k, v) # no conflict
(_, _) => store collision at # conflict
*/
else
mcontents.as_array
# get the value k is mapped to
#
public index [] (k HK) option V =>
retrieve (at i32) option V =>
match contents[at]
nil => nil
t tuple =>
(ek, v) := t
if ek = k
v
else
retrieve (collision at)
retrieve (at k)
# get a list of all key/value pairs in this map
#
public items Sequence (tuple HK V) =>
contents
.filter (o -> o??)
.map (o -> match o
nil => panic "filter failed"
t tuple => t)
# this hash map as a human readable string
# example: [(0,a),(1,b),(2,c),(3,d)]
#
public redef as_string =>
items
.map (t -> "({t.values.0},{t.values.1})")
.as_string
# empty -- convenience routine to create an empty instance of hash_map
#
public type.empty => container.hash_map HK V [] []
last changed: 2024-03-07