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
  #
  public redef size i32 => 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 ! ()->
    for
      mcontents := (mutate.array (option (tuple HK V))).new mi allocated_size.as_i64 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.as_i64]
          nil     =>     # slot is free, so use it:
            mcontents[at.as_i64] := (k, v)

          t tuple =>     # we have a conflict
            ek, _ := t
            if ek = k    # no conflict, but remapping of k
              mcontents[at.as_i64] := (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 redef 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 redef items Sequence (tuple HK V) =>
    contents
      .filter o->o??
      .map (o -> o.get (panic "filter failed"))


  # NYI: implement this when #4642 is done
  # create a mutable map from this
  #
  # public redef as_mutable_map container.Mutable_Map PK V =>


  # empty -- convenience routine to create an empty instance of hash_map
  #
  public fixed redef type.empty container.hash_map HK V =>
    container.hash_map HK V [] []