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


# A `from..through` interval with a given `step`.
#
# This is a `Set T` and a `Sequence T` created by repeatedly adding `step` to `from`.
# Stops before passing `through` (exceeding it for `step > 0`, falling below for `step < 0`).
#
# Empty if `step` points away from `through`:
#     interval 1 2 -1     # empty: steps down, but through is up
#     interval 2 1 1      # empty: steps up, but through is down
#
#     interval 1 7 3      # 1, 4, 7
#     interval 1 8 3      # 1, 4, 7  (10 would exceed through)
#     interval 7 1 -3     # 7, 4, 1
#
# A zero `step` is only allowed when `from = through`; such an interval
# contains the single element `from`:
#     interval 5 5 0      # 5
#
# If `through` is `nil`, the interval is unbounded and limited only by type `T` range.
#
# This is not an interval in the mathematical sense, but rather a representation
# of an arithmetic progression.
#
public interval(T type : integer,

                # Start value. Included unless the interval is empty.
                public from T,

                # Inclusive bound. Included only if reachable via `from + n * step`.
                # `nil` means unbounded.
                public through option T,

                # Step size. Positive increments; negative decrements.
                public step T)
  : container.Set T

pre
  debug: ((step.sign = 0): through = from)  # step cannot be zero unless from=through
is


  # Creates a new interval with the `step` multiplied by `step_factor`.
  # `from` and `through` remain unchanged.
  #
  # Since it returns an interval, `infix :` can be chained (factors multiply):
  #     2..10        # {2,4,6,8,10} (implicit step 1 -> new step 2)
  #     (2..12:2):3  # {2,8}        (step becomes 1 * 2 * 3 = 6)
  #
  # A negative `step_factor` reverses the direction. It usually makes the
  # interval empty because `from` and `through` do not change:
  #     2..10: -2     # empty: step points away from `through`
  #
  public infix : (step_factor T) interval T
  pre
    debug: ((step_factor.sign = 0): through=from) # `step_factor` cannot be zero unless `from == through`, because a zero step would never reach `through`.
    safety: (step *? step_factor).ok
  =>
    interval from through step*step_factor


  # the values of this interval as a list, in order
  #
  # Returns an empty list if `step` moves in the opposite direction of `through`.
  #
  # For `step = 0` the result is the single element `from`: the
  # precondition guarantees `from = through` in that case.
  #
  # Otherwise starts at `from` and advances by `step` until `through`
  # is passed or `T` overflows.
  #
  public redef as_list list T =>
    if (through ? nil    => false
                | thru T => from != thru && step.sign = (from ? thru).sign) then
      nil
    else
      tail => if step.sign = 0
                nil
              else
                (from+?step ? next T => (interval next through step).as_list
                            | nil    => nil)
      list T .of from tail finite


  # get the number of elements in this interval
  #
  # Complexity: O(1).
  #
  #
  public size T
  pre
   debug: through.ok   # unbounded intervals have no size, use `size_option`
  =>
    thru := through.or_panic
    if from = thru then
      1
    else if step.sign = (from ? thru).sign then
      0
    else
      (thru - from) / step + 1


  # get the first element of this interval
  #
  # Complexity: O(1)
  #
  public redef first option T
  =>
    match through
      thru T =>
        if from = thru then
          from
        else if step.sign = (from ? thru).sign then
          nil
        else
          from
      nil =>
        from


  # the last element of this interval, `nil` if there is none
  #
  # There is no last element if the interval is empty or unbounded.
  #
  # Complexity: O(1)
  #
  public redef last option T
  =>
    match through
      thru T =>
        if from = thru then
          from
        else if step.sign = (from ? thru).sign then
          nil
        else
          thru-(thru-from)%step
      nil =>
        nil


  # the n-th element of this interval, `nil` if out of range
  #
  # For `step = 0` only index 0 exists: every index would otherwise
  # yield `from`.
  #
  # Complexity: O(1), which relies on the O(1) `contains` redefined in
  # this feature.
  #
  public redef nth(n i64) option T
  =>
    if n < 0 || (n > 0 && step.sign = 0) then
      nil
    else
      (step *? T.from_u32 n.as_u32)
        >>= (off -> from +? off)
        >>= (e   -> if contains e then e
                    else nil)


  # number of elements as `i64`, `nil` if unbounded
  # or if size does not fit into an i64.
  #
  # Enables the inherited `Set.finite` and `Set.type.equality`, which are
  # built on `size_option` and panic without it.
  #
  public redef size_option option i64
  =>
    if through.ok && size.fits_in_i64
      size.as_i64
    else
      nil


  # index of `e` in this interval, `nil` if not contained
  #
  # Inverse of `nth`: for a valid index `i`, `index_of` of the `i`-th
  # element returns `i`.
  #
  # Complexity: O(1), unlike the inherited O(n) search. This depends on
  # `contains` being redefined in this feature to be O(1) as well.
  #
  public redef index_of(e T) option i64
  =>
    if !contains e then
      nil
    else if step.sign = 0 then
      0 # single-element interval: avoid division by zero
    else
      ((e - from) / step).as_i64


  # two intervals are equal if they contain the same elements,
  # regardless of how `through` and `step` are stated:
  # `interval 1 8 3 = interval 1 7 3` and `2..10:2 = interval 2 10 2`.
  #
  # Complexity: O(1)
  #
  # NOTE: two intervals with the same elements in opposite order are not
  # equal, e.g. `1..10 ? 10..1:-1` ? an `interval` compares as an ordered
  # sequence, not as an unordered set.
  #
  public fixed redef type.equality(a, b interval T) bool
  =>
    if a.is_empty || b.is_empty then
      a.is_empty = b.is_empty
    else
      a.from = b.from
        && a.last = b.last
        && (a.from = a.last || a.step = b.step)


  # reverse the order of the elements in this interval
  #
  # Complexity: O(1)
  #
  public reverse_interval interval T
  pre
    safety: T.zero -! step  # We must be able to negate `step`, so `T` must be signed
    debug: through.ok && first.ok
  =>
    match last
      l T =>
        interval l first -step
      nil =>
        interval T 1 T.zero 1  # empty interval


  # does this interval contain the given value?
  #
  # `e` must lie within the bounds and be reachable from `from` by whole steps
  #
  public redef contains(e T) bool =>
    if      step.sign > 0 then from <= e <= through.or_else e && (e - from) %  step = 0
    else if step.sign < 0 then from >= e >= through.or_else e && (e - from) % -step = 0
    else                       from =  e


  # string representation of this interval, e.g., "1..10:2"
  #
  # Prints `??` for unbounded intervals; omits step if it equals 1.
  #
  public redef as_string String =>
    thru := through.bind ($)
                   .or_else ()->if step.sign < 0 then "-?" else "?"
    "$from..$thru$(if step = T.one then "" else ":$step")"


  # is this sequence known to be finite?  For infinite sequences, features like
  # count diverge.
  #
  public redef finite trit =>
    through.ok.as_trit