Haibo Huang | 0d330f2 | 2020-04-17 20:30:09 -0700 | [diff] [blame] | 1 | use std::fmt; |
Chih-Hung Hsieh | e42c505 | 2020-04-16 10:44:21 -0700 | [diff] [blame] | 2 | use std::ops::Deref; |
| 3 | use std::slice; |
| 4 | |
| 5 | /// A sparse set used for representing ordered NFA states. |
| 6 | /// |
| 7 | /// This supports constant time addition and membership testing. Clearing an |
| 8 | /// entire set can also be done in constant time. Iteration yields elements |
| 9 | /// in the order in which they were inserted. |
| 10 | /// |
Elliott Hughes | ffb6030 | 2021-04-01 17:11:40 -0700 | [diff] [blame^] | 11 | /// The data structure is based on: https://research.swtch.com/sparse |
Chih-Hung Hsieh | e42c505 | 2020-04-16 10:44:21 -0700 | [diff] [blame] | 12 | /// Note though that we don't actually use uninitialized memory. We generally |
| 13 | /// reuse allocations, so the initial allocation cost is bareable. However, |
| 14 | /// its other properties listed above are extremely useful. |
Haibo Huang | 0d330f2 | 2020-04-17 20:30:09 -0700 | [diff] [blame] | 15 | #[derive(Clone)] |
Chih-Hung Hsieh | e42c505 | 2020-04-16 10:44:21 -0700 | [diff] [blame] | 16 | pub struct SparseSet { |
| 17 | /// Dense contains the instruction pointers in the order in which they |
| 18 | /// were inserted. |
| 19 | dense: Vec<usize>, |
| 20 | /// Sparse maps instruction pointers to their location in dense. |
| 21 | /// |
| 22 | /// An instruction pointer is in the set if and only if |
| 23 | /// sparse[ip] < dense.len() && ip == dense[sparse[ip]]. |
| 24 | sparse: Box<[usize]>, |
| 25 | } |
| 26 | |
| 27 | impl SparseSet { |
| 28 | pub fn new(size: usize) -> SparseSet { |
| 29 | SparseSet { |
| 30 | dense: Vec::with_capacity(size), |
| 31 | sparse: vec![0; size].into_boxed_slice(), |
| 32 | } |
| 33 | } |
| 34 | |
| 35 | pub fn len(&self) -> usize { |
| 36 | self.dense.len() |
| 37 | } |
| 38 | |
| 39 | pub fn is_empty(&self) -> bool { |
| 40 | self.dense.is_empty() |
| 41 | } |
| 42 | |
| 43 | pub fn capacity(&self) -> usize { |
| 44 | self.dense.capacity() |
| 45 | } |
| 46 | |
| 47 | pub fn insert(&mut self, value: usize) { |
| 48 | let i = self.len(); |
| 49 | assert!(i < self.capacity()); |
| 50 | self.dense.push(value); |
| 51 | self.sparse[value] = i; |
| 52 | } |
| 53 | |
| 54 | pub fn contains(&self, value: usize) -> bool { |
| 55 | let i = self.sparse[value]; |
| 56 | self.dense.get(i) == Some(&value) |
| 57 | } |
| 58 | |
| 59 | pub fn clear(&mut self) { |
| 60 | self.dense.clear(); |
| 61 | } |
| 62 | } |
| 63 | |
Haibo Huang | 0d330f2 | 2020-04-17 20:30:09 -0700 | [diff] [blame] | 64 | impl fmt::Debug for SparseSet { |
| 65 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
| 66 | write!(f, "SparseSet({:?})", self.dense) |
| 67 | } |
| 68 | } |
| 69 | |
Chih-Hung Hsieh | e42c505 | 2020-04-16 10:44:21 -0700 | [diff] [blame] | 70 | impl Deref for SparseSet { |
| 71 | type Target = [usize]; |
| 72 | |
| 73 | fn deref(&self) -> &Self::Target { |
| 74 | &self.dense |
| 75 | } |
| 76 | } |
| 77 | |
| 78 | impl<'a> IntoIterator for &'a SparseSet { |
| 79 | type Item = &'a usize; |
| 80 | type IntoIter = slice::Iter<'a, usize>; |
| 81 | fn into_iter(self) -> Self::IntoIter { |
| 82 | self.iter() |
| 83 | } |
| 84 | } |