///|
/// Array of mergeable runs - core RLE data structure
pub struct Runs[T](Array[T]) derive(Debug, Eq)

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

///|
/// Create an empty Runs with no elements
pub fn[T] Runs::new() -> Runs[T] {
  Runs([])
}

///|
/// 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.
pub fn[T : Mergeable + Spanning] Runs::from_array_batch(
  arr : Array[T],
) -> Runs[T] {
  let out : Array[T] = []
  for item in arr {
    if T::span(item) <= 0 {
      continue
    }
    push_normalized(out, item)
  }
  Runs(out)
}

///|
/// Push one already-valid run into `out`, merging leftward until the
/// no-adjacent-mergeable invariant is restored.
fn[T : Mergeable] push_normalized(out : Array[T], item : T) -> Unit {
  let mut cur = item
  while !out.is_empty() {
    let last = out[out.length() - 1]
    if T::can_merge(last, cur) {
      let _ = out.pop()
      cur = T::merge(last, cur)
    } else {
      break
    }
  }
  out.push(cur)
}

///|
/// Construct Runs from an array, merging adjacent elements
pub fn[T : Mergeable + Spanning] Runs::from_array(arr : Array[T]) -> Runs[T] {
  Runs::from_array_batch(arr)
}

///|
/// 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.
///
/// ```text
/// 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`.
pub fn[T : FromRange + Spanning + Mergeable] Runs::from_sorted_ints(
  ints : Array[Int],
) -> Runs[T] {
  if ints.is_empty() {
    return Runs::new()
  }
  // Phase 1: Group consecutive integers into ranges.
  // We track the current group's start value and count, emitting a run
  // via FromRange::from_range whenever we encounter a gap or duplicate.
  let groups : Array[T] = []
  let mut group_start = ints[0]
  let mut group_count = 1
  for i = 1; i < ints.length(); i = i + 1 {
    let cur = ints[i]
    if cur == ints[i - 1] {
      // Same value as previous — skip (deduplication contract)
      continue
    }
    if cur == ints[i - 1] + 1 {
      // Next consecutive integer — extend the current group
      group_count = group_count + 1
    } else {
      // Gap detected — emit the current group and start a new one
      groups.push(FromRange::from_range(group_start, group_count))
      group_start = cur
      group_count = 1
    }
  }
  // Don't forget the last group (the loop only emits on gaps)
  groups.push(FromRange::from_range(group_start, group_count))
  // Phase 2: Normalize via stack-merge to restore the invariant.
  // This is the same normalization used by from_array and concat.
  Runs::from_array_batch(groups)
}

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

///|
/// HasLength impl — is_empty (overrides default for direct Array check)
pub impl[T] HasLength for Runs[T] with fn is_empty(self : Runs[T]) -> Bool {
  self.0.is_empty()
}

///|
/// Get run at index (0-indexed), returns None if out of bounds
#alias("_[_]")
pub fn[T] Runs::get(self : Runs[T], index : Int) -> T? {
  if index < 0 || index >= self.0.length() {
    None
  } else {
    Some(self.0[index])
  }
}

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

///|
/// Copy runs into a new array
pub fn[T] Runs::to_array(self : Runs[T]) -> Array[T] {
  self.0.copy()
}

///|
/// Spanning impl — total span, O(n)
pub impl[T : Spanning] Spanning for Runs[T] with fn span(self : Runs[T]) -> Int {
  self.0.fold(init=0, fn(acc, item) { acc + T::span(item) })
}

///|
/// Spanning impl — total logical length, O(n)
pub impl[T : Spanning] Spanning for Runs[T] with fn logical_length(
  self : Runs[T],
) -> Int {
  self.0.fold(init=0, fn(acc, item) { acc + T::logical_length(item) })
}

///|
/// 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.
pub fn[T : Mergeable + Spanning] Runs::append(
  self : Runs[T],
  elem : T,
) -> Result[Unit, RleError] {
  if T::span(elem) <= 0 {
    return Err(RleError::Internal(InternalError::EmptyElement))
  }
  match self.0.last() {
    Some(last) =>
      if T::can_merge(last, elem) {
        self.0[self.0.length() - 1] = T::merge(last, elem)
        self.normalize_tail()
      } else {
        self.0.push(elem)
      }
    None => self.0.push(elem)
  }
  Ok(())
}

///|
/// Cascade merging leftward after append to maintain RLE invariants.
///
/// After merging the last two runs, the resulting run may now be mergeable
/// with its predecessor. This function iteratively merges backward until
/// no more merges are possible.
///
/// **Complexity**: O(k) where k = number of consecutive mergeable runs.
/// In practice, k is typically 1-2 for well-distributed insertions.
///
/// **Invariant**: After normalization, no two adjacent runs satisfy `can_merge`.
fn[T : Mergeable] Runs::normalize_tail(self : Runs[T]) -> Unit {
  while self.0.length() >= 2 {
    let last = self.0.length() - 1
    let prev = last - 1
    let a = self.0[prev]
    let b = self.0[last]
    if T::can_merge(a, b) {
      self.0[prev] = T::merge(a, b)
      let _ = self.0.pop()
    } else {
      break
    }
  }
}

///|
/// Find position in runs - O(n) linear scan
/// Prefer `Runs::find_fast` with cached prefix sums for repeated lookups.
pub fn[T : Spanning] Runs::find(self : Runs[T], pos : Int) -> RunPos? {
  if pos < 0 {
    return None
  }
  let mut prefix = 0
  for i = 0; i < self.0.length(); i = i + 1 {
    let run_len = T::span(self.0[i])
    if pos < prefix + run_len {
      return Some({ run: i, offset: pos - prefix })
    }
    prefix = prefix + run_len
  }
  None
}

///|
/// 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.
pub fn[T] Runs::find_fast(
  self : Runs[T],
  sums : PrefixSums,
  pos : Int,
) -> RunPos? {
  if pos < 0 || self.is_empty() {
    return None
  }
  let total = match sums.spans.last() {
    Some(t) => t
    None => return None
  }
  if pos >= total {
    return None
  }
  // Upper-bound binary search: find smallest i where spans[i] > pos
  let mut lo = 0
  let mut hi = self.0.length()
  while lo < hi {
    let mid = lo + (hi - lo) / 2
    if sums.spans[mid] <= pos {
      lo = mid + 1
    } else {
      hi = mid
    }
  }
  if lo == 0 {
    Some({ run: 0, offset: pos })
  } else {
    Some({ run: lo, offset: pos - sums.spans[lo - 1] })
  }
}

///|
/// Build prefix sums from runs
pub fn[T : Spanning] Runs::prefix_sums(self : Runs[T]) -> PrefixSums {
  let spans : Array[Int] = []
  let content : Array[Int] = []
  let mut span_sum = 0
  let mut content_sum = 0
  for item in self.0 {
    span_sum = span_sum + T::span(item)
    content_sum = content_sum + T::logical_length(item)
    spans.push(span_sum)
    content.push(content_sum)
  }
  { spans, content }
}

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

///|
/// Build range slices after the caller has already validated or clamped bounds.
fn[T : Spanning] Runs::range_unchecked(
  self : Runs[T],
  start~ : Int,
  end~ : Int,
) -> Iter[Slice[T]] {
  if start == end {
    return Iter::empty()
  }
  let result : Array[Slice[T]] = []
  let mut pos = 0
  for item in self.0 {
    let run_len = T::span(item)
    let item_end = pos + run_len
    if item_end > start && pos < end {
      let slice_start = if pos < start { start - pos } else { 0 }
      let slice_end = if item_end > end { end - pos } else { run_len }
      result.push({ value: item, start: slice_start, end: slice_end })
    }
    pos = item_end
    if pos >= end {
      break
    }
  }
  result.iter()
}

///|
/// Iterate slices with clamped bounds
pub fn[T : Spanning] Runs::range_clamped(
  self : Runs[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(start=s, end=e)
}

///|
/// 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.
pub fn[T : Sliceable + Spanning + Mergeable] Runs::split(
  self : Runs[T],
  pos : Int,
) -> Result[(Runs[T], Runs[T]), RleError] {
  let total = self.span()
  if pos < 0 || pos > total {
    return Err(RleError::PositionOutOfBounds(position=pos, length=total))
  }
  if pos == 0 {
    return Ok((Runs::new(), self))
  }
  if pos == total {
    return Ok((self, Runs::new()))
  }
  let left : Runs[T] = Runs::new()
  let right : Runs[T] = Runs::new()
  let mut cur = 0
  for item in self.0 {
    let run_len = T::span(item)
    let item_end = cur + run_len
    if item_end <= pos {
      match left.append(item) {
        Err(e) => return Err(e)
        Ok(_) => ()
      }
    } else if cur >= pos {
      match right.append(item) {
        Err(e) => return Err(e)
        Ok(_) => ()
      }
    } else {
      let offset = pos - cur
      if offset > 0 {
        match T::slice(item, start=0, end=offset) {
          Ok(slice) =>
            match left.append(slice) {
              Err(e) => return Err(e)
              Ok(_) => ()
            }
          Err(e) => return Err(e)
        }
      }
      if offset < run_len {
        match T::slice(item, start=offset, end=run_len) {
          Ok(slice) =>
            match right.append(slice) {
              Err(e) => return Err(e)
              Ok(_) => ()
            }
          Err(e) => return Err(e)
        }
      }
    }
    cur = item_end
  }
  Ok((left, right))
}

///|
/// Clear all runs
pub fn[T] Runs::clear(self : Runs[T]) -> Unit {
  self.0.clear()
}

///|
/// 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).
pub fn[T : Mergeable + Spanning] Runs::concat(
  self : Runs[T],
  other : Runs[T],
) -> Runs[T] {
  if self.is_empty() {
    return Runs::from_array_batch(other.0)
  }
  if other.is_empty() {
    return Runs(self.0.copy())
  }
  let out : Array[T] = self.0.copy()
  for item in other.0 {
    if T::span(item) <= 0 {
      continue
    }
    push_normalized(out, item)
  }
  Runs(out)
}

///|
/// Extend in-place from another Runs - batch optimized
pub fn[T : Mergeable + Spanning] Runs::extend(
  self : Runs[T],
  other : Runs[T],
) -> Unit {
  if other.is_empty() {
    return
  }
  for item in other.0 {
    if T::span(item) <= 0 {
      continue
    }
    push_normalized(self.0, item)
  }
}

///|
/// Get the run containing span position `pos` - O(n) linear scan
pub fn[T : Spanning] Runs::value_at(
  self : Runs[T],
  pos : Int,
) -> Result[T, RleError] {
  let total = self.span()
  if pos < 0 || pos >= total {
    return Err(RleError::PositionOutOfBounds(position=pos, length=total))
  }
  match self.find(pos) {
    Some(rp) =>
      match self.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 runs at span position `pos`, returning a new Runs
pub fn[T : Sliceable + Spanning + Mergeable] Runs::insert(
  self : Runs[T],
  pos : Int,
  elem : Runs[T],
) -> Result[Runs[T], RleError] {
  match self.split(pos) {
    Ok((left, right)) => Ok(left.concat(elem).concat(right))
    Err(e) => Err(e)
  }
}

///|
/// Delete the range [start, end), returning a new Runs
pub fn[T : Sliceable + Spanning + Mergeable] Runs::delete(
  self : Runs[T],
  start~ : Int,
  end~ : Int,
) -> Result[Runs[T], RleError] {
  let total = self.span()
  match range_check(start, end, total) {
    Ok(_) => ()
    Err(e) => return Err(e)
  }
  // Validate boundary even for empty ranges (e.g. surrogate pair interior)
  let (left, rest) = match self.split(start) {
    Ok(pair) => pair
    Err(e) => return Err(e)
  }
  let (_, right) = match rest.split(end - start) {
    Ok(pair) => pair
    Err(e) => return Err(e)
  }
  Ok(left.concat(right))
}

///|
/// Replace the range [start, end) with `replacement`, returning a new Runs
pub fn[T : Sliceable + Spanning + Mergeable] Runs::splice(
  self : Runs[T],
  start~ : Int,
  end~ : Int,
  replacement : Runs[T],
) -> Result[Runs[T], RleError] {
  let total = self.span()
  match range_check(start, end, total) {
    Ok(_) => ()
    Err(e) => return Err(e)
  }
  let (left, rest) = match self.split(start) {
    Ok(pair) => pair
    Err(e) => return Err(e)
  }
  let (_, right) = match rest.split(end - start) {
    Ok(pair) => pair
    Err(e) => return Err(e)
  }
  Ok(left.concat(replacement).concat(right))
}

///|
fn range_check(start : Int, end : Int, total : Int) -> Result[Unit, RleError] {
  if start < 0 {
    return Err(
      RleError::InvalidRange(start~, end~, length=total, reason=NegativeStart),
    )
  }
  if end < 0 {
    return Err(
      RleError::InvalidRange(start~, end~, length=total, reason=NegativeEnd),
    )
  }
  if start > end {
    return Err(
      RleError::InvalidRange(start~, end~, length=total, reason=StartAfterEnd),
    )
  }
  if end > total {
    return Err(
      RleError::InvalidRange(start~, end~, length=total, reason=ExceedsLength),
    )
  }
  Ok(())
}