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 11:06:32 UTC
(datasketches-rust) branch main updated: test: go through crate tests (#168)
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 3789978 test: go through crate tests (#168)
3789978 is described below
commit 3789978401e7f61711b744c67e70ec53061dab29
Author: tison <wa...@gmail.com>
AuthorDate: Tue Jul 28 19:06:27 2026 +0800
test: go through crate tests (#168)
---
.github/workflows/ci.yml | 2 +-
datasketches/Cargo.toml | 5 +
datasketches/src/bloom/builder.rs | 2 +-
datasketches/src/bloom/sketch.rs | 158 ---------
datasketches/src/hash/murmurhash.rs | 18 ++
datasketches/src/hash/xxhash.rs | 18 ++
datasketches/src/theta/hash_table.rs | 336 -------------------
datasketches/src/theta/sketch.rs | 49 ---
datasketches/src/thetacommon/hash_table.rs | 12 -
datasketches/src/tuple/a_not_b.rs | 241 --------------
datasketches/src/tuple/hash_table.rs | 355 --------------------
datasketches/src/tuple/intersection.rs | 227 -------------
datasketches/src/tuple/policy.rs | 67 ----
datasketches/src/tuple/serialization.rs | 35 --
datasketches/src/tuple/sketch.rs | 356 ---------------------
datasketches/src/tuple/union.rs | 224 -------------
.../tests/{tuple_test => bloom_test}/main.rs | 18 --
datasketches/tests/bloom_test/sketch.rs | 163 ++++++++++
datasketches/tests/cpc_test/union.rs | 6 +-
datasketches/tests/serde_tests/theta.rs | 28 ++
datasketches/tests/serde_tests/tuple.rs | 39 +++
datasketches/tests/theta_test/sketch.rs | 17 +-
datasketches/tests/tuple_test/a_not_b.rs | 300 +++++++----------
datasketches/tests/tuple_test/intersection.rs | 342 ++++++--------------
datasketches/tests/tuple_test/main.rs | 1 +
datasketches/tests/tuple_test/sketch.rs | 327 +++++++------------
datasketches/tests/tuple_test/union.rs | 153 +++++++++
xtask/src/main.rs | 2 +-
28 files changed, 774 insertions(+), 2727 deletions(-)
diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml
index 13c665e..4768c32 100644
--- a/.github/workflows/ci.yml
+++ b/.github/workflows/ci.yml
@@ -94,7 +94,7 @@ jobs:
- name: Prepare test data
shell: bash
run: ./tools/download_serde_tests_data.py
- - name: Run unit tests
+ - name: Run test suite
shell: bash
run: cargo x test
diff --git a/datasketches/Cargo.toml b/datasketches/Cargo.toml
index e3bdec1..2f3912b 100644
--- a/datasketches/Cargo.toml
+++ b/datasketches/Cargo.toml
@@ -47,6 +47,11 @@ tdigest = []
theta = []
tuple = []
+[[test]]
+name = "bloom_test"
+path = "tests/bloom_test/main.rs"
+required-features = ["bloom"]
+
[[test]]
name = "countmin_test"
path = "tests/countmin_test/main.rs"
diff --git a/datasketches/src/bloom/builder.rs b/datasketches/src/bloom/builder.rs
index 6cb0158..7622160 100644
--- a/datasketches/src/bloom/builder.rs
+++ b/datasketches/src/bloom/builder.rs
@@ -120,7 +120,7 @@ impl BloomFilterBuilder {
);
assert!(
(Self::MIN_NUM_HASHES..=Self::MAX_NUM_HASHES).contains(&num_hashes),
- "num_bits must be between {} and {}, got {}",
+ "num_hashes must be between {} and {}, got {}",
Self::MIN_NUM_HASHES,
Self::MAX_NUM_HASHES,
num_hashes
diff --git a/datasketches/src/bloom/sketch.rs b/datasketches/src/bloom/sketch.rs
index 4fab1c0..ee17cff 100644
--- a/datasketches/src/bloom/sketch.rs
+++ b/datasketches/src/bloom/sketch.rs
@@ -567,161 +567,3 @@ impl BloomFilter {
size_of::<Self>() + self.bit_array.len() * size_of::<u64>()
}
}
-
-#[cfg(test)]
-mod tests {
- use super::BloomFilter;
- use crate::bloom::BloomFilterBuilder;
-
- #[test]
- fn test_builder_with_accuracy() {
- let filter = BloomFilterBuilder::with_accuracy(1000, 0.01).build();
- assert!(filter.capacity() >= 9000);
- assert_eq!(filter.num_hashes(), 7);
- assert!(filter.is_empty());
- }
-
- #[test]
- fn test_builder_with_size() {
- let filter = BloomFilterBuilder::with_size(1024, 5).build();
- assert_eq!(filter.capacity(), 1024);
- assert_eq!(filter.num_hashes(), 5);
- }
-
- #[test]
- fn test_builder_with_size_rounds_to_word_boundary() {
- let filter = BloomFilterBuilder::with_size(1, 3).build();
- assert_eq!(filter.capacity(), 64);
- assert_eq!(filter.num_hashes(), 3);
- }
-
- #[test]
- fn test_insert_and_contains() {
- let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01).build();
-
- assert!(!filter.contains(&"apple"));
- filter.insert("apple");
- assert!(filter.contains(&"apple"));
- assert!(!filter.is_empty());
- }
-
- #[test]
- fn test_contains_and_insert() {
- let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01).build();
-
- let was_present = filter.contains_and_insert(&42_u64);
- assert!(!was_present);
-
- let was_present = filter.contains_and_insert(&42_u64);
- assert!(was_present);
- }
-
- #[test]
- fn test_reset() {
- let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01).build();
- filter.insert("test");
- assert!(!filter.is_empty());
-
- filter.reset();
- assert!(filter.is_empty());
- assert!(!filter.contains(&"test"));
- }
-
- #[test]
- fn test_union() {
- let mut f1 = BloomFilterBuilder::with_accuracy(100, 0.01)
- .seed(123)
- .build();
- let mut f2 = BloomFilterBuilder::with_accuracy(100, 0.01)
- .seed(123)
- .build();
-
- f1.insert("a");
- f2.insert("b");
-
- f1.union(&f2);
- assert!(f1.contains(&"a"));
- assert!(f1.contains(&"b"));
- }
-
- #[test]
- fn test_intersect() {
- let mut f1 = BloomFilterBuilder::with_accuracy(100, 0.01)
- .seed(123)
- .build();
- let mut f2 = BloomFilterBuilder::with_accuracy(100, 0.01)
- .seed(123)
- .build();
-
- f1.insert("a");
- f1.insert("b");
- f2.insert("b");
- f2.insert("c");
-
- f1.intersect(&f2);
- assert!(f1.contains(&"b"));
- }
-
- #[test]
- fn test_serialize_deserialize_empty() {
- let filter = BloomFilterBuilder::with_accuracy(100, 0.01).build();
- let bytes = filter.serialize();
- let restored = BloomFilter::deserialize(&bytes).unwrap();
-
- assert_eq!(filter, restored);
- }
-
- #[test]
- fn test_serialize_deserialize_with_data() {
- let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01).build();
- filter.insert("test");
- filter.insert(42_u64);
-
- let bytes = filter.serialize();
- let restored = BloomFilter::deserialize(&bytes).unwrap();
-
- assert_eq!(filter, restored);
- assert!(restored.contains(&"test"));
- assert!(restored.contains(&42_u64));
- }
-
- #[test]
- fn test_statistics() {
- let mut filter = BloomFilterBuilder::with_size(1000, 5).build();
- assert_eq!(filter.bits_used(), 0);
- assert_eq!(filter.load_factor(), 0.0);
-
- filter.insert("test");
- assert!(filter.bits_used() > 0);
- assert!(filter.load_factor() > 0.0);
- assert!(filter.estimated_fpp() > 0.0);
- }
-
- #[test]
- fn test_is_compatible() {
- let f1 = BloomFilterBuilder::with_accuracy(100, 0.01)
- .seed(123)
- .build();
- let f2 = BloomFilterBuilder::with_accuracy(100, 0.01)
- .seed(123)
- .build();
- let f3 = BloomFilterBuilder::with_accuracy(100, 0.01)
- .seed(456)
- .build();
-
- assert!(f1.is_compatible(&f2));
- assert!(!f1.is_compatible(&f3));
- }
-
- #[test]
- #[should_panic(expected = "max_items must be greater than 0")]
- fn test_invalid_max_items() {
- BloomFilterBuilder::with_accuracy(0, 0.01);
- }
-
- #[test]
- #[should_panic(expected = "fpp must be between")]
- fn test_invalid_fpp() {
- BloomFilterBuilder::with_accuracy(100, 1.5);
- }
-}
diff --git a/datasketches/src/hash/murmurhash.rs b/datasketches/src/hash/murmurhash.rs
index a99f5eb..03345f2 100644
--- a/datasketches/src/hash/murmurhash.rs
+++ b/datasketches/src/hash/murmurhash.rs
@@ -186,6 +186,24 @@ mod tests {
hasher.finish128()
}
+ #[test]
+ fn streaming_writes_match_single_write() {
+ let input: Vec<u8> = (0..=96).collect();
+ for len in 0..=input.len() {
+ let expected = murmurhash3_x64_128(&input[..len], 42);
+ for split in 0..=len {
+ let mut hasher = MurmurHash3X64128::with_seed(42);
+ hasher.write(&input[..split]);
+ hasher.write(&input[split..len]);
+ assert_eq!(
+ hasher.finish128(),
+ expected,
+ "hash changed for input length {len} split at {split}"
+ );
+ }
+ }
+ }
+
#[test]
fn test_remainder() {
// remainder > 8
diff --git a/datasketches/src/hash/xxhash.rs b/datasketches/src/hash/xxhash.rs
index 6232c04..25852ea 100644
--- a/datasketches/src/hash/xxhash.rs
+++ b/datasketches/src/hash/xxhash.rs
@@ -216,6 +216,24 @@ mod tests {
hasher.finish64()
}
+ #[test]
+ fn streaming_writes_match_single_write() {
+ let input: Vec<u8> = (0..=96).collect();
+ for len in 0..=input.len() {
+ let expected = xxhash64(&input[..len], PRIME32);
+ for split in 0..=len {
+ let mut hasher = XxHash64::with_seed(PRIME32);
+ hasher.write(&input[..split]);
+ hasher.write(&input[split..len]);
+ assert_eq!(
+ hasher.finish64(),
+ expected,
+ "hash changed for input length {len} split at {split}"
+ );
+ }
+ }
+ }
+
#[test]
fn test_vectors_seed_zero() {
let buf = fill_test_buffer(101);
diff --git a/datasketches/src/theta/hash_table.rs b/datasketches/src/theta/hash_table.rs
index f9e82d6..b10ae57 100644
--- a/datasketches/src/theta/hash_table.rs
+++ b/datasketches/src/theta/hash_table.rs
@@ -76,339 +76,3 @@ impl ThetaHashTable {
})
}
}
-
-#[cfg(test)]
-mod tests {
- use super::*;
- use crate::common::ResizeFactor;
- use crate::hash::DEFAULT_UPDATE_SEED;
- use crate::thetacommon::constants::MAX_THETA;
- use crate::thetacommon::constants::MIN_LG_K;
- use crate::thetacommon::hash_table::starting_sub_multiple;
- use crate::thetacommon::hash_table::starting_theta_from_sampling_probability;
-
- impl ThetaHashTable {
- /// Get iterator over entries.
- pub fn iter(&self) -> impl Iterator<Item = u64> + '_ {
- self.iter_entries().map(RetainedEntry::hash)
- }
- }
-
- #[test]
- fn test_new_hash_table() {
- let table = ThetaHashTable::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- assert_eq!(
- table.lg_cur_size(),
- starting_sub_multiple(8 + 1, MIN_LG_K, ResizeFactor::X8.lg_value())
- );
- assert_eq!(table.theta(), starting_theta_from_sampling_probability(1.0));
- assert_eq!(table.num_retained(), 0);
- assert!(table.is_empty());
- assert_eq!(table.iter().count(), 0);
- }
-
- #[test]
- fn test_hash_and_theta_screen_behavior() {
- let mut table = ThetaHashTable::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- // With MAX_THETA, hashes are computed normally.
- let hash1 = table.hash("test1");
- let hash2 = table.hash("test2");
- assert_ne!(hash1, 0);
- assert_ne!(hash2, 0);
- assert_ne!(hash1, hash2);
-
- // With low theta, update should be screened out.
- table.set_theta(1);
- assert!(!table.try_insert("test3"));
- }
-
- #[test]
- fn test_try_insert() {
- let mut table = ThetaHashTable::new(5, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- assert!(table.try_insert("test_value"));
- assert_eq!(table.num_retained(), 1);
- assert!(!table.is_empty());
-
- // Try to insert the same value again (should fail)
- assert!(!table.try_insert("test_value"));
- assert_eq!(table.num_retained(), 1);
-
- // Force screening and verify insertion fails
- table.set_theta(1); // Set theta to a low value to screen out new entries
- assert!(!table.try_insert("screened"));
- assert_eq!(table.num_retained(), 1);
- assert!(!table.is_empty());
- }
-
- #[test]
- fn test_insert_multiple_values() {
- let mut table = ThetaHashTable::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- // Insert multiple distinct values
- let mut inserted_count = 0;
- for i in 0..10 {
- if table.try_insert(format!("value_{}", i)) {
- inserted_count += 1;
- }
- }
-
- assert_eq!(table.num_retained(), inserted_count);
- assert!(!table.is_empty());
- assert_eq!(table.iter().count(), inserted_count);
- }
-
- #[test]
- fn test_resize() {
- fn populate_values(table: &mut ThetaHashTable, count: usize) -> usize {
- let mut inserted = 0;
- for i in 0..count {
- if table.try_insert(format!("value_{}", i)) {
- inserted += 1;
- }
- }
- inserted
- }
-
- {
- let mut table = ThetaHashTable::new(8, ResizeFactor::X2, 1.0, DEFAULT_UPDATE_SEED);
-
- assert_eq!(table.num_entries(), 32);
-
- // Insert enough values to trigger resize (50% threshold)
- // Capacity = 32 * 0.5 = 16
- let inserted = populate_values(&mut table, 20);
-
- // Table should have resized and all values should be inserted
- assert!(table.num_retained() > 0);
- assert_eq!(table.num_retained(), inserted);
- assert_eq!(table.num_entries(), 64);
- }
-
- // Test different resize factors
- {
- let mut table = ThetaHashTable::new(8, ResizeFactor::X4, 1.0, DEFAULT_UPDATE_SEED);
-
- assert_eq!(table.num_entries(), 32);
-
- // Insert enough values to trigger resize (50% threshold)
- // Capacity = 32 * 0.5 = 16
- let inserted = populate_values(&mut table, 20);
-
- // Table should have resized and all values should be inserted
- assert!(table.num_retained() > 0);
- assert_eq!(table.num_retained(), inserted);
- assert_eq!(table.num_entries(), 128);
- }
- }
-
- #[test]
- fn test_rebuild() {
- let mut table = ThetaHashTable::new(5, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- assert_eq!(table.lg_cur_size(), 6);
- assert_eq!(table.num_entries(), 64);
- assert_eq!(table.theta(), MAX_THETA);
-
- // Insert many values to trigger rebuild
- for i in 0..100 {
- table.try_insert(format!("value_{i}"));
- }
-
- // After rebuild, theta should be reduced (rebuild is called automatically during insert)
- let new_theta = table.theta();
- assert!(
- new_theta < MAX_THETA,
- "Theta should be reduced after rebuild"
- );
-
- // Continue to insert values to trigger rebuild again
- for i in 100..200 {
- table.try_insert(format!("value_{i}"));
- }
-
- assert_eq!(table.lg_cur_size(), 6);
- assert!(table.num_entries() >= 64);
- assert!(table.theta() < new_theta);
- }
-
- #[test]
- fn test_trim() {
- let mut table = ThetaHashTable::new(5, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- // Insert more than k values
- for i in 0..100 {
- table.try_insert(format!("value_{i}"));
- }
-
- let before_trim = table.num_retained();
- assert!(before_trim > 32);
-
- table.trim();
- let after_trim = table.num_retained();
- assert!(after_trim <= 32);
- assert!(table.theta() < MAX_THETA);
- }
-
- #[test]
- fn test_trim_when_not_needed() {
- let mut table = ThetaHashTable::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- // Insert fewer than k values
- for i in 0..10 {
- table.try_insert(format!("value_{i}"));
- }
-
- let before_trim = table.num_retained();
- let before_theta = table.theta();
- table.trim();
- let after_trim = table.num_retained();
-
- // Should not change if already <= k
- assert_eq!(before_trim, after_trim);
- assert_eq!(before_theta, table.theta());
- }
-
- #[test]
- fn test_reset() {
- let mut table = ThetaHashTable::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
- let init_theta = table.theta();
- let init_lg_cur = table.lg_cur_size();
- let init_entries = table.num_entries();
-
- // Insert some values
- for i in 0..10 {
- table.try_insert(format!("value_{i}"));
- }
-
- assert!(!table.is_empty());
- assert!(table.num_retained() > 0);
-
- // Reset
- table.reset();
-
- assert!(table.is_empty());
- assert_eq!(table.num_retained(), 0);
- assert_eq!(table.theta(), init_theta);
- assert_eq!(table.lg_cur_size(), init_lg_cur);
- assert_eq!(table.num_entries(), init_entries);
- assert_eq!(table.iter().count(), 0);
- }
-
- #[test]
- fn test_table_with_sampling() {
- let mut table = ThetaHashTable::new(
- 8,
- ResizeFactor::X8,
- 0.5, // sampling_probability = 0.5
- DEFAULT_UPDATE_SEED,
- );
- assert_eq!(table.theta(), (MAX_THETA as f64 * 0.5) as u64);
-
- // Insert some values
- for i in 0..10 {
- table.try_insert(format!("value_{i}"));
- }
-
- table.reset();
-
- // With sampling_probability = 0.5, theta should be MAX_THETA * 0.5
- assert_eq!(table.theta(), (MAX_THETA as f64 * 0.5) as u64);
- assert!(table.is_empty());
- }
-
- #[test]
- fn test_iterator() {
- let mut table = ThetaHashTable::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- // Insert some values
- let mut inserted_hashes = vec![];
- for i in 0..10 {
- let hash = table.hash(i);
- if table.try_insert(i) {
- inserted_hashes.push(hash);
- }
- }
-
- // Check iterator
- let iter_hashes: Vec<u64> = table.iter().collect();
- assert_eq!(iter_hashes.len(), table.num_retained());
- assert_eq!(iter_hashes.len(), inserted_hashes.len());
-
- // All inserted hashes should be in iterator
- for hash in &inserted_hashes {
- assert!(iter_hashes.contains(hash));
- }
-
- // Iterator should not contain 0
- assert!(!iter_hashes.contains(&0));
- }
-
- #[test]
- fn test_empty_table_operations() {
- let mut table = ThetaHashTable::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- assert!(table.is_empty());
- assert_eq!(table.num_retained(), 0);
- assert_eq!(table.iter().count(), 0);
-
- // Trim on empty table should not panic
- table.trim();
- assert!(table.is_empty());
-
- // Reset on empty table should not panic
- table.reset();
- assert!(table.is_empty());
- }
-
- #[test]
- fn test_rebuild_preserves_entries_less_than_kth() {
- let mut table = ThetaHashTable::new(5, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
- let k = 1u64 << 5; // k = 32
-
- // Insert many values to trigger rebuild
- let mut i = 0;
- let mut inserted_hashes = vec![];
- loop {
- let hash = table.hash(i);
- i += 1;
- if table.try_insert(i - 1) {
- inserted_hashes.push(hash);
- }
- if table.num_retained() >= k as usize {
- break;
- }
- }
-
- let rebuild_threshold = table.capacity_threshold();
-
- loop {
- let hash = table.hash(i);
- i += 1;
- if table.try_insert(i - 1) {
- inserted_hashes.push(hash);
- }
- if table.num_retained() >= rebuild_threshold {
- break;
- }
- }
-
- // trigger rebuild
- loop {
- let hash = table.hash(i);
- i += 1;
- if table.try_insert(i - 1) {
- inserted_hashes.push(hash);
- break;
- }
- }
-
- // assert all entries are less than kth
- inserted_hashes.sort();
- let kth = inserted_hashes[k as usize];
- assert!(table.iter().all(|e| e < kth));
- assert_eq!(table.theta(), kth);
- }
-}
diff --git a/datasketches/src/theta/sketch.rs b/datasketches/src/theta/sketch.rs
index 9ced2b4..cc78b9c 100644
--- a/datasketches/src/theta/sketch.rs
+++ b/datasketches/src/theta/sketch.rs
@@ -1135,53 +1135,4 @@ mod tests {
assert_compressed_round_trip(&theta, &compact);
}
-
- #[test]
- fn deserialize_rejects_seed_hash_mismatch() {
- let mut theta = ThetaSketchBuilder::default().seed(7).build();
- theta.update("apple");
- let bytes = theta.compact(true).serialize();
-
- let err = CompactThetaSketch::deserialize_with_seed(&bytes, 8).unwrap_err();
- assert_eq!(err.kind(), crate::error::ErrorKind::InvalidData);
- assert!(err.message().contains("incompatible seed hash"));
- }
-
- #[test]
- fn deserialize_rejects_invalid_family_id() {
- let mut theta = ThetaSketchBuilder::default().build();
- theta.update("apple");
- let mut bytes = theta.compact(true).serialize();
- bytes[2] = 0;
-
- let err = CompactThetaSketch::deserialize(&bytes).unwrap_err();
- assert_eq!(err.kind(), crate::error::ErrorKind::InvalidData);
- assert!(err.message().contains("invalid family"));
- }
-
- #[test]
- fn deserialize_rejects_unsupported_serial_version() {
- let mut theta = ThetaSketchBuilder::default().build();
- theta.update("apple");
- let mut bytes = theta.compact(true).serialize();
- bytes[1] = 99;
-
- let err = CompactThetaSketch::deserialize(&bytes).unwrap_err();
- assert_eq!(err.kind(), crate::error::ErrorKind::InvalidData);
- assert!(err.message().contains("unsupported serial version"));
- }
-
- #[test]
- fn deserialize_rejects_truncated_payload() {
- let mut theta = ThetaSketchBuilder::default().lg_k(5).build();
- for i in 0..5000 {
- theta.update(i);
- }
- let mut bytes = theta.compact(true).serialize();
- bytes.pop();
-
- let err = CompactThetaSketch::deserialize(&bytes).unwrap_err();
- assert_eq!(err.kind(), crate::error::ErrorKind::InvalidData);
- assert!(err.message().contains("insufficient data"));
- }
}
diff --git a/datasketches/src/thetacommon/hash_table.rs b/datasketches/src/thetacommon/hash_table.rs
index 21b54f7..6cc2a9c 100644
--- a/datasketches/src/thetacommon/hash_table.rs
+++ b/datasketches/src/thetacommon/hash_table.rs
@@ -287,18 +287,6 @@ where
}
}
- /// Return number of all entries.
- #[cfg(test)]
- pub fn num_entries(&self) -> usize {
- self.entries.len()
- }
-
- /// Get log2 of current size.
- #[cfg(test)]
- pub fn lg_cur_size(&self) -> u8 {
- self.lg_cur_size
- }
-
/// Get log2 of nominal size.
pub fn lg_nom_size(&self) -> u8 {
self.lg_nom_size
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/hash_table.rs b/datasketches/src/tuple/hash_table.rs
index c88d4f0..e64520f 100644
--- a/datasketches/src/tuple/hash_table.rs
+++ b/datasketches/src/tuple/hash_table.rs
@@ -119,358 +119,3 @@ impl<P: SummaryCombinePolicy> IntersectionMergePolicy<TupleEntry<P::Summary>> fo
self.combine(&mut existing.summary, &incoming.summary);
}
}
-
-#[cfg(test)]
-mod tests {
- use super::*;
- use crate::common::ResizeFactor;
- use crate::hash::DEFAULT_UPDATE_SEED;
- use crate::thetacommon::constants::MAX_THETA;
- use crate::thetacommon::constants::MIN_LG_K;
- use crate::thetacommon::hash_table::starting_sub_multiple;
- use crate::thetacommon::hash_table::starting_theta_from_sampling_probability;
-
- impl TupleHashTable<u64> {
- /// Inserts a key with count-style summary semantics: a new key starts at 1, a repeated key
- /// increments the retained count. Returns true if a new entry was created.
- fn insert(&mut self, value: impl Hash) -> bool {
- self.try_insert(value, |existing| match existing {
- Some(count) => {
- *count += 1;
- None
- }
- None => Some(1),
- })
- }
-
- /// Returns the retained `(hash, count)` pairs.
- fn pairs(&self) -> Vec<(u64, u64)> {
- self.iter().map(|(hash, &count)| (hash, count)).collect()
- }
- }
-
- #[test]
- fn option_entry_keeps_nonzero_niche() {
- // The NonZeroU64 hash gives Option<TupleEntry<S>> a niche, so table slots carry no
- // discriminant overhead on top of the entry itself.
- assert_eq!(
- size_of::<Option<TupleEntry<u64>>>(),
- size_of::<TupleEntry<u64>>()
- );
- }
-
- #[test]
- fn test_new_hash_table() {
- let table = TupleHashTable::<u64>::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- assert_eq!(
- table.lg_cur_size(),
- starting_sub_multiple(8 + 1, MIN_LG_K, ResizeFactor::X8.lg_value())
- );
- assert_eq!(table.theta(), starting_theta_from_sampling_probability(1.0));
- assert_eq!(table.num_retained(), 0);
- assert!(table.is_empty());
- assert_eq!(table.iter().count(), 0);
- }
-
- #[test]
- fn test_hash_and_theta_screen_behavior() {
- let mut table = TupleHashTable::<u64>::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- // With MAX_THETA, hashes are computed normally.
- let hash1 = table.hash("test1");
- let hash2 = table.hash("test2");
- assert_ne!(hash1, 0);
- assert_ne!(hash2, 0);
- assert_ne!(hash1, hash2);
-
- // With low theta, update should be screened out.
- table.set_theta(1);
- assert!(!table.insert("test3"));
- }
-
- #[test]
- fn test_insert() {
- let mut table = TupleHashTable::<u64>::new(5, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- assert!(table.insert("test_value"));
- assert_eq!(table.num_retained(), 1);
- assert!(!table.is_empty());
-
- // Insert the same value again: not a new entry, but the summary is merged.
- assert!(!table.insert("test_value"));
- assert_eq!(table.num_retained(), 1);
- assert_eq!(table.pairs(), vec![(table.hash("test_value"), 2)]);
-
- // Force screening and verify insertion fails
- table.set_theta(1);
- assert!(!table.insert("screened"));
- assert_eq!(table.num_retained(), 1);
- assert!(!table.is_empty());
- }
-
- #[test]
- fn test_insert_multiple_values() {
- let mut table = TupleHashTable::<u64>::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- let mut inserted_count = 0;
- for i in 0..10 {
- if table.insert(format!("value_{}", i)) {
- inserted_count += 1;
- }
- }
-
- assert_eq!(table.num_retained(), inserted_count);
- assert!(!table.is_empty());
- assert_eq!(table.iter().count(), inserted_count);
- }
-
- #[test]
- fn test_summary_is_merged_on_collision() {
- let mut table = TupleHashTable::<u64>::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- for _ in 0..5 {
- table.insert("same_key");
- }
-
- assert_eq!(table.num_retained(), 1);
- assert_eq!(table.pairs(), vec![(table.hash("same_key"), 5)]);
- }
-
- #[test]
- fn test_resize() {
- fn populate_values(table: &mut TupleHashTable<u64>, count: usize) -> usize {
- let mut inserted = 0;
- for i in 0..count {
- if table.insert(format!("value_{i}")) {
- inserted += 1;
- }
- }
- inserted
- }
-
- {
- let mut table =
- TupleHashTable::<u64>::new(8, ResizeFactor::X2, 1.0, DEFAULT_UPDATE_SEED);
-
- assert_eq!(table.num_entries(), 32);
-
- // Insert enough values to trigger resize (50% threshold)
- // Capacity = 32 * 0.5 = 16
- let inserted = populate_values(&mut table, 20);
-
- assert!(table.num_retained() > 0);
- assert_eq!(table.num_retained(), inserted);
- assert_eq!(table.num_entries(), 64);
- }
-
- {
- let mut table =
- TupleHashTable::<u64>::new(8, ResizeFactor::X4, 1.0, DEFAULT_UPDATE_SEED);
-
- assert_eq!(table.num_entries(), 32);
-
- let inserted = populate_values(&mut table, 20);
-
- assert!(table.num_retained() > 0);
- assert_eq!(table.num_retained(), inserted);
- assert_eq!(table.num_entries(), 128);
- }
- }
-
- #[test]
- fn test_rebuild() {
- let mut table = TupleHashTable::<u64>::new(5, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- assert_eq!(table.lg_cur_size(), 6);
- assert_eq!(table.num_entries(), 64);
- assert_eq!(table.theta(), MAX_THETA);
-
- // Insert many values to trigger rebuild
- for i in 0..100 {
- table.insert(format!("value_{i}"));
- }
-
- let new_theta = table.theta();
- assert!(
- new_theta < MAX_THETA,
- "Theta should be reduced after rebuild"
- );
-
- // Continue to insert values to trigger rebuild again
- for i in 100..200 {
- table.insert(format!("value_{i}"));
- }
-
- assert_eq!(table.lg_cur_size(), 6);
- assert!(table.num_entries() >= 64);
- assert!(table.theta() < new_theta);
- }
-
- #[test]
- fn test_trim() {
- let mut table = TupleHashTable::<u64>::new(5, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- for i in 0..100 {
- table.insert(format!("value_{i}"));
- }
-
- let before_trim = table.num_retained();
- assert!(before_trim > 32);
-
- table.trim();
- let after_trim = table.num_retained();
- assert!(after_trim <= 32);
- assert!(table.theta() < MAX_THETA);
- }
-
- #[test]
- fn test_trim_when_not_needed() {
- let mut table = TupleHashTable::<u64>::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- for i in 0..10 {
- table.insert(format!("value_{i}"));
- }
-
- let before_trim = table.num_retained();
- let before_theta = table.theta();
- table.trim();
- let after_trim = table.num_retained();
-
- assert_eq!(before_trim, after_trim);
- assert_eq!(before_theta, table.theta());
- }
-
- #[test]
- fn test_reset() {
- let mut table = TupleHashTable::<u64>::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
- let init_theta = table.theta();
- let init_lg_cur = table.lg_cur_size();
- let init_entries = table.num_entries();
-
- for i in 0..10 {
- table.insert(format!("value_{i}"));
- }
-
- assert!(!table.is_empty());
- assert!(table.num_retained() > 0);
-
- table.reset();
-
- assert!(table.is_empty());
- assert_eq!(table.num_retained(), 0);
- assert_eq!(table.theta(), init_theta);
- assert_eq!(table.lg_cur_size(), init_lg_cur);
- assert_eq!(table.num_entries(), init_entries);
- assert_eq!(table.iter().count(), 0);
- }
-
- #[test]
- fn test_table_with_sampling() {
- let mut table = TupleHashTable::<u64>::new(
- 8,
- ResizeFactor::X8,
- 0.5, // sampling_probability = 0.5
- DEFAULT_UPDATE_SEED,
- );
- assert_eq!(table.theta(), (MAX_THETA as f64 * 0.5) as u64);
-
- for i in 0..10 {
- table.insert(format!("value_{i}"));
- }
-
- table.reset();
-
- assert_eq!(table.theta(), (MAX_THETA as f64 * 0.5) as u64);
- assert!(table.is_empty());
- }
-
- #[test]
- fn test_iterator() {
- let mut table = TupleHashTable::<u64>::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- let mut inserted_hashes = vec![];
- for i in 0..10 {
- let hash = table.hash(i);
- if table.insert(i) {
- inserted_hashes.push(hash);
- }
- }
-
- let iter_hashes: Vec<u64> = table.iter().map(|(hash, _)| hash).collect();
- assert_eq!(iter_hashes.len(), table.num_retained());
- assert_eq!(iter_hashes.len(), inserted_hashes.len());
-
- for hash in &inserted_hashes {
- assert!(iter_hashes.contains(hash));
- }
-
- assert!(!iter_hashes.contains(&0));
- }
-
- #[test]
- fn test_empty_table_operations() {
- let mut table = TupleHashTable::<u64>::new(8, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
-
- assert!(table.is_empty());
- assert_eq!(table.num_retained(), 0);
- assert_eq!(table.iter().count(), 0);
-
- // Trim on empty table should not panic
- table.trim();
- assert!(table.is_empty());
-
- // Reset on empty table should not panic
- table.reset();
- assert!(table.is_empty());
- }
-
- #[test]
- fn test_rebuild_preserves_entries_less_than_kth() {
- let mut table = TupleHashTable::<u64>::new(5, ResizeFactor::X8, 1.0, DEFAULT_UPDATE_SEED);
- let k = 1u64 << 5; // k = 32
-
- // Insert many values to trigger rebuild
- let mut i = 0;
- let mut inserted_hashes = vec![];
- loop {
- let hash = table.hash(i);
- i += 1;
- if table.insert(i - 1) {
- inserted_hashes.push(hash);
- }
- if table.num_retained() >= k as usize {
- break;
- }
- }
-
- let rebuild_threshold = table.capacity_threshold();
-
- loop {
- let hash = table.hash(i);
- i += 1;
- if table.insert(i - 1) {
- inserted_hashes.push(hash);
- }
- if table.num_retained() >= rebuild_threshold {
- break;
- }
- }
-
- // trigger rebuild
- loop {
- let hash = table.hash(i);
- i += 1;
- if table.insert(i - 1) {
- inserted_hashes.push(hash);
- break;
- }
- }
-
- // assert all entries are less than kth
- inserted_hashes.sort();
- let kth = inserted_hashes[k as usize];
- assert!(table.iter().all(|(hash, _)| hash < kth));
- assert_eq!(table.theta(), kth);
- }
-}
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 b43adeb..b06c406 100644
--- a/datasketches/src/tuple/sketch.rs
+++ b/datasketches/src/tuple/sketch.rs
@@ -709,359 +709,3 @@ where
}
}
}
-
-#[cfg(test)]
-mod tests {
- use super::*;
- use crate::error::ErrorKind;
- 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
- P: SummaryPolicy<Summary = u64>,
- {
- let mut entries: Vec<(u64, u64)> = sketch.iter().map(|(h, &s)| (h, s)).collect();
- entries.sort_unstable();
- entries
- }
-
- fn sorted_compact_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
- }
-
- fn assert_updatable_and_compact_equivalent<P>(
- updatable: &TupleSketch<P>,
- compact: &CompactTupleSketch<u64>,
- ) where
- P: SummaryPolicy<Summary = u64>,
- {
- assert_eq!(updatable.is_empty(), compact.is_empty());
- assert_eq!(updatable.is_estimation_mode(), compact.is_estimation_mode());
- assert_eq!(updatable.num_retained(), compact.num_retained());
- assert_eq!(updatable.theta64(), compact.theta64());
- assert_eq!(updatable.seed_hash(), compact.seed_hash());
- assert_eq!(
- sorted_updatable_entries(updatable),
- sorted_compact_entries(compact)
- );
- assert!((updatable.estimate() - compact.estimate()).abs() <= 1e-9);
- }
-
- #[test]
- fn exact_mode_updatable_and_compact_equivalent() {
- 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());
-
- for ordered in [false, true] {
- let compact = sketch.compact(ordered);
- assert_updatable_and_compact_equivalent(&sketch, &compact);
- if compact.num_retained() > 1 {
- assert_eq!(compact.is_ordered(), ordered);
- }
- }
- }
-
- #[test]
- fn estimation_mode_updatable_and_compact_equivalent() {
- let policy = DefaultUpdatePolicy::<u64>::default();
- let mut sketch = TupleSketchBuilder::new(policy).lg_k(5).build();
- for i in 0..5000 {
- sketch.update(i, 1u64);
- }
- assert!(sketch.is_estimation_mode());
-
- for ordered in [false, true] {
- let compact = sketch.compact(ordered);
- 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));
- }
-
- #[test]
- fn deserialize_rejects_wrong_family() {
- let policy = DefaultUpdatePolicy::<u64>::default();
- let mut sketch = TupleSketchBuilder::new(policy).build();
- for i in 0..10 {
- sketch.update(i, 1u64);
- }
- let mut bytes = sketch.compact(true).serialize();
- bytes[2] = 3; // pretend it is a THETA sketch
- let err = CompactTupleSketch::<u64>::deserialize(&bytes).unwrap_err();
- assert_eq!(err.kind(), ErrorKind::InvalidData);
- }
-
- #[test]
- fn deserialize_rejects_seed_mismatch() {
- let policy = DefaultUpdatePolicy::<u64>::default();
- let mut sketch = TupleSketchBuilder::new(policy).build();
- for i in 0..10 {
- sketch.update(i, 1u64);
- }
- let bytes = sketch.compact(true).serialize();
- let err = CompactTupleSketch::<u64>::deserialize_with_seed(&bytes, 999).unwrap_err();
- assert_eq!(err.kind(), ErrorKind::InvalidData);
- }
-
- #[test]
- fn deserialize_rejects_truncated_summary() {
- 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();
- let truncated = &bytes[..bytes.len() - 4]; // cut the last summary in half
- let err = CompactTupleSketch::<u64>::deserialize(truncated).unwrap_err();
- assert_eq!(err.kind(), ErrorKind::InvalidData);
- }
-}
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/tuple_test/main.rs b/datasketches/tests/bloom_test/main.rs
similarity index 59%
copy from datasketches/tests/tuple_test/main.rs
copy to datasketches/tests/bloom_test/main.rs
index f5747e9..825a628 100644
--- a/datasketches/tests/tuple_test/main.rs
+++ b/datasketches/tests/bloom_test/main.rs
@@ -15,22 +15,4 @@
// specific language governing permissions and limitations
// under the License.
-mod a_not_b;
-mod intersection;
mod sketch;
-
-use datasketches::tuple::DefaultUpdatePolicy;
-use datasketches::tuple::TupleSketch;
-use datasketches::tuple::TupleSketchBuilder;
-
-fn default_tuple_sketch_builder() -> TupleSketchBuilder<DefaultUpdatePolicy<u64>> {
- TupleSketchBuilder::new(DefaultUpdatePolicy::<u64>::default())
-}
-
-fn tuple_sketch_with_range(start: u64, count: u64) -> TupleSketch<DefaultUpdatePolicy<u64>> {
- let mut sketch = default_tuple_sketch_builder().build();
- for i in 0..count {
- sketch.update(start + i, 1u64);
- }
- sketch
-}
diff --git a/datasketches/tests/bloom_test/sketch.rs b/datasketches/tests/bloom_test/sketch.rs
new file mode 100644
index 0000000..7267607
--- /dev/null
+++ b/datasketches/tests/bloom_test/sketch.rs
@@ -0,0 +1,163 @@
+// 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::bloom::BloomFilterBuilder;
+
+const NUM_BITS: u64 = 65_536;
+const NUM_HASHES: u16 = 5;
+const SEED: u64 = 123;
+
+fn filter() -> datasketches::bloom::BloomFilter {
+ BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES)
+ .seed(SEED)
+ .build()
+}
+
+#[test]
+fn test_membership_statistics_and_reset() {
+ let mut filter = filter();
+ assert_eq!(filter.capacity(), NUM_BITS as usize);
+ assert_eq!(filter.num_hashes(), NUM_HASHES);
+ assert_eq!(filter.seed(), SEED);
+ assert!(filter.is_empty());
+ assert!(!filter.contains(&"apple"));
+
+ assert!(!filter.contains_and_insert(&"apple"));
+ assert!(filter.contains_and_insert(&"apple"));
+ assert!(filter.bits_used() > 0);
+ assert!(filter.load_factor() > 0.0);
+ assert!(filter.estimated_fpp() > 0.0);
+
+ filter.reset();
+ assert!(filter.is_empty());
+ assert_eq!(filter.bits_used(), 0);
+ assert!(!filter.contains(&"apple"));
+}
+
+#[test]
+fn test_union_and_intersection() {
+ let mut left = filter();
+ left.insert("shared");
+ left.insert("left");
+
+ let mut right = filter();
+ right.insert("shared");
+ right.insert("right");
+
+ let left_bits = left.bits_used();
+ let right_bits = right.bits_used();
+
+ let mut intersection = left.clone();
+ intersection.intersect(&right);
+ assert!(intersection.contains(&"shared"));
+ let intersection_bits = intersection.bits_used();
+ assert!(intersection_bits <= left_bits);
+ assert!(intersection_bits <= right_bits);
+
+ let mut union = left;
+ union.union(&right);
+ assert!(union.contains(&"shared"));
+ assert!(union.contains(&"left"));
+ assert!(union.contains(&"right"));
+ assert!(union.bits_used() >= left_bits);
+ assert!(union.bits_used() >= right_bits);
+}
+
+#[test]
+fn test_invert_is_reversible() {
+ let mut filter = filter();
+ filter.insert("apple");
+ filter.insert("banana");
+
+ let original = filter.clone();
+ let original_bits = filter.bits_used();
+ filter.invert();
+ assert_eq!(filter.bits_used(), filter.capacity() as u64 - original_bits);
+
+ filter.invert();
+ assert_eq!(filter, original);
+}
+
+#[test]
+fn test_compatibility_checks_all_configuration() {
+ let baseline = filter();
+ assert!(baseline.is_compatible(&filter()));
+
+ let different_seed = BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES)
+ .seed(SEED + 1)
+ .build();
+ let different_size = BloomFilterBuilder::with_size(NUM_BITS * 2, NUM_HASHES)
+ .seed(SEED)
+ .build();
+ let different_hashes = BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES + 1)
+ .seed(SEED)
+ .build();
+
+ assert!(!baseline.is_compatible(&different_seed));
+ assert!(!baseline.is_compatible(&different_size));
+ assert!(!baseline.is_compatible(&different_hashes));
+}
+
+#[test]
+#[should_panic(expected = "Cannot union incompatible Bloom filters")]
+fn test_union_rejects_incompatible_filters() {
+ let mut left = filter();
+ let right = BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES)
+ .seed(SEED + 1)
+ .build();
+ left.union(&right);
+}
+
+#[test]
+#[should_panic(expected = "Cannot intersect incompatible Bloom filters")]
+fn test_intersection_rejects_incompatible_filters() {
+ let mut left = filter();
+ let right = BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES)
+ .seed(SEED + 1)
+ .build();
+ left.intersect(&right);
+}
+
+#[test]
+fn test_requested_size_rounds_to_word_boundary() {
+ let filter = BloomFilterBuilder::with_size(65, 3).build();
+ assert_eq!(filter.capacity(), 128);
+}
+
+#[test]
+#[should_panic(expected = "max_items must be greater than 0")]
+fn test_accuracy_builder_rejects_zero_items() {
+ BloomFilterBuilder::with_accuracy(0, 0.01);
+}
+
+#[test]
+#[should_panic(expected = "fpp must be between")]
+fn test_accuracy_builder_rejects_invalid_probability() {
+ BloomFilterBuilder::with_accuracy(100, 1.5);
+}
+
+#[test]
+#[should_panic(expected = "num_bits must be between")]
+fn test_size_builder_rejects_zero_bits() {
+ BloomFilterBuilder::with_size(0, 3);
+}
+
+#[test]
+#[should_panic(expected = "num_hashes must be between")]
+fn test_size_builder_rejects_zero_hashes() {
+ BloomFilterBuilder::with_size(128, 0);
+}
diff --git a/datasketches/tests/cpc_test/union.rs b/datasketches/tests/cpc_test/union.rs
index 8f871ee..aaa5fa3 100644
--- a/datasketches/tests/cpc_test/union.rs
+++ b/datasketches/tests/cpc_test/union.rs
@@ -46,7 +46,7 @@ fn test_two_values() {
let result = union.to_sketch();
assert!(!result.is_empty());
assert_that!(
- sketch.estimate(),
+ result.estimate(),
near(2.0, RELATIVE_ERROR_FOR_LG_K_11 * 2.0)
);
}
@@ -140,7 +140,7 @@ fn test_reduce_k_sparse() {
assert_eq!(result.lg_k(), 11);
assert_that!(
result.estimate(),
- near(1000.0, RELATIVE_ERROR_FOR_LG_K_11 * 10000.0)
+ near(1000.0, RELATIVE_ERROR_FOR_LG_K_11 * 1000.0)
);
}
@@ -164,7 +164,7 @@ fn test_reduce_k_window() {
assert_eq!(result.lg_k(), 11);
assert_that!(
result.estimate(),
- near(1000.0, RELATIVE_ERROR_FOR_LG_K_11 * 10000.0)
+ near(1000.0, RELATIVE_ERROR_FOR_LG_K_11 * 1000.0)
);
}
diff --git a/datasketches/tests/serde_tests/theta.rs b/datasketches/tests/serde_tests/theta.rs
index a1206aa..b74cd44 100644
--- a/datasketches/tests/serde_tests/theta.rs
+++ b/datasketches/tests/serde_tests/theta.rs
@@ -18,7 +18,9 @@
use std::fs;
use std::path::PathBuf;
+use datasketches::error::ErrorKind;
use datasketches::theta::CompactThetaSketch;
+use datasketches::theta::ThetaSketchBuilder;
use googletest::assert_that;
use googletest::prelude::near;
@@ -113,3 +115,29 @@ fn test_cpp_compatibility() {
let path = serialization_test_data("cpp_generated_files", "theta_non_empty_no_entries_cpp.sk");
test_sketch_file(path, 0, false);
}
+
+#[test]
+fn malformed_input_is_rejected() {
+ let mut sketch = ThetaSketchBuilder::default().lg_k(5).build();
+ for value in 0..5000 {
+ sketch.update(value);
+ }
+ let bytes = sketch.compact(true).serialize();
+
+ let truncated = &bytes[..bytes.len() - 1];
+ let err = CompactThetaSketch::deserialize(truncated).unwrap_err();
+ assert_eq!(err.kind(), ErrorKind::InvalidData);
+
+ let err = CompactThetaSketch::deserialize_with_seed(&bytes, 8).unwrap_err();
+ assert_eq!(err.kind(), ErrorKind::InvalidData);
+
+ let mut wrong_family = bytes.clone();
+ wrong_family[2] = 0;
+ let err = CompactThetaSketch::deserialize(&wrong_family).unwrap_err();
+ assert_eq!(err.kind(), ErrorKind::InvalidData);
+
+ let mut unsupported_version = bytes;
+ unsupported_version[1] = 99;
+ let err = CompactThetaSketch::deserialize(&unsupported_version).unwrap_err();
+ assert_eq!(err.kind(), ErrorKind::InvalidData);
+}
diff --git a/datasketches/tests/serde_tests/tuple.rs b/datasketches/tests/serde_tests/tuple.rs
index 00a3ca2..03b0d7c 100644
--- a/datasketches/tests/serde_tests/tuple.rs
+++ b/datasketches/tests/serde_tests/tuple.rs
@@ -18,7 +18,10 @@
use std::fs;
use std::path::PathBuf;
+use datasketches::error::ErrorKind;
use datasketches::tuple::CompactTupleSketch;
+use datasketches::tuple::DefaultUpdatePolicy;
+use datasketches::tuple::TupleSketchBuilder;
use googletest::assert_that;
use googletest::prelude::near;
@@ -90,3 +93,39 @@ fn test_cpp_compatibility() {
test_sketch_file(path, n);
}
}
+
+#[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()).build();
+ for value in 0..100 {
+ sketch.update(value, 1);
+ }
+ let bytes = sketch.compact(true).serialize();
+
+ let truncated = &bytes[..bytes.len() - 4];
+ let err = CompactTupleSketch::<u64>::deserialize(truncated).unwrap_err();
+ assert_eq!(err.kind(), ErrorKind::InvalidData);
+
+ let err = CompactTupleSketch::<u64>::deserialize_with_seed(&bytes, 8).unwrap_err();
+ assert_eq!(err.kind(), ErrorKind::InvalidData);
+
+ let mut wrong_family = bytes;
+ wrong_family[2] = 0;
+ let err = CompactTupleSketch::<u64>::deserialize(&wrong_family).unwrap_err();
+ assert_eq!(err.kind(), ErrorKind::InvalidData);
+}
diff --git a/datasketches/tests/theta_test/sketch.rs b/datasketches/tests/theta_test/sketch.rs
index f99413d..3ce86f0 100644
--- a/datasketches/tests/theta_test/sketch.rs
+++ b/datasketches/tests/theta_test/sketch.rs
@@ -93,20 +93,27 @@ fn test_theta_reduction() {
#[test]
fn test_trim() {
+ let mut exact = ThetaSketchBuilder::default().lg_k(12).build();
let mut sketch = ThetaSketchBuilder::default().lg_k(5).build();
- // Insert many values
for i in 0..1000 {
- sketch.update(format!("value_{}", i));
+ exact.update(i);
+ sketch.update(i);
}
+ let mut expected_hashes: Vec<_> = exact.iter().map(|entry| entry.hash()).collect();
+ expected_hashes.sort_unstable();
+
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);
+ let mut retained_hashes: Vec<_> = sketch.iter().map(|entry| entry.hash()).collect();
+ retained_hashes.sort_unstable();
+
+ assert!(sketch.num_retained() <= before_trim);
assert_eq!(sketch.num_retained(), 32);
+ assert_eq!(retained_hashes, expected_hashes[..32]);
+ assert_eq!(sketch.theta64(), expected_hashes[32]);
}
#[test]
diff --git a/datasketches/tests/tuple_test/a_not_b.rs b/datasketches/tests/tuple_test/a_not_b.rs
index ac1d3a8..d0162be 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,144 @@ 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();
-
- // "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);
-}
-
-#[test]
-fn test_accepts_updatable_and_compact_inputs() {
- 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.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();
+ let result = TupleANotB::default().compute(&a, &b, true).unwrap();
- assert_eq!(r.num_retained(), 1000);
- assert_eq!(r.estimate(), 1000.0);
+ assert_eq!(result.num_retained(), 1);
+ assert_eq!(result.estimate(), 1.0);
+ assert_eq!(result.iter().next().unwrap().1, &5);
}
#[test]
-fn test_exact_partial_overlap_unordered() {
+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, &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 input_and_result_ordering_preserve_entries() {
+ 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 from_unordered_inputs = op.compute(&a, &b, true).unwrap();
+ let from_ordered_inputs = 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);
-}
-
-#[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);
+ let unordered_result = op.compute(&a, &b, false).unwrap();
+
+ assert!(from_unordered_inputs.is_ordered());
+ assert!(from_ordered_inputs.is_ordered());
+ assert!(!unordered_result.is_ordered());
+ assert_eq!(
+ from_unordered_inputs.theta64(),
+ from_ordered_inputs.theta64()
+ );
+ assert_eq!(from_unordered_inputs.theta64(), unordered_result.theta64());
+ assert_eq!(
+ sorted_entries(&from_unordered_inputs),
+ sorted_entries(&from_ordered_inputs)
+ );
+ assert_eq!(
+ sorted_entries(&from_unordered_inputs),
+ sorted_entries(&unordered_result)
+ );
}
#[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..a13d36a 100644
--- a/datasketches/tests/tuple_test/sketch.rs
+++ b/datasketches/tests/tuple_test/sketch.rs
@@ -17,284 +17,189 @@
use datasketches::common::NumStdDev;
use datasketches::hash_value;
+use datasketches::tuple::CompactTupleSketch;
+use datasketches::tuple::DefaultUpdatePolicy;
+use datasketches::tuple::SummaryPolicy;
+use datasketches::tuple::SummaryUpdatePolicy;
+use datasketches::tuple::TupleSketch;
+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();
-
- 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();
-
+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 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();
+fn default_update_policy_accepts_distinct_rhs_type() {
+ let mut sketch = TupleSketchBuilder::new(DefaultUpdatePolicy::<String>::default()).build();
+ sketch.update("key", "hello");
+ sketch.update("key", " world");
- for _ in 0..100 {
- sketch.update("same_value", 1u64);
- }
+ assert_eq!(sketch.iter().next().unwrap().1, "hello world");
+}
- assert_eq!(sketch.estimate(), 1.0);
+struct ArraySumPolicy {
+ num_values: usize,
}
-#[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());
+impl SummaryPolicy for ArraySumPolicy {
+ type Summary = Vec<f64>;
- // Insert many values to trigger theta reduction
- for i in 0..1000 {
- sketch.update(format!("value_{}", i), 1u64);
+ fn create(&self) -> Self::Summary {
+ vec![0.0; self.num_values]
}
-
- assert!(sketch.is_estimation_mode());
- assert!(sketch.theta() < 1.0);
}
-#[test]
-fn test_trim() {
- 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);
+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;
+ }
}
+}
- let before_trim = sketch.num_retained();
- sketch.trim();
- let after_trim = sketch.num_retained();
+#[test]
+fn custom_update_policy_accepts_multiple_value_representations() {
+ let mut sketch = TupleSketchBuilder::new(ArraySumPolicy { num_values: 2 }).build();
+ sketch.update("key", &[1.0, 2.0]);
+ sketch.update("key", vec![3.0, 4.0]);
- // After trim, should have approximately k entries
- assert!(after_trim <= before_trim);
- assert_eq!(sketch.num_retained(), 32);
+ assert_eq!(sketch.num_retained(), 1);
+ assert_eq!(sketch.iter().next().unwrap().1.as_slice(), [4.0, 6.0]);
}
#[test]
-fn test_reset() {
+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);
}
- assert!(!sketch.is_empty());
+
+ sketch.trim();
+ assert_eq!(sketch.num_retained(), 32);
assert!(sketch.is_estimation_mode());
- assert!(sketch.num_retained() > 32);
- assert!(sketch.theta() < 1.0);
sketch.reset();
assert!(sketch.is_empty());
+ assert_eq!(sketch.num_retained(), 0);
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);
+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);
- let count: usize = sketch.iter().count();
- assert_eq!(count, sketch.num_retained());
+ let mut estimated = default_tuple_sketch_builder().lg_k(8).build();
+ for value in 0..50_000 {
+ estimated.update(value, 1u64);
+ }
+ 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_sketch() {
- let sketch = default_tuple_sketch_builder().lg_k(12).build();
+fn empty_sampled_sketch_has_zero_bounds() {
+ let sketch = default_tuple_sketch_builder()
+ .sampling_probability(0.1)
+ .build();
+
assert!(sketch.is_empty());
- assert!(!sketch.is_estimation_mode());
- assert_eq!(sketch.theta(), 1.0);
+ 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::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);
+fn sorted_entries<'a>(entries: impl Iterator<Item = (u64, &'a u64)>) -> Vec<(u64, u64)> {
+ let mut entries: Vec<_> = entries.map(|(hash, &summary)| (hash, summary)).collect();
+ entries.sort_unstable();
+ entries
}
-#[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
+fn assert_compact_preserves_state(
+ updatable: &TupleSketch<DefaultUpdatePolicy<u64>>,
+ compact: &CompactTupleSketch<u64>,
+ ordered: bool,
+) {
+ assert_eq!(compact.is_estimation_mode(), updatable.is_estimation_mode());
+ assert_eq!(compact.theta64(), updatable.theta64());
+ assert_eq!(compact.seed_hash(), updatable.seed_hash());
+ assert_eq!(
+ sorted_entries(compact.iter()),
+ sorted_entries(updatable.iter())
);
-
- // 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_eq!(compact.estimate(), updatable.estimate());
+ assert_eq!(compact.is_ordered(), ordered);
}
#[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 compact_preserves_state_in_exact_and_estimation_modes() {
+ for (lg_k, num_updates, expected_estimation_mode) in [(12, 2_000, false), (5, 5_000, true)] {
+ let mut sketch = default_tuple_sketch_builder().lg_k(lg_k).build();
+ for key in 0..num_updates {
+ sketch.update(key, key + 1);
+ sketch.update(key, 10u64);
+ }
+ assert_eq!(sketch.is_estimation_mode(), expected_estimation_mode);
+
+ for ordered in [false, true] {
+ let compact = sketch.compact(ordered);
+ assert_compact_preserves_state(&sketch, &compact, ordered);
+ }
}
-
- 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 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);
-}
-
-#[test]
-fn test_bounds_empty_estimation_mode() {
- // Create a sketch with sampling probability < 1.0 to force estimation mode
- 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);
-}
-
-#[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 +208,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}]"
+ );
+}
diff --git a/xtask/src/main.rs b/xtask/src/main.rs
index da33cd0..14f5478 100644
--- a/xtask/src/main.rs
+++ b/xtask/src/main.rs
@@ -46,7 +46,7 @@ enum SubCommand {
Docs(CommandDocs),
#[clap(about = "Run linter checks.")]
Lint(CommandLint),
- #[clap(about = "Run unit tests.")]
+ #[clap(about = "Run the test suite.")]
Test(CommandTest),
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org