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 i64
  pre
    T : property.equatable
=>
  find [x]


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


# 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 i64
  pre
    T : property.equatable
=>

  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 (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 i64) option i64 =>
    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


# helper features for knuth morris pratt algorithm
#
universe.Node(T type, top Sequence T, next once (option (Node T)), rest option (Node T)) ref is


# 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 i64 =>
      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) i64
  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) i64
  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
=>

  accum_result (split_of Sequence (Sequence T), rest Sequence T) is

  l := limit.or_else u32.max
  for
    idx option i64 := i64.min, ar.rest.find s
    ar := accum_result (Sequence (Sequence T) .empty) Sequence.this, {
      match idx
        nil =>
          accum_result ar.split_of ar.rest
        i i64 =>
          accum_result
            (ar.split_of ++ [ar.rest.take (if split_after then i + s.count else i)])
            (ar.rest.drop i+s.count)
    }
    c := u32 0, c+1
  while idx.ok && c<l
  else
    ar.split_of ++ [ar.rest]


# 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