1 use std::slice; 2 3 /// A sparse set used for representing ordered NFA states. 4 /// 5 /// This supports constant time addition and membership testing. Clearing an 6 /// entire set can also be done in constant time. Iteration yields elements 7 /// in the order in which they were inserted. 8 /// 9 /// The data structure is based on: https://research.swtch.com/sparse 10 /// Note though that we don't actually use uninitialized memory. We generally 11 /// reuse sparse sets, so the initial allocation cost is bareable. However, its 12 /// other properties listed above are extremely useful. 13 #[derive(Clone, Debug)] 14 pub struct SparseSet { 15 /// Dense contains the instruction pointers in the order in which they 16 /// were inserted. 17 dense: Vec<usize>, 18 /// Sparse maps instruction pointers to their location in dense. 19 /// 20 /// An instruction pointer is in the set if and only if 21 /// sparse[ip] < dense.len() && ip == dense[sparse[ip]]. 22 sparse: Box<[usize]>, 23 } 24 25 impl SparseSet { new(size: usize) -> SparseSet26 pub fn new(size: usize) -> SparseSet { 27 SparseSet { 28 dense: Vec::with_capacity(size), 29 sparse: vec![0; size].into_boxed_slice(), 30 } 31 } 32 len(&self) -> usize33 pub fn len(&self) -> usize { 34 self.dense.len() 35 } 36 insert(&mut self, value: usize)37 pub fn insert(&mut self, value: usize) { 38 let i = self.len(); 39 assert!(i < self.dense.capacity()); 40 self.dense.push(value); 41 self.sparse[value] = i; 42 } 43 contains(&self, value: usize) -> bool44 pub fn contains(&self, value: usize) -> bool { 45 let i = self.sparse[value]; 46 self.dense.get(i) == Some(&value) 47 } 48 clear(&mut self)49 pub fn clear(&mut self) { 50 self.dense.clear(); 51 } 52 } 53 54 impl<'a> IntoIterator for &'a SparseSet { 55 type Item = &'a usize; 56 type IntoIter = slice::Iter<'a, usize>; into_iter(self) -> Self::IntoIter57 fn into_iter(self) -> Self::IntoIter { 58 self.dense.iter() 59 } 60 } 61