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

   1 use crate::fmt;
   2 use crate::ops::Try;
   3
   4 use super::super::{DoubleEndedIterator, Fuse, FusedIterator, Iterator};
   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> {
  18     inner: FlattenCompat<Map<I, F>, <U as IntoIterator>::IntoIter>,
  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")]
  27 impl<I: Clone, U, F: Clone> Clone for FlatMap<I, U, F>
  28 where
  29     U: Clone + IntoIterator<IntoIter: Clone>,
  30 {
  31     fn clone(&self) -> Self {
  32         FlatMap { inner: self.inner.clone() }
  33     }
  34 }
  35
  36 #[stable(feature = "core_impl_debug", since = "1.9.0")]
  37 impl<I: fmt::Debug, U, F> fmt::Debug for FlatMap<I, U, F>
  38 where
  39     U: IntoIterator<IntoIter: fmt::Debug>,
  40 {
  41     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  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>
  48 where
  49     F: FnMut(I::Item) -> U,
  50 {
  51     type Item = U::Item;
  52
  53     #[inline]
  54     fn next(&mut self) -> Option<U::Item> {
  55         self.inner.next()
  56     }
  57
  58     #[inline]
  59     fn size_hint(&self) -> (usize, Option<usize>) {
  60         self.inner.size_hint()
  61     }
  62
  63     #[inline]
  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>,
  69     {
  70         self.inner.try_fold(init, fold)
  71     }
  72
  73     #[inline]
  74     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
  75     where
  76         Fold: FnMut(Acc, Self::Item) -> Acc,
  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>
  84 where
  85     F: FnMut(I::Item) -> U,
  86     U: IntoIterator<IntoIter: DoubleEndedIterator>,
  87 {
  88     #[inline]
  89     fn next_back(&mut self) -> Option<U::Item> {
  90         self.inner.next_back()
  91     }
  92
  93     #[inline]
  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>,
  99     {
 100         self.inner.try_rfold(init, fold)
 101     }
 102
 103     #[inline]
 104     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 105     where
 106         Fold: FnMut(Acc, Self::Item) -> Acc,
 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>
 114 where
 115     I: FusedIterator,
 116     U: IntoIterator,
 117     F: FnMut(I::Item) -> U,
 118 {
 119 }
 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")]
 131 pub struct Flatten<I: Iterator<Item: IntoIterator>> {
 132     inner: FlattenCompat<I, <I::Item as IntoIterator>::IntoIter>,
 133 }
 134
 135 impl<I: Iterator<Item: IntoIterator>> Flatten<I> {
 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>
 143 where
 144     I: fmt::Debug + Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 145     U: fmt::Debug + Iterator,
 146 {
 147     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 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>
 154 where
 155     I: Clone + Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 156     U: Clone + Iterator,
 157 {
 158     fn clone(&self) -> Self {
 159         Flatten { inner: self.inner.clone() }
 160     }
 161 }
 162
 163 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 164 impl<I, U> Iterator for Flatten<I>
 165 where
 166     I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 167     U: Iterator,
 168 {
 169     type Item = U::Item;
 170
 171     #[inline]
 172     fn next(&mut self) -> Option<U::Item> {
 173         self.inner.next()
 174     }
 175
 176     #[inline]
 177     fn size_hint(&self) -> (usize, Option<usize>) {
 178         self.inner.size_hint()
 179     }
 180
 181     #[inline]
 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>,
 187     {
 188         self.inner.try_fold(init, fold)
 189     }
 190
 191     #[inline]
 192     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 193     where
 194         Fold: FnMut(Acc, Self::Item) -> Acc,
 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>
 202 where
 203     I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 204     U: DoubleEndedIterator,
 205 {
 206     #[inline]
 207     fn next_back(&mut self) -> Option<U::Item> {
 208         self.inner.next_back()
 209     }
 210
 211     #[inline]
 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>,
 217     {
 218         self.inner.try_rfold(init, fold)
 219     }
 220
 221     #[inline]
 222     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 223     where
 224         Fold: FnMut(Acc, Self::Item) -> Acc,
 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>
 232 where
 233     I: FusedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 234     U: Iterator,
 235 {
 236 }
 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: Fuse<I>,
 243     frontiter: Option<U>,
 244     backiter: Option<U>,
 245 }
 246 impl<I, U> FlattenCompat<I, U>
 247 where
 248     I: Iterator,
 249 {
 250     /// Adapts an iterator by flattening it, for use in `flatten()` and `flat_map()`.
 251     fn new(iter: I) -> FlattenCompat<I, U> {
 252         FlattenCompat { iter: iter.fuse(), frontiter: None, backiter: None }
 253     }
 254 }
 255
 256 impl<I, U> Iterator for FlattenCompat<I, U>
 257 where
 258     I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 259     U: Iterator,
 260 {
 261     type Item = U::Item;
 262
 263     #[inline]
 264     fn next(&mut self) -> Option<U::Item> {
 265         loop {
 266             if let Some(ref mut inner) = self.frontiter {
 267                 match inner.next() {
 268                     None => self.frontiter = None,
 269                     elt @ Some(_) => return elt,
 270                 }
 271             }
 272             match self.iter.next() {
 273                 None => return self.backiter.as_mut()?.next(),
 274                 Some(inner) => self.frontiter = Some(inner.into_iter()),
 275             }
 276         }
 277     }
 278
 279     #[inline]
 280     fn size_hint(&self) -> (usize, Option<usize>) {
 281         let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), U::size_hint);
 282         let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), U::size_hint);
 283         let lo = flo.saturating_add(blo);
 284         match (self.iter.size_hint(), fhi, bhi) {
 285             ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
 286             _ => (lo, None),
 287         }
 288     }
 289
 290     #[inline]
 291     fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
 292     where
 293         Self: Sized,
 294         Fold: FnMut(Acc, Self::Item) -> R,
 295         R: Try<Ok = Acc>,
 296     {
 297         #[inline]
 298         fn flatten<'a, T: IntoIterator, Acc, R: Try<Ok = Acc>>(
 299             frontiter: &'a mut Option<T::IntoIter>,
 300             fold: &'a mut impl FnMut(Acc, T::Item) -> R,
 301         ) -> impl FnMut(Acc, T) -> R + 'a {
 302             move |acc, x| {
 303                 let mut mid = x.into_iter();
 304                 let r = mid.try_fold(acc, &mut *fold);
 305                 *frontiter = Some(mid);
 306                 r
 307             }
 308         }
 309
 310         if let Some(ref mut front) = self.frontiter {
 311             init = front.try_fold(init, &mut fold)?;
 312         }
 313         self.frontiter = None;
 314
 315         init = self.iter.try_fold(init, flatten(&mut self.frontiter, &mut fold))?;
 316         self.frontiter = None;
 317
 318         if let Some(ref mut back) = self.backiter {
 319             init = back.try_fold(init, &mut fold)?;
 320         }
 321         self.backiter = None;
 322
 323         Try::from_ok(init)
 324     }
 325
 326     #[inline]
 327     fn fold<Acc, Fold>(self, init: Acc, ref mut fold: Fold) -> Acc
 328     where
 329         Fold: FnMut(Acc, Self::Item) -> Acc,
 330     {
 331         #[inline]
 332         fn flatten<U: Iterator, Acc>(
 333             fold: &mut impl FnMut(Acc, U::Item) -> Acc,
 334         ) -> impl FnMut(Acc, U) -> Acc + '_ {
 335             move |acc, iter| iter.fold(acc, &mut *fold)
 336         }
 337
 338         self.frontiter
 339             .into_iter()
 340             .chain(self.iter.map(IntoIterator::into_iter))
 341             .chain(self.backiter)
 342             .fold(init, flatten(fold))
 343     }
 344 }
 345
 346 impl<I, U> DoubleEndedIterator for FlattenCompat<I, U>
 347 where
 348     I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 349     U: DoubleEndedIterator,
 350 {
 351     #[inline]
 352     fn next_back(&mut self) -> Option<U::Item> {
 353         loop {
 354             if let Some(ref mut inner) = self.backiter {
 355                 match inner.next_back() {
 356                     None => self.backiter = None,
 357                     elt @ Some(_) => return elt,
 358                 }
 359             }
 360             match self.iter.next_back() {
 361                 None => return self.frontiter.as_mut()?.next_back(),
 362                 next => self.backiter = next.map(IntoIterator::into_iter),
 363             }
 364         }
 365     }
 366
 367     #[inline]
 368     fn try_rfold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
 369     where
 370         Self: Sized,
 371         Fold: FnMut(Acc, Self::Item) -> R,
 372         R: Try<Ok = Acc>,
 373     {
 374         #[inline]
 375         fn flatten<'a, T: IntoIterator, Acc, R: Try<Ok = Acc>>(
 376             backiter: &'a mut Option<T::IntoIter>,
 377             fold: &'a mut impl FnMut(Acc, T::Item) -> R,
 378         ) -> impl FnMut(Acc, T) -> R + 'a
 379         where
 380             T::IntoIter: DoubleEndedIterator,
 381         {
 382             move |acc, x| {
 383                 let mut mid = x.into_iter();
 384                 let r = mid.try_rfold(acc, &mut *fold);
 385                 *backiter = Some(mid);
 386                 r
 387             }
 388         }
 389
 390         if let Some(ref mut back) = self.backiter {
 391             init = back.try_rfold(init, &mut fold)?;
 392         }
 393         self.backiter = None;
 394
 395         init = self.iter.try_rfold(init, flatten(&mut self.backiter, &mut fold))?;
 396         self.backiter = None;
 397
 398         if let Some(ref mut front) = self.frontiter {
 399             init = front.try_rfold(init, &mut fold)?;
 400         }
 401         self.frontiter = None;
 402
 403         Try::from_ok(init)
 404     }
 405
 406     #[inline]
 407     fn rfold<Acc, Fold>(self, init: Acc, ref mut fold: Fold) -> Acc
 408     where
 409         Fold: FnMut(Acc, Self::Item) -> Acc,
 410     {
 411         #[inline]
 412         fn flatten<U: DoubleEndedIterator, Acc>(
 413             fold: &mut impl FnMut(Acc, U::Item) -> Acc,
 414         ) -> impl FnMut(Acc, U) -> Acc + '_ {
 415             move |acc, iter| iter.rfold(acc, &mut *fold)
 416         }
 417
 418         self.frontiter
 419             .into_iter()
 420             .chain(self.iter.map(IntoIterator::into_iter))
 421             .chain(self.backiter)
 422             .rfold(init, flatten(fold))
 423     }
 424 }