container/ps_set.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 ps_set
#
# Author: Fridtjof Siebert (siebert@tokiwa.software)
#
# -----------------------------------------------------------------------
# ps_set -- a partially sorted set based on ps_map
#
# ps_set is a persistent set of ordered values. This set is generally
# well-behaved with respect to cumulative and average performance.
#
# WARNING: Due to the high worst-case time for addition, this structure should
# not be used in situations when adding a single element repeatedly to the same
# instance of ps_set is performance critical. If the resulting set's size n is a
# power of 2, this will trigger the worst-case addition time resulting in
# O(m*n log² n) for adding an element m times.
#
private:public ps_set
(K type : property.orderable,
psm container.ps_map K unit,
dummy unit # just to distinguish this from routine ps_set(vs Sequence K)
)
: Set K
is
# list representation of values in this set
#
public redef as_list => psm.keys.as_list
# add new element k to this set.
#
# NYI: Resolve duality of `add0` (that results in `ps_set`) and `add` (that
# results in `Set`). Maybe `Set.add` should result in `Set.this.type`,
# so we do not need `add0`?
#
fixed add0 (k K) ps_set K =>
if has k
ps_set.this
else
ps_set (psm.add k unit) unit
# add new element k to this set.
#
# NYI: this should be integrated in the mutate effect!
#
public redef add (k K) Set K =>
add0 k
# create a sorted array from the elements of this set
#
redef as_array => psm.as_key_array
# check if an element equal to given element k is part of this set
#
public has (k K) => psm.has k
# get the lowest element in this set
#
public redef min => psm.min
# get the highest element in this set
#
public redef max => psm.max
# add all elements of the given Sequence to this set
#
public fixed add_all (s Sequence K) ps_set K =>
s.reduce ps_set.this (r,k -> r.add0 k)
# number of entries in this set. May be undefined, i.e., a range of
# floating point numbers or an infinite set.
#
public redef size_option option i32 => psm.size
# does this set contain the given value?
#
public redef contains (e K) bool => has e
# an empty ps_set
#
public fixed type.empty container.ps_set K =>
container.ps_set (container.ps_map K unit).empty unit
# initialize a partially sorted set from one Sequence
#
# This feature creates a pre-initialized instance of ps_set.
#
public fixed redef type.new(vs Sequence K) container.Set K => (container.ps_set K).empty.add_all vs
last changed: 2025-01-23