///|
/// One key's winning source, retaining gap versus tombstone distinctions.
pub struct AlignedFact {
  priv key : String
  priv source : Revision?
}

///|
pub fn AlignedFact::key(self : AlignedFact) -> String {
  self.key
}

///|
pub fn AlignedFact::source(self : AlignedFact) -> Revision? {
  self.source
}

///|
pub fn AlignedFact::value(self : AlignedFact) -> String? {
  match self.source {
    Some(r) => r.value
    None => None
  }
}

///|
pub fn AlignedFact::is_gap(self : AlignedFact) -> Bool {
  self.source is None
}

///|
pub fn AlignedFact::is_deleted(self : AlignedFact) -> Bool {
  match self.source {
    Some(r) => r.value is None
    None => false
  }
}

///|
/// Maximal interval with one constant source revision per selected key.
pub struct AlignedSegment {
  priv valid : Span
  priv facts : Array[AlignedFact]
}

///|
pub fn AlignedSegment::valid(self : AlignedSegment) -> Span {
  self.valid
}

///|
pub fn AlignedSegment::facts(self : AlignedSegment) -> Array[AlignedFact] {
  self.facts.copy()
}

///|
/// Outer temporal alignment: every selected key appears in every output row,
/// including gaps and withdrawals. Keys are deduplicated and sorted. Source
/// changes split intervals even when values are equal. No business rule runs.
pub fn Ledger::aligned_timeline(
  self : Ledger,
  keys : Array[String],
  bounds : Span,
  known_at : Int64,
  max_keys~ : Int32 = 64,
  max_segments~ : Int32 = 4096,
  max_cells~ : Int32 = 65536,
  max_input_segments~ : Int32 = 16384,
) -> Array[AlignedSegment] raise TemporalError {
  if max_segments <= 0 {
    raise TooManySegments(maximum=max_segments)
  }
  if max_cells < 0 {
    raise TooManyCells(maximum=max_cells)
  }
  if max_input_segments <= 0 || max_input_segments > 1000000 {
    raise TooManySegments(maximum=max_input_segments)
  }
  let selected = unique_query_keys(keys, max_keys)
  for key in selected {
    if key.is_empty() {
      raise EmptyKey
    }
  }
  if selected.length() > max_cells {
    raise TooManyCells(maximum=max_cells)
  }
  let timelines : Array[Array[Segment]] = []
  let points : Array[Int64] = [bounds.start]
  let mut used = 0
  for key in selected {
    if used >= max_input_segments {
      raise TooManySegments(maximum=max_input_segments)
    }
    let segments = self.timeline(
      key,
      bounds,
      known_at,
      max_segments=max_input_segments - used,
    )
    used += segments.length()
    timelines.push(segments)
    for segment in segments {
      points.push(segment.valid.start)
      if segment.valid.end is Some(end) {
        points.push(end)
      }
    }
  }
  if bounds.end is Some(end) {
    points.push(end)
  }
  points.sort_by(fn(a, b) { if a < b { -1 } else if a > b { 1 } else { 0 } })
  let unique : Array[Int64] = []
  for point in points {
    if unique.is_empty() || unique[unique.length() - 1] != point {
      unique.push(point)
    }
  }
  let cursors = Array::make(selected.length(), 0)
  let output : Array[AlignedSegment] = []
  for position, start in unique {
    if bounds.end == Some(start) {
      break
    }
    if output.length() >= max_segments {
      raise TooManySegments(maximum=max_segments)
    }
    if selected.length() > 0 && output.length() >= max_cells / selected.length() {
      raise TooManyCells(maximum=max_cells)
    }
    let end = if position + 1 < unique.length() {
      Some(unique[position + 1])
    } else {
      bounds.end
    }
    let facts : Array[AlignedFact] = []
    for index, key in selected {
      let timeline = timelines[index]
      while cursors[index] + 1 < timeline.length() &&
            timeline[cursors[index]].valid.end is Some(e) &&
            e <= start {
        cursors[index] = cursors[index] + 1
      }
      facts.push({ key, source: timeline[cursors[index]].source, })
    }
    output.push({ valid: { start, end, }, facts, })
  }
  output
}