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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
//! Provides a simple iterator adaptor that buffers data from the
//! underlying iterator when needed. It will only read ahead when peek requests
//! are made, but it will only request each element from the source once. That
//! is, no matter how many positions of lookahead you allocate, they won't be
//! filled unless you need them, once you have seen them they will be buffered
//! until iterated to.
//!
//! This is a fundamental, low level component of lexical analyzers and of
//! parsers in general as well as many other systems.
/// LookAhead uses a statically allocated ring buffer to store it's data in, an
/// internal array of Options to make moving the data in and out easier.
///
/// C: How many positions are in the buffer, this should be 1+lookahead length,
/// that is C=2 means you get a current value and one lookahead token.
/// T: The type of the underlying items
/// U: The type of the underlying iterator, must implement Iterator with Type=T
pub struct LookAhead<const C: usize, T, U>
where
U: Iterator<Item=T> + Sized
{
iter: U,
data: [Option<T>;C],
cur: usize,
fill: usize,
}
impl<const C: usize, T, U> LookAhead<C,T,U>
where
U: Iterator<Item=T> + Sized
{
/// Create a new LookAhead Iterator wrapping the provided iterator.
///
/// This does nothing to the base iterator, it does not begin reading yet.
pub fn new(iter: U) -> Self {
Self {
iter,
data: [const {None};C],
cur: 0,
fill: 0,
}
}
/// Look ahead into the buffered look-ahead. If you exceed the size of the
/// internal buffer (C) then this will panic. This will fill the buffer to
/// the point requested if it is not already full. This will not advance
/// the iterator, so multiple calls to peek for the same position without
/// calling next() will provide the same value and will not affect the state
/// of the interior iterator.
pub fn peek(&mut self, offset: usize) -> Option<&T> {
assert!(offset<C);
self.fill_to( offset );
self.data[(self.cur+offset)%C].as_ref()
}
/// Fills the internal buffer to the requested level by calling next() on
/// the underlying iterator. This will call the underlying iterator for
/// each position to fill, even if the next() function has returned None.
/// It will simply fill the lookahead buffer with None values.
fn fill_to(&mut self, qty: usize) {
for i in self.fill..=qty {
if let Some(x) = self.iter.next() {
self.data[(self.cur+i)%C].replace( x );
self.fill += 1;
}
}
}
}
impl<const C: usize, T, U> std::iter::Iterator for LookAhead<C,T,U>
where
U: Iterator<Item=T> + Sized
{
type Item=T;
/// Follows the standard rules for an iterator. This will only call the
/// underlying iterator's next function if our lookahead buffer is empty.
/// Otherwise this is a pass-through. It does nothing special in the case
/// of a None response from the underlying iterator.
fn next(&mut self) -> Option<T> {
if self.fill == 0 {
self.iter.next()
} else {
let old = self.cur;
self.cur = (self.cur+1)%C;
self.fill -= 1;
self.data[old].take()
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn basic() {
let data = [1, 2, 3, 4, 5, 6, 7, 8];
let mut i = LookAhead::<3,_,_>::new(data.iter());
assert_eq!(i.next(), Some(&1));
assert_eq!(i.peek(1), Some(&&3));
assert_eq!(i.peek(0), Some(&&2));
assert_eq!(i.next(), Some(&2));
assert_eq!(i.peek(0), Some(&&3));
assert_eq!(i.next(), Some(&3));
assert_eq!(i.next(), Some(&4));
assert_eq!(i.next(), Some(&5));
assert_eq!(i.peek(0), Some(&&6));
assert_eq!(i.peek(1), Some(&&7));
assert_eq!(i.peek(2), Some(&&8));
assert_eq!(i.next(), Some(&6));
assert_eq!(i.peek(2), None);
assert_eq!(i.next(), Some(&7));
assert_eq!(i.peek(2), None);
assert_eq!(i.next(), Some(&8));
assert_eq!(i.next(), None);
}
}
|
