1//! Some iterator that produces tuples
2
3use std::iter::Fuse;
4use std::iter::FusedIterator;
5use std::iter::Take;
6use std::iter::Cycle;
7use 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.
15pub trait HomogeneousTuple
16 : TupleCollect
17{}
18
19impl<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)]
26pub struct TupleBuffer<T>
27 where T: HomogeneousTuple
28{
29 cur: usize,
30 buf: T::Buffer,
31}
32
33impl<T> TupleBuffer<T>
34 where T: HomogeneousTuple
35{
36 fn new(buf: T::Buffer) -> Self {
37 TupleBuffer {
38 cur: 0,
39 buf,
40 }
41 }
42}
43
44impl<T> Iterator for TupleBuffer<T>
45 where T: HomogeneousTuple
46{
47 type Item = T::Item;
48
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
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
72impl<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"]
82pub 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.
91pub 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
101impl<I, T> Iterator for Tuples<I, T>
102 where I: Iterator<Item = T::Item>,
103 T: HomogeneousTuple
104{
105 type Item = T;
106
107 fn next(&mut self) -> Option<Self::Item> {
108 T::collect_from_iter(&mut self.iter, &mut self.buf)
109 }
110}
111
112impl<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 /// ```
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)]
138pub 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.
147pub 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 iter,
166 last,
167 }
168}
169
170impl<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
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
191impl<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)]
205pub 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
213pub 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
227impl<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
234 fn next(&mut self) -> Option<Self::Item> {
235 self.iter.next()
236 }
237}
238
239pub trait TupleCollect: Sized {
240 type Item;
241 type Buffer: Default + AsRef<[Option<Self::Item>]> + AsMut<[Option<Self::Item>]>;
242
243 fn collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self>
244 where I: IntoIterator<Item = Self::Item>;
245
246 fn collect_from_iter_no_buf<I>(iter: I) -> Option<Self>
247 where I: IntoIterator<Item = Self::Item>;
248
249 fn num_items() -> usize;
250
251 fn left_shift_push(&mut self, item: Self::Item);
252}
253
254macro_rules! count_ident{
255 () => {0};
256 ($i0:ident, $($i:ident,)*) => {1 + count_ident!($($i,)*)};
257}
258macro_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
266macro_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}
331impl_tuple_collect!(dummy, a, b, c, d, e, f, g, h, i, j, k, l,);
332