///|
/// Approximate sliding window counter: divides time into `slices` fixed
/// sub-windows and admits against the sum of the `slices` sub-windows
/// ending at the current one. That sum covers the trailing window
/// (now - window, now] with an error of at most one sub-window's count,
/// because the true window starts partway through the oldest sub-window
/// summed. Memory is O(slices), not O(events).
/// Each ring slot remembers which sub-window index it was last written
/// for, and a slot read for any other index counts as zero. That
/// bookkeeping is what stops a reused slot from leaking a count written
/// one full ring earlier, and it removes the need for an aging pass.
priv struct SlidingWindowCounter {
  limit : Int32
  slices : Int32
  counts : Array[Int32]
  origins : Array[Int32]
  slice_width : Double
}

///|
fn sliding_window_counter(
  limit : Int32,
  window : Double,
  slices : Int32,
) -> SlidingWindowCounter {
  {
    limit,
    slices,
    counts: Array::make(slices, 0),
    origins: Array::make(slices, -1),
    slice_width: window / slices.to_double(),
  }
}

///|
/// The stored count of sub-window `index`, or zero when the slot it maps
/// to was last written for a different sub-window.
fn SlidingWindowCounter::held_at(
  self : SlidingWindowCounter,
  index : Int32,
) -> Int32 {
  let slot = (index % self.slices + self.slices) % self.slices
  if self.origins[slot] == index {
    self.counts[slot]
  } else {
    0
  }
}

///|
/// The decision for (now, weight) summed over the `slices` sub-windows
/// ending at the current one, without writing anything: the ring is only
/// touched when the event is committed.
fn SlidingWindowCounter::decide(
  self : SlidingWindowCounter,
  now : Double,
  weight : Int32,
) -> Admission {
  let current = (now / self.slice_width).floor().to_int()
  // Sub-windows older than the `slices` ending at `current` lie outside
  // the trailing window and are never summed, so they need no erasure.
  let mut held = 0
  for i in 0..= 0 {
      held += self.held_at(index)
    }
  }
  if held + weight <= self.limit {
    {
      allowed: true,
      retry_after: None,
      tokens: (self.limit - held - weight).to_double(),
    }
  } else {
    // Capacity reappears only when `current` advances and the oldest
    // summed sub-window leaves the range, which happens at the next
    // sub-window boundary.
    {
      allowed: false,
      retry_after: Some((current + 1).to_double() * self.slice_width - now),
      tokens: (self.limit - held).to_double(),
    }
  }
}

///|
fn SlidingWindowCounter::commit(
  self : SlidingWindowCounter,
  now : Double,
  weight : Int32,
  allowed : Bool,
) -> Unit {
  if allowed {
    let current = (now / self.slice_width).floor().to_int()
    let slot = (current % self.slices + self.slices) % self.slices
    if self.origins[slot] != current {
      self.origins[slot] = current
      self.counts[slot] = 0
    }
    self.counts[slot] = self.counts[slot] + weight
  }
}

///|
fn SlidingWindowCounter::check(
  self : SlidingWindowCounter,
  now : Double,
  weight : Int32,
) -> Admission {
  let decision = self.decide(now, weight)
  self.commit(now, weight, decision.allowed)
  decision
}