]>
Commit | Line | Data |
---|---|---|
48663c56 | 1 | use crate::fmt; |
fc512014 | 2 | use crate::iter::{DoubleEndedIterator, Fuse, FusedIterator, Iterator, Map}; |
48663c56 XL |
3 | use crate::ops::Try; |
4 | ||
9fa01778 XL |
5 | /// An iterator that maps each element to an iterator, and yields the elements |
6 | /// of the produced iterators. | |
7 | /// | |
1b1a35ee XL |
8 | /// This `struct` is created by [`Iterator::flat_map`]. See its documentation |
9 | /// for more. | |
9fa01778 XL |
10 | #[must_use = "iterators are lazy and do nothing unless consumed"] |
11 | #[stable(feature = "rust1", since = "1.0.0")] | |
12 | pub struct FlatMap<I, U: IntoIterator, F> { | |
60c5eb7d | 13 | inner: FlattenCompat<Map<I, F>, <U as IntoIterator>::IntoIter>, |
9fa01778 | 14 | } |
fc512014 | 15 | |
9fa01778 | 16 | impl<I: Iterator, U: IntoIterator, F: FnMut(I::Item) -> U> FlatMap<I, U, F> { |
fc512014 | 17 | pub(in crate::iter) fn new(iter: I, f: F) -> FlatMap<I, U, F> { |
9fa01778 XL |
18 | FlatMap { inner: FlattenCompat::new(iter.map(f)) } |
19 | } | |
20 | } | |
21 | ||
22 | #[stable(feature = "rust1", since = "1.0.0")] | |
416331ca XL |
23 | impl<I: Clone, U, F: Clone> Clone for FlatMap<I, U, F> |
24 | where | |
25 | U: Clone + IntoIterator<IntoIter: Clone>, | |
9fa01778 | 26 | { |
60c5eb7d XL |
27 | fn clone(&self) -> Self { |
28 | FlatMap { inner: self.inner.clone() } | |
29 | } | |
9fa01778 XL |
30 | } |
31 | ||
32 | #[stable(feature = "core_impl_debug", since = "1.9.0")] | |
416331ca XL |
33 | impl<I: fmt::Debug, U, F> fmt::Debug for FlatMap<I, U, F> |
34 | where | |
35 | U: IntoIterator<IntoIter: fmt::Debug>, | |
9fa01778 | 36 | { |
48663c56 | 37 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
9fa01778 XL |
38 | f.debug_struct("FlatMap").field("inner", &self.inner).finish() |
39 | } | |
40 | } | |
41 | ||
42 | #[stable(feature = "rust1", since = "1.0.0")] | |
43 | impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F> | |
60c5eb7d XL |
44 | where |
45 | F: FnMut(I::Item) -> U, | |
9fa01778 XL |
46 | { |
47 | type Item = U::Item; | |
48 | ||
49 | #[inline] | |
60c5eb7d XL |
50 | fn next(&mut self) -> Option<U::Item> { |
51 | self.inner.next() | |
52 | } | |
9fa01778 XL |
53 | |
54 | #[inline] | |
60c5eb7d XL |
55 | fn size_hint(&self) -> (usize, Option<usize>) { |
56 | self.inner.size_hint() | |
57 | } | |
9fa01778 XL |
58 | |
59 | #[inline] | |
60c5eb7d XL |
60 | fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R |
61 | where | |
62 | Self: Sized, | |
63 | Fold: FnMut(Acc, Self::Item) -> R, | |
64 | R: Try<Ok = Acc>, | |
9fa01778 XL |
65 | { |
66 | self.inner.try_fold(init, fold) | |
67 | } | |
68 | ||
69 | #[inline] | |
70 | fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc | |
60c5eb7d XL |
71 | where |
72 | Fold: FnMut(Acc, Self::Item) -> Acc, | |
9fa01778 XL |
73 | { |
74 | self.inner.fold(init, fold) | |
75 | } | |
76 | } | |
77 | ||
78 | #[stable(feature = "rust1", since = "1.0.0")] | |
79 | impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F> | |
416331ca XL |
80 | where |
81 | F: FnMut(I::Item) -> U, | |
e1599b0c | 82 | U: IntoIterator<IntoIter: DoubleEndedIterator>, |
9fa01778 XL |
83 | { |
84 | #[inline] | |
60c5eb7d XL |
85 | fn next_back(&mut self) -> Option<U::Item> { |
86 | self.inner.next_back() | |
87 | } | |
9fa01778 XL |
88 | |
89 | #[inline] | |
60c5eb7d XL |
90 | fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R |
91 | where | |
92 | Self: Sized, | |
93 | Fold: FnMut(Acc, Self::Item) -> R, | |
94 | R: Try<Ok = Acc>, | |
9fa01778 XL |
95 | { |
96 | self.inner.try_rfold(init, fold) | |
97 | } | |
98 | ||
99 | #[inline] | |
100 | fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc | |
60c5eb7d XL |
101 | where |
102 | Fold: FnMut(Acc, Self::Item) -> Acc, | |
9fa01778 XL |
103 | { |
104 | self.inner.rfold(init, fold) | |
105 | } | |
106 | } | |
107 | ||
108 | #[stable(feature = "fused", since = "1.26.0")] | |
109 | impl<I, U, F> FusedIterator for FlatMap<I, U, F> | |
60c5eb7d XL |
110 | where |
111 | I: FusedIterator, | |
112 | U: IntoIterator, | |
113 | F: FnMut(I::Item) -> U, | |
114 | { | |
115 | } | |
9fa01778 XL |
116 | |
117 | /// An iterator that flattens one level of nesting in an iterator of things | |
118 | /// that can be turned into iterators. | |
119 | /// | |
120 | /// This `struct` is created by the [`flatten`] method on [`Iterator`]. See its | |
121 | /// documentation for more. | |
122 | /// | |
fc512014 | 123 | /// [`flatten`]: Iterator::flatten() |
9fa01778 XL |
124 | #[must_use = "iterators are lazy and do nothing unless consumed"] |
125 | #[stable(feature = "iterator_flatten", since = "1.29.0")] | |
e1599b0c | 126 | pub struct Flatten<I: Iterator<Item: IntoIterator>> { |
9fa01778 XL |
127 | inner: FlattenCompat<I, <I::Item as IntoIterator>::IntoIter>, |
128 | } | |
416331ca XL |
129 | |
130 | impl<I: Iterator<Item: IntoIterator>> Flatten<I> { | |
9fa01778 XL |
131 | pub(in super::super) fn new(iter: I) -> Flatten<I> { |
132 | Flatten { inner: FlattenCompat::new(iter) } | |
133 | } | |
134 | } | |
135 | ||
136 | #[stable(feature = "iterator_flatten", since = "1.29.0")] | |
137 | impl<I, U> fmt::Debug for Flatten<I> | |
416331ca XL |
138 | where |
139 | I: fmt::Debug + Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>, | |
140 | U: fmt::Debug + Iterator, | |
9fa01778 | 141 | { |
48663c56 | 142 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
9fa01778 XL |
143 | f.debug_struct("Flatten").field("inner", &self.inner).finish() |
144 | } | |
145 | } | |
146 | ||
147 | #[stable(feature = "iterator_flatten", since = "1.29.0")] | |
148 | impl<I, U> Clone for Flatten<I> | |
416331ca XL |
149 | where |
150 | I: Clone + Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>, | |
151 | U: Clone + Iterator, | |
9fa01778 | 152 | { |
60c5eb7d XL |
153 | fn clone(&self) -> Self { |
154 | Flatten { inner: self.inner.clone() } | |
155 | } | |
9fa01778 XL |
156 | } |
157 | ||
158 | #[stable(feature = "iterator_flatten", since = "1.29.0")] | |
159 | impl<I, U> Iterator for Flatten<I> | |
416331ca XL |
160 | where |
161 | I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>, | |
162 | U: Iterator, | |
9fa01778 XL |
163 | { |
164 | type Item = U::Item; | |
165 | ||
166 | #[inline] | |
60c5eb7d XL |
167 | fn next(&mut self) -> Option<U::Item> { |
168 | self.inner.next() | |
169 | } | |
9fa01778 XL |
170 | |
171 | #[inline] | |
60c5eb7d XL |
172 | fn size_hint(&self) -> (usize, Option<usize>) { |
173 | self.inner.size_hint() | |
174 | } | |
9fa01778 XL |
175 | |
176 | #[inline] | |
60c5eb7d XL |
177 | fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R |
178 | where | |
179 | Self: Sized, | |
180 | Fold: FnMut(Acc, Self::Item) -> R, | |
181 | R: Try<Ok = Acc>, | |
9fa01778 XL |
182 | { |
183 | self.inner.try_fold(init, fold) | |
184 | } | |
185 | ||
186 | #[inline] | |
187 | fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc | |
60c5eb7d XL |
188 | where |
189 | Fold: FnMut(Acc, Self::Item) -> Acc, | |
9fa01778 XL |
190 | { |
191 | self.inner.fold(init, fold) | |
192 | } | |
193 | } | |
194 | ||
195 | #[stable(feature = "iterator_flatten", since = "1.29.0")] | |
196 | impl<I, U> DoubleEndedIterator for Flatten<I> | |
416331ca XL |
197 | where |
198 | I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>, | |
199 | U: DoubleEndedIterator, | |
9fa01778 XL |
200 | { |
201 | #[inline] | |
60c5eb7d XL |
202 | fn next_back(&mut self) -> Option<U::Item> { |
203 | self.inner.next_back() | |
204 | } | |
9fa01778 XL |
205 | |
206 | #[inline] | |
60c5eb7d XL |
207 | fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R |
208 | where | |
209 | Self: Sized, | |
210 | Fold: FnMut(Acc, Self::Item) -> R, | |
211 | R: Try<Ok = Acc>, | |
9fa01778 XL |
212 | { |
213 | self.inner.try_rfold(init, fold) | |
214 | } | |
215 | ||
216 | #[inline] | |
217 | fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc | |
60c5eb7d XL |
218 | where |
219 | Fold: FnMut(Acc, Self::Item) -> Acc, | |
9fa01778 XL |
220 | { |
221 | self.inner.rfold(init, fold) | |
222 | } | |
223 | } | |
224 | ||
225 | #[stable(feature = "iterator_flatten", since = "1.29.0")] | |
226 | impl<I, U> FusedIterator for Flatten<I> | |
416331ca XL |
227 | where |
228 | I: FusedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>, | |
229 | U: Iterator, | |
60c5eb7d XL |
230 | { |
231 | } | |
9fa01778 XL |
232 | |
233 | /// Real logic of both `Flatten` and `FlatMap` which simply delegate to | |
234 | /// this type. | |
235 | #[derive(Clone, Debug)] | |
236 | struct FlattenCompat<I, U> { | |
ba9703b0 | 237 | iter: Fuse<I>, |
9fa01778 XL |
238 | frontiter: Option<U>, |
239 | backiter: Option<U>, | |
240 | } | |
ba9703b0 XL |
241 | impl<I, U> FlattenCompat<I, U> |
242 | where | |
243 | I: Iterator, | |
244 | { | |
9fa01778 XL |
245 | /// Adapts an iterator by flattening it, for use in `flatten()` and `flat_map()`. |
246 | fn new(iter: I) -> FlattenCompat<I, U> { | |
ba9703b0 | 247 | FlattenCompat { iter: iter.fuse(), frontiter: None, backiter: None } |
9fa01778 XL |
248 | } |
249 | } | |
250 | ||
251 | impl<I, U> Iterator for FlattenCompat<I, U> | |
416331ca XL |
252 | where |
253 | I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>, | |
254 | U: Iterator, | |
9fa01778 XL |
255 | { |
256 | type Item = U::Item; | |
257 | ||
258 | #[inline] | |
259 | fn next(&mut self) -> Option<U::Item> { | |
260 | loop { | |
261 | if let Some(ref mut inner) = self.frontiter { | |
ba9703b0 XL |
262 | match inner.next() { |
263 | None => self.frontiter = None, | |
264 | elt @ Some(_) => return elt, | |
60c5eb7d | 265 | } |
9fa01778 XL |
266 | } |
267 | match self.iter.next() { | |
5869c6ff XL |
268 | None => match self.backiter.as_mut()?.next() { |
269 | None => { | |
270 | self.backiter = None; | |
271 | return None; | |
272 | } | |
273 | elt @ Some(_) => return elt, | |
274 | }, | |
9fa01778 XL |
275 | Some(inner) => self.frontiter = Some(inner.into_iter()), |
276 | } | |
277 | } | |
278 | } | |
279 | ||
280 | #[inline] | |
281 | fn size_hint(&self) -> (usize, Option<usize>) { | |
e1599b0c XL |
282 | let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), U::size_hint); |
283 | let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), U::size_hint); | |
9fa01778 XL |
284 | let lo = flo.saturating_add(blo); |
285 | match (self.iter.size_hint(), fhi, bhi) { | |
286 | ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)), | |
60c5eb7d | 287 | _ => (lo, None), |
9fa01778 XL |
288 | } |
289 | } | |
290 | ||
291 | #[inline] | |
60c5eb7d XL |
292 | fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R |
293 | where | |
294 | Self: Sized, | |
295 | Fold: FnMut(Acc, Self::Item) -> R, | |
296 | R: Try<Ok = Acc>, | |
9fa01778 | 297 | { |
e1599b0c XL |
298 | #[inline] |
299 | fn flatten<'a, T: IntoIterator, Acc, R: Try<Ok = Acc>>( | |
300 | frontiter: &'a mut Option<T::IntoIter>, | |
301 | fold: &'a mut impl FnMut(Acc, T::Item) -> R, | |
302 | ) -> impl FnMut(Acc, T) -> R + 'a { | |
303 | move |acc, x| { | |
304 | let mut mid = x.into_iter(); | |
305 | let r = mid.try_fold(acc, &mut *fold); | |
306 | *frontiter = Some(mid); | |
307 | r | |
308 | } | |
309 | } | |
310 | ||
9fa01778 XL |
311 | if let Some(ref mut front) = self.frontiter { |
312 | init = front.try_fold(init, &mut fold)?; | |
313 | } | |
314 | self.frontiter = None; | |
315 | ||
e1599b0c | 316 | init = self.iter.try_fold(init, flatten(&mut self.frontiter, &mut fold))?; |
9fa01778 XL |
317 | self.frontiter = None; |
318 | ||
319 | if let Some(ref mut back) = self.backiter { | |
320 | init = back.try_fold(init, &mut fold)?; | |
321 | } | |
322 | self.backiter = None; | |
323 | ||
29967ef6 | 324 | try { init } |
9fa01778 XL |
325 | } |
326 | ||
327 | #[inline] | |
6a06907d | 328 | fn fold<Acc, Fold>(self, mut init: Acc, mut fold: Fold) -> Acc |
60c5eb7d XL |
329 | where |
330 | Fold: FnMut(Acc, Self::Item) -> Acc, | |
9fa01778 | 331 | { |
e1599b0c | 332 | #[inline] |
6a06907d XL |
333 | fn flatten<T: IntoIterator, Acc>( |
334 | fold: &mut impl FnMut(Acc, T::Item) -> Acc, | |
335 | ) -> impl FnMut(Acc, T) -> Acc + '_ { | |
336 | move |acc, x| x.into_iter().fold(acc, &mut *fold) | |
e1599b0c XL |
337 | } |
338 | ||
6a06907d XL |
339 | if let Some(front) = self.frontiter { |
340 | init = front.fold(init, &mut fold); | |
341 | } | |
342 | ||
343 | init = self.iter.fold(init, flatten(&mut fold)); | |
344 | ||
345 | if let Some(back) = self.backiter { | |
346 | init = back.fold(init, &mut fold); | |
347 | } | |
348 | ||
349 | init | |
9fa01778 XL |
350 | } |
351 | } | |
352 | ||
353 | impl<I, U> DoubleEndedIterator for FlattenCompat<I, U> | |
416331ca XL |
354 | where |
355 | I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>, | |
356 | U: DoubleEndedIterator, | |
9fa01778 XL |
357 | { |
358 | #[inline] | |
359 | fn next_back(&mut self) -> Option<U::Item> { | |
360 | loop { | |
361 | if let Some(ref mut inner) = self.backiter { | |
ba9703b0 XL |
362 | match inner.next_back() { |
363 | None => self.backiter = None, | |
364 | elt @ Some(_) => return elt, | |
60c5eb7d | 365 | } |
9fa01778 XL |
366 | } |
367 | match self.iter.next_back() { | |
5869c6ff XL |
368 | None => match self.frontiter.as_mut()?.next_back() { |
369 | None => { | |
370 | self.frontiter = None; | |
371 | return None; | |
372 | } | |
373 | elt @ Some(_) => return elt, | |
374 | }, | |
9fa01778 XL |
375 | next => self.backiter = next.map(IntoIterator::into_iter), |
376 | } | |
377 | } | |
378 | } | |
379 | ||
380 | #[inline] | |
60c5eb7d XL |
381 | fn try_rfold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R |
382 | where | |
383 | Self: Sized, | |
384 | Fold: FnMut(Acc, Self::Item) -> R, | |
385 | R: Try<Ok = Acc>, | |
9fa01778 | 386 | { |
e1599b0c XL |
387 | #[inline] |
388 | fn flatten<'a, T: IntoIterator, Acc, R: Try<Ok = Acc>>( | |
389 | backiter: &'a mut Option<T::IntoIter>, | |
390 | fold: &'a mut impl FnMut(Acc, T::Item) -> R, | |
60c5eb7d XL |
391 | ) -> impl FnMut(Acc, T) -> R + 'a |
392 | where | |
e1599b0c | 393 | T::IntoIter: DoubleEndedIterator, |
9fa01778 | 394 | { |
e1599b0c | 395 | move |acc, x| { |
9fa01778 | 396 | let mut mid = x.into_iter(); |
e1599b0c | 397 | let r = mid.try_rfold(acc, &mut *fold); |
9fa01778 XL |
398 | *backiter = Some(mid); |
399 | r | |
e1599b0c XL |
400 | } |
401 | } | |
402 | ||
403 | if let Some(ref mut back) = self.backiter { | |
404 | init = back.try_rfold(init, &mut fold)?; | |
9fa01778 XL |
405 | } |
406 | self.backiter = None; | |
407 | ||
e1599b0c XL |
408 | init = self.iter.try_rfold(init, flatten(&mut self.backiter, &mut fold))?; |
409 | self.backiter = None; | |
410 | ||
9fa01778 XL |
411 | if let Some(ref mut front) = self.frontiter { |
412 | init = front.try_rfold(init, &mut fold)?; | |
413 | } | |
414 | self.frontiter = None; | |
415 | ||
29967ef6 | 416 | try { init } |
9fa01778 XL |
417 | } |
418 | ||
419 | #[inline] | |
6a06907d | 420 | fn rfold<Acc, Fold>(self, mut init: Acc, mut fold: Fold) -> Acc |
60c5eb7d XL |
421 | where |
422 | Fold: FnMut(Acc, Self::Item) -> Acc, | |
9fa01778 | 423 | { |
e1599b0c | 424 | #[inline] |
6a06907d XL |
425 | fn flatten<T: IntoIterator, Acc>( |
426 | fold: &mut impl FnMut(Acc, T::Item) -> Acc, | |
427 | ) -> impl FnMut(Acc, T) -> Acc + '_ | |
428 | where | |
429 | T::IntoIter: DoubleEndedIterator, | |
430 | { | |
431 | move |acc, x| x.into_iter().rfold(acc, &mut *fold) | |
432 | } | |
433 | ||
434 | if let Some(back) = self.backiter { | |
435 | init = back.rfold(init, &mut fold); | |
436 | } | |
437 | ||
438 | init = self.iter.rfold(init, flatten(&mut fold)); | |
439 | ||
440 | if let Some(front) = self.frontiter { | |
441 | init = front.rfold(init, &mut fold); | |
e1599b0c XL |
442 | } |
443 | ||
6a06907d | 444 | init |
9fa01778 XL |
445 | } |
446 | } |