1 //! Some iterator that produces tuples
2
3 use std::iter::Fuse;
4
5 // `HomogeneousTuple` is a public facade for `TupleCollect`, allowing
6 // tuple-related methods to be used by clients in generic contexts, while
7 // hiding the implementation details of `TupleCollect`.
8 // See https://github.com/rust-itertools/itertools/issues/387
9
10 /// Implemented for homogeneous tuples of size up to 4.
11 pub trait HomogeneousTuple
12 : TupleCollect
13 {}
14
15 impl<T: TupleCollect> HomogeneousTuple for T {}
16
17 /// An iterator over a incomplete tuple.
18 ///
19 /// See [`.tuples()`](../trait.Itertools.html#method.tuples) and
20 /// [`Tuples::into_buffer()`](struct.Tuples.html#method.into_buffer).
21 #[derive(Clone, Debug)]
22 pub struct TupleBuffer<T>
23 where T: HomogeneousTuple
24 {
25 cur: usize,
26 buf: T::Buffer,
27 }
28
29 impl<T> TupleBuffer<T>
30 where T: HomogeneousTuple
31 {
new(buf: T::Buffer) -> Self32 fn new(buf: T::Buffer) -> Self {
33 TupleBuffer {
34 cur: 0,
35 buf,
36 }
37 }
38 }
39
40 impl<T> Iterator for TupleBuffer<T>
41 where T: HomogeneousTuple
42 {
43 type Item = T::Item;
44
next(&mut self) -> Option<Self::Item>45 fn next(&mut self) -> Option<Self::Item> {
46 let s = self.buf.as_mut();
47 if let Some(ref mut item) = s.get_mut(self.cur) {
48 self.cur += 1;
49 item.take()
50 } else {
51 None
52 }
53 }
54
size_hint(&self) -> (usize, Option<usize>)55 fn size_hint(&self) -> (usize, Option<usize>) {
56 let buffer = &self.buf.as_ref()[self.cur..];
57 let len = if buffer.len() == 0 {
58 0
59 } else {
60 buffer.iter()
61 .position(|x| x.is_none())
62 .unwrap_or(buffer.len())
63 };
64 (len, Some(len))
65 }
66 }
67
68 impl<T> ExactSizeIterator for TupleBuffer<T>
69 where T: HomogeneousTuple
70 {
71 }
72
73 /// An iterator that groups the items in tuples of a specific size.
74 ///
75 /// See [`.tuples()`](../trait.Itertools.html#method.tuples) for more information.
76 #[derive(Clone)]
77 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
78 pub struct Tuples<I, T>
79 where I: Iterator<Item = T::Item>,
80 T: HomogeneousTuple
81 {
82 iter: Fuse<I>,
83 buf: T::Buffer,
84 }
85
86 /// Create a new tuples iterator.
tuples<I, T>(iter: I) -> Tuples<I, T> where I: Iterator<Item = T::Item>, T: HomogeneousTuple87 pub fn tuples<I, T>(iter: I) -> Tuples<I, T>
88 where I: Iterator<Item = T::Item>,
89 T: HomogeneousTuple
90 {
91 Tuples {
92 iter: iter.fuse(),
93 buf: Default::default(),
94 }
95 }
96
97 impl<I, T> Iterator for Tuples<I, T>
98 where I: Iterator<Item = T::Item>,
99 T: HomogeneousTuple
100 {
101 type Item = T;
102
next(&mut self) -> Option<T>103 fn next(&mut self) -> Option<T> {
104 T::collect_from_iter(&mut self.iter, &mut self.buf)
105 }
106 }
107
108 impl<I, T> Tuples<I, T>
109 where I: Iterator<Item = T::Item>,
110 T: HomogeneousTuple
111 {
112 /// Return a buffer with the produced items that was not enough to be grouped in a tuple.
113 ///
114 /// ```
115 /// use itertools::Itertools;
116 ///
117 /// let mut iter = (0..5).tuples();
118 /// assert_eq!(Some((0, 1, 2)), iter.next());
119 /// assert_eq!(None, iter.next());
120 /// itertools::assert_equal(vec![3, 4], iter.into_buffer());
121 /// ```
into_buffer(self) -> TupleBuffer<T>122 pub fn into_buffer(self) -> TupleBuffer<T> {
123 TupleBuffer::new(self.buf)
124 }
125 }
126
127
128 /// An iterator over all contiguous windows that produces tuples of a specific size.
129 ///
130 /// See [`.tuple_windows()`](../trait.Itertools.html#method.tuple_windows) for more
131 /// information.
132 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
133 #[derive(Clone, Debug)]
134 pub struct TupleWindows<I, T>
135 where I: Iterator<Item = T::Item>,
136 T: HomogeneousTuple
137 {
138 iter: I,
139 last: Option<T>,
140 }
141
142 /// 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: Clone143 pub fn tuple_windows<I, T>(mut iter: I) -> TupleWindows<I, T>
144 where I: Iterator<Item = T::Item>,
145 T: HomogeneousTuple,
146 T::Item: Clone
147 {
148 use std::iter::once;
149
150 let mut last = None;
151 if T::num_items() != 1 {
152 // put in a duplicate item in front of the tuple; this simplifies
153 // .next() function.
154 if let Some(item) = iter.next() {
155 let iter = once(item.clone()).chain(once(item)).chain(&mut iter);
156 last = T::collect_from_iter_no_buf(iter);
157 }
158 }
159
160 TupleWindows {
161 last,
162 iter,
163 }
164 }
165
166 impl<I, T> Iterator for TupleWindows<I, T>
167 where I: Iterator<Item = T::Item>,
168 T: HomogeneousTuple + Clone,
169 T::Item: Clone
170 {
171 type Item = T;
172
next(&mut self) -> Option<T>173 fn next(&mut self) -> Option<T> {
174 if T::num_items() == 1 {
175 return T::collect_from_iter_no_buf(&mut self.iter)
176 }
177 if let Some(ref mut last) = self.last {
178 if let Some(new) = self.iter.next() {
179 last.left_shift_push(new);
180 return Some(last.clone());
181 }
182 }
183 None
184 }
185 }
186
187 pub trait TupleCollect: Sized {
188 type Item;
189 type Buffer: Default + AsRef<[Option<Self::Item>]> + AsMut<[Option<Self::Item>]>;
190
collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self> where I: IntoIterator<Item = Self::Item>191 fn collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self>
192 where I: IntoIterator<Item = Self::Item>;
193
collect_from_iter_no_buf<I>(iter: I) -> Option<Self> where I: IntoIterator<Item = Self::Item>194 fn collect_from_iter_no_buf<I>(iter: I) -> Option<Self>
195 where I: IntoIterator<Item = Self::Item>;
196
num_items() -> usize197 fn num_items() -> usize;
198
left_shift_push(&mut self, item: Self::Item)199 fn left_shift_push(&mut self, item: Self::Item);
200 }
201
202 macro_rules! impl_tuple_collect {
203 () => ();
204 ($N:expr; $A:ident ; $($X:ident),* ; $($Y:ident),* ; $($Y_rev:ident),*) => (
205 impl<$A> TupleCollect for ($($X),*,) {
206 type Item = $A;
207 type Buffer = [Option<$A>; $N - 1];
208
209 #[allow(unused_assignments, unused_mut)]
210 fn collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self>
211 where I: IntoIterator<Item = $A>
212 {
213 let mut iter = iter.into_iter();
214 $(
215 let mut $Y = None;
216 )*
217
218 loop {
219 $(
220 $Y = iter.next();
221 if $Y.is_none() {
222 break
223 }
224 )*
225 return Some(($($Y.unwrap()),*,))
226 }
227
228 let mut i = 0;
229 let mut s = buf.as_mut();
230 $(
231 if i < s.len() {
232 s[i] = $Y;
233 i += 1;
234 }
235 )*
236 return None;
237 }
238
239 #[allow(unused_assignments)]
240 fn collect_from_iter_no_buf<I>(iter: I) -> Option<Self>
241 where I: IntoIterator<Item = $A>
242 {
243 let mut iter = iter.into_iter();
244 loop {
245 $(
246 let $Y = if let Some($Y) = iter.next() {
247 $Y
248 } else {
249 break;
250 };
251 )*
252 return Some(($($Y),*,))
253 }
254
255 return None;
256 }
257
258 fn num_items() -> usize {
259 $N
260 }
261
262 fn left_shift_push(&mut self, item: $A) {
263 use std::mem::replace;
264
265 let &mut ($(ref mut $Y),*,) = self;
266 let tmp = item;
267 $(
268 let tmp = replace($Y_rev, tmp);
269 )*
270 drop(tmp);
271 }
272 }
273 )
274 }
275
276 impl_tuple_collect!(1; A; A; a; a);
277 impl_tuple_collect!(2; A; A, A; a, b; b, a);
278 impl_tuple_collect!(3; A; A, A, A; a, b, c; c, b, a);
279 impl_tuple_collect!(4; A; A, A, A, A; a, b, c, d; d, c, b, a);
280