v0id-X commented on code in PR #271:
URL: https://github.com/apache/datasketches-rust/pull/271#discussion_r3920227331
##########
datasketches/src/bloom/sketch.rs:
##########
@@ -251,13 +251,17 @@ impl BloomFilter {
Ok(())
}
- /// Inverts all bits in the filter.
+ /// Consumes the filter and inverts all its bits, returning a read-only
inverted view.
///
/// This approximately inverts the notion of set membership. After
inversion, neither the
/// no-false-negative nor the false-positive guarantee holds: inserted
items may return
- /// `false` from [`contains()`](Self::contains), and
[`is_empty()`](Self::is_empty),
- /// [`bits_used()`](Self::bits_used), and
[`load_factor()`](Self::load_factor) describe the
- /// raw bit state rather than the inserted items.
+ /// `false` from [`contains()`](BloomFilterInvertedView::contains), and
metadata methods
+ /// describe the raw inverted bit state.
+ ///
+ /// Updates are disallowed on an inverted view to prevent unsound filter
states. An inverted
+ /// view can be converted back into an updatable [`BloomFilter`] via
+ /// [`invert()`](BloomFilterInvertedView::invert) or
+ /// [`into_filter()`](BloomFilterInvertedView::into_filter).
Review Comment:
Agreed. I'll trim the method documentation down to its core behavior and
move the details regarding disallowed mutations and reinversion up to the
BloomFilterInvertedView struct documentation.
##########
datasketches/src/bloom/sketch.rs:
##########
@@ -613,6 +622,114 @@ impl BloomFilter {
}
}
+/// A read-only inverted view of a [`BloomFilter`].
+///
+/// An inverted view is created by calling [`BloomFilter::invert()`].
+/// Modifications (such as inserting new elements or merging) are disallowed
+/// on an inverted view to avoid corrupting set membership invariants.
+///
+/// Set membership queries can still be executed via
[`contains()`](Self::contains),
+/// and the view can be reinverted back into an updatable [`BloomFilter`].
+#[derive(Debug, Clone, PartialEq)]
+pub struct BloomFilterInvertedView {
+ inner: BloomFilter,
+}
+
+impl BloomFilterInvertedView {
+ /// Returns `true` if an item is possibly in the inverted set.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::bloom::BloomFilterBuilder;
+ ///
+ /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// .build()
+ /// .unwrap();
+ /// filter.insert("apple");
+ ///
+ /// let inverted = filter.invert();
+ /// assert!(!inverted.contains(&"apple"));
+ /// ```
+ pub fn contains<T: Hash>(&self, item: &T) -> bool {
+ self.inner.contains(item)
+ }
+
+ /// Re-inverts the view back into an updatable [`BloomFilter`].
+ ///
+ /// Inverting twice restores the original bit state and filter guarantees.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::bloom::BloomFilterBuilder;
+ ///
+ /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// .build()
+ /// .unwrap();
+ /// filter.insert("apple");
+ ///
+ /// let inverted = filter.invert();
+ /// let restored = inverted.invert();
+ /// assert!(restored.contains(&"apple"));
+ /// ```
+ pub fn invert(self) -> BloomFilter {
+ self.into_filter()
+ }
+
+ /// Converts this inverted view back into an updatable [`BloomFilter`] by
+ /// inverting the bits again.
+ ///
+ /// Equivalent to [`invert()`](Self::invert).
+ pub fn into_filter(mut self) -> BloomFilter {
+ for word in &mut self.inner.bit_array {
+ *word = !*word;
+ }
+ self.inner.num_bits_set = self.inner.capacity() as u64 -
self.inner.num_bits_set;
+ self.inner
+ }
Review Comment:
That makes a lot more sense. Symmetrical .invert()
(filter.invert().invert()) is way cleaner anyway. Dropping into_filter and
keeping just invert(self) -> BloomFilter.
##########
datasketches/src/bloom/sketch.rs:
##########
@@ -613,6 +622,114 @@ impl BloomFilter {
}
}
+/// A read-only inverted view of a [`BloomFilter`].
+///
+/// An inverted view is created by calling [`BloomFilter::invert()`].
+/// Modifications (such as inserting new elements or merging) are disallowed
+/// on an inverted view to avoid corrupting set membership invariants.
+///
+/// Set membership queries can still be executed via
[`contains()`](Self::contains),
+/// and the view can be reinverted back into an updatable [`BloomFilter`].
+#[derive(Debug, Clone, PartialEq)]
+pub struct BloomFilterInvertedView {
+ inner: BloomFilter,
+}
+
+impl BloomFilterInvertedView {
+ /// Returns `true` if an item is possibly in the inverted set.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::bloom::BloomFilterBuilder;
+ ///
+ /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// .build()
+ /// .unwrap();
+ /// filter.insert("apple");
+ ///
+ /// let inverted = filter.invert();
+ /// assert!(!inverted.contains(&"apple"));
+ /// ```
+ pub fn contains<T: Hash>(&self, item: &T) -> bool {
+ self.inner.contains(item)
+ }
+
+ /// Re-inverts the view back into an updatable [`BloomFilter`].
+ ///
+ /// Inverting twice restores the original bit state and filter guarantees.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::bloom::BloomFilterBuilder;
+ ///
+ /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// .build()
+ /// .unwrap();
+ /// filter.insert("apple");
+ ///
+ /// let inverted = filter.invert();
+ /// let restored = inverted.invert();
+ /// assert!(restored.contains(&"apple"));
+ /// ```
+ pub fn invert(self) -> BloomFilter {
+ self.into_filter()
+ }
+
+ /// Converts this inverted view back into an updatable [`BloomFilter`] by
+ /// inverting the bits again.
+ ///
+ /// Equivalent to [`invert()`](Self::invert).
+ pub fn into_filter(mut self) -> BloomFilter {
+ for word in &mut self.inner.bit_array {
+ *word = !*word;
+ }
+ self.inner.num_bits_set = self.inner.capacity() as u64 -
self.inner.num_bits_set;
+ self.inner
+ }
+
+ /// Returns a reference to the underlying [`BloomFilter`] representation.
+ pub fn as_filter(&self) -> &BloomFilter {
+ &self.inner
+ }
Review Comment:
I thought about it, this makes the abstraction weaker risking misuse.
Removing it entirely.
##########
CHANGELOG.md:
##########
@@ -3,6 +3,7 @@
All significant changes to this project will be documented in this file.
## Unreleased
+- feat(bloom): make post-invert semantics observable via
`BloomFilterInvertedView` (#270, #271)
Review Comment:
My bad, will fix the formatting to match the rest of the file.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
