🥮 mooncakes.io

    moonbitstack/moonstl/text does not have a README file

    AhoCorasick

    source
    pub struct AhoCorasick {
      lengths : Array[Int]
      next : Map[(Int, Int), Int]
      children : Array[Array[(Int, Int)]]
      fail : Array[Int]
      out_head : Array[Int]
      out_tail : Array[Int]
      out_next : Array[Int]
      dict : Array[Int]
      built : Bool
    }

    Many patterns matched in one pass: a trie whose nodes also carry failure links, so the text is read once and every occurrence is reported as soon as its last code unit is read. Overlapping matches all appear, including suffixes of longer ones, which the output chain walks without visiting nodes that match nothing. Build is O(total pattern length), search O(n + matches).

    Matches come out in text order of their last code unit, longest first among those that end at the same place. A zero-length pattern is reported at every offset, before the matches ending at that offset.

    test {
      let ac = @text.AhoCorasick::new(["he", "she", "his", "hers"])
      @test.assert_eq(ac.search_all("ushers").to_array(), [(1, 1), (0, 2), (3, 2)])
      assert_true(ac.is_match("ushers"))
      assert_false(ac.is_match("us"))
    }

    AhoCorasick::add

    source
    fn AhoCorasick::add(self : AhoCorasick, pattern : StringView) -> Int

    Add one pattern and return its index, which is what search_all reports. Patterns may be added between searches; the links are rebuilt lazily.

    AhoCorasick::build

    source
    fn AhoCorasick::build(self : AhoCorasick) -> Unit

    Fill in the failure and output links in O(nodes + edges). Calling it twice is harmless; a search calls it when a pattern was added after the last build.

    AhoCorasick::is_match

    source
    fn AhoCorasick::is_match(self : AhoCorasick, text : StringView) -> Bool

    Whether any pattern occurs in text, stopping at the first one found.

    AhoCorasick::new

    source
    fn AhoCorasick::new(patterns : Array[StringView]) -> AhoCorasick

    Build an automaton for patterns, in the order they appear in the array: the index search_all reports is the index in this array.

    AhoCorasick::search_all

    source
    fn AhoCorasick::search_all(self : AhoCorasick, text : StringView) -> Iter[(Int, Int)]

    Every (pattern index, offset) the automaton finds, as a lazy iterator that reads the text once. The index is the one add returned.

    BoyerMoore

    source
    pub struct BoyerMoore {
      pattern : String
      bad : Map[Int, Int]
      good : Array[Int]
    }

    One pattern matched with the Boyer-Moore scan: it compares the pattern from its last character backwards and skips ahead with the bad-character and good-suffix rules, so a mismatch usually costs less than one comparison per text position. Worst case is still O(n), build is O(m + sigma).

    test {
      let bm = @text.BoyerMoore::new("needle")
      assert_eq(bm.search("a needle in a haystack"), Some(2))
      assert_eq(bm.search("haystack"), None)
    }

    BoyerMoore::new

    source
    fn BoyerMoore::new(pattern : StringView) -> BoyerMoore

    Build both shift tables in O(m + sigma), where sigma is the number of distinct code units in the pattern.

    BoyerMoore::search

    source
    fn BoyerMoore::search(self : BoyerMoore, text : StringView) -> Int?

    The offset of the first occurrence, or None. An empty pattern is found at offset 0.

    BoyerMoore::search_all

    source
    fn BoyerMoore::search_all(self : BoyerMoore, text : StringView) -> Iter[Int]

    Every occurrence, overlapping ones included, in ascending order. An empty pattern occurs at every offset from 0 to the text length.

    Kmp

    source
    pub struct Kmp {
      pattern : String
      fail : Array[Int]
    }

    One pattern matched with the Knuth-Morris-Pratt scan: O(n + m) time with a worst-case guarantee, because the failure table never lets the text pointer move backwards. Offsets are UTF-16 code units, the indices String uses.

    test {
      let kmp = @text.Kmp::new("ab")
      assert_eq(kmp.search("cababc"), Some(1))
      assert_eq(kmp.search_all("abab").to_array(), [0, 2])
    }

    Kmp::new

    source
    fn Kmp::new(pattern : StringView) -> Kmp

    Build the failure table of pattern in O(m). The pattern is copied, so the caller's view may be a window into a rope that is edited afterwards.

    Kmp::search

    source
    fn Kmp::search(self : Kmp, text : StringView) -> Int?

    The offset of the first occurrence of the pattern in text, or None. An empty pattern is found at offset 0, as String::find reports it.

    Kmp::search_all

    source
    fn Kmp::search_all(self : Kmp, text : StringView) -> Iter[Int]

    Every occurrence of the pattern, overlapping ones included, in ascending order. An empty pattern occurs at every offset from 0 to the text length.

    Match

    source
    pub(all) struct Match {
      a_start : Int
      b_start : Int
      size : Int
    } derive(Eq, 
    Debug    )

    One block the two runs share: where it starts in each and how long it is.

    Match::equal

    source
    fn Match::equal(Match, Match) -> Bool

    Match::not_equal

    source
    fn Match::not_equal(x : Match, y : Match) -> Bool

    Match::to_repr

    source

    Opcode

    source
    pub(all) enum Opcode {
      Equal(a1~ : Int, a2~ : Int, b1~ : Int, b2~ : Int)
      Replace(a1~ : Int, a2~ : Int, b1~ : Int, b2~ : Int)
      Delete(a1~ : Int, a2~ : Int, b1~ : Int, b2~ : Int)
      Insert(a1~ : Int, a2~ : Int, b1~ : Int, b2~ : Int)
    } derive(Eq, 
    Debug    )

    One step of a diff: what happened to a[i1..i2] and b[j1..j2].

    Opcode::a1

    source
    fn Opcode::a1(self : Opcode) -> Int

    Opcode::a2

    source
    fn Opcode::a2(self : Opcode) -> Int

    Opcode::b1

    source
    fn Opcode::b1(self : Opcode) -> Int

    Opcode::b2

    source
    fn Opcode::b2(self : Opcode) -> Int

    Opcode::equal

    source
    fn Opcode::equal(Opcode, Opcode) -> Bool

    Opcode::not_equal

    source
    fn Opcode::not_equal(x : Opcode, y : Opcode) -> Bool

    Opcode::tag

    source
    fn Opcode::tag(self : Opcode) -> String

    The tag as one word, the way difflib prints it.

    Opcode::to_repr

    source

    Rope

    source
    pub struct Rope {
      chunks : Array[String]
      starts : Array[Int]
    }

    A rope keeps its text in chunks and remembers where each chunk starts, so an offset can be found without flattening the whole document. Offsets are UTF-16 code units, as String counts them, and an edit that would split a surrogate pair is refused.

    test {
      let rope : @text.Rope = @text.Rope::from_string("hello world")
      rope.insert(5, ",")
      assert_true(rope.to_string() == "hello, world")
      rope.edit(start=0, end=5, "goodbye")
      assert_true(rope.to_string() == "goodbye, world")
      assert_true(rope.length() == 14)
    }

    Rope::append

    source
    fn Rope::append(self : Rope, text : StringView) -> Unit

    Rope::char_at

    source
    fn Rope::char_at(self : Rope, offset : Int) -> Char?

    The character at offset, or None when the offset is past the end. An offset in the middle of a surrogate pair yields the pair's low half, because the rope has no way to name half a character.

    Rope::char_length

    source
    fn Rope::char_length(self : Rope) -> Int

    The number of characters rather than code units, which differs when the text carries surrogate pairs.

    Rope::chars

    source
    fn Rope::chars(self : Rope) -> Iter[Char]

    Rope::chunks

    source
    fn Rope::chunks(self : Rope) -> Iter[StringView]

    The chunks as views, which is what a matcher walks when it does not need the text flattened.

    Rope::clear

    source
    fn Rope::clear(self : Rope) -> Unit

    Rope::copy

    source
    fn Rope::copy(self : Rope) -> Rope

    Rope::edit

    source
    fn Rope::edit(self : Rope, start~ : Int, end~ : Int, text : StringView) -> Unit

    Replaces [start, end) with text, which is what an editor does on every keystroke and paste.

    Rope::from_string

    source
    fn Rope::from_string(text : StringView) -> Rope

    Rope::insert

    source
    fn Rope::insert(self : Rope, offset : Int, text : StringView) -> Unit

    Inserts text at offset, appending to the chunk that ends there so that typing at the same place does not shatter the document into one chunk per keystroke.

    Rope::is_empty

    source
    fn Rope::is_empty(self : Rope) -> Bool

    Rope::length

    source
    fn Rope::length(self : Rope) -> Int

    The total length in code units.

    Rope::line_at

    source
    fn Rope::line_at(self : Rope, offset : Int) -> Int

    The line a code unit belongs to.

    Rope::line_count

    source
    fn Rope::line_count(self : Rope) -> Int

    The number of lines, which is one more than the number of line breaks.

    Rope::line_start

    source
    fn Rope::line_start(self : Rope, line : Int) -> Int

    The offset a line starts at.

    Rope::line_starts

    source
    fn Rope::line_starts(self : Rope) -> Array[Int]

    The offsets at which each line starts, plus one past the end.

    Rope::lines

    source
    fn Rope::lines(self : Rope) -> Iter[StringView]

    The lines, without their line breaks.

    Rope::new

    source
    fn Rope::new() -> Rope

    Rope::remove

    source
    fn Rope::remove(self : Rope, start~ : Int, end~ : Int) -> Unit

    Removes [start, end).

    Rope::slice

    source
    fn Rope::slice(self : Rope, start~ : Int, end~ : Int) -> RopeView

    The text between two offsets, as a view that reads the chunks without copying them.

    Rope::split_off

    source
    fn Rope::split_off(self : Rope, offset : Int) -> Rope

    Cuts the rope at offset and returns the tail.

    Rope::to_string

    source
    fn Rope::to_string(self : Rope) -> String

    Rope::write_to

    source
    fn Rope::write_to(self : Rope, out : StringBuilder) -> Unit

    RopeBuilder

    source
    pub struct RopeBuilder {
      chunks : Array[String]
    }

    Builds a rope by appending, which is what a reader or a parser wants: one chunk per append, and one reindex at the end.

    test {
      let builder : @text.RopeBuilder = @text.RopeBuilder::new()
      builder.append("one ")
      builder.append("two")
      let rope = builder.finish()
      assert_true(rope.to_string() == "one two")
    }

    RopeBuilder::append

    source
    fn RopeBuilder::append(self : RopeBuilder, text : StringView) -> Unit

    RopeBuilder::finish

    source
    fn RopeBuilder::finish(self : RopeBuilder) -> Rope

    RopeBuilder::new

    source

    RopeView

    source
    pub struct RopeView {
      rope : Rope
      start : Int
      end : Int
    }

    A window into a rope. It holds its own copy of the rope's chunk list, so an edit to the rope does not move the text under the window.

    test {
      let rope : @text.Rope = @text.Rope::from_string("abcdef")
      let window = rope.slice(start=2, end=4)
      assert_true(window.to_string() == "cd")
      assert_true(window.length() == 2)
    }

    RopeView::char_length

    source
    fn RopeView::char_length(self : RopeView) -> Int

    RopeView::chars

    source
    fn RopeView::chars(self : RopeView) -> Iter[Char]

    RopeView::length

    source
    fn RopeView::length(self : RopeView) -> Int

    RopeView::lines

    source
    fn RopeView::lines(self : RopeView) -> Iter[StringView]

    RopeView::slice

    source
    fn RopeView::slice(self : RopeView, start~ : Int, end~ : Int) -> RopeView

    RopeView::to_rope

    source
    fn RopeView::to_rope(self : RopeView) -> Rope

    The window as a rope of its own.

    RopeView::to_string

    source
    fn RopeView::to_string(self : RopeView) -> String

    SequenceMatcher

    source
    pub struct SequenceMatcher[T] {
      a : Array[T]
      b : Array[T]
      options : SequenceMatcherOptions[T]
      b2j : Map[T, Array[Int]]
      bjunk : Array[Bool]
      bpopular : Map[T, Unit]
    }

    A matcher over two runs: it indexes the second one, finds the longest block the two share, and reports the matching blocks and the steps between them.

    test {
      let left : Array[Char] = "abcd".iter().to_array()
      let right : Array[Char] = "bcde".iter().to_array()
      let matcher : @text.SequenceMatcher[Char] = @text.SequenceMatcher::new(
        left[:],
        right[:],
      )
      @test.assert_eq(matcher.ratio() > 0.7, true)
      let blocks = matcher.get_matching_blocks()
      @test.assert_eq(blocks.length(), 2)
    }

    SequenceMatcher::find_longest_match

    source
    fn[T : Hash + Eq] SequenceMatcher::find_longest_match(self : SequenceMatcher[T], alo : Int, ahi : Int, blo : Int, bhi : Int) -> Match

    The longest block shared by a[alo..ahi] and b[blo..bhi], as (a_start, b_start, size). The search takes each element of the first run that occurs in the second, walks the positions it holds, and extends the match in both directions, so the result is the same block difflib reports.

    SequenceMatcher::get_matching_blocks

    source
    fn[T : Hash + Eq] SequenceMatcher::get_matching_blocks(self : SequenceMatcher[T]) -> Array[Match]

    The matching blocks, in order, ending with the empty block at the end of both runs that difflib appends.

    SequenceMatcher::get_opcodes

    source
    fn[T : Hash + Eq] SequenceMatcher::get_opcodes(self : SequenceMatcher[T]) -> Array[Opcode]

    The steps a diff is made of: one per gap between the matching blocks.

    SequenceMatcher::new

    source
    fn[T : Hash + Eq] SequenceMatcher::new(a : ArrayView[T], b : ArrayView[T], options? : SequenceMatcherOptions[T]) -> SequenceMatcher[T]

    SequenceMatcher::quick_ratio

    source
    fn[T : Hash + Eq] SequenceMatcher::quick_ratio(self : SequenceMatcher[T]) -> Double

    An upper bound on the ratio that costs one pass: the elements of the first run that the second one holds at all.

    SequenceMatcher::ratio

    source
    fn[T : Hash + Eq] SequenceMatcher::ratio(self : SequenceMatcher[T]) -> Double

    Twice the number of matched elements over the total, which is one when the runs are equal and zero when they share nothing.

    SequenceMatcher::real_quick_ratio

    source
    fn[T] SequenceMatcher::real_quick_ratio(self : SequenceMatcher[T]) -> Double

    The cheapest of the three ratios, which only looks at the two lengths.

    SequenceMatcherOptions

    source
    pub(all) struct SequenceMatcherOptions[T] {
      autojunk : Bool
      junk : (T) -> Bool
    }

    What counts as junk, and whether the popular-element heuristic runs.

    autojunk is difflib's defence against a diff of a run with hundreds of identical lines: an element of a run of two hundred or more that appears in more than one percent of it is treated as junk, because matching on it would produce a diff no reader can use.

    SuffixArray

    source
    pub struct SuffixArray {
      text_ : String
      order : Array[Int]
      ranks : Array[Int]
    }

    The suffixes of a text in sorted order, built by doubling: after round k every suffix is ranked by its first 2^k units, and a round ranks the pairs of ranks it already has. Two rounds of comparison sort per doubling give O(n log^2 n), which is what a text of any ordinary size needs.

    test {
      let array : @text.SuffixArray = @text.SuffixArray::new("banana")
      @test.assert_eq(array.search("ana"), [1, 3])
      @test.assert_eq(array.length(), 6)
    }

    SuffixArray::lcp_array

    source
    fn SuffixArray::lcp_array(self : SuffixArray) -> Array[Int]

    The Kasai LCP array: lcp[i] is how many units suffix order[i] shares with suffix order[i - 1]. It costs one pass because a suffix and its neighbour never lose more than one unit of common prefix as the start moves forward.

    SuffixArray::length

    source
    fn SuffixArray::length(self : SuffixArray) -> Int

    SuffixArray::new

    source
    fn SuffixArray::new(text : StringView) -> SuffixArray

    SuffixArray::search

    source
    fn SuffixArray::search(self : SuffixArray, pattern : StringView) -> Array[Int]

    Every occurrence of pattern, in increasing order. The suffixes that start with the pattern are contiguous in the sorted order, so the search is two binary searches and a scan.

    SuffixArray::text

    source
    fn SuffixArray::text(self : SuffixArray) -> String

    SuffixArray::to_array

    source
    fn SuffixArray::to_array(self : SuffixArray) -> Array[Int]

    The sorted starting offsets of the suffixes.

    SuffixAutomaton

    source
    pub struct SuffixAutomaton {
      text_ : String
      next : Map[(Int, Int), Int]
      link : Array[Int]
      length : Array[Int]
      occurrences : Array[Int]
      last : Int
    }

    A suffix automaton: every substring of the text is a path from the start state, and each state remembers how many times the substring it stands for occurs. The build is one pass and the state count is at most twice the text length, which is what makes "how often does this appear" a lookup.

    test {
      let automaton : @text.SuffixAutomaton = @text.SuffixAutomaton::new("banana")
      @test.assert_eq(automaton.contains("ana"), true)
      @test.assert_eq(automaton.count_occurrences("ana"), 2)
      @test.assert_eq(automaton.contains("band"), false)
    }

    SuffixAutomaton::contains

    source
    fn SuffixAutomaton::contains(self : SuffixAutomaton, pattern : StringView) -> Bool

    SuffixAutomaton::count_occurrences

    source
    fn SuffixAutomaton::count_occurrences(self : SuffixAutomaton, pattern : StringView) -> Int

    SuffixAutomaton::length

    source
    fn SuffixAutomaton::length(self : SuffixAutomaton) -> Int

    SuffixAutomaton::longest_common_substring

    source
    fn SuffixAutomaton::longest_common_substring(self : SuffixAutomaton, other : StringView) -> (Int, Int)

    The longest substring of other that also occurs in this automaton, as a half-open range in other. One pass over other, following the automaton and falling back along the suffix links when a step is missing.

    SuffixAutomaton::new

    source
    fn SuffixAutomaton::new(text : StringView) -> SuffixAutomaton

    SuffixAutomaton::text

    source
    fn SuffixAutomaton::text(self : SuffixAutomaton) -> String

    context_diff

    source
    fn context_diff(a : StringView, b : StringView, fromfile? : StringView, tofile? : StringView, n? : Int) -> String

    A context diff: the same idea as the unified one, with the older *** and --- hunk headers and the ! marker for a replaced line.

    get_close_matches

    source
    fn get_close_matches(word : StringView, possibilities : ArrayView[StringView], n? : Int, cutoff? : Double) -> Array[StringView]

    The n strings of possibilities closest to word, each scoring at least cutoff with the two runs read as character sequences.

    is_character_junk

    source
    fn is_character_junk(ch : Char) -> Bool

    Whether a character is junk in a character diff: whitespace, which difflib treats as noise when it diffs text rather than lines.

    is_line_junk

    source
    fn is_line_junk(line : StringView) -> Bool

    Whether a line carries nothing a reader would miss: a blank line or a line that is only a comment marker, which is difflib's IS_LINE_JUNK.

    lines_of

    source
    fn lines_of(text : StringView) -> Array[StringView]

    The lines of a text, without their breaks, which is what the diff formats take.

    longest_palindrome

    source
    fn longest_palindrome(text : StringView) -> (Int, Int)

    The longest palindromic substring, as a half-open range. Manacher's scan keeps the palindrome around each centre, so the whole text costs one pass.

    test {
      @test.assert_eq(@text.longest_palindrome("forgeeksskeegfor"), (3, 13))
      @test.assert_eq(@text.longest_palindrome("abc"), (0, 1))
    }

    ndiff

    source
    fn ndiff(a : StringView, b : StringView) -> String

    The ndiff form: every line of either file, marked with - , + or .

    restore

    source
    fn restore(diff : StringView) -> String

    The lines of a diff with their markers removed, which is how a diff is turned back into the text it describes.

    sequence_matcher_options

    source
    fn[T] sequence_matcher_options() -> SequenceMatcherOptions[T]

    The preset: the popular-element heuristic on, and nothing treated as junk.

    unified_diff

    source
    fn unified_diff(a : StringView, b : StringView, fromfile? : StringView, tofile? : StringView, n? : Int) -> String

    A unified diff: the two file headers, then each hunk with n lines of context, the way diff -u and difflib's unified_diff write it.

    z_function

    source
    fn z_function(text : StringView) -> Array[Int]

    The Z array of text: z[i] is the length of the longest run starting at i that is also a prefix of the text. It is the linear-time answer to "where does this prefix repeat", and it is what makes the suffix array's first ranking pass unnecessary.

    test {
      @test.assert_eq(@text.z_function("aabxaab"), [7, 1, 0, 0, 3, 1, 0])
    }

    Source Files

    Powered by MoonBit

    Site sourceReport issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io