///|
pub(all) struct Witness {
  position : Int32
  time : Int64
}

///|
struct CandidateQueue {
  mut items : Array[Witness]
  mut head : Int32
}

///|
fn CandidateQueue::new() -> CandidateQueue {
  { items: [], head: 0, }
}

///|
/// Advancing a logical head avoids shifting all retained candidates per event.
/// Compact after at least 32 consumed entries and at least half the allocation.
fn CandidateQueue::commit(
  self : CandidateQueue,
  head : Int32,
  added : Witness?,
) -> Unit {
  self.head = head
  if self.head == self.items.length() {
    self.items = []
    self.head = 0
  } else if self.head >= 32 && self.head >= self.items.length() / 2 {
    self.items = self.items[self.head:].to_owned()
    self.head = 0
  }
  if added is Some(value) {
    self.items.push(value)
  }
}

///|
pub(all) struct MonitorStats {
  processed : Int32
  graph_nodes : Int32
  retained_candidates : Int32
  peak_candidates : Int32
  node_updates : Int64
}

///|
pub struct Decision {
  priv position : Int32
  priv time : Int64
  priv names : Array[String]
  priv values : Array[Bool]
}

///|
pub fn Decision::position(self : Decision) -> Int32 {
  self.position
}

///|
pub fn Decision::timestamp(self : Decision) -> Int64 {
  self.time
}

///|
pub fn Decision::values(self : Decision) -> Array[Bool] {
  self.values.copy()
}

///|
pub fn Decision::names(self : Decision) -> Array[String] {
  self.names.copy()
}

///|
pub fn Decision::value(self : Decision, name : String) -> Bool? {
  for i in 0.. Bool {
  for value in self.values {
    if !value {
      return false
    }
  }
  true
}

///|
/// A monitor owns all mutable queues and prior values; plans may be shared.
/// It stores witnesses, not the complete input trace. One push is atomic on
/// validation or capacity errors: callers may retry the same timestamp.
pub struct Monitor {
  priv plan : Plan
  priv queues : Array[CandidateQueue]
  priv staged_heads : Array[Int32]
  priv staged_additions : Array[Witness?]
  priv mut last_values : Array[Bool]
  priv mut scratch_values : Array[Bool]
  priv mut witnesses : Array[Witness?]
  priv mut staged_witnesses : Array[Witness?]
  priv barriers : Array[Witness?]
  priv mut last_time : Int64?
  priv mut processed : Int32
  priv mut retained : Int32
  priv mut peak : Int32
}

///|
pub fn Monitor::new(plan : Plan) -> Monitor {
  let queues : Array[CandidateQueue] = []
  for _ in plan.nodes {
    queues.push(CandidateQueue::new())
  }
  {
    plan,
    queues,
    staged_heads: Array::make(plan.nodes.length(), 0),
    staged_additions: Array::make(plan.nodes.length(), None),
    last_values: Array::make(plan.nodes.length(), false),
    scratch_values: Array::make(plan.nodes.length(), false),
    witnesses: Array::make(plan.nodes.length(), None),
    staged_witnesses: Array::make(plan.nodes.length(), None),
    barriers: Array::make(plan.nodes.length(), None),
    last_time: None,
    processed: 0,
    retained: 0,
    peak: 0,
  }
}

///|
pub fn Monitor::stats(self : Monitor) -> MonitorStats {
  {
    processed: self.processed,
    graph_nodes: self.plan.nodes.length(),
    retained_candidates: self.retained,
    peak_candidates: self.peak,
    node_updates: self.processed.to_int64() *
    self.plan.nodes.length().to_int64(),
  }
}

///|
pub fn Monitor::plan(self : Monitor) -> Plan {
  self.plan
}

///|
pub fn Monitor::push(
  self : Monitor,
  event : Observation,
) -> Result[Decision, MonitorError] {
  if self.processed >= self.plan.limits.events {
    return Err(ResourceLimit("monitor event count"))
  }
  if self.last_time is Some(previous) && event.time <= previous {
    return Err(InvalidTimestamp(self.processed))
  }
  match self.plan.validate_observation(event, self.processed) {
    Err(e) => return Err(e)
    Ok(_) => ()
  }
  let size = self.plan.nodes.length()
  let values = self.scratch_values
  let heads = self.staged_heads
  let additions = self.staged_additions
  // Only Prior and queue-backed nodes have witnesses; each overwrites its slot.
  let witnesses = self.staged_witnesses
  let mut retained = 0
  let current = Witness::{ position: self.processed, time: event.time, }
  for id in 0.. values[id] = value
      Input(name) => values[id] = event.values.get(name).unwrap()
      Neg(child) => values[id] = !values[child]
      Both(a, b) => values[id] = values[a] && values[b]
      Either(a, b) => values[id] = values[a] || values[b]
      Implication(a, b) => values[id] = !values[a] || values[b]
      Prior(child) => {
        values[id] = self.processed > 0 && self.last_values[child]
        witnesses[id] = self.last_time.map(time => Witness::{
          position: self.processed - 1,
          time,
        })
      }
      AnyPast(window, child)
      | AllPast(window, child)
      | SincePast(window, child, _) => {
        let queue = self.queues[id]
        let mut head = queue.head
        let universal = node is AllPast(_, _)
        let mut add = if universal { !values[child] } else { values[child] }
        match node {
          SincePast(_, left, right) => {
            if !values[left] {
              head = queue.items.length()
            }
            add = values[right]
          }
          _ => ()
        }
        head = queue.first_live(head, event.time, window.upper)
        heads[id] = head
        additions[id] = if add { Some(current) } else { None }
        let candidate = if head < queue.items.length() {
          Some(queue.items[head])
        } else {
          additions[id]
        }
        let eligible = match candidate {
          Some(value) if event.time - value.time >= window.lower => Some(value)
          _ => None
        }
        witnesses[id] = eligible
        values[id] = if universal {
          eligible is None
        } else {
          eligible is Some(_)
        }
        retained += queue.items.length() - head + (if add { 1 } else { 0 })
        if retained > self.plan.limits.candidates {
          return Err(ResourceLimit("retained temporal candidates"))
        }
      }
    }
  }
  // The compiler records exactly the nodes owning temporal queues.
  for id in self.plan.temporal_nodes {
    self.queues[id].commit(heads[id], additions[id])
    if self.plan.nodes[id] is SincePast(_, left, _) && !values[left] {
      self.barriers[id] = Some(current)
    }
  }
  let output : Array[Bool] = []
  for root in self.plan.roots {
    output.push(values[root])
  }
  let decision = Decision::{
    position: self.processed,
    time: event.time,
    names: self.plan.names.copy(),
    values: output,
  }
  let previous_values = self.last_values
  self.last_values = values
  self.scratch_values = previous_values
  self.staged_witnesses = self.witnesses
  self.witnesses = witnesses
  self.last_time = Some(event.time)
  self.processed += 1
  self.retained = retained
  if retained > self.peak {
    self.peak = retained
  }
  Ok(decision)
}

///|
pub fn Monitor::last_decision(self : Monitor) -> Decision? {
  match self.last_time {
    None => None
    Some(time) => {
      let values : Array[Bool] = []
      for root in self.plan.roots {
        values.push(self.last_values[root])
      }
      Some({
        position: self.processed - 1,
        time,
        names: self.plan.names.copy(),
        values,
      })
    }
  }
}

///|
/// Fast paths cover no expiration, one expiration and a fully expired queue.
/// Larger partial expiration jumps use lower-bound search instead of scanning.
fn CandidateQueue::first_live(
  self : CandidateQueue,
  head : Int32,
  time : Int64,
  upper : Int64,
) -> Int32 {
  let end = self.items.length()
  if head == end || time - self.items[head].time <= upper {
    return head
  }
  if time - self.items[end - 1].time > upper {
    return end
  }
  let mut low = head + 1
  if time - self.items[low].time <= upper {
    return low
  }
  let mut high = end - 1
  while low < high {
    let middle = low + (high - low) / 2
    if time - self.items[middle].time > upper {
      low = middle + 1
    } else {
      high = middle
    }
  }
  low
}