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]))