🥮 mooncakes.io

rle

Generic run-length encoded sequence with O(log n) position lookup

rle
run-length-encoding
data-structure
moon add dowdiness/rle@0.2.3
Download zip
Author
Version
0.2.3
License
Apache-2.0
Repository
Last updated
last month
Downloads
40K

Dependencies

README

#rle

Generic run-length encoded sequence for MoonBit with O(log n) position lookup.

#Quick Start

#Working with Strings

Strings implement all required traits out of the box:

///|
test {
  // Create from a string
  let rle = @rle.Rle::from_string("hello world")

  // Length and lookup
  inspect(rle.span(), content="11")
  match rle.find(6) {
    Some(pos) => {
      inspect(pos.run, content="0")
      inspect(pos.offset, content="6")
    }
    None => fail("find should succeed")
  }
}

Append merges automatically (strings always merge into one run):

///|
test {
  let rle : @rle.Rle[String] = @rle.Rle::Rle()
  let _ = rle.append("hello")
  let _ = rle.append(" world")
  inspect(rle.length(), content="1")
  inspect(rle.to_string(), content="hello world")
}

Split at any position:

///|
test {
  let rle = @rle.Rle::from_string("hello world")
  let (left, right) = rle.split(5).unwrap()
  inspect(left.to_string(), content="hello")
  inspect(right.to_string(), content=" world")
}

Range iteration returns lazy slices without copying:

///|
test {
  let rle = @rle.Rle::from_string("hello world")
  let slices = rle.range(start=1, end=4).unwrap().collect()
  inspect(slices.length(), content="1")
  let s = slices[0]
  match @rle.Sliceable::slice(s.value, start=s.start, end=s.end) {
    Ok(value) => inspect(value, content="ell")
    Err(_) => fail("slice should succeed")
  }
}

#Batch Construction

Build from an array in a single O(n) pass. Empty elements are skipped and adjacent ones merged:

///|
test {
  let rle = @rle.Rle::from_array(["a", "", "b", "", "c"])
  inspect(rle.length(), content="1")
  inspect(rle.to_string(), content="abc")
}

#Editing Operations

Insert, delete, and splice at any position. These produce new Rle values:

///|
test {
  // Insert at position
  let rle = @rle.Rle::from_string("helo")
  let elem = @rle.Rle::from_string("l")
  let result = rle.insert(2, elem).unwrap()
  inspect(result.to_string(), content="hello")
}

///|
test {
  // Delete a range
  let rle = @rle.Rle::from_string("hello world")
  let result = rle.delete(start=5, end=6).unwrap()
  inspect(result.to_string(), content="helloworld")
}

///|
test {
  // Splice: replace a range with new content
  let rle = @rle.Rle::from_string("hello world")
  let replacement = @rle.Rle::from_string("beautiful ")
  let result = rle.splice(start=6, end=11, replacement).unwrap()
  inspect(result.to_string(), content="hello beautiful ")
}

#Cursor for Sequential Traversal

Cursors track position and detect mutations:

///|
test {
  let rle = @rle.Rle::from_string("abcdef")
  let cursor = rle.cursor()

  inspect(cursor.advance(3), content="true")
  match cursor.position() {
    Some(position) => inspect(position, content="3")
    None => fail("cursor position should be available")
  }
  match cursor.current_item() {
    Some(item) => inspect(item, content="abcdef")
    None => fail("cursor item should be available")
  }

  // seek() uses binary search — O(log n)
  inspect(cursor.seek(1), content="true")
  match cursor.position() {
    Some(position) => inspect(position, content="1")
    None => fail("cursor position should be available")
  }
}

Mutation invalidates the cursor:

///|
test {
  let rle = @rle.Rle::from_string("abcdef")
  let cursor = rle.cursor()
  let _ = cursor.advance(3)

  let _ = rle.append("ghi")
  inspect(cursor.is_stale(), content="true")
  inspect(cursor.next() is None, content="true")
}

#Concatenation and Extension

///|
test {
  // Non-mutating concat — returns a new Rle
  let a = @rle.Rle::from_string("hello")
  let b = @rle.Rle::from_string(" world")
  let c = a.concat(b)
  inspect(c.to_string(), content="hello world")
}

///|
test {
  // In-place extend — mutates the receiver
  let rle = @rle.Rle::from_string("hello")
  rle.extend(@rle.Rle::from_string(" world"))
  inspect(rle.to_string(), content="hello world")
}

#Position Lookup

find returns the run index and offset within that run:

///|
test {
  let rle = @rle.Rle::from_string("hello")
  match rle.find(0) {
    Some(pos) => {
      inspect(pos.run, content="0")
      inspect(pos.offset, content="0")
    }
    None => fail("find should succeed")
  }
  match rle.find(4) {
    Some(pos) => {
      inspect(pos.run, content="0")
      inspect(pos.offset, content="4")
    }
    None => fail("find should succeed")
  }
  inspect(rle.find(5) is None, content="true")
  inspect(rle.find(-1) is None, content="true")
}

value_at returns the full run containing a position:

///|
test {
  let rle = @rle.Rle::from_string("hello")
  match rle.value_at(2) {
    Ok(value) => inspect(value, content="hello")
    Err(_) => fail("value_at should succeed")
  }
  inspect(rle.value_at(5) is Err(_), content="true")
}

#Dual-Length Semantics

span() and logical_length() are equal for strings:

///|
test {
  let rle = @rle.Rle::from_string("hello")
  inspect(rle.span(), content="5")
  inspect(rle.logical_length(), content="5")
  inspect(rle.span() == rle.logical_length(), content="true")
}

#Lazy Prefix Sum Caching

Prefix sums are rebuilt lazily — mutations invalidate the cache, queries rebuild it:

///|
test {
  let rle = @rle.Rle::from_string("hello")
  let _ = rle.span() // builds cache
  let _ = rle.append(" world") // invalidates cache
  // next query rebuilds automatically
  inspect(rle.span(), content="11")
}

#Cursor Version Tracking

The version counter increments on every mutation:

///|
test {
  let rle : @rle.Rle[String] = @rle.Rle::Rle()
  inspect(rle.get_version(), content="0")
  let _ = rle.append("a")
  inspect(rle.get_version(), content="1")
  let _ = rle.append("b")
  inspect(rle.get_version(), content="2")
  rle.clear()
  inspect(rle.get_version(), content="3")
}

#Error Handling

Operations return Result[T, RleError] with user-friendly messages:

///|
test {
  let rle = @rle.Rle::from_string("hello")
  match rle.split(100) {
    Ok(_) => fail("should fail")
    Err(e) =>
      inspect(
        e.message(),
        content="Position 100 is outside the document (length: 5)",
      )
  }
}

Range validation provides specific reasons:

///|
test {
  let rle = @rle.Rle::from_string("hello")
  match rle.range(start=-1, end=3) {
    Ok(_) => fail("should fail")
    Err(e) =>
      inspect(e.message(), content="Range start (-1) cannot be negative")
  }
}

///|
test {
  let rle = @rle.Rle::from_string("hello")
  match rle.range(start=0, end=10) {
    Ok(_) => fail("should fail")
    Err(e) =>
      inspect(e.message(), content="Range end (10) exceeds document length (5)")
  }
}

Appending an empty string returns an error:

///|
test {
  let rle : @rle.Rle[String] = @rle.Rle::Rle()
  inspect(rle.append("") is Err(_), content="true")
}

#UTF-16 String Indices

All string indices are in UTF-16 code units. Emoji like "😀" occupy 2 code units:

///|
test {
  let rle = @rle.Rle::from_string("A😀B")
  inspect(rle.span(), content="4") // A(1) + 😀(2) + B(1)
}

Splitting inside a surrogate pair returns an error:

///|
test {
  let rle = @rle.Rle::from_string("😀")
  inspect(rle.span(), content="2")
  match rle.split(1) {
    Ok(_) => fail("should fail on invalid boundary")
    Err(e) =>
      inspect(e.message(), content="Slice indices are not on valid boundaries")
  }
}

Valid emoji boundaries work correctly:

///|
test {
  let rle = @rle.Rle::from_string("A😀B")
  // Position 3 is after the emoji, before B — valid boundary
  match rle.range(start=0, end=3) {
    Ok(iter) => {
      let slices = iter.collect()
      inspect(slices.length(), content="1")
    }
    Err(_) => fail("range should succeed")
  }
}

#Unicode Support

BMP characters (CJK) work as expected:

///|
test {
  let rle = @rle.Rle::from_string("こんにちは")
  inspect(rle.span(), content="5")
  match rle.find(2) {
    Some(pos) => {
      inspect(pos.run, content="0")
      inspect(pos.offset, content="2")
    }
    None => fail("find should succeed")
  }
  match rle.split(1) {
    Ok((left, right)) => {
      inspect(left.to_string(), content="こ")
      inspect(right.to_string(), content="んにちは")
    }
    Err(_) => fail("split should work with unicode")
  }
}

#Empty Ranges and Edge Cases

Empty range (start == end) is valid and returns empty iterator:

///|
test {
  let rle = @rle.Rle::from_string("hello")
  match rle.range(start=2, end=2) {
    Ok(iter) => inspect(iter.collect().length(), content="0")
    Err(_) => fail("empty range should succeed")
  }
}

Delete empty range is a no-op:

///|
test {
  let rle = @rle.Rle::from_string("hello")
  match rle.delete(start=2, end=2) {
    Ok(result) => inspect(result.to_string(), content="hello")
    Err(_) => fail("delete empty range should succeed")
  }
}

Split at boundaries:

///|
test {
  let rle = @rle.Rle::from_string("hello")
  // Split at start
  let (left, right) = rle.split(0).unwrap()
  inspect(left.to_string(), content="")
  inspect(right.to_string(), content="hello")
}

///|
test {
  let rle = @rle.Rle::from_string("hello")
  // Split at end
  let (left, right) = rle.split(5).unwrap()
  inspect(left.to_string(), content="hello")
  inspect(right.to_string(), content="")
}

#Clamped Range

range_clamped auto-clamps bounds instead of returning errors:

///|
test {
  let rle = @rle.Rle::from_string("hello")
  let slices = rle.range_clamped(start=-5, end=100).collect()
  inspect(slices.length(), content="1")
  let s = slices[0]
  match @rle.Sliceable::slice(s.value, start=s.start, end=s.end) {
    Ok(value) => inspect(value, content="hello")
    Err(_) => fail("slice should succeed")
  }
}

#
MayStale

source
using @moonbitlang/core/builtin { type Option as MayStale }

Result type for cursor operations that may become stale. Some(value) when cursor is valid, None when stale due to Rle mutations. This is a type alias for T? — its purpose is documentation, not runtime overhead. When you see MayStale[Int] as a return type, None means "the cursor is stale" rather than "value not found."

#
Addressable

source
pub(open) trait Addressable {
  fn address(Self, global_start : Int, offset : Int) -> Int
}

Addressable — map a position within a run to a domain integer value.

This trait enables the generic iter_units algorithm: given compressed runs, expand them back into individual integers. For each unit offset within a run, address returns the corresponding domain value.

Parameters

  • global_start: the run's start position in the RLE, derived from prefix sums (the cumulative span of all preceding runs). The library computes this automatically — you don't need to store or track it.

  • offset: 0-based index within the current run (0 <= offset < span).

Index-Carrying vs Index-Free

Your type decides which parameter to use:

  • Index-carrying (e.g., LvRange): self.start + offset — the run knows its own start, so global_start is ignored.

  • Index-free (e.g., DenseRun): global_start + offset — the run doesn't store a start, so positions are derived from prefix sums.

Both approaches produce correct results. The library doesn't know or care which one your type uses — it just calls address and gets an Int back.

#
FromRange

source
pub(open) trait FromRange {
  fn from_range(start : Int, count : Int) -> Self
}

FromRange — construct a run value from an integer range [start, start+count).

This trait enables the generic from_sorted_ints algorithm: given sorted integers like [0, 1, 2, 5, 6, 7], the library groups consecutive values into ranges ([0..3) and [5..8)) and calls from_range to build each run.

The library does not prescribe what your run type looks like — it only needs to know how to construct one from a start value and a count.

Index-Carrying vs Index-Free

Your type decides whether to store the start value or discard it:

  • Index-carrying (e.g., LvRange { start, count }): stores start as a domain identifier. The run knows its own position in the value space. Use this when values have gaps (e.g., Lamport version ranges in a CRDT).

  • Index-free (e.g., DenseRun { count }): discards start — the library's prefix sums will compute positions when needed. Use this when values are dense from zero (no gaps).

This follows the algorithm-by-trait pattern: the library provides the algorithm (from_sorted_ints), your type provides the behavior (from_range). Just as Compare lets you write a generic sort without knowing the element type, FromRange lets the library compress sorted integers without knowing your run type.

#
HasLength

source
pub(open) trait HasLength {
  fn length(Self) -> Int
  fn is_empty(Self) -> Bool = _
}

HasLength — basic size of a value (number of runs for containers, character count for strings, etc.).

Provides is_empty() with a default implementation (length() == 0).
impl HasLength for String

#
Mergeable

source
pub(open) trait Mergeable {
  fn can_merge(Self, Self) -> Bool
  fn merge(Self, Self) -> Self
}

Mergeable — determines when two adjacent runs compress into one.

The RLE structure stores a sequence as an array of "runs." Whenever two adjacent runs satisfy can_merge, they are automatically combined via merge. This is the core compression mechanism.

Contract

Implementors must ensure:

  1. merge is associative: merge(merge(a, b), c) == merge(a, merge(b, c)). The library's stack-based batch merge processes elements left-to-right and cascades merges backward. Without associativity, different insertion orders could produce different results.

  2. merge preserves content: the merged run must represent the same logical sequence as the two original runs placed side by side.

  3. can_merge is consistent with merge: if can_merge(a, b) returns true, then merge(a, b) must produce a valid element with span(merge(a,b)) == span(a) + span(b).

Examples

  • Strings: can_merge always returns true; merge concatenates.
  • Authored text: can_merge checks a.author == b.author.
  • Pixel runs: can_merge checks a.color == b.color; merge sums counts.
impl Mergeable for String

#
Sliceable

source
pub(open) trait Sliceable {
  fn slice(Self, start~ : Int, end~ : Int) -> Result[Self, RleError]
}

Sliceable — extract a sub-range [start, end) from a run.

This trait is optional. Without it, you can still use append, find, concat, extend, value_at, and range. You need Sliceable to unlock positional editing operations: split, insert, delete, and splice. Note: range() returns Slice[T] values that work without Sliceable, but calling Slice::to_inner() to materialize them requires it.

Uses half-open interval [start, end) — start inclusive, end exclusive. Indices are in the same units as span() (e.g., UTF-16 code units for strings, pixel count for pixel runs).

String Warning

For String, indices are UTF-16 code units, not Unicode codepoints. Emoji like "😀" occupy 2 code units (a surrogate pair). Slicing at an index inside a surrogate pair returns Err(InvalidSlice(InvalidIndex)). Always slice on valid character boundaries.
impl Sliceable for String

#
Spanning

source
pub(open) trait Spanning : HasLength {
  fn span(Self) -> Int = _
  fn logical_length(Self) -> Int = _
}

Spanning — two notions of size for position-aware data structures.

Default Chain

The three size methods form a defaulting chain:

HasLength::length  ←──  Spanning::span  ←──  Spanning::logical_length
       (base)          (defaults to length)    (defaults to span)

If you only implement HasLength::length, all three return the same value. Override span() to diverge from length(), or override logical_length() to diverge from span().

When to Override

  • Simple types (strings, pixel runs): implement span() returning the same value as length(). MoonBit requires an explicit impl Spanning declaration even when using the default behavior.

  • CRDT tombstones / gap buffers: override logical_length to return visible content size, while span counts all elements including deleted or hidden ones. The library uses span for position lookup and logical_length for content metrics.

Units

span defines the coordinate space for find, split, range, etc. For strings, this is UTF-16 code units. For pixel runs, pixel count. Choose units that match your indexing needs.
impl Spanning for String

#
InternalError

source
pub(all) suberror InternalError {
  EmptyElement
  InvalidState(String)
} derive(
Debug)

Internal invariant violations - indicates bugs, not user errors

#
RleError

source
pub(all) suberror RleError {
  PositionOutOfBounds(Int, Int)
  InvalidRange(Int, Int, Int, RangeIssue)
  InvalidSlice(SliceError)
  Internal(InternalError)
} derive(
Debug)

User-facing errors with context for friendly messages
impl Show for RleError

#
RleError::message

source
fn RleError::message(self : RleError) -> ErrorMessage

Get a user-friendly message wrapper for this error

#
SliceError

source
pub(all) suberror SliceError {
  IndexOutOfBounds
  InvalidIndex
} derive(Eq, 
Debug)

Slice errors when extracting sub-ranges from a run.

These are raised when a slice lands outside the valid bounds or splits a UTF-16 surrogate pair (string slicing is done in code units).
impl Show for SliceError

#
ErrorMessage

source
pub struct ErrorMessage {
  // private fields
}

Rust style wrapper struct for user-friendly error display

https://doc.rust-lang.org/stable/std/path/struct.Display.html

#
PrefixSums

source
pub(all) struct PrefixSums {
  spans : Array[Int]
  content : Array[Int]
} derive(Eq, 
Debug)
fn PrefixSums::PrefixSums() -> PrefixSums

PrefixSums — cumulative span and content arrays for O(log n) lookup.

Built from a Runs[T] in O(n) by Runs::prefix_sums(). Once built:

  • spans[i] = total span of runs 0 through i (inclusive). Enables binary search in find_fast and O(1) total span via spans.last().

  • content[i] = total logical length of runs 0 through i. Enables O(1) total logical length via content.last().

The library caches this inside Rle (as prefix: PrefixSums?). The cache is set to None on mutation and rebuilt lazily on the next query.
impl Show for PrefixSums

#
PrefixSums::new

source
#deprecated("Use PrefixSums::PrefixSums() instead")
fn PrefixSums::new() -> PrefixSums

Create an empty prefix sum table.

#
PrefixSums::span_at

source
fn PrefixSums::span_at(self : PrefixSums, index : Int) -> Int?

Get span offset at run index (end of run i) with bounds checking.

#
PrefixSums::span_before

source
fn PrefixSums::span_before(self : PrefixSums, index : Int) -> Int

Get span offset before run index (start of run i)

#
RangeIssue

source
pub enum RangeIssue {
  NegativeStart
  NegativeEnd
  StartAfterEnd
  ExceedsLength
} derive(Eq, 
Debug)

Why a range is invalid
impl Show for RangeIssue

#
Rle

source
pub struct Rle[T] {
  runs : Runs[T]
  prefix : PrefixSums?
  version : Int
} derive(Eq, 
Debug)
fn Rle::Rle() -> Rle[T]

Rle — run-length encoded sequence with lazy O(log n) position lookup.

Wraps Runs[T] with two pieces of mutable state:

  • prefix (PrefixSums?): cached cumulative span/content arrays. Set to None on every mutation; rebuilt lazily on the next query. This means consecutive mutations (e.g., multiple append calls) pay no prefix-rebuild cost — the rebuild is amortized over queries.

  • version (Int): monotonically increasing counter, bumped on every mutation. Cursors capture this value at creation and compare on each operation — if they differ, the cursor is stale and refuses to return data. This is a form of optimistic concurrency control.

Mutation Protocol

Every mutating method must call both:
  1. self.bump_version() — so existing cursors detect the change
  2. self.invalidate() — so the next query triggers a prefix rebuild

When to Use Rle vs Runs

Use Rle when you perform repeated queries (find, span, range) between mutations — the cached prefix sums make these O(log n) or O(1). Use Runs directly for one-shot operations or when you manage your own PrefixSums via Runs::prefix_sums() and Runs::find_fast().
impl HasLength for Rle[T]
impl Spanning for Rle[T]
impl Show for Rle[T]
impl Arbitrary for Rle[String]
impl Shrink for Rle[String]

#
Rle::append

source
fn[T : Mergeable + Spanning + HasLength] Rle::append(self : Rle[T], elem : T) -> Result[Unit, RleError]

Append element - invalidates cache and bumps version

#
Rle::clear

source
fn[T] Rle::clear(self : Rle[T]) -> Unit

Clear all runs - invalidates cache and bumps version

#
Rle::concat

source
fn[T : Mergeable + Spanning + HasLength] Rle::concat(self : Rle[T], other : Rle[T]) -> Rle[T]

Concatenate two Rle

#
Rle::cursor

source
fn[T] Rle::cursor(self : Rle[T]) -> RleCursor[T]

Create cursor for Rle (starts at position 0)

#
Rle::delete

source
fn[T : Sliceable + Spanning + Mergeable + HasLength] Rle::delete(self : Rle[T], start~ : Int, end~ : Int) -> Result[Rle[T], RleError]

Delete the range [start, end), returning a new Rle

#
Rle::each_with_position

source
fn[T : Spanning + HasLength] Rle::each_with_position(self : Rle[T], f : (T, Int, Int) -> Unit) -> Unit

Iterate runs with their start and end positions in the span coordinate space.

For each run, calls f(run, start, end) where start and end are half-open positions [start, end) derived from prefix sums — the same coordinate space used by find, range, and split.

Rle: ["abc", "de"]  (spans: 3, 2)

each_with_position yields:
  f("abc", 0, 3)   — positions [0, 3)
  f("de",  3, 5)   — positions [3, 5)

This is the building block for consumer-defined algorithms that need to know where each run sits in the overall sequence. The positions are never stored inside the runs — they are computed on the fly from the lazy prefix sums, keeping runs context-free and reusable.

#
Rle::extend

source
fn[T : Mergeable + Spanning + HasLength] Rle::extend(self : Rle[T], other : Rle[T]) -> Unit

Extend in-place — invalidates cache and bumps version only if actual mutation occurs. Detects mutation by checking both the run count and the last run's span (a merge changes span even when count is unchanged).

#
Rle::find

source
fn[T : Spanning + HasLength] Rle::find(self : Rle[T], pos : Int) -> RunPos?

Find position - O(log n) with cache

#
Rle::from_array

source
fn[T : Mergeable + Spanning + HasLength] Rle::from_array(arr : Array[T]) -> Rle[T]

Construct an Rle from an array, merging adjacent runs

#
Rle::from_runs

source
fn[T] Rle::from_runs(runs : Runs[T]) -> Rle[T]

Wrap existing Runs into an Rle with lazy prefix sums

#
Rle::from_sorted_ints

source
fn[T : FromRange + Spanning + Mergeable + HasLength] Rle::from_sorted_ints(ints : Array[Int]) -> Rle[T]

Construct an Rle from a sorted array of integers.

Convenience wrapper around Runs::from_sorted_ints — groups consecutive integers into compressed runs, then wraps the result with lazy prefix sums.

Rle::from_sorted_ints([0, 1, 2, 5, 6, 7])
  → groups: [range(0, 3), range(5, 3)]
  → Rle with 2 runs, total span 6

See Runs::from_sorted_ints for deduplication and sortedness contracts.

#
Rle::from_string

source
fn Rle::from_string(text : String) -> Rle[String]

Create Rle from string

#
Rle::get

source
fn[T] Rle::get(self : Rle[T], index : Int) -> T?

Get run at index (0-indexed)

#
Rle::get_version

source
fn[T] Rle::get_version(self : Rle[T]) -> Int

Current mutation version (for cursor staleness detection)

#
Rle::insert

source
fn[T : Sliceable + Spanning + Mergeable + HasLength] Rle::insert(self : Rle[T], pos : Int, elem : Rle[T]) -> Result[Rle[T], RleError]

Insert an Rle at span position pos, returning a new Rle

#
Rle::iter

source
fn[T] Rle::iter(self : Rle[T]) -> Iter[T]

Iterate over all runs

#
Rle::iter_chars

source
fn Rle::iter_chars(self : Rle[String]) -> Iter[Char]

Iterate over codepoints

#
Rle::iter_units

source
fn[T : Addressable + Spanning + HasLength] Rle::iter_units(self : Rle[T]) -> Iter[Int]

Expand compressed runs back into individual integer values.

This is the inverse of from_sorted_ints: where from_sorted_ints compresses [0, 1, 2, 5, 6, 7] into two runs, iter_units expands those runs back into [0, 1, 2, 5, 6, 7].

For each run, the library computes global_start from prefix sums, then calls Addressable::address(run, global_start, offset) for each offset 0..span-1. The Addressable implementation decides how to turn that into a domain value — see the trait docs for details.

Returns a lazy Iter[Int] — values are computed on demand, not materialized into an array. Call .collect() if you need an array.

Complexity: O(total_span) — one yield per expanded integer.

#
Rle::new

source
#deprecated("Use Rle::Rle() instead")
fn[T] Rle::new() -> Rle[T]

Create an empty Rle with no runs

#
Rle::range

source
fn[T : Spanning + HasLength] Rle::range(self : Rle[T], start~ : Int, end~ : Int) -> Result[Iter[Slice[T]], RleError]

Iterate slices in range [start, end) — O(log n + k) with cache.

Unlike Runs::range (which scans linearly from the beginning), this method uses find_fast to binary-search for the starting run, then scans forward only through the k runs overlapping the range. For queries near the end of a long sequence, this avoids scanning irrelevant earlier runs.

#
Rle::range_clamped

source
fn[T : Spanning + HasLength] Rle::range_clamped(self : Rle[T], start~ : Int, end~ : Int) -> Iter[Slice[T]]

Iterate slices with clamped bounds

#
Rle::splice

source
fn[T : Sliceable + Spanning + Mergeable + HasLength] Rle::splice(self : Rle[T], start~ : Int, end~ : Int, replacement : Rle[T]) -> Result[Rle[T], RleError]

Replace the range [start, end) with replacement, returning a new Rle

#
Rle::split

source
fn[T : Sliceable + Spanning + Mergeable + HasLength] Rle::split(self : Rle[T], pos : Int) -> Result[(Rle[T], Rle[T]), RleError]

Split at position - invalidates cache

#
Rle::to_runs

source
fn[T] Rle::to_runs(self : Rle[T]) -> Runs[T]

Extract the underlying Runs

#
Rle::to_string

source
fn Rle::to_string(self : Rle[String]) -> String

Concatenate all runs into single string

#
Rle::value_at

source
fn[T : Spanning + HasLength] Rle::value_at(self : Rle[T], pos : Int) -> Result[T, RleError]

Get the run containing span position pos - O(log n) with cache

#
RleCursor

source
pub struct RleCursor[T] {
  rle : Rle[T]
  version : Int
  run_index : Int
  offset_in_run : Int
  global_offset : Int
} derive(Eq, 
Debug)

RleCursor — sequential traversal with automatic staleness detection.

A cursor captures the Rle's version at creation time. On every operation, it compares its captured version against the current version. If they differ (meaning the Rle was mutated), the cursor is stale and all operations return None or false. This is conservative: the cursor refuses to return potentially wrong data rather than guessing.

The version counter is monotonically increasing, so there is no ABA problem — even if the data returns to its original state after two mutations, the version number is higher and staleness is correctly detected.

Typical Usage

let cursor = rle.cursor()   // captures version
cursor.advance(5)           // move forward
cursor.current_item()       // read current run
rle.append(x)               // mutation! version bumps
cursor.is_stale()           // true — cursor is now invalid
cursor.next()               // None — refuses to operate

Create a new cursor after mutations to continue traversal.
impl Show for RleCursor[T]

#
RleCursor::advance

source
fn[T : Spanning + HasLength] RleCursor::advance(self : RleCursor[T], n : Int) -> Bool

Advance by n positions (returns false if stale)

#
RleCursor::at_end

source
fn[T : Spanning + HasLength] RleCursor::at_end(self : RleCursor[T]) -> Bool

Check if at end (returns true if stale - conservative stop)

#
RleCursor::current

source
fn[T] RleCursor::current(self : RleCursor[T]) -> (T, Int)?

Current run and offset within it (returns None if stale)

#
RleCursor::current_item

source
fn[T] RleCursor::current_item(self : RleCursor[T]) -> T?

Current item without offset (returns None if stale)

#
RleCursor::is_stale

source
fn[T] RleCursor::is_stale(self : RleCursor[T]) -> Bool

Check if cursor is stale due to Rle mutations

#
RleCursor::iter_forward

source
fn[T : Spanning + HasLength] RleCursor::iter_forward(self : RleCursor[T]) -> Iter[(T, Int, Int)]

Iterate forward from current position, yielding (item, offset_in_run, global_pos) for each atomic position (per unit of span, not per run).

For a string run "hello" (span 5), this yields 5 entries, each pointing to the same run object with increasing offsets. Returns empty iterator if stale.

#
RleCursor::next

source
fn[T : Spanning + HasLength] RleCursor::next(self : RleCursor[T]) -> T?

Get next item and advance (returns None if stale)

#
RleCursor::position

source
fn[T] RleCursor::position(self : RleCursor[T]) -> Int?

Current global position (returns None if stale)

#
RleCursor::prev

source
fn[T : Spanning + HasLength] RleCursor::prev(self : RleCursor[T]) -> T?

Retreat and get previous item (returns None if stale)

#
RleCursor::retreat

source
fn[T : Spanning + HasLength] RleCursor::retreat(self : RleCursor[T], n : Int) -> Bool

Retreat by n positions (returns false if stale)

#
RleCursor::seek

source
fn[T : Spanning + HasLength] RleCursor::seek(self : RleCursor[T], pos : Int) -> Bool

Seek to absolute position — O(log n) via Rle::find binary search. Returns false if stale or if pos is out of bounds.

#
RleCursor::seek_end

source
fn[T : Spanning + HasLength] RleCursor::seek_end(self : RleCursor[T]) -> Unit

Seek to end

#
RleCursor::seek_start

source
fn[T] RleCursor::seek_start(self : RleCursor[T]) -> Unit

Seek to start

#
RunPos

source
pub(all) struct RunPos {
  run : Int
  offset : Int
} derive(Eq, 
Debug)

Position within runs - result of find operations
impl Show for RunPos
impl Arbitrary for RunPos
impl Shrink for RunPos

#
Runs

source
pub struct Runs[T](Array[T]) derive(Eq, 
Debug)

Array of mergeable runs - core RLE data structure
impl HasLength for Runs[T]
impl Spanning for Runs[T]
impl Show for Runs[T]
impl Shrink for Runs[String]

#
Runs::append

source
fn[T : Mergeable + Spanning + HasLength] Runs::append(self : Runs[T], elem : T) -> Result[Unit, RleError]

Append an element to the runs, merging with the last run if possible.

This is the primary insertion method for RLE-compressed sequences. If the new element is contiguous with the last run (determined by can_merge), they are combined into a single run. Otherwise, a new run is created.

Complexity: O(1) amortized. Merge check and append are constant time, with occasional O(k) normalization where k = number of cascading merges.

Invariant: After append, no two adjacent runs are mergeable.

#
Runs::clear

source
fn[T] Runs::clear(self : Runs[T]) -> Unit

Clear all runs

#
Runs::concat

source
fn[T : Mergeable + Spanning + HasLength] Runs::concat(self : Runs[T], other : Runs[T]) -> Runs[T]

Concatenate two Runs — uses the same stack-merge pattern as from_array_batch.

Copies self's runs, then processes other's runs one by one with the merge cascade. This means the boundary between the two inputs is properly normalized (adjacent mergeable runs across the boundary are combined).

#
Runs::delete

source
fn[T : Sliceable + Spanning + Mergeable + HasLength] Runs::delete(self : Runs[T], start~ : Int, end~ : Int) -> Result[Runs[T], RleError]

Delete the range [start, end), returning a new Runs

#
Runs::extend

source
fn[T : Mergeable + Spanning + HasLength] Runs::extend(self : Runs[T], other : Runs[T]) -> Unit

Extend in-place from another Runs - batch optimized

#
Runs::find

source
fn[T : Spanning + HasLength] Runs::find(self : Runs[T], pos : Int) -> RunPos?

Find position in runs - O(n) linear scan Prefer Runs::find_fast with cached prefix sums for repeated lookups.

#
Runs::find_fast

source
fn[T] Runs::find_fast(self : Runs[T], sums : PrefixSums, pos : Int) -> RunPos?

Find position using prefix sums — O(log n) via upper-bound binary search.

sums.spans is a cumulative array where spans[i] = total span of runs 0 through i. The search finds the smallest index i where spans[i] > pos, which is the run containing position pos. The offset within that run is pos - spans[i-1] (or just pos for run 0).

Caller is responsible for keeping sums in sync with the runs array. Prefer Rle::find() which manages this automatically via lazy caching.

#
Runs::from_array

source
fn[T : Mergeable + Spanning + HasLength] Runs::from_array(arr : Array[T]) -> Runs[T]

Construct Runs from an array, merging adjacent elements

#
Runs::from_array_batch

source
fn[T : Mergeable + Spanning + HasLength] Runs::from_array_batch(arr : Array[T]) -> Runs[T]

Batch construction — O(n) single-pass stack merge.

Uses a stack-based cascade merge: each input element is pushed onto the output array, then the top of the stack is repeatedly merged with the element below it as long as can_merge returns true. This "cascade" ensures the no-adjacent-mergeable invariant in one pass, without the overhead of calling normalize_tail for each element.

Zero-span elements are silently skipped (not an error, unlike append).

Amortized Cost

Each element is pushed and popped at most once, so total work is O(n) regardless of cascade depth. For types where can_merge is selective (e.g., same-author check), most iterations do zero cascading.

#
Runs::from_sorted_ints

source
fn[T : FromRange + Spanning + Mergeable + HasLength] Runs::from_sorted_ints(ints : Array[Int]) -> Runs[T]

Construct Runs from a sorted array of integers by grouping consecutive values.

This is a two-phase algorithm:

  1. Group — walk the sorted array, collecting consecutive integers into ranges. [0, 1, 2, 5, 6, 7] becomes two groups: [0..3) and [5..8). Each group is constructed via FromRange::from_range(start, count).

  2. Normalize — feed the groups through from_array_batch to restore the no-adjacent-mergeable-runs invariant. For types where can_merge checks adjacency (like LvRange), distinct groups stay separate. For types where can_merge is always true (like DenseRun), everything collapses into a single run — maximum compression.

Deduplication

Duplicate values are silently skipped. This is a stated guarantee, not incidental behavior — consumers like CRDT's graph_diff (which may produce duplicates from hashset-derived arrays) rely on it.

from_sorted_ints([1, 1, 2, 3, 5, 5])
  dedup → [1, 2, 3, 5]
  group → [range(1, 3), range(5, 1)]

Sortedness

Assumes input is sorted in ascending order. Non-sorted input produces unspecified (not incorrect) grouping.

Precondition

ints[i-1] + 1 must not overflow Int for any i.

#
Runs::from_string

source
fn Runs::from_string(text : String) -> Runs[String]

Create from string (single run)

#
Runs::get

source
#alias("_[_]")
fn[T] Runs::get(self : Runs[T], index : Int) -> T?

Get run at index (0-indexed), returns None if out of bounds

#
Runs::insert

source
fn[T : Sliceable + Spanning + Mergeable + HasLength] Runs::insert(self : Runs[T], pos : Int, elem : Runs[T]) -> Result[Runs[T], RleError]

Insert runs at span position pos, returning a new Runs

#
Runs::iter

source
fn[T] Runs::iter(self : Runs[T]) -> Iter[T]

Iterate over all runs

#
Runs::iter_chars

source
fn Runs::iter_chars(self : Runs[String]) -> Iter[Char]

Iterate over codepoints

#
Runs::new

source
fn[T] Runs::new() -> Runs[T]

Create an empty Runs with no elements

#
Runs::prefix_sums

source
fn[T : Spanning + HasLength] Runs::prefix_sums(self : Runs[T]) -> PrefixSums

Build prefix sums from runs

#
Runs::range

source
fn[T : Spanning + HasLength] Runs::range(self : Runs[T], start~ : Int, end~ : Int) -> Result[Iter[Slice[T]], RleError]

Iterate slices in range [start, end).

Returns Slice[T] values — lazy views that defer materialization until to_inner() is called. This avoids allocating substrings or sub-runs when the caller only needs to inspect metadata or count matches.

#
Runs::range_clamped

source
fn[T : Spanning + HasLength] Runs::range_clamped(self : Runs[T], start~ : Int, end~ : Int) -> Iter[Slice[T]]

Iterate slices with clamped bounds

#
Runs::splice

source
fn[T : Sliceable + Spanning + Mergeable + HasLength] Runs::splice(self : Runs[T], start~ : Int, end~ : Int, replacement : Runs[T]) -> Result[Runs[T], RleError]

Replace the range [start, end) with replacement, returning a new Runs

#
Runs::split

source
fn[T : Sliceable + Spanning + Mergeable + HasLength] Runs::split(self : Runs[T], pos : Int) -> Result[(Runs[T], Runs[T]), RleError]

Split at position into two Runs.

Requires Sliceable because the run straddling the split point must be sliced into two pieces. The resulting halves are built using append, which maintains the no-adjacent-mergeable invariant.

Note: round-tripping split then concat preserves content but may change the run count. This is expected — the split may create run boundaries that didn't exist before, and re-concatenation merges them differently.

#
Runs::to_array

source
fn[T] Runs::to_array(self : Runs[T]) -> Array[T]

Copy runs into a new array

#
Runs::to_string

source
fn Runs::to_string(self : Runs[String]) -> String

Concatenate all runs into single string

#
Runs::value_at

source
fn[T : Spanning + HasLength] Runs::value_at(self : Runs[T], pos : Int) -> Result[T, RleError]

Get the run containing span position pos - O(n) linear scan

#
Slice

source
pub struct Slice[T] {
  value : T
  start : Int
  end : Int
} derive(Eq, 
Debug)

Slice — a lazy view into a run, representing the sub-range [start, end).

range() operations return Iter[Slice[T]] instead of Iter[T]. Each Slice holds a reference to the original run plus the sub-range bounds, but does not materialize the sliced value until to_inner() is called.

This enables zero-copy iteration: if you only need to count matching runs, check a condition, or read metadata, you can inspect Slice fields without ever allocating new strings or sub-runs.
impl Show for Slice[T]
impl Shrink for Slice[String]

#
Slice::to_inner

source
fn[T : Sliceable] Slice::to_inner(self : Slice[T]) -> Result[T, RleError]

Materializes the sliced value by calling T::slice(value, start, end).

This is the point where allocation happens (e.g., creating a substring). Returns Err if the slice bounds are invalid (e.g., inside a UTF-16 surrogate pair for strings).

#
slice_string_view

source
fn slice_string_view(text : String, start~ : Int, end~ : Int) -> Result[String, SliceError]

String helper that slices with bounds and surrogate pair validation.

MoonBit's text[start:end] no longer raises on invalid boundaries, so we validate explicitly:
  • Out of bounds → SliceError::IndexOutOfBounds
  • Boundary inside a surrogate pair → SliceError::InvalidIndex

A UTF-16 surrogate pair is [high (0xD800–0xDBFF), low (0xDC00–0xDFFF)]. A boundary on a low surrogate means we'd split inside a pair. A boundary on a high surrogate is valid (start of the character).

Source Files

Powered by MoonBit

Site sourceReport issuePackagesBuild queueSkillsStatistics

© 2026 mooncakes.io