This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new 8ea7899 feat(kll): add weighted update (#293)
8ea7899 is described below
commit 8ea78996c96150d104c50c98617343dd004de178
Author: Shani Elharrar <[email protected]>
AuthorDate: Thu Nov 19 11:17:25 2026 +0200
feat(kll): add weighted update (#293)
Co-authored-by: Claude Opus 5.5 <[email protected]>
Co-authored-by: tison <[email protected]>
---
CHANGELOG.md | 1 +
CONTRIBUTING.md | 12 +-
datasketches/src/kll/sketch.rs | 143 +++++++++++--
tests-integration/tests/kll_test/main.rs | 1 +
tests-integration/tests/kll_test/update.rs | 322 +++++++++++++++++++++++++++++
5 files changed, 458 insertions(+), 21 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index fb67c46..526468e 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -7,6 +7,7 @@ All significant changes to this project will be documented in
this file.
### New features
* Add `DensitySketch`, `Kernel`, `GaussianKernel`, `DensityValue`, and
`DensitySketchIter` behind the `density` feature for streaming kernel density
estimation and coreset construction over multidimensional `f32` and `f64`
vectors, with custom kernel support, merging, iteration, and cross-language
serialization.
+* Add `KllSketch::update_with_weight` for updating a sketch with an item
repeated a given number of times.
### Performance improvements
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
index b49d8e5..67d39b6 100644
--- a/CONTRIBUTING.md
+++ b/CONTRIBUTING.md
@@ -103,11 +103,19 @@ When adding or resizing a scenario, use `--rounds` to
select a suitable fixed co
- Describe types with noun phrases and API behavior with third-person
present-tense verbs such as `Creates`, `Updates`, and `Returns`.
- End summary sentences with punctuation, and format Rust identifiers,
literals, and numeric ranges as inline code.
-- Put contract sections and compatibility notes before examples. When
applicable, order sections as `# Errors`, `# Panics`, and `# Examples`. Include
only sections that describe an actual contract.
+- Put contract and compatibility sections before examples. When applicable,
order sections as `# Errors`, `# Panics`, `# Cross-language compatibility`, and
`# Examples`, including only sections that apply.
- Document return values and error conditions on the relevant methods rather
than repeating them in crate or module overviews.
-- Describe shared capabilities in language-neutral terms. Name another
implementation when it clarifies interoperability requirements, a specific
source, a format variant, or a behavior difference. Retain useful
implementation references in internal comments.
+- Describe this crate's own capabilities and contracts in language-neutral
terms first. Name another implementation (`DataSketches Java`, `DataSketches
C++`, `DataSketches Go`, or `DataSketches Python`) only when documenting
interoperability requirements, format variants, or behavior differences; retain
repository references such as `datasketches-java` in internal code comments.
- Keep imports visible in doctests. A trailing hidden `Ok(...)` may be used to
support `?`.
+### Cross-language compatibility
+
+Use consistent patterns for the three kinds of cross-language guidance:
+
+- **Serialization interchange**: On `serialize` methods, state `The serialized
data can be read by other DataSketches implementations [when ...].` On
`deserialize` methods, state `Also accepts data serialized by other
DataSketches implementations [when ...].` State any format-specific caveats
(such as unstored configuration or incompatible counter mappings) immediately
after that sentence.
+- **Hash input encoding**: On modules whose operations hash caller inputs, add
a `# Cross-language hashing` section listing the required `hash::value`
wrappers (`raw_bytes`, `canonical_float`, and `sign_extend` or
`natural_extend`) and any empty-input handling needed to match peer
implementations.
+- **API behavior and range differences**: When a method or type intentionally
differs from peer implementations in accepted inputs, edge-case behavior, or
value bounds, keep the summary and `# Errors` or `# Panics` sections focused on
the Rust contract and record the difference under `# Cross-language
compatibility`. Name the peer implementations, contrast their behavior or
domain with this crate's behavior, and state any narrower bound callers must
stay within when exchanging serialized [...]
+
## Query semantics
- Validate query arguments before handling an empty sketch. Invalid arguments
return `InvalidArgument` regardless of whether the sketch is empty.
diff --git a/datasketches/src/kll/sketch.rs b/datasketches/src/kll/sketch.rs
index 950e1c2..48b9994 100644
--- a/datasketches/src/kll/sketch.rs
+++ b/datasketches/src/kll/sketch.rs
@@ -164,6 +164,70 @@ impl<T: Clone + Ord> KllSketch<T> {
self.internal_update(item);
}
+ /// Updates the sketch with an item repeated `weight` times.
+ ///
+ /// Equivalent to calling [`update`](Self::update) `weight` times. Weights
that fit in the
+ /// remaining capacity are appended directly to level zero; larger weights
build an exact
+ /// binary-level representation and merge it in one pass. A weight of `0`
is a no-op.
+ ///
+ /// # Panics
+ ///
+ /// Panics without modifying the sketch if the stream weight would exceed
[`u64::MAX`].
+ ///
+ /// # Cross-language compatibility
+ ///
+ /// DataSketches Java and DataSketches C++ reject weights of `0` and
weights above `2^61 - 1`.
+ /// This method treats `0` as a no-op and accepts weights up to
[`u64::MAX`], folding bits at or
+ /// above level `60` into level `60`. DataSketches Java reads serialized
stream weights as
+ /// signed 64-bit integers, so keep [`total_weight`](Self::total_weight)
at or below
+ /// `i64::MAX as u64` when serializing sketches for Java.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::common::SearchCriteria;
+ /// use datasketches::kll::KllSketch;
+ ///
+ /// let mut sketch = KllSketch::<i64>::new(200)?;
+ /// sketch.update_with_weight(1, 3);
+ /// sketch.update_with_weight(2, 1_000_000);
+ /// assert_eq!(sketch.total_weight(), 1_000_003);
+ /// assert_eq!(
+ /// sketch.rank(&1, SearchCriteria::Inclusive),
+ /// Some(3.0 / 1_000_003.0)
+ /// );
+ /// # Ok::<(), datasketches::error::Error>(())
+ /// ```
+ pub fn update_with_weight(&mut self, item: T, weight: u64) {
+ if weight == 0 {
+ return;
+ }
+ if weight == 1 {
+ self.update(item);
+ return;
+ }
+ let final_n = self
+ .n
+ .checked_add(weight)
+ .expect("total stream weight overflow");
+
+ let free_capacity = self.capacity - self.num_retained;
+ if weight <= free_capacity as u64 {
+ let count = weight as usize;
+ self.levels[0].reserve(count);
+ self.update_min_max(&item);
+ for _ in 1..count {
+ self.levels[0].push(item.clone());
+ }
+ self.levels[0].push(item);
+ self.n = final_n;
+ self.num_retained += count;
+ self.is_level_zero_sorted = false;
+ } else {
+ self.merge_weighted(item, weight, final_n);
+ }
+ }
+
/// Resets this sketch to its empty state while retaining its
configuration.
pub fn reset(&mut self) {
self.min_k = self.k;
@@ -826,29 +890,58 @@ impl<T: Clone + Ord> KllSketch<T> {
fn merge_higher_levels(&mut self, other: &KllSketch<T>) {
let provisional_levels = self.levels.len().max(other.levels.len());
- let mut self_levels = std::mem::take(&mut self.levels);
- let mut work_levels = vec![Vec::new(); provisional_levels];
- work_levels[0] = std::mem::take(&mut self_levels[0]);
+ let mut work_levels = std::mem::take(&mut self.levels);
+ work_levels.resize_with(provisional_levels, Vec::new);
- for level in 1..provisional_levels {
- let left = if level < self_levels.len() {
- std::mem::take(&mut self_levels[level])
- } else {
- Vec::new()
- };
- let right = other.levels.get(level).cloned().unwrap_or_default();
+ for (work_level, other_level) in
work_levels.iter_mut().zip(&other.levels).skip(1) {
+ if !other_level.is_empty() {
+ merge_into_level(work_level, other_level.clone());
+ }
+ }
- work_levels[level] = if left.is_empty() {
- right
- } else if right.is_empty() {
- left
- } else {
- merge_sorted_vec(left, right)
- };
+ self.levels = general_compress(work_levels, self.k,
self.is_level_zero_sorted);
+ self.refresh_capacity_state();
+ }
+
+ fn merge_weighted(&mut self, item: T, weight: u64, final_n: u64) {
+ debug_assert!(weight >= 2);
+ self.update_min_max(&item);
+ if weight & 1 != 0 {
+ self.internal_update(item.clone());
+ }
+
+ // An item at level `h` carries weight `2^h`, so `(weight >> h) & 1`
copies at each level
+ // form an exact representation of `weight` copies. Bits at or above
`MAX_NUM_LEVELS - 1`
+ // fold into `weight >> (MAX_NUM_LEVELS - 1)` (at most 15) copies at
the top level.
+ let num_levels = ((u64::BITS - weight.leading_zeros()) as
usize).min(MAX_NUM_LEVELS);
+ let top_level = num_levels - 1;
+ let provisional_levels = self.levels.len().max(num_levels);
+ let mut work_levels = std::mem::take(&mut self.levels);
+ work_levels.resize_with(provisional_levels, Vec::new);
+
+ for (level, work_level) in
work_levels.iter_mut().enumerate().take(top_level).skip(1) {
+ if (weight >> level) & 1 != 0 {
+ merge_into_level(work_level, vec![item.clone()]);
+ }
}
+ let top_count = (weight >> top_level) as usize;
+ let mut top_items = Vec::with_capacity(top_count);
+ for _ in 1..top_count {
+ top_items.push(item.clone());
+ }
+ top_items.push(item);
+ merge_into_level(&mut work_levels[top_level], top_items);
+
self.levels = general_compress(work_levels, self.k,
self.is_level_zero_sorted);
self.refresh_capacity_state();
+ self.n = final_n;
+
+ debug_assert_eq!(
+ self.levels_weight(),
+ self.n,
+ "total weight does not match n"
+ );
}
fn refresh_capacity_state(&mut self) {
@@ -1014,7 +1107,19 @@ fn downsample<T, I: ExactSizeIterator<Item = T>>(items:
I, offset: bool, use_up:
.collect()
}
-fn merge_sorted_vec<T: Clone + Ord>(left: Vec<T>, right: Vec<T>) -> Vec<T> {
+fn merge_into_level<T: Ord>(target: &mut Vec<T>, right: Vec<T>) {
+ if right.is_empty() {
+ return;
+ }
+ let left = std::mem::take(target);
+ *target = if left.is_empty() {
+ right
+ } else {
+ merge_sorted_vec(left, right)
+ };
+}
+
+fn merge_sorted_vec<T: Ord>(left: Vec<T>, right: Vec<T>) -> Vec<T> {
let mut merged = Vec::with_capacity(left.len() + right.len());
let mut left_iter = left.into_iter().peekable();
let mut right_iter = right.into_iter().peekable();
@@ -1031,7 +1136,7 @@ fn merge_sorted_vec<T: Clone + Ord>(left: Vec<T>, right:
Vec<T>) -> Vec<T> {
merged
}
-fn general_compress<T: Clone + Ord>(
+fn general_compress<T: Ord>(
mut levels_in: Vec<Vec<T>>,
k: u16,
is_level_zero_sorted: bool,
diff --git a/tests-integration/tests/kll_test/main.rs
b/tests-integration/tests/kll_test/main.rs
index 26441bc..7754cc0 100644
--- a/tests-integration/tests/kll_test/main.rs
+++ b/tests-integration/tests/kll_test/main.rs
@@ -19,3 +19,4 @@ mod core;
mod generic;
mod merge;
mod query;
+mod update;
diff --git a/tests-integration/tests/kll_test/update.rs
b/tests-integration/tests/kll_test/update.rs
new file mode 100644
index 0000000..2dd6f74
--- /dev/null
+++ b/tests-integration/tests/kll_test/update.rs
@@ -0,0 +1,322 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::panic::AssertUnwindSafe;
+use std::panic::catch_unwind;
+
+use datasketches::common::SearchCriteria;
+use datasketches::kll::KllSketch;
+
+const DEFAULT_K: u16 = 200;
+const MIN_K: u16 = 8;
+const NUMERIC_NOISE_TOLERANCE: f64 = 1e-6;
+
+#[test]
+fn zero_weight_is_a_no_op() {
+ let mut sketch = KllSketch::<i64>::new(DEFAULT_K).unwrap();
+ sketch.update_with_weight(10, 0);
+ assert!(sketch.is_empty());
+ assert_eq!(sketch.total_weight(), 0);
+ assert_eq!(sketch.num_retained(), 0);
+ assert_eq!(sketch.min_item(), None);
+ assert_eq!(sketch.max_item(), None);
+
+ sketch.update_with_weight(10, 5);
+ let before = sketch.serialize();
+ sketch.update_with_weight(-100, 0);
+ sketch.update_with_weight(100, 0);
+ assert_eq!(sketch.min_item(), Some(&10));
+ assert_eq!(sketch.max_item(), Some(&10));
+ assert_eq!(sketch.serialize(), before);
+}
+
+#[test]
+fn exact_mode_and_capacity_boundary_match_repeated_updates() {
+ let mut weighted = KllSketch::<i64>::new(DEFAULT_K).unwrap();
+ let mut repeated = KllSketch::<i64>::new(DEFAULT_K).unwrap();
+
+ // Weights 1..=15 sum to 120; adding 80 reaches the exact k=200 capacity
boundary.
+ for (item, weight) in (1..=15).map(|i| (i, i as u64)).chain([(16, 80)]) {
+ weighted.update_with_weight(item, weight);
+ for _ in 0..weight {
+ repeated.update(item);
+ }
+ }
+
+ assert_eq!(weighted.total_weight(), DEFAULT_K as u64);
+ assert_eq!(weighted.num_retained(), DEFAULT_K as usize);
+ assert!(!weighted.is_estimation_mode());
+ assert_eq!(weighted.serialize(), repeated.serialize());
+
+ // One additional unit crosses capacity and triggers compaction on the
weight == 1 path.
+ weighted.update_with_weight(17, 1);
+ assert_eq!(weighted.total_weight(), DEFAULT_K as u64 + 1);
+ assert!(weighted.is_estimation_mode());
+ assert_eq!(weighted.max_item(), Some(&17));
+}
+
+#[test]
+fn binary_level_decomposition_and_top_level_folding() {
+ // Cover both an even weight (leaving level zero empty) and an odd
multi-bit weight.
+ for weight in [1u64 << 40, (1u64 << 40) + 12_345] {
+ let mut sketch = KllSketch::<i64>::new(DEFAULT_K).unwrap();
+ sketch.update_with_weight(7, weight);
+
+ assert_eq!(sketch.total_weight(), weight);
+ assert!(sketch.is_estimation_mode());
+ assert_eq!(sketch.num_retained(), weight.count_ones() as usize);
+ assert_eq!(sketch.sorted_view().total_weight(), weight);
+ assert_eq!(sketch.min_item(), Some(&7));
+ assert_eq!(sketch.max_item(), Some(&7));
+ assert_eq!(sketch.rank(&7, SearchCriteria::Inclusive), Some(1.0));
+ assert_eq!(sketch.rank(&7, SearchCriteria::Exclusive), Some(0.0));
+ assert_eq!(
+ sketch.quantile(0.5, SearchCriteria::Inclusive).unwrap(),
+ Some(7)
+ );
+
+ let bytes = sketch.serialize();
+ let decoded = KllSketch::<i64>::deserialize(&bytes).unwrap();
+ assert_eq!(decoded.serialize(), bytes);
+ }
+
+ // At MIN_K = 8, folding u64::MAX - 8 places 15 copies at level 60 (above
level_capacity = 8)
+ // without overflowing MAX_NUM_LEVELS (61).
+ let mut sketch = KllSketch::<i64>::new(MIN_K).unwrap();
+ for item in 1..=8 {
+ sketch.update(item);
+ }
+ sketch.update_with_weight(9, u64::MAX - 8);
+
+ assert_eq!(sketch.total_weight(), u64::MAX);
+ assert_eq!(sketch.sorted_view().total_weight(), u64::MAX);
+ assert_eq!(sketch.min_item(), Some(&1));
+ assert_eq!(sketch.max_item(), Some(&9));
+ assert_eq!(
+ sketch.quantile(0.0, SearchCriteria::Inclusive).unwrap(),
+ Some(1)
+ );
+ assert_eq!(
+ sketch.quantile(0.5, SearchCriteria::Inclusive).unwrap(),
+ Some(9)
+ );
+ assert_eq!(
+ sketch.quantile(1.0, SearchCriteria::Inclusive).unwrap(),
+ Some(9)
+ );
+
+ let bytes = sketch.serialize();
+ let decoded = KllSketch::<i64>::deserialize(&bytes).unwrap();
+ assert_eq!(decoded.total_weight(), u64::MAX);
+ assert_eq!(decoded.num_retained(), sketch.num_retained());
+ assert_eq!(decoded.serialize(), bytes);
+}
+
+#[test]
+fn merging_sparse_and_top_folded_weighted_sketches() {
+ let mut sparse = KllSketch::<i64>::new(DEFAULT_K).unwrap();
+ sparse.update_with_weight(100, 1u64 << 40);
+
+ let mut unit = KllSketch::<i64>::new(DEFAULT_K).unwrap();
+ for item in 1..=5 {
+ unit.update(item);
+ }
+
+ let mut unit_into_sparse = sparse.clone();
+ unit_into_sparse.merge(&unit);
+ let mut sparse_into_unit = unit;
+ sparse_into_unit.merge(&sparse);
+
+ let expected_weight = (1u64 << 40) + 5;
+ for merged in [&unit_into_sparse, &sparse_into_unit] {
+ assert_eq!(merged.total_weight(), expected_weight);
+ assert_eq!(merged.sorted_view().total_weight(), expected_weight);
+ assert_eq!(merged.num_retained(), 6);
+ assert_eq!(merged.min_item(), Some(&1));
+ assert_eq!(merged.max_item(), Some(&100));
+ assert_eq!(
+ merged.rank(&5, SearchCriteria::Inclusive),
+ Some(5.0 / expected_weight as f64)
+ );
+ assert_eq!(
+ merged.rank(&100, SearchCriteria::Exclusive),
+ Some(5.0 / expected_weight as f64)
+ );
+ assert_eq!(merged.rank(&100, SearchCriteria::Inclusive), Some(1.0));
+
+ let bytes = merged.serialize();
+ let decoded = KllSketch::<i64>::deserialize(&bytes).unwrap();
+ assert_eq!(decoded.serialize(), bytes);
+ }
+
+ let mut top_left = KllSketch::<i64>::new(MIN_K).unwrap();
+ top_left.update_with_weight(1, 7u64 << 60);
+ let mut top_right = KllSketch::<i64>::new(MIN_K).unwrap();
+ top_right.update_with_weight(2, (8u64 << 60) + 3);
+ top_left.merge(&top_right);
+
+ let top_total = (15u64 << 60) + 3;
+ assert_eq!(top_left.total_weight(), top_total);
+ assert_eq!(top_left.sorted_view().total_weight(), top_total);
+ assert_eq!(top_left.num_retained(), 7 + 8 + 2);
+ assert_eq!(top_left.min_item(), Some(&1));
+ assert_eq!(top_left.max_item(), Some(&2));
+ assert_eq!(
+ top_left.rank(&1, SearchCriteria::Inclusive),
+ Some((7u64 << 60) as f64 / top_total as f64)
+ );
+
+ let bytes = top_left.serialize();
+ let decoded = KllSketch::<i64>::deserialize(&bytes).unwrap();
+ assert_eq!(decoded.serialize(), bytes);
+}
+
+#[test]
+fn weighted_updates_into_populated_sketch_preserve_disjoint_mass_and_min_k() {
+ let mut sketch = KllSketch::<i64>::new(DEFAULT_K).unwrap();
+ for item in 0..1_000 {
+ sketch.update(item);
+ }
+ // Every retained item from 0..1_000 lies strictly inside (-1, 2_000), and
adding 13 binary
+ // level items stays well below the 12-level capacity (636), so no further
compaction occurs.
+ sketch.update_with_weight(-1, 1_000);
+ sketch.update_with_weight(2_000, 3_000);
+
+ assert_eq!(sketch.total_weight(), 5_000);
+ assert_eq!(sketch.min_item(), Some(&-1));
+ assert_eq!(sketch.max_item(), Some(&2_000));
+ assert_eq!(sketch.rank(&-1, SearchCriteria::Inclusive), Some(0.2));
+ assert_eq!(sketch.rank(&0, SearchCriteria::Exclusive), Some(0.2));
+ assert_eq!(sketch.rank(&2_000, SearchCriteria::Exclusive), Some(0.4));
+ assert_eq!(sketch.rank(&2_000, SearchCriteria::Inclusive), Some(1.0));
+
+ let mut lower_k = KllSketch::<i64>::new(64).unwrap();
+ for item in 0..1_000 {
+ lower_k.update(item);
+ }
+ sketch.merge(&lower_k);
+ assert_eq!(sketch.min_k(), 64);
+
+ sketch.update_with_weight(500, 3);
+ sketch.update_with_weight(600, 100_000);
+ assert_eq!(sketch.k(), DEFAULT_K);
+ assert_eq!(sketch.min_k(), 64);
+}
+
+#[test]
+fn estimation_mode_stream_preserves_deterministic_invariants() {
+ let mut sketch = KllSketch::<i64>::new(32).unwrap();
+ let mut expected_total = 0u64;
+ for item in 0..500i64 {
+ let weight = match item % 4 {
+ 0 => 1,
+ 1 => (item as u64 % 7) + 2,
+ 2 => ((item as u64 % 11) + 1) * 100,
+ _ => ((item as u64 % 9) + 1) * 250 + 1,
+ };
+ sketch.update_with_weight(item, weight);
+ expected_total += weight;
+ }
+
+ assert!(sketch.is_estimation_mode());
+ assert_eq!(sketch.total_weight(), expected_total);
+ assert_eq!(sketch.sorted_view().total_weight(), expected_total);
+ assert_eq!(sketch.min_item(), Some(&0));
+ assert_eq!(sketch.max_item(), Some(&499));
+
+ let split_points: Vec<_> = (25..500).step_by(25).collect();
+ for criteria in [SearchCriteria::Inclusive, SearchCriteria::Exclusive] {
+ let cdf = sketch.cdf(&split_points, criteria).unwrap().unwrap();
+ let pmf = sketch.pmf(&split_points, criteria).unwrap().unwrap();
+ let mut previous_rank = 0.0;
+ let mut subtotal = 0.0;
+ for (index, split_point) in split_points.iter().enumerate() {
+ let rank = sketch.rank(split_point, criteria).unwrap();
+ assert!(rank >= previous_rank);
+ assert!((0.0..=1.0).contains(&rank));
+ previous_rank = rank;
+
+ subtotal += pmf[index];
+ assert!((cdf[index] - subtotal).abs() <= NUMERIC_NOISE_TOLERANCE);
+ assert_eq!(cdf[index], rank);
+ }
+ assert!((pmf.iter().sum::<f64>() - 1.0).abs() <=
NUMERIC_NOISE_TOLERANCE);
+ }
+
+ let bytes = sketch.serialize();
+ let decoded = KllSketch::<i64>::deserialize(&bytes).unwrap();
+ assert_eq!(decoded.total_weight(), sketch.total_weight());
+ assert_eq!(decoded.num_retained(), sketch.num_retained());
+ assert_eq!(decoded.serialize(), bytes);
+}
+
+#[test]
+fn owned_string_items_roundtrip_across_update_paths() {
+ let mut sketch = KllSketch::<String>::new(DEFAULT_K).unwrap();
+ sketch.update_with_weight("ignored".to_owned(), 0);
+ sketch.update_with_weight("m".to_owned(), 1);
+ sketch.update_with_weight("b".to_owned(), 4);
+ sketch.update_with_weight("a".to_owned(), 1_000);
+ sketch.update_with_weight("z".to_owned(), 1u64 << 62);
+
+ let expected_total = 1 + 4 + 1_000 + (1u64 << 62);
+ assert_eq!(sketch.total_weight(), expected_total);
+ assert_eq!(sketch.min_item().map(String::as_str), Some("a"));
+ assert_eq!(sketch.max_item().map(String::as_str), Some("z"));
+
+ let bytes = sketch.serialize();
+ let decoded = KllSketch::<String>::deserialize(&bytes).unwrap();
+ assert_eq!(decoded.total_weight(), expected_total);
+ assert_eq!(decoded.min_item().map(String::as_str), Some("a"));
+ assert_eq!(decoded.max_item().map(String::as_str), Some("z"));
+ assert_eq!(decoded.serialize(), bytes);
+}
+
+#[test]
+fn weighted_update_overflow_preserves_state() {
+ let mut sketch = KllSketch::<i64>::new(DEFAULT_K).unwrap();
+ sketch.update_with_weight(10, u64::MAX - 5);
+ let before = sketch.serialize();
+
+ for bad_weight in [6, u64::MAX] {
+ assert!(
+ catch_unwind(AssertUnwindSafe(
+ || sketch.update_with_weight(20, bad_weight)
+ ))
+ .is_err()
+ );
+ assert_eq!(sketch.serialize(), before, "overflow changed the sketch");
+ }
+
+ sketch.update_with_weight(20, 5);
+ assert_eq!(sketch.total_weight(), u64::MAX);
+ assert_eq!(sketch.max_item(), Some(&20));
+ let at_max = sketch.serialize();
+
+ // Zero remains a no-op at u64::MAX; both weight == 1 and weight >= 2
panic unchanged.
+ sketch.update_with_weight(30, 0);
+ assert_eq!(sketch.serialize(), at_max);
+ for bad_weight in [1, 2] {
+ assert!(
+ catch_unwind(AssertUnwindSafe(
+ || sketch.update_with_weight(30, bad_weight)
+ ))
+ .is_err()
+ );
+ assert_eq!(sketch.serialize(), at_max, "overflow changed the sketch");
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]