itertools/
tuple_impl.rs

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,);
itertools/tuple_impl.rs

itertools/
tuple_impl.rs
