pumpkin_core/containers/
sparse_set.rs

1//! A set for keeping track of which values are still part of the original domain, allows O(1)
2//! removals and O(|D|) traversal of the domain (where D are the values which are currently in the
3//! domain).
4//!
5//! # Theoretical
6//! The idea of this structure is to allow efficient removal and traversal of the values which are
7//! still in the domain at the "cost" of expensive queries to check whether a value is currently in
8//! the domain.
9//!
10//! The idea is that the sparse-set keeps track of the number of elements which are in
11//! the domain in ([`SparseSet::size`]) and it guarantees that the first [`SparseSet::size`] values
12//! are in the domain. To remove a value, the element at index `i` is swapped with the element at
13//! index [`SparseSet::size`] and [`SparseSet::size`] is afterwards decremented by 1. This does not
14//! allow the reclamation of memory when an element is removed from the structure but it allows easy
15//! backtracking by simply moving the [`SparseSet::size`] pointer.
16//!
17//! # Practical
18//! Our implementation follows [\[1\]](https://hal.science/hal-01339250/document). The [`SparseSet`]
19//! structure keeps track of a number of variables; the main practical consideration is that a
20//! function `mapping` should be provided which maps every
21//! value in the domain to an index such that no two elements map to the same index.
22//!
23//! For performance, it is recommended to provide a mapping which maps an element to the
24//! range `[0, |domain|]`.
25//!
26//! # Bibliography
27//! \[1\] V. le C. de Saint-Marcq, P. Schaus, C. Solnon, and C. Lecoutre, ‘Sparse-sets for domain
28//! implementation’, in CP workshop on Techniques foR Implementing Constraint programming Systems
29//! (TRICS), 2013, pp. 1–10.
30
31use crate::containers::HashSet;
32use crate::containers::StorageKey;
33use crate::pumpkin_assert_moderate;
34use crate::pumpkin_assert_simple;
35
36/// A set for keeping track of which values are still part of the original domain based on [\[1\]](https://hal.science/hal-01339250/document).
37/// See the module level documentation for more information.
38///
39/// It provides O(1) removals of values from the domain and O(|D|) traversal of the domain (where D
40/// are the values which are currently in the domain).
41///
42/// Note that it is required that each element contained in the domain can be
43/// uniquely mapped to an index via the provided mapping.
44///
45/// # Bibliography
46/// \[1\] V. le C. de Saint-Marcq, P. Schaus, C. Solnon, and C. Lecoutre, ‘Sparse-sets for domain
47/// implementation’, in CP workshop on Techniques foR Implementing Constraint programming Systems
48/// (TRICS), 2013, pp. 1–10.
49#[derive(Debug, Clone)]
50pub struct SparseSet<T> {
51    /// The number of elements which are currently in the domain
52    size: usize,
53    /// The current state of the domain, this structure guarantees that the first
54    /// [`size`][SparseSet::size] elements are part of the domain
55    domain: Vec<T>,
56    /// Stores for each value of T what its corresponding index is in
57    /// [`domain`][`SparseSet::domain`]
58    indices: Vec<usize>,
59    /// A bijective function which takes as input an element `T` and returns an index in the range
60    /// [0, |D_{original}|) to be used for retrieving values from
61    /// [`indices`][`SparseSet::indices`]
62    mapping: fn(&T) -> i32,
63    index_offset: i32,
64}
65
66impl<T: StorageKey> SparseSet<T> {
67    /// Creates a new [`SparseSet`], using [`StorageKey::index`] as the index for the elements.
68    ///
69    /// If [`StorageKey::index`] returns the same index for two elements, then this method will
70    /// panic.
71    pub fn new(input: Vec<T>) -> Self {
72        Self::new_with_mapping(input, |element: &T| element.index() as i32)
73    }
74}
75
76impl<T> SparseSet<T> {
77    /// Creates a new [`SparseSet`], using the provided `mapping` to map the elements to indices.
78    ///
79    /// If the provided `mapping` maps two elements in `input` to the same element then this method
80    /// will panic.
81    ///
82    /// For performance, it is recommended to provide a mapping which maps all elements to the
83    /// range `[0, |domain|]`.
84    pub fn new_with_mapping(input: Vec<T>, mapping: fn(&T) -> i32) -> Self {
85        let input_len = input.len();
86
87        let mut min_index = 0;
88        let mut max_index = 0;
89
90        let mut used_indices = HashSet::new();
91
92        for element in input.iter() {
93            let index = (mapping)(element);
94            let not_previously_inserted = used_indices.insert(index);
95
96            pumpkin_assert_simple!(
97                not_previously_inserted,
98                "Two elements in the provided `input` map to the same index."
99            );
100
101            min_index = min_index.min(index);
102            max_index = max_index.max(index);
103        }
104
105        pumpkin_assert_simple!(min_index <= max_index);
106
107        // Now we need to adjust the indices; we first assign everything to usize::Max
108        let mut indices =
109            std::iter::repeat_n(usize::MAX, (max_index.abs() + min_index.abs()) as usize + 1)
110                .collect::<Vec<_>>();
111        // Then we go over all of the elements in the domain and assign them to their appropriate
112        // indices
113        for (i, element) in input.iter().enumerate().collect::<Vec<_>>() {
114            indices[((mapping)(element) - min_index) as usize] = i;
115        }
116
117        SparseSet {
118            size: input_len,
119            domain: input,
120            indices,
121            mapping,
122            index_offset: -min_index,
123        }
124    }
125
126    fn get_mapping(&self, element: &T) -> usize {
127        let output_index = (self.mapping)(element) + self.index_offset;
128        output_index.try_into().unwrap()
129    }
130
131    pub fn set_to_empty(&mut self) {
132        self.indices = vec![usize::MAX; self.indices.len()];
133        self.domain.clear();
134        self.size = 0;
135    }
136
137    pub fn restore_temporarily_removed(&mut self) {
138        self.size = self.domain.len();
139    }
140
141    /// Determines whether the domain represented by the [`SparseSet`] is empty
142    pub fn is_empty(&self) -> bool {
143        self.size == 0
144    }
145
146    /// Returns how many elements are part of the domain
147    pub fn len(&self) -> usize {
148        self.size
149    }
150
151    /// Returns the `index`th element in the domain; if `index` is larger than or equal to
152    /// [`SparseSet::len`] then this method will panic.
153    pub fn get(&self, index: usize) -> &T {
154        pumpkin_assert_simple!(index < self.size);
155        &self.domain[index]
156    }
157
158    /// Swaps the elements at positions `i` and `j` in [`domain`][SparseSet::domain] and swaps the
159    /// corresponding indices in [`indices`][SparseSet::indices]
160    fn swap(&mut self, i: usize, j: usize) {
161        self.domain.swap(i, j);
162
163        let index_i = self.get_mapping(&self.domain[i]);
164        self.indices[index_i] = i;
165
166        let index_j = self.get_mapping(&self.domain[j]);
167        self.indices[index_j] = j;
168    }
169
170    /// Remove the value of `to_remove` from the domain; if the value is not in the domain then this
171    /// method does not perform any operations.
172    pub fn remove(&mut self, to_remove: &T) {
173        if self.indices[self.get_mapping(to_remove)] < self.size {
174            // The element is part of the domain and should be removed
175            self.size -= 1;
176            if self.size > 0 {
177                self.swap(self.indices[self.get_mapping(to_remove)], self.size);
178            }
179
180            self.swap(
181                self.indices[self.get_mapping(to_remove)],
182                self.domain.len() - 1,
183            );
184            let element = self.domain.pop().expect("Has to have something to pop.");
185            pumpkin_assert_moderate!((self.mapping)(&element) == (self.mapping)(to_remove));
186
187            let to_remove_index = self.get_mapping(to_remove);
188            self.indices[to_remove_index] = usize::MAX;
189        } else if self.indices[self.get_mapping(to_remove)] < self.domain.len() {
190            self.swap(
191                self.indices[self.get_mapping(to_remove)],
192                self.domain.len() - 1,
193            );
194            let element = self.domain.pop().expect("Has to have something to pop.");
195            pumpkin_assert_moderate!((self.mapping)(&element) == (self.mapping)(to_remove));
196
197            let to_remove_index = self.get_mapping(to_remove);
198            self.indices[to_remove_index] = usize::MAX;
199        }
200    }
201
202    pub fn remove_temporarily(&mut self, to_remove: &T) {
203        if self.indices[self.get_mapping(to_remove)] < self.size {
204            // The element is part of the domain and should be removed
205            self.size -= 1;
206            self.swap(self.indices[self.get_mapping(to_remove)], self.size);
207        }
208    }
209
210    /// Determines whehter the `element` is contained in the domain of the sparse-set.
211    pub fn contains(&self, element: &T) -> bool {
212        self.get_mapping(element) < self.indices.len()
213            && self.indices[self.get_mapping(element)] < self.size
214    }
215
216    /// Accomodates the `element`.
217    pub fn accommodate(&mut self, element: &T) {
218        let index = self.get_mapping(element);
219        if self.indices.len() <= index {
220            self.indices.resize(index + 1, usize::MAX);
221        }
222    }
223
224    /// Inserts the element if it is not already contained in the sparse set.
225    ///
226    /// Note that this method does *not* check whether the insertion of this element causes clashes
227    /// in the provided mapping (i.e., it does not check whether two elements are now mapped to the
228    /// same index).
229    pub fn insert(&mut self, element: T) {
230        if !self.contains(&element) {
231            self.accommodate(&element);
232
233            let mut index = self.indices[self.get_mapping(&element)];
234
235            // The index is outside of the domain, we need to readjust it
236            //
237            // If the index is `<= self.domain.len()`, then it could be that it is a temporarily
238            // removed variable; in this case, we do not want to add a new element, but we just want
239            // to place it inside of the domain again
240            if index >= self.domain.len() {
241                index = self.domain.len();
242
243                let element_index = self.get_mapping(&element);
244                self.indices[element_index] = index;
245
246                self.domain.push(element);
247            }
248
249            self.swap(self.size, index);
250            self.size += 1;
251        }
252    }
253
254    /// Returns an iterator which goes over the values in the domain of the sparse-set
255    pub fn iter(&self) -> impl Iterator<Item = &T> {
256        self.domain[..self.size].iter()
257    }
258
259    pub fn out_of_domain(&self) -> impl Iterator<Item = &T> {
260        self.domain[self.size..].iter()
261    }
262}
263
264impl<T> IntoIterator for SparseSet<T> {
265    type Item = T;
266
267    type IntoIter = std::iter::Take<std::vec::IntoIter<T>>;
268
269    fn into_iter(self) -> Self::IntoIter {
270        self.domain.into_iter().take(self.size)
271    }
272}
273
274#[cfg(test)]
275mod tests {
276    use super::SparseSet;
277
278    fn mapping_function(input: &i32) -> i32 {
279        *input
280    }
281
282    #[test]
283    fn test_len() {
284        let sparse_set = SparseSet::new_with_mapping(vec![0, 1, 2], mapping_function);
285        assert_eq!(sparse_set.len(), 3);
286    }
287
288    #[test]
289    fn removal() {
290        let mut sparse_set = SparseSet::new_with_mapping(vec![0, 1, 2], mapping_function);
291        sparse_set.remove(&1);
292        assert_eq!(sparse_set.domain, vec![0, 2]);
293        assert_eq!(sparse_set.size, 2);
294        assert_eq!(sparse_set.indices, vec![0, usize::MAX, 1]);
295    }
296
297    #[test]
298    fn removal_adjusts_size() {
299        let mut sparse_set = SparseSet::new_with_mapping(vec![0, 1, 2], mapping_function);
300        assert_eq!(sparse_set.size, 3);
301        sparse_set.remove(&0);
302        assert_eq!(sparse_set.size, 2);
303    }
304
305    #[test]
306    fn remove_all_elements_leads_to_empty_set() {
307        let mut sparse_set = SparseSet::new_with_mapping(vec![0, 1, 2], mapping_function);
308        sparse_set.remove(&0);
309        sparse_set.remove(&1);
310        sparse_set.remove(&2);
311        assert!(sparse_set.is_empty());
312    }
313
314    #[test]
315    fn iter1() {
316        let sparse_set = SparseSet::new_with_mapping(vec![5, 10, 2], mapping_function);
317        let v: Vec<i32> = sparse_set.iter().copied().collect();
318        assert_eq!(v.len(), 3);
319        assert!(v.contains(&10));
320        assert!(v.contains(&5));
321        assert!(v.contains(&2));
322    }
323
324    #[test]
325    fn iter2() {
326        let mut sparse_set = SparseSet::new_with_mapping(vec![5, 10, 2], mapping_function); // 5, 10, 2
327        sparse_set.insert(100); // 5, 10, 2, 100
328        sparse_set.insert(2); // 5, 10, 2, 100
329        sparse_set.insert(20); // 5, 10, 2, 100, 20
330        sparse_set.remove(&10); // 5, 2, 100, 20
331        sparse_set.insert(10); // 5, 10, 2, 100, 20
332        sparse_set.remove(&10); // 5, 2, 100, 20
333
334        let v: Vec<i32> = sparse_set.iter().copied().collect();
335        assert_eq!(v.len(), 4);
336        assert!(v.contains(&5));
337        assert!(v.contains(&2));
338        assert!(v.contains(&100));
339        assert!(v.contains(&20));
340        assert!(!v.contains(&10));
341    }
342
343    #[test]
344    fn remove_temporarily_simple() {
345        let mut sparse_set = SparseSet::new_with_mapping(vec![0], mapping_function);
346
347        sparse_set.remove_temporarily(&0);
348        sparse_set.insert(0);
349        sparse_set.remove_temporarily(&0);
350
351        assert!(sparse_set.is_empty())
352    }
353
354    #[test]
355    fn remove_temporarily() {
356        let mut sparse_set = SparseSet::new_with_mapping(vec![2, 0, 1], mapping_function);
357
358        assert!(!sparse_set.is_empty());
359
360        sparse_set.remove_temporarily(&0);
361        sparse_set.insert(0);
362        sparse_set.remove_temporarily(&0);
363        assert!(!sparse_set.contains(&0));
364
365        assert!(!sparse_set.is_empty());
366
367        sparse_set.remove_temporarily(&0);
368        assert!(!sparse_set.contains(&0));
369
370        sparse_set.remove_temporarily(&0);
371        sparse_set.remove_temporarily(&2);
372        assert!(!sparse_set.contains(&2));
373        sparse_set.remove_temporarily(&1);
374        assert!(!sparse_set.contains(&1));
375
376        assert!(sparse_set.is_empty());
377
378        sparse_set.insert(1);
379
380        assert!(sparse_set.contains(&1));
381
382        assert!(!sparse_set.contains(&0));
383        assert!(sparse_set.contains(&1));
384        assert!(!sparse_set.contains(&2));
385
386        sparse_set.restore_temporarily_removed();
387
388        assert!(sparse_set.contains(&0));
389        assert!(sparse_set.contains(&1));
390        assert!(sparse_set.contains(&2));
391    }
392
393    #[test]
394    fn remove_temporarily_non_continuous() {
395        let mut sparse_set = SparseSet::new_with_mapping(vec![5, 10, 2], mapping_function);
396        sparse_set.remove_temporarily(&10);
397        assert!(!sparse_set.contains(&10));
398
399        sparse_set.remove_temporarily(&5);
400        sparse_set.remove_temporarily(&2);
401        assert!(sparse_set.is_empty());
402    }
403
404    #[test]
405    fn remove_temporarily_non_continuous_spanning() {
406        let mut sparse_set = SparseSet::new_with_mapping(vec![5, 10, -2], mapping_function);
407        sparse_set.remove_temporarily(&10);
408        assert!(!sparse_set.contains(&10));
409
410        sparse_set.remove_temporarily(&-2);
411        assert!(!sparse_set.contains(&-2));
412
413        sparse_set.remove_temporarily(&5);
414
415        assert!(sparse_set.is_empty());
416    }
417
418    #[test]
419    fn remove_temporarily_non_continuous_negative() {
420        let mut sparse_set = SparseSet::new_with_mapping(vec![-5, -10, -2], mapping_function);
421        sparse_set.remove_temporarily(&-10);
422        assert!(!sparse_set.contains(&-10));
423
424        sparse_set.remove_temporarily(&-2);
425        assert!(!sparse_set.contains(&-2));
426
427        sparse_set.remove_temporarily(&-5);
428
429        assert!(sparse_set.is_empty());
430    }
431}
pumpkin_core/containers/sparse_set.rs

pumpkin_core/containers/
sparse_set.rs
