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