1use 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)]
14pub 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
25impl SparseSet {
26 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
33 pub fn len(&self) -> usize {
34 self.dense.len()
35 }
36
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
44 pub fn contains(&self, value: usize) -> bool {
45 let i = self.sparse[value];
46 self.dense.get(i) == Some(&value)
47 }
48
49 pub fn clear(&mut self) {
50 self.dense.clear();
51 }
52}
53
54impl<'a> IntoIterator for &'a SparseSet {
55 type Item = &'a usize;
56 type IntoIter = slice::Iter<'a, usize>;
57 fn into_iter(self) -> Self::IntoIter {
58 self.dense.iter()
59 }
60}
61