4 use super::super::{DoubleEndedIterator, Fuse, FusedIterator, Iterator};
7 /// An iterator that maps each element to an iterator, and yields the elements
8 /// of the produced iterators.
10 /// This `struct` is created by [`Iterator::flat_map`]. See its documentation
12 #[must_use = "iterators are lazy and do nothing unless consumed"]
13 #[stable(feature = "rust1", since = "1.0.0")]
14 pub struct FlatMap<I, U: IntoIterator, F> {
15 inner: FlattenCompat<Map<I, F>, <U as IntoIterator>::IntoIter>,
17 impl<I: Iterator, U: IntoIterator, F: FnMut(I::Item) -> U> FlatMap<I, U, F> {
18 pub(in super::super) fn new(iter: I, f: F) -> FlatMap<I, U, F> {
19 FlatMap { inner: FlattenCompat::new(iter.map(f)) }
23 #[stable(feature = "rust1", since = "1.0.0")]
24 impl<I: Clone, U, F: Clone> Clone for FlatMap<I, U, F>
26 U: Clone + IntoIterator<IntoIter: Clone>,
28 fn clone(&self) -> Self {
29 FlatMap { inner: self.inner.clone() }
33 #[stable(feature = "core_impl_debug", since = "1.9.0")]
34 impl<I: fmt::Debug, U, F> fmt::Debug for FlatMap<I, U, F>
36 U: IntoIterator<IntoIter: fmt::Debug>,
38 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
39 f.debug_struct("FlatMap").field("inner", &self.inner).finish()
43 #[stable(feature = "rust1", since = "1.0.0")]
44 impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F>
46 F: FnMut(I::Item) -> U,
51 fn next(&mut self) -> Option<U::Item> {
56 fn size_hint(&self) -> (usize, Option<usize>) {
57 self.inner.size_hint()
61 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
64 Fold: FnMut(Acc, Self::Item) -> R,
67 self.inner.try_fold(init, fold)
71 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
73 Fold: FnMut(Acc, Self::Item) -> Acc,
75 self.inner.fold(init, fold)
79 #[stable(feature = "rust1", since = "1.0.0")]
80 impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F>
82 F: FnMut(I::Item) -> U,
83 U: IntoIterator<IntoIter: DoubleEndedIterator>,
86 fn next_back(&mut self) -> Option<U::Item> {
87 self.inner.next_back()
91 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
94 Fold: FnMut(Acc, Self::Item) -> R,
97 self.inner.try_rfold(init, fold)
101 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
103 Fold: FnMut(Acc, Self::Item) -> Acc,
105 self.inner.rfold(init, fold)
109 #[stable(feature = "fused", since = "1.26.0")]
110 impl<I, U, F> FusedIterator for FlatMap<I, U, F>
114 F: FnMut(I::Item) -> U,
118 /// An iterator that flattens one level of nesting in an iterator of things
119 /// that can be turned into iterators.
121 /// This `struct` is created by the [`flatten`] method on [`Iterator`]. See its
122 /// documentation for more.
124 /// [`flatten`]: Iterator::flatten
125 /// [`Iterator`]: trait.Iterator.html
126 #[must_use = "iterators are lazy and do nothing unless consumed"]
127 #[stable(feature = "iterator_flatten", since = "1.29.0")]
128 pub struct Flatten<I: Iterator<Item: IntoIterator>> {
129 inner: FlattenCompat<I, <I::Item as IntoIterator>::IntoIter>,
132 impl<I: Iterator<Item: IntoIterator>> Flatten<I> {
133 pub(in super::super) fn new(iter: I) -> Flatten<I> {
134 Flatten { inner: FlattenCompat::new(iter) }
138 #[stable(feature = "iterator_flatten", since = "1.29.0")]
139 impl<I, U> fmt::Debug for Flatten<I>
141 I: fmt::Debug + Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
142 U: fmt::Debug + Iterator,
144 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
145 f.debug_struct("Flatten").field("inner", &self.inner).finish()
149 #[stable(feature = "iterator_flatten", since = "1.29.0")]
150 impl<I, U> Clone for Flatten<I>
152 I: Clone + Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
155 fn clone(&self) -> Self {
156 Flatten { inner: self.inner.clone() }
160 #[stable(feature = "iterator_flatten", since = "1.29.0")]
161 impl<I, U> Iterator for Flatten<I>
163 I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
169 fn next(&mut self) -> Option<U::Item> {
174 fn size_hint(&self) -> (usize, Option<usize>) {
175 self.inner.size_hint()
179 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
182 Fold: FnMut(Acc, Self::Item) -> R,
185 self.inner.try_fold(init, fold)
189 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
191 Fold: FnMut(Acc, Self::Item) -> Acc,
193 self.inner.fold(init, fold)
197 #[stable(feature = "iterator_flatten", since = "1.29.0")]
198 impl<I, U> DoubleEndedIterator for Flatten<I>
200 I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
201 U: DoubleEndedIterator,
204 fn next_back(&mut self) -> Option<U::Item> {
205 self.inner.next_back()
209 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
212 Fold: FnMut(Acc, Self::Item) -> R,
215 self.inner.try_rfold(init, fold)
219 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
221 Fold: FnMut(Acc, Self::Item) -> Acc,
223 self.inner.rfold(init, fold)
227 #[stable(feature = "iterator_flatten", since = "1.29.0")]
228 impl<I, U> FusedIterator for Flatten<I>
230 I: FusedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
235 /// Real logic of both `Flatten` and `FlatMap` which simply delegate to
237 #[derive(Clone, Debug)]
238 struct FlattenCompat<I, U> {
240 frontiter: Option<U>,
243 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: iter.fuse(), frontiter: None, backiter: None }
253 impl<I, U> Iterator for FlattenCompat<I, U>
255 I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
261 fn next(&mut self) -> Option<U::Item> {
263 if let Some(ref mut inner) = self.frontiter {
265 None => self.frontiter = None,
266 elt @ Some(_) => return elt,
269 match self.iter.next() {
270 None => return self.backiter.as_mut()?.next(),
271 Some(inner) => self.frontiter = Some(inner.into_iter()),
277 fn size_hint(&self) -> (usize, Option<usize>) {
278 let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), U::size_hint);
279 let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), U::size_hint);
280 let lo = flo.saturating_add(blo);
281 match (self.iter.size_hint(), fhi, bhi) {
282 ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
288 fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
291 Fold: FnMut(Acc, Self::Item) -> R,
295 fn flatten<'a, T: IntoIterator, Acc, R: Try<Ok = Acc>>(
296 frontiter: &'a mut Option<T::IntoIter>,
297 fold: &'a mut impl FnMut(Acc, T::Item) -> R,
298 ) -> impl FnMut(Acc, T) -> R + 'a {
300 let mut mid = x.into_iter();
301 let r = mid.try_fold(acc, &mut *fold);
302 *frontiter = Some(mid);
307 if let Some(ref mut front) = self.frontiter {
308 init = front.try_fold(init, &mut fold)?;
310 self.frontiter = None;
312 init = self.iter.try_fold(init, flatten(&mut self.frontiter, &mut fold))?;
313 self.frontiter = None;
315 if let Some(ref mut back) = self.backiter {
316 init = back.try_fold(init, &mut fold)?;
318 self.backiter = None;
324 fn fold<Acc, Fold>(self, init: Acc, ref mut fold: Fold) -> Acc
326 Fold: FnMut(Acc, Self::Item) -> Acc,
329 fn flatten<U: Iterator, Acc>(
330 fold: &mut impl FnMut(Acc, U::Item) -> Acc,
331 ) -> impl FnMut(Acc, U) -> Acc + '_ {
332 move |acc, iter| iter.fold(acc, &mut *fold)
337 .chain(self.iter.map(IntoIterator::into_iter))
338 .chain(self.backiter)
339 .fold(init, flatten(fold))
343 impl<I, U> DoubleEndedIterator for FlattenCompat<I, U>
345 I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
346 U: DoubleEndedIterator,
349 fn next_back(&mut self) -> Option<U::Item> {
351 if let Some(ref mut inner) = self.backiter {
352 match inner.next_back() {
353 None => self.backiter = None,
354 elt @ Some(_) => return elt,
357 match self.iter.next_back() {
358 None => return self.frontiter.as_mut()?.next_back(),
359 next => self.backiter = next.map(IntoIterator::into_iter),
365 fn try_rfold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
368 Fold: FnMut(Acc, Self::Item) -> R,
372 fn flatten<'a, T: IntoIterator, Acc, R: Try<Ok = Acc>>(
373 backiter: &'a mut Option<T::IntoIter>,
374 fold: &'a mut impl FnMut(Acc, T::Item) -> R,
375 ) -> impl FnMut(Acc, T) -> R + 'a
377 T::IntoIter: DoubleEndedIterator,
380 let mut mid = x.into_iter();
381 let r = mid.try_rfold(acc, &mut *fold);
382 *backiter = Some(mid);
387 if let Some(ref mut back) = self.backiter {
388 init = back.try_rfold(init, &mut fold)?;
390 self.backiter = None;
392 init = self.iter.try_rfold(init, flatten(&mut self.backiter, &mut fold))?;
393 self.backiter = None;
395 if let Some(ref mut front) = self.frontiter {
396 init = front.try_rfold(init, &mut fold)?;
398 self.frontiter = None;
404 fn rfold<Acc, Fold>(self, init: Acc, ref mut fold: Fold) -> Acc
406 Fold: FnMut(Acc, Self::Item) -> Acc,
409 fn flatten<U: DoubleEndedIterator, Acc>(
410 fold: &mut impl FnMut(Acc, U::Item) -> Acc,
411 ) -> impl FnMut(Acc, U) -> Acc + '_ {
412 move |acc, iter| iter.rfold(acc, &mut *fold)
417 .chain(self.iter.map(IntoIterator::into_iter))
418 .chain(self.backiter)
419 .rfold(init, flatten(fold))