1use crate::json::Value;
11use std::cell::RefCell;
12
13const INITIAL_CAPACITY: usize = 16;
15
16#[derive(Clone, Debug)]
23pub struct TDigest {
24 compression: f64,
25 max_unprocessed: f64,
26 state: RefCell<State>,
27}
28
29#[derive(Clone, Debug)]
30struct State {
31 means: Vec<f64>,
33 weights: Vec<f64>,
35 unprocessed_means: Vec<f64>,
37 unprocessed_weights: Vec<f64>,
38 cumulative: Vec<f64>,
39 processed_weight: f64,
40 unprocessed_weight: f64,
41 min: f64,
42 max: f64,
43}
44
45impl Default for TDigest {
46 fn default() -> Self {
48 TDigest::new(100.0)
49 }
50}
51
52impl PartialEq for TDigest {
53 fn eq(&self, other: &Self) -> bool {
55 self.to_vec() == other.to_vec()
56 }
57}
58
59fn js_max(a: f64, b: f64) -> f64 {
61 if a.is_nan() || b.is_nan() {
62 return f64::NAN;
63 }
64 if a == b {
65 return if a.is_sign_negative() { b } else { a };
66 }
67 if a > b { a } else { b }
68}
69
70fn js_min(a: f64, b: f64) -> f64 {
72 if a.is_nan() || b.is_nan() {
73 return f64::NAN;
74 }
75 if a == b {
76 return if a.is_sign_negative() { a } else { b };
77 }
78 if a < b { a } else { b }
79}
80
81fn binary_search(mut high: usize, compare: impl Fn(usize) -> f64) -> usize {
83 let mut low = 0;
84 while low < high {
85 let mid = low + ((high - low) >> 1);
86 let i = compare(mid);
87 if i == 0.0 {
88 return mid;
89 }
90 if i > 0.0 {
91 low = mid + 1;
92 } else {
93 high = mid;
94 }
95 }
96 low
97}
98
99fn weighted_average(x1: f64, w1: f64, x2: f64, w2: f64) -> f64 {
100 if x1 <= x2 {
101 weighted_average_sorted(x1, w1, x2, w2)
102 } else {
103 weighted_average_sorted(x2, w2, x1, w1)
104 }
105}
106
107fn weighted_average_sorted(x1: f64, w1: f64, x2: f64, w2: f64) -> f64 {
108 let x = (x1 * w1 + x2 * w2) / (w1 + w2);
109 js_max(x1, js_min(x, x2))
110}
111
112impl TDigest {
113 pub fn new(compression: f64) -> Self {
116 let max_unprocessed = compression.ceil() * 8.0;
117 let capacity = if max_unprocessed + 1.0 < INITIAL_CAPACITY as f64 {
118 (max_unprocessed + 1.0).max(0.0) as usize
119 } else {
120 INITIAL_CAPACITY
121 };
122 TDigest {
123 compression,
124 max_unprocessed,
125 state: RefCell::new(State {
126 means: Vec::new(),
127 weights: Vec::new(),
128 unprocessed_means: Vec::with_capacity(capacity),
129 unprocessed_weights: Vec::with_capacity(capacity),
130 cumulative: Vec::new(),
131 processed_weight: 0.0,
132 unprocessed_weight: 0.0,
133 min: f64::MAX,
134 max: -f64::MAX,
135 }),
136 }
137 }
138
139 pub fn from_json(data: &[f64]) -> Result<Self, String> {
142 let mut digest = TDigest::new(data.first().copied().unwrap_or(100.0));
143 if data.len() % 2 != 1 {
144 return Err("Invalid centroids array".into());
145 }
146 for pair in data[1..].chunks(2) {
147 digest.add(pair[0], pair[1]);
148 }
149 Ok(digest)
150 }
151
152 pub fn from_json_value(v: &Value) -> Result<Self, String> {
154 let Some(a) = v.as_array() else {
155 return Err("Expected a TDigest array".into());
156 };
157 let numbers: Option<Vec<f64>> = a.iter().map(Value::as_f64).collect();
158 let numbers = numbers.ok_or("Expected a TDigest array of numbers")?;
159 TDigest::from_json(&numbers)
160 }
161
162 pub fn compression(&self) -> f64 {
164 self.compression
165 }
166
167 pub fn reset(&mut self) {
169 let s = self.state.get_mut();
170 s.means.clear();
171 s.weights.clear();
172 s.unprocessed_means.clear();
173 s.unprocessed_weights.clear();
174 s.cumulative.clear();
175 s.processed_weight = 0.0;
176 s.unprocessed_weight = 0.0;
177 s.min = f64::MAX;
178 s.max = -f64::MAX;
179 }
180
181 pub fn add(&mut self, mean: f64, weight: f64) {
184 if mean.is_nan() || weight <= 0.0 || !weight.is_finite() {
185 return;
186 }
187 let process = {
188 let s = self.state.get_mut();
189 s.unprocessed_means.push(mean);
190 s.unprocessed_weights.push(weight);
191 s.unprocessed_weight += weight;
192 s.unprocessed_means.len() as f64 > self.max_unprocessed
193 };
194 if process {
195 Self::process(self.compression, self.state.get_mut());
196 }
197 }
198
199 pub fn merge(&mut self, other: &TDigest) {
201 let (means, weights) = {
202 let mut s = other.state.borrow_mut();
203 Self::process(other.compression, &mut s);
204 (s.means.clone(), s.weights.clone())
205 };
206 for (m, w) in means.into_iter().zip(weights) {
207 self.add(m, w);
208 }
209 }
210
211 pub fn centroids(&self) -> Vec<(f64, f64)> {
213 let s = self.processed();
214 s.means
215 .iter()
216 .copied()
217 .zip(s.weights.iter().copied())
218 .collect()
219 }
220
221 pub fn count(&self) -> f64 {
223 self.processed().processed_weight
224 }
225
226 pub fn to_vec(&self) -> Vec<f64> {
228 let s = self.processed();
229 let mut data = Vec::with_capacity(1 + 2 * s.means.len());
230 data.push(self.compression);
231 for (m, w) in s.means.iter().zip(&s.weights) {
232 data.push(*m);
233 data.push(*w);
234 }
235 data
236 }
237
238 pub fn to_json(&self) -> Value {
240 Value::Array(self.to_vec().into_iter().map(Value::Number).collect())
241 }
242
243 fn processed(&self) -> std::cell::RefMut<'_, State> {
244 let mut s = self.state.borrow_mut();
245 Self::process(self.compression, &mut s);
246 s
247 }
248
249 fn process(compression: f64, s: &mut State) {
253 if s.unprocessed_means.is_empty() {
254 return;
255 }
256 let (new_means, new_weights) = sorted_unprocessed(s);
257 s.unprocessed_means.clear();
258 s.unprocessed_weights.clear();
259 let n = new_means.len();
260 let p = s.means.len();
261 s.processed_weight += s.unprocessed_weight;
262 s.unprocessed_weight = 0.0;
263 let total = s.processed_weight;
264
265 let mut means = Vec::with_capacity(p + 1);
266 let mut weights = Vec::with_capacity(p + 1);
267 let mut mean = 0.0;
268 let mut weight = 0.0;
269 let mut so_far = 0.0;
270 let mut limit = 0.0;
271 let (mut i, mut j) = (0, 0);
272 while i < n || j < p {
273 let (m, w);
275 if i < n && (j == p || new_means[i] <= s.means[j]) {
276 m = new_means[i];
277 w = new_weights[i];
278 i += 1;
279 } else {
280 m = s.means[j];
281 w = s.weights[j];
282 j += 1;
283 }
284 if so_far + w <= limit {
285 weight += w;
286 mean += (w * (m - mean)) / weight;
287 } else {
288 if weight > 0.0 {
289 means.push(mean);
290 weights.push(weight);
291 }
292 let k = integrated_location(compression, so_far / total);
293 limit = total * integrated_q(compression, k + 1.0);
294 mean = m;
295 weight = w;
296 }
297 so_far += w;
298 }
299 means.push(mean);
300 weights.push(weight);
301
302 s.min = js_min(s.min, means[0]);
303 s.max = js_max(s.max, *means.last().expect("a centroid"));
304 s.means = means;
305 s.weights = weights;
306 }
307
308 fn update_cumulative(s: &mut State) {
309 if s.cumulative.last() == Some(&s.processed_weight) {
312 return;
313 }
314 s.cumulative.resize(s.means.len() + 1, 0.0);
315 let mut prev = 0.0;
316 for i in 0..s.means.len() {
317 let cur = s.weights[i];
318 s.cumulative[i] = prev + cur / 2.0;
319 prev += cur;
320 }
321 let n = s.means.len();
322 s.cumulative[n] = prev;
323 }
324
325 pub fn quantile(&self, q: f64) -> f64 {
328 let mut s = self.processed();
329 Self::update_cumulative(&mut s);
330 if q < 0.0 || q > 1.0 || s.means.is_empty() {
331 return f64::NAN;
332 }
333 if s.means.len() == 1 {
334 return s.means[0];
335 }
336 if q.is_nan() {
337 return f64::NAN;
339 }
340 let index = q * s.processed_weight;
341 if index <= s.weights[0] / 2.0 {
342 return s.min + ((2.0 * index) / s.weights[0]) * (s.means[0] - s.min);
343 }
344 let lower = binary_search(s.cumulative.len(), |i| -s.cumulative[i] + index);
345 if lower >= s.cumulative.len() {
346 return f64::NAN;
349 }
350 if lower + 1 != s.cumulative.len() {
351 let z1 = index - s.cumulative[lower - 1];
352 let z2 = s.cumulative[lower] - index;
353 return weighted_average(s.means[lower - 1], z2, s.means[lower], z1);
354 }
355 let z1 = index - s.processed_weight - s.weights[lower - 1] / 2.0;
356 let z2 = s.weights[lower - 1] / 2.0 - z1;
357 weighted_average(*s.means.last().expect("a centroid"), z1, s.max, z2)
358 }
359
360 pub fn cdf(&self, x: f64) -> f64 {
362 let mut s = self.processed();
363 Self::update_cumulative(&mut s);
364 match s.means.len() {
365 0 => return 0.0,
366 1 => {
367 let width = s.max - s.min;
368 if x <= s.min {
369 return 0.0;
370 }
371 if x >= s.max {
372 return 1.0;
373 }
374 if x - s.min <= width {
375 return 0.5;
377 }
378 return (x - s.min) / width;
379 }
380 _ => {}
381 }
382 if x <= s.min {
383 return 0.0;
384 }
385 if x >= s.max {
386 return 1.0;
387 }
388 let m0 = s.means[0];
389 if x <= m0 {
390 if m0 - s.min > 0.0 {
391 return (((x - s.min) / (m0 - s.min)) * s.weights[0]) / s.processed_weight / 2.0;
392 }
393 return 0.0;
394 }
395 let mn = *s.means.last().expect("a centroid");
396 if x >= mn {
397 if s.max - mn > 0.0 {
398 return 1.0
399 - (((s.max - x) / (s.max - mn)) * s.weights.last().expect("a centroid"))
400 / s.processed_weight
401 / 2.0;
402 }
403 return 1.0;
404 }
405 let upper = binary_search(s.means.len(), |i| {
407 let d = x - s.means[i];
408 if d == 0.0 || d.is_nan() { 1.0 } else { d }
409 });
410 let z1 = x - s.means[upper - 1];
411 let z2 = s.means[upper] - x;
412 weighted_average(s.cumulative[upper - 1], z2, s.cumulative[upper], z1) / s.processed_weight
413 }
414}
415
416fn sorted_unprocessed(s: &State) -> (Vec<f64>, Vec<f64>) {
418 let means = &s.unprocessed_means;
419 let weights = &s.unprocessed_weights;
420 if means
422 .windows(2)
423 .all(|w| w[1].partial_cmp(&w[0]) != Some(std::cmp::Ordering::Less))
424 {
425 return (means.clone(), weights.clone());
426 }
427 if weights.iter().all(|w| *w == weights[0]) {
430 let mut sorted = means.clone();
431 sorted.sort_by(f64::total_cmp);
432 return (sorted, weights.clone());
433 }
434 let mut order: Vec<usize> = (0..means.len()).collect();
436 order.sort_by(|&a, &b| {
437 let d = means[a] - means[b];
438 if d < 0.0 {
439 std::cmp::Ordering::Less
440 } else if d > 0.0 {
441 std::cmp::Ordering::Greater
442 } else {
443 std::cmp::Ordering::Equal
444 }
445 });
446 (
447 order.iter().map(|&k| means[k]).collect(),
448 order.iter().map(|&k| weights[k]).collect(),
449 )
450}
451
452fn integrated_q(compression: f64, k: f64) -> f64 {
453 ((js_min(k, compression) * std::f64::consts::PI / compression - std::f64::consts::PI / 2.0)
454 .sin()
455 + 1.0)
456 / 2.0
457}
458
459fn integrated_location(compression: f64, q: f64) -> f64 {
460 (compression * ((2.0 * q - 1.0).asin() + std::f64::consts::PI / 2.0)) / std::f64::consts::PI
461}
462
463#[cfg(test)]
464mod tests {
465 use super::*;
466
467 #[test]
468 fn quantiles_of_a_few_values() {
469 let mut d = TDigest::default();
470 assert!(d.quantile(0.5).is_nan());
471 for v in [1.0, 2.0, 3.0, 4.0] {
472 d.add(v, 1.0);
473 }
474 assert_eq!(d.count(), 4.0);
475 assert_eq!(d.quantile(0.0), 1.0);
476 assert_eq!(d.quantile(1.0), 4.0);
477 assert_eq!(
478 d.to_vec(),
479 vec![100.0, 1.0, 1.0, 2.0, 1.0, 3.0, 1.0, 4.0, 1.0]
480 );
481 let back = TDigest::from_json(&d.to_vec()).unwrap();
482 assert_eq!(back, d);
483 assert!(TDigest::from_json(&[100.0, 1.0]).is_err());
484 }
485
486 #[test]
487 fn js_min_max() {
488 assert!(js_max(1.0, f64::NAN).is_nan());
489 assert!(js_max(-0.0, 0.0).is_sign_positive());
490 assert!(js_min(0.0, -0.0).is_sign_negative());
491 }
492}