1 use std::fmt; 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 /// 11 /// The data structure is based on: https://research.swtch.com/sparse 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. 15 #[derive(Clone)] 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 { new(size: usize) -> SparseSet28 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 len(&self) -> usize35 pub fn len(&self) -> usize { 36 self.dense.len() 37 } 38 is_empty(&self) -> bool39 pub fn is_empty(&self) -> bool { 40 self.dense.is_empty() 41 } 42 capacity(&self) -> usize43 pub fn capacity(&self) -> usize { 44 self.dense.capacity() 45 } 46 insert(&mut self, value: usize)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 contains(&self, value: usize) -> bool54 pub fn contains(&self, value: usize) -> bool { 55 let i = self.sparse[value]; 56 self.dense.get(i) == Some(&value) 57 } 58 clear(&mut self)59 pub fn clear(&mut self) { 60 self.dense.clear(); 61 } 62 } 63 64 impl fmt::Debug for SparseSet { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result65 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 66 write!(f, "SparseSet({:?})", self.dense) 67 } 68 } 69 70 impl Deref for SparseSet { 71 type Target = [usize]; 72 deref(&self) -> &Self::Target73 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>; into_iter(self) -> Self::IntoIter81 fn into_iter(self) -> Self::IntoIter { 82 self.iter() 83 } 84 } 85