pushback_iter/
lib.rs

1//! This create providers an implementation of `PushBackIterator` which is a
2//! wrapper around an iterator which allows for items to be pushed back onto
3//! the iterator to be consumed on subsequent call to `next()`.
4//!
5//! ```
6//! use pushback_iter::PushBackIterator;
7//!
8//! let items = vec![1, 2, 3];
9//! let mut iter = PushBackIterator::from(items.into_iter());
10//!
11//! let item = iter.next().unwrap();
12//! assert_eq!(item, 1);
13//!
14//! iter.push_back(item);
15//! assert_eq!(iter.next(), Some(1));
16//!
17//! iter.push_back(6);
18//! iter.push_back(5);
19//! assert_eq!(iter.next(), Some(5));
20//! assert_eq!(iter.next(), Some(6));
21//! assert_eq!(iter.next(), Some(2));
22//! ```
23
24#![deny(
25    missing_docs,
26    missing_debug_implementations,
27    unreachable_pub,
28    broken_intra_doc_links
29)]
30#![warn(rust_2018_idioms)]
31
32use std::collections::VecDeque;
33
34/// An iterator with a `push_back(item)` method that allows
35/// items to be pushed back onto the iterator.
36///
37/// [`Iterator`]: trait.Iterator.html
38#[derive(Debug, Clone)]
39pub struct PushBackIterator<I: Iterator> {
40    buffer: VecDeque<I::Item>,
41    inner: I,
42}
43
44impl<I: Iterator> PushBackIterator<I> {
45    /// Push back an item to the beginning of the iterator.
46    ///
47    /// Items pushed back onto the iterator are returned from [`next`] in a
48    /// last-in-first out basis.
49    pub fn push_back(&mut self, item: I::Item) {
50        self.buffer.push_back(item)
51    }
52
53    /// Returns a reference to the next() value without advancing the iterator.
54    ///
55    /// Like [`next`], if there is a value, it is wrapped in a `Some(T)`.
56    /// But if the iteration is over, `None` is returned.
57    #[inline]
58    pub fn peek(&mut self) -> Option<&I::Item> {
59        self.peek_nth(0)
60    }
61
62    /// Returns a reference to the nth(n) value without advancing the iterator.
63    ///
64    /// Like [`nth`], if there is a value, it is wrapped in a `Some(T)`.
65    /// But if the iteration is over, `None` is returned.
66    pub fn peek_nth(&mut self, n: usize) -> Option<&I::Item> {
67        if n >= self.buffer.len() {
68            for _ in 0..=(n - self.buffer.len()) {
69                self.buffer.push_front(self.inner.next()?);
70            }
71        }
72        Some(&self.buffer[self.buffer.len() - n - 1])
73    }
74
75    /// Reserves capacity for at least `additional` more elements in the push back buffer
76    ///
77    /// # Panics
78    ///
79    /// Panics if the new capacity overflows `usize`.
80    ///
81    pub fn reserve(&mut self, additional: usize) {
82        self.buffer.reserve(additional)
83    }
84
85    /// Shrinks the capacity of the buffer as much as possible.
86    ///
87    pub fn shrink_to_fit(&mut self) {
88        self.buffer.shrink_to_fit()
89    }
90}
91
92impl<I: Iterator> From<I> for PushBackIterator<I> {
93    fn from(inner: I) -> Self {
94        PushBackIterator {
95            buffer: VecDeque::new(),
96            inner,
97        }
98    }
99}
100
101impl<I: Iterator> Iterator for PushBackIterator<I> {
102    type Item = I::Item;
103
104    fn next(&mut self) -> Option<Self::Item> {
105        self.buffer.pop_back().or_else(|| self.inner.next())
106    }
107
108    fn size_hint(&self) -> (usize, Option<usize>) {
109        let (lower, upper) = self.inner.size_hint();
110        (
111            lower + self.buffer.len(),
112            upper.map(|upper| upper + self.buffer.len()),
113        )
114    }
115
116    fn count(self) -> usize
117    where
118        Self: Sized,
119    {
120        self.buffer.len() + self.inner.count()
121    }
122
123    fn last(self) -> Option<Self::Item>
124    where
125        Self: Sized,
126    {
127        self.inner.last()
128    }
129
130    fn nth(&mut self, n: usize) -> Option<Self::Item> {
131        if n < self.buffer.len() {
132            self.buffer.truncate(self.buffer.len() - n);
133            self.buffer.pop_back()
134        } else {
135            let n = n - self.buffer.len();
136            self.buffer.clear();
137            self.inner.nth(n)
138        }
139    }
140}
141
142impl<I: ExactSizeIterator> ExactSizeIterator for PushBackIterator<I> {
143    fn len(&self) -> usize {
144        self.buffer.len() + self.inner.len()
145    }
146}
147
148impl<I: DoubleEndedIterator> DoubleEndedIterator for PushBackIterator<I> {
149    fn next_back(&mut self) -> Option<Self::Item> {
150        self.inner.next_back().or_else(|| self.buffer.pop_front())
151    }
152}
153
154#[cfg(test)]
155mod tests {
156    use super::*;
157
158    #[test]
159    fn push_back() {
160        let items = vec![0, 1, 2, 3];
161        let mut iter = PushBackIterator::from(items.into_iter());
162        assert_eq!(iter.next(), Some(0));
163        assert_eq!(iter.next(), Some(1));
164        iter.push_back(1);
165        assert_eq!(iter.next(), Some(1));
166        assert_eq!(iter.next(), Some(2));
167        iter.push_back(2);
168        iter.push_back(1);
169        assert_eq!(iter.next(), Some(1));
170        assert_eq!(iter.next(), Some(2));
171
172        assert_eq!(iter.next(), Some(3));
173        assert_eq!(iter.next(), None);
174
175        iter.push_back(0);
176        assert_eq!(iter.next(), Some(0));
177        assert_eq!(iter.next(), None);
178    }
179
180    #[test]
181    fn peek_nth() {
182        let items = vec![0, 1, 2, 3, 4, 5];
183        let mut iter = PushBackIterator::from(items.into_iter());
184        assert_eq!(iter.peek_nth(2), Some(&2));
185        assert_eq!(iter.peek_nth(2), Some(&2));
186        assert_eq!(iter.next(), Some(0));
187        assert_eq!(iter.peek_nth(2), Some(&3));
188        iter.push_back(0);
189        assert_eq!(iter.peek_nth(2), Some(&2));
190        assert_eq!(iter.next(), Some(0));
191        assert_eq!(iter.next(), Some(1));
192        assert_eq!(iter.next(), Some(2));
193        assert_eq!(iter.next(), Some(3));
194    }
195}
pushback_iter/lib.rs

pushback_iter/
lib.rs
