///|
/// **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()`.
pub struct Rle[T] {
  runs : Runs[T]
  mut prefix : PrefixSums? // None = stale, needs rebuild
  mut version : Int // Monotonically increasing mutation counter
} derive(Debug, Eq)

///|
pub impl[T : Debug] Show for Rle[T] with output(self, logger) {
  logger.write_string(@debug.to_string(self))
}

///|
/// Create an empty Rle with no runs
pub fn[T] Rle::Rle() -> Rle[T] {
  { runs: Runs::new(), prefix: None, version: 0 }
}

///|
/// Create an empty Rle with no runs
#deprecated("Use Rle::Rle() instead", skip_current_package=true)
pub fn[T] Rle::new() -> Rle[T] {
  Rle()
}

///|
/// Construct an Rle from an array, merging adjacent runs
pub fn[T : Mergeable + Spanning] Rle::from_array(arr : Array[T]) -> Rle[T] {
  { runs: Runs::from_array(arr), prefix: None, version: 0 }
}

///|
/// 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.
///
/// ```text
/// 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.
pub fn[T : FromRange + Spanning + Mergeable] Rle::from_sorted_ints(
  ints : Array[Int],
) -> Rle[T] {
  { runs: Runs::from_sorted_ints(ints), prefix: None, version: 0 }
}

///|
/// Wrap existing Runs into an Rle with lazy prefix sums
pub fn[T] Rle::from_runs(runs : Runs[T]) -> Rle[T] {
  { runs, prefix: None, version: 0 }
}

///|
/// 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`.
///
/// ```text
/// 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.
pub fn[T : Spanning] Rle::each_with_position(
  self : Rle[T],
  f : (T, Int, Int) -> Unit,
) -> Unit {
  let prefix = self.ensure_prefix()
  let mut start = 0
  for i = 0; i < self.runs.0.length(); i = i + 1 {
    let run = self.runs.0[i]
    let end = prefix.spans[i]
    f(run, start, end)
    start = end
  }
}

///|
/// 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.
pub fn[T : Addressable + Spanning] Rle::iter_units(self : Rle[T]) -> Iter[Int] {
  let prefix = self.ensure_prefix()
  let items = self.runs.0
  let total_runs = items.length()
  // Iterator state: which run we're in, and which offset within that run.
  let mut run_idx = 0
  let mut offset = 0
  // Cache per-run values to avoid recomputing on every yield.
  // These are updated only when we advance to a new run.
  let mut cached_start = if total_runs > 0 { prefix.span_before(0) } else { 0 }
  let mut cached_span = if total_runs > 0 { T::span(items[0]) } else { 0 }
  Iter::new(fn() {
    while run_idx < total_runs {
      if offset < cached_span {
        // Still within the current run — yield the next domain value.
        // Addressable::address translates (run, global_start, offset) → Int.
        let value = T::address(items[run_idx], cached_start, offset)
        offset = offset + 1
        return Some(value)
      }
      // Current run exhausted — advance to the next one and refresh cache.
      run_idx = run_idx + 1
      offset = 0
      if run_idx < total_runs {
        cached_start = prefix.span_before(run_idx)
        cached_span = T::span(items[run_idx])
      }
    }
    None
  })
}

///|
/// Extract the underlying Runs
pub fn[T] Rle::to_runs(self : Rle[T]) -> Runs[T] {
  self.runs
}

///|
/// Current mutation version (for cursor staleness detection)
pub fn[T] Rle::get_version(self : Rle[T]) -> Int {
  self.version
}

///|
/// Increment version on structural mutations
fn[T] Rle::bump_version(self : Rle[T]) -> Unit {
  self.version = self.version + 1
}

///|
/// Mark prefix sums as stale
fn[T] Rle::invalidate(self : Rle[T]) -> Unit {
  self.prefix = None
}

///|
/// Apply the mutation protocol shared by all in-place structural changes.
fn[T] Rle::mark_mutated(self : Rle[T]) -> Unit {
  self.bump_version()
  self.invalidate()
}

///|
/// Rebuild prefix sums if stale
fn[T : Spanning] Rle::ensure_prefix(self : Rle[T]) -> PrefixSums {
  match self.prefix {
    Some(p) => p
    None => {
      let p = self.runs.prefix_sums()
      self.prefix = Some(p)
      p
    }
  }
}

///|
/// HasLength impl — number of runs
pub impl[T] HasLength for Rle[T] with length(self : Rle[T]) -> Int {
  self.runs.length()
}

///|
/// HasLength impl — is_empty (overrides default to delegate to Runs::is_empty)
pub impl[T] HasLength for Rle[T] with is_empty(self : Rle[T]) -> Bool {
  self.runs.is_empty()
}

///|
/// Get run at index (0-indexed)
pub fn[T] Rle::get(self : Rle[T], index : Int) -> T? {
  self.runs.get(index)
}

///|
/// Iterate over all runs
pub fn[T] Rle::iter(self : Rle[T]) -> Iter[T] {
  self.runs.iter()
}

///|
/// Spanning impl — total span, O(1) with cache
pub impl[T : Spanning] Spanning for Rle[T] with span(self : Rle[T]) -> Int {
  self.ensure_prefix().span()
}

///|
/// Spanning impl — logical content length, O(1) with cache
pub impl[T : Spanning] Spanning for Rle[T] with logical_length(self : Rle[T]) -> Int {
  self.ensure_prefix().logical_length()
}

///|
/// Append element - invalidates cache and bumps version
pub fn[T : Mergeable + Spanning] Rle::append(
  self : Rle[T],
  elem : T,
) -> Result[Unit, RleError] {
  match self.runs.append(elem) {
    Ok(_) => {
      self.mark_mutated()
      Ok(())
    }
    Err(e) => Err(e)
  }
}

///|
/// Find position - O(log n) with cache
pub fn[T : Spanning] Rle::find(self : Rle[T], pos : Int) -> RunPos? {
  let sums = self.ensure_prefix()
  self.runs.find_fast(sums, pos)
}

///|
/// 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.
pub fn[T : Spanning] Rle::range(
  self : Rle[T],
  start~ : Int,
  end~ : Int,
) -> Result[Iter[Slice[T]], RleError] {
  let sums = self.ensure_prefix()
  let total = sums.span()
  match range_check(start, end, total) {
    Ok(_) => ()
    Err(e) => return Err(e)
  }
  Ok(self.range_unchecked(sums, start~, end~))
}

///|
/// Build range slices after the caller has already validated or clamped bounds.
fn[T] Rle::range_unchecked(
  self : Rle[T],
  sums : PrefixSums,
  start~ : Int,
  end~ : Int,
) -> Iter[Slice[T]] {
  if start == end {
    return Iter::empty()
  }
  // Use binary search to find starting run
  let start_pos = self.runs.find_fast(sums, start)
  guard start_pos is Some(sp) else { return Iter::empty() }
  let result : Array[Slice[T]] = []
  let mut i = sp.run
  let mut prefix = sums.span_before(i)
  while i < self.runs.0.length() {
    let item = self.runs.0[i]
    let item_end = sums.spans[i]
    if item_end > start && prefix < end {
      let slice_start = if prefix < start { start - prefix } else { 0 }
      let slice_end = if item_end > end {
        end - prefix
      } else {
        item_end - prefix
      }
      result.push({ value: item, start: slice_start, end: slice_end })
    }
    if item_end >= end {
      break
    }
    prefix = item_end
    i = i + 1
  }
  result.iter()
}

///|
/// Iterate slices with clamped bounds
pub fn[T : Spanning] Rle::range_clamped(
  self : Rle[T],
  start~ : Int,
  end~ : Int,
) -> Iter[Slice[T]] {
  let total = self.span()
  let s = if start < 0 { 0 } else { start }
  let e = if end > total { total } else { end }
  if s >= e {
    return Iter::empty()
  }
  self.range_unchecked(self.ensure_prefix(), start=s, end=e)
}

///|
/// Split at position - invalidates cache
pub fn[T : Sliceable + Spanning + Mergeable] Rle::split(
  self : Rle[T],
  pos : Int,
) -> Result[(Rle[T], Rle[T]), RleError] {
  match self.runs.split(pos) {
    Ok((left, right)) => Ok((Rle::from_runs(left), Rle::from_runs(right)))
    Err(e) => Err(e)
  }
}

///|
/// Clear all runs - invalidates cache and bumps version
pub fn[T] Rle::clear(self : Rle[T]) -> Unit {
  self.runs.clear()
  self.mark_mutated()
}

///|
/// Concatenate two Rle
pub fn[T : Mergeable + Spanning] Rle::concat(
  self : Rle[T],
  other : Rle[T],
) -> Rle[T] {
  Rle::from_runs(self.runs.concat(other.runs))
}

///|
/// 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).
pub fn[T : Mergeable + Spanning] Rle::extend(
  self : Rle[T],
  other : Rle[T],
) -> Unit {
  if other.runs.is_empty() {
    return
  }
  let old_count = self.runs.length()
  let old_last_span = match self.runs.get(old_count - 1) {
    Some(r) => T::span(r)
    None => 0
  }
  self.runs.extend(other.runs)
  let new_count = self.runs.length()
  let new_last_span = match self.runs.get(new_count - 1) {
    Some(r) => T::span(r)
    None => 0
  }
  if new_count != old_count || new_last_span != old_last_span {
    self.mark_mutated()
  }
}

///|
/// Get the run containing span position `pos` - O(log n) with cache
pub fn[T : Spanning] Rle::value_at(
  self : Rle[T],
  pos : Int,
) -> Result[T, RleError] {
  let sums = self.ensure_prefix()
  let total = sums.span()
  if pos < 0 || pos >= total {
    return Err(RleError::PositionOutOfBounds(position=pos, length=total))
  }
  match self.runs.find_fast(sums, pos) {
    Some(rp) =>
      match self.runs.get(rp.run) {
        Some(value) => Ok(value)
        None =>
          Err(
            RleError::Internal(
              InternalError::InvalidState(
                detail="find returned invalid run index",
              ),
            ),
          )
      }
    None =>
      Err(
        RleError::Internal(
          InternalError::InvalidState(
            detail="find returned None for valid position",
          ),
        ),
      )
  }
}

///|
/// Insert an Rle at span position `pos`, returning a new Rle
pub fn[T : Sliceable + Spanning + Mergeable] Rle::insert(
  self : Rle[T],
  pos : Int,
  elem : Rle[T],
) -> Result[Rle[T], RleError] {
  match self.runs.insert(pos, elem.runs) {
    Ok(runs) => Ok(Rle::from_runs(runs))
    Err(e) => Err(e)
  }
}

///|
/// Delete the range [start, end), returning a new Rle
pub fn[T : Sliceable + Spanning + Mergeable] Rle::delete(
  self : Rle[T],
  start~ : Int,
  end~ : Int,
) -> Result[Rle[T], RleError] {
  match self.runs.delete(start~, end~) {
    Ok(runs) => Ok(Rle::from_runs(runs))
    Err(e) => Err(e)
  }
}

///|
/// Replace the range [start, end) with `replacement`, returning a new Rle
pub fn[T : Sliceable + Spanning + Mergeable] Rle::splice(
  self : Rle[T],
  start~ : Int,
  end~ : Int,
  replacement : Rle[T],
) -> Result[Rle[T], RleError] {
  match self.runs.splice(start~, end~, replacement.runs) {
    Ok(runs) => Ok(Rle::from_runs(runs))
    Err(e) => Err(e)
  }
}