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

# ordered_map -- 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.
#
public ordered_map(
           public OK type : property.orderable,
           public V  type,
           ks array OK,
           vs array V) : Map OK V
  pre
    ks.length = vs.length

is


  # entry represents the pair of key and value at the given
  # index i of the ordered map.
  #
  public entry(i i32) : property.orderable is


    key => ks[i]
    val => vs[i]


    # total order over entries.
    #
    fixed type.lteq(a, b entry.this) => a.key ≤ b.key


  # a sorted array of entries of this map
  #
  public sorted_entries := sorted_array_of (ks.indices.map (i -> entry i)).as_array


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


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


  # get an array of all key/value pairs in this map
  #
  public items Sequence (tuple OK V) => sorted_entries.map (e -> (e.key, e.val))


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


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


  # create an empty instance of ordered_map
  #
  public type.empty => (container.ordered_map
                        (list OK).empty.as_array
                        (list V).empty.as_array)