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/25 09:11:55 UTC
(datasketches-rust) branch main updated: feat: add theta and tuple a-not-B operation (#155)
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 87e9e84 feat: add theta and tuple a-not-B operation (#155)
87e9e84 is described below
commit 87e9e84133dc2ba6ff5a94e164adf430507d82c0
Author: Yijun Zhao <ar...@gmail.com>
AuthorDate: Sat Jul 25 17:11:49 2026 +0800
feat: add theta and tuple a-not-B operation (#155)
---
datasketches/src/theta/a_not_b.rs | 95 +++++++
datasketches/src/theta/mod.rs | 2 +
datasketches/src/thetacommon/a_not_b.rs | 184 +++++++++++++
datasketches/src/thetacommon/mod.rs | 1 +
datasketches/src/tuple/a_not_b.rs | 361 ++++++++++++++++++++++++++
datasketches/src/tuple/mod.rs | 2 +
datasketches/tests/common.rs | 26 ++
datasketches/tests/theta_a_not_b_test.rs | 246 ++++++++++++++++++
datasketches/tests/tuple_a_not_b_test.rs | 246 ++++++++++++++++++
datasketches/tests/tuple_intersection_test.rs | 82 +++---
datasketches/tests/tuple_sketch_test.rs | 42 ++-
11 files changed, 1220 insertions(+), 67 deletions(-)
diff --git a/datasketches/src/theta/a_not_b.rs b/datasketches/src/theta/a_not_b.rs
new file mode 100644
index 0000000..245bb39
--- /dev/null
+++ b/datasketches/src/theta/a_not_b.rs
@@ -0,0 +1,95 @@
+// 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.
+
+//! Theta sketch set difference (`A and not B`).
+//!
+//! [`ThetaAnotB`] computes the set difference of two Theta sketches: the keys retained in `A`
+//! that are not present in `B`. The logic lives in the shared raw operator (`RawAnotB`) that also
+//! drives the Tuple a-not-B; Theta entries carry no summary, so nothing needs to be combined.
+
+use crate::error::Error;
+use crate::hash::DEFAULT_UPDATE_SEED;
+use crate::theta::CompactThetaSketch;
+use crate::theta::ThetaSketchView;
+use crate::thetacommon::a_not_b::RawAnotB;
+
+/// Set difference operator (`A and not B`) for Theta sketches.
+///
+/// This is a stateless operator (other than the seed): each call to [`compute`](Self::compute)
+/// takes two input sketches and returns a new [`CompactThetaSketch`].
+///
+/// # Examples
+///
+/// ```
+/// # use datasketches::theta::{ThetaAnotB, ThetaSketchBuilder};
+/// let mut a = ThetaSketchBuilder::default().build();
+/// a.update("apple");
+/// a.update("banana");
+///
+/// let mut b = ThetaSketchBuilder::default().build();
+/// b.update("banana");
+///
+/// let a_not_b = ThetaAnotB::new_with_default_seed();
+/// let result = a_not_b.compute(&a, &b, true).unwrap();
+/// assert_eq!(result.num_retained(), 1); // only "apple" survives
+/// ```
+#[derive(Debug, Clone, Copy)]
+pub struct ThetaAnotB {
+ raw: RawAnotB,
+}
+
+impl ThetaAnotB {
+ /// Creates a new set difference operator for the given `seed`.
+ pub fn new(seed: u64) -> Self {
+ Self {
+ raw: RawAnotB::new(seed),
+ }
+ }
+
+ /// Creates a new set difference operator with the default seed.
+ pub fn new_with_default_seed() -> Self {
+ Self::new(DEFAULT_UPDATE_SEED)
+ }
+
+ /// Computes `a and not b`.
+ ///
+ /// The result retains every key of `a` (below the combined theta) that is not present in `b`.
+ /// If `ordered` is true, the retained entries are sorted ascending by hash.
+ ///
+ /// # Errors
+ ///
+ /// Returns an error if either non-trivial input has a seed hash that differs from this
+ /// operator's seed.
+ pub fn compute<A, B>(&self, a: &A, b: &B, ordered: bool) -> Result<CompactThetaSketch, Error>
+ where
+ A: ThetaSketchView,
+ B: ThetaSketchView,
+ {
+ let parts = self.raw.compute(a, b, ordered)?;
+ Ok(CompactThetaSketch::from_parts(
+ parts
+ .entries
+ .into_iter()
+ .map(|entry| entry.hash())
+ .collect(),
+ parts.theta,
+ parts.seed_hash,
+ parts.ordered,
+ parts.empty,
+ ))
+ }
+}
diff --git a/datasketches/src/theta/mod.rs b/datasketches/src/theta/mod.rs
index 0178f34..596f85e 100644
--- a/datasketches/src/theta/mod.rs
+++ b/datasketches/src/theta/mod.rs
@@ -39,6 +39,7 @@
//! assert!(sketch.estimate() >= 1.0);
//! ```
+mod a_not_b;
mod bit_pack;
mod hash_table;
mod intersection;
@@ -46,6 +47,7 @@ mod serialization;
mod sketch;
mod union;
+pub use self::a_not_b::ThetaAnotB;
pub use self::hash_table::ThetaEntry;
pub use self::intersection::ThetaIntersection;
pub use self::sketch::CompactThetaSketch;
diff --git a/datasketches/src/thetacommon/a_not_b.rs b/datasketches/src/thetacommon/a_not_b.rs
new file mode 100644
index 0000000..937f69e
--- /dev/null
+++ b/datasketches/src/thetacommon/a_not_b.rs
@@ -0,0 +1,184 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::collections::HashSet;
+
+use crate::error::Error;
+use crate::hash::compute_seed_hash;
+use crate::thetacommon::RawHashTableEntry;
+use crate::thetacommon::RawThetaSketchView;
+use crate::thetacommon::constants::MAX_THETA;
+use crate::thetacommon::hash_table::RawCompactParts;
+
+/// Stateless set difference (`A and not B`) operator shared by Theta and Tuple sketches.
+///
+/// `E` is the retained entry type. Ordinary Theta entries only contain a hash, while tuple
+/// entries also carry a summary. Surviving entries are moved from `A` unchanged, so unlike the
+/// union and intersection this operation needs no entry-merge policy.
+#[derive(Debug, Clone, Copy)]
+pub struct RawAnotB {
+ seed_hash: u16,
+}
+
+impl RawAnotB {
+ /// Creates a new set difference operator for the given `seed`.
+ pub fn new(seed: u64) -> Self {
+ Self {
+ seed_hash: compute_seed_hash(seed),
+ }
+ }
+
+ /// Computes `a and not b`.
+ ///
+ /// The result retains every entry of `a` (below the combined theta) whose hash is not present
+ /// in `b`. If `ordered` is true, the retained entries are sorted ascending by hash.
+ ///
+ /// # Errors
+ ///
+ /// Returns an error if either non-trivial input has a seed hash that differs from this
+ /// operator's seed.
+ pub fn compute<E, A, B>(&self, a: &A, b: &B, ordered: bool) -> Result<RawCompactParts<E>, Error>
+ where
+ E: RawHashTableEntry,
+ A: RawThetaSketchView<E>,
+ B: RawThetaSketchView<E>,
+ {
+ // If A is empty the result is an (empty) copy of A. As with the union and intersection, an
+ // empty input carries no keys, so its seed is not validated.
+ if a.is_empty() {
+ return Ok(Self::parts_from_view(a, ordered));
+ }
+
+ // A is non-empty, so its seed must be compatible.
+ if a.seed_hash() != self.seed_hash {
+ return Err(Error::invalid_argument(format!(
+ "A seed hash mismatch: expected {}, got {}",
+ self.seed_hash,
+ a.seed_hash()
+ )));
+ }
+
+ // An empty B subtracts nothing, so the result is simply a copy of A. This also covers the
+ // "A is non-empty but has no retained keys" state: B's seed and theta must not influence
+ // the result, so we return before touching them.
+ if b.is_empty() {
+ return Ok(Self::parts_from_view(a, ordered));
+ }
+
+ // B is non-empty, so its seed must be compatible.
+ if b.seed_hash() != self.seed_hash {
+ return Err(Error::invalid_argument(format!(
+ "B seed hash mismatch: expected {}, got {}",
+ self.seed_hash,
+ b.seed_hash()
+ )));
+ }
+
+ let theta = a.theta().min(b.theta());
+ // A is non-empty here; the result only becomes empty if everything is subtracted in exact
+ // mode (handled below).
+ let mut is_empty = false;
+
+ let entries: Vec<E> = if b.num_retained() == 0 {
+ a.iter().filter(|entry| entry.hash() < theta).collect()
+ } else if a.is_ordered() && b.is_ordered() {
+ // Both inputs are sorted ascending by hash: merge-scan without a hash set. Only
+ // b hashes below theta can exclude an a entry (a entries are all < theta), so
+ // unexamined b entries at or above theta are harmless.
+ let mut b_hashes = b.iter().map(|entry| entry.hash()).peekable();
+ let mut entries = Vec::new();
+ for entry in a.iter() {
+ let hash = entry.hash();
+ if hash >= theta {
+ break;
+ }
+ while let Some(&b_hash) = b_hashes.peek() {
+ if b_hash < hash {
+ b_hashes.next();
+ } else {
+ break;
+ }
+ }
+ if b_hashes.peek() != Some(&hash) {
+ entries.push(entry);
+ }
+ }
+ entries
+ } else {
+ let mut b_keys: HashSet<u64> = HashSet::with_capacity(b.num_retained());
+ for entry in b.iter() {
+ let hash = entry.hash();
+ if hash < theta {
+ b_keys.insert(hash);
+ } else if b.is_ordered() {
+ break;
+ }
+ }
+
+ let mut entries = Vec::new();
+ for entry in a.iter() {
+ let hash = entry.hash();
+ if hash < theta {
+ if !b_keys.contains(&hash) {
+ entries.push(entry);
+ }
+ } else if a.is_ordered() {
+ break;
+ }
+ }
+ entries
+ };
+
+ if entries.is_empty() && theta == MAX_THETA {
+ is_empty = true;
+ }
+
+ let out_ordered = ordered || a.is_ordered();
+ let mut entries = entries;
+ if ordered && !a.is_ordered() && entries.len() > 1 {
+ entries.sort_unstable_by_key(RawHashTableEntry::hash);
+ }
+
+ Ok(RawCompactParts {
+ entries,
+ theta,
+ seed_hash: self.seed_hash,
+ ordered: out_ordered,
+ empty: is_empty,
+ })
+ }
+
+ /// Builds compact parts that are a copy of the view `a`.
+ fn parts_from_view<E, V>(a: &V, ordered: bool) -> RawCompactParts<E>
+ where
+ E: RawHashTableEntry,
+ V: RawThetaSketchView<E>,
+ {
+ let mut entries: Vec<E> = a.iter().collect();
+ let out_ordered = ordered || a.is_ordered();
+ if ordered && !a.is_ordered() && entries.len() > 1 {
+ entries.sort_unstable_by_key(RawHashTableEntry::hash);
+ }
+ RawCompactParts {
+ entries,
+ theta: a.theta(),
+ seed_hash: a.seed_hash(),
+ ordered: out_ordered,
+ empty: a.is_empty(),
+ }
+ }
+}
diff --git a/datasketches/src/thetacommon/mod.rs b/datasketches/src/thetacommon/mod.rs
index 11c9346..2bd279e 100644
--- a/datasketches/src/thetacommon/mod.rs
+++ b/datasketches/src/thetacommon/mod.rs
@@ -17,6 +17,7 @@
//! Data structures and functions that may be used across all the Theta sketch family.
+pub(crate) mod a_not_b;
pub(crate) mod binomial_bounds;
pub(crate) mod constants;
pub(crate) mod hash_table;
diff --git a/datasketches/src/tuple/a_not_b.rs b/datasketches/src/tuple/a_not_b.rs
new file mode 100644
index 0000000..b113280
--- /dev/null
+++ b/datasketches/src/tuple/a_not_b.rs
@@ -0,0 +1,361 @@
+// 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.
+
+//! Tuple sketch set difference (`A and not B`).
+//!
+//! [`TupleAnotB`] computes the set difference of two Tuple sketches: the keys retained in `A` that
+//! are not present in `B`. Surviving keys keep their summaries from `A` unchanged, so unlike the
+//! union and intersection this operation needs no combine policy. The logic lives in the shared
+//! raw operator (`RawAnotB`) that also drives the Theta a-not-B.
+
+use crate::error::Error;
+use crate::hash::DEFAULT_UPDATE_SEED;
+use crate::thetacommon::a_not_b::RawAnotB;
+use crate::tuple::sketch::CompactTupleSketch;
+use crate::tuple::sketch::TupleSketchView;
+
+/// Set difference operator (`A and not B`) for Tuple sketches.
+///
+/// This is a stateless operator (other than the seed): each call to [`compute`](Self::compute)
+/// takes two input sketches and returns a new [`CompactTupleSketch`]. Surviving keys carry their
+/// summaries straight from `A`.
+///
+/// # Examples
+///
+/// ```
+/// # use datasketches::tuple::{DefaultUpdatePolicy, TupleAnotB, TupleSketchBuilder};
+/// let update_policy = DefaultUpdatePolicy::<u64>::default();
+/// let mut a = TupleSketchBuilder::new(update_policy).build();
+/// a.update("apple", 1);
+/// a.update("banana", 1);
+///
+/// let mut b = TupleSketchBuilder::new(update_policy).build();
+/// b.update("banana", 1);
+///
+/// let a_not_b = TupleAnotB::new_with_default_seed();
+/// let result = a_not_b.compute(&a, &b, true).unwrap();
+/// assert_eq!(result.num_retained(), 1); // only "apple" survives
+/// ```
+#[derive(Debug, Clone, Copy)]
+pub struct TupleAnotB {
+ raw: RawAnotB,
+}
+
+impl TupleAnotB {
+ /// Creates a new set difference operator for the given `seed`.
+ pub fn new(seed: u64) -> Self {
+ Self {
+ raw: RawAnotB::new(seed),
+ }
+ }
+
+ /// Creates a new set difference operator with the default seed.
+ pub fn new_with_default_seed() -> Self {
+ Self::new(DEFAULT_UPDATE_SEED)
+ }
+
+ /// Computes `a and not b`.
+ ///
+ /// The result retains every key of `a` (below the combined theta) that is not present in `b`,
+ /// keeping the summaries from `a`. If `ordered` is true, the retained entries are sorted
+ /// ascending by hash.
+ ///
+ /// # Errors
+ ///
+ /// Returns an error if either non-trivial input has a seed hash that differs from this
+ /// operator's seed.
+ pub fn compute<S, A, B>(
+ &self,
+ a: &A,
+ b: &B,
+ ordered: bool,
+ ) -> Result<CompactTupleSketch<S>, Error>
+ where
+ A: TupleSketchView<S>,
+ B: TupleSketchView<S>,
+ {
+ let parts = self.raw.compute(a, b, ordered)?;
+ Ok(CompactTupleSketch::from_parts(
+ parts.entries,
+ parts.theta,
+ parts.seed_hash,
+ parts.ordered,
+ parts.empty,
+ ))
+ }
+}
+
+#[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::new_with_default_seed()
+ .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::new_with_default_seed()
+ .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::new_with_default_seed()
+ .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::new_with_default_seed()
+ .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::new_with_default_seed()
+ .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::new_with_default_seed()
+ .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::new_with_default_seed()
+ .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::new_with_default_seed()
+ .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::new_with_default_seed();
+ 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::new_with_default_seed()
+ .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::new(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::new(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::new_with_default_seed()
+ .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::new_with_default_seed()
+ .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/mod.rs b/datasketches/src/tuple/mod.rs
index 6701f42..ffa4603 100644
--- a/datasketches/src/tuple/mod.rs
+++ b/datasketches/src/tuple/mod.rs
@@ -38,6 +38,7 @@
//! assert!(sketch.estimate() >= 1.0);
//! ```
+mod a_not_b;
mod hash_table;
mod intersection;
mod policy;
@@ -45,6 +46,7 @@ mod serialization;
mod sketch;
mod union;
+pub use self::a_not_b::TupleAnotB;
pub use self::hash_table::TupleEntry;
pub use self::intersection::TupleIntersection;
pub use self::policy::DefaultUnionPolicy;
diff --git a/datasketches/tests/common.rs b/datasketches/tests/common.rs
index ca26fe6..348f156 100644
--- a/datasketches/tests/common.rs
+++ b/datasketches/tests/common.rs
@@ -17,6 +17,13 @@
use std::path::PathBuf;
+#[cfg(feature = "tuple")]
+use datasketches::tuple::DefaultUpdatePolicy;
+#[cfg(feature = "tuple")]
+use datasketches::tuple::TupleSketch;
+#[cfg(feature = "tuple")]
+use datasketches::tuple::TupleSketchBuilder;
+
#[allow(dead_code)] // false-positive
pub fn test_data(name: &str) -> PathBuf {
const TEST_DATA_DIR: &str = "tests/test_data";
@@ -26,6 +33,7 @@ pub fn test_data(name: &str) -> PathBuf {
.join(name)
}
+#[allow(dead_code)] // not every test target uses all helpers
pub fn serialization_test_data(sub_dir: &str, name: &str) -> PathBuf {
const SERDE_TEST_DATA_DIR: &str = "tests/serialization_test_data";
@@ -50,3 +58,21 @@ pub fn serialization_test_data(sub_dir: &str, name: &str) -> PathBuf {
path
}
+
+/// Returns a tuple sketch builder with the default additive `u64` summary policy.
+#[cfg(feature = "tuple")]
+#[allow(dead_code)] // not every test target uses all helpers
+pub fn default_tuple_sketch_builder() -> TupleSketchBuilder<DefaultUpdatePolicy<u64>> {
+ TupleSketchBuilder::new(DefaultUpdatePolicy::<u64>::default())
+}
+
+/// Builds a tuple sketch updated with keys `start..start + count`, each with summary 1.
+#[cfg(feature = "tuple")]
+#[allow(dead_code)] // not every test target uses all helpers
+pub 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/theta_a_not_b_test.rs b/datasketches/tests/theta_a_not_b_test.rs
new file mode 100644
index 0000000..2570398
--- /dev/null
+++ b/datasketches/tests/theta_a_not_b_test.rs
@@ -0,0 +1,246 @@
+// 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.
+
+//! Behavioral tests for the Theta a-not-B (set difference) operator, mirroring
+//! `theta_intersection_test.rs`.
+//!
+//! The result of `a and not b` retains the keys of `a` that are absent from `b`.
+
+#![cfg(feature = "theta")]
+
+use datasketches::theta::CompactThetaSketch;
+use datasketches::theta::ThetaAnotB;
+use datasketches::theta::ThetaSketch;
+use datasketches::theta::ThetaSketchBuilder;
+
+fn sketch_with_range(start: u64, count: u64) -> ThetaSketch {
+ let mut sketch = ThetaSketchBuilder::default().build();
+ for i in 0..count {
+ sketch.update(start + i);
+ }
+ sketch
+}
+
+#[test]
+fn test_basic_difference() {
+ let mut a = ThetaSketchBuilder::default().build();
+ a.update("shared");
+ a.update("only_a");
+ let mut b = ThetaSketchBuilder::default().build();
+ b.update("shared");
+ b.update("only_b");
+
+ let a_not_b = ThetaAnotB::new_with_default_seed();
+ let r = a_not_b.compute(&a, &b, true).unwrap();
+
+ // "shared" is subtracted; only "only_a" survives.
+ assert_eq!(r.num_retained(), 1);
+ assert!(!r.is_estimation_mode());
+ assert_eq!(r.estimate(), 1.0);
+}
+
+#[test]
+fn test_accepts_updatable_and_compact_inputs() {
+ let a = sketch_with_range(0, 1000);
+ let b = sketch_with_range(500, 1000);
+
+ let a_not_b = ThetaAnotB::new_with_default_seed();
+ 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 = ThetaSketchBuilder::default().seed(2).build();
+ one_other_seed.update("value");
+ let good = sketch_with_range(0, 10);
+
+ let a_not_b = ThetaAnotB::new(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 = ThetaSketchBuilder::default().seed(2).build();
+ let good = sketch_with_range(0, 10);
+
+ let a_not_b = ThetaAnotB::new_with_default_seed();
+
+ 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 = ThetaSketchBuilder::default().build();
+ let b = sketch_with_range(0, 1000);
+
+ let a_not_b = ThetaAnotB::new_with_default_seed();
+ 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 = sketch_with_range(0, 1000);
+ let empty = ThetaSketchBuilder::default().build();
+
+ let a_not_b = ThetaAnotB::new_with_default_seed();
+ let r = a_not_b.compute(&a, &empty, true).unwrap();
+
+ assert_eq!(r.num_retained(), 1000);
+ assert_eq!(r.estimate(), 1000.0);
+}
+
+#[test]
+fn test_exact_partial_overlap_unordered() {
+ let a = sketch_with_range(0, 1000);
+ let b = sketch_with_range(500, 1000);
+
+ let a_not_b = ThetaAnotB::new_with_default_seed();
+ let r = a_not_b.compute(&a, &b, 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);
+}
+
+#[test]
+fn test_exact_partial_overlap_ordered() {
+ let a = sketch_with_range(0, 1000);
+ let b = sketch_with_range(500, 1000);
+
+ let a_not_b = ThetaAnotB::new_with_default_seed();
+ let r = a_not_b
+ .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 = sketch_with_range(0, 1000);
+ let b = sketch_with_range(1000, 1000);
+
+ let a_not_b = ThetaAnotB::new_with_default_seed();
+ let r = a_not_b.compute(&a, &b, true).unwrap();
+
+ assert!(!r.is_estimation_mode());
+ assert_eq!(r.num_retained(), 1000);
+ assert_eq!(r.estimate(), 1000.0);
+}
+
+#[test]
+fn test_exact_superset_b_returns_empty() {
+ let a = sketch_with_range(0, 1000);
+ let b = sketch_with_range(0, 2000);
+
+ let a_not_b = ThetaAnotB::new_with_default_seed();
+ 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);
+}
+
+#[test]
+fn test_result_ordering() {
+ let a = sketch_with_range(0, 64);
+ let empty = ThetaSketchBuilder::default().build();
+
+ let a_not_b = ThetaAnotB::new_with_default_seed();
+
+ 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 = sketch_with_range(0, 10000);
+ let b = sketch_with_range(5000, 10000);
+
+ let a_not_b = ThetaAnotB::new_with_default_seed();
+ 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 = sketch_with_range(0, 10000);
+ let b = sketch_with_range(5000, 10000);
+
+ let a_not_b = ThetaAnotB::new_with_default_seed();
+ let r = a_not_b
+ .compute(&a.compact(true), &b.compact(true), true)
+ .unwrap();
+
+ 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_deserialized_compact() {
+ let a = sketch_with_range(0, 10000);
+ let b = sketch_with_range(5000, 10000);
+ let c1 = CompactThetaSketch::deserialize(&a.compact(true).serialize()).unwrap();
+ let c2 = CompactThetaSketch::deserialize(&b.compact(true).serialize()).unwrap();
+
+ let a_not_b = ThetaAnotB::new_with_default_seed();
+ 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);
+}
+
+#[test]
+fn test_estimation_disjoint_returns_a() {
+ let a = sketch_with_range(0, 10000);
+ let b = sketch_with_range(10000, 10000);
+
+ let a_not_b = ThetaAnotB::new_with_default_seed();
+ let r = a_not_b.compute(&a, &b, true).unwrap();
+
+ assert!(!r.is_empty());
+ assert!(r.is_estimation_mode());
+ assert!((r.estimate() - 10000.0).abs() <= 10000.0 * 0.02);
+}
diff --git a/datasketches/tests/tuple_a_not_b_test.rs b/datasketches/tests/tuple_a_not_b_test.rs
new file mode 100644
index 0000000..4c35799
--- /dev/null
+++ b/datasketches/tests/tuple_a_not_b_test.rs
@@ -0,0 +1,246 @@
+// 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.
+
+//! 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.
+
+#![cfg(feature = "tuple")]
+
+mod common;
+
+use datasketches::tuple::CompactTupleSketch;
+use datasketches::tuple::TupleAnotB;
+
+use crate::common::default_tuple_sketch_builder;
+use crate::common::tuple_sketch_with_range;
+
+#[test]
+fn test_basic_difference_keeps_summaries_from_a() {
+ let mut a = default_tuple_sketch_builder().build();
+ a.update("shared", 3u64);
+ a.update("only_a", 5u64);
+ let mut b = default_tuple_sketch_builder().build();
+ b.update("shared", 9u64);
+ b.update("only_b", 7u64);
+
+ let a_not_b = TupleAnotB::new_with_default_seed();
+ 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::new_with_default_seed();
+ 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::new(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::new_with_default_seed();
+
+ 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::new_with_default_seed();
+ 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::new_with_default_seed();
+ let r = a_not_b.compute(&a, &empty, true).unwrap();
+
+ assert_eq!(r.num_retained(), 1000);
+ assert_eq!(r.estimate(), 1000.0);
+}
+
+#[test]
+fn test_exact_partial_overlap_unordered() {
+ let a = tuple_sketch_with_range(0, 1000);
+ let b = tuple_sketch_with_range(500, 1000);
+
+ let a_not_b = TupleAnotB::new_with_default_seed();
+ let r = a_not_b.compute(&a, &b, 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);
+}
+
+#[test]
+fn test_exact_partial_overlap_ordered() {
+ let a = tuple_sketch_with_range(0, 1000);
+ let b = tuple_sketch_with_range(500, 1000);
+
+ let a_not_b = TupleAnotB::new_with_default_seed();
+ let r = a_not_b
+ .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::new_with_default_seed();
+ let r = a_not_b.compute(&a, &b, true).unwrap();
+
+ assert!(!r.is_estimation_mode());
+ assert_eq!(r.num_retained(), 1000);
+ assert_eq!(r.estimate(), 1000.0);
+}
+
+#[test]
+fn test_exact_superset_b_returns_empty() {
+ let a = tuple_sketch_with_range(0, 1000);
+ let b = tuple_sketch_with_range(0, 2000);
+
+ let a_not_b = TupleAnotB::new_with_default_seed();
+ 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);
+}
+
+#[test]
+fn test_result_ordering() {
+ let mut a = default_tuple_sketch_builder().build();
+ for i in 0..64 {
+ a.update(i, 1u64);
+ }
+ let empty = default_tuple_sketch_builder().build();
+
+ let a_not_b = TupleAnotB::new_with_default_seed();
+
+ 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::new_with_default_seed();
+ 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::new_with_default_seed();
+ let r = a_not_b
+ .compute(&a.compact(true), &b.compact(true), true)
+ .unwrap();
+
+ 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_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::new_with_default_seed();
+ 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);
+}
+
+#[test]
+fn test_estimation_disjoint_returns_a() {
+ let a = tuple_sketch_with_range(0, 10000);
+ let b = tuple_sketch_with_range(10000, 10000);
+
+ let a_not_b = TupleAnotB::new_with_default_seed();
+ let r = a_not_b.compute(&a, &b, true).unwrap();
+
+ assert!(!r.is_empty());
+ assert!(r.is_estimation_mode());
+ assert!((r.estimate() - 10000.0).abs() <= 10000.0 * 0.02);
+}
diff --git a/datasketches/tests/tuple_intersection_test.rs b/datasketches/tests/tuple_intersection_test.rs
index 9407a88..1608074 100644
--- a/datasketches/tests/tuple_intersection_test.rs
+++ b/datasketches/tests/tuple_intersection_test.rs
@@ -17,13 +17,15 @@
#![cfg(feature = "tuple")]
+mod common;
+
use datasketches::tuple::CompactTupleSketch;
-use datasketches::tuple::DefaultUpdatePolicy;
use datasketches::tuple::SummaryCombinePolicy;
use datasketches::tuple::SummaryPolicy;
use datasketches::tuple::TupleIntersection;
-use datasketches::tuple::TupleSketch;
-use datasketches::tuple::TupleSketchBuilder;
+
+use crate::common::default_tuple_sketch_builder;
+use crate::common::tuple_sketch_with_range;
#[derive(Debug, Default, Clone, Copy)]
struct SumPolicy;
@@ -42,21 +44,9 @@ impl SummaryCombinePolicy for SumPolicy {
}
}
-fn default_sketch_builder() -> TupleSketchBuilder<DefaultUpdatePolicy<u64>> {
- TupleSketchBuilder::new(DefaultUpdatePolicy::<u64>::default())
-}
-
-fn sketch_with_range(start: u64, count: u64) -> TupleSketch<DefaultUpdatePolicy<u64>> {
- let mut sketch = default_sketch_builder().build();
- for i in 0..count {
- sketch.update(start + i, 1u64);
- }
- sketch
-}
-
#[test]
fn test_has_result_state_machine() {
- let mut a = default_sketch_builder().build();
+ let mut a = default_tuple_sketch_builder().build();
a.update("x", 1u64);
let mut i = TupleIntersection::new_with_default_seed(SumPolicy);
@@ -77,11 +67,11 @@ fn test_result_before_update_panics() {
#[test]
fn test_update_accepts_compact_sketch() {
- let mut a = default_sketch_builder().build();
+ let mut a = default_tuple_sketch_builder().build();
a.update("x", 1u64);
a.update("y", 1u64);
- let mut b = default_sketch_builder().build();
+ let mut b = default_tuple_sketch_builder().build();
b.update("y", 1u64);
b.update("z", 1u64);
@@ -93,7 +83,7 @@ fn test_update_accepts_compact_sketch() {
assert!(r.estimate() == 1.0);
assert!(r.is_ordered());
- let mut c = default_sketch_builder().build();
+ let mut c = default_tuple_sketch_builder().build();
c.update("a", 1u64);
c.update("b", 1u64);
c.update("c", 1u64);
@@ -107,7 +97,7 @@ fn test_update_accepts_compact_sketch() {
#[test]
fn test_seed_mismatch_behaviour_for_empty_sketch() {
- let empty_other_seed = default_sketch_builder().seed(2).build();
+ let empty_other_seed = default_tuple_sketch_builder().seed(2).build();
let mut i = TupleIntersection::new(1, SumPolicy);
i.update(&empty_other_seed).unwrap();
@@ -118,7 +108,7 @@ fn test_seed_mismatch_behaviour_for_empty_sketch() {
#[test]
fn test_seed_mismatch_behaviour() {
- let mut one_other_seed = default_sketch_builder().seed(2).build();
+ let mut one_other_seed = default_tuple_sketch_builder().seed(2).build();
one_other_seed.update("value", 1u64);
let mut i = TupleIntersection::new(1, SumPolicy);
@@ -127,9 +117,9 @@ fn test_seed_mismatch_behaviour() {
#[test]
fn test_terminal_empty_state_ignores_future_updates() {
- let empty = default_sketch_builder().build();
+ let empty = default_tuple_sketch_builder().build();
- let mut non_empty = default_sketch_builder().build();
+ let mut non_empty = default_tuple_sketch_builder().build();
non_empty.update("x", 1u64);
let mut i = TupleIntersection::new_with_default_seed(SumPolicy);
@@ -142,7 +132,7 @@ fn test_terminal_empty_state_ignores_future_updates() {
#[test]
fn test_to_sketch_unordered_is_not_ordered() {
- let mut a = default_sketch_builder().build();
+ let mut a = default_tuple_sketch_builder().build();
for i in 0..64 {
a.update(i, 1u64);
}
@@ -155,7 +145,7 @@ fn test_to_sketch_unordered_is_not_ordered() {
#[test]
fn test_empty_update_twice() {
- let empty = default_sketch_builder().build();
+ let empty = default_tuple_sketch_builder().build();
let mut i = TupleIntersection::new_with_default_seed(SumPolicy);
i.update(&empty).unwrap();
@@ -175,7 +165,9 @@ fn test_empty_update_twice() {
#[test]
fn test_non_empty_no_retained_keys() {
- let mut s = default_sketch_builder().sampling_probability(0.001).build();
+ let mut s = default_tuple_sketch_builder()
+ .sampling_probability(0.001)
+ .build();
s.update(1u64, 1u64);
let mut i = TupleIntersection::new_with_default_seed(SumPolicy);
@@ -198,8 +190,8 @@ fn test_non_empty_no_retained_keys() {
#[test]
fn test_exact_half_overlap_unordered() {
- let s1 = sketch_with_range(0, 1000);
- let s2 = sketch_with_range(500, 1000);
+ let s1 = tuple_sketch_with_range(0, 1000);
+ let s2 = tuple_sketch_with_range(500, 1000);
let mut i = TupleIntersection::new_with_default_seed(SumPolicy);
i.update(&s1).unwrap();
@@ -213,8 +205,8 @@ fn test_exact_half_overlap_unordered() {
#[test]
fn test_exact_half_overlap_ordered() {
- let s1 = sketch_with_range(0, 1000);
- let s2 = sketch_with_range(500, 1000);
+ let s1 = tuple_sketch_with_range(0, 1000);
+ let s2 = tuple_sketch_with_range(500, 1000);
let mut i = TupleIntersection::new_with_default_seed(SumPolicy);
i.update(&s1.compact(true)).unwrap();
@@ -228,8 +220,8 @@ fn test_exact_half_overlap_ordered() {
#[test]
fn test_exact_disjoint_unordered() {
- let s1 = sketch_with_range(0, 1000);
- let s2 = sketch_with_range(1000, 1000);
+ let s1 = tuple_sketch_with_range(0, 1000);
+ let s2 = tuple_sketch_with_range(1000, 1000);
let mut i = TupleIntersection::new_with_default_seed(SumPolicy);
i.update(&s1).unwrap();
@@ -243,8 +235,8 @@ fn test_exact_disjoint_unordered() {
#[test]
fn test_exact_disjoint_ordered() {
- let s1 = sketch_with_range(0, 1000);
- let s2 = sketch_with_range(1000, 1000);
+ let s1 = tuple_sketch_with_range(0, 1000);
+ let s2 = tuple_sketch_with_range(1000, 1000);
let mut i = TupleIntersection::new_with_default_seed(SumPolicy);
i.update(&s1.compact(true)).unwrap();
@@ -258,8 +250,8 @@ fn test_exact_disjoint_ordered() {
#[test]
fn test_estimation_half_overlap_unordered() {
- let s1 = sketch_with_range(0, 10000);
- let s2 = sketch_with_range(5000, 10000);
+ let s1 = tuple_sketch_with_range(0, 10000);
+ let s2 = tuple_sketch_with_range(5000, 10000);
let mut i = TupleIntersection::new_with_default_seed(SumPolicy);
i.update(&s1).unwrap();
@@ -273,8 +265,8 @@ fn test_estimation_half_overlap_unordered() {
#[test]
fn test_estimation_half_overlap_ordered() {
- let s1 = sketch_with_range(0, 10000);
- let s2 = sketch_with_range(5000, 10000);
+ let s1 = tuple_sketch_with_range(0, 10000);
+ let s2 = tuple_sketch_with_range(5000, 10000);
let mut i = TupleIntersection::new_with_default_seed(SumPolicy);
i.update(&s1.compact(true)).unwrap();
@@ -288,8 +280,8 @@ fn test_estimation_half_overlap_ordered() {
#[test]
fn test_estimation_half_overlap_ordered_deserialized_compact() {
- let s1 = sketch_with_range(0, 10000);
- let s2 = sketch_with_range(5000, 10000);
+ 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();
@@ -305,8 +297,8 @@ fn test_estimation_half_overlap_ordered_deserialized_compact() {
#[test]
fn test_estimation_disjoint_unordered() {
- let s1 = sketch_with_range(0, 10000);
- let s2 = sketch_with_range(10000, 10000);
+ let s1 = tuple_sketch_with_range(0, 10000);
+ let s2 = tuple_sketch_with_range(10000, 10000);
let mut i = TupleIntersection::new_with_default_seed(SumPolicy);
i.update(&s1).unwrap();
@@ -320,8 +312,8 @@ fn test_estimation_disjoint_unordered() {
#[test]
fn test_estimation_disjoint_ordered() {
- let s1 = sketch_with_range(0, 10000);
- let s2 = sketch_with_range(10000, 10000);
+ let s1 = tuple_sketch_with_range(0, 10000);
+ let s2 = tuple_sketch_with_range(10000, 10000);
let mut i = TupleIntersection::new_with_default_seed(SumPolicy);
i.update(&s1.compact(true)).unwrap();
@@ -335,7 +327,7 @@ fn test_estimation_disjoint_ordered() {
#[test]
fn test_seed_mismatch_non_empty_returns_error() {
- let mut s = default_sketch_builder().build();
+ let mut s = default_tuple_sketch_builder().build();
s.update(1u64, 1u64);
let mut i = TupleIntersection::new(123, SumPolicy);
diff --git a/datasketches/tests/tuple_sketch_test.rs b/datasketches/tests/tuple_sketch_test.rs
index ca69e02..5371483 100644
--- a/datasketches/tests/tuple_sketch_test.rs
+++ b/datasketches/tests/tuple_sketch_test.rs
@@ -17,18 +17,16 @@
#![cfg(feature = "tuple")]
+mod common;
+
use datasketches::common::NumStdDev;
use datasketches::hash_value;
-use datasketches::tuple::DefaultUpdatePolicy;
-use datasketches::tuple::TupleSketchBuilder;
-fn default_sketch_builder() -> TupleSketchBuilder<DefaultUpdatePolicy<u64>> {
- TupleSketchBuilder::new(DefaultUpdatePolicy::<u64>::default())
-}
+use crate::common::default_tuple_sketch_builder;
#[test]
fn test_basic_update() {
- let mut sketch = default_sketch_builder().lg_k(12).build();
+ let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
assert!(sketch.is_empty());
assert_eq!(sketch.estimate(), 0.0);
@@ -42,7 +40,7 @@ fn test_basic_update() {
#[test]
fn test_summary_accumulates_per_key() {
- let mut sketch = default_sketch_builder().lg_k(12).build();
+ let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
for _ in 0..5 {
sketch.update("same_key", 2u64);
}
@@ -54,7 +52,7 @@ fn test_summary_accumulates_per_key() {
#[test]
fn test_update_various_types() {
- let mut sketch = default_sketch_builder().lg_k(12).build();
+ let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
sketch.update("string", 1u64);
sketch.update(42i64, 1u64);
@@ -69,7 +67,7 @@ fn test_update_various_types() {
assert!(!sketch.is_empty());
assert_eq!(sketch.estimate(), 5.0);
- let mut sketch = default_sketch_builder().lg_k(12).build();
+ let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
sketch.update("string", 1u64);
sketch.update(42i64, 1u64);
@@ -87,7 +85,7 @@ fn test_update_various_types() {
#[test]
fn test_duplicate_updates() {
- let mut sketch = default_sketch_builder().lg_k(12).build();
+ let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
for _ in 0..100 {
sketch.update("same_value", 1u64);
@@ -98,7 +96,7 @@ fn test_duplicate_updates() {
#[test]
fn test_theta_reduction() {
- let mut sketch = default_sketch_builder().lg_k(5).build(); // Small k to trigger theta reduction
+ let mut sketch = default_tuple_sketch_builder().lg_k(5).build(); // Small k to trigger theta reduction
assert!(!sketch.is_estimation_mode());
// Insert many values to trigger theta reduction
@@ -112,7 +110,7 @@ fn test_theta_reduction() {
#[test]
fn test_trim() {
- let mut sketch = default_sketch_builder().lg_k(5).build();
+ let mut sketch = default_tuple_sketch_builder().lg_k(5).build();
// Insert many values
for i in 0..1000 {
@@ -130,7 +128,7 @@ fn test_trim() {
#[test]
fn test_reset() {
- let mut sketch = default_sketch_builder().lg_k(5).build();
+ let mut sketch = default_tuple_sketch_builder().lg_k(5).build();
// Insert many values
for i in 0..1000 {
@@ -153,7 +151,7 @@ fn test_reset() {
#[test]
fn test_iterator() {
- let mut sketch = default_sketch_builder().lg_k(12).build();
+ let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
sketch.update("value1", 1u64);
sketch.update("value2", 1u64);
@@ -165,7 +163,7 @@ fn test_iterator() {
#[test]
fn test_bounds_empty_sketch() {
- let sketch = default_sketch_builder().lg_k(12).build();
+ let sketch = default_tuple_sketch_builder().lg_k(12).build();
assert!(sketch.is_empty());
assert!(!sketch.is_estimation_mode());
assert_eq!(sketch.theta(), 1.0);
@@ -180,7 +178,7 @@ fn test_bounds_empty_sketch() {
#[test]
fn test_bounds_exact_mode() {
- let mut sketch = default_sketch_builder().lg_k(12).build();
+ let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
for i in 0..2000 {
sketch.update(i, 1u64);
}
@@ -194,7 +192,7 @@ fn test_bounds_exact_mode() {
#[test]
fn test_bounds_estimation_mode() {
- let mut sketch = default_sketch_builder().lg_k(12).build();
+ let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
let n = 10000;
for i in 0..n {
sketch.update(i, 1u64);
@@ -236,7 +234,7 @@ fn test_bounds_estimation_mode() {
#[test]
fn test_bounds_with_sampling() {
- let mut sketch = default_sketch_builder()
+ let mut sketch = default_tuple_sketch_builder()
.lg_k(12)
.sampling_probability(0.5)
.build();
@@ -259,7 +257,7 @@ fn test_bounds_with_sampling() {
#[test]
fn test_bounds_all_num_std_devs() {
- let mut sketch = default_sketch_builder().lg_k(12).build();
+ let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
for i in 0..10000 {
sketch.update(i, 1u64);
}
@@ -281,7 +279,7 @@ fn test_bounds_all_num_std_devs() {
#[test]
fn test_bounds_empty_estimation_mode() {
// Create a sketch with sampling probability < 1.0 to force estimation mode
- let sketch = default_sketch_builder()
+ let sketch = default_tuple_sketch_builder()
.lg_k(12)
.sampling_probability(0.1)
.build();
@@ -299,7 +297,7 @@ fn test_bounds_empty_estimation_mode() {
fn test_compact_preserves_logical_non_empty_after_screened_update() {
let screened_value = (0u64..)
.find(|candidate| {
- let mut sketch = default_sketch_builder()
+ let mut sketch = default_tuple_sketch_builder()
.lg_k(12)
.sampling_probability(0.5)
.build();
@@ -308,7 +306,7 @@ 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_sketch_builder()
+ let mut sketch = default_tuple_sketch_builder()
.lg_k(12)
.sampling_probability(0.5)
.build();
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org