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)
last changed: 2024-03-07