1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
use std::iter::Enumerate;
use utils::{IntoTextIterator, TextIterator};
pub struct ShiftAnd {
m: usize,
masks: [u64; 256],
accept: u64,
}
impl ShiftAnd {
pub fn new<'a, P: IntoTextIterator<'a>>(pattern: P) -> Self where
P::IntoIter: ExactSizeIterator {
let pattern = pattern.into_iter();
let m = pattern.len();
assert!(m <= 64,
"Expecting a pattern of at most 64 symbols.");
let (masks, accept) = masks(pattern);
ShiftAnd {
m: m,
masks: masks,
accept: accept,
}
}
pub fn find_all<'a, I: IntoTextIterator<'a>>(&'a self, text: I) -> Matches<I::IntoIter> {
Matches {
shiftand: self,
active: 0,
text: text.into_iter().enumerate(),
}
}
}
pub fn masks<'a, I: IntoTextIterator<'a>>(pattern: I) -> ([u64; 256], u64) {
let mut masks = [0; 256];
let mut bit = 1;
for &c in pattern {
masks[c as usize] |= bit;
bit *= 2;
}
(masks, bit / 2)
}
pub struct Matches<'a, I: TextIterator<'a>> {
shiftand: &'a ShiftAnd,
active: u64,
text: Enumerate<I>,
}
impl<'a, I: Iterator<Item = &'a u8>> Iterator for Matches<'a, I> {
type Item = usize;
fn next(&mut self) -> Option<usize> {
for (i, &c) in self.text.by_ref() {
self.active = ((self.active << 1) | 1) & self.shiftand.masks[c as usize];
if self.active & self.shiftand.accept > 0 {
return Some(i - self.shiftand.m + 1);
}
}
None
}
}