bitset.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 bitset
#
#  Author: Fridtjof Siebert (siebert@tokiwa.software)
#
# -----------------------------------------------------------------------

# bitset -- persistent set of unsigned integers
#
private:public bitset : choice nil          # empty bitset
                               u64          # unit bitset
                               (array bool) # general
                        , property.equatable
is

  # test if the given bit is part of this bitset
  #
  public has (bit u64) bool =>
    match bitset.this
      _ nil   => false
      x u64   => bit = x
      a array => a.length.as_u64 > bit && a[bit.as_i32]

  # alternative for has using []
  #
  public index[] (bit u64) => has bit

  # set the given bit
  public put (bit u64) bitset =>
    if has bit
      bitset.this
    else
      match bitset.this
        _ nil   => bit
        x u64   => array bool (max bit x).as_i32+1 (i -> i.as_u64 = bit || i.as_u64 = x)
        a array => a.put bit.as_i32 true false

  # union of two bitsets
  #
  public infix ∪ (other bitset) bitset =>
    match bitset.this
      _ nil   => other
      x u64   => other.put x
      a array =>
        match other
          _ nil   => bitset.this
          x u64   => bitset.this.put x
          b array =>
            array bool (max a.length b.length) (i -> (has i.as_u64) || (other.has i.as_u64))

  # get the highest bit in this bitset
  #
  public highest option u64 =>
    match bitset.this
      _ nil   => nil
      x u64   => x
      a array => a.length.as_u64-1

  # equality
  #
  public fixed type.equality(a, b bitset) bool =>
     h := a.highest >>= i -> b.highest >>= j -> max i j
     match h
       _ nil => a.highest!! && b.highest!!
       m u64 =>
         for
           r := true, r && (a.has i <=> b.has i)
           i in u64 0 .. m
         else
           r

  # create a string representation of a bitset of the form "{2, 4}"
  #
  public redef as_string String =>
    match highest
      _ nil => "\{}"
      h u64 =>
        for
          first := true, first && !(has i)
          s := "", s + (if (has i) comma + $i else "")
          comma := if (first) "" else ", "
          i in u64 0 .. h
        else
          "\{" + s + "}"


  # an empty bitset
  #
  public type.empty bitset => nil

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