Fuzion Logo
flang.dev — The Fuzion Language Portal
JavaScript seems to be disabled. Functionality is limited.

hashMap.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 hashMap
#
#  Author: Fridtjof Siebert (siebert@tokiwa.software)
#
# -----------------------------------------------------------------------

# hashMap -- an immutable hash map from keys HK to values V
#
hashMap(HK (hasHash HK).type,
        redef 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
  #
  /* NYI: local */
  allocatedSize => size * 2


  # calculate the index of k within contents array in case of no conflict
  #
  at (k HK) => (k.hash.low32bits.castTo_i32 & 0.max) % allocatedSize


  # in case of a collision at given position,
  # return the next alternative position to check
  #
  collision (at i32) =>
    (at + 1) % allocatedSize  # NYI: dumb collision function, check literature and improve!


  # the contents
  #
  /* NYI: local */
  contents :=
    for
      mcontents := (marrays (option (tuple HK V))).new allocatedSize nil, mcontents
      k in ks
      v in vs
    do
      store (at k)

      # store k,v for index at,
      store (at i32) unit is

        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
  #
  index [] (k HK) option V is

    retrieve (at i32) option V is
      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
  #
  items Sequence (tuple HK V) is
    contents
      .filter      (o -> o??)
      .mapSequence (o -> match o
                            nil     => panic "filter failed"
                            t tuple => t)


# hashMaps -- unit type feature declaring features related to haspMap
#
# NYI: move to hashMap.type
#
hashMaps(HK (hasHash HK).type, V type) is


  # empty -- convenience routine to create an empty instance of hashMap
  #
  empty => (hashMap
            (Sequences.empty HK).asArray
            (Sequences.empty V).asArray)