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


  # number of elements in this set
  #
  public size => psm.size


  # list representation of values in this set
  #
  public redef as_list => psm.keys.as_list


  # print contents of this set
  #
  show => psm.show


  # 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 K (psm.add k unit) unit


  # add new element k to this set.
  #
  # NYI: this should be intergrated 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 min => psm.min


  # get the highest element in this set
  #
  public max => psm.max


  # union of two ps_sets
  #
  public infix ∪ (other ps_set.this) => ps_set K (psm ∪ other.psm) unit


  # intersection of two ps_sets
  public infix ∩ (other ps_set.this) =>
    s := (ps_set.this ∪ other).filter (x -> ps_set.this.has x && other.has x)
    (ps_set K).empty.add_all s


  # add all elements of the given Sequence to this set
  #
  public fixed add_all (s Sequence K) ps_set K =>
    s.reduce (ps_set K) 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 => size


  # does this set contain the given value?
  #
  public contains (e K) bool => has e

/*
has     -- NYI: 'has' keyword not supported yet, so the following require an instance to be called on
*/

  # an empty ps_set
  #
  public fixed type.empty container.ps_set K =>
    container.ps_set K (container.ps_map K unit).empty unit


  # monoid of ps_set with infix ∪ operation.
  #
  public type.union : Monoid (container.ps_set K) is
    redef infix ∙ (a, b container.ps_set K) => a ∪ b
    redef e => (container.ps_set K).empty


  # equality
  #
  public fixed type.equality(a, b container.ps_set K) bool =>
    # NYI: a bit expensive
    (a ∪ b).size = a.size


  # initialize a partially sorted set from one Sequence
  #
  # This feature creates a pre-initialized instance of ps_set.
  #
  public type.from_sequence(vs Sequence K) => (container.ps_set K).empty.add_all vs