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 [] []