Fuzion Logo
flang.dev — The Fuzion Language Portal
JavaScript seems to be disabled. Functionality is limited.

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

# searchablelist -- a list whose elements inherit from hasEquals
#
# In contrast to searchableSequence, this uses choice type 'list' and not ref
# type 'Sequence', so it is more efficient.
#
#
searchablelist(A (hasEquals A).type, from list A) : Sequence A
/* : list A -- NYI: we might allow inherting from a choice to get a choice
                    with more restrictions on the type arguments

  also, if we could add a compile time check for the type of the actual generic
  such as

    pre
      A : hasEquals

  Then, the inner features of searchableList could move to list.fz.

*/

is

  # create a list from this searchablelist.
  #
  redef asList => from


  # does this list start with l?
  #
  startsWith (l list A) bool is
    match l
      nil    => true
      c2 Cons =>
        match from
          nil     => false
          c1 Cons => c1.head = c2.head && (searchablelist c1.tail).startsWith c2.tail # tail recursion


  # get the index of l within this list or nil if it does not exist
  #
  find (l list A) option i32 is
    if startsWith l
      0
    else
      match from
        nil     => nil
        c1 Cons => ((searchablelist c1.tail).find l) >>= n -> n + 1


  # replace all occurances of f by r
  #
  replace (f, r list A) =>

    # tail recursive helper
    #
    repl (h,       # the head part of from with f already replaced by r
          t list A # the tail that still needs to be searched for f
         ) list A
    is
      match (searchablelist t).find f
        nil   => h ++ t
        n i32 => repl h++(t.take n)++r (t.drop n+f.count)

    repl nil from


  # get the number of matches of l
  #
  countMatchesOverlapping (l list A) i32 is
    (tails & (t -> (searchablelist t).startsWith l)).count


  # get the number of non-overlapping matches of l within this
  #
  countMatches (l list A) i32 is
    match from
      nil     => 0
      c1 Cons => (if (startsWith l) 1 + (searchablelist (drop l.count)).countMatches l
                  else                  (searchablelist c1.tail       ).countMatches l)