///|
/// Immutable prefix counts for repeated queries over one observation set.
pub struct Distribution {
priv prefix : Array[Int64]
priv total : Int64
}
///|
pub fn Histogram::distribution(self : Histogram) -> Distribution {
let mut count = 0L
let prefix = Array::makei(bounds.length(), i => {
count += self.counts[i]
count
})
{ prefix, total: self.total, }
}
///|
pub fn Distribution::count(self : Distribution) -> Int64 {
self.total
}
///|
pub fn Distribution::quantile(self : Distribution, p : Int32) -> 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 lo = 0
let mut hi = self.prefix.length() - 1
while lo < hi {
let mid = lo + (hi - lo) / 2
if self.prefix[mid] < rank {
lo = mid + 1
} else {
hi = mid
}
}
Some({ lower: bounds[lo], upper: upper_at(lo), })
}
///|
pub fn Distribution::count_at_most(
self : Distribution,
threshold : Int64,
) -> Interval {
if threshold < 0L {
return { lower: 0L, upper: 0L, }
}
let index = bucket(threshold)
let upper = self.prefix[index]
let lower = if threshold == upper_at(index) {
upper
} else if index == 0 {
0L
} else {
self.prefix[index - 1]
}
{ lower, upper, }
}
///|
/// Count observations in an inclusive interval without counting the same
/// partially covered bucket twice in the upper bound.
pub fn Distribution::count_between(
self : Distribution,
lower : Int64,
upper : Int64,
) -> Interval? {
if lower < 0L || upper < lower {
return None
}
let first = bucket(lower)
let last = bucket(upper)
let before = if first == 0 { 0L } else { self.prefix[first - 1] }
let possible = self.prefix[last] - before
let exact_start = if lower == bounds[first] {
before
} else {
self.prefix[first]
}
let exact_end = if upper == upper_at(last) {
self.prefix[last]
} else if last == 0 {
0L
} else {
self.prefix[last - 1]
}
Some({
lower: if exact_end < exact_start {
0L
} else {
exact_end - exact_start
},
upper: possible,
})
}