use crate::core::counter::Counter;
use crate::iterators::{HistogramIterator, PickMetadata, PickyIterator};
use crate::Histogram;
/// An iterator that will yield at quantile steps through the histogram's value range.
pub struct Iter<'a, T: 'a + Counter> {
hist: &'a Histogram<T>,
ticks_per_half_distance: u32,
quantile_to_iterate_to: f64,
reached_end: bool,
}
impl<'a, T: 'a + Counter> Iter<'a, T> {
/// Construct a new iterator. See `Histogram::iter_quantiles` for details.
pub fn new(
hist: &'a Histogram<T>,
ticks_per_half_distance: u32,
) -> HistogramIterator<'a, T, Iter<'a, T>> {
assert!(
ticks_per_half_distance > 0,
"Ticks per half distance must be > 0"
);
HistogramIterator::new(
hist,
Iter {
hist,
ticks_per_half_distance,
quantile_to_iterate_to: 0.0,
reached_end: false,
},
)
}
}
impl<'a, T: 'a + Counter> PickyIterator<T> for Iter<'a, T> {
#[allow(clippy::float_cmp)]
fn pick(&mut self, _: usize, running_total: u64, count_at_index: T) -> Option<PickMetadata> {
if count_at_index == T::zero() {
return None;
}
// This calculation, combined with the `quantile * count` in `value_at_quantile`, tends
// to produce a count_at_quantile that is 1 ulp wrong. That's just the way IEEE754 works.
let current_quantile = running_total as f64 / self.hist.len() as f64;
if current_quantile < self.quantile_to_iterate_to {
return None;
}
// Because there are effectively two quantiles in play (the quantile of the value for the
// bucket we're at aka "value quantile", and the quantile we're iterating to aka "iteration
// quantile", which may be significantly different, especially in highly non-uniform
// distributions), the behavior around 1.0 is a little tricky.
//
// The desired behavior is that we always iterate until the iteration quantile reaches 1.0,
// but if the value quantile reaches 1.0 (by reaching the last index with a non-zero count)
// before that point, we skip the remaining intermediate iterations in that same index and
// jump straight to iteration quantile 1.0.
// This is effectively a policy decision, but it is consistent with other iterators: they
// don't just stop when the quantile reaches 1.0 upon first entering the final bucket.
// At the same time, it's arguably unhelpful to have a bunch of all-but-identical quantile
// ticks, hence skipping the intermediate iterations. (This is also how the Java impl
// behaves.)
//
// Note that it is impossible to have the value quantile lower than the iteration quantile
// since the value quantile incorporates the count for the entire bucket when it's first
// entered, while the hypothetical fractional count that the iteration quantile would use is
// necessarily less than that.
//
// Cases for ending iteration:
// 1. Iteration quantile reaches 1.0 along with the value quantile reaching 1.0 at the max
// value index
// 2. Iteration quantile is below 1.0 when the value quantile reaches 1.0 at the max value
// index
// 3. Same as #1, but not at the max value index because total count has saturated. This
// means that more() will not be called.
// 4. Same as #2, but not at the max value index because total count has saturated. See #3.
if self.reached_end {
// #3, #4 part 2: Need to check here, not just in `more()`: when we see quantile 1.0 and
// set `reached_end`, `more()` will not be called (because we haven't reached the last
// non-zero-count index) so it can't stop iteration, and we must stop it here.
//
// This will be hit for all remaining non-zero-count indices, then control will proceed
// to `more()`.
return None;
}
// #1: If we reach iteration quantile 1.0 at the same time as value quantile 1.0 (because we
// moved to the final non-zero-count index exactly when the iteration ticked over to 1.0),
// we want to emit a value at that point, but not proceed past that.
// #2, last phase: This could also be the second visit to the max value index in the #2 case
// where `quantile_to_iterate_to` has been set to 1.0.
// #3, #4 last phase: Similar, but iteration proceeded normally up to 1.0 without any
// last-bucket skipping because it wasn't at the last bucket.
if self.quantile_to_iterate_to == 1.0 {
// We want to pick this value but not do the math below because it doesn't work when
// quantile >= 1.0.
//
// We also want to prevent any further iteration.
self.reached_end = true;
return Some(PickMetadata::new(Some(1.0), None));
}
// #2, first phase:
// Value quantile reached 1.0 while the iteration quantile is somewhere below 1.0 (it can be
// arbitrarily close to 0 for lopsided histograms). So, we continue with normal quantile
// tick logic for the first time, and pick up the #2 case in `more()` below.
// The choice to maintain fixed-sized "ticks" in each half-distance to 100% [starting from
// 0%], as opposed to a "tick" size that varies with each interval, was made to make the
// steps easily comprehensible and readable to humans. The resulting quantile steps are
// much easier to browse through in a quantile distribution output, for example.
//
// We calculate the number of equal-sized "ticks" that the 0-1 range will be divided by
// at the current scale. The scale is determined by the quantile level we are iterating
// to. The following math determines the tick size for the current scale, and maintain a
// fixed tick size for the remaining "half the distance to 100%" [from either 0% or from
// the previous half-distance]. When that half-distance is crossed, the scale changes and
// the tick size is effectively cut in half.
//
// Calculate the number of times we've halved the distance to 100%, This is 1 at 50%, 2 at
// 75%, 3 at 87.5%, etc. 2 ^ num_halvings is the number of slices that will fit into 100%.
// At 50%, num_halvings would be 1, so 2 ^ 1 would yield 2 slices, etc. At any given number
// of slices, the last slice is what we're going to traverse the first half of. With 1 total
// slice, traverse half to get to 50%. Then traverse half of the last (second) slice to get
// to 75%, etc.
// Minimum of 0 (1.0/1.0 = 1, log 2 of which is 0) so unsigned cast is safe.
// Won't hit the `inf` case because quantile < 1.0, so this should yield an actual number.
let num_halvings = (1.0 / (1.0 - self.quantile_to_iterate_to)).log2() as u32;
// Calculate the total number of ticks in 0-1 given that half of each slice is tick'd.
// The number of slices is 2 ^ num_halvings, and each slice has two "half distances" to
// tick, so we add an extra power of two to get ticks per whole distance.
// Use u64 math so that there's less risk of overflow with large numbers of ticks and data
// that ends up needing large numbers of halvings.
let total_ticks = u64::from(self.ticks_per_half_distance)
.checked_mul(
1_u64
.checked_shl(num_halvings + 1)
.expect("too many halvings"),
)
.expect("too many total ticks");
let increment_size = 1.0_f64 / total_ticks as f64;
let metadata = PickMetadata::new(Some(self.quantile_to_iterate_to), None);
let sum = self.quantile_to_iterate_to + increment_size;
self.quantile_to_iterate_to = if sum == self.quantile_to_iterate_to {
// the iteration has reached the point where the increment is too small to actually
// change an f64 slightly smaller than 1.0, so just short circuit to 1.0.
// This happens easily in case #4, and plausibly in #3: it will iterate up to 1.0
// without any skipping, which will
1.0
} else {
sum
};
Some(metadata)
}
fn more(&mut self, _: usize) -> bool {
// One of the end cases has already declared we're done.
if self.reached_end {
return false;
}
// #2, middle phase: already picked the max-value index once with iteration quantile < 1.0,
// and `more()` is now called (for the first time), so iterate one more time, but jump to
// quantile 1.0 while doing so. We don't set `reached_end` here because we do want 1 more
// iteration.
self.quantile_to_iterate_to = 1.0;
true
}
}