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