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) : container.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.
    #
    public fixed redef type.lteq(a, b entry.this) => a.key ≤ b.key


  # a sorted array of entries of this map
  #
  public sorted_entries =>
    sorted_indices
      .map (i -> entry i)
      .as_array


  # a sorted array of indices of this map
  #
  sorted_indices := ks.indices.sort_by (a,b)->ks[a]≤ks[b]


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


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


  # get an array of all key/value pairs in this map
  #
  public redef items Sequence (tuple OK V) => sorted_indices.map i->(ks[i], vs[i])


  # add mapping from k to v
  #
  public add(k OK, v V) =>
    match ordered_map.this[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 a mutable map from this
  #
  public redef as_mutable_map(LM type : mutate) container.Mutable_Map OK V =>
    (container.mutable_tree_map LM OK V).from_array items.as_array


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