Sequence/equatable.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
#
# -----------------------------------------------------------------------


# does this sequence start with l?
#
public starts_with(l Sequence T) bool
  pre
    T : property.equatable
=>
  match l.as_list
    nil     => true
    c1 Cons =>
      match as_list
        nil     => false
        c2 Cons => c2.head = c1.head && c2.tail.starts_with c1.tail # tail recursion


# determine the index of element x within this list.  0 if x is at the
# head of the list, 1 if it comes directly after head, etc. nil if x is
# not in the list.
#
public index_of(x T) option i32
  pre
    T : property.equatable
=>
  find [x]


# does the Sequence contain element x?
#
public contains(x T) bool
  pre
    T : property.equatable
=>
  (find [x]).exists


# get the index of pattern within this Sequence or nil if it does not exist
#
# uses the Knuth-Morris-Pratt algorithm
# port of racket code from this paper:
# https://www.cambridge.org/core/services/aop-cambridge-core/content/view/8EFA77D663D585B68630E372BCE1EBA4/S0956796824000017a.pdf/knuth-morris-pratt-illustrated.pdf
#
# worst-case performance: O( seq_length ) + O( pattern_length )
# worst-case space complexity: O( pattern_length )
#
public find(pattern Sequence T) option i32
  pre
    T : property.equatable
=>

  find_lm ! ()->

    p := pattern.as_array_backed
    ab := as_array_backed

    make(t Sequence T, r option (Node T)) =>
      n option (Node T) =>
        if t.is_empty then nil else make (t.drop 1) (step r t[0])
      r_star =>
        if t.is_empty
          r
        else if is_match r t[0]
          r.or_panic.rest
        else
          r
      Node t (once find_lm (option (Node T)) ()->n) r_star

    init := make p nil

    step(acc option (Node T), x T) =>
      match acc
        nil => init
        n Node => if is_match acc x then n.next.or_panic else step n.rest x

    is_done (option (Node T))->bool => (acc)->
      match acc
        nil => false
        n Node => n.top.is_empty

    is_match(acc option (Node T), x T) =>
      match acc
        nil => false
        n Node => !n.top.is_empty && n.top[0] = x

    fold_until(acc option (Node T), i i32) option i32 =>
      if is_done acc
        ab.count - (ab.count-i) - p.count
      else if i >= ab.count
        nil
      else
        acc_star := step acc ab[i]
        fold_until acc_star i+1

    fold_until init 0



# replace all occurrences of old by new
#
public replace(old, new Sequence T) Sequence T
  pre
    T : property.equatable
=>
  replace old.as_array_backed new.as_array_backed [] as_array_backed nil


# replace the first n occurrences of old by new
#
public replace (old, new Sequence T, n u64) Sequence T
  pre
    T : property.equatable
=>
  replace old.as_array_backed new.as_array_backed [] as_array_backed n


# tail recursive helper for the replace features
#
replace(old, new,
        already_replaced,          # the head part with old already replaced by new
        to_be_replaced Sequence T, # the tail that still needs to be searched for old
        limit option u64
        )
  pre
    T : property.equatable
    debug: old.is_array_backed
    debug: new.is_array_backed
    debug: to_be_replaced.is_array_backed
=>
  match to_be_replaced.find old
    nil   => already_replaced ++ to_be_replaced
    n i32 =>
      if limit = 0
        already_replaced ++ to_be_replaced
      else
        a := already_replaced ++ (to_be_replaced.take n) ++ new
        b := to_be_replaced.drop (n + old.count)
        replace old new a b (limit >>= (l -> l - 1))


# get the number of matches of l
#
public count_matches_overlapping(l Sequence T) i32
  pre
    T : property.equatable
=>
  tails
    .filter (.starts_with l)
    .count


# get the number of non-overlapping matches of l within this
#
public count_matches(l Sequence T) i32
  pre
    T : property.equatable
=>
  match as_list
    nil     => 0
    c1 Cons => if starts_with l then 1 + (drop l.count).count_matches l
                                else            c1.tail.count_matches l


# split sequence at s, if there is no limit, otherwise if limit is an integer n,
# for at most n occurrences of s
#
# if split_after is true, all but the last element of the resulting Sequence include
# the separator
#
# helper feature which unifies the code of the different split features in one
#
module split0(s Sequence T, limit option u32, split_after bool) Sequence (Sequence T)
  pre
    T : property.equatable
    debug: !s.is_empty
    debug: match limit
            nil => true
            n u32 => n > 0
    debug: is_array_backed
    debug: s.is_array_backed
  =>
    match find s
      nil     =>
        [Sequence.this]
      i i32 =>
        head Sequence T => take (if split_after then i + s.count else i)

        tail Sequence (Sequence T) =>

          rest => drop i+s.count

          match limit
            nil => rest.split0 s nil split_after
            n u32 =>
              if n > 1
                rest.split0 s (n - 1) split_after
              else
                [rest]

        [head] ++ tail


# filter out consecutive duplicate elements.
#
# Keep the order of elements unchanged.
#
# ex.
#
#     [1,2,2,3,2,2,2,4].dedup = [1,2,3,2,4]
#
public dedup Sequence T
  pre
    T : property.equatable
  =>
    as_list.dedup_list


# filter out consecutive duplicate elements using the
# given relation.
#
# Keep the order of elements unchanged.
#
# ex.
#
#     [4,2,2,6,2,1,2,4].dedup (a,b -> a%2=b%2) = [4,1,2]
#     [4,2,2,6,2,1,2,4].dedup (<=) = [4,2,1]
#
public dedup(by (T,T) -> bool) Sequence T
  pre
    T : property.equatable
  =>
    as_list.dedup_list by