datasketches 0.5.0

A software library of stochastic streaming algorithms (a.k.a. sketches)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

// 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. It shares its set-difference
//! implementation with Theta a-not-B.

use crate::error::Error;
use crate::error::ErrorKind;
use crate::hash::DEFAULT_UPDATE_SEED;
use crate::hash::compute_seed_hash;
use crate::thetacommon::a_not_b;
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;
/// use datasketches::tuple::TupleANotB;
/// use datasketches::tuple::TupleSketchBuilder;
///
/// let update_policy = DefaultUpdatePolicy::<u64>::default();
/// let mut a = TupleSketchBuilder::new(update_policy).build().unwrap();
/// a.update("apple", 1);
/// a.update("banana", 1);
///
/// let mut b = TupleSketchBuilder::new(update_policy).build().unwrap();
/// b.update("banana", 1);
///
/// let a_not_b = TupleANotB::default();
/// 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 {
    seed_hash: u16,
}

impl Default for TupleANotB {
    fn default() -> Self {
        Self::with_seed(DEFAULT_UPDATE_SEED).unwrap()
    }
}

impl TupleANotB {
    /// Creates a new set difference operator for the given `seed`.
    ///
    /// # Errors
    ///
    /// Returns an error if the computed seed hash is zero.
    pub fn with_seed(seed: u64) -> Result<Self, Error> {
        Ok(Self {
            seed_hash: compute_seed_hash(seed, ErrorKind::InvalidArgument)?,
        })
    }

    /// 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`. Summary values in `b` are ignored and need not be
    /// cloneable. 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, S, T>(
        &self,
        a: impl Into<TupleSketchView<'a, S>>,
        b: impl Into<TupleSketchView<'b, T>>,
        ordered: bool,
    ) -> Result<CompactTupleSketch<S>, Error>
    where
        S: Clone + 'a,
        T: 'b,
    {
        let a = a.into();
        let b = b.into();
        let compact_state = a_not_b::compute(self.seed_hash, a, b, ordered)?;
        Ok(CompactTupleSketch::from_compact_state(compact_state))
    }
}