README
U
MayStale
Tr
Addressable
Tr
FromRange
Tr
HasLength
Tr
Mergeable
Tr
Sliceable
Tr
Spanning
E
InternalError
- ::messageRleError::message
E
SliceError
T
ErrorMessage
- ::newPrefixSums::new
- ::span_atPrefixSums::span_at
- ::span_beforePrefixSums::span_before
T
RangeIssue
- ::appendRle::append
- ::clearRle::clear
- ::concatRle::concat
- ::cursorRle::cursor
- ::deleteRle::delete
- ::each_with_positionRle::each_with_position
- ::extendRle::extend
- ::findRle::find
- ::from_arrayRle::from_array
- ::from_runsRle::from_runs
- ::from_sorted_intsRle::from_sorted_ints
- ::from_stringRle::from_string
- ::getRle::get
- ::get_versionRle::get_version
- ::insertRle::insert
- ::iterRle::iter
- ::iter_charsRle::iter_chars
- ::iter_unitsRle::iter_units
- ::newRle::new
- ::rangeRle::range
- ::range_clampedRle::range_clamped
- ::spliceRle::splice
- ::splitRle::split
- ::to_runsRle::to_runs
- ::to_stringRle::to_string
- ::value_atRle::value_at
- ::advanceRleCursor::advance
- ::at_endRleCursor::at_end
- ::currentRleCursor::current
- ::current_itemRleCursor::current_item
- ::is_staleRleCursor::is_stale
- ::iter_forwardRleCursor::iter_forward
- ::nextRleCursor::next
- ::positionRleCursor::position
- ::prevRleCursor::prev
- ::retreatRleCursor::retreat
- ::seekRleCursor::seek
- ::seek_endRleCursor::seek_end
- ::seek_startRleCursor::seek_start
T
RunPos
- ::appendRuns::append
- ::clearRuns::clear
- ::concatRuns::concat
- ::deleteRuns::delete
- ::extendRuns::extend
- ::findRuns::find
- ::find_fastRuns::find_fast
- ::from_arrayRuns::from_array
- ::from_array_batchRuns::from_array_batch
- ::from_sorted_intsRuns::from_sorted_ints
- ::from_stringRuns::from_string
- ::getRuns::get
- ::insertRuns::insert
- ::iterRuns::iter
- ::iter_charsRuns::iter_chars
- ::newRuns::new
- ::prefix_sumsRuns::prefix_sums
- ::rangeRuns::range
- ::range_clampedRuns::range_clamped
- ::spliceRuns::splice
- ::splitRuns::split
- ::to_arrayRuns::to_array
- ::to_stringRuns::to_string
- ::value_atRuns::value_at
- ::to_innerSlice::to_inner
V
slice_string_view

rle

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

rle

run-length-encoding

data-structure

Download zip

Author

dowdiness

Version

0.2.0

License

Apache-2.0

Repository

github.com/dowdiness/rle

Last updated

6 months ago

Downloads

50K

moonbitlang/quickcheck0.11.2

#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")
  inspect(
    rle.find(6),
    content=(
      #|Some({ run: 0, offset: 6 })
    ),
  )
}

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

///|
test {
  let rle : @rle.Rle[String] = @rle.Rle::new()
  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]
  inspect(
    @rle.Sliceable::slice(s.value, start=s.start, end=s.end),
    content="Ok(\"ell\")",
  )
}

#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")
  inspect(cursor.position(), content="Some(3)")
  inspect(cursor.current_item(), content="Some(\"abcdef\")")

  // seek() uses binary search — O(log n)
  inspect(cursor.seek(1), content="true")
  inspect(cursor.position(), content="Some(1)")
}

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(), content="None")
}

#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")
  inspect(
    rle.find(0),
    content=(
      #|Some({ run: 0, offset: 0 })
    ),
  )
  inspect(
    rle.find(4),
    content=(
      #|Some({ run: 0, offset: 4 })
    ),
  )
  inspect(rle.find(5), content="None")
  inspect(rle.find(-1), content="None")
}

value_at returns the full run containing a position:

///|
test {
  let rle = @rle.Rle::from_string("hello")
  inspect(rle.value_at(2), content="Ok(\"hello\")")
  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::new()
  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::new()
  inspect(rle.append(""), content="Err(Internal(EmptyElement))")
}

#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, content="InvalidSlice(reason=InvalidIndex)")
  }
}

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")
  inspect(
    rle.find(2),
    content=(
      #|Some({ run: 0, offset: 2 })
    ),
  )
  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]
  inspect(
    @rle.Sliceable::slice(s.value, start=s.start, end=s.end),
    content="Ok(\"hello\")",
  )
}

#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")
  inspect(
    rle.find(6),
    content=(
      #|Some({ run: 0, offset: 6 })
    ),
  )
}

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

///|
test {
  let rle : @rle.Rle[String] = @rle.Rle::new()
  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]
  inspect(
    @rle.Sliceable::slice(s.value, start=s.start, end=s.end),
    content="Ok(\"ell\")",
  )
}

#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")
  inspect(cursor.position(), content="Some(3)")
  inspect(cursor.current_item(), content="Some(\"abcdef\")")

  // seek() uses binary search — O(log n)
  inspect(cursor.seek(1), content="true")
  inspect(cursor.position(), content="Some(1)")
}

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(), content="None")
}

#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")
  inspect(
    rle.find(0),
    content=(
      #|Some({ run: 0, offset: 0 })
    ),
  )
  inspect(
    rle.find(4),
    content=(
      #|Some({ run: 0, offset: 4 })
    ),
  )
  inspect(rle.find(5), content="None")
  inspect(rle.find(-1), content="None")
}

value_at returns the full run containing a position:

///|
test {
  let rle = @rle.Rle::from_string("hello")
  inspect(rle.value_at(2), content="Ok(\"hello\")")
  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::new()
  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::new()
  inspect(rle.append(""), content="Err(Internal(EmptyElement))")
}

#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, content="InvalidSlice(reason=InvalidIndex)")
  }
}

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")
  inspect(
    rle.find(2),
    content=(
      #|Some({ run: 0, offset: 2 })
    ),
  )
  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]
  inspect(
    @rle.Sliceable::slice(s.value, start=s.start, end=s.end),
    content="Ok(\"hello\")",
  )
}

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 {
  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 {
  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 {
  length(Self) -> Int
  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 {
  can_merge(Self, Self) -> Bool
  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:

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.
merge preserves content: the merged run must represent the same logical sequence as the two original runs placed side by side.
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 {
  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 {
  span(Self) -> Int = _
  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(@moonbitlang/core/debug.Debug
Debug)

Internal invariant violations - indicates bugs, not user errors

impl Show for InternalError

RleError

source

pub(all) suberror RleError {
  PositionOutOfBounds(Int, Int)
  InvalidRange(Int, Int, Int, RangeIssue)
  InvalidSlice(SliceError)
  Internal(InternalError)
} derive(@moonbitlang/core/debug.Debug
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, @moonbitlang/core/debug.Debug
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

impl Show for ErrorMessage

PrefixSums

source

pub(all) struct PrefixSums {
  spans : Array[Int]
  content : Array[Int]
} derive(Eq, @moonbitlang/core/debug.Debug
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 HasLength for PrefixSums

impl Spanning for PrefixSums

impl Show for PrefixSums

impl Arbitrary for PrefixSums

impl Shrink for PrefixSums

PrefixSums::new

source

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, @moonbitlang/core/debug.Debug
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, @moonbitlang/core/debug.Debug
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:

self.bump_version() — so existing cursors detect the change
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]

fn[T : Spanning + HasLength] logical_length(self : Rle[T]) -> Int

source

Spanning impl — logical content length, O(1) with cache

fn[T : Spanning + HasLength] span(self : Rle[T]) -> Int

source

Spanning impl — total span, O(1) with cache

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

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, @moonbitlang/core/debug.Debug
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, @moonbitlang/core/debug.Debug
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, @moonbitlang/core/debug.Debug
Debug)

Array of mergeable runs - core RLE data structure

impl HasLength for Runs[T]

impl Spanning for Runs[T]

fn[T : Spanning + HasLength] logical_length(self : Runs[T]) -> Int

source

Spanning impl — total logical length, O(n)

fn[T : Spanning + HasLength] span(self : Runs[T]) -> Int

source

Spanning impl — total span, O(n)

impl Show for Runs[T]

impl Arbitrary for Runs[String]

fn arbitrary(size : Int, random_state : @moonbitlang/core/quickcheck/splitmix.RandomState
RandomState) -> Runs[String]

source

Arbitrary instance for Runs[String] - generates random run-length encoded strings

impl Shrink for Runs[String]

fn shrink(runs : Runs[String]) -> Iter[Runs[String]]

source

Shrink instance for Runs[String] - simplifies failing test cases

Shrinking strategies:

Remove runs (fewer runs = simpler)
Shorten individual runs
Simplify characters (later chars -> earlier chars)

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:

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).
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, @moonbitlang/core/debug.Debug
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 Arbitrary for Slice[String]

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

Install

Download zip

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

rlerun-length-encodingdata-structure

dowdiness

Apache-2.0

github.com/dowdiness/rle

Updated 6 months ago

50K downloads

Site source Report issue Modules Skills CLI Build queue Statistics

rle

#rle

#Quick Start

#Working with Strings

#Batch Construction

#Editing Operations

#Cursor for Sequential Traversal

#Concatenation and Extension

#Position Lookup

#Dual-Length Semantics

#Lazy Prefix Sum Caching

#Cursor Version Tracking

#Error Handling

#UTF-16 String Indices

#Unicode Support

#Empty Ranges and Edge Cases

#Clamped Range

#rle

#Quick Start

#Working with Strings

#Batch Construction

#Editing Operations

#Cursor for Sequential Traversal

#Concatenation and Extension

#Position Lookup

#Dual-Length Semantics

#Lazy Prefix Sum Caching

#Cursor Version Tracking

#Error Handling

#UTF-16 String Indices

#Unicode Support

#Empty Ranges and Edge Cases

#Clamped Range

#MayStale

#Addressable

Parameters

Index-Carrying vs Index-Free

#FromRange

Index-Carrying vs Index-Free

#HasLength

#Mergeable

Contract

Examples

#Sliceable

String Warning

#Spanning

Default Chain

When to Override

Units

#InternalError

#RleError

#RleError::message

#SliceError

#ErrorMessage

#PrefixSums

#PrefixSums::new

#PrefixSums::span_at

#PrefixSums::span_before

#RangeIssue

#Rle

Mutation Protocol

When to Use Rle vs Runs

#Rle::append

#Rle::clear

#Rle::concat

#Rle::cursor

#Rle::delete

#Rle::each_with_position

#Rle::extend

#Rle::find

#Rle::from_array

#Rle::from_runs

#Rle::from_sorted_ints

#Rle::from_string

#Rle::get

#Rle::get_version

#Rle::insert

#Rle::iter

#Rle::iter_chars

#Rle::iter_units

MayStale

Addressable

FromRange

HasLength

Mergeable

Sliceable

Spanning

InternalError

RleError

RleError::message

SliceError

ErrorMessage

PrefixSums

PrefixSums::new

PrefixSums::span_at

PrefixSums::span_before

RangeIssue

Rle

Rle::append

Rle::clear

Rle::concat

Rle::cursor

Rle::delete

Rle::each_with_position

Rle::extend

Rle::find

Rle::from_array

Rle::from_runs

Rle::from_sorted_ints

Rle::from_string

Rle::get

Rle::get_version

Rle::insert

Rle::iter

Rle::iter_chars

Rle::iter_units

Rle::new

Rle::range

Rle::range_clamped

Rle::splice

Rle::split

Rle::to_runs

Rle::to_string

Rle::value_at

RleCursor

RleCursor::advance

RleCursor::at_end

RleCursor::current

RleCursor::current_item

RleCursor::is_stale

RleCursor::iter_forward

RleCursor::next

RleCursor::position

RleCursor::prev

RleCursor::retreat

RleCursor::seek

RleCursor::seek_end

RleCursor::seek_start

RunPos

Runs

Runs::append

Runs::clear

Runs::concat

Runs::delete

Runs::extend

Runs::find

Runs::find_fast

Runs::from_array

Runs::from_array_batch

Runs::from_sorted_ints

Runs::from_string

Runs::get

Runs::insert

Runs::iter

Runs::iter_chars

Runs::new

Runs::prefix_sums

Runs::range

Runs::range_clamped

Runs::splice