1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
use crate::core::counter::Counter;
use crate::Histogram;

/// An iterator that iterates over histogram quantiles.
pub mod quantile;

/// An iterator that iterates linearly over histogram values.
pub mod linear;

/// An iterator that iterates logarithmically over histogram values.
pub mod log;

/// An iterator that iterates over recorded histogram values.
pub mod recorded;

/// An iterator that iterates over histogram values.
pub mod all;

/// Extra information about the picked point in the histogram provided by the picker.
pub struct PickMetadata {
    /// Supply the quantile iterated to in the last `pick()`, if available. If `None` is provided,
    /// the quantile of the current value will be used instead. Probably only useful for the
    /// quantile iterator.
    quantile_iterated_to: Option<f64>,

    /// Supply the value iterated to in the last `pick()`, if the picker can supply a more useful
    /// value than the largest value represented by the bucket.
    value_iterated_to: Option<u64>,
}

impl PickMetadata {
    fn new(quantile_iterated_to: Option<f64>, value_iterated_to: Option<u64>) -> PickMetadata {
        PickMetadata {
            quantile_iterated_to,
            value_iterated_to,
        }
    }
}

/// A trait for designing an subset iterator over values in a `Histogram`.
pub trait PickyIterator<T: Counter> {
    /// Return `Some` if an `IterationValue` should be emitted at this point.
    ///
    /// `index` is a valid index in the relevant histogram.
    ///
    /// This will be called with the same index until it returns `None`. This enables modes of
    /// iteration that pick different values represented by the same bucket, for instance.
    fn pick(
        &mut self,
        index: usize,
        total_count_to_index: u64,
        count_at_index: T,
    ) -> Option<PickMetadata>;

    /// Should we keep iterating even though the last index with non-zero count has already been
    /// picked at least once?
    ///
    /// This will be called on every iteration once the last index with non-zero count has been
    /// picked, even if the index was not advanced in the last iteration (because `pick()` returned
    /// `Some`).
    fn more(&mut self, index_to_pick: usize) -> bool;
}

/// `HistogramIterator` provides a base iterator for a `Histogram`.
///
/// It will iterate over all discrete values until there are no more recorded values (i.e., *not*
/// necessarily until all bins have been exhausted). To facilitate the development of more
/// sophisticated iterators, a *picker* is also provided, which is allowed to only select some bins
/// that should be yielded. The picker may also extend the iteration to include a suffix of empty
/// bins.
pub struct HistogramIterator<'a, T: 'a + Counter, P: PickyIterator<T>> {
    hist: &'a Histogram<T>,
    total_count_to_index: u64,
    count_since_last_iteration: u64,
    count_at_index: T,
    current_index: usize,
    last_picked_index: Option<usize>,
    max_value_index: usize,
    fresh: bool,
    ended: bool,
    picker: P,
}

/// The value emitted at each step when iterating over a `Histogram`.
#[derive(Debug, PartialEq)]
pub struct IterationValue<T: Counter> {
    value_iterated_to: u64,
    quantile: f64,
    quantile_iterated_to: f64,
    count_at_value: T,
    count_since_last_iteration: u64,
}

impl<T: Counter> IterationValue<T> {
    /// Create a new IterationValue.
    pub fn new(
        value_iterated_to: u64,
        quantile: f64,
        quantile_iterated_to: f64,
        count_at_value: T,
        count_since_last_iteration: u64,
    ) -> IterationValue<T> {
        IterationValue {
            value_iterated_to,
            quantile,
            quantile_iterated_to,
            count_at_value,
            count_since_last_iteration,
        }
    }

    /// The value iterated to. Some iterators provide a specific value inside the bucket, while
    /// others just use the highest value in the bucket.
    pub fn value_iterated_to(&self) -> u64 {
        self.value_iterated_to
    }

    /// Percent of recorded values that are at or below the current bucket.
    /// This is simply the quantile multiplied by 100.0, so if you care about maintaining the best
    /// floating-point precision, use `quantile()` instead.
    pub fn percentile(&self) -> f64 {
        self.quantile * 100.0
    }

    /// Quantile of recorded values that are at or below the current bucket.
    pub fn quantile(&self) -> f64 {
        self.quantile
    }

    /// Quantile iterated to, which may be different than `quantile()` when an iterator provides
    /// information about the specific quantile it's iterating to.
    pub fn quantile_iterated_to(&self) -> f64 {
        self.quantile_iterated_to
    }

    /// Recorded count for values equivalent to `value`
    pub fn count_at_value(&self) -> T {
        self.count_at_value
    }

    /// Number of values traversed since the last iteration step
    pub fn count_since_last_iteration(&self) -> u64 {
        self.count_since_last_iteration
    }
}

impl<'a, T: Counter, P: PickyIterator<T>> HistogramIterator<'a, T, P> {
    fn new(h: &'a Histogram<T>, picker: P) -> HistogramIterator<'a, T, P> {
        HistogramIterator {
            hist: h,
            total_count_to_index: 0,
            count_since_last_iteration: 0,
            count_at_index: T::zero(),
            current_index: 0,
            last_picked_index: None,
            max_value_index: h.index_for(h.max()).expect("Either 0 or an existing index"),
            picker,
            fresh: true,
            ended: false,
        }
    }
}

impl<'a, T: 'a, P> Iterator for HistogramIterator<'a, T, P>
where
    T: Counter,
    P: PickyIterator<T>,
{
    type Item = IterationValue<T>;
    fn next(&mut self) -> Option<Self::Item> {
        // here's the deal: we are iterating over all the indices in the histogram's .count array.
        // however, most of those values (especially towards the end) will be zeros, which the
        // original HdrHistogram implementation doesn't yield (probably with good reason -- there
        // could be a lot of them!). so, what we do instead is iterate over indicies until we reach
        // the total *count*. After that, we iterate only until .more() returns false, at which
        // point we stop completely.

        // rust doesn't support tail call optimization, so we'd run out of stack if we simply
        // called self.next() again at the bottom. instead, we loop when we would have yielded None
        // unless we have ended.
        while !self.ended {
            // have we reached the end?
            if self.current_index == self.hist.distinct_values() {
                self.ended = true;
                return None;
            }

            // Have we already picked the index with the last non-zero count in the histogram?
            if self.last_picked_index >= Some(self.max_value_index) {
                // is the picker done?
                if !self.picker.more(self.current_index) {
                    self.ended = true;
                    return None;
                }
            } else {
                // nope -- alright, let's keep iterating
                assert!(self.current_index < self.hist.distinct_values());

                if self.fresh {
                    // at a new index, and not past the max, so there's nonzero counts to add
                    self.count_at_index = self
                        .hist
                        .count_at_index(self.current_index)
                        .expect("Already checked that current_index is < counts len");

                    self.total_count_to_index = self
                        .total_count_to_index
                        .saturating_add(self.count_at_index.as_u64());
                    self.count_since_last_iteration = self
                        .count_since_last_iteration
                        .saturating_add(self.count_at_index.as_u64());

                    // make sure we don't add this index again
                    self.fresh = false;
                }
            }

            // figure out if picker thinks we should yield this value
            if let Some(metadata) = self.picker.pick(
                self.current_index,
                self.total_count_to_index,
                self.count_at_index,
            ) {
                let quantile = self.total_count_to_index as f64 / self.hist.len() as f64;
                let val = IterationValue {
                    value_iterated_to: metadata.value_iterated_to.unwrap_or_else(|| {
                        self.hist
                            .highest_equivalent(self.hist.value_for(self.current_index))
                    }),
                    quantile,
                    quantile_iterated_to: metadata.quantile_iterated_to.unwrap_or(quantile),
                    count_at_value: self
                        .hist
                        .count_at_index(self.current_index)
                        .expect("current index cannot exceed counts length"),
                    count_since_last_iteration: self.count_since_last_iteration,
                };

                // Note that we *don't* increment self.current_index here. The picker will be
                // exposed to the same value again after yielding. This is to allow a picker to
                // pick multiple times at the same index. An example of this is how the linear
                // picker may be using a step size smaller than the bucket size, so it should
                // step multiple times without advancing the index.

                self.count_since_last_iteration = 0;
                self.last_picked_index = Some(self.current_index);
                return Some(val);
            }

            // check the next entry
            self.current_index += 1;
            self.fresh = true;
        }
        None
    }
}