///|
/// Policies for combining traces recorded by separate simulators or runs.
pub enum MergeTimeMode {
  PreserveLeft
  PreserveRight
  ShiftRightToEnd
  AlignFirstChange
  AlignNamedSignal
} derive(Debug, Eq)

///|
/// Return every merge timing mode supported by the library.
pub fn merge_time_mode_catalog() -> Array[MergeTimeMode] {
  [
    PreserveLeft,
    PreserveRight,
    ShiftRightToEnd,
    AlignFirstChange,
    AlignNamedSignal,
  ]
}

///|
/// Options for a deterministic trace merge.
pub struct MergeOptions {
  mode : MergeTimeMode
  offset : Int64
  align_signal : String?
  include_duplicate_changes : Bool
  rename_conflicts : Bool
  sort_changes : Bool
} derive(Debug, Eq)

///|
/// A trace patch with a source label for audit logs.
pub struct TracePatch {
  source : String
  offset : Int64
  start : Int64
  end : Int64
  changes : Array[Change]
  renamed_signals : Int
} derive(Debug)

///|
/// A signal selection used to reduce a large trace before analysis.
pub struct MergeSelection {
  ids : Array[String]
  paths : Array[String]
  include_vectors : Bool
  include_reals : Bool
} derive(Debug, Eq)

///|
/// Return a default merge policy for two traces with a shared timeline.
pub fn default_merge_options() -> MergeOptions {
  {
    mode: PreserveLeft,
    offset: 0L,
    align_signal: None,
    include_duplicate_changes: false,
    rename_conflicts: false,
    sort_changes: true,
  }
}

///|
/// Return a selection that includes every signal.
pub fn all_merge_selection() -> MergeSelection {
  { ids: [], paths: [], include_vectors: true, include_reals: true }
}

///|
/// Return a selection by identifier.
pub fn merge_selection_ids(ids : Array[String]) -> MergeSelection {
  { ids: ids.copy(), paths: [], include_vectors: true, include_reals: true }
}

///|
/// Return a selection by hierarchical path fragments.
pub fn merge_selection_paths(paths : Array[String]) -> MergeSelection {
  { ids: [], paths: paths.copy(), include_vectors: true, include_reals: true }
}

///|
/// Restrict whether vector declarations are selected.
pub fn MergeSelection::vectors(
  self : MergeSelection,
  enabled : Bool,
) -> MergeSelection {
  { ..self, include_vectors: enabled }
}

///|
/// Restrict whether real declarations are selected.
pub fn MergeSelection::reals(
  self : MergeSelection,
  enabled : Bool,
) -> MergeSelection {
  { ..self, include_reals: enabled }
}

///|
/// Return a copy of a trace with all times shifted by a signed offset.
pub fn shift_trace(trace : Trace, offset : Int64) -> Trace {
  let changes = trace.changes.map(fn(change) {
    { ..change, time: Int64::max(0L, change.time + offset) }
  })
  { ..trace, changes, end_time: Int64::max(0L, trace.end_time + offset) }
}

///|
/// Clip a trace to inclusive time bounds and preserve its declaration shape.
pub fn merge_clip_trace(trace : Trace, start : Int64, end : Int64) -> Trace {
  let low = Int64::min(start, end)
  let high = Int64::max(start, end)
  let changes = trace.changes.filter(fn(change) {
    change.time >= low && change.time <= high
  })
  { ..trace, changes, end_time: Int64::max(0L, high - low) }
}

///|
/// Keep only signals matched by a selection and their changes.
pub fn merge_select_trace(trace : Trace, selection : MergeSelection) -> Trace {
  let signals = trace.signals.filter(fn(signal) {
    selected_signal(signal, selection)
  })
  let ids = signals.map(fn(signal) { signal.id })
  let changes = trace.changes.filter(fn(change) { ids.contains(change.id) })
  { ..trace, signals, changes }
}

///|
/// Rename one signal ID while preserving its display name and path.
pub fn rename_trace_signal(
  trace : Trace,
  old_id : String,
  new_id : String,
) -> Trace {
  let signals = trace.signals.map(fn(signal) {
    if signal.id == old_id {
      { ..signal, id: new_id }
    } else {
      signal
    }
  })
  let changes = trace.changes.map(fn(change) {
    if change.id == old_id {
      { ..change, id: new_id }
    } else {
      change
    }
  })
  { ..trace, signals, changes }
}

///|
/// Rename a sequence of identifiers in declaration order.
pub fn rename_trace_signals(
  trace : Trace,
  pairs : Array[(String, String)],
) -> Trace {
  let mut result = trace
  for pair in pairs {
    result = rename_trace_signal(result, pair.0, pair.1)
  }
  result
}

///|
/// Normalize a trace by sorting changes and optionally removing duplicates.
pub fn normalize_trace_changes(
  trace : Trace,
  include_duplicates : Bool,
) -> Trace {
  let sorted = sort_changes_by_time(trace.changes)
  let changes = if include_duplicates {
    sorted
  } else {
    deduplicate_changes(sorted)
  }
  { ..trace, changes, end_time: maximum_change_time(changes, trace.end_time) }
}

///|
/// Merge two traces under explicit timing and conflict policies.
pub fn merge_traces_with_options(
  left : Trace,
  right : Trace,
  options : MergeOptions,
) -> Trace {
  let offset = merge_offset(left, right, options)
  let shifted_right = shift_trace(right, offset)
  let right_signals = merge_signal_shape(
    left,
    shifted_right,
    options.rename_conflicts,
  )
  let right_changes = remap_conflicting_changes(shifted_right, right_signals)
  let changes = left.changes.copy()
  for change in right_changes {
    if options.include_duplicate_changes || !same_change_exists(changes, change) {
      changes.push(change)
    }
  }
  let ordered = if options.sort_changes {
    sort_changes_by_time(changes)
  } else {
    changes
  }
  {
    header: merge_headers(left.header, right.header),
    signals: merge_signal_declarations(left.signals, right_signals),
    changes: ordered,
    end_time: Int64::max(left.end_time, shifted_right.end_time),
  }
}

///|
/// Overlay a reference trace and a candidate trace into a named pair.
pub fn overlay_traces(
  reference : Trace,
  candidate : Trace,
  reference_prefix : String,
  candidate_prefix : String,
) -> Trace {
  let left = prefix_trace_ids(reference, reference_prefix)
  let right = prefix_trace_ids(candidate, candidate_prefix)
  merge_traces_with_options(left, right, default_merge_options())
}

///|
/// Concatenate traces in sequence, shifting each trace after the previous end.
pub fn concatenate_traces(traces : Array[Trace], gap : Int64) -> Trace? {
  if traces.length() == 0 {
    return None
  }
  let mut result = traces[0]
  let mut cursor = result.end_time + Int64::max(0L, gap)
  for trace in traces[1:] {
    let shifted = shift_trace(trace, cursor)
    result = merge_traces_with_options(result, shifted, default_merge_options())
    cursor = result.end_time + Int64::max(0L, gap)
  }
  Some(result)
}

///|
/// Return a patch describing the selected portion of a trace.
pub fn make_trace_patch(
  trace : Trace,
  source : String,
  start : Int64,
  end : Int64,
  selection : MergeSelection,
) -> TracePatch {
  let selected = merge_select_trace(
    merge_clip_trace(trace, start, end),
    selection,
  )
  {
    source,
    offset: 0L,
    start: Int64::min(start, end),
    end: Int64::max(start, end),
    changes: selected.changes,
    renamed_signals: 0,
  }
}

///|
/// Return whether a patch contains a timestamp.
pub fn TracePatch::contains(self : TracePatch, time : Int64) -> Bool {
  time >= self.start && time <= self.end
}

///|
/// Return stable per-signal change counts after selection.
pub fn selected_change_counts(
  trace : Trace,
  selection : MergeSelection,
) -> Array[(String, Int)] {
  let selected = merge_select_trace(trace, selection)
  selected.signals.map(fn(signal) {
    (
      signal.id,
      selected.changes.count_if(fn(change) { change.id == signal.id }),
    )
  })
}

///|
/// Return a report describing a merge result.
pub fn merge_report(left : Trace, right : Trace, merged : Trace) -> String {
  "left_signals=" +
  left.signals.length().to_string() +
  " right_signals=" +
  right.signals.length().to_string() +
  " merged_signals=" +
  merged.signals.length().to_string() +
  " left_changes=" +
  left.changes.length().to_string() +
  " right_changes=" +
  right.changes.length().to_string() +
  " merged_changes=" +
  merged.changes.length().to_string() +
  " duration=" +
  merged.duration().to_string()
}

///|
/// Return whether a signal satisfies selection constraints.
fn selected_signal(signal : Signal, selection : MergeSelection) -> Bool {
  let id_match = selection.ids.length() == 0 ||
    selection.ids.contains(signal.id)
  let path = signal_path(signal)
  let path_match = selection.paths.length() == 0 ||
    selection.paths.any(fn(pattern) {
      path == pattern ||
      path.has_prefix(pattern + ".") ||
      path.contains(pattern)
    })
  let kind_match = if signal.kind == "real" {
    selection.include_reals
  } else {
    selection.include_vectors || signal.width <= 1
  }
  id_match && path_match && kind_match
}

///|
/// Compute the right-hand offset according to a merge mode.
fn merge_offset(left : Trace, right : Trace, options : MergeOptions) -> Int64 {
  match options.mode {
    PreserveLeft | PreserveRight => options.offset
    ShiftRightToEnd => left.end_time + Int64::max(0L, options.offset)
    AlignFirstChange => first_time(right) - first_time(left) + options.offset
    AlignNamedSignal =>
      match options.align_signal {
        Some(signal_id) =>
          first_signal_time(left, signal_id) -
          first_signal_time(right, signal_id) +
          options.offset
        None => options.offset
      }
  }
}

///|
/// Return the first observed time or zero for an empty trace.
fn first_time(trace : Trace) -> Int64 {
  if trace.changes.length() == 0 {
    0L
  } else {
    trace.changes[0].time
  }
}

///|
/// Return the first time of a named signal or zero.
fn first_signal_time(trace : Trace, signal_id : String) -> Int64 {
  for change in trace.changes {
    if change.id == signal_id {
      return change.time
    }
  }
  0L
}

///|
/// Prefix IDs to avoid collisions when overlaying separate traces.
fn prefix_trace_ids(trace : Trace, prefix : String) -> Trace {
  let normalized = if prefix == "" { "trace" } else { prefix }
  let signals = trace.signals.map(fn(signal) {
    { ..signal, id: normalized + ":" + signal.id }
  })
  let changes = trace.changes.map(fn(change) {
    { ..change, id: normalized + ":" + change.id }
  })
  { ..trace, signals, changes }
}

///|
/// Merge declarations and keep the first declaration for an identical ID.
fn merge_signal_declarations(
  left : Array[Signal],
  right : Array[Signal],
) -> Array[Signal] {
  let result = left.copy()
  for signal in right {
    if !result.any(fn(item) { item.id == signal.id }) {
      result.push(signal)
    }
  }
  result
}

///|
/// Resolve declaration collisions by deterministic suffixing.
fn merge_signal_shape(
  left : Trace,
  right : Trace,
  rename_conflicts : Bool,
) -> Array[Signal] {
  if !rename_conflicts {
    return right.signals.copy()
  }
  let result : Array[Signal] = []
  for signal in right.signals {
    let mut id = signal.id
    let mut suffix = 1
    while left.has_signal(id) || result.any(fn(item) { item.id == id }) {
      id = signal.id + "_r" + suffix.to_string()
      suffix += 1
    }
    result.push({ ..signal, id, })
  }
  result
}

///|
/// Remap changes using the resolved declarations.
fn remap_conflicting_changes(
  right : Trace,
  right_signals : Array[Signal],
) -> Array[Change] {
  right.changes.map(fn(change) {
    match signal_index(right.signals, change.id) {
      Some(old_index) => { ..change, id: right_signals[old_index].id }
      None => change
    }
  })
}

///|
/// Return whether an identical record already exists.
fn same_change_exists(changes : Array[Change], incoming : Change) -> Bool {
  changes.any(fn(change) {
    change.time == incoming.time &&
    change.id == incoming.id &&
    change.value == incoming.value
  })
}

///|
/// Sort changes by timestamp, ID, then display value using insertion sort.
fn sort_changes_by_time(changes : Array[Change]) -> Array[Change] {
  let result : Array[Change] = []
  for change in changes {
    insert_sorted_change(result, change)
  }
  result
}

///|
/// Insert one change into an ordered array.
fn insert_sorted_change(result : Array[Change], change : Change) -> Unit {
  let mut position = result.length()
  for index in 0.. Bool {
  left.time < right.time ||
  (
    left.time == right.time &&
    (
      left.id < right.id ||
      (left.id == right.id && left.value.display() < right.value.display())
    )
  )
}

///|
/// Remove identical consecutive records after sorting.
fn deduplicate_changes(changes : Array[Change]) -> Array[Change] {
  let result : Array[Change] = []
  for change in changes {
    if result.length() == 0 ||
      !same_change_exists([result[result.length() - 1]], change) {
      result.push(change)
    }
  }
  result
}

///|
/// Return the greatest change time or the supplied fallback.
fn maximum_change_time(changes : Array[Change], fallback : Int64) -> Int64 {
  changes.fold(init=fallback, fn(value, change) {
    Int64::max(value, change.time)
  })
}

///|
/// Return a header with available metadata from both sources.
fn merge_headers(left : Header, right : Header) -> Header {
  {
    date: match left.date {
      Some(_) => left.date
      None => right.date
    },
    version: match left.version {
      Some(_) => left.version
      None => right.version
    },
    timescale: match left.timescale {
      Some(_) => left.timescale
      None => right.timescale
    },
    comment: match (left.comment, right.comment) {
      (Some(a), Some(b)) => Some(a + " | " + b)
      (Some(a), None) => Some(a)
      (None, Some(b)) => Some(b)
      _ => None
    },
  }
}

///|
/// Find a declaration position by ID.
fn signal_index(signals : Array[Signal], id : String) -> Int? {
  for index, signal in signals {
    if signal.id == id {
      return Some(index)
    }
  }
  None
}