/rust/registry/src/index.crates.io-1949cf8c6b5b557f/regex-1.5.6/src/sparse.rs
Line | Count | Source |
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: 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)] |
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 { |
28 | 90 | pub fn new(size: usize) -> SparseSet { |
29 | 90 | SparseSet { |
30 | 90 | dense: Vec::with_capacity(size), |
31 | 90 | sparse: vec![0; size].into_boxed_slice(), |
32 | 90 | } |
33 | 90 | } <regex::sparse::SparseSet>::new Line | Count | Source | 28 | 54 | pub fn new(size: usize) -> SparseSet { | 29 | 54 | SparseSet { | 30 | 54 | dense: Vec::with_capacity(size), | 31 | 54 | sparse: vec![0; size].into_boxed_slice(), | 32 | 54 | } | 33 | 54 | } |
<regex::sparse::SparseSet>::new Line | Count | Source | 28 | 36 | pub fn new(size: usize) -> SparseSet { | 29 | 36 | SparseSet { | 30 | 36 | dense: Vec::with_capacity(size), | 31 | 36 | sparse: vec![0; size].into_boxed_slice(), | 32 | 36 | } | 33 | 36 | } |
|
34 | | |
35 | 0 | pub fn len(&self) -> usize { |
36 | 0 | self.dense.len() |
37 | 0 | } Unexecuted instantiation: <regex::sparse::SparseSet>::len Unexecuted instantiation: <regex::sparse::SparseSet>::len |
38 | | |
39 | 0 | pub fn is_empty(&self) -> bool { |
40 | 0 | self.dense.is_empty() |
41 | 0 | } Unexecuted instantiation: <regex::sparse::SparseSet>::is_empty Unexecuted instantiation: <regex::sparse::SparseSet>::is_empty |
42 | | |
43 | 0 | pub fn capacity(&self) -> usize { |
44 | 0 | self.dense.capacity() |
45 | 0 | } Unexecuted instantiation: <regex::sparse::SparseSet>::capacity Unexecuted instantiation: <regex::sparse::SparseSet>::capacity |
46 | | |
47 | 0 | pub fn insert(&mut self, value: usize) { |
48 | 0 | let i = self.len(); |
49 | 0 | assert!(i < self.capacity()); |
50 | 0 | self.dense.push(value); |
51 | 0 | self.sparse[value] = i; |
52 | 0 | } Unexecuted instantiation: <regex::sparse::SparseSet>::insert Unexecuted instantiation: <regex::sparse::SparseSet>::insert |
53 | | |
54 | 0 | pub fn contains(&self, value: usize) -> bool { |
55 | 0 | let i = self.sparse[value]; |
56 | 0 | self.dense.get(i) == Some(&value) |
57 | 0 | } Unexecuted instantiation: <regex::sparse::SparseSet>::contains Unexecuted instantiation: <regex::sparse::SparseSet>::contains |
58 | | |
59 | 0 | pub fn clear(&mut self) { |
60 | 0 | self.dense.clear(); |
61 | 0 | } Unexecuted instantiation: <regex::sparse::SparseSet>::clear Unexecuted instantiation: <regex::sparse::SparseSet>::clear |
62 | | } |
63 | | |
64 | | impl fmt::Debug for SparseSet { |
65 | 0 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
66 | 0 | write!(f, "SparseSet({:?})", self.dense) |
67 | 0 | } Unexecuted instantiation: <regex::sparse::SparseSet as core::fmt::Debug>::fmt Unexecuted instantiation: <regex::sparse::SparseSet as core::fmt::Debug>::fmt |
68 | | } |
69 | | |
70 | | impl Deref for SparseSet { |
71 | | type Target = [usize]; |
72 | | |
73 | 0 | fn deref(&self) -> &Self::Target { |
74 | 0 | &self.dense |
75 | 0 | } Unexecuted instantiation: <regex::sparse::SparseSet as core::ops::deref::Deref>::deref Unexecuted instantiation: <regex::sparse::SparseSet as core::ops::deref::Deref>::deref |
76 | | } |
77 | | |
78 | | impl<'a> IntoIterator for &'a SparseSet { |
79 | | type Item = &'a usize; |
80 | | type IntoIter = slice::Iter<'a, usize>; |
81 | 0 | fn into_iter(self) -> Self::IntoIter { |
82 | 0 | self.iter() |
83 | 0 | } Unexecuted instantiation: <®ex::sparse::SparseSet as core::iter::traits::collect::IntoIterator>::into_iter Unexecuted instantiation: <®ex::sparse::SparseSet as core::iter::traits::collect::IntoIterator>::into_iter |
84 | | } |