1 //! Some iterator that produces tuples
2
3 use std::iter::Fuse;
4 use std::iter::FusedIterator;
5 use std::iter::Take;
6 use std::iter::Cycle;
7 use std::marker::PhantomData;
8
9 // `HomogeneousTuple` is a public facade for `TupleCollect`, allowing
10 // tuple-related methods to be used by clients in generic contexts, while
11 // hiding the implementation details of `TupleCollect`.
12 // See https://github.com/rust-itertools/itertools/issues/387
13
14 /// Implemented for homogeneous tuples of size up to 12.
15 pub trait HomogeneousTuple
16 : TupleCollect
17 {}
18
19 impl<T: TupleCollect> HomogeneousTuple for T {}
20
21 /// An iterator over a incomplete tuple.
22 ///
23 /// See [`.tuples()`](crate::Itertools::tuples) and
24 /// [`Tuples::into_buffer()`].
25 #[derive(Clone, Debug)]
26 pub struct TupleBuffer<T>
27 where T: HomogeneousTuple
28 {
29 cur: usize,
30 buf: T::Buffer,
31 }
32
33 impl<T> TupleBuffer<T>
34 where T: HomogeneousTuple
35 {
new(buf: T::Buffer) -> Self36 fn new(buf: T::Buffer) -> Self {
37 TupleBuffer {
38 cur: 0,
39 buf,
40 }
41 }
42 }
43
44 impl<T> Iterator for TupleBuffer<T>
45 where T: HomogeneousTuple
46 {
47 type Item = T::Item;
48
next(&mut self) -> Option<Self::Item>49 fn next(&mut self) -> Option<Self::Item> {
50 let s = self.buf.as_mut();
51 if let Some(ref mut item) = s.get_mut(self.cur) {
52 self.cur += 1;
53 item.take()
54 } else {
55 None
56 }
57 }
58
size_hint(&self) -> (usize, Option<usize>)59 fn size_hint(&self) -> (usize, Option<usize>) {
60 let buffer = &self.buf.as_ref()[self.cur..];
61 let len = if buffer.is_empty() {
62 0
63 } else {
64 buffer.iter()
65 .position(|x| x.is_none())
66 .unwrap_or_else(|| buffer.len())
67 };
68 (len, Some(len))
69 }
70 }
71
72 impl<T> ExactSizeIterator for TupleBuffer<T>
73 where T: HomogeneousTuple
74 {
75 }
76
77 /// An iterator that groups the items in tuples of a specific size.
78 ///
79 /// See [`.tuples()`](crate::Itertools::tuples) for more information.
80 #[derive(Clone, Debug)]
81 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
82 pub struct Tuples<I, T>
83 where I: Iterator<Item = T::Item>,
84 T: HomogeneousTuple
85 {
86 iter: Fuse<I>,
87 buf: T::Buffer,
88 }
89
90 /// Create a new tuples iterator.
tuples<I, T>(iter: I) -> Tuples<I, T> where I: Iterator<Item = T::Item>, T: HomogeneousTuple91 pub fn tuples<I, T>(iter: I) -> Tuples<I, T>
92 where I: Iterator<Item = T::Item>,
93 T: HomogeneousTuple
94 {
95 Tuples {
96 iter: iter.fuse(),
97 buf: Default::default(),
98 }
99 }
100
101 impl<I, T> Iterator for Tuples<I, T>
102 where I: Iterator<Item = T::Item>,
103 T: HomogeneousTuple
104 {
105 type Item = T;
106
next(&mut self) -> Option<Self::Item>107 fn next(&mut self) -> Option<Self::Item> {
108 T::collect_from_iter(&mut self.iter, &mut self.buf)
109 }
110 }
111
112 impl<I, T> Tuples<I, T>
113 where I: Iterator<Item = T::Item>,
114 T: HomogeneousTuple
115 {
116 /// Return a buffer with the produced items that was not enough to be grouped in a tuple.
117 ///
118 /// ```
119 /// use itertools::Itertools;
120 ///
121 /// let mut iter = (0..5).tuples();
122 /// assert_eq!(Some((0, 1, 2)), iter.next());
123 /// assert_eq!(None, iter.next());
124 /// itertools::assert_equal(vec![3, 4], iter.into_buffer());
125 /// ```
into_buffer(self) -> TupleBuffer<T>126 pub fn into_buffer(self) -> TupleBuffer<T> {
127 TupleBuffer::new(self.buf)
128 }
129 }
130
131
132 /// An iterator over all contiguous windows that produces tuples of a specific size.
133 ///
134 /// See [`.tuple_windows()`](crate::Itertools::tuple_windows) for more
135 /// information.
136 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
137 #[derive(Clone, Debug)]
138 pub struct TupleWindows<I, T>
139 where I: Iterator<Item = T::Item>,
140 T: HomogeneousTuple
141 {
142 iter: I,
143 last: Option<T>,
144 }
145
146 /// Create a new tuple windows iterator.
tuple_windows<I, T>(mut iter: I) -> TupleWindows<I, T> where I: Iterator<Item = T::Item>, T: HomogeneousTuple, T::Item: Clone147 pub fn tuple_windows<I, T>(mut iter: I) -> TupleWindows<I, T>
148 where I: Iterator<Item = T::Item>,
149 T: HomogeneousTuple,
150 T::Item: Clone
151 {
152 use std::iter::once;
153
154 let mut last = None;
155 if T::num_items() != 1 {
156 // put in a duplicate item in front of the tuple; this simplifies
157 // .next() function.
158 if let Some(item) = iter.next() {
159 let iter = once(item.clone()).chain(once(item)).chain(&mut iter);
160 last = T::collect_from_iter_no_buf(iter);
161 }
162 }
163
164 TupleWindows {
165 last,
166 iter,
167 }
168 }
169
170 impl<I, T> Iterator for TupleWindows<I, T>
171 where I: Iterator<Item = T::Item>,
172 T: HomogeneousTuple + Clone,
173 T::Item: Clone
174 {
175 type Item = T;
176
next(&mut self) -> Option<Self::Item>177 fn next(&mut self) -> Option<Self::Item> {
178 if T::num_items() == 1 {
179 return T::collect_from_iter_no_buf(&mut self.iter)
180 }
181 if let Some(ref mut last) = self.last {
182 if let Some(new) = self.iter.next() {
183 last.left_shift_push(new);
184 return Some(last.clone());
185 }
186 }
187 None
188 }
189 }
190
191 impl<I, T> FusedIterator for TupleWindows<I, T>
192 where I: FusedIterator<Item = T::Item>,
193 T: HomogeneousTuple + Clone,
194 T::Item: Clone
195 {}
196
197 /// An iterator over all windows,wrapping back to the first elements when the
198 /// window would otherwise exceed the length of the iterator, producing tuples
199 /// of a specific size.
200 ///
201 /// See [`.circular_tuple_windows()`](crate::Itertools::circular_tuple_windows) for more
202 /// information.
203 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
204 #[derive(Debug)]
205 pub struct CircularTupleWindows<I, T: Clone>
206 where I: Iterator<Item = T::Item> + Clone,
207 T: TupleCollect + Clone
208 {
209 iter: Take<TupleWindows<Cycle<I>, T>>,
210 phantom_data: PhantomData<T>
211 }
212
circular_tuple_windows<I, T>(iter: I) -> CircularTupleWindows<I, T> where I: Iterator<Item = T::Item> + Clone + ExactSizeIterator, T: TupleCollect + Clone, T::Item: Clone213 pub fn circular_tuple_windows<I, T>(iter: I) -> CircularTupleWindows<I, T>
214 where I: Iterator<Item = T::Item> + Clone + ExactSizeIterator,
215 T: TupleCollect + Clone,
216 T::Item: Clone
217 {
218 let len = iter.len();
219 let iter = tuple_windows(iter.cycle()).take(len);
220
221 CircularTupleWindows {
222 iter,
223 phantom_data: PhantomData{}
224 }
225 }
226
227 impl<I, T> Iterator for CircularTupleWindows<I, T>
228 where I: Iterator<Item = T::Item> + Clone,
229 T: TupleCollect + Clone,
230 T::Item: Clone
231 {
232 type Item = T;
233
next(&mut self) -> Option<Self::Item>234 fn next(&mut self) -> Option<Self::Item> {
235 self.iter.next()
236 }
237 }
238
239 pub trait TupleCollect: Sized {
240 type Item;
241 type Buffer: Default + AsRef<[Option<Self::Item>]> + AsMut<[Option<Self::Item>]>;
242
collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self> where I: IntoIterator<Item = Self::Item>243 fn collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self>
244 where I: IntoIterator<Item = Self::Item>;
245
collect_from_iter_no_buf<I>(iter: I) -> Option<Self> where I: IntoIterator<Item = Self::Item>246 fn collect_from_iter_no_buf<I>(iter: I) -> Option<Self>
247 where I: IntoIterator<Item = Self::Item>;
248
num_items() -> usize249 fn num_items() -> usize;
250
left_shift_push(&mut self, item: Self::Item)251 fn left_shift_push(&mut self, item: Self::Item);
252 }
253
254 macro_rules! count_ident{
255 () => {0};
256 ($i0:ident, $($i:ident,)*) => {1 + count_ident!($($i,)*)};
257 }
258 macro_rules! rev_for_each_ident{
259 ($m:ident, ) => {};
260 ($m:ident, $i0:ident, $($i:ident,)*) => {
261 rev_for_each_ident!($m, $($i,)*);
262 $m!($i0);
263 };
264 }
265
266 macro_rules! impl_tuple_collect {
267 ($dummy:ident,) => {}; // stop
268 ($dummy:ident, $($Y:ident,)*) => (
269 impl_tuple_collect!($($Y,)*);
270 impl<A> TupleCollect for ($(ignore_ident!($Y, A),)*) {
271 type Item = A;
272 type Buffer = [Option<A>; count_ident!($($Y,)*) - 1];
273
274 #[allow(unused_assignments, unused_mut)]
275 fn collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self>
276 where I: IntoIterator<Item = A>
277 {
278 let mut iter = iter.into_iter();
279 $(
280 let mut $Y = None;
281 )*
282
283 loop {
284 $(
285 $Y = iter.next();
286 if $Y.is_none() {
287 break
288 }
289 )*
290 return Some(($($Y.unwrap()),*,))
291 }
292
293 let mut i = 0;
294 let mut s = buf.as_mut();
295 $(
296 if i < s.len() {
297 s[i] = $Y;
298 i += 1;
299 }
300 )*
301 return None;
302 }
303
304 fn collect_from_iter_no_buf<I>(iter: I) -> Option<Self>
305 where I: IntoIterator<Item = A>
306 {
307 let mut iter = iter.into_iter();
308
309 Some(($(
310 { let $Y = iter.next()?; $Y },
311 )*))
312 }
313
314 fn num_items() -> usize {
315 count_ident!($($Y,)*)
316 }
317
318 fn left_shift_push(&mut self, mut item: A) {
319 use std::mem::replace;
320
321 let &mut ($(ref mut $Y),*,) = self;
322 macro_rules! replace_item{($i:ident) => {
323 item = replace($i, item);
324 }}
325 rev_for_each_ident!(replace_item, $($Y,)*);
326 drop(item);
327 }
328 }
329 )
330 }
331 impl_tuple_collect!(dummy, a, b, c, d, e, f, g, h, i, j, k, l,);
332