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 c23ee3e test: remove redundant and implementation-coupled coverage
(#337)
c23ee3e is described below
commit c23ee3efa379eac3eabafc2818ed3c38407a1388
Author: tison <[email protected]>
AuthorDate: Sun Nov 8 09:31:12 2026 +0800
test: remove redundant and implementation-coupled coverage (#337)
---
datasketches/src/req/sorted_view.rs | 122 ------
tests-integration/tests/bloom_test/sketch.rs | 1 -
tests-integration/tests/countmin_test/sketch.rs | 30 --
tests-integration/tests/cpc_test/union.rs | 13 -
tests-integration/tests/cpc_test/update.rs | 12 -
tests-integration/tests/frequencies_test/main.rs | 1 -
tests-integration/tests/frequencies_test/rehash.rs | 111 -----
tests-integration/tests/frequencies_test/update.rs | 287 ++----------
tests-integration/tests/hll_test/union.rs | 13 -
tests-integration/tests/hll_test/update.rs | 15 -
tests-integration/tests/req_test/query.rs | 27 +-
.../tests/req_test/sorted_view_api.rs | 70 ---
tests-integration/tests/req_test/structure.rs | 25 --
tests-integration/tests/serde_tests/frequencies.rs | 17 -
tests-integration/tests/serde_tests/tdigest.rs | 47 --
tests-integration/tests/tdigest_test/sketch.rs | 486 ++-------------------
tests-integration/tests/theta_test/intersection.rs | 10 -
tests-integration/tests/theta_test/sketch.rs | 2 -
tests-integration/tests/theta_test/union.rs | 21 -
tests-integration/tests/tuple_test/intersection.rs | 10 -
tests-integration/tests/tuple_test/sketch.rs | 61 ---
tests-integration/tests/tuple_test/union.rs | 21 -
22 files changed, 72 insertions(+), 1330 deletions(-)
diff --git a/datasketches/src/req/sorted_view.rs
b/datasketches/src/req/sorted_view.rs
index 78c4bc6..c0cdd78 100644
--- a/datasketches/src/req/sorted_view.rs
+++ b/datasketches/src/req/sorted_view.rs
@@ -215,125 +215,3 @@ where
Ok(())
}
}
-
-#[cfg(test)]
-mod tests {
- use googletest::assert_that;
- use googletest::prelude::all;
- use googletest::prelude::ge;
- use googletest::prelude::le;
- use googletest::prelude::near;
-
- use super::*;
-
- fn create_test_view() -> SortedView<i32> {
- let weighted_items = vec![(1, 1), (3, 1), (5, 1), (7, 1), (9, 1)];
- SortedView::new(weighted_items, Some(1), Some(9))
- }
-
- #[test]
- fn test_sorted_view_creation() {
- let view = create_test_view();
- assert_eq!(view.len(), 5);
- assert_eq!(view.total_weight(), 5);
- assert!(!view.is_empty());
- }
-
- #[test]
- fn test_rank_queries() {
- let view = create_test_view();
-
- // Test exact matches
- assert_that!(
- view.rank(&1, SearchCriteria::Inclusive).unwrap(),
- near(0.2, 1e-10)
- );
- assert_that!(
- view.rank(&1, SearchCriteria::Exclusive).unwrap(),
- near(0.0, 1e-10)
- );
-
- // Test values between items
- assert_that!(
- view.rank(&2, SearchCriteria::Inclusive).unwrap(),
- near(0.2, 1e-10)
- );
- assert_that!(
- view.rank(&6, SearchCriteria::Inclusive).unwrap(),
- near(0.6, 1e-10)
- );
-
- // Test edge cases
- assert_that!(
- view.rank(&0, SearchCriteria::Inclusive).unwrap(),
- near(0.0, 1e-10)
- );
- assert_that!(
- view.rank(&10, SearchCriteria::Inclusive).unwrap(),
- near(1.0, 1e-10)
- );
- }
-
- #[test]
- fn test_quantile_queries() -> Result<(), Error> {
- let view = create_test_view();
-
- // Test edge cases
- assert_eq!(view.quantile(0.0, SearchCriteria::Inclusive)?, Some(1));
- assert_eq!(view.quantile(1.0, SearchCriteria::Inclusive)?, Some(9));
-
- // Test middle values
- let median = view.quantile(0.5, SearchCriteria::Inclusive)?.unwrap();
- assert_that!(median, all!(ge(3), le(7))); // Should be around the
middle (values are 1,3,5,7,9)
-
- // Test various ranks
- let q25 = view.quantile(0.25, SearchCriteria::Inclusive)?.unwrap();
- let q75 = view.quantile(0.75, SearchCriteria::Inclusive)?.unwrap();
- assert_that!(q25, le(median));
- assert_that!(median, le(q75));
- Ok(())
- }
-
- #[test]
- fn test_pmf() -> Result<(), Error> {
- let view = create_test_view();
- let split_points = vec![3, 7];
-
- let pmf = view.pmf(&split_points, SearchCriteria::Inclusive)?.unwrap();
- assert_eq!(pmf.len(), 3); // 2 split points create 3 intervals
-
- // Sum should be approximately 1.0
- let sum: f64 = pmf.iter().sum();
- assert_that!(sum, near(1.0, 1e-10));
- Ok(())
- }
-
- #[test]
- fn test_cdf() -> Result<(), Error> {
- let view = create_test_view();
- let split_points = vec![3, 7];
-
- let cdf = view.cdf(&split_points, SearchCriteria::Inclusive)?.unwrap();
- assert_eq!(cdf.len(), 3);
-
- // CDF should be monotonically increasing
- for i in 1..cdf.len() {
- assert_that!(cdf[i], ge(cdf[i - 1]));
- }
-
- // Last value should be 1.0
- assert_that!(cdf[cdf.len() - 1], near(1.0, 1e-10));
- Ok(())
- }
-
- #[test]
- fn test_empty_view() {
- let view: SortedView<i32> = SortedView::new(vec![], None, None);
- assert!(view.is_empty());
- assert_eq!(view.len(), 0);
- assert_eq!(view.total_weight(), 0);
-
- assert_eq!(view.rank(&5, SearchCriteria::Inclusive), None);
- assert_eq!(view.quantile(0.5, SearchCriteria::Inclusive).unwrap(),
None);
- }
-}
diff --git a/tests-integration/tests/bloom_test/sketch.rs
b/tests-integration/tests/bloom_test/sketch.rs
index 11c27c4..b6fe2c3 100644
--- a/tests-integration/tests/bloom_test/sketch.rs
+++ b/tests-integration/tests/bloom_test/sketch.rs
@@ -251,7 +251,6 @@ fn test_intersection_rejects_incompatible_filters() {
fn test_requested_size_rounds_to_word_boundary() {
let filter = BloomFilterBuilder::with_size(65, 3).build().unwrap();
assert_eq!(filter.capacity(), 128);
- assert_eq!(filter.estimated_size(), 16);
}
#[test]
diff --git a/tests-integration/tests/countmin_test/sketch.rs
b/tests-integration/tests/countmin_test/sketch.rs
index b85a887..8508bee 100644
--- a/tests-integration/tests/countmin_test/sketch.rs
+++ b/tests-integration/tests/countmin_test/sketch.rs
@@ -432,33 +432,3 @@ fn test_merge_incompatible() {
let error = left.merge(&right).unwrap_err();
assert_eq!(error.kind(), ErrorKind::InvalidArgument);
}
-
-#[test]
-fn test_increment_single_key_like_rust_count_min_sketch() {
- let mut sketch = CountMinSketch::<i64>::new(4, 32).unwrap();
- for _ in 0..300 {
- sketch.update("key");
- }
- assert_eq!(sketch.estimate("key"), 300);
-}
-
-#[test]
-fn test_estimated_size() {
- let mut sketch = CountMinSketch::<i64>::new(4, 128).unwrap();
- assert_eq!(sketch.estimated_size(), 4128);
-
- // The backing tables are allocated up front; updates do not grow the
sketch.
- sketch.update("apple");
- assert_eq!(sketch.estimated_size(), 4128);
-}
-
-#[test]
-fn test_increment_multi_like_rust_count_min_sketch() {
- let mut sketch = CountMinSketch::<i64>::new(6, 128).unwrap();
- for i in 0..1_000_000u64 {
- sketch.update(i % 100);
- }
- for key in 0..100u64 {
- assert_that!(sketch.estimate(key), ge(9_000));
- }
-}
diff --git a/tests-integration/tests/cpc_test/union.rs
b/tests-integration/tests/cpc_test/union.rs
index d72a7d4..963d0ee 100644
--- a/tests-integration/tests/cpc_test/union.rs
+++ b/tests-integration/tests/cpc_test/union.rs
@@ -179,16 +179,3 @@ fn test_lg_k_too_large_returns_error() {
let error = CpcSketch::new(27).unwrap_err();
assert_eq!(error.kind(), ErrorKind::InvalidArgument);
}
-
-#[test]
-fn test_union_estimated_size() {
- let mut union = CpcUnion::new(11).unwrap();
- assert_eq!(union.estimated_size(), 0);
-
- let mut sketch = CpcSketch::new(11).unwrap();
- for i in 0..1000 {
- sketch.update(i);
- }
- union.update(&sketch).unwrap();
- assert_eq!(union.estimated_size(), 16384);
-}
diff --git a/tests-integration/tests/cpc_test/update.rs
b/tests-integration/tests/cpc_test/update.rs
index 8aec8df..99a1cb5 100644
--- a/tests-integration/tests/cpc_test/update.rs
+++ b/tests-integration/tests/cpc_test/update.rs
@@ -67,15 +67,3 @@ fn test_max_serialized_bytes_validates_lg_k() {
assert_eq!(error.kind(), ErrorKind::InvalidArgument);
}
}
-
-#[test]
-fn test_estimated_size() {
- let mut sketch = CpcSketch::new(11).unwrap();
- let empty_size = sketch.estimated_size();
- assert_eq!(empty_size, 0);
-
- for i in 0..10_000 {
- sketch.update(i);
- }
- assert_eq!(sketch.estimated_size(), 2304);
-}
diff --git a/tests-integration/tests/frequencies_test/main.rs
b/tests-integration/tests/frequencies_test/main.rs
index 6181db4..1dea33b 100644
--- a/tests-integration/tests/frequencies_test/main.rs
+++ b/tests-integration/tests/frequencies_test/main.rs
@@ -15,5 +15,4 @@
// specific language governing permissions and limitations
// under the License.
-mod rehash;
mod update;
diff --git a/tests-integration/tests/frequencies_test/rehash.rs
b/tests-integration/tests/frequencies_test/rehash.rs
deleted file mode 100644
index e166c55..0000000
--- a/tests-integration/tests/frequencies_test/rehash.rs
+++ /dev/null
@@ -1,111 +0,0 @@
-// 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.
-
-//! Growing the item map must keep every item with its exact weight.
-
-use std::hash::Hash;
-use std::hash::Hasher;
-
-use datasketches::frequencies::FrequentItemsSketch;
-
-fn weight(i: u64) -> u64 {
- i % 5 + 1
-}
-
-// Stay below the purge threshold and check all counts at each growth boundary.
-fn check_growth<T: Eq + Hash>(max_map_size: usize, distinct: u64, item: impl
Fn(u64) -> T) {
- let mut sketch = FrequentItemsSketch::new(max_map_size).unwrap();
- let initial_capacity = sketch.current_map_capacity();
- let mut total_weight = 0;
- for i in 0..distinct {
- let capacity = sketch.current_map_capacity();
- sketch.update_with_count(item(i), weight(i));
- total_weight += weight(i);
- if sketch.current_map_capacity() != capacity || i + 1 == distinct {
- assert_eq!(sketch.total_weight(), total_weight);
- assert_eq!(sketch.num_active_items() as u64, i + 1);
- assert_eq!(sketch.maximum_error(), 0);
- for j in 0..=i {
- assert_eq!(sketch.estimate(&item(j)), weight(j), "item {j}
after {i}");
- }
- }
- }
- assert!(sketch.current_map_capacity() > initial_capacity);
-}
-
-#[test]
-fn test_longs_growth_keeps_every_item() {
- check_growth(1 << 12, 2_000, |i| (i * 7_919 + 13) as i64);
-}
-
-#[test]
-fn test_items_growth_keeps_every_item() {
- check_growth(1 << 12, 2_000, |i| format!("item-{i}"));
-}
-
-#[derive(Debug, PartialEq, Eq)]
-struct CollidingItem(u64);
-
-impl Hash for CollidingItem {
- fn hash<H: Hasher>(&self, state: &mut H) {
- 0u64.hash(state);
- }
-}
-
-#[test]
-fn test_colliding_items_survive_growth_updates_and_purge() {
- let mut sketch = FrequentItemsSketch::new(64).unwrap();
- for i in 0..48 {
- sketch.update_with_count(CollidingItem(i), if i % 4 == 0 { 100 } else
{ 1 });
- }
- assert_eq!(sketch.current_map_capacity(), sketch.maximum_map_capacity());
- assert_eq!(sketch.maximum_error(), 0);
- for i in 0..48 {
- assert_eq!(
- sketch.estimate(&CollidingItem(i)),
- if i % 4 == 0 { 100 } else { 1 }
- );
- }
-
- for i in (0..48).step_by(4) {
- sketch.update_with_count(CollidingItem(i), 7);
- }
- assert_eq!(sketch.num_active_items(), 48);
- assert_eq!(sketch.maximum_error(), 0);
-
- // The new key triggers a purge with median 1. Deleting light items from
- // the collision chain must preserve access to every displaced heavy item.
- sketch.update(CollidingItem(48));
- assert_eq!(sketch.maximum_error(), 1);
- assert_eq!(sketch.num_active_items(), 12);
- for i in 0..49 {
- if i < 48 && i % 4 == 0 {
- assert_eq!(sketch.estimate(&CollidingItem(i)), 107);
- assert_eq!(sketch.lower_bound(&CollidingItem(i)), 106);
- } else {
- assert_eq!(sketch.estimate(&CollidingItem(i)), 0);
- assert_eq!(sketch.upper_bound(&CollidingItem(i)), 1);
- }
- }
-
- sketch.update_with_count(CollidingItem(44), 3);
- sketch.update_with_count(CollidingItem(1), 5);
- assert_eq!(sketch.estimate(&CollidingItem(44)), 110);
- assert_eq!(sketch.estimate(&CollidingItem(1)), 6);
- assert_eq!(sketch.num_active_items(), 13);
- assert_eq!(sketch.total_weight(), 12 * 107 + 37 + 3 + 5);
-}
diff --git a/tests-integration/tests/frequencies_test/update.rs
b/tests-integration/tests/frequencies_test/update.rs
index ca357d6..4dec64e 100644
--- a/tests-integration/tests/frequencies_test/update.rs
+++ b/tests-integration/tests/frequencies_test/update.rs
@@ -16,6 +16,7 @@
// under the License.
use std::hash::Hash;
+use std::hash::Hasher;
use std::panic::AssertUnwindSafe;
use std::panic::catch_unwind;
@@ -28,26 +29,6 @@ use googletest::prelude::gt;
use googletest::prelude::le;
use googletest::prelude::near;
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
-struct TestItem(i32);
-
-#[derive(Debug, PartialEq, Eq, Hash)]
-struct NonCloneItem(i32);
-
-#[test]
-fn test_non_clone_items_update_and_query() {
- let mut sketch = FrequentItemsSketch::<NonCloneItem>::new(8).unwrap();
-
- sketch.update(NonCloneItem(7));
- sketch.update_with_count(NonCloneItem(11), 3);
-
- assert_eq!(sketch.total_weight(), 4);
- assert_eq!(sketch.num_active_items(), 2);
- assert_eq!(sketch.estimate(&NonCloneItem(7)), 1);
- assert_eq!(sketch.lower_bound(&NonCloneItem(11)), 3);
- assert_eq!(sketch.upper_bound(&NonCloneItem(11)), 3);
-}
-
#[test]
fn test_longs_update_with_zero_count_is_noop() {
let mut sketch: FrequentItemsSketch<i64> =
FrequentItemsSketch::new(8).unwrap();
@@ -58,16 +39,6 @@ fn test_longs_update_with_zero_count_is_noop() {
assert_eq!(sketch.num_active_items(), 0);
}
-#[test]
-fn test_items_update_with_zero_count_is_noop() {
- let mut sketch = FrequentItemsSketch::new(8).unwrap();
- sketch.update_with_count("a".to_string(), 0);
-
- assert!(sketch.is_empty());
- assert_eq!(sketch.total_weight(), 0);
- assert_eq!(sketch.num_active_items(), 0);
-}
-
#[test]
fn test_capacity_and_epsilon_helpers() {
let longs: FrequentItemsSketch<i64> = FrequentItemsSketch::new(8).unwrap();
@@ -110,47 +81,6 @@ fn test_longs_empty() {
assert_eq!(sketch.maximum_error(), 0);
}
-#[test]
-fn test_items_empty() {
- let sketch: FrequentItemsSketch<String> =
FrequentItemsSketch::new(8).unwrap();
- let item = "a".to_string();
-
- assert!(sketch.is_empty());
- assert_eq!(sketch.num_active_items(), 0);
- assert_eq!(sketch.total_weight(), 0);
- assert_eq!(sketch.estimate(&item), 0);
- assert_eq!(sketch.lower_bound(&item), 0);
- assert_eq!(sketch.upper_bound(&item), 0);
- assert_eq!(sketch.maximum_error(), 0);
-}
-
-#[test]
-fn test_longs_one_item() {
- let mut sketch: FrequentItemsSketch<i64> =
FrequentItemsSketch::new(8).unwrap();
- sketch.update(10);
-
- assert!(!sketch.is_empty());
- assert_eq!(sketch.num_active_items(), 1);
- assert_eq!(sketch.total_weight(), 1);
- assert_eq!(sketch.estimate(&10), 1);
- assert_eq!(sketch.lower_bound(&10), 1);
- assert_eq!(sketch.upper_bound(&10), 1);
-}
-
-#[test]
-fn test_items_one_item() {
- let mut sketch = FrequentItemsSketch::new(8).unwrap();
- let item = "a".to_string();
- sketch.update(item.clone());
-
- assert!(!sketch.is_empty());
- assert_eq!(sketch.num_active_items(), 1);
- assert_eq!(sketch.total_weight(), 1);
- assert_eq!(sketch.estimate(&item), 1);
- assert_eq!(sketch.lower_bound(&item), 1);
- assert_eq!(sketch.upper_bound(&item), 1);
-}
-
#[test]
fn test_items_borrowed_key_updates_and_queries() {
let mut sketch = FrequentItemsSketch::<String>::new(16).unwrap();
@@ -293,34 +223,6 @@ fn test_longs_estimation_mode() {
assert_that!(items.len(), le(12));
}
-#[test]
-fn test_items_estimation_mode() {
- let mut sketch: FrequentItemsSketch<i32> =
FrequentItemsSketch::new(8).unwrap();
- sketch.update_with_count(1, 10);
- for item in 2..=6 {
- sketch.update(item);
- }
- sketch.update_with_count(7, 15);
- for item in 8..=12 {
- sketch.update(item);
- }
-
- assert!(!sketch.is_empty());
- assert_eq!(sketch.total_weight(), 35);
- assert_that!(sketch.maximum_error(), gt(0));
-
- let items = sketch.frequent_items(ErrorType::NoFalsePositives);
- assert_eq!(items.len(), 2);
- assert_eq!(items[0].item(), &7);
- assert_eq!(items[0].estimate(), 15);
- assert_eq!(items[1].item(), &1);
- assert_eq!(items[1].estimate(), 10);
-
- let items = sketch.frequent_items(ErrorType::NoFalseNegatives);
- assert_that!(items.len(), ge(2));
- assert_that!(items.len(), le(12));
-}
-
#[test]
fn test_longs_purge_keeps_heavy_hitters() {
let mut sketch: FrequentItemsSketch<i64> =
FrequentItemsSketch::new(8).unwrap();
@@ -340,45 +242,6 @@ fn test_longs_purge_keeps_heavy_hitters() {
assert_eq!(rows[0].estimate(), 10);
}
-#[test]
-fn test_items_purge_keeps_heavy_hitters() {
- let mut sketch = FrequentItemsSketch::new(8).unwrap();
- sketch.update_with_count("a".to_string(), 10);
- for item in ["b", "c", "d", "e", "f", "g"] {
- sketch.update(item.to_string());
- }
-
- assert_eq!(sketch.total_weight(), 16);
- assert_eq!(sketch.maximum_error(), 1);
- assert_eq!(sketch.estimate(&"a".to_string()), 10);
- assert_eq!(sketch.lower_bound(&"a".to_string()), 9);
-
- let rows = sketch.frequent_items(ErrorType::NoFalsePositives);
- assert_eq!(rows.len(), 1);
- assert_eq!(rows[0].item(), "a");
- assert_eq!(rows[0].estimate(), 10);
-}
-
-#[test]
-fn test_items_custom_type() {
- let mut sketch: FrequentItemsSketch<TestItem> =
FrequentItemsSketch::new(8).unwrap();
- sketch.update_with_count(TestItem(1), 10);
- for item in 2..=7 {
- sketch.update(TestItem(item));
- }
- let item = TestItem(8);
- sketch.update(item);
-
- assert!(!sketch.is_empty());
- assert_eq!(sketch.total_weight(), 17);
- assert_eq!(sketch.estimate(&TestItem(1)), 10);
-
- let rows = sketch.frequent_items(ErrorType::NoFalsePositives);
- assert_eq!(rows.len(), 1);
- assert_eq!(rows[0].item(), &TestItem(1));
- assert_eq!(rows[0].estimate(), 10);
-}
-
#[test]
fn test_longs_merge_estimation_mode() {
let mut sketch1: FrequentItemsSketch<i64> =
FrequentItemsSketch::new(16).unwrap();
@@ -408,57 +271,6 @@ fn test_longs_merge_estimation_mode() {
assert_that!(items[1].estimate(), ge(9));
}
-#[test]
-fn test_items_merge_estimation_mode() {
- let mut sketch1: FrequentItemsSketch<i32> =
FrequentItemsSketch::new(16).unwrap();
- sketch1.update_with_count(1, 9);
- for item in 2..=14 {
- sketch1.update(item);
- }
- assert_that!(sketch1.maximum_error(), gt(0));
-
- let mut sketch2: FrequentItemsSketch<i32> =
FrequentItemsSketch::new(16).unwrap();
- for item in 8..=20 {
- sketch2.update(item);
- }
- sketch2.update_with_count(21, 11);
- assert_that!(sketch2.maximum_error(), gt(0));
-
- sketch1.merge(&sketch2);
- assert!(!sketch1.is_empty());
- assert_eq!(sketch1.total_weight(), 46);
- assert_that!(sketch1.num_active_items(), ge(2));
-
- let items =
sketch1.frequent_items_with_threshold(ErrorType::NoFalsePositives, 2);
- assert_eq!(items.len(), 2);
- assert_eq!(items[0].item(), &21);
- assert_that!(items[0].estimate(), ge(11));
- assert_eq!(items[1].item(), &1);
- assert_that!(items[1].estimate(), ge(9));
-}
-
-#[test]
-fn test_longs_merge_exact_mode() {
- let mut sketch1: FrequentItemsSketch<i64> =
FrequentItemsSketch::new(8).unwrap();
- sketch1.update(1);
- sketch1.update(2);
- sketch1.update(2);
-
- let mut sketch2: FrequentItemsSketch<i64> =
FrequentItemsSketch::new(8).unwrap();
- sketch2.update(2);
- sketch2.update(3);
-
- sketch1.merge(&sketch2);
-
- assert!(!sketch1.is_empty());
- assert_eq!(sketch1.total_weight(), 5);
- assert_eq!(sketch1.num_active_items(), 3);
- assert_eq!(sketch1.estimate(&1), 1);
- assert_eq!(sketch1.estimate(&2), 3);
- assert_eq!(sketch1.estimate(&3), 1);
- assert_eq!(sketch1.maximum_error(), 0);
-}
-
#[test]
fn test_items_merge_exact_mode() {
let mut sketch1 = FrequentItemsSketch::new(8).unwrap();
@@ -498,22 +310,10 @@ fn test_longs_merge_empty_is_noop() {
}
#[test]
-fn test_items_merge_empty_is_noop() {
- let mut sketch: FrequentItemsSketch<i32> =
FrequentItemsSketch::new(8).unwrap();
- sketch.update(1);
-
- let empty: FrequentItemsSketch<i32> = FrequentItemsSketch::new(8).unwrap();
- sketch.merge(&empty);
-
- assert_eq!(sketch.total_weight(), 1);
- assert_eq!(sketch.num_active_items(), 1);
- assert_eq!(sketch.estimate(&1), 1);
-}
-
-fn check_purged_state<T: Eq + Hash + Clone>(make_item: impl Fn(i64) -> T) {
+fn test_purged_state_survives_merge_and_reset() {
let mut purged = FrequentItemsSketch::new(256).unwrap();
for item in 0..193 {
- purged.update(make_item(item));
+ purged.update(item);
}
assert!(!purged.is_empty());
assert_eq!(purged.num_active_items(), 0);
@@ -527,14 +327,14 @@ fn check_purged_state<T: Eq + Hash + Clone>(make_item:
impl Fn(i64) -> T) {
assert_eq!(merged.num_active_items(), 0);
assert_eq!(merged.total_weight(), purged.total_weight());
assert_eq!(merged.maximum_error(), purged.maximum_error());
- assert_eq!(merged.upper_bound(&make_item(0)), 1);
+ assert_eq!(merged.upper_bound(&0), 1);
let mut nonempty = FrequentItemsSketch::new(256).unwrap();
- nonempty.update(make_item(1000));
+ nonempty.update(1000);
nonempty.merge(&purged);
assert_eq!(nonempty.total_weight(), 194);
assert_eq!(nonempty.maximum_error(), 1);
- assert_eq!(nonempty.upper_bound(&make_item(0)), 1);
+ assert_eq!(nonempty.upper_bound(&0), 1);
purged.reset();
assert!(purged.is_empty());
@@ -542,16 +342,6 @@ fn check_purged_state<T: Eq + Hash + Clone>(make_item:
impl Fn(i64) -> T) {
assert_eq!(purged.maximum_error(), 0);
}
-#[test]
-fn test_longs_purged_state() {
- check_purged_state(|item| item);
-}
-
-#[test]
-fn test_items_purged_state() {
- check_purged_state(|item| item.to_string());
-}
-
#[test]
fn test_update_weight_overflow_preserves_state() {
let mut sketch = FrequentItemsSketch::<String>::new(8).unwrap();
@@ -586,24 +376,6 @@ fn test_merge_weight_overflow_preserves_state() {
assert!(!sketch.is_empty());
}
-#[test]
-fn test_row_equality_changes_with_updates() {
- let mut sketch: FrequentItemsSketch<i32> =
FrequentItemsSketch::new(8).unwrap();
- sketch.update(1);
- let rows1 = sketch.frequent_items(ErrorType::NoFalsePositives);
- assert_eq!(rows1.len(), 1);
- let row1 = rows1[0].clone();
-
- sketch.update(1);
- let rows2 = sketch.frequent_items(ErrorType::NoFalsePositives);
- assert_eq!(rows2.len(), 1);
- let row2 = rows2[0].clone();
-
- assert_ne!(row1, row2);
- assert_eq!(row2.item(), &1);
- assert_eq!(row2.estimate(), 2);
-}
-
#[test]
fn test_longs_reset() {
let mut sketch: FrequentItemsSketch<i64> =
FrequentItemsSketch::new(8).unwrap();
@@ -631,30 +403,35 @@ fn
test_map_size_above_cross_language_limit_returns_error() {
assert_eq!(error.kind(), ErrorKind::InvalidArgument);
}
-#[test]
-fn test_estimated_size() {
- let mut sketch: FrequentItemsSketch<i64> =
FrequentItemsSketch::new(64).unwrap();
- assert_eq!(sketch.estimated_size(), 208);
+#[derive(Debug, PartialEq, Eq)]
+struct CollidingItem(usize);
- // The internal map grows from its starting size up to the maximum size.
- for i in 0..100 {
- sketch.update(i);
+impl Hash for CollidingItem {
+ fn hash<H: Hasher>(&self, state: &mut H) {
+ 0u64.hash(state);
}
- assert_eq!(sketch.estimated_size(), 1664);
}
#[test]
-fn estimated_size_is_shallow_for_generic_items() {
- let mut small_item_sketch = FrequentItemsSketch::new(8).unwrap();
- small_item_sketch.update("key".to_string());
-
- let mut large_item = String::with_capacity(4096);
- large_item.push_str("key");
- let mut large_item_sketch = FrequentItemsSketch::new(8).unwrap();
- large_item_sketch.update(large_item);
-
- assert_eq!(
- small_item_sketch.estimated_size(),
- large_item_sketch.estimated_size()
- );
+fn test_colliding_items_preserve_frequency_bounds() {
+ let mut sketch = FrequentItemsSketch::new(64).unwrap();
+ let mut counts = [1u64; 100];
+ for count in counts.iter_mut().step_by(16) {
+ *count = 100;
+ }
+ for (item, &count) in counts.iter().enumerate() {
+ sketch.update_with_count(CollidingItem(item), count);
+ }
+ assert!(sketch.maximum_error() > 0);
+
+ // Exercise subsequent updates to both a heavy hitter and a light item.
+ for item in [0, 1] {
+ sketch.update_with_count(CollidingItem(item), 10);
+ counts[item] += 10;
+ }
+ assert_eq!(sketch.total_weight(), counts.iter().sum::<u64>());
+ for (item, &count) in counts.iter().enumerate() {
+ assert!(sketch.lower_bound(&CollidingItem(item)) <= count);
+ assert!(sketch.upper_bound(&CollidingItem(item)) >= count);
+ }
}
diff --git a/tests-integration/tests/hll_test/union.rs
b/tests-integration/tests/hll_test/union.rs
index 5f807d8..e02f240 100644
--- a/tests-integration/tests/hll_test/union.rs
+++ b/tests-integration/tests/hll_test/union.rs
@@ -707,19 +707,6 @@ fn test_union_validation() {
assert_eq!(union.lg_max_k(), 15, "lg_max_k should persist after reset");
}
-#[test]
-fn test_union_estimated_size() {
- let mut union = HllUnion::new(10).unwrap();
- assert_eq!(union.estimated_size(), 32);
-
- let mut sketch = HllSketch::new(10, HllType::Hll8).unwrap();
- for i in 0..1000 {
- sketch.update(i);
- }
- union.update(&sketch);
- assert_eq!(union.estimated_size(), 1024);
-}
-
#[test]
fn test_single_hll_input_preserves_estimate_and_bounds() {
for hll_type in HLL_TYPES {
diff --git a/tests-integration/tests/hll_test/update.rs
b/tests-integration/tests/hll_test/update.rs
index 5ec6ac8..50fd0b4 100644
--- a/tests-integration/tests/hll_test/update.rs
+++ b/tests-integration/tests/hll_test/update.rs
@@ -201,18 +201,3 @@ fn test_invalid_lg_k_high_returns_error() {
let error = HllSketch::new(22, HllType::Hll8).unwrap_err();
assert_eq!(error.kind(), ErrorKind::InvalidArgument);
}
-
-#[test]
-fn estimated_size_tracks_retained_storage() {
- let mut sketch = HllSketch::new(10, HllType::Hll8).unwrap();
- let initial_size = sketch.estimated_size();
- assert_eq!(initial_size, 32);
-
- sketch.update(0);
- assert_eq!(sketch.estimated_size(), initial_size);
-
- for i in 1..1000 {
- sketch.update(i);
- }
- assert_eq!(sketch.estimated_size(), 1024);
-}
diff --git a/tests-integration/tests/req_test/query.rs
b/tests-integration/tests/req_test/query.rs
index 20d2fda..4eae968 100644
--- a/tests-integration/tests/req_test/query.rs
+++ b/tests-integration/tests/req_test/query.rs
@@ -41,23 +41,26 @@ fn exact_mode_rank_quantile_pmf_and_cdf_match_reference() {
assert!(!sketch.is_estimation_mode());
assert_eq!(sketch.n(), 10);
assert_eq!(sketch.num_retained(), 10);
+ let view = sketch.sorted_view();
for (value, expected) in [(1.0, 0.0), (2.0, 0.1), (6.0, 0.5), (9.0, 0.8),
(10.0, 0.9)] {
- assert_that!(
- sketch
- .rank(&req_f64(value), SearchCriteria::Exclusive)
- .expect("rank should succeed"),
- near(expected, 1e-6)
- );
+ let value = req_f64(value);
+ for rank in [
+ sketch.rank(&value, SearchCriteria::Exclusive),
+ view.rank(&value, SearchCriteria::Exclusive),
+ ] {
+ assert_that!(rank.unwrap(), near(expected, 1e-6));
+ }
}
for (value, expected) in [(1.0, 0.1), (2.0, 0.2), (5.0, 0.5), (9.0, 0.9),
(10.0, 1.0)] {
- assert_that!(
- sketch
- .rank(&req_f64(value), SearchCriteria::Inclusive)
- .expect("rank should succeed"),
- near(expected, 1e-6)
- );
+ let value = req_f64(value);
+ for rank in [
+ sketch.rank(&value, SearchCriteria::Inclusive),
+ view.rank(&value, SearchCriteria::Inclusive),
+ ] {
+ assert_that!(rank.unwrap(), near(expected, 1e-6));
+ }
}
for (rank, expected) in [(0.0, 1.0), (0.1, 2.0), (0.5, 6.0), (0.9, 10.0),
(1.0, 10.0)] {
diff --git a/tests-integration/tests/req_test/sorted_view_api.rs
b/tests-integration/tests/req_test/sorted_view_api.rs
index 4c4d3d7..86f2f97 100644
--- a/tests-integration/tests/req_test/sorted_view_api.rs
+++ b/tests-integration/tests/req_test/sorted_view_api.rs
@@ -15,19 +15,10 @@
// specific language governing permissions and limitations
// under the License.
-//! Tests for the user-managed SortedView API (ported from reqsketch-rs #25):
-//! distribution queries take `&self`, and `sorted_view()` returns an owned
-//! snapshot instead of relying on an internal cache.
-
use datasketches::common::SearchCriteria;
use datasketches::error::ErrorKind;
use datasketches::req::ReqSketch;
use datasketches::req::SortedView;
-use googletest::assert_that;
-use googletest::prelude::all;
-use googletest::prelude::ge;
-use googletest::prelude::lt;
-use googletest::prelude::near;
use super::ReqF64;
use super::req_f64;
@@ -40,36 +31,6 @@ fn populated_sketch(n: i64) -> ReqSketch<ReqF64> {
sketch
}
-/// All distribution queries must work through a shared (`&self`) reference.
-fn query_through_shared_ref(sketch: &ReqSketch<ReqF64>) {
- sketch
- .quantile(0.5, SearchCriteria::Inclusive)
- .expect("quantile")
- .expect("the sketch is non-empty");
- sketch
- .quantiles(&[0.25, 0.5, 0.75], SearchCriteria::Inclusive)
- .expect("quantiles")
- .expect("the sketch is non-empty");
- sketch
- .rank(&req_f64(50.0), SearchCriteria::Inclusive)
- .expect("rank");
- sketch
- .pmf(&[req_f64(10.0), req_f64(50.0)], SearchCriteria::Inclusive)
- .expect("pmf")
- .expect("the sketch is non-empty");
- sketch
- .cdf(&[req_f64(10.0), req_f64(50.0)], SearchCriteria::Inclusive)
- .expect("cdf")
- .expect("the sketch is non-empty");
- assert!(!sketch.sorted_view().is_empty());
-}
-
-#[test]
-fn queries_work_through_shared_reference() {
- let sketch = populated_sketch(100);
- query_through_shared_ref(&sketch);
-}
-
#[test]
fn sorted_view_is_an_owned_snapshot() {
let mut sketch = populated_sketch(100);
@@ -128,16 +89,6 @@ fn empty_argument_slices_preserve_the_sketch_empty_state() {
}
}
-#[test]
-fn view_rank_is_primary_query_name() {
- let sketch = populated_sketch(10);
- let view = sketch.sorted_view();
- let r = view
- .rank(&req_f64(5.0), SearchCriteria::Inclusive)
- .expect("rank");
- assert_that!(r, near(0.6, 1e-10));
-}
-
#[test]
fn invalid_arguments_are_rejected_regardless_of_sketch_state() {
for n in [0, 1, 1_000] {
@@ -174,24 +125,3 @@ fn view_is_send_and_sync() {
assert_send_sync::<SortedView<ReqF64>>();
assert_send_sync::<ReqSketch<ReqF64>>();
}
-
-#[test]
-fn concurrent_readers_share_the_sketch() {
- let sketch = std::sync::Arc::new(populated_sketch(1_000));
- let handles: Vec<_> = (0..4)
- .map(|i| {
- let sketch = std::sync::Arc::clone(&sketch);
- std::thread::spawn(move || {
- let rank = 0.2 * (i + 1) as f64;
- sketch
- .quantile(rank, SearchCriteria::Inclusive)
- .expect("quantile from shared sketch")
- .expect("the sketch is non-empty")
- })
- })
- .collect();
- for handle in handles {
- let q = handle.join().expect("thread");
- assert_that!(*q, all!(ge(0.0), lt(1_000.0)));
- }
-}
diff --git a/tests-integration/tests/req_test/structure.rs
b/tests-integration/tests/req_test/structure.rs
index 8eff732..ddf20eb 100644
--- a/tests-integration/tests/req_test/structure.rs
+++ b/tests-integration/tests/req_test/structure.rs
@@ -22,9 +22,7 @@ use googletest::assert_that;
use googletest::prelude::each;
use googletest::prelude::eq;
use googletest::prelude::ge;
-use googletest::prelude::gt;
use googletest::prelude::le;
-use googletest::prelude::predicate;
use super::ReqF64;
use super::req_f64;
@@ -65,26 +63,3 @@ fn empty_sketch_iterator_yields_nothing() {
let sketch: ReqSketch<ReqF64> = ReqSketch::default();
assert_eq!(sketch.iter().count(), 0);
}
-
-#[test]
-fn compaction_promotes_surviving_items_to_higher_weights() {
- // After enough updates to trigger compaction, surviving items are
promoted up a
- // level at double weight, so the maximum item weight exceeds 1.
- let mut sketch: ReqSketch<ReqF64> = ReqSketch::default();
- for i in 0..100_000 {
- sketch.update(req_f64(i as f64));
- }
-
- let max_weight = sketch.iter().map(|(_, weight)| weight).max().unwrap();
- assert_that!(max_weight, gt(1));
-
- // Every weight is a power of two (2^level).
- let weights: Vec<_> = sketch.iter().map(|(_, weight)| weight).collect();
- assert_that!(
- weights,
- each(
- predicate(|weight: &u64| weight.is_power_of_two())
- .with_description("is a power of two", "is not a power of two")
- )
- );
-}
diff --git a/tests-integration/tests/serde_tests/frequencies.rs
b/tests-integration/tests/serde_tests/frequencies.rs
index dd301cc..9c1df36 100644
--- a/tests-integration/tests/serde_tests/frequencies.rs
+++ b/tests-integration/tests/serde_tests/frequencies.rs
@@ -64,23 +64,6 @@ fn test_longs_round_trip() {
assert_eq!(restored.maximum_error(), sketch.maximum_error());
}
-#[test]
-fn test_growth_survives_serialization() {
- let mut sketch = FrequentItemsSketch::<i64>::new(1 << 12).unwrap();
- for i in 0..2_000 {
- sketch.update_with_count(i * 7_919 + 13, (i % 5 + 1) as u64);
- }
- let bytes = sketch.serialize();
- let restored = FrequentItemsSketch::<i64>::deserialize(&bytes).unwrap();
- assert_eq!(restored.serialize(), bytes);
- assert_eq!(restored.total_weight(), sketch.total_weight());
- assert_eq!(restored.num_active_items(), 2_000);
- assert_eq!(restored.maximum_error(), 0);
- for i in 0..2_000 {
- assert_eq!(restored.estimate(&(i * 7_919 + 13)), (i % 5 + 1) as u64);
- }
-}
-
#[test]
fn test_items_round_trip() {
let mut sketch = FrequentItemsSketch::new(32).unwrap();
diff --git a/tests-integration/tests/serde_tests/tdigest.rs
b/tests-integration/tests/serde_tests/tdigest.rs
index a426e78..1006e44 100644
--- a/tests-integration/tests/serde_tests/tdigest.rs
+++ b/tests-integration/tests/serde_tests/tdigest.rs
@@ -30,12 +30,6 @@ use googletest::prelude::near;
use crate::serialization_test_data;
-fn fnv1a(bytes: &[u8]) -> u64 {
- bytes.iter().fold(0xcbf2_9ce4_8422_2325, |hash, byte| {
- (hash ^ u64::from(*byte)).wrapping_mul(0x0000_0100_0000_01b3)
- })
-}
-
fn patterned_digest(k: u16, len: usize, salt: usize) -> TDigestMut {
let mut tdigest = TDigestMut::new(k).unwrap();
for index in 0..len {
@@ -263,47 +257,6 @@ fn test_frozen_roundtrip() {
);
}
-#[test]
-fn test_serialized_bytes_stable_for_full_and_merged_digests() {
- let mut full_buffer = patterned_digest(200, 1_641, 0);
- let bytes = full_buffer.serialize();
- assert_eq!(bytes.len(), 2_864);
- assert_eq!(fnv1a(&bytes), 0xaffe_62f2_3716_59b8);
-
- let mut left = patterned_digest(10, 201, 2);
- let mut right = patterned_digest(10, 199, 3);
- right.rank(0.0).unwrap();
- left.merge(&right);
- let bytes = left.serialize();
- assert_eq!(bytes.len(), 272);
- assert_eq!(fnv1a(&bytes), 0x6037_b570_d640_d31f);
-
- for &(left_len, right_len, expected_len, expected_hash) in &[
- (8, 201, 272, 0x4ec5_2661_c556_c10e),
- (201, 8, 256, 0x2b43_056d_9a57_b2a5),
- (201, 401, 288, 0x1e43_34b7_ba13_4fe0),
- (401, 201, 288, 0x6f6d_e965_77a7_a53f),
- ] {
- let mut left = patterned_digest(10, left_len, 2);
- let right = patterned_digest(10, right_len, 3);
- left.merge(&right);
- let bytes = left.serialize();
- assert_eq!(bytes.len(), expected_len);
- assert_eq!(fnv1a(&bytes), expected_hash);
- }
-
- let mut left = patterned_digest(10, 199, 2);
- let left = left.serialize();
- let mut left = TDigestMut::deserialize(&left).unwrap();
- let mut right = patterned_digest(10, 199, 3);
- let right = right.serialize();
- let right = TDigestMut::deserialize(&right).unwrap();
- left.merge(&right);
- let bytes = left.serialize();
- assert_eq!(bytes.len(), 272);
- assert_eq!(fnv1a(&bytes), 0x5759_0428_c175_88ab);
-}
-
#[test]
fn test_updates_normalize_overfull_deserialized_buffer_without_centroids() {
let path = serialization_test_data("cpp_generated_files",
"tdigest_double_buf_n10_cpp.sk");
diff --git a/tests-integration/tests/tdigest_test/sketch.rs
b/tests-integration/tests/tdigest_test/sketch.rs
index 4eba82d..6ad04ab 100644
--- a/tests-integration/tests/tdigest_test/sketch.rs
+++ b/tests-integration/tests/tdigest_test/sketch.rs
@@ -112,58 +112,6 @@ fn test_maximum_k() {
assert_eq!(tdigest.quantile(0.5).unwrap(), Some(1.0));
}
-#[test]
-fn test_estimated_size_reuses_buffer_after_compression() {
- const K: u16 = 200;
- const TARGET_CENTROIDS: usize = 410;
- const MAX_UNMERGED: usize = TARGET_CENTROIDS * 4;
-
- let mut tdigest = TDigestMut::new(K).unwrap();
- assert_eq!(tdigest.estimated_size(), 0);
-
- for value in 0..MAX_UNMERGED {
- tdigest.update(value as f64);
- }
- let size_before_compression = tdigest.estimated_size();
- assert!(size_before_compression > 0);
- tdigest.rank(0.5).unwrap();
- assert!(tdigest.estimated_size() <= size_before_compression);
-
- for value in MAX_UNMERGED..10_000 {
- tdigest.update(value as f64);
- }
- let size_before_compression = tdigest.estimated_size();
- tdigest.rank(0.5).unwrap();
- assert!(tdigest.estimated_size() <= size_before_compression);
-
- let mut left = TDigestMut::new(K).unwrap();
- for value in 0..8 {
- left.update(value as f64);
- }
- let mut right = TDigestMut::new(K).unwrap();
- for value in 0..MAX_UNMERGED {
- right.update(value as f64);
- }
- let right_size = right.estimated_size();
- left.merge(&right);
- assert_eq!(left.total_weight(), (MAX_UNMERGED + 8) as u64);
- assert_eq!(right.total_weight(), MAX_UNMERGED as u64);
- assert_eq!(right.estimated_size(), right_size);
-
- let mut full_left = TDigestMut::new(K).unwrap();
- for value in 0..MAX_UNMERGED {
- full_left.update(value as f64);
- }
- let combined_size = full_left.estimated_size() + right_size;
- full_left.merge(&right);
- assert_eq!(full_left.total_weight(), (MAX_UNMERGED * 2) as u64);
- assert!(full_left.estimated_size() <= combined_size + combined_size / 2);
-
- let mutable_size = full_left.estimated_size();
- let frozen = full_left.freeze();
- assert!(frozen.estimated_size() <= mutable_size);
-}
-
#[test]
fn test_many_values() {
let n = 10000;
@@ -401,85 +349,14 @@ fn
test_from_iter_uses_one_result_with_the_smallest_nonempty_k() {
assert!(quantiles.windows(2).all(|pair| pair[0] <= pair[1]));
}
-#[test]
-fn test_from_iter_matches_single_digest_for_uncompressed_inputs() {
- let values = [3.0, 1.0, 2.0, 2.0, 5.0, 4.0];
- let partials = values
- .chunks(3)
- .map(|values| {
- let mut digest = TDigestMut::new(100).unwrap();
- for &value in values {
- digest.update(value);
- }
- digest
- })
- .collect::<Vec<_>>();
- let mut merged = partials.into_iter().collect::<TDigestMut>();
-
- let mut expected = TDigestMut::new(100).unwrap();
- for value in values {
- expected.update(value);
- }
-
- assert_eq!(merged.serialize(), expected.serialize());
-}
-
-#[test]
-fn test_from_iter_matches_single_compression_for_interleaved_runs() {
- let runs: [&[(f64, u64)]; 4] = [
- &[(0.0, 1), (3.0, 2), (3.0, 5), (6.0, 100), (9.0, 1)],
- &[(0.0, 7), (2.0, 3), (5.0, 4), (8.0, 2), (9.0, 10)],
- &[(1.0, 2), (3.0, 6), (4.0, 1), (7.0, 8), (9.0, 20)],
- &[(0.0, 2), (3.0, 9), (6.0, 7), (9.0, 30)],
- ];
- for k in [10, 100] {
- for reverse in [false, true] {
- let make_digest = |centroids: &[(f64, u64)]| {
- let mut digest = deserialize_with_centroids(k, -10.0, 20.0,
centroids);
- if reverse {
- let mut bytes = digest.serialize();
- bytes[5] |= 1 << 2; // reverse-merge flag
- digest = TDigestMut::deserialize(&bytes).unwrap();
- }
- digest
- };
- let mut ordered = runs
- .iter()
- .flat_map(|run| run.iter().copied())
- .collect::<Vec<_>>();
- ordered.sort_by(|left, right| left.0.total_cmp(&right.0));
-
- // Borrowed merge puts the right input first on ties. Keeping the
last centroid on
- // the left reproduces the concatenated runs' stable order in one
compression pass.
- let last = ordered.pop().unwrap();
- let mut expected = make_digest(&[last]);
- expected.merge(&make_digest(&ordered));
- let mut merged =
runs.into_iter().map(make_digest).collect::<TDigestMut>();
-
- assert_eq!(merged.serialize(), expected.serialize());
- assert_eq!(merged.quantile(0.0).unwrap(), Some(-10.0));
- assert_eq!(merged.quantile(1.0).unwrap(), Some(20.0));
-
- // A collected digest must still support enough updates to grow
and compress again.
- for value in 0..1_000 {
- merged.update(value as f64);
- expected.update(value as f64);
- }
- assert_eq!(merged.serialize(), expected.serialize());
- }
- }
-}
-
#[test]
fn test_from_iter_handles_mixed_compressed_and_buffered_inputs() {
- let mut expected = TDigestMut::new(100).unwrap();
let partials = (0..4)
.map(|run| {
let mut digest = TDigestMut::new(100).unwrap();
for row in 0..60 {
let value = ((row * 13 + run * 7) % 37) as f64;
digest.update(value);
- expected.update(value);
if run == 2 && row == 29 {
let _ = digest.quantile(0.5).unwrap();
}
@@ -493,7 +370,9 @@ fn
test_from_iter_handles_mixed_compressed_and_buffered_inputs() {
let mut merged = partials.into_iter().collect::<TDigestMut>();
assert_eq!(merged.total_weight(), 240);
- assert_eq!(merged.serialize(), expected.serialize());
+ assert_eq!(merged.min_value(), Some(0.0));
+ assert_eq!(merged.max_value(), Some(36.0));
+ assert_that!(merged.quantile(0.5).unwrap().unwrap(), near(18.0, 2.0));
}
#[test]
@@ -737,65 +616,6 @@ fn assert_quantile_queries(tdigest: &TDigestMut, ranks:
&[f64], expected: &[f64]
}
}
-#[test]
-fn test_quantile_moves_toward_the_nearer_bracketing_centroid() {
- let mut tdigest =
- deserialize_with_centroids(100, -1.0, 21.0, &[(0.0, 4), (10.0, 4),
(20.0, 4)]);
-
- assert_eq!(tdigest.total_weight(), 12);
- // Ranks 2/12 and 6/12 sit exactly on the two centroids bracketing the
first interval.
- assert_that!(
- tdigest.quantile(2.0 / 12.0).unwrap().unwrap(),
- near(0.0, 1e-12)
- );
- assert_that!(
- tdigest.quantile(3.0 / 12.0).unwrap().unwrap(),
- near(2.5, 1e-12)
- );
- assert_that!(
- tdigest.quantile(4.0 / 12.0).unwrap().unwrap(),
- near(5.0, 1e-12)
- );
- assert_that!(
- tdigest.quantile(5.0 / 12.0).unwrap().unwrap(),
- near(7.5, 1e-12)
- );
- assert_that!(
- tdigest.quantile(6.0 / 12.0).unwrap().unwrap(),
- near(10.0, 1e-12)
- );
-}
-
-#[test]
-fn test_quantile_right_tail_stays_within_max() {
- let mut tdigest =
- deserialize_with_centroids(100, 0.0, 100.0, &[(10.0, 10), (50.0, 10),
(90.0, 10)]);
-
- assert_eq!(tdigest.max_value(), Some(100.0));
- assert_that!(tdigest.quantile(0.9).unwrap().unwrap(), near(95.0, 1e-12));
- assert_that!(
- tdigest.quantile(29.0 / 30.0).unwrap().unwrap(),
- near(100.0, 1e-12)
- );
- // Mirrors the left tail, which interpolates from min up to the first
centroid mean.
- assert_that!(
- tdigest.quantile(1.0 / 30.0).unwrap().unwrap(),
- near(0.0, 1e-12)
- );
- assert_that!(
- tdigest.quantile(5.0 / 30.0).unwrap().unwrap(),
- near(10.0, 1e-12)
- );
-}
-
-#[test]
-fn test_quantile_handles_two_sample_last_centroid() {
- let mut tdigest =
- deserialize_with_centroids(100, 0.0, 100.0, &[(0.0, 1), (50.0, 1),
(90.0, 2)]);
-
- assert_eq!(tdigest.quantile(0.75).unwrap(), Some(100.0));
-}
-
#[test]
fn test_single_centroid_preserves_stored_tail_information() {
let mut digest = deserialize_with_centroids(100, 0., 100., &[(50., 10)]);
@@ -859,196 +679,7 @@ fn
test_rank_tails_stay_monotonic_after_updating_weighted_centroids() {
}
#[test]
-fn test_small_compression_preserves_weighted_centroids_and_tie_order() {
- // Exercise the no-merge bound at two k values and a tiny input whose K_2
normalizer
- // is negative. Existing weighted centroids must remain intact in every
case.
- for (k, middle_weight) in [(200, 95), (u16::MAX, 2), (u16::MAX, 32_762)] {
- for reverse in [false, true] {
- let mut digest = deserialize_with_centroids(
- k,
- -10.,
- 10.,
- &[(-10., 1), (-0., 1), (0., middle_weight), (1., 1), (10., 1)],
- );
- let mut bytes = digest.serialize();
- if reverse {
- bytes[5] |= 1 << 2;
- }
- let mut digest = TDigestMut::deserialize(&bytes).unwrap();
- digest.update(0.);
-
- // Buffered values precede retained centroids on ties, including
signed zeros.
- let mut expected = deserialize_with_centroids(
- k,
- -10.,
- 10.,
- &[
- (-10., 1),
- (0., 1),
- (-0., 1),
- (0., middle_weight),
- (1., 1),
- (10., 1),
- ],
- )
- .serialize();
- if !reverse {
- expected[5] |= 1 << 2;
- }
- assert_eq!(digest.total_weight(), middle_weight + 5);
- assert_eq!(digest.serialize(), expected);
- }
- }
-}
-
-// Exercise both compression paths and inspect the mean directly; query
interpolation can hide
-// rounding errors. The heavy outer centroids keep the middle pair away from
the protected tails.
-fn merged_centroid_mean(centroids: [(f64, u64); 4], reverse: bool, owned:
bool) -> f64 {
- let min = centroids[0].0;
- let max = centroids[3].0;
- let mut bytes = deserialize_with_centroids(10, min, max,
¢roids).serialize();
- if reverse {
- bytes[5] |= 1 << 2;
- }
- let mut digest = TDigestMut::deserialize(&bytes).unwrap();
- if owned {
- let other = deserialize_with_centroids(10, max, max, &[(max, 1)]);
- digest = [digest, other].into_iter().collect();
- } else {
- digest.update(min);
- }
- let bytes = digest.serialize();
- let merged_weight = centroids[1].1 + centroids[2].1;
- let centroid = bytes[32..]
- .chunks_exact(16)
- .find(|c| u64::from_le_bytes(c[8..].try_into().unwrap()) ==
merged_weight)
- .unwrap_or_else(|| {
- panic!(
- "middle pair {:?} did not merge (reverse={reverse},
owned={owned})",
- ¢roids[1..3]
- )
- });
- f64::from_le_bytes(centroid[..8].try_into().unwrap())
-}
-
-#[test]
-fn test_compression_preserves_a_small_centroid_weight() {
- for weight in [1_u64 << 20, 1_u64 << 40, 1_u64 << 54] {
- for reverse in [false, true] {
- let mean = merged_centroid_mean(
- [(0., weight), (1., weight), (1e300, 1), (f64::MAX, weight)],
- reverse,
- false,
- );
- // The exact mean is (weight * 1 + 1e300) / (weight + 1). The
first term is far
- // below one ULP of the numerator, so this division is an
independent reference.
- let expected = 1e300 / (weight + 1) as f64;
- assert_that!(mean / expected, near(1., 4. * f64::EPSILON));
- }
- }
-}
-
-#[test]
-fn test_opposite_sign_merge_preserves_a_representable_correction() {
- let outer_weight = 1_u64 << 56;
- for magnitude in [1., f64::MAX] {
- for exponent in [54, 55] {
- let total_weight = 1_u64 << exponent;
- // The exact mean is magnitude * (1 - 2 / total_weight). At 2^54 it
- // rounds to the next value toward zero; at 2^55 it rounds back to
magnitude.
- let expected = if exponent == 54 {
- magnitude.next_down()
- } else {
- magnitude
- };
- for negative_heavy in [false, true] {
- let (left_weight, right_weight, expected) = if negative_heavy {
- (total_weight - 1, 1, -expected)
- } else {
- (1, total_weight - 1, expected)
- };
- for reverse in [false, true] {
- for owned in [false, true] {
- let mean = merged_centroid_mean(
- [
- (-f64::MAX, outer_weight),
- (-magnitude, left_weight),
- (magnitude, right_weight),
- (f64::MAX, outer_weight),
- ],
- reverse,
- owned,
- );
- assert_eq!(
- mean, expected,
- "magnitude={magnitude:?}, exponent={exponent},
negative_heavy={negative_heavy}, reverse={reverse}, owned={owned}"
- );
- }
- }
- }
- }
- }
-}
-
-#[test]
-fn test_compression_keeps_merged_means_within_their_endpoints() {
- let tiny = f64::from_bits(1);
- let heavy = 1_u64 << 54;
- for (left, right) in [
- (0., tiny),
- (tiny, 2. * tiny),
- (f64::MIN_POSITIVE.next_down(), f64::MIN_POSITIVE),
- (1., 1_f64.next_up()),
- (f64::MAX.next_down(), f64::MAX),
- (f64::MAX / 4., f64::MAX),
- (-f64::MAX, -f64::MAX / 4.),
- (-2. * tiny, -tiny),
- (-tiny, tiny),
- (-f64::MAX, f64::MAX),
- ] {
- for (left_weight, right_weight) in [(1, 1), (1, heavy), (heavy, 1)] {
- for reverse in [false, true] {
- for owned in [false, true] {
- let mean = merged_centroid_mean(
- [
- (-f64::MAX, heavy),
- (left, left_weight),
- (right, right_weight),
- (f64::MAX, heavy),
- ],
- reverse,
- owned,
- );
- assert!(
- mean.is_finite() && (left..=right).contains(&mean),
- "{mean:?} is outside [{left:?}, {right:?}]
(weights={left_weight}:{right_weight}, reverse={reverse}, owned={owned})"
- );
- }
- }
- }
- }
-}
-
-#[test]
-fn test_signed_zero_and_symmetric_centroids_survive_interpolation() {
- for magnitude in [0., f64::from_bits(1), 1., f64::MAX] {
- let heavy = 1_u64 << 54;
- for reverse in [false, true] {
- let mean = merged_centroid_mean(
- [
- (-f64::MAX, heavy),
- (-magnitude, 1),
- (magnitude, 1),
- (f64::MAX, heavy),
- ],
- reverse,
- false,
- );
- // Equal and opposite contributions cancel exactly, including
subnormal values.
- assert_eq!(mean, 0.);
- }
- }
-
+fn test_signed_zero_queries_are_consistent() {
let mut digest =
deserialize_with_centroids(100, -1., 1., &[(-1., 1), (-0., 2), (0.,
2), (1., 1)]);
assert_eq!(digest.rank(-0.).unwrap(), Some(0.5));
@@ -1193,10 +824,17 @@ fn
test_quantiles_stay_within_extrema_at_large_total_weights() {
#[test]
fn test_queries_stay_ordered_at_large_centroid_centers() {
- for total_weight in [1_u64 << 53, 1_u64 << 54, u64::MAX] {
+ for total_weight in [
+ (1_u64 << 53) - 2,
+ (1_u64 << 53) - 1,
+ (1_u64 << 53) + 2,
+ 1_u64 << 54,
+ u64::MAX,
+ ] {
for centroids in [
vec![(10., total_weight - 5), (50., 1), (90., 4)],
vec![(0., 1), (90., total_weight - 1)],
+ vec![(0., total_weight - 3), (90., 3)],
] {
let digest = deserialize_with_centroids(100, 0., 100.,
¢roids).freeze();
// Probe either side of a heavy centroid's center and the rounded
upper endpoint.
@@ -1217,104 +855,30 @@ fn
test_queries_stay_ordered_at_large_centroid_centers() {
);
assert!(quantiles.iter().all(|value|
(0.0..=100.0).contains(value)));
- let cdf = digest
- .cdf(&[0., 5., 10., 50., 90., 95., 100.])
- .unwrap()
- .unwrap();
+ let points = [
+ 0.,
+ 5.,
+ 10.,
+ 50.,
+ 90.,
+ 90_f64.next_up(),
+ 100_f64.next_down(),
+ 100.,
+ ];
+ let cdf = digest.cdf(&points).unwrap().unwrap();
assert!(cdf.is_sorted(), "centroids {centroids:?}: {cdf:?}");
assert!(cdf.iter().all(|rank| (0.0..=1.0).contains(rank)));
+ let pmf = digest.pmf(&points).unwrap().unwrap();
+ assert!(pmf.iter().all(|&mass| mass >= 0.));
}
}
}
-#[test]
-fn test_quantile_right_tail_uses_the_same_center_as_rank() {
- for (total_weight, last_weight, rank) in [
- (1_u64 << 53, 5, 1. - f64::EPSILON),
- ((1_u64 << 53) + 1, 4, 1_f64.next_down()),
- (1_u64 << 54, 9, 1. - f64::EPSILON),
- (u64::MAX, 4097, 1_f64.next_down()),
- ] {
- let mut digest = deserialize_with_centroids(
- 100,
- 0.,
- 100.,
- &[(0., total_weight - last_weight), (90., last_weight)],
- );
- // These ranks land exactly on the rounded mass N - last_weight/2.
Quantile must
- // return the centroid mean there, before interpolating toward the
stored maximum.
- assert_eq!(digest.rank(90.).unwrap(), Some(rank));
- assert_quantile_queries(&digest, &[rank, rank, 1.], &[90., 90., 100.]);
- }
-
- // At N = 2^53 + 2 the last center and N - 1 round to the same mass. The
zero-width
- // tail must stay finite and ordered, just as a two-sample tail does at
smaller counts.
- let total_weight = (1_u64 << 53) + 2;
- let digest = deserialize_with_centroids(100, 0., 100., &[(0., total_weight
- 3), (90., 3)]);
- let rank = 1. - f64::EPSILON;
- let ranks = [rank.next_down(), rank, rank.next_up(), 1.];
- let quantiles = digest.clone().quantiles(&ranks).unwrap().unwrap();
- assert!(quantiles.is_sorted());
- assert!(quantiles.iter().all(|value| (0.0..=100.0).contains(value)));
- assert_eq!(quantiles[3], 100.);
- assert_quantile_queries(&digest, &ranks, &quantiles);
-}
-
-#[test]
-fn test_quantile_uses_max_when_last_center_rounds_down() {
- let total_weight = (1_u64 << 53) - 1;
- let first_weight = (total_weight - 1) / 2;
- let middle_weight = total_weight - first_weight - 1;
- let digest = deserialize_with_centroids(
- 100,
- 0.,
- 100.,
- &[(10., first_weight), (50., middle_weight), (90., 1)],
- );
-
- // The last center's +0.5 ties down to the even count 2^53 - 2. The
highest rank
- // below 1 lands there and exhausts the scan; the adjacent rank stays
inside it.
- assert_quantile_queries(
- &digest,
- &[1. - f64::EPSILON, 1_f64.next_down()],
- &[90_f64.next_down(), 100.],
- );
-}
-
-#[test]
-fn test_rank_max_uses_the_same_rounded_mass_as_last_centroid() {
- // The last half-sample center can round up or down. At N = 2^53 - 2 it
rounds to N,
- // while 1 - 0.5/N rounds below 1 and would give max a lower rank than the
last mean.
- for (total_weight, expected) in [
- ((1_u64 << 53) - 2, 1.),
- ((1_u64 << 53) - 1, 1_f64.next_down()),
- (u64::MAX, 1.),
- ] {
- let mut digest =
- deserialize_with_centroids(100, 0., 100., &[(0., total_weight -
1), (90., 1)]);
- let frozen = digest.clone().freeze();
- let points = [90., 90_f64.next_up(), 95., 100_f64.next_down(), 100.];
- let cdf = digest.cdf(&points).unwrap().unwrap();
- assert_eq!(&cdf[..points.len()], &[expected; 5]);
- assert_eq!(cdf, frozen.cdf(&points).unwrap().unwrap());
- assert!(
- frozen
- .pmf(&points)
- .unwrap()
- .unwrap()
- .iter()
- .all(|&mass| mass >= 0.)
- );
- }
-}
-
#[test]
fn test_rank_stays_monotonic_at_the_right_tail_boundary() {
let digest = deserialize_with_centroids(100, 0., 300., &[(0., 1), (100.,
29)]).freeze();
let points = [100., 100_f64.next_up(), 150., 300.];
let cdf = digest.cdf(&points).unwrap().unwrap();
- // The last center is at weight 1 + 29/2 = 15.5. Entering the tail must
not lower its rank.
- assert_eq!(cdf[0], 15.5 / 30.);
assert!(cdf.is_sorted(), "CDF at {points:?}: {cdf:?}");
}
diff --git a/tests-integration/tests/theta_test/intersection.rs
b/tests-integration/tests/theta_test/intersection.rs
index f6068a1..5cab864 100644
--- a/tests-integration/tests/theta_test/intersection.rs
+++ b/tests-integration/tests/theta_test/intersection.rs
@@ -322,13 +322,3 @@ fn test_seed_mismatch_non_empty_returns_error() {
let mut i = ThetaIntersection::with_seed(123).unwrap();
assert_that!(i.update(&s), err(anything()));
}
-
-#[test]
-fn test_intersection_estimated_size() {
- let mut intersection = ThetaIntersection::default();
- assert_eq!(intersection.estimated_size(), 0);
-
- let sketch = sketch_with_range(0, 1000);
- intersection.update(&sketch).unwrap();
- assert_eq!(intersection.estimated_size(), 16384);
-}
diff --git a/tests-integration/tests/theta_test/sketch.rs
b/tests-integration/tests/theta_test/sketch.rs
index cd43f36..b900ab1 100644
--- a/tests-integration/tests/theta_test/sketch.rs
+++ b/tests-integration/tests/theta_test/sketch.rs
@@ -157,7 +157,6 @@ fn test_reset() {
assert_that!(sketch.num_retained(), gt(32));
assert_that!(sketch.theta(), lt(1.0));
- assert_eq!(sketch.estimated_size(), 512);
sketch.reset();
assert!(sketch.is_empty());
assert_eq!(sketch.estimate(), 0.0);
@@ -166,7 +165,6 @@ fn test_reset() {
assert!(!sketch.is_estimation_mode());
assert_eq!(sketch.lower_bound(NumStdDev::One), 0.0);
assert_eq!(sketch.upper_bound(NumStdDev::One), 0.0);
- assert_eq!(sketch.estimated_size(), 512);
}
#[test]
diff --git a/tests-integration/tests/theta_test/union.rs
b/tests-integration/tests/theta_test/union.rs
index 3935b82..d60c69a 100644
--- a/tests-integration/tests/theta_test/union.rs
+++ b/tests-integration/tests/theta_test/union.rs
@@ -730,24 +730,3 @@ fn test_corner_case_union_states() {
assert_eq!(compact_result.is_empty(), expected_empty);
}
}
-
-#[test]
-fn test_union_estimated_size() {
- let mut union = ThetaUnionBuilder::default().build().unwrap();
- assert_eq!(union.estimated_size(), 1024);
-
- let sketch = sketch_with_range(12, 0, 1000);
- union.update(&sketch).unwrap();
- assert_eq!(union.estimated_size(), 65536);
-}
-
-#[test]
-fn compact_estimated_size_includes_retained_capacity() {
- let sketch = sketch_with_range(5, 0, 1000);
- let mut union = ThetaUnionBuilder::default().lg_k(5).build().unwrap();
- union.update(&sketch).unwrap();
- let result = union.to_sketch(true);
-
- assert_eq!(result.num_retained(), 32);
- assert_eq!(result.estimated_size(), 512);
-}
diff --git a/tests-integration/tests/tuple_test/intersection.rs
b/tests-integration/tests/tuple_test/intersection.rs
index d01381a..32a4438 100644
--- a/tests-integration/tests/tuple_test/intersection.rs
+++ b/tests-integration/tests/tuple_test/intersection.rs
@@ -181,13 +181,3 @@ fn estimation_bounds_cover_the_true_intersection() {
assert!(result.is_estimation_mode());
assert_that!(25_000.0, all!(ge(lower), le(upper)));
}
-
-#[test]
-fn intersection_estimated_size_grows_with_updates() {
- let mut intersection = TupleIntersection::new(SumPolicy);
- assert_eq!(intersection.estimated_size(), 0);
-
- let sketch = tuple_sketch_with_range(0, 1000);
- intersection.update(&sketch).unwrap();
- assert_eq!(intersection.estimated_size(), 32768);
-}
diff --git a/tests-integration/tests/tuple_test/sketch.rs
b/tests-integration/tests/tuple_test/sketch.rs
index 694644e..194060d 100644
--- a/tests-integration/tests/tuple_test/sketch.rs
+++ b/tests-integration/tests/tuple_test/sketch.rs
@@ -131,67 +131,6 @@ fn
custom_update_policy_accepts_multiple_value_representations() {
);
}
-#[test]
-fn estimated_size_is_shallow_for_generic_summaries() {
- let mut small_summary_sketch = TupleSketchBuilder::new(ArraySumPolicy {
num_values: 1 })
- .build()
- .unwrap();
- small_summary_sketch.update("key", [1.0]);
-
- let mut large_summary_sketch = TupleSketchBuilder::new(ArraySumPolicy {
num_values: 1024 })
- .build()
- .unwrap();
- large_summary_sketch.update("key", vec![1.0; 1024]);
-
- assert_eq!(
- small_summary_sketch.estimated_size(),
- large_summary_sketch.estimated_size()
- );
- assert_eq!(
- small_summary_sketch.compact(false).estimated_size(),
- large_summary_sketch.compact(false).estimated_size()
- );
-}
-
-struct PaddedArraySumPolicy {
- inner: ArraySumPolicy,
- _padding: [u8; 1024],
-}
-
-impl SummaryPolicy for PaddedArraySumPolicy {
- type Summary = Vec<f64>;
-
- fn create(&self) -> Self::Summary {
- self.inner.create()
- }
-}
-
-impl<U> SummaryUpdatePolicy<U> for PaddedArraySumPolicy
-where
- U: AsRef<[f64]>,
-{
- fn update(&self, summary: &mut Self::Summary, value: U) {
- self.inner.update(summary, value);
- }
-}
-
-#[test]
-fn estimated_size_includes_policy_inline_storage() {
- let mut small_policy_sketch = TupleSketchBuilder::new(ArraySumPolicy {
num_values: 1 })
- .build()
- .unwrap();
- small_policy_sketch.update("key", [1.0]);
-
- let policy = PaddedArraySumPolicy {
- inner: ArraySumPolicy { num_values: 1 },
- _padding: [0; 1024],
- };
- let mut large_policy_sketch =
TupleSketchBuilder::new(policy).build().unwrap();
- large_policy_sketch.update("key", [1.0]);
-
- assert!(large_policy_sketch.estimated_size() >
small_policy_sketch.estimated_size());
-}
-
#[test]
fn trim_and_reset_update_public_state() {
let mut sketch = default_tuple_sketch_builder().lg_k(5).build().unwrap();
diff --git a/tests-integration/tests/tuple_test/union.rs
b/tests-integration/tests/tuple_test/union.rs
index 6c23c10..496838c 100644
--- a/tests-integration/tests/tuple_test/union.rs
+++ b/tests-integration/tests/tuple_test/union.rs
@@ -182,24 +182,3 @@ fn estimation_bounds_cover_the_true_union() {
assert!(result.is_estimation_mode());
assert_that!(75_000.0, all!(ge(lower), le(upper)));
}
-
-#[test]
-fn union_estimated_size_grows_with_updates() {
- let mut union = default_union_builder().build().unwrap();
- assert_eq!(union.estimated_size(), 2048);
-
- let sketch = tuple_sketch_with_range(0, 1000);
- union.update(&sketch).unwrap();
- assert_eq!(union.estimated_size(), 131072);
-}
-
-#[test]
-fn compact_estimated_size_includes_retained_capacity() {
- let sketch = tuple_sketch_with_range(0, 1000);
- let mut union = default_union_builder().lg_k(5).build().unwrap();
- union.update(&sketch).unwrap();
- let result = union.to_sketch(true);
-
- assert_eq!(result.num_retained(), 32);
- assert_eq!(result.estimated_size(), 1024);
-}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]