rolling_set/
lib.rs

1use std::{
2    collections::{BTreeMap, HashMap},
3    sync::Arc,
4};
5
6#[derive(Debug, Clone, PartialEq)]
7pub struct RollingSet<T: std::hash::Hash + std::cmp::Eq> {
8    value_identifyer: usize,
9    capacity: usize,
10    time_to_value: BTreeMap<usize, Arc<T>>,
11    value_to_time: HashMap<Arc<T>, usize>,
12}
13
14impl<T> RollingSet<T>
15where
16    T: Eq + std::hash::Hash + Clone,
17{
18    pub fn new(capacity: usize) -> Self {
19        Self {
20            capacity,
21            value_identifyer: 0,
22            time_to_value: BTreeMap::new(),
23            value_to_time: HashMap::new(),
24        }
25    }
26
27    pub fn with_capacity(capacity: usize) -> Self {
28        Self {
29            capacity,
30            value_identifyer: 0,
31            time_to_value: BTreeMap::new(),
32
33            value_to_time: HashMap::with_capacity(capacity),
34        }
35    }
36
37    pub fn insert(&mut self, element: T) {
38        self.value_identifyer += 1;
39        let v = Arc::new(element);
40        self.time_to_value.insert(self.value_identifyer, v.clone());
41        // Here v is guaranteed to be unique
42        self.value_to_time.insert(v, self.value_identifyer);
43
44        if self.len() > self.capacity {
45            self.pop();
46        }
47    }
48
49    pub fn pop(&mut self) -> Option<T> {
50        // These clones are always cheap, usize and Arc
51        let first = self.time_to_value.first_key_value()?.0.clone();
52        let value = self.time_to_value.get(&first)?.clone();
53        self.value_to_time.remove(&value);
54        self.time_to_value.remove(&first);
55        if !self.is_empty() {
56            self.value_identifyer = 0;
57        }
58        Some((*value).clone())
59    }
60
61    pub fn is_empty(&self) -> bool {
62        self.len() == 0
63    }
64
65    pub fn is_full(&self) -> bool {
66        self.len() == self.capacity
67    }
68
69    pub fn set_capacity(&mut self, new: usize) -> usize {
70        self.capacity = new;
71        self.capacity
72    }
73
74    pub fn capacity(&self) -> usize {
75        self.capacity
76    }
77
78    pub fn remove(&mut self, element: &T) -> bool {
79        let i = match self.value_to_time.get(element) {
80            Some(i) => i,
81            None => return false,
82        };
83
84        self.time_to_value.remove(i);
85        self.value_to_time.remove(element);
86        true
87    }
88
89    pub fn contains(&self, element: &T) -> bool {
90        self.value_to_time.contains_key(element)
91    }
92
93    pub fn len(&self) -> usize {
94        self.value_to_time.len()
95    }
96
97    pub fn clear(&mut self) {
98        self.value_identifyer = 0;
99        self.time_to_value.clear();
100        self.value_to_time.clear();
101    }
102}
103
104#[cfg(test)]
105mod tests {
106
107    use crate::RollingSet;
108
109    #[test]
110    fn create() {
111        let mut set = RollingSet::new(100);
112        set.insert("one");
113        set.insert("two");
114        set.insert("three");
115
116        assert!(set.contains(&"one"));
117        assert!(set.contains(&"two"));
118        assert!(set.contains(&"three"));
119        assert!(!set.contains(&"four"));
120    }
121
122    #[test]
123    fn roll() {
124        let mut set = RollingSet::new(3);
125        set.insert("one");
126        set.insert("two");
127        set.insert("three");
128        // Set rolls here
129        set.insert("four");
130        assert_eq!(set.len(), 3);
131        assert!(!set.contains(&"one"));
132        assert!(set.contains(&"two"));
133        assert!(set.contains(&"three"));
134        assert!(set.contains(&"four"));
135    }
136
137    #[test]
138    fn remove() {
139        let mut set = RollingSet::new(3);
140        set.insert("one");
141        set.insert("two");
142        set.insert("three");
143        set.insert("four");
144
145        assert!(set.contains(&"two"));
146        assert!(set.contains(&"three"));
147        assert!(set.contains(&"four"));
148
149        set.remove(&"two");
150        assert_eq!(set.len(), 2);
151        assert!(!set.contains(&"two"));
152        assert!(set.contains(&"three"));
153        assert!(set.contains(&"four"));
154    }
155
156    #[test]
157    fn len() {
158        let mut set = RollingSet::new(3);
159        set.insert("one");
160        set.insert("two");
161        set.insert("three");
162        assert_eq!(set.len(), 3);
163        set.insert("four");
164
165        // The set should have rolled so the len should still be three
166        assert_eq!(set.len(), 3);
167
168        assert!(set.contains(&"two"));
169        assert!(set.contains(&"three"));
170        assert!(set.contains(&"four"));
171
172        set.remove(&"two");
173        assert_eq!(set.len(), 2);
174        assert!(!set.contains(&"two"));
175        assert!(set.contains(&"three"));
176        assert!(set.contains(&"four"));
177    }
178
179    #[test]
180    fn pop() {
181        let mut set = RollingSet::new(3);
182        set.insert("one");
183        set.insert("two");
184        set.insert("three");
185        assert_eq!(set.len(), 3);
186
187        let value = set.pop();
188        assert_eq!(value, Some("one"));
189        assert_eq!(set.len(), 2);
190
191        let value = set.pop();
192        assert_eq!(value, Some("two"));
193        assert_eq!(set.len(), 1);
194
195        let value = set.pop();
196        assert_eq!(value, Some("three"));
197        assert_eq!(set.len(), 0);
198
199        set.insert("one");
200        set.insert("two");
201        set.insert("three");
202        set.insert("four");
203        assert_eq!(set.len(), 3);
204
205        let value = set.pop();
206        assert_eq!(value, Some("two"));
207        assert_eq!(set.len(), 2);
208
209        let value = set.pop();
210        assert_eq!(value, Some("three"));
211        assert_eq!(set.len(), 1);
212
213        let value = set.pop();
214        assert_eq!(value, Some("four"));
215        assert_eq!(set.len(), 0);
216    }
217
218    #[test]
219    fn iter() {
220        let mut set = RollingSet::new(3);
221        set.insert("one");
222        set.insert("two");
223        set.insert("three");
224    }
225}
rolling_set/lib.rs

rolling_set/
lib.rs
