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