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]

Reply via email to