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
      ix := at k
      store ix
#     store (at k)     # NYI! Currently parser treats this like a declaration

      # 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
              newAt := collision at
              store newAt
#             store (collision at)     # NYI! Currently parser treats this like a declaration

/* 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
            newAt := collision at
            retrieve newAt
#           retrieve (collision at)     # NYI! Currently parser treats this like a declaration

    ix := at k
    retrieve ix
#   retrieve (at k)     # NYI! Currently parser treats this like a declaration


  # get a stream of all key/value pairs in this map
  #
  items Sequence<tuple<HK,V>> is
    res : Sequence<tuple<HK,V>> is
      redef asList =>
        contents
          .filter         (o -> o??)
          .mapSequence<tuple<HK,V>>(o -> match o
                                           nil     => panic "filter failed"
                                           t tuple => t)
    res


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


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