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 := sortedArray<entry> ((0..ks.length-1).mapSequence<entry> (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<V> (i -> sortedEntries[i].val)


  # get a stream of all key/value pairs in this map
  #
  items Sequence<tuple<OK,V>> is sortedEntries.map<tuple<OK,V>> (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++(marray<V> 1 v)).asArray)
      V =>
        va := array<V> 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


# orderedMap -- convenience routine to create an empty instance of orderedMap
#
#
orderedMap<OK : ordered<OK>, V> => (orderedMap
                                    Sequences.empty<OK>.asArray
                                    Sequences.empty<V>.asArray)