///|
/// A bounded time bucket containing changes from one or more signals.
pub struct TimeBucket {
  start : Int64
  end : Int64
  changes : Array[Change]
  mut signal_count : Int
} derive(Debug)

///|
/// Select events by identifier and inclusive time window.
pub struct EventFilter {
  signal_ids : Array[String]
  start : Int64
  end : Int64
  include_unknown : Bool
} derive(Debug, Eq)

///|
/// Create an event filter for the complete trace.
pub fn default_event_filter(trace : Trace) -> EventFilter {
  {
    signal_ids: trace_signal_ids(trace),
    start: 0L,
    end: trace.end_time,
    include_unknown: true,
  }
}

///|
/// Filter changes without changing their source order.
pub fn filter_events(trace : Trace, filter : EventFilter) -> Array[Change] {
  trace.changes.filter(fn(change) {
    let id_ok = filter.signal_ids.length() == 0 ||
      filter.signal_ids.contains(change.id)
    let time_ok = change.time >= filter.start && change.time <= filter.end
    let value_ok = filter.include_unknown || !change.value.is_unknown()
    id_ok && time_ok && value_ok
  })
}

///|
/// Partition events into equal-width timestamp buckets.
pub fn bucket_changes(trace : Trace, bucket_width : Int64) -> Array[TimeBucket] {
  let width = Int64::max(1L, bucket_width)
  let changes = trace.changes
  let result : Array[TimeBucket] = []
  for change in changes {
    let start = change.time / width * width
    let end = start + width
    match result.search_by(fn(bucket) { bucket.start == start }) {
      Some(index) => {
        let bucket = result[index]
        let had_signal = bucket.changes.any(fn(item) { item.id == change.id })
        bucket.changes.push(change)
        if !had_signal {
          bucket.signal_count += 1
        }
      }
      None => result.push({ start, end, changes: [change], signal_count: 1 })
    }
  }
  result.sort_by(fn(left, right) {
    if left.start < right.start {
      -1
    } else if left.start > right.start {
      1
    } else {
      0
    }
  })
  result
}

///|
/// Return the number of changes per time bucket.
pub fn change_density(
  trace : Trace,
  bucket_width : Int64,
) -> Array[(Int64, Int)] {
  bucket_changes(trace, bucket_width).map(fn(bucket) {
    (bucket.start, bucket.changes.length())
  })
}

///|
/// Return the maximum number of changes in a bucket.
pub fn peak_change_density(trace : Trace, bucket_width : Int64) -> Int {
  bucket_changes(trace, bucket_width).fold(init=0, fn(current, bucket) {
    Int::max(current, bucket.changes.length())
  })
}

///|
/// Combine writes at the same timestamp by keeping the final write per signal.
pub fn coalesce_events(changes : Array[Change]) -> Array[Change] {
  let result : Array[Change] = []
  for change in changes {
    let previous_index = result.search_by(fn(item) {
      item.time == change.time && item.id == change.id
    })
    match previous_index {
      Some(index) => result[index] = change
      None => result.push(change)
    }
  }
  result
}

///|
/// Fold every selected change in source order.
pub fn[A] fold_events(
  trace : Trace,
  filter : EventFilter,
  init : A,
  step : (A, Change) -> A,
) -> A {
  filter_events(trace, filter).fold(init~, fn(state, change) {
    step(state, change)
  })
}

///|
/// Return all events for a group of identifiers, sorted by time.
pub fn merged_signal_events(
  trace : Trace,
  signal_ids : Array[String],
) -> Array[Change] {
  let result = changes_for_ids(trace, signal_ids)
  result.sort_by(fn(left, right) {
    if left.time < right.time {
      -1
    } else if left.time > right.time {
      1
    } else {
      0
    }
  })
  result
}

///|
/// Return the first event in each non-empty time bucket.
pub fn bucket_first_changes(
  trace : Trace,
  bucket_width : Int64,
) -> Array[Change] {
  bucket_changes(trace, bucket_width).filter_map(fn(bucket) {
    bucket.changes.get(0)
  })
}

///|
/// Render a density table suitable for a CI artifact.
pub fn density_report(trace : Trace, bucket_width : Int64) -> String {
  let out : Array[String] = ["bucket_start,changes"]
  for item in change_density(trace, bucket_width) {
    out.push(item.0.to_string() + "," + item.1.to_string())
  }
  out.join("\n")
}