// Main package file for your library code.
// Put public APIs and shared helpers here.
// Keep blocks small and focused for easy refactors.

///|
pub(all) struct Interval {
  lower : Int64
  upper : Int64
}

///|
pub struct Histogram {
  priv counts : Array[Int64]
  priv mut total : Int64
}

///|
// Integer values below 32 are exact. Each subsequent octave has 16 bins.
let bounds : Array[Int64] = {
  let result = Array::makei(32, i => i.to_int64())
  for exponent in 5..<63 {
    let base = 1L << exponent
    let step = base / 16L
    for sub in 0..<16 {
      result.push(base + sub.to_int64() * step)
    }
  }
  result
}

///|
const MAX_COUNT : Int64 = 9223372036854775807L

///|
pub fn Histogram::new() -> Histogram {
  { counts: Array::make(bounds.length(), 0L), total: 0L, }
}

///|
pub fn Histogram::count(self : Histogram) -> Int64 {
  self.total
}

///|
fn bucket(value : Int64) -> Int32 {
  let mut lo = 0
  let mut hi = bounds.length()
  while lo + 1 < hi {
    let mid = lo + (hi - lo) / 2
    if bounds[mid] <= value {
      lo = mid
    } else {
      hi = mid
    }
  }
  lo
}

///|
fn upper_at(id : Int32) -> Int64 {
  if id + 1 == bounds.length() {
    MAX_COUNT
  } else {
    bounds[id + 1] - 1L
  }
}

///|
pub fn Histogram::record(
  self : Histogram,
  value : Int64,
  count~ : Int64 = 1L,
) -> Bool {
  if value < 0L || count <= 0L || count > MAX_COUNT - self.total {
    return false
  }
  let id = bucket(value)
  self.counts[id] += count
  self.total += count
  true
}

///|
pub fn Histogram::merge(self : Histogram, other : Histogram) -> Bool {
  if other.total > MAX_COUNT - self.total {
    return false
  }
  for id in 0.. Interval? {
  if p < 0 || p > 1000000 || self.total == 0L {
    return None
  }
  let rank = if p == 0 { 1L } else { ceil_fraction(self.total, p) }
  let mut prefix = 0L
  for id in 0..= rank {
      return Some({ lower: bounds[id], upper: upper_at(id), })
    }
  }
  None
}

///|
/// Return lower and upper bounds on the number of observations <= threshold.
pub fn Histogram::count_at_most(
  self : Histogram,
  threshold : Int64,
) -> Interval {
  if threshold < 0L {
    return { lower: 0L, upper: 0L, }
  }
  let last = bucket(threshold)
  let mut lower = 0L
  for id in 0..