Fix false negatives that may result from the removal of items

sile commented 5 months ago

This PR fixes an issue reported in the comment https://github.com/sile/scalable_cuckoo_filter/pull/4#issuecomment-2033055195 .

Copilot generated summary

This pull request includes changes to the src/buckets.rs, src/cuckoo_filter.rs, and src/scalable_cuckoo_filter.rs files in the Cuckoo Filter implementation. The changes primarily focus on improving the remove method's functionality, simplifying the insert method, and enhancing the fingerprint collision handling in the filter.

Changes to the remove method:

src/cuckoo_filter.rs: The remove method in the impl CuckooFilter { block now returns a boolean value indicating whether the removal was successful. This change is reflected in the method signature and the addition of a return statement. [1] [2]

Changes to the insert method:

src/cuckoo_filter.rs: The insert method in the impl CuckooFilter { block has been simplified. The check for the existence of a fingerprint before incrementing the item_count has been removed.
src/scalable_cuckoo_filter.rs: The insert method in the impl<T: Hash + ?Sized, H: Hasher + Clone, R: Rng> ScalableCuckooFilter<T, H, R> block has been modified. The iteration over filters to check for item existence has been removed. An explanatory note has been added to the method documentation to clarify the behavior of the filter when the same item is inserted multiple times.

Changes to fingerprint collision handling:

src/buckets.rs: Several debug assertions checking for fingerprint collisions have been removed from the impl Buckets { block. [1] [2] [3]
src/scalable_cuckoo_filter.rs: The remove method in the impl<T: Hash + ?Sized, H: Hasher + Clone, R: Rng> ScalableCuckooFilter<T, H, R> block has been modified to stop iterating over filters once an item has been successfully removed. A new test case has been added to verify the correct behavior when removing items with the same fingerprint. [1] [2]

Other changes:

src/cuckoo_filter.rs: The insert method in the impl ExceptionalItems { block has been simplified to use a binary search for insertion.
src/cuckoo_filter.rs: The insert method in the impl CuckooFilter { block has been modified to return directly after inserting an item into exceptional_items.