mappy_core/
deletion.rs

1//! Multiset-based deletion support
2//!
3//! Implements deletion support for maplets using the multiset approach
4//! described in Section 2 of the research paper.
5
6use crate::MapletResult;
7
8/// Multiset deletion manager
9#[derive(Debug, Clone)]
10pub struct DeletionManager {
11    /// Track multiple instances per fingerprint
12    instance_counts: std::collections::HashMap<u64, usize>,
13    /// Track which slots contain which instances
14    slot_instances: std::collections::HashMap<usize, Vec<u64>>,
15}
16
17impl Default for DeletionManager {
18    fn default() -> Self {
19        Self::new()
20    }
21}
22
23impl DeletionManager {
24    /// Create a new deletion manager
25    #[must_use]
26    pub fn new() -> Self {
27        Self {
28            instance_counts: std::collections::HashMap::new(),
29            slot_instances: std::collections::HashMap::new(),
30        }
31    }
32
33    /// Add an instance of a fingerprint
34    pub fn add_instance(&mut self, fingerprint: u64, slot: usize) {
35        *self.instance_counts.entry(fingerprint).or_insert(0) += 1;
36        self.slot_instances
37            .entry(slot)
38            .or_default()
39            .push(fingerprint);
40    }
41
42    /// Remove an instance of a fingerprint
43    /// # Errors
44    ///
45    /// Returns an error if the removal operation fails
46    pub fn remove_instance(&mut self, fingerprint: u64, slot: usize) -> MapletResult<bool> {
47        if let Some(count) = self.instance_counts.get_mut(&fingerprint)
48            && *count > 0
49        {
50            *count -= 1;
51            if *count == 0 {
52                self.instance_counts.remove(&fingerprint);
53            }
54
55            // Remove from slot instances
56            if let Some(instances) = self.slot_instances.get_mut(&slot) {
57                instances.retain(|&fp| fp != fingerprint);
58            }
59
60            return Ok(true);
61        }
62        Ok(false)
63    }
64
65    /// Get the number of instances for a fingerprint
66    #[must_use]
67    pub fn instance_count(&self, fingerprint: u64) -> usize {
68        self.instance_counts.get(&fingerprint).copied().unwrap_or(0)
69    }
70
71    /// Check if a fingerprint has any instances
72    #[must_use]
73    pub fn has_instances(&self, fingerprint: u64) -> bool {
74        self.instance_count(fingerprint) > 0
75    }
76
77    /// Get all fingerprints for a slot
78    #[must_use]
79    pub fn get_slot_fingerprints(&self, slot: usize) -> Vec<u64> {
80        self.slot_instances.get(&slot).cloned().unwrap_or_default()
81    }
82}
83
84#[cfg(test)]
85mod tests {
86    use super::*;
87
88    #[test]
89    fn test_deletion_manager() {
90        let mut manager = DeletionManager::new();
91
92        // Add some instances
93        manager.add_instance(0x1234, 0);
94        manager.add_instance(0x1234, 1);
95        manager.add_instance(0x5678, 2);
96
97        assert_eq!(manager.instance_count(0x1234), 2);
98        assert_eq!(manager.instance_count(0x5678), 1);
99        assert!(manager.has_instances(0x1234));
100
101        // Remove an instance
102        assert!(manager.remove_instance(0x1234, 0).unwrap());
103        assert_eq!(manager.instance_count(0x1234), 1);
104
105        // Remove the last instance
106        assert!(manager.remove_instance(0x1234, 1).unwrap());
107        assert_eq!(manager.instance_count(0x1234), 0);
108        assert!(!manager.has_instances(0x1234));
109    }
110}
mappy_core/deletion.rs

mappy_core/
deletion.rs
