library/core/src/iter/adapters/flatten.rs

   1 use crate::fmt;
   2 use crate::iter::{DoubleEndedIterator, Fuse, FusedIterator, Iterator, Map};
   3 use crate::ops::Try;
   4
   5 /// An iterator that maps each element to an iterator, and yields the elements
   6 /// of the produced iterators.
   7 ///
   8 /// This `struct` is created by [`Iterator::flat_map`]. See its documentation
   9 /// for more.
  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> {
  13     inner: FlattenCompat<Map<I, F>, <U as IntoIterator>::IntoIter>,
  14 }
  15
  16 impl<I: Iterator, U: IntoIterator, F: FnMut(I::Item) -> U> FlatMap<I, U, F> {
  17     pub(in crate::iter) fn new(iter: I, f: F) -> FlatMap<I, U, F> {
  18         FlatMap { inner: FlattenCompat::new(iter.map(f)) }
  19     }
  20 }
  21
  22 #[stable(feature = "rust1", since = "1.0.0")]
  23 impl<I: Clone, U, F: Clone> Clone for FlatMap<I, U, F>
  24 where
  25     U: Clone + IntoIterator<IntoIter: Clone>,
  26 {
  27     fn clone(&self) -> Self {
  28         FlatMap { inner: self.inner.clone() }
  29     }
  30 }
  31
  32 #[stable(feature = "core_impl_debug", since = "1.9.0")]
  33 impl<I: fmt::Debug, U, F> fmt::Debug for FlatMap<I, U, F>
  34 where
  35     U: IntoIterator<IntoIter: fmt::Debug>,
  36 {
  37     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  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>
  44 where
  45     F: FnMut(I::Item) -> U,
  46 {
  47     type Item = U::Item;
  48
  49     #[inline]
  50     fn next(&mut self) -> Option<U::Item> {
  51         self.inner.next()
  52     }
  53
  54     #[inline]
  55     fn size_hint(&self) -> (usize, Option<usize>) {
  56         self.inner.size_hint()
  57     }
  58
  59     #[inline]
  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>,
  65     {
  66         self.inner.try_fold(init, fold)
  67     }
  68
  69     #[inline]
  70     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
  71     where
  72         Fold: FnMut(Acc, Self::Item) -> Acc,
  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>
  80 where
  81     F: FnMut(I::Item) -> U,
  82     U: IntoIterator<IntoIter: DoubleEndedIterator>,
  83 {
  84     #[inline]
  85     fn next_back(&mut self) -> Option<U::Item> {
  86         self.inner.next_back()
  87     }
  88
  89     #[inline]
  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>,
  95     {
  96         self.inner.try_rfold(init, fold)
  97     }
  98
  99     #[inline]
 100     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 101     where
 102         Fold: FnMut(Acc, Self::Item) -> Acc,
 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>
 110 where
 111     I: FusedIterator,
 112     U: IntoIterator,
 113     F: FnMut(I::Item) -> U,
 114 {
 115 }
 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 ///
 123 /// [`flatten`]: Iterator::flatten()
 124 #[must_use = "iterators are lazy and do nothing unless consumed"]
 125 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 126 pub struct Flatten<I: Iterator<Item: IntoIterator>> {
 127     inner: FlattenCompat<I, <I::Item as IntoIterator>::IntoIter>,
 128 }
 129
 130 impl<I: Iterator<Item: IntoIterator>> Flatten<I> {
 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>
 138 where
 139     I: fmt::Debug + Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 140     U: fmt::Debug + Iterator,
 141 {
 142     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 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>
 149 where
 150     I: Clone + Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 151     U: Clone + Iterator,
 152 {
 153     fn clone(&self) -> Self {
 154         Flatten { inner: self.inner.clone() }
 155     }
 156 }
 157
 158 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 159 impl<I, U> Iterator for Flatten<I>
 160 where
 161     I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 162     U: Iterator,
 163 {
 164     type Item = U::Item;
 165
 166     #[inline]
 167     fn next(&mut self) -> Option<U::Item> {
 168         self.inner.next()
 169     }
 170
 171     #[inline]
 172     fn size_hint(&self) -> (usize, Option<usize>) {
 173         self.inner.size_hint()
 174     }
 175
 176     #[inline]
 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>,
 182     {
 183         self.inner.try_fold(init, fold)
 184     }
 185
 186     #[inline]
 187     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 188     where
 189         Fold: FnMut(Acc, Self::Item) -> Acc,
 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>
 197 where
 198     I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 199     U: DoubleEndedIterator,
 200 {
 201     #[inline]
 202     fn next_back(&mut self) -> Option<U::Item> {
 203         self.inner.next_back()
 204     }
 205
 206     #[inline]
 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>,
 212     {
 213         self.inner.try_rfold(init, fold)
 214     }
 215
 216     #[inline]
 217     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 218     where
 219         Fold: FnMut(Acc, Self::Item) -> Acc,
 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>
 227 where
 228     I: FusedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 229     U: Iterator,
 230 {
 231 }
 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> {
 237     iter: Fuse<I>,
 238     frontiter: Option<U>,
 239     backiter: Option<U>,
 240 }
 241 impl<I, U> FlattenCompat<I, U>
 242 where
 243     I: Iterator,
 244 {
 245     /// Adapts an iterator by flattening it, for use in `flatten()` and `flat_map()`.
 246     fn new(iter: I) -> FlattenCompat<I, U> {
 247         FlattenCompat { iter: iter.fuse(), frontiter: None, backiter: None }
 248     }
 249 }
 250
 251 impl<I, U> Iterator for FlattenCompat<I, U>
 252 where
 253     I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 254     U: Iterator,
 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 {
 262                 match inner.next() {
 263                     None => self.frontiter = None,
 264                     elt @ Some(_) => return elt,
 265                 }
 266             }
 267             match self.iter.next() {
 268                 None => return self.backiter.as_mut()?.next(),
 269                 Some(inner) => self.frontiter = Some(inner.into_iter()),
 270             }
 271         }
 272     }
 273
 274     #[inline]
 275     fn size_hint(&self) -> (usize, Option<usize>) {
 276         let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), U::size_hint);
 277         let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), U::size_hint);
 278         let lo = flo.saturating_add(blo);
 279         match (self.iter.size_hint(), fhi, bhi) {
 280             ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
 281             _ => (lo, None),
 282         }
 283     }
 284
 285     #[inline]
 286     fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
 287     where
 288         Self: Sized,
 289         Fold: FnMut(Acc, Self::Item) -> R,
 290         R: Try<Ok = Acc>,
 291     {
 292         #[inline]
 293         fn flatten<'a, T: IntoIterator, Acc, R: Try<Ok = Acc>>(
 294             frontiter: &'a mut Option<T::IntoIter>,
 295             fold: &'a mut impl FnMut(Acc, T::Item) -> R,
 296         ) -> impl FnMut(Acc, T) -> R + 'a {
 297             move |acc, x| {
 298                 let mut mid = x.into_iter();
 299                 let r = mid.try_fold(acc, &mut *fold);
 300                 *frontiter = Some(mid);
 301                 r
 302             }
 303         }
 304
 305         if let Some(ref mut front) = self.frontiter {
 306             init = front.try_fold(init, &mut fold)?;
 307         }
 308         self.frontiter = None;
 309
 310         init = self.iter.try_fold(init, flatten(&mut self.frontiter, &mut fold))?;
 311         self.frontiter = None;
 312
 313         if let Some(ref mut back) = self.backiter {
 314             init = back.try_fold(init, &mut fold)?;
 315         }
 316         self.backiter = None;
 317
 318         try { init }
 319     }
 320
 321     #[inline]
 322     fn fold<Acc, Fold>(self, init: Acc, ref mut fold: Fold) -> Acc
 323     where
 324         Fold: FnMut(Acc, Self::Item) -> Acc,
 325     {
 326         #[inline]
 327         fn flatten<U: Iterator, Acc>(
 328             fold: &mut impl FnMut(Acc, U::Item) -> Acc,
 329         ) -> impl FnMut(Acc, U) -> Acc + '_ {
 330             move |acc, iter| iter.fold(acc, &mut *fold)
 331         }
 332
 333         self.frontiter
 334             .into_iter()
 335             .chain(self.iter.map(IntoIterator::into_iter))
 336             .chain(self.backiter)
 337             .fold(init, flatten(fold))
 338     }
 339 }
 340
 341 impl<I, U> DoubleEndedIterator for FlattenCompat<I, U>
 342 where
 343     I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 344     U: DoubleEndedIterator,
 345 {
 346     #[inline]
 347     fn next_back(&mut self) -> Option<U::Item> {
 348         loop {
 349             if let Some(ref mut inner) = self.backiter {
 350                 match inner.next_back() {
 351                     None => self.backiter = None,
 352                     elt @ Some(_) => return elt,
 353                 }
 354             }
 355             match self.iter.next_back() {
 356                 None => return self.frontiter.as_mut()?.next_back(),
 357                 next => self.backiter = next.map(IntoIterator::into_iter),
 358             }
 359         }
 360     }
 361
 362     #[inline]
 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>,
 368     {
 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,
 373         ) -> impl FnMut(Acc, T) -> R + 'a
 374         where
 375             T::IntoIter: DoubleEndedIterator,
 376         {
 377             move |acc, x| {
 378                 let mut mid = x.into_iter();
 379                 let r = mid.try_rfold(acc, &mut *fold);
 380                 *backiter = Some(mid);
 381                 r
 382             }
 383         }
 384
 385         if let Some(ref mut back) = self.backiter {
 386             init = back.try_rfold(init, &mut fold)?;
 387         }
 388         self.backiter = None;
 389
 390         init = self.iter.try_rfold(init, flatten(&mut self.backiter, &mut fold))?;
 391         self.backiter = None;
 392
 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 { init }
 399     }
 400
 401     #[inline]
 402     fn rfold<Acc, Fold>(self, init: Acc, ref mut fold: Fold) -> Acc
 403     where
 404         Fold: FnMut(Acc, Self::Item) -> Acc,
 405     {
 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
 413         self.frontiter
 414             .into_iter()
 415             .chain(self.iter.map(IntoIterator::into_iter))
 416             .chain(self.backiter)
 417             .rfold(init, flatten(fold))
 418     }
 419 }