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

# orderedMap -- an immutable map from ordered keys OK to values V
#
# Lookup performance is O(log size) since it uses binary search in a
# sorted array.  When deterministic performance is desired, an ordered map
# should be preferred over a hash map.
#
# performance of creation of the map is in O(n log n) where n is
# keys.length.
#
orderedMap(OK ordered OK .type,
           redef V type,
           ks array OK,
           vs array V) : map OK V
  pre
    ks.length == vs.length

is

  # entry is an index in ks/vs

  entry(i i32) : ordered entry is
    infix <= (other entry) => ks[i] <= ks[other.i]
    key => ks[i]
    val => vs[i]
  sortedEntries := sortedArrayOf ((0..ks.length-1).mapSequence (i -> entry i)).asArray

  # number of entries in this map
  #
  size => sortedEntries.length


  # get the value k is mapped to, or nil if none.
  #
  # performance is O(log size).
  #
  index [] (k OK) option V is
    sortedEntries.find (e -> ks[e.i] <> k)
                 .map (i -> sortedEntries[i].val)


  # get a stream of all key/value pairs in this map
  #
  items Sequence (tuple OK V) is sortedEntries.map (e -> (e.key, e.val))


  # add mapping from k to v
  #
  add(k OK, v V) orderedMap OK V is
    match index[](k)
      nil =>
        (orderedMap
          (ks++[k]).asArray
          (vs++[v]).asArray)
      V =>
        va := array size (i -> if ks[i]=k then v else vs[i])
        (orderedMap ks va)


  # create a string containing all mappings
  #
  redef asString =>
    for
      r := "", r + c + n
      i in ks.indices
      n := "({ks[i]} => {vs[i]})"
      c := "", ", "
    else
      r


# orderedMaps -- unit type feature declaring features related to orderedMap
#
# NYI: move to orderedMap.type
#
orderedMaps (OK ordered OK .type, V type) is


  # create an empty instance of orderedMap
  #
  empty => (orderedMap
            (Sequences.empty OK).asArray
            (Sequences.empty V ).asArray)