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