You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by ti...@apache.org on 2026/07/28 07:06:56 UTC
(datasketches-rust) 07/08: test(tuple): keep observable contracts at public boundary
This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch codex/analyze-crate-tests
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
commit a93e3c94b4257a2596c58bf11bcd70a4f5a7de9d
Author: tison <wa...@gmail.com>
AuthorDate: Tue Jul 28 14:51:32 2026 +0800
test(tuple): keep observable contracts at public boundary
---
datasketches/src/tuple/a_not_b.rs | 241 ------------------
datasketches/src/tuple/intersection.rs | 227 -----------------
datasketches/src/tuple/policy.rs | 67 -----
datasketches/src/tuple/serialization.rs | 35 ---
datasketches/src/tuple/sketch.rs | 244 ------------------
datasketches/src/tuple/union.rs | 224 -----------------
datasketches/tests/serde_tests/tuple.rs | 15 ++
datasketches/tests/tuple_test/a_not_b.rs | 283 ++++++++-------------
datasketches/tests/tuple_test/intersection.rs | 342 ++++++++------------------
datasketches/tests/tuple_test/main.rs | 1 +
datasketches/tests/tuple_test/sketch.rs | 281 +++++----------------
datasketches/tests/tuple_test/union.rs | 153 ++++++++++++
12 files changed, 432 insertions(+), 1681 deletions(-)
diff --git a/datasketches/src/tuple/a_not_b.rs b/datasketches/src/tuple/a_not_b.rs
index 16c9355..c24c559 100644
--- a/datasketches/src/tuple/a_not_b.rs
+++ b/datasketches/src/tuple/a_not_b.rs
@@ -99,244 +99,3 @@ impl TupleANotB {
))
}
}
-
-#[cfg(test)]
-mod tests {
- use super::*;
- use crate::common::NumStdDev;
- use crate::error::ErrorKind;
- use crate::tuple::DefaultUpdatePolicy;
- use crate::tuple::TupleSketchBuilder;
-
- fn default_sketch_builder() -> TupleSketchBuilder<DefaultUpdatePolicy<u64>> {
- TupleSketchBuilder::new(DefaultUpdatePolicy::<u64>::default())
- }
-
- fn sorted_entries(sketch: &CompactTupleSketch<u64>) -> Vec<(u64, u64)> {
- let mut entries: Vec<(u64, u64)> = sketch.iter().map(|(h, &s)| (h, s)).collect();
- entries.sort_unstable();
- entries
- }
-
- #[test]
- fn a_not_b_basic_difference() {
- let mut a = default_sketch_builder().build();
- for i in 0..1000 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().build();
- for i in 500..1500 {
- b.update(i, 1u64);
- }
-
- let result = TupleANotB::default().compute(&a, &b, true).unwrap();
- // Keys 0..500 are only in A (exact mode).
- assert_eq!(result.num_retained(), 500);
- assert_eq!(result.estimate(), 500.0);
- }
-
- #[test]
- fn a_not_b_keeps_summaries_from_a() {
- let mut a = default_sketch_builder().build();
- a.update("only_a", 7u64);
- a.update("shared", 7u64);
- let mut b = default_sketch_builder().build();
- b.update("shared", 99u64);
-
- let result = TupleANotB::default().compute(&a, &b, true).unwrap();
- assert_eq!(result.num_retained(), 1);
- // The surviving key keeps A's summary; B's summary is never combined in.
- assert_eq!(result.iter().next().unwrap().1, &7);
- }
-
- #[test]
- fn a_not_b_with_empty_b_returns_a() {
- let mut a = default_sketch_builder().build();
- for i in 0..100 {
- a.update(i, 3u64);
- }
- let b = default_sketch_builder().build();
-
- let result = TupleANotB::default().compute(&a, &b, true).unwrap();
- assert_eq!(result.num_retained(), 100);
- assert!(result.iter().all(|(_, &s)| s == 3));
- }
-
- #[test]
- fn a_not_b_with_empty_a_is_empty() {
- let a = default_sketch_builder().build();
- let mut b = default_sketch_builder().build();
- for i in 0..100 {
- b.update(i, 1u64);
- }
-
- let result = TupleANotB::default().compute(&a, &b, true).unwrap();
- assert!(result.is_empty());
- assert_eq!(result.num_retained(), 0);
- assert_eq!(result.estimate(), 0.0);
- }
-
- #[test]
- fn a_not_b_with_superset_b_is_empty() {
- let mut a = default_sketch_builder().build();
- for i in 0..500 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().build();
- for i in 0..1000 {
- b.update(i, 1u64);
- }
-
- let result = TupleANotB::default().compute(&a, &b, true).unwrap();
- assert_eq!(result.num_retained(), 0);
- assert_eq!(result.estimate(), 0.0);
- }
-
- #[test]
- fn a_not_b_with_disjoint_b_returns_a() {
- let mut a = default_sketch_builder().build();
- for i in 0..500 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().build();
- for i in 500..1000 {
- b.update(i, 1u64);
- }
-
- let result = TupleANotB::default().compute(&a, &b, true).unwrap();
- assert_eq!(result.num_retained(), 500);
- }
-
- #[test]
- fn a_not_b_accepts_updatable_and_compact_inputs() {
- let mut a = default_sketch_builder().build();
- for i in 0..1000 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().build();
- for i in 500..1500 {
- b.update(i, 1u64);
- }
- let b_compact = b.compact(true);
-
- // a (updatable) not b (compact)
- let result = TupleANotB::default().compute(&a, &b_compact, true).unwrap();
- assert_eq!(result.num_retained(), 500);
-
- // a (compact) not b (compact)
- let a_compact = a.compact(true);
- let result2 = TupleANotB::default()
- .compute(&a_compact, &b_compact, true)
- .unwrap();
- assert_eq!(result2.num_retained(), 500);
- }
-
- #[test]
- fn a_not_b_ordered_merge_matches_hash_set_path() {
- // In estimation mode, the both-ordered merge-scan path must produce the same result as
- // the hash-set path taken for unordered inputs.
- let mut a = default_sketch_builder().lg_k(8).build();
- for i in 0..75000 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().lg_k(8).build();
- for i in 25000..75000 {
- b.update(i, 2u64);
- }
- assert!(a.is_estimation_mode() && b.is_estimation_mode());
-
- let op = TupleANotB::default();
- let unordered = op.compute(&a, &b, true).unwrap();
- let ordered = op
- .compute(&a.compact(true), &b.compact(true), true)
- .unwrap();
-
- assert!(ordered.is_ordered());
- assert_eq!(unordered.theta64(), ordered.theta64());
- assert_eq!(sorted_entries(&unordered), sorted_entries(&ordered));
- }
-
- #[test]
- fn a_not_b_result_is_ordered_when_requested() {
- let mut a = default_sketch_builder().build();
- for i in 0..1000 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().build();
- for i in 500..1500 {
- b.update(i, 1u64);
- }
-
- let result = TupleANotB::default().compute(&a, &b, true).unwrap();
- assert!(result.is_ordered());
- let entries = sorted_entries(&result);
- let iter_order: Vec<u64> = result.iter().map(|(h, _)| h).collect();
- let sorted_order: Vec<u64> = entries.iter().map(|(h, _)| *h).collect();
- assert_eq!(iter_order, sorted_order);
- }
-
- #[test]
- fn a_not_b_rejects_seed_mismatch() {
- let mut a = default_sketch_builder().seed(1).build();
- a.update(1, 1u64);
- let mut b = default_sketch_builder().seed(1).build();
- b.update(2, 1u64);
-
- let err = TupleANotB::with_seed(2).compute(&a, &b, true).unwrap_err();
- assert_eq!(err.kind(), ErrorKind::InvalidArgument);
- }
-
- #[test]
- fn a_not_b_validates_a_seed_even_when_b_is_empty() {
- // A is non-empty with a seed that does not match the operator; B is empty. The empty-B fast
- // path must not bypass A's seed check.
- let mut a = default_sketch_builder().seed(1).build();
- a.update(1, 1u64);
- let b = default_sketch_builder().seed(1).build(); // empty
-
- let err = TupleANotB::with_seed(2).compute(&a, &b, true).unwrap_err();
- assert_eq!(err.kind(), ErrorKind::InvalidArgument);
- }
-
- #[test]
- fn a_not_b_empty_b_returns_a_for_non_empty_zero_retained_a() {
- // A is logically non-empty but retains no keys (the single update is screened out by the
- // sampling theta).
- let mut a = default_sketch_builder().sampling_probability(0.001).build();
- a.update(1u64, 1u64);
- assert!(!a.is_empty());
- assert_eq!(a.num_retained(), 0);
-
- // B is empty and built with a different seed. Since an empty B subtracts nothing, the
- // result must be a copy of A: no seed error, and A's theta is preserved (not
- // lowered by B).
- let b = default_sketch_builder().seed(999).build();
-
- let result = TupleANotB::default().compute(&a, &b, true).unwrap();
- assert!(!result.is_empty());
- assert_eq!(result.num_retained(), 0);
- assert_eq!(result.theta64(), a.theta64());
- }
-
- #[test]
- fn a_not_b_in_estimation_mode_estimates_within_bounds() {
- let mut a = default_sketch_builder().lg_k(8).build();
- for i in 0..75000 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().lg_k(8).build();
- for i in 25000..75000 {
- b.update(i, 1u64);
- }
-
- let result = TupleANotB::default().compute(&a, &b, true).unwrap();
- assert!(result.is_estimation_mode());
- // True difference size is 25000 (keys 0..25000).
- let lower = result.lower_bound(NumStdDev::Three);
- let upper = result.upper_bound(NumStdDev::Three);
- assert!(
- lower <= 25000.0 && 25000.0 <= upper,
- "expected 25000 in [{lower}, {upper}]"
- );
- }
-}
diff --git a/datasketches/src/tuple/intersection.rs b/datasketches/src/tuple/intersection.rs
index 531a7ea..58524d4 100644
--- a/datasketches/src/tuple/intersection.rs
+++ b/datasketches/src/tuple/intersection.rs
@@ -155,230 +155,3 @@ where
)
}
}
-
-#[cfg(test)]
-mod tests {
- use super::*;
- use crate::tuple::DefaultUpdatePolicy;
- use crate::tuple::SummaryPolicy;
- use crate::tuple::TupleSketchBuilder;
-
- #[derive(Debug, Default, Clone, Copy)]
- struct SumPolicy;
-
- impl SummaryPolicy for SumPolicy {
- type Summary = u64;
-
- fn create(&self) -> Self::Summary {
- 0
- }
- }
-
- impl SummaryCombinePolicy for SumPolicy {
- fn combine(&self, summary: &mut Self::Summary, other: &Self::Summary) {
- *summary += *other;
- }
- }
-
- fn default_sketch_builder() -> TupleSketchBuilder<DefaultUpdatePolicy<u64>> {
- TupleSketchBuilder::new(DefaultUpdatePolicy::<u64>::default())
- }
-
- fn sorted_entries(sketch: &CompactTupleSketch<u64>) -> Vec<(u64, u64)> {
- let mut entries: Vec<(u64, u64)> = sketch.iter().map(|(h, &s)| (h, s)).collect();
- entries.sort_unstable();
- entries
- }
-
- #[test]
- fn intersection_of_overlapping_sketches() {
- let mut a = default_sketch_builder().build();
- for i in 0..1000 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().build();
- for i in 500..1500 {
- b.update(i, 1u64);
- }
-
- let mut intersection = TupleIntersection::new(SumPolicy);
- intersection.update(&a).unwrap();
- intersection.update(&b).unwrap();
-
- let result = intersection.to_sketch(true);
- // Keys 500..1000 are shared (exact mode), each summary is 1 + 1 = 2.
- assert_eq!(result.num_retained(), 500);
- assert_eq!(result.estimate(), 500.0);
- assert!(result.iter().all(|(_, &s)| s == 2));
- }
-
- #[test]
- fn intersection_combines_summaries_of_shared_keys() {
- let mut a = default_sketch_builder().build();
- a.update("shared", 3u64);
- a.update("only_a", 100u64);
- let mut b = default_sketch_builder().build();
- b.update("shared", 4u64);
- b.update("only_b", 200u64);
-
- let mut intersection = TupleIntersection::new(SumPolicy);
- intersection.update(&a).unwrap();
- intersection.update(&b).unwrap();
-
- let result = intersection.to_sketch(true);
- assert_eq!(sorted_entries(&result).len(), 1);
- assert_eq!(result.iter().next().unwrap().1, &7); // 3 + 4
- }
-
- #[test]
- fn intersection_is_order_independent() {
- let mut a = default_sketch_builder().build();
- for i in 0..1000 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().build();
- for i in 500..1500 {
- b.update(i, 1u64);
- }
-
- let mut a_then_b = TupleIntersection::new(SumPolicy);
- a_then_b.update(&a).unwrap();
- a_then_b.update(&b).unwrap();
-
- let mut b_then_a = TupleIntersection::new(SumPolicy);
- b_then_a.update(&b).unwrap();
- b_then_a.update(&a).unwrap();
-
- assert_eq!(
- sorted_entries(&a_then_b.to_sketch(true)),
- sorted_entries(&b_then_a.to_sketch(true))
- );
- }
-
- #[test]
- fn intersection_accepts_updatable_and_compact_inputs() {
- let mut a = default_sketch_builder().build();
- for i in 0..1000 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().build();
- for i in 500..1500 {
- b.update(i, 1u64);
- }
- let b_compact = b.compact(true);
-
- let mut intersection = TupleIntersection::new(SumPolicy);
- intersection.update(&a).unwrap();
- intersection.update(&b_compact).unwrap();
-
- assert_eq!(intersection.to_sketch(true).num_retained(), 500);
- }
-
- #[test]
- fn intersection_with_disjoint_sketches_is_empty() {
- let mut a = default_sketch_builder().build();
- for i in 0..1000 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().build();
- for i in 1000..2000 {
- b.update(i, 1u64);
- }
-
- let mut intersection = TupleIntersection::new(SumPolicy);
- intersection.update(&a).unwrap();
- intersection.update(&b).unwrap();
-
- let result = intersection.to_sketch(true);
- assert_eq!(result.num_retained(), 0);
- assert_eq!(result.estimate(), 0.0);
- }
-
- #[test]
- fn intersection_with_empty_input_is_empty() {
- let mut a = default_sketch_builder().build();
- for i in 0..1000 {
- a.update(i, 1u64);
- }
- let empty = default_sketch_builder().build();
-
- let mut intersection = TupleIntersection::new(SumPolicy);
- intersection.update(&a).unwrap();
- intersection.update(&empty).unwrap();
-
- let result = intersection.to_sketch(true);
- assert!(result.is_empty());
- assert_eq!(result.num_retained(), 0);
- assert_eq!(result.estimate(), 0.0);
- }
-
- #[test]
- fn intersection_single_update_returns_input() {
- let mut a = default_sketch_builder().build();
- for i in 0..100 {
- a.update(i, 5u64);
- }
-
- let mut intersection = TupleIntersection::new(SumPolicy);
- intersection.update(&a).unwrap();
-
- let result = intersection.to_sketch(true);
- assert_eq!(result.num_retained(), 100);
- // A single update copies the input unchanged (summaries not combined with anything).
- assert!(result.iter().all(|(_, &s)| s == 5));
- }
-
- #[test]
- fn has_result_reflects_first_update() {
- let mut intersection = TupleIntersection::new(SumPolicy);
- assert!(!intersection.has_result());
-
- let mut a = default_sketch_builder().build();
- a.update(1, 1u64);
- intersection.update(&a).unwrap();
- assert!(intersection.has_result());
- }
-
- #[test]
- #[should_panic(expected = "before first update")]
- fn result_before_update_panics() {
- let intersection = TupleIntersection::new(SumPolicy);
- let _ = intersection.to_sketch(true);
- }
-
- #[test]
- fn intersection_rejects_seed_mismatch() {
- let mut a = default_sketch_builder().seed(1).build();
- a.update(1, 1u64);
-
- let mut intersection = TupleIntersection::with_seed(SumPolicy, 2);
- let err = intersection.update(&a).unwrap_err();
- assert_eq!(err.kind(), crate::error::ErrorKind::InvalidArgument);
- }
-
- #[test]
- fn intersection_in_estimation_mode_estimates_within_bounds() {
- let mut a = default_sketch_builder().lg_k(8).build();
- for i in 0..50000 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().lg_k(8).build();
- for i in 25000..75000 {
- b.update(i, 1u64);
- }
-
- let mut intersection = TupleIntersection::new(SumPolicy);
- intersection.update(&a).unwrap();
- intersection.update(&b).unwrap();
-
- let result = intersection.to_sketch(true);
- assert!(result.is_estimation_mode());
- // True intersection size is 25000 (keys 25000..50000).
- let lower = result.lower_bound(crate::common::NumStdDev::Three);
- let upper = result.upper_bound(crate::common::NumStdDev::Three);
- assert!(
- lower <= 25000.0 && 25000.0 <= upper,
- "expected 25000 in [{lower}, {upper}]"
- );
- }
-}
diff --git a/datasketches/src/tuple/policy.rs b/datasketches/src/tuple/policy.rs
index 70b3fae..05646e0 100644
--- a/datasketches/src/tuple/policy.rs
+++ b/datasketches/src/tuple/policy.rs
@@ -119,70 +119,3 @@ where
*summary += other;
}
}
-
-#[cfg(test)]
-mod tests {
- use super::*;
-
- #[test]
- fn default_update_policy_update_accumulates() {
- let policy = DefaultUpdatePolicy::<u64>::default();
- let mut summary = 0u64;
- policy.update(&mut summary, 3);
- policy.update(&mut summary, 4);
- assert_eq!(summary, 7);
- }
-
- /// A non-trivial custom policy (keeps the maximum) to exercise the traits beyond the additive
- /// default.
- #[derive(Debug, Default, Clone, Copy)]
- struct MaxPolicy;
-
- impl SummaryPolicy for MaxPolicy {
- type Summary = u64;
-
- fn create(&self) -> Self::Summary {
- 0
- }
- }
-
- impl SummaryUpdatePolicy<u64> for MaxPolicy {
- fn update(&self, summary: &mut Self::Summary, value: u64) {
- *summary = (*summary).max(value);
- }
- }
-
- impl SummaryCombinePolicy for MaxPolicy {
- fn combine(&self, summary: &mut Self::Summary, other: &Self::Summary) {
- self.update(summary, *other);
- }
- }
-
- #[test]
- fn custom_update_policy_keeps_max() {
- let policy = MaxPolicy;
- let mut summary = policy.create();
- policy.update(&mut summary, 3);
- policy.update(&mut summary, 7);
- policy.update(&mut summary, 2);
- assert_eq!(summary, 7);
- }
-
- #[test]
- fn custom_combine_policy_keeps_max() {
- let policy = MaxPolicy;
- let mut summary = 5u64;
- policy.combine(&mut summary, &10);
- policy.combine(&mut summary, &7);
- assert_eq!(summary, 10);
- }
-
- #[test]
- fn default_union_policy_combines_additively() {
- let policy = DefaultUnionPolicy::<u64>::default();
- let mut summary = 5u64;
- policy.combine(&mut summary, &10);
- policy.combine(&mut summary, &7);
- assert_eq!(summary, 22);
- }
-}
diff --git a/datasketches/src/tuple/serialization.rs b/datasketches/src/tuple/serialization.rs
index 09763ca..5798883 100644
--- a/datasketches/src/tuple/serialization.rs
+++ b/datasketches/src/tuple/serialization.rs
@@ -89,38 +89,3 @@ impl_primitive_summary!(i32, read_i32_le, write_i32_le);
impl_primitive_summary!(i64, read_i64_le, write_i64_le);
impl_primitive_summary!(f32, read_f32_le, write_f32_le);
impl_primitive_summary!(f64, read_f64_le, write_f64_le);
-
-#[cfg(test)]
-mod tests {
- use super::*;
- use crate::error::ErrorKind;
-
- #[test]
- fn primitive_values_round_trip() {
- let mut bytes = SketchBytes::with_capacity(8);
- 123456789u64.serialize_value(&mut bytes);
- let bytes = bytes.into_bytes();
- assert_eq!(bytes.len(), 8);
- let mut cursor = SketchSlice::new(&bytes);
- assert_eq!(u64::deserialize_value(&mut cursor).unwrap(), 123456789);
- }
-
- #[test]
- fn primitive_values_consume_only_their_width() {
- let mut bytes = SketchBytes::with_capacity(6);
- 9u32.serialize_value(&mut bytes);
- bytes.write(&[0xAA, 0xBB]); // trailing bytes belonging to the next entry
- let bytes = bytes.into_bytes();
- let mut cursor = SketchSlice::new(&bytes);
- assert_eq!(u32::deserialize_value(&mut cursor).unwrap(), 9);
- assert_eq!(cursor.remaining(), &[0xAA, 0xBB]);
- }
-
- #[test]
- fn primitive_values_reject_short_input() {
- let bytes = [0u8; 3];
- let mut cursor = SketchSlice::new(&bytes);
- let err = u64::deserialize_value(&mut cursor).unwrap_err();
- assert_eq!(err.kind(), ErrorKind::InvalidData);
- }
-}
diff --git a/datasketches/src/tuple/sketch.rs b/datasketches/src/tuple/sketch.rs
index bb0832d..c6e5b04 100644
--- a/datasketches/src/tuple/sketch.rs
+++ b/datasketches/src/tuple/sketch.rs
@@ -715,7 +715,6 @@ mod tests {
use super::*;
use crate::tuple::policy::DefaultUpdatePolicy;
use crate::tuple::policy::SummaryPolicy;
- use crate::tuple::policy::SummaryUpdatePolicy;
fn sorted_updatable_entries<P>(sketch: &TupleSketch<P>) -> Vec<(u64, u64)>
where
@@ -782,247 +781,4 @@ mod tests {
assert_updatable_and_compact_equivalent(&sketch, &compact);
}
}
-
- #[test]
- fn summaries_accumulate_with_default_policy() {
- let policy = DefaultUpdatePolicy::<u64>::default();
- let mut sketch = TupleSketchBuilder::new(policy).build();
- for _ in 0..5 {
- sketch.update("same_key", 2u64);
- }
- assert_eq!(sketch.num_retained(), 1);
- let entries = sorted_updatable_entries(&sketch);
- assert_eq!(entries.len(), 1);
- assert_eq!(entries[0].1, 10); // 5 updates of 2
-
- // Summaries survive the compaction.
- let compact = sketch.compact(true);
- assert_eq!(sorted_compact_entries(&compact)[0].1, 10);
- }
-
- #[test]
- fn default_policy_accepts_any_add_assign_rhs() {
- let policy = DefaultUpdatePolicy::<String>::default();
- let mut sketch = TupleSketchBuilder::new(policy).build();
- sketch.update("k", "hello");
- sketch.update("k", " world");
-
- assert_eq!(sketch.iter().next().unwrap().1, "hello world");
- }
-
- #[test]
- fn empty_sketch_is_ordered_and_zero_estimate() {
- let policy = DefaultUpdatePolicy::<u64>::default();
- let sketch = TupleSketchBuilder::new(policy).build();
- assert!(sketch.is_empty());
- assert_eq!(sketch.estimate(), 0.0);
-
- let compact = sketch.compact(false);
- assert!(compact.is_empty());
- assert!(compact.is_ordered());
- assert_eq!(compact.estimate(), 0.0);
- assert_eq!(compact.theta64(), MAX_THETA);
- }
-
- #[test]
- fn bounds_bracket_estimate_in_estimation_mode() {
- let policy = DefaultUpdatePolicy::<u64>::default();
- let mut sketch = TupleSketchBuilder::new(policy).lg_k(12).build();
- for i in 0..10000 {
- sketch.update(i, 1u64);
- }
- let estimate = sketch.estimate();
- let lower = sketch.lower_bound(NumStdDev::Two);
- let upper = sketch.upper_bound(NumStdDev::Two);
- assert!(lower <= estimate);
- assert!(estimate <= upper);
- }
-
- #[derive(Default)]
- struct MaxPolicy;
-
- impl SummaryPolicy for MaxPolicy {
- type Summary = u64;
-
- fn create(&self) -> Self::Summary {
- 0
- }
- }
-
- impl SummaryUpdatePolicy<u64> for MaxPolicy {
- fn update(&self, summary: &mut Self::Summary, value: u64) {
- *summary = (*summary).max(value);
- }
- }
-
- #[test]
- fn custom_policy_drives_summary_behavior() {
- let mut sketch = TupleSketchBuilder::new(MaxPolicy).build();
- sketch.update("k", 3u64);
- sketch.update("k", 7u64);
- sketch.update("k", 2u64);
-
- assert_eq!(sketch.num_retained(), 1);
- let entries = sorted_updatable_entries(&sketch);
- assert_eq!(entries[0].1, 7);
- }
-
- struct ArraySumPolicy {
- num_values: usize,
- }
-
- impl SummaryPolicy for ArraySumPolicy {
- type Summary = Vec<f64>;
-
- fn create(&self) -> Self::Summary {
- vec![0.0; self.num_values]
- }
- }
-
- impl<U> SummaryUpdatePolicy<U> for ArraySumPolicy
- where
- U: AsRef<[f64]>,
- {
- fn update(&self, summary: &mut Self::Summary, value: U) {
- let value = value.as_ref();
- assert_eq!(value.len(), self.num_values);
- for (summary, value) in summary.iter_mut().zip(value) {
- *summary += value;
- }
- }
- }
-
- #[test]
- fn custom_policy_accepts_multiple_update_representations() {
- let mut sketch = TupleSketchBuilder::new(ArraySumPolicy { num_values: 2 }).build();
- sketch.update("k", &[1.0, 2.0]);
- sketch.update("k", vec![3.0, 4.0]);
-
- assert_eq!(sketch.iter().next().unwrap().1, &vec![4.0, 6.0]);
- }
-
- fn view_num_retained<V: TupleSketchView<u64>>(view: &V) -> usize {
- view.num_retained()
- }
-
- fn view_summary_sum<V: TupleSketchView<u64>>(view: &V) -> u64 {
- view.iter().map(|entry| *entry.summary()).sum()
- }
-
- fn view_is_ordered<V: TupleSketchView<u64>>(view: &V) -> bool {
- view.is_ordered()
- }
-
- #[test]
- fn view_trait_accepts_both_sketch_types() {
- let policy = DefaultUpdatePolicy::<u64>::default();
- let mut sketch = TupleSketchBuilder::new(policy).build();
- for i in 0..100 {
- sketch.update(i, 2u64);
- }
- let compact = sketch.compact(true);
-
- // Both sketch types are accepted through the shared view trait.
- assert_eq!(view_num_retained(&sketch), 100);
- assert_eq!(view_num_retained(&compact), 100);
- assert_eq!(view_summary_sum(&sketch), view_summary_sum(&compact));
- assert_eq!(view_summary_sum(&compact), 200); // 100 keys * 2
-
- // Updatable is unordered by default; compact(true) reports ordered.
- assert!(!view_is_ordered(&sketch));
- assert!(view_is_ordered(&compact));
- }
-
- fn assert_compact_round_trip(original: &CompactTupleSketch<u64>) {
- let bytes = original.serialize();
- let restored = CompactTupleSketch::<u64>::deserialize(&bytes).unwrap();
- assert_eq!(original.is_empty(), restored.is_empty());
- assert_eq!(original.is_ordered(), restored.is_ordered());
- assert_eq!(original.theta64(), restored.theta64());
- assert_eq!(original.seed_hash(), restored.seed_hash());
- assert_eq!(original.num_retained(), restored.num_retained());
- assert_eq!(
- sorted_compact_entries(original),
- sorted_compact_entries(&restored)
- );
- }
-
- #[test]
- fn serialize_round_trip_exact_mode() {
- let policy = DefaultUpdatePolicy::<u64>::default();
- let mut sketch = TupleSketchBuilder::new(policy).lg_k(12).build();
- for i in 0..2000 {
- sketch.update(i, 1u64);
- }
- assert!(!sketch.is_estimation_mode());
- assert_compact_round_trip(&sketch.compact(true));
- assert_compact_round_trip(&sketch.compact(false));
- }
-
- #[test]
- fn serialize_round_trip_estimation_mode() {
- let policy = DefaultUpdatePolicy::<u64>::default();
- let mut sketch = TupleSketchBuilder::new(policy).lg_k(5).build();
- for i in 0..5000 {
- sketch.update(i, 3u64);
- }
- let compact = sketch.compact(true);
- assert!(compact.is_estimation_mode());
- assert_compact_round_trip(&compact);
- assert_compact_round_trip(&sketch.compact(false));
- }
-
- #[test]
- fn serialize_round_trip_empty() {
- let policy = DefaultUpdatePolicy::<u64>::default();
- let sketch = TupleSketchBuilder::new(policy).build();
- let compact = sketch.compact(true);
- assert!(compact.is_empty());
- assert_compact_round_trip(&compact);
- }
-
- #[test]
- fn serialize_round_trip_single_entry() {
- let policy = DefaultUpdatePolicy::<u64>::default();
- let mut sketch = TupleSketchBuilder::new(policy).build();
- sketch.update("only", 42u64);
- let compact = sketch.compact(true);
- assert_eq!(compact.num_retained(), 1);
-
- let bytes = compact.serialize();
- // A single-entry exact sketch uses a 1-long preamble.
- assert_eq!(bytes[0], 1);
-
- let restored = CompactTupleSketch::<u64>::deserialize(&bytes).unwrap();
- assert_eq!(restored.num_retained(), 1);
- assert_eq!(restored.iter().next().unwrap().1, &42);
- }
-
- #[test]
- fn serialize_header_fields_match_tuple_format() {
- let policy = DefaultUpdatePolicy::<u64>::default();
- let mut sketch = TupleSketchBuilder::new(policy).build();
- for i in 0..100 {
- sketch.update(i, 1u64);
- }
- let bytes = sketch.compact(true).serialize();
- assert_eq!(bytes[0], 2); // preamble longs (exact, multi-entry)
- assert_eq!(bytes[1], 3); // serial version
- assert_eq!(bytes[2], 9); // TUPLE family id
- assert_eq!(bytes[3], 1); // sketch type
- }
-
- #[test]
- fn serialize_preserves_summaries() {
- let policy = DefaultUpdatePolicy::<u64>::default();
- let mut sketch = TupleSketchBuilder::new(policy).build();
- for i in 0..50 {
- sketch.update(i, 1u64);
- sketch.update(i, 1u64); // each summary accumulates to 2
- }
- let bytes = sketch.compact(true).serialize();
- let restored = CompactTupleSketch::<u64>::deserialize(&bytes).unwrap();
- assert_eq!(restored.num_retained(), 50);
- assert!(restored.iter().all(|(_, &s)| s == 2));
- }
}
diff --git a/datasketches/src/tuple/union.rs b/datasketches/src/tuple/union.rs
index ea3a8b2..4fdf5e4 100644
--- a/datasketches/src/tuple/union.rs
+++ b/datasketches/src/tuple/union.rs
@@ -208,227 +208,3 @@ where
}
}
}
-
-#[cfg(test)]
-mod tests {
- use super::*;
- use crate::common::NumStdDev;
- use crate::error::ErrorKind;
- use crate::tuple::DefaultUnionPolicy;
- use crate::tuple::DefaultUpdatePolicy;
- use crate::tuple::SummaryPolicy;
- use crate::tuple::TupleSketchBuilder;
-
- fn default_union_builder() -> TupleUnionBuilder<DefaultUnionPolicy<u64>> {
- TupleUnionBuilder::new(DefaultUnionPolicy::<u64>::default())
- }
-
- fn default_sketch_builder() -> TupleSketchBuilder<DefaultUpdatePolicy<u64>> {
- TupleSketchBuilder::new(DefaultUpdatePolicy::<u64>::default())
- }
-
- fn sorted_entries(sketch: &CompactTupleSketch<u64>) -> Vec<(u64, u64)> {
- let mut entries: Vec<(u64, u64)> = sketch.iter().map(|(h, &s)| (h, s)).collect();
- entries.sort_unstable();
- entries
- }
-
- #[test]
- fn union_of_disjoint_sketches_sums_cardinality() {
- let mut a = default_sketch_builder().build();
- for i in 0..1000 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().build();
- for i in 1000..2000 {
- b.update(i, 1u64);
- }
-
- let mut union = default_union_builder().build();
- union.update(&a).unwrap();
- union.update(&b).unwrap();
-
- let result = union.to_sketch(true);
- // 2000 distinct keys < k (4096), so the union is in exact mode.
- assert!(!result.is_estimation_mode());
- assert_eq!(result.num_retained(), 2000);
- assert_eq!(result.estimate(), 2000.0);
- // Every summary stays at 1 because the inputs are disjoint.
- assert!(result.iter().all(|(_, &s)| s == 1));
- }
-
- #[test]
- fn union_combines_overlapping_summaries() {
- let mut a = default_sketch_builder().build();
- a.update("shared", 3u64);
- a.update("only_a", 1u64);
- let mut b = default_sketch_builder().build();
- b.update("shared", 4u64);
- b.update("only_b", 1u64);
-
- let mut union = default_union_builder().build();
- union.update(&a).unwrap();
- union.update(&b).unwrap();
-
- let result = union.to_sketch(true);
- assert_eq!(result.num_retained(), 3);
-
- // The shared key's summary is the default-policy sum (3 + 4 = 7); the rest are 1.
- let summaries: Vec<u64> = sorted_entries(&result)
- .into_iter()
- .map(|(_, s)| s)
- .collect();
- let mut sorted = summaries.clone();
- sorted.sort_unstable();
- assert_eq!(sorted, vec![1, 1, 7]);
- }
-
- #[test]
- fn union_result_is_order_independent() {
- let mut a = default_sketch_builder().build();
- a.update("shared", 3u64);
- a.update("only_a", 5u64);
- let mut b = default_sketch_builder().build();
- b.update("shared", 4u64);
- b.update("only_b", 6u64);
-
- let mut a_then_b = default_union_builder().build();
- a_then_b.update(&a).unwrap();
- a_then_b.update(&b).unwrap();
-
- let mut b_then_a = default_union_builder().build();
- b_then_a.update(&b).unwrap();
- b_then_a.update(&a).unwrap();
-
- assert_eq!(
- sorted_entries(&a_then_b.to_sketch(true)),
- sorted_entries(&b_then_a.to_sketch(true))
- );
- }
-
- #[test]
- fn union_accepts_updatable_and_compact_inputs() {
- let mut a = default_sketch_builder().build();
- for i in 0..500 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().build();
- for i in 250..750 {
- b.update(i, 1u64);
- }
- let b_compact = b.compact(true);
-
- let mut union = default_union_builder().build();
- union.update(&a).unwrap(); // updatable input
- union.update(&b_compact).unwrap(); // compact input
-
- let result = union.to_sketch(true);
- assert_eq!(result.num_retained(), 750); // 0..750 distinct
- }
-
- #[test]
- fn union_of_empty_inputs_is_empty() {
- let empty = default_sketch_builder().build();
-
- let mut union = default_union_builder().build();
- union.update(&empty).unwrap();
-
- let result = union.to_sketch(true);
- assert!(result.is_empty());
- assert!(result.is_ordered());
- assert_eq!(result.estimate(), 0.0);
- assert_eq!(result.num_retained(), 0);
- }
-
- #[test]
- fn union_never_updated_is_empty() {
- let union = default_union_builder().build();
- let result = union.to_sketch(true);
- assert!(result.is_empty());
- assert_eq!(result.estimate(), 0.0);
- }
-
- #[test]
- fn union_rejects_seed_mismatch() {
- let mut a = default_sketch_builder().seed(1).build();
- a.update("k", 1u64);
-
- let mut union = default_union_builder().seed(2).build();
- let err = union.update(&a).unwrap_err();
- assert_eq!(err.kind(), ErrorKind::InvalidArgument);
- }
-
- #[test]
- fn union_in_estimation_mode_estimates_within_bounds() {
- let mut a = default_sketch_builder().lg_k(8).build();
- for i in 0..50000 {
- a.update(i, 1u64);
- }
- let mut b = default_sketch_builder().lg_k(8).build();
- for i in 25000..75000 {
- b.update(i, 1u64);
- }
-
- let mut union = default_union_builder().lg_k(8).build();
- union.update(&a).unwrap();
- union.update(&b).unwrap();
-
- let result = union.to_sketch(true);
- assert!(result.is_estimation_mode());
- // Union of 0..75000 distinct keys.
- let lower = result.lower_bound(NumStdDev::Three);
- let upper = result.upper_bound(NumStdDev::Three);
- assert!(
- lower <= 75000.0 && 75000.0 <= upper,
- "expected 75000 in [{lower}, {upper}]"
- );
- }
-
- #[derive(Debug, Default, Clone, Copy)]
- struct MaxUnionPolicy;
-
- impl SummaryPolicy for MaxUnionPolicy {
- type Summary = u64;
-
- fn create(&self) -> Self::Summary {
- 0
- }
- }
-
- impl SummaryCombinePolicy for MaxUnionPolicy {
- fn combine(&self, summary: &mut Self::Summary, other: &Self::Summary) {
- *summary = (*summary).max(*other);
- }
- }
-
- #[test]
- fn union_uses_custom_combine_policy() {
- let mut a = default_sketch_builder().build();
- a.update("shared", 3u64);
- let mut b = default_sketch_builder().build();
- b.update("shared", 9u64);
-
- let mut union = TupleUnionBuilder::new(MaxUnionPolicy).build();
- union.update(&a).unwrap();
- union.update(&b).unwrap();
-
- let result = union.to_sketch(true);
- assert_eq!(result.num_retained(), 1);
- assert_eq!(result.iter().next().unwrap().1, &9); // max(3, 9)
- }
-
- #[test]
- fn union_reset_clears_state() {
- let mut a = default_sketch_builder().build();
- for i in 0..100 {
- a.update(i, 1u64);
- }
-
- let mut union = default_union_builder().build();
- union.update(&a).unwrap();
- assert!(!union.to_sketch(true).is_empty());
-
- union.reset();
- assert!(union.to_sketch(true).is_empty());
- }
-}
diff --git a/datasketches/tests/serde_tests/tuple.rs b/datasketches/tests/serde_tests/tuple.rs
index e076617..45b5529 100644
--- a/datasketches/tests/serde_tests/tuple.rs
+++ b/datasketches/tests/serde_tests/tuple.rs
@@ -95,6 +95,21 @@ fn test_cpp_compatibility() {
}
}
+#[test]
+fn round_trip_preserves_summaries() {
+ let mut sketch = TupleSketchBuilder::new(DefaultUpdatePolicy::<u64>::default()).build();
+ for value in 0..50 {
+ sketch.update(value, 1);
+ sketch.update(value, 2);
+ }
+
+ let restored =
+ CompactTupleSketch::<u64>::deserialize(&sketch.compact(true).serialize()).unwrap();
+
+ assert_eq!(restored.num_retained(), 50);
+ assert!(restored.iter().all(|(_, &summary)| summary == 3));
+}
+
#[test]
fn malformed_input_is_rejected() {
let mut sketch = TupleSketchBuilder::new(DefaultUpdatePolicy::<u64>::default())
diff --git a/datasketches/tests/tuple_test/a_not_b.rs b/datasketches/tests/tuple_test/a_not_b.rs
index ac1d3a8..6dffad3 100644
--- a/datasketches/tests/tuple_test/a_not_b.rs
+++ b/datasketches/tests/tuple_test/a_not_b.rs
@@ -15,20 +15,25 @@
// specific language governing permissions and limitations
// under the License.
-//! Behavioral tests for the Tuple a-not-B (set difference) operator.
-//!
-//! The result of `a and not b` retains the keys of `a` that are absent from `b`, keeping the
-//! summaries from `a`. These tests use a `u64` summary with the default additive update policy,
-//! so the distinct-count behavior matches a plain Theta a-not-B.
-
+use datasketches::common::NumStdDev;
+use datasketches::error::ErrorKind;
use datasketches::tuple::CompactTupleSketch;
use datasketches::tuple::TupleANotB;
use super::default_tuple_sketch_builder;
use super::tuple_sketch_with_range;
+fn sorted_entries(sketch: &CompactTupleSketch<u64>) -> Vec<(u64, u64)> {
+ let mut entries: Vec<_> = sketch
+ .iter()
+ .map(|(hash, &summary)| (hash, summary))
+ .collect();
+ entries.sort_unstable();
+ entries
+}
+
#[test]
-fn test_basic_difference_keeps_summaries_from_a() {
+fn difference_keeps_only_a_summaries() {
let mut a = default_tuple_sketch_builder().build();
a.update("shared", 3u64);
a.update("only_a", 5u64);
@@ -36,207 +41,129 @@ fn test_basic_difference_keeps_summaries_from_a() {
b.update("shared", 9u64);
b.update("only_b", 7u64);
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&a, &b, true).unwrap();
+ let result = TupleANotB::default().compute(&a, &b, true).unwrap();
- // "shared" is subtracted; "only_a" survives with A's summary.
- assert_eq!(r.num_retained(), 1);
- assert_eq!(r.iter().next().unwrap().1, &5);
- assert!(!r.is_estimation_mode());
- assert_eq!(r.estimate(), 1.0);
+ assert_eq!(result.num_retained(), 1);
+ assert_eq!(result.estimate(), 1.0);
+ assert_eq!(result.iter().next().unwrap().1, &5);
}
#[test]
-fn test_accepts_updatable_and_compact_inputs() {
+fn accepts_mutable_and_compact_inputs() {
let a = tuple_sketch_with_range(0, 1000);
let b = tuple_sketch_with_range(500, 1000);
+ let op = TupleANotB::default();
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&a.compact(true), &b, true).unwrap();
- assert_eq!(r.num_retained(), 500);
-
- let r = a_not_b.compute(&a, &b.compact(false), true).unwrap();
- assert_eq!(r.num_retained(), 500);
-}
-
-#[test]
-fn test_seed_mismatch_returns_error() {
- let mut one_other_seed = default_tuple_sketch_builder().seed(2).build();
- one_other_seed.update("value", 1u64);
- let good = tuple_sketch_with_range(0, 10);
-
- let a_not_b = TupleANotB::with_seed(1);
- assert!(a_not_b.compute(&one_other_seed, &good, true).is_err());
- assert!(a_not_b.compute(&good, &one_other_seed, true).is_err());
-}
-
-#[test]
-fn test_seed_mismatch_ignored_for_empty_inputs() {
- // Empty inputs carry no keys, so their seeds are not validated.
- let empty_other_seed = default_tuple_sketch_builder().seed(2).build();
- let good = tuple_sketch_with_range(0, 10);
-
- let a_not_b = TupleANotB::default();
-
- let r = a_not_b.compute(&empty_other_seed, &good, true).unwrap();
- assert!(r.is_empty());
-
- let r = a_not_b.compute(&good, &empty_other_seed, true).unwrap();
- assert_eq!(r.num_retained(), 10);
-}
-
-#[test]
-fn test_empty_a_returns_empty() {
- let empty = default_tuple_sketch_builder().build();
- let b = tuple_sketch_with_range(0, 1000);
-
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&empty, &b, true).unwrap();
-
- assert!(r.is_empty());
- assert_eq!(r.num_retained(), 0);
- assert_eq!(r.estimate(), 0.0);
-}
-
-#[test]
-fn test_empty_b_returns_a() {
- let a = tuple_sketch_with_range(0, 1000);
- let empty = default_tuple_sketch_builder().build();
-
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&a, &empty, true).unwrap();
-
- assert_eq!(r.num_retained(), 1000);
- assert_eq!(r.estimate(), 1000.0);
-}
-
-#[test]
-fn test_exact_partial_overlap_unordered() {
- let a = tuple_sketch_with_range(0, 1000);
- let b = tuple_sketch_with_range(500, 1000);
-
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&a, &b, true).unwrap();
+ let mutable_result = op.compute(&a, &b, true).unwrap();
+ let compact_result = op
+ .compute(&a.compact(true), &b.compact(false), true)
+ .unwrap();
- // Keys 0..500 survive (exact mode).
- assert!(!r.is_empty());
- assert!(!r.is_estimation_mode());
- assert_eq!(r.num_retained(), 500);
- assert_eq!(r.estimate(), 500.0);
+ assert_eq!(
+ sorted_entries(&mutable_result),
+ sorted_entries(&compact_result)
+ );
+ assert_eq!(mutable_result.num_retained(), 500);
}
#[test]
-fn test_exact_partial_overlap_ordered() {
- let a = tuple_sketch_with_range(0, 1000);
- let b = tuple_sketch_with_range(500, 1000);
+fn ordered_and_unordered_inputs_produce_the_same_result() {
+ let mut a = default_tuple_sketch_builder().lg_k(8).build();
+ let mut b = default_tuple_sketch_builder().lg_k(8).build();
+ for value in 0..20_000 {
+ a.update(value, 1u64);
+ }
+ for value in 10_000..30_000 {
+ b.update(value, 1u64);
+ }
- let a_not_b = TupleANotB::default();
- let r = a_not_b
+ let op = TupleANotB::default();
+ let unordered = op.compute(&a, &b, true).unwrap();
+ let ordered = op
.compute(&a.compact(true), &b.compact(true), true)
.unwrap();
- assert!(!r.is_empty());
- assert!(!r.is_estimation_mode());
- assert_eq!(r.num_retained(), 500);
- assert_eq!(r.estimate(), 500.0);
+ assert_eq!(unordered.theta64(), ordered.theta64());
+ assert_eq!(sorted_entries(&unordered), sorted_entries(&ordered));
}
#[test]
-fn test_exact_disjoint_returns_a() {
- let a = tuple_sketch_with_range(0, 1000);
- let b = tuple_sketch_with_range(1000, 1000);
-
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&a, &b, true).unwrap();
-
- assert!(!r.is_estimation_mode());
- assert_eq!(r.num_retained(), 1000);
- assert_eq!(r.estimate(), 1000.0);
-}
-
-#[test]
-fn test_exact_superset_b_returns_empty() {
- let a = tuple_sketch_with_range(0, 1000);
- let b = tuple_sketch_with_range(0, 2000);
-
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&a, &b, true).unwrap();
-
- assert!(r.is_empty());
- assert_eq!(r.num_retained(), 0);
- assert_eq!(r.estimate(), 0.0);
+fn empty_inputs_do_not_impose_a_seed() {
+ let empty_other_seed = default_tuple_sketch_builder().seed(2).build();
+ let non_empty = tuple_sketch_with_range(0, 10);
+ let op = TupleANotB::default();
+
+ assert!(
+ op.compute(&empty_other_seed, &non_empty, true)
+ .unwrap()
+ .is_empty()
+ );
+ assert_eq!(
+ op.compute(&non_empty, &empty_other_seed, true)
+ .unwrap()
+ .num_retained(),
+ 10
+ );
}
#[test]
-fn test_result_ordering() {
- let mut a = default_tuple_sketch_builder().build();
- for i in 0..64 {
- a.update(i, 1u64);
- }
+fn non_empty_inputs_require_the_operator_seed() {
+ let mut other_seed = default_tuple_sketch_builder().seed(2).build();
+ other_seed.update("value", 1u64);
let empty = default_tuple_sketch_builder().build();
+ let good = tuple_sketch_with_range(0, 10);
+ let op = TupleANotB::default();
- let a_not_b = TupleANotB::default();
-
- let r = a_not_b.compute(&a, &empty, true).unwrap();
- assert!(r.is_ordered());
-
- let r = a_not_b.compute(&a, &empty, false).unwrap();
- assert!(!r.is_ordered());
-}
-
-#[test]
-fn test_estimation_partial_overlap_unordered() {
- let a = tuple_sketch_with_range(0, 10000);
- let b = tuple_sketch_with_range(5000, 10000);
-
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&a, &b, true).unwrap();
-
- // True difference size is 5000 (keys 0..5000).
- assert!(!r.is_empty());
- assert!(r.is_estimation_mode());
- assert!((r.estimate() - 5000.0).abs() <= 5000.0 * 0.02);
-}
-
-#[test]
-fn test_estimation_partial_overlap_ordered() {
- let a = tuple_sketch_with_range(0, 10000);
- let b = tuple_sketch_with_range(5000, 10000);
-
- let a_not_b = TupleANotB::default();
- let r = a_not_b
- .compute(&a.compact(true), &b.compact(true), true)
- .unwrap();
+ let err = op.compute(&other_seed, &empty, true).unwrap_err();
+ assert_eq!(err.kind(), ErrorKind::InvalidArgument);
- assert!(!r.is_empty());
- assert!(r.is_estimation_mode());
- assert!((r.estimate() - 5000.0).abs() <= 5000.0 * 0.02);
+ let err = op.compute(&good, &other_seed, true).unwrap_err();
+ assert_eq!(err.kind(), ErrorKind::InvalidArgument);
}
#[test]
-fn test_estimation_partial_overlap_deserialized_compact() {
- let a = tuple_sketch_with_range(0, 10000);
- let b = tuple_sketch_with_range(5000, 10000);
- let c1 = CompactTupleSketch::<u64>::deserialize(&a.compact(true).serialize()).unwrap();
- let c2 = CompactTupleSketch::<u64>::deserialize(&b.compact(true).serialize()).unwrap();
-
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&c1, &c2, true).unwrap();
-
- assert!(!r.is_empty());
- assert!(r.is_estimation_mode());
- assert!((r.estimate() - 5000.0).abs() <= 5000.0 * 0.02);
+fn empty_b_preserves_logically_non_empty_a_without_retained_entries() {
+ let screened_value = (0u64..)
+ .find(|candidate| {
+ let mut sketch = default_tuple_sketch_builder()
+ .sampling_probability(0.001)
+ .build();
+ sketch.update(*candidate, 1u64);
+ !sketch.is_empty() && sketch.num_retained() == 0
+ })
+ .expect("failed to find a value screened out by the sampling theta");
+
+ let mut a = default_tuple_sketch_builder()
+ .sampling_probability(0.001)
+ .build();
+ a.update(screened_value, 1u64);
+ let empty_b = default_tuple_sketch_builder().seed(999).build();
+
+ let result = TupleANotB::default().compute(&a, &empty_b, true).unwrap();
+
+ assert!(!result.is_empty());
+ assert_eq!(result.num_retained(), 0);
+ assert_eq!(result.theta64(), a.theta64());
}
#[test]
-fn test_estimation_disjoint_returns_a() {
- let a = tuple_sketch_with_range(0, 10000);
- let b = tuple_sketch_with_range(10000, 10000);
+fn estimation_bounds_cover_the_true_difference() {
+ let mut a = default_tuple_sketch_builder().lg_k(8).build();
+ let mut b = default_tuple_sketch_builder().lg_k(8).build();
+ for value in 0..50_000 {
+ a.update(value, 1u64);
+ }
+ for value in 25_000..75_000 {
+ b.update(value, 1u64);
+ }
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&a, &b, true).unwrap();
+ let result = TupleANotB::default().compute(&a, &b, true).unwrap();
+ let lower = result.lower_bound(NumStdDev::Three);
+ let upper = result.upper_bound(NumStdDev::Three);
- assert!(!r.is_empty());
- assert!(r.is_estimation_mode());
- assert!((r.estimate() - 10000.0).abs() <= 10000.0 * 0.02);
+ assert!(result.is_estimation_mode());
+ assert!(
+ lower <= 25_000.0 && 25_000.0 <= upper,
+ "expected 25000 in [{lower}, {upper}]"
+ );
}
diff --git a/datasketches/tests/tuple_test/intersection.rs b/datasketches/tests/tuple_test/intersection.rs
index 40000df..e339055 100644
--- a/datasketches/tests/tuple_test/intersection.rs
+++ b/datasketches/tests/tuple_test/intersection.rs
@@ -15,7 +15,8 @@
// specific language governing permissions and limitations
// under the License.
-use datasketches::tuple::CompactTupleSketch;
+use datasketches::common::NumStdDev;
+use datasketches::error::ErrorKind;
use datasketches::tuple::SummaryCombinePolicy;
use datasketches::tuple::SummaryPolicy;
use datasketches::tuple::TupleIntersection;
@@ -41,291 +42,140 @@ impl SummaryCombinePolicy for SumPolicy {
}
#[test]
-fn test_has_result_state_machine() {
- let mut a = default_tuple_sketch_builder().build();
- a.update("x", 1u64);
+fn has_result_tracks_the_first_update() {
+ let sketch = tuple_sketch_with_range(0, 10);
+ let mut intersection = TupleIntersection::new(SumPolicy);
- let mut i = TupleIntersection::new(SumPolicy);
- assert!(!i.has_result());
- i.update(&a).unwrap();
- assert!(i.has_result());
- assert!(i.to_sketch(true).estimate() >= 1.0);
+ assert!(!intersection.has_result());
+ intersection.update(&sketch).unwrap();
+ assert!(intersection.has_result());
+ assert_eq!(intersection.to_sketch(true).num_retained(), 10);
}
#[test]
-fn test_result_before_update_panics() {
- let i = TupleIntersection::with_seed(SumPolicy, 123);
- let result = std::panic::catch_unwind(|| {
- let _ = i.to_sketch(true);
- });
- assert!(result.is_err());
+#[should_panic(expected = "before first update")]
+fn result_before_first_update_panics() {
+ let intersection = TupleIntersection::new(SumPolicy);
+ let _ = intersection.to_sketch(true);
}
#[test]
-fn test_update_accepts_compact_sketch() {
+fn overlap_combines_summaries() {
let mut a = default_tuple_sketch_builder().build();
- a.update("x", 1u64);
- a.update("y", 1u64);
-
+ a.update("shared", 3u64);
+ a.update("only_a", 100u64);
let mut b = default_tuple_sketch_builder().build();
- b.update("y", 1u64);
- b.update("z", 1u64);
-
- let mut i = TupleIntersection::new(SumPolicy);
- i.update(&a.compact(true)).unwrap();
- i.update(&b).unwrap();
-
- let r = i.to_sketch(true);
- assert!(r.estimate() == 1.0);
- assert!(r.is_ordered());
+ b.update("shared", 4u64);
+ b.update("only_b", 200u64);
- let mut c = default_tuple_sketch_builder().build();
- c.update("a", 1u64);
- c.update("b", 1u64);
- c.update("c", 1u64);
+ let mut intersection = TupleIntersection::new(SumPolicy);
+ intersection.update(&a).unwrap();
+ intersection.update(&b).unwrap();
+ let result = intersection.to_sketch(true);
- i.update(&c.compact(false)).unwrap();
-
- let r = i.to_sketch(false);
- assert!(r.estimate() == 0.0);
- assert!(!r.is_ordered());
+ assert_eq!(result.num_retained(), 1);
+ assert_eq!(result.iter().next().unwrap().1, &7);
}
#[test]
-fn test_seed_mismatch_behaviour_for_empty_sketch() {
- let empty_other_seed = default_tuple_sketch_builder().seed(2).build();
- let mut i = TupleIntersection::with_seed(SumPolicy, 1);
+fn accepts_mutable_and_compact_inputs() {
+ let a = tuple_sketch_with_range(0, 1000);
+ let b = tuple_sketch_with_range(500, 1000);
- i.update(&empty_other_seed).unwrap();
- assert!(i.has_result());
- let r = i.to_sketch(true);
- assert!(r.is_empty());
-}
+ let mut intersection = TupleIntersection::new(SumPolicy);
+ intersection.update(&a).unwrap();
+ intersection.update(&b.compact(true)).unwrap();
-#[test]
-fn test_seed_mismatch_behaviour() {
- let mut one_other_seed = default_tuple_sketch_builder().seed(2).build();
- one_other_seed.update("value", 1u64);
- let mut i = TupleIntersection::with_seed(SumPolicy, 1);
-
- assert!(i.update(&one_other_seed).is_err());
+ assert_eq!(intersection.to_sketch(true).num_retained(), 500);
}
#[test]
-fn test_terminal_empty_state_ignores_future_updates() {
- let empty = default_tuple_sketch_builder().build();
-
- let mut non_empty = default_tuple_sketch_builder().build();
- non_empty.update("x", 1u64);
+fn disjoint_result_is_terminally_empty() {
+ let a = tuple_sketch_with_range(0, 100);
+ let b = tuple_sketch_with_range(100, 100);
+ let later = tuple_sketch_with_range(0, 100);
- let mut i = TupleIntersection::new(SumPolicy);
- i.update(&empty).unwrap();
- i.update(&non_empty).unwrap();
-
- let r = i.to_sketch(true);
- assert!(r.is_empty());
-}
-
-#[test]
-fn test_to_sketch_unordered_is_not_ordered() {
- let mut a = default_tuple_sketch_builder().build();
- for i in 0..64 {
- a.update(i, 1u64);
- }
- let mut i = TupleIntersection::new(SumPolicy);
- i.update(&a).unwrap();
+ let mut intersection = TupleIntersection::new(SumPolicy);
+ intersection.update(&a).unwrap();
+ intersection.update(&b).unwrap();
+ intersection.update(&later).unwrap();
- let r = i.to_sketch(false);
- assert!(!r.is_ordered());
+ let result = intersection.to_sketch(true);
+ assert!(result.is_empty());
+ assert_eq!(result.num_retained(), 0);
}
#[test]
-fn test_empty_update_twice() {
- let empty = default_tuple_sketch_builder().build();
- let mut i = TupleIntersection::new(SumPolicy);
-
- i.update(&empty).unwrap();
- let r1 = i.to_sketch(true);
- assert_eq!(r1.num_retained(), 0);
- assert!(r1.is_empty());
- assert!(!r1.is_estimation_mode());
- assert_eq!(r1.estimate(), 0.0);
-
- i.update(&empty).unwrap();
- let r2 = i.to_sketch(true);
- assert_eq!(r2.num_retained(), 0);
- assert!(r2.is_empty());
- assert!(!r2.is_estimation_mode());
- assert_eq!(r2.estimate(), 0.0);
-}
+fn logically_non_empty_input_without_retained_entries_is_preserved() {
+ let screened_value = (0u64..)
+ .find(|candidate| {
+ let mut sketch = default_tuple_sketch_builder()
+ .sampling_probability(0.001)
+ .build();
+ sketch.update(*candidate, 1u64);
+ !sketch.is_empty() && sketch.num_retained() == 0
+ })
+ .expect("failed to find a value screened out by the sampling theta");
-#[test]
-fn test_non_empty_no_retained_keys() {
- let mut s = default_tuple_sketch_builder()
+ let mut sketch = default_tuple_sketch_builder()
.sampling_probability(0.001)
.build();
- s.update(1u64, 1u64);
-
- let mut i = TupleIntersection::new(SumPolicy);
- i.update(&s).unwrap();
- let r1 = i.to_sketch(true);
- assert_eq!(r1.num_retained(), 0);
- assert!(!r1.is_empty());
- assert!(r1.is_estimation_mode());
- assert!((r1.theta() - 0.001).abs() < 1e-10);
- assert_eq!(r1.estimate(), 0.0);
-
- i.update(&s).unwrap();
- let r2 = i.to_sketch(true);
- assert_eq!(r2.num_retained(), 0);
- assert!(!r2.is_empty());
- assert!(r2.is_estimation_mode());
- assert!((r2.theta() - 0.001).abs() < 1e-10);
- assert_eq!(r2.estimate(), 0.0);
-}
-
-#[test]
-fn test_exact_half_overlap_unordered() {
- let s1 = tuple_sketch_with_range(0, 1000);
- let s2 = tuple_sketch_with_range(500, 1000);
-
- let mut i = TupleIntersection::new(SumPolicy);
- i.update(&s1).unwrap();
- i.update(&s2).unwrap();
- let r = i.to_sketch(true);
-
- assert!(!r.is_empty());
- assert!(!r.is_estimation_mode());
- assert_eq!(r.estimate(), 500.0);
-}
-
-#[test]
-fn test_exact_half_overlap_ordered() {
- let s1 = tuple_sketch_with_range(0, 1000);
- let s2 = tuple_sketch_with_range(500, 1000);
+ sketch.update(screened_value, 1u64);
- let mut i = TupleIntersection::new(SumPolicy);
- i.update(&s1.compact(true)).unwrap();
- i.update(&s2.compact(true)).unwrap();
- let r = i.to_sketch(true);
+ let mut intersection = TupleIntersection::new(SumPolicy);
+ intersection.update(&sketch).unwrap();
+ let result = intersection.to_sketch(true);
- assert!(!r.is_empty());
- assert!(!r.is_estimation_mode());
- assert_eq!(r.estimate(), 500.0);
+ assert!(!result.is_empty());
+ assert_eq!(result.num_retained(), 0);
+ assert_eq!(result.theta64(), sketch.theta64());
}
#[test]
-fn test_exact_disjoint_unordered() {
- let s1 = tuple_sketch_with_range(0, 1000);
- let s2 = tuple_sketch_with_range(1000, 1000);
-
- let mut i = TupleIntersection::new(SumPolicy);
- i.update(&s1).unwrap();
- i.update(&s2).unwrap();
- let r = i.to_sketch(true);
-
- assert!(r.is_empty());
- assert!(!r.is_estimation_mode());
- assert_eq!(r.estimate(), 0.0);
-}
-
-#[test]
-fn test_exact_disjoint_ordered() {
- let s1 = tuple_sketch_with_range(0, 1000);
- let s2 = tuple_sketch_with_range(1000, 1000);
-
- let mut i = TupleIntersection::new(SumPolicy);
- i.update(&s1.compact(true)).unwrap();
- i.update(&s2.compact(true)).unwrap();
- let r = i.to_sketch(true);
-
- assert!(r.is_empty());
- assert!(!r.is_estimation_mode());
- assert_eq!(r.estimate(), 0.0);
-}
-
-#[test]
-fn test_estimation_half_overlap_unordered() {
- let s1 = tuple_sketch_with_range(0, 10000);
- let s2 = tuple_sketch_with_range(5000, 10000);
-
- let mut i = TupleIntersection::new(SumPolicy);
- i.update(&s1).unwrap();
- i.update(&s2).unwrap();
- let r = i.to_sketch(true);
-
- assert!(!r.is_empty());
- assert!(r.is_estimation_mode());
- assert!((r.estimate() - 5000.0).abs() <= 5000.0 * 0.02);
-}
-
-#[test]
-fn test_estimation_half_overlap_ordered() {
- let s1 = tuple_sketch_with_range(0, 10000);
- let s2 = tuple_sketch_with_range(5000, 10000);
-
- let mut i = TupleIntersection::new(SumPolicy);
- i.update(&s1.compact(true)).unwrap();
- i.update(&s2.compact(true)).unwrap();
- let r = i.to_sketch(true);
-
- assert!(!r.is_empty());
- assert!(r.is_estimation_mode());
- assert!((r.estimate() - 5000.0).abs() <= 5000.0 * 0.02);
-}
-
-#[test]
-fn test_estimation_half_overlap_ordered_deserialized_compact() {
- let s1 = tuple_sketch_with_range(0, 10000);
- let s2 = tuple_sketch_with_range(5000, 10000);
- let c1 = CompactTupleSketch::<u64>::deserialize(&s1.compact(true).serialize()).unwrap();
- let c2 = CompactTupleSketch::<u64>::deserialize(&s2.compact(true).serialize()).unwrap();
-
- let mut i = TupleIntersection::new(SumPolicy);
- i.update(&c1).unwrap();
- i.update(&c2).unwrap();
- let r = i.to_sketch(true);
-
- assert!(!r.is_empty());
- assert!(r.is_estimation_mode());
- assert!((r.estimate() - 5000.0).abs() <= 5000.0 * 0.02);
-}
-
-#[test]
-fn test_estimation_disjoint_unordered() {
- let s1 = tuple_sketch_with_range(0, 10000);
- let s2 = tuple_sketch_with_range(10000, 10000);
+fn only_non_empty_inputs_require_the_operator_seed() {
+ let empty_other_seed = default_tuple_sketch_builder().seed(2).build();
+ let mut non_empty_other_seed = default_tuple_sketch_builder().seed(2).build();
+ non_empty_other_seed.update("value", 1u64);
- let mut i = TupleIntersection::new(SumPolicy);
- i.update(&s1).unwrap();
- i.update(&s2).unwrap();
- let r = i.to_sketch(true);
+ let mut intersection = TupleIntersection::with_seed(SumPolicy, 1);
+ intersection.update(&empty_other_seed).unwrap();
- assert!(!r.is_empty());
- assert!(r.is_estimation_mode());
- assert_eq!(r.estimate(), 0.0);
+ let mut intersection = TupleIntersection::with_seed(SumPolicy, 1);
+ let err = intersection.update(&non_empty_other_seed).unwrap_err();
+ assert_eq!(err.kind(), ErrorKind::InvalidArgument);
}
#[test]
-fn test_estimation_disjoint_ordered() {
- let s1 = tuple_sketch_with_range(0, 10000);
- let s2 = tuple_sketch_with_range(10000, 10000);
+fn result_ordering_follows_the_request() {
+ let input = tuple_sketch_with_range(0, 100);
+ let mut intersection = TupleIntersection::new(SumPolicy);
+ intersection.update(&input).unwrap();
- let mut i = TupleIntersection::new(SumPolicy);
- i.update(&s1.compact(true)).unwrap();
- i.update(&s2.compact(true)).unwrap();
- let r = i.to_sketch(true);
-
- assert!(!r.is_empty());
- assert!(r.is_estimation_mode());
- assert_eq!(r.estimate(), 0.0);
+ assert!(intersection.to_sketch(true).is_ordered());
+ assert!(!intersection.to_sketch(false).is_ordered());
}
#[test]
-fn test_seed_mismatch_non_empty_returns_error() {
- let mut s = default_tuple_sketch_builder().build();
- s.update(1u64, 1u64);
+fn estimation_bounds_cover_the_true_intersection() {
+ let mut a = default_tuple_sketch_builder().lg_k(8).build();
+ let mut b = default_tuple_sketch_builder().lg_k(8).build();
+ for value in 0..50_000 {
+ a.update(value, 1u64);
+ }
+ for value in 25_000..75_000 {
+ b.update(value, 1u64);
+ }
- let mut i = TupleIntersection::with_seed(SumPolicy, 123);
- assert!(i.update(&s).is_err());
+ let mut intersection = TupleIntersection::new(SumPolicy);
+ intersection.update(&a).unwrap();
+ intersection.update(&b).unwrap();
+ let result = intersection.to_sketch(true);
+ let lower = result.lower_bound(NumStdDev::Three);
+ let upper = result.upper_bound(NumStdDev::Three);
+
+ assert!(result.is_estimation_mode());
+ assert!(
+ lower <= 25_000.0 && 25_000.0 <= upper,
+ "expected 25000 in [{lower}, {upper}]"
+ );
}
diff --git a/datasketches/tests/tuple_test/main.rs b/datasketches/tests/tuple_test/main.rs
index f5747e9..887a280 100644
--- a/datasketches/tests/tuple_test/main.rs
+++ b/datasketches/tests/tuple_test/main.rs
@@ -18,6 +18,7 @@
mod a_not_b;
mod intersection;
mod sketch;
+mod union;
use datasketches::tuple::DefaultUpdatePolicy;
use datasketches::tuple::TupleSketch;
diff --git a/datasketches/tests/tuple_test/sketch.rs b/datasketches/tests/tuple_test/sketch.rs
index 148c19f..d0a49ec 100644
--- a/datasketches/tests/tuple_test/sketch.rs
+++ b/datasketches/tests/tuple_test/sketch.rs
@@ -17,284 +17,131 @@
use datasketches::common::NumStdDev;
use datasketches::hash_value;
+use datasketches::tuple::SummaryPolicy;
+use datasketches::tuple::SummaryUpdatePolicy;
+use datasketches::tuple::TupleSketchBuilder;
use super::default_tuple_sketch_builder;
#[test]
-fn test_basic_update() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
- assert!(sketch.is_empty());
- assert_eq!(sketch.estimate(), 0.0);
-
- sketch.update("value1", 1u64);
- assert!(!sketch.is_empty());
- assert_eq!(sketch.estimate(), 1.0);
+fn updates_distinct_keys_and_accumulates_summaries() {
+ let mut sketch = default_tuple_sketch_builder().build();
+ sketch.update("shared", 2u64);
+ sketch.update("shared", 3u64);
+ sketch.update("other", 7u64);
- sketch.update("value2", 1u64);
assert_eq!(sketch.estimate(), 2.0);
-}
+ assert_eq!(sketch.num_retained(), 2);
-#[test]
-fn test_summary_accumulates_per_key() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
- for _ in 0..5 {
- sketch.update("same_key", 2u64);
- }
- assert_eq!(sketch.estimate(), 1.0);
- assert_eq!(sketch.num_retained(), 1);
- // The default policy folds each update into the retained summary: 5 * 2 == 10.
- assert_eq!(sketch.iter().next().unwrap().1, &10);
+ let mut summaries: Vec<u64> = sketch.iter().map(|(_, &summary)| summary).collect();
+ summaries.sort_unstable();
+ assert_eq!(summaries, [5, 7]);
}
#[test]
-fn test_update_various_types() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
-
+fn accepts_supported_hash_representations() {
+ let mut sketch = default_tuple_sketch_builder().build();
sketch.update("string", 1u64);
sketch.update(42i64, 1u64);
sketch.update(42u64, 1u64);
- // where floating-point numbers have different representations
- sketch.update(hash_value::canonical_float::from_f64(3.15), 1u64);
- sketch.update(hash_value::canonical_float::from_f64(3.15), 1u64);
- sketch.update(hash_value::canonical_float::from_f32(3.15), 1u64);
- sketch.update(hash_value::canonical_float::from_f32(3.15), 1u64);
- sketch.update([1u8, 2, 3], 1u64);
-
- assert!(!sketch.is_empty());
- assert_eq!(sketch.estimate(), 5.0);
-
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
-
- sketch.update("string", 1u64);
- sketch.update(42i64, 1u64);
- sketch.update(42u64, 1u64);
- // where floating-point numbers have the same representation
- sketch.update(hash_value::canonical_float::from_f64(5.0), 1u64);
sketch.update(hash_value::canonical_float::from_f64(5.0), 1u64);
sketch.update(hash_value::canonical_float::from_f32(5.0), 1u64);
- sketch.update(hash_value::canonical_float::from_f32(5.0), 1u64);
sketch.update([1u8, 2, 3], 1u64);
- assert!(!sketch.is_empty());
assert_eq!(sketch.estimate(), 4.0);
}
-#[test]
-fn test_duplicate_updates() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
+#[derive(Default)]
+struct MaxPolicy;
+
+impl SummaryPolicy for MaxPolicy {
+ type Summary = u64;
- for _ in 0..100 {
- sketch.update("same_value", 1u64);
+ fn create(&self) -> Self::Summary {
+ 0
}
+}
- assert_eq!(sketch.estimate(), 1.0);
+impl SummaryUpdatePolicy<u64> for MaxPolicy {
+ fn update(&self, summary: &mut Self::Summary, value: u64) {
+ *summary = (*summary).max(value);
+ }
}
#[test]
-fn test_theta_reduction() {
- let mut sketch = default_tuple_sketch_builder().lg_k(5).build(); // Small k to trigger theta reduction
- assert!(!sketch.is_estimation_mode());
-
- // Insert many values to trigger theta reduction
- for i in 0..1000 {
- sketch.update(format!("value_{}", i), 1u64);
- }
+fn custom_update_policy_controls_retained_summaries() {
+ let mut sketch = TupleSketchBuilder::new(MaxPolicy).build();
+ sketch.update("key", 3);
+ sketch.update("key", 9);
+ sketch.update("key", 5);
- assert!(sketch.is_estimation_mode());
- assert!(sketch.theta() < 1.0);
+ assert_eq!(sketch.num_retained(), 1);
+ assert_eq!(sketch.iter().next().unwrap().1, &9);
}
#[test]
-fn test_trim() {
+fn trim_and_reset_update_public_state() {
let mut sketch = default_tuple_sketch_builder().lg_k(5).build();
-
- // Insert many values
- for i in 0..1000 {
- sketch.update(format!("value_{}", i), 1u64);
+ for value in 0..1000 {
+ sketch.update(value, 1u64);
}
- let before_trim = sketch.num_retained();
sketch.trim();
- let after_trim = sketch.num_retained();
-
- // After trim, should have approximately k entries
- assert!(after_trim <= before_trim);
assert_eq!(sketch.num_retained(), 32);
-}
-
-#[test]
-fn test_reset() {
- let mut sketch = default_tuple_sketch_builder().lg_k(5).build();
-
- // Insert many values
- for i in 0..1000 {
- sketch.update(format!("value_{}", i), 1u64);
- }
- assert!(!sketch.is_empty());
assert!(sketch.is_estimation_mode());
- assert!(sketch.num_retained() > 32);
- assert!(sketch.theta() < 1.0);
sketch.reset();
assert!(sketch.is_empty());
- assert_eq!(sketch.estimate(), 0.0);
- assert_eq!(sketch.theta(), 1.0);
assert_eq!(sketch.num_retained(), 0);
- assert!(!sketch.is_estimation_mode());
- assert_eq!(sketch.lower_bound(NumStdDev::One), 0.0);
- assert_eq!(sketch.upper_bound(NumStdDev::One), 0.0);
-}
-
-#[test]
-fn test_iterator() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
-
- sketch.update("value1", 1u64);
- sketch.update("value2", 1u64);
- sketch.update("value3", 1u64);
-
- let count: usize = sketch.iter().count();
- assert_eq!(count, sketch.num_retained());
-}
-
-#[test]
-fn test_bounds_empty_sketch() {
- let sketch = default_tuple_sketch_builder().lg_k(12).build();
- assert!(sketch.is_empty());
- assert!(!sketch.is_estimation_mode());
- assert_eq!(sketch.theta(), 1.0);
assert_eq!(sketch.estimate(), 0.0);
- assert_eq!(sketch.lower_bound(NumStdDev::One), 0.0);
- assert_eq!(sketch.upper_bound(NumStdDev::One), 0.0);
- assert_eq!(sketch.lower_bound(NumStdDev::Two), 0.0);
- assert_eq!(sketch.upper_bound(NumStdDev::Two), 0.0);
- assert_eq!(sketch.lower_bound(NumStdDev::Three), 0.0);
- assert_eq!(sketch.upper_bound(NumStdDev::Three), 0.0);
-}
-
-#[test]
-fn test_bounds_exact_mode() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
- for i in 0..2000 {
- sketch.update(i, 1u64);
- }
- assert!(!sketch.is_empty());
- assert!(!sketch.is_estimation_mode());
assert_eq!(sketch.theta(), 1.0);
- assert_eq!(sketch.estimate(), 2000.0);
- assert_eq!(sketch.lower_bound(NumStdDev::One), 2000.0);
- assert_eq!(sketch.upper_bound(NumStdDev::One), 2000.0);
-}
-
-#[test]
-fn test_bounds_estimation_mode() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
- let n = 10000;
- for i in 0..n {
- sketch.update(i, 1u64);
- }
- assert!(!sketch.is_empty());
- assert!(sketch.is_estimation_mode());
- assert!(sketch.theta() < 1.0);
-
- let estimate = sketch.estimate();
- let lower_bound_1 = sketch.lower_bound(NumStdDev::One);
- let upper_bound_1 = sketch.upper_bound(NumStdDev::One);
- let lower_bound_2 = sketch.lower_bound(NumStdDev::Two);
- let upper_bound_2 = sketch.upper_bound(NumStdDev::Two);
- let lower_bound_3 = sketch.lower_bound(NumStdDev::Three);
- let upper_bound_3 = sketch.upper_bound(NumStdDev::Three);
-
- // Check estimate is within reasonable margin (2% to be safe)
- assert!(
- (estimate - n as f64).abs() < n as f64 * 0.02,
- "estimate {} is not within 2% of {}",
- estimate,
- n
- );
-
- // Check bounds are in correct order
- assert!(lower_bound_1 < estimate);
- assert!(estimate < upper_bound_1);
- assert!(lower_bound_2 < estimate);
- assert!(estimate < upper_bound_2);
- assert!(lower_bound_3 < estimate);
- assert!(estimate < upper_bound_3);
-
- // Check that wider confidence intervals are indeed wider
- assert!(lower_bound_3 < lower_bound_2);
- assert!(lower_bound_2 < lower_bound_1);
- assert!(upper_bound_1 < upper_bound_2);
- assert!(upper_bound_2 < upper_bound_3);
+ assert!(!sketch.is_estimation_mode());
}
#[test]
-fn test_bounds_with_sampling() {
- let mut sketch = default_tuple_sketch_builder()
- .lg_k(12)
- .sampling_probability(0.5)
- .build();
-
- for i in 0..1000 {
- sketch.update(i, 1u64);
+fn bounds_cover_exact_and_estimation_results() {
+ let mut exact = default_tuple_sketch_builder().build();
+ for value in 0..100 {
+ exact.update(value, 1u64);
}
+ assert_eq!(exact.lower_bound(NumStdDev::One), 100.0);
+ assert_eq!(exact.upper_bound(NumStdDev::Three), 100.0);
- assert!(!sketch.is_empty());
- assert!(sketch.is_estimation_mode());
- assert!(sketch.theta() < 1.0);
-
- let estimate = sketch.estimate();
- let lower_bound = sketch.lower_bound(NumStdDev::Two);
- let upper_bound = sketch.upper_bound(NumStdDev::Two);
-
- assert!(lower_bound <= estimate);
- assert!(estimate <= upper_bound);
-}
-
-#[test]
-fn test_bounds_all_num_std_devs() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
- for i in 0..10000 {
- sketch.update(i, 1u64);
+ let mut estimated = default_tuple_sketch_builder().lg_k(8).build();
+ for value in 0..50_000 {
+ estimated.update(value, 1u64);
}
-
- let lb1 = sketch.lower_bound(NumStdDev::One);
- let lb2 = sketch.lower_bound(NumStdDev::Two);
- let lb3 = sketch.lower_bound(NumStdDev::Three);
- let ub1 = sketch.upper_bound(NumStdDev::One);
- let ub2 = sketch.upper_bound(NumStdDev::Two);
- let ub3 = sketch.upper_bound(NumStdDev::Three);
-
- // Verify the bounds are properly ordered
- assert!(lb3 <= lb2);
- assert!(lb2 <= lb1);
- assert!(ub1 <= ub2);
- assert!(ub2 <= ub3);
+ let estimate = estimated.estimate();
+ let lower_one = estimated.lower_bound(NumStdDev::One);
+ let lower_three = estimated.lower_bound(NumStdDev::Three);
+ let upper_one = estimated.upper_bound(NumStdDev::One);
+ let upper_three = estimated.upper_bound(NumStdDev::Three);
+
+ assert!(estimated.is_estimation_mode());
+ assert!(lower_three <= lower_one);
+ assert!(lower_one < estimate);
+ assert!(estimate < upper_one);
+ assert!(upper_one <= upper_three);
}
#[test]
-fn test_bounds_empty_estimation_mode() {
- // Create a sketch with sampling probability < 1.0 to force estimation mode
+fn empty_sampled_sketch_has_zero_bounds() {
let sketch = default_tuple_sketch_builder()
- .lg_k(12)
.sampling_probability(0.1)
.build();
- // The sketch is empty but theta < 1.0, so it's in estimation mode.
- // When empty, both bounds should return 0.0 (matching the Java/Theta behavior).
assert!(sketch.is_empty());
assert!(sketch.is_estimation_mode());
assert_eq!(sketch.estimate(), 0.0);
- assert_eq!(sketch.lower_bound(NumStdDev::One), 0.0);
- assert_eq!(sketch.upper_bound(NumStdDev::One), 0.0);
+ assert_eq!(sketch.lower_bound(NumStdDev::Three), 0.0);
+ assert_eq!(sketch.upper_bound(NumStdDev::Three), 0.0);
}
#[test]
-fn test_compact_preserves_logical_non_empty_after_screened_update() {
+fn compact_preserves_logical_non_empty_after_screened_update() {
let screened_value = (0u64..)
.find(|candidate| {
let mut sketch = default_tuple_sketch_builder()
- .lg_k(12)
.sampling_probability(0.5)
.build();
sketch.update(*candidate, 1u64);
@@ -303,15 +150,11 @@ fn test_compact_preserves_logical_non_empty_after_screened_update() {
.expect("failed to find a value screened out by the sampling theta");
let mut sketch = default_tuple_sketch_builder()
- .lg_k(12)
.sampling_probability(0.5)
.build();
sketch.update(screened_value, 1u64);
-
- assert!(!sketch.is_empty());
- assert_eq!(sketch.num_retained(), 0);
-
let compact = sketch.compact(false);
+
assert!(!compact.is_empty());
assert_eq!(compact.num_retained(), 0);
assert_eq!(compact.theta64(), sketch.theta64());
diff --git a/datasketches/tests/tuple_test/union.rs b/datasketches/tests/tuple_test/union.rs
new file mode 100644
index 0000000..bb4af8b
--- /dev/null
+++ b/datasketches/tests/tuple_test/union.rs
@@ -0,0 +1,153 @@
+// 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 datasketches::common::NumStdDev;
+use datasketches::error::ErrorKind;
+use datasketches::tuple::DefaultUnionPolicy;
+use datasketches::tuple::SummaryCombinePolicy;
+use datasketches::tuple::SummaryPolicy;
+use datasketches::tuple::TupleUnionBuilder;
+
+use super::default_tuple_sketch_builder;
+use super::tuple_sketch_with_range;
+
+fn default_union_builder() -> TupleUnionBuilder<DefaultUnionPolicy<u64>> {
+ TupleUnionBuilder::new(DefaultUnionPolicy::<u64>::default())
+}
+
+#[test]
+fn union_combines_overlapping_summaries() {
+ let mut a = default_tuple_sketch_builder().build();
+ a.update("shared", 3u64);
+ a.update("only_a", 1u64);
+ let mut b = default_tuple_sketch_builder().build();
+ b.update("shared", 4u64);
+ b.update("only_b", 1u64);
+
+ let mut union = default_union_builder().build();
+ union.update(&a).unwrap();
+ union.update(&b).unwrap();
+ let result = union.to_sketch(true);
+
+ let mut summaries: Vec<u64> = result.iter().map(|(_, &summary)| summary).collect();
+ summaries.sort_unstable();
+ assert_eq!(result.num_retained(), 3);
+ assert_eq!(summaries, [1, 1, 7]);
+}
+
+#[test]
+fn accepts_mutable_and_compact_inputs() {
+ let a = tuple_sketch_with_range(0, 500);
+ let b = tuple_sketch_with_range(250, 500);
+
+ let mut union = default_union_builder().build();
+ union.update(&a).unwrap();
+ union.update(&b.compact(true)).unwrap();
+
+ assert_eq!(union.to_sketch(true).num_retained(), 750);
+}
+
+#[test]
+fn reset_restores_the_initial_empty_state() {
+ let input = tuple_sketch_with_range(0, 100);
+ let mut union = default_union_builder().build();
+
+ assert!(union.to_sketch(true).is_empty());
+ union.update(&input).unwrap();
+ assert!(!union.to_sketch(true).is_empty());
+
+ union.reset();
+ let result = union.to_sketch(true);
+ assert!(result.is_empty());
+ assert_eq!(result.estimate(), 0.0);
+}
+
+#[test]
+fn non_empty_input_requires_the_union_seed() {
+ let mut input = default_tuple_sketch_builder().seed(1).build();
+ input.update("value", 1u64);
+ let mut union = default_union_builder().seed(2).build();
+
+ let err = union.update(&input).unwrap_err();
+ assert_eq!(err.kind(), ErrorKind::InvalidArgument);
+}
+
+#[derive(Debug, Default, Clone, Copy)]
+struct MaxPolicy;
+
+impl SummaryPolicy for MaxPolicy {
+ type Summary = u64;
+
+ fn create(&self) -> Self::Summary {
+ 0
+ }
+}
+
+impl SummaryCombinePolicy for MaxPolicy {
+ fn combine(&self, summary: &mut Self::Summary, other: &Self::Summary) {
+ *summary = (*summary).max(*other);
+ }
+}
+
+#[test]
+fn custom_combine_policy_controls_overlapping_summaries() {
+ let mut a = default_tuple_sketch_builder().build();
+ a.update("shared", 3u64);
+ let mut b = default_tuple_sketch_builder().build();
+ b.update("shared", 9u64);
+
+ let mut union = TupleUnionBuilder::new(MaxPolicy).build();
+ union.update(&a).unwrap();
+ union.update(&b).unwrap();
+
+ assert_eq!(union.to_sketch(true).iter().next().unwrap().1, &9);
+}
+
+#[test]
+fn result_ordering_follows_the_request() {
+ let input = tuple_sketch_with_range(0, 100);
+ let mut union = default_union_builder().build();
+ union.update(&input).unwrap();
+
+ assert!(union.to_sketch(true).is_ordered());
+ assert!(!union.to_sketch(false).is_ordered());
+}
+
+#[test]
+fn estimation_bounds_cover_the_true_union() {
+ let mut a = default_tuple_sketch_builder().lg_k(8).build();
+ let mut b = default_tuple_sketch_builder().lg_k(8).build();
+ for value in 0..50_000 {
+ a.update(value, 1u64);
+ }
+ for value in 25_000..75_000 {
+ b.update(value, 1u64);
+ }
+
+ let mut union = default_union_builder().lg_k(8).build();
+ union.update(&a).unwrap();
+ union.update(&b).unwrap();
+ let result = union.to_sketch(true);
+ let lower = result.lower_bound(NumStdDev::Three);
+ let upper = result.upper_bound(NumStdDev::Three);
+
+ assert!(result.is_estimation_mode());
+ assert!(
+ lower <= 75_000.0 && 75_000.0 <= upper,
+ "expected 75000 in [{lower}, {upper}]"
+ );
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org