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: http://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