contrail_collections/sparse_set.rs
1/*
2 * This Source Code Form is subject to the terms of the Mozilla Public License,
3 * v. 2.0. If a copy of the MPL was not distributed with this file, You can
4 * obtain one at http://mozilla.org/MPL/2.0/.
5 */
6
7//! Sparse sets.
8
9use contrail::{
10 storage::{Backtrackable, NonBacktrackable, StorageMode},
11 NonBacktrackableArray, Trail, TrailBuilder, Value,
12};
13use std::fmt;
14
15/// A sparse set stored on the trail in backtrackable memory.
16pub type BacktrackableSparseSet = SparseSet<Backtrackable>;
17
18/// A sparse set stored on the trail in non-backtrackable memory.
19pub type NonBacktrackableSparseSet = SparseSet<NonBacktrackable>;
20
21/// A specialized backtrackable data structure for storing subsets of the range `0..n` that can
22/// only decrease in size.
23///
24/// Features O(1) `contains()` and `remove()` as well as fast value iteration.
25pub struct SparseSet<M> {
26 values: NonBacktrackableArray<usize>,
27 positions: NonBacktrackableArray<usize>,
28 len: Value<M, usize>,
29}
30
31impl<M> SparseSet<M>
32where
33 M: StorageMode,
34{
35 /// Creates a new `SparseSet` initialized with the values `0..len`.
36 ///
37 /// # Examples
38 ///
39 /// ```
40 /// use contrail::TrailBuilder;
41 /// use contrail_collections::sparse_set::BacktrackableSparseSet;
42 ///
43 /// let mut builder = TrailBuilder::new();
44 /// let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
45 /// let mut trail = builder.finish();
46 ///
47 /// assert_eq!(sparse_set.len(&trail), 10);
48 /// ```
49 pub fn new_full(builder: &mut TrailBuilder, len: usize) -> Self {
50 Self {
51 values: NonBacktrackableArray::new(builder, 0..len),
52 positions: NonBacktrackableArray::new(builder, 0..len),
53 len: Value::new(builder, len),
54 }
55 }
56
57 /// Returns an iterator over the elements of the `SparseSet` in arbitrary order.
58 ///
59 /// # Examples
60 ///
61 /// ```
62 /// use contrail::TrailBuilder;
63 /// use contrail_collections::sparse_set::BacktrackableSparseSet;
64 ///
65 /// let mut builder = TrailBuilder::new();
66 /// let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
67 /// let mut trail = builder.finish();
68 ///
69 /// // remove some values
70 /// sparse_set.remove(&mut trail, 2);
71 /// sparse_set.remove(&mut trail, 3);
72 /// sparse_set.remove(&mut trail, 6);
73 ///
74 /// for value in sparse_set.iter(&trail) {
75 /// assert!(value != 2 && value != 3 && value != 6);
76 /// }
77 /// ```
78 pub fn iter<'s, 't: 's>(&'s self, trail: &'t Trail) -> impl Iterator<Item = usize> + 's {
79 (0..self.len.get(trail)).map(move |i| self.values.get(trail, i))
80 }
81
82 /// Returns the length of the `SparseSet`.
83 ///
84 /// # Examples
85 ///
86 /// ```
87 /// use contrail::TrailBuilder;
88 /// use contrail_collections::sparse_set::BacktrackableSparseSet;
89 ///
90 /// let mut builder = TrailBuilder::new();
91 /// let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
92 /// let mut trail = builder.finish();
93 ///
94 /// assert_eq!(sparse_set.len(&trail), 10);
95 ///
96 /// sparse_set.remove(&mut trail, 5);
97 ///
98 /// assert_eq!(sparse_set.len(&trail), 9);
99 /// ```
100 pub fn len(&self, trail: &Trail) -> usize {
101 self.len.get(trail)
102 }
103
104 /// Returns true if the sparse set is empty and false otherwise.
105 ///
106 /// # Examples
107 ///
108 /// ```
109 /// use contrail::TrailBuilder;
110 /// use contrail_collections::sparse_set::BacktrackableSparseSet;
111 ///
112 /// let mut builder = TrailBuilder::new();
113 /// let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 1);
114 /// let mut trail = builder.finish();
115 ///
116 /// assert!(!sparse_set.is_empty(&trail));
117 ///
118 /// sparse_set.remove(&mut trail, 0);
119 ///
120 /// assert!(sparse_set.is_empty(&trail));
121 /// ```
122 pub fn is_empty(&self, trail: &Trail) -> bool {
123 self.len.get(trail) == 0
124 }
125
126 /// Checks if the sparse set contains the given value.
127 ///
128 /// # Examples
129 ///
130 /// ```
131 /// use contrail::TrailBuilder;
132 /// use contrail_collections::sparse_set::BacktrackableSparseSet;
133 ///
134 /// let mut builder = TrailBuilder::new();
135 /// let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
136 /// let mut trail = builder.finish();
137 ///
138 /// assert!(sparse_set.contains(&trail, 5));
139 /// assert!(!sparse_set.contains(&trail, 15));
140 /// ```
141 pub fn contains(&self, trail: &Trail, val: usize) -> bool {
142 val < self.positions.len() && self.positions.get(trail, val) < self.len.get(trail)
143 }
144
145 /// Removes a value from the sparse set.
146 ///
147 /// # Examples
148 ///
149 /// ```
150 /// use contrail::TrailBuilder;
151 /// use contrail_collections::sparse_set::BacktrackableSparseSet;
152 ///
153 /// let mut builder = TrailBuilder::new();
154 /// let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
155 /// let mut trail = builder.finish();
156 ///
157 /// assert!(sparse_set.contains(&trail, 5));
158 /// assert_eq!(sparse_set.len(&trail), 10);
159 ///
160 /// sparse_set.remove(&mut trail, 5);
161 ///
162 /// assert!(!sparse_set.contains(&trail, 5));
163 /// assert_eq!(sparse_set.len(&trail), 9);
164 /// ```
165 pub fn remove(&self, trail: &mut Trail, val: usize) {
166 if self.contains(trail, val) {
167 let position = self.positions.get(trail, val);
168 let new_size = self.len.get(trail) - 1;
169 self.swap(trail, position, new_size);
170 self.len.set(trail, new_size);
171 }
172 }
173
174 /// Filters the elements in the sparse set according to the predicate
175 /// function.
176 ///
177 /// # Examples
178 ///
179 /// ```
180 /// use contrail::TrailBuilder;
181 /// use contrail_collections::sparse_set::BacktrackableSparseSet;
182 ///
183 /// // create a sparse set initialized with the values 0..10
184 /// let mut builder = TrailBuilder::new();
185 /// let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
186 /// let mut trail = builder.finish();
187 ///
188 /// // keep only the odd numbers
189 /// sparse_set.filter(&mut trail, |x| x % 2 == 1);
190 ///
191 /// // make sure we kept only the odd numbers
192 /// let mut values = sparse_set.iter(&trail).collect::<Vec<_>>();
193 /// // we have to sort the values because a sparse set is unordered
194 /// values.sort();
195 /// assert_eq!(values, vec![1, 3, 5, 7, 9]);
196 /// ```
197 pub fn filter(&self, trail: &mut Trail, f: impl Fn(usize) -> bool) {
198 for position in (0..self.len.get(trail)).rev() {
199 let val = self.values.get(trail, position);
200 if !f(val) {
201 let new_size = self.len.get(trail) - 1;
202 self.swap(trail, position, new_size);
203 self.len.set(trail, new_size);
204 }
205 }
206 }
207
208 /// Intersects the sparse set with the given values.
209 ///
210 /// # Examples
211 ///
212 /// ```
213 /// use contrail::TrailBuilder;
214 /// use contrail_collections::sparse_set::BacktrackableSparseSet;
215 ///
216 /// // create a sparse set initialized with the elements 0..10
217 /// let mut builder = TrailBuilder::new();
218 /// let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
219 /// let mut trail = builder.finish();
220 ///
221 /// // keep only the fibonacci numbers
222 /// sparse_set.intersect(&mut trail, vec![0, 1, 1, 2, 3, 5, 8, 13]);
223 ///
224 /// // make sure we kept only the fibonacci numbers
225 /// let mut values = sparse_set.iter(&trail).collect::<Vec<_>>();
226 /// // we have to sort the values because a sparse set is unordered
227 /// values.sort();
228 /// assert_eq!(values, vec![0, 1, 2, 3, 5, 8]);
229 /// ```
230 pub fn intersect(&self, trail: &mut Trail, vals: impl IntoIterator<Item = usize>) {
231 let mut vals = vals.into_iter().collect::<Vec<_>>();
232 vals.sort();
233 vals.dedup();
234 let mut new_size = 0;
235 for val in vals {
236 if self.contains(trail, val) {
237 let position = self.positions.get(trail, val);
238 self.swap(trail, position, new_size);
239 new_size += 1;
240 }
241 }
242 self.len.set(trail, new_size);
243 }
244
245 /// Swaps two positions in the sparse set.
246 fn swap(&self, trail: &mut Trail, i: usize, j: usize) {
247 let val_i = self.values.get(trail, i);
248 let val_j = self.values.get(trail, j);
249
250 self.values.set(trail, i, val_j);
251 self.values.set(trail, j, val_i);
252
253 self.positions.set(trail, val_i, j);
254 self.positions.set(trail, val_j, i);
255 }
256}
257
258impl<M> Clone for SparseSet<M> {
259 fn clone(&self) -> Self {
260 Self {
261 values: self.values,
262 positions: self.positions,
263 len: self.len,
264 }
265 }
266}
267
268impl<M> Copy for SparseSet<M> {}
269
270impl<M> fmt::Debug for SparseSet<M>
271where
272 M: StorageMode,
273{
274 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
275 f.debug_struct("SparseSet")
276 .field("values", &self.values)
277 .field("positions", &self.positions)
278 .field("len", &self.len)
279 .finish()
280 }
281}
282
283impl<M> Eq for SparseSet<M> {}
284
285impl<M> PartialEq for SparseSet<M> {
286 fn eq(&self, other: &Self) -> bool {
287 self.values == other.values && self.positions == other.positions && self.len == other.len
288 }
289}
290
291#[cfg(test)]
292mod test {
293 use super::*;
294 use contrail::TrailBuilder;
295
296 #[test]
297 fn clone_eq() {
298 let mut builder = TrailBuilder::new();
299 let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
300
301 let clone = sparse_set.clone();
302 assert_eq!(sparse_set, clone);
303 }
304
305 #[test]
306 fn debug() {
307 let mut builder = TrailBuilder::new();
308 let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
309 assert_eq!(format!("{:?}", sparse_set), "SparseSet { values: Array { pointer: ArrayPointer { offset: 0, len: 10 }, storage_mode: NonBacktrackable }, positions: Array { pointer: ArrayPointer { offset: 80, len: 10 }, storage_mode: NonBacktrackable }, len: Value { pointer: Pointer { offset: 0 }, storage_mode: Backtrackable } }");
310 }
311
312 #[test]
313 fn iter() {
314 let mut builder = TrailBuilder::new();
315 let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 6);
316 let mut trail = builder.finish();
317
318 sparse_set.remove(&mut trail, 1);
319 sparse_set.remove(&mut trail, 3);
320 sparse_set.remove(&mut trail, 5);
321
322 let mut values = sparse_set.iter(&trail).collect::<Vec<_>>();
323 values.sort();
324 assert_eq!(values, &[0, 2, 4]);
325 }
326
327 #[test]
328 fn is_empty() {
329 let mut builder = TrailBuilder::new();
330 let empty = BacktrackableSparseSet::new_full(&mut builder, 0);
331 let not_empty = BacktrackableSparseSet::new_full(&mut builder, 1);
332 let trail = builder.finish();
333
334 assert_eq!(empty.len(&trail), 0);
335 assert!(empty.is_empty(&trail));
336
337 assert_eq!(not_empty.len(&trail), 1);
338 assert!(!not_empty.is_empty(&trail));
339 }
340
341 #[test]
342 fn filter() {
343 let mut builder = TrailBuilder::new();
344 let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
345 let mut trail = builder.finish();
346
347 sparse_set.filter(&mut trail, |x| x % 2 == 1);
348
349 let mut values = sparse_set.iter(&trail).collect::<Vec<_>>();
350 values.sort();
351 assert_eq!(values, vec![1, 3, 5, 7, 9]);
352 }
353
354 #[test]
355 fn intersect() {
356 let mut builder = TrailBuilder::new();
357 let sparse_set = BacktrackableSparseSet::new_full(&mut builder, 10);
358 let mut trail = builder.finish();
359
360 sparse_set.intersect(&mut trail, vec![0, 1, 1, 2, 3, 5, 8, 13]);
361
362 let mut values = sparse_set.iter(&trail).collect::<Vec<_>>();
363 values.sort();
364 assert_eq!(values, vec![0, 1, 2, 3, 5, 8]);
365 }
366
367 #[test]
368 fn backtrack() {
369 let mut builder = TrailBuilder::new();
370
371 // 0..5
372 let trailed_sparse_set = BacktrackableSparseSet::new_full(&mut builder, 5);
373
374 let trail = &mut builder.finish();
375
376 trail.new_level();
377
378 trailed_sparse_set.remove(trail, 1);
379 assert!(!trailed_sparse_set.contains(trail, 1));
380
381 trail.new_level();
382
383 trailed_sparse_set.remove(trail, 4);
384 assert!(!trailed_sparse_set.contains(trail, 4));
385
386 trailed_sparse_set.remove(trail, 2);
387
388 assert!(!trailed_sparse_set.contains(trail, 4));
389
390 trail.new_level();
391
392 trailed_sparse_set.remove(trail, 0);
393 assert!(!trailed_sparse_set.contains(trail, 0));
394
395 trail.backtrack();
396
397 assert!(trailed_sparse_set.contains(trail, 0));
398
399 trail.backtrack();
400
401 assert!(trailed_sparse_set.contains(trail, 4));
402 assert!(trailed_sparse_set.contains(trail, 2));
403
404 trail.backtrack();
405
406 assert!(trailed_sparse_set.contains(trail, 1));
407 }
408}