token_deque/
iterators.rs

1use crate::deque::Deque;
2use std::usize;
3
4/// An iterator over the deque starting from the front. It is
5/// constructed from the [`iter_front`] method on `Deque`.
6///
7/// [`iter_front`]: struct.Deque.html#method.iter_front
8pub struct IterFront<'l, T> {
9    target: &'l Deque<T>,
10    next_index: usize,
11}
12
13impl<'l, T> IterFront<'l, T> {
14    pub(crate) fn new(target: &'l Deque<T>, next_index: usize) -> Self {
15        Self { target, next_index }
16    }
17}
18
19impl<'l, T> Iterator for IterFront<'l, T> {
20    type Item = &'l T;
21
22    fn next(&mut self) -> Option<Self::Item> {
23        if usize::MAX != self.next_index {
24            let r = self.target.slots[self.next_index]
25                .get_used()
26                .expect("self.target.slots[self.next_index] is expected to be used");
27            self.next_index = r.back();
28            Some(r.data())
29        } else {
30            None
31        }
32    }
33}
34
35/// An iterator over the deque starting from the back. It is
36/// constructed from the [`iter_back`] method on `Deque`.
37///
38/// [`iter_back`]: struct.Deque.html#method.iter_back
39pub struct IterBack<'l, T> {
40    target: &'l Deque<T>,
41    next_index: usize,
42}
43
44impl<'l, T> IterBack<'l, T> {
45    pub(crate) fn new(target: &'l Deque<T>, next_index: usize) -> Self {
46        Self { target, next_index }
47    }
48}
49
50impl<'l, T> Iterator for IterBack<'l, T> {
51    type Item = &'l T;
52
53    fn next(&mut self) -> Option<Self::Item> {
54        if usize::MAX != self.next_index {
55            let r = &self.target.slots[self.next_index]
56                .get_used()
57                .expect("self.target.slots[self.next_index] is expected to be used");
58            self.next_index = r.front();
59            Some(r.data())
60        } else {
61            None
62        }
63    }
64}
65
66/// A draining iterator over the deque starting from the front. It is
67/// constructed from the [`drain_front`] method on `Deque`.
68///
69/// [`drain_front`]: struct.Deque.html#method.drain_front
70pub struct DrainFront<'l, T> {
71    target: &'l mut Deque<T>,
72    next_index: usize,
73}
74
75impl<'l, T> DrainFront<'l, T> {
76    pub(crate) fn new(target: &'l mut Deque<T>, next_index: usize) -> Self {
77        Self { target, next_index }
78    }
79}
80
81impl<'l, T> Iterator for DrainFront<'l, T> {
82    type Item = T;
83
84    fn next(&mut self) -> Option<Self::Item> {
85        if usize::MAX != self.next_index {
86            let r = self.target.free(self.next_index);
87            let (_, value, back) = r
88                .into_used()
89                .expect("self.target.slots[self.next_index] is expected to be used")
90                .take();
91            self.next_index = back;
92            Some(value)
93        } else {
94            None
95        }
96    }
97}
98
99/// A draining iterator over the deque starting from the front. It is
100/// constructed from the [`drain_back`] method on `Deque`.
101///
102/// [`drain_back`]: struct.Deque.html#method.drain_back
103pub struct DrainBack<'l, T> {
104    target: &'l mut Deque<T>,
105    next_index: usize,
106}
107
108impl<'l, T> DrainBack<'l, T> {
109    pub(crate) fn new(target: &'l mut Deque<T>, next_index: usize) -> Self {
110        Self { target, next_index }
111    }
112}
113
114impl<'l, T> Iterator for DrainBack<'l, T> {
115    type Item = T;
116
117    fn next(&mut self) -> Option<Self::Item> {
118        if usize::MAX != self.next_index {
119            let r = self.target.free(self.next_index);
120            let (front, value, _) = r
121                .into_used()
122                .expect("self.target.slots[self.next_index] is expected to be used")
123                .take();
124            self.next_index = front;
125            Some(value)
126        } else {
127            None
128        }
129    }
130}
131
132#[cfg(test)]
133mod test {
134    use super::*;
135
136    #[test]
137    fn filter_can_find_items() {
138        let mut l = Deque::new();
139        l.push_front(10u8);
140        l.push_front(11u8);
141        l.push_front(12u8);
142
143        assert_eq!(Some(&10), l.iter_front().filter(|i| **i == 10).next());
144        assert_eq!(Some(&11), l.iter_front().filter(|i| **i == 11).next());
145        assert_eq!(Some(&12), l.iter_front().filter(|i| **i == 12).next());
146        assert_eq!(None, l.iter_front().filter(|i| **i == 13).next());
147    }
148
149    #[test]
150    fn iterator_filter_can_find_duplicates() {
151        let mut l = Deque::new();
152        l.push_back(10u8);
153        l.push_back(11u8);
154        l.push_back(12u8);
155        l.push_back(13u8);
156        l.push_back(14u8);
157
158        let mut s = l.iter_front().filter(|i| 0 == *i % 2);
159
160        assert_eq!(Some(&10), s.next());
161        assert_eq!(Some(&12), s.next());
162        assert_eq!(Some(&14), s.next());
163        assert_eq!(None, s.next());
164
165        let mut s = l.iter_back().filter(|i| 0 == *i % 2);
166
167        assert_eq!(Some(&14), s.next());
168        assert_eq!(Some(&12), s.next());
169        assert_eq!(Some(&10), s.next());
170        assert_eq!(None, s.next());
171    }
172
173    #[test]
174    fn iters_finds_everything() {
175        let mut l = Deque::new();
176        l.push_front(10u8);
177        let tok = l.push_front(11u8);
178        l.push_front(12u8);
179
180        assert_eq!(vec![&12, &11, &10], l.iter_front().collect::<Vec<&u8>>());
181        assert_eq!(vec![&10, &11, &12], l.iter_back().collect::<Vec<&u8>>());
182
183        l.remove(&tok);
184
185        assert_eq!(vec![&12, &10], l.iter_front().collect::<Vec<&u8>>());
186        assert_eq!(vec![&10, &12], l.iter_back().collect::<Vec<&u8>>());
187    }
188
189    #[test]
190    fn drains_find_everything_and_leave_slots_free() {
191        let mut l = Deque::new();
192        l.push_front(10u8);
193        l.push_front(11u8);
194        l.push_front(12u8);
195
196        assert_eq!(0, l.len_freelist());
197        assert_eq!(vec![12, 11, 10], l.drain_front().collect::<Vec<u8>>());
198        assert_eq!(3, l.len_freelist());
199
200        let mut l = Deque::new();
201        l.push_front(10u8);
202        l.push_front(11u8);
203        l.push_front(12u8);
204
205        assert_eq!(0, l.len_freelist());
206        assert_eq!(vec![10, 11, 12], l.drain_back().collect::<Vec<u8>>());
207        assert_eq!(3, l.len_freelist());
208    }
209}
token_deque/iterators.rs

token_deque/
iterators.rs
