1use std::fmt; 2use std::ops::Deref; 3use 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)] 16pub 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 27impl 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 64impl fmt::Debug for SparseSet { 65 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 66 write!(f, "SparseSet({:?})", self.dense) 67 } 68} 69 70impl Deref for SparseSet { 71 type Target = [usize]; 72 73 fn deref(&self) -> &Self::Target { 74 &self.dense 75 } 76} 77 78impl<'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} 85