container/searchable_sequence.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 searchable_sequence
#
# Author: Fridtjof Siebert (siebert@tokiwa.software)
#
# -----------------------------------------------------------------------
# searchable_sequence -- a Sequence whose elements inherit from property.equatable
#
#
public searchable_sequence(public A type : property.equatable,
from Sequence A ) : Sequence A,
property.equatable
is
# create a list from this searchable_sequence.
#
public redef as_list => from.as_list
# is this sequence known to be finite? For infinite sequences, features like
# count diverge.
#
public redef finite => from.finite
# does this sequence start with l?
#
public starts_with (l Sequence A) bool =>
match l.as_list
nil => true
c2 Cons =>
match from.as_list
nil => false
c1 Cons => c1.head = c2.head && (searchable_sequence c1.tail).starts_with c2.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 A) => find [x]
# get the index of l within this list or nil if it does not exist
#
public find (l Sequence A) option i32 =>
if starts_with l
0
else
match from.as_list
nil => nil
c1 Cons => ((searchable_sequence c1.tail).find l) >>= n -> n + 1
# replace all occurrences of old by new
#
public replace (old, new Sequence A) =>
nil_list list A := nil
replace old new nil_list from nil
# replace the first n occurrences of old by new
#
public replace (old, new Sequence A, n u64) =>
nil_list list A := nil
replace old new nil_list from n
# tail recursive helper for the replace features
#
private replace (old, new,
already_replaced, # the head part with old already replaced by new
to_be_replaced Sequence A, # the tail that still needs to be searched for old
limit option u64) list A
=>
match (searchable_sequence to_be_replaced).find old
nil => already_replaced ++ to_be_replaced
n i32 =>
# NYI: #637: perhaps make it possible to do
# if limit = option 0
# here.
if (limit.map_to_option (v -> v = (u64 0))).get false
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 A) i32 =>
tails
.filter (t -> (searchable_sequence t).starts_with l)
.count
# get the number of non-overlapping matches of l within this
#
public count_matches (l Sequence A) i32 =>
match from.as_list
nil => 0
c1 Cons => (if (starts_with l) 1 + (searchable_sequence (drop l.count)).count_matches l
else (searchable_sequence 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 list include
# the separator
#
# helper feature which unifies the code of the different split features in one
#
module split0(s Sequence A, limit option u32, split_after bool) list (Sequence A)
pre
debug: !s.is_empty
debug: match limit
nil => true
n u32 => n > (u32 0)
=>
match (find s)
nil => from : nil
idx i32 =>
ref : Cons (Sequence A) (list (Sequence A))
head Sequence A := from.take (if split_after then idx + s.count else idx)
tail =>
rest := from.drop (idx + s.count)
srest := searchable_sequence rest
match limit
nil => srest.split0 s nil split_after
n u32 =>
if n > u32 1
srest.split0 s (n - 1) split_after
else
res Sequence A := rest;
res : nil
# equality check implementation for inherited property.equatable
#
public fixed type.equality(a, b container.searchable_sequence A) bool =>
aa := a.as_array
ba := b.as_array
aa.count = ba.count
&& ((0..(a.count - 1)) ∀ (i -> aa[i] = ba[i]))
last changed: 2024-03-07