src/libcore/iter/adapters/flatten.rs

   1 use crate::fmt;
   2 use crate::ops::Try;
   3
   4 use super::super::{DoubleEndedIterator, 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: 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>
 254 where
 255     I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 256     U: Iterator,
 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 {
 264                 if let elt @ Some(_) = inner.next() {
 265                     return elt;
 266                 }
 267             }
 268             match self.iter.next() {
 269                 None => return self.backiter.as_mut()?.next(),
 270                 Some(inner) => self.frontiter = Some(inner.into_iter()),
 271             }
 272         }
 273     }
 274
 275     #[inline]
 276     fn size_hint(&self) -> (usize, Option<usize>) {
 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);
 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)),
 282             _ => (lo, None),
 283         }
 284     }
 285
 286     #[inline]
 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>,
 292     {
 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
 306         if let Some(ref mut front) = self.frontiter {
 307             init = front.try_fold(init, &mut fold)?;
 308         }
 309         self.frontiter = None;
 310
 311         init = self.iter.try_fold(init, flatten(&mut self.frontiter, &mut fold))?;
 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]
 323     fn fold<Acc, Fold>(self, init: Acc, ref mut fold: Fold) -> Acc
 324     where
 325         Fold: FnMut(Acc, Self::Item) -> Acc,
 326     {
 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
 334         self.frontiter
 335             .into_iter()
 336             .chain(self.iter.map(IntoIterator::into_iter))
 337             .chain(self.backiter)
 338             .fold(init, flatten(fold))
 339     }
 340 }
 341
 342 impl<I, U> DoubleEndedIterator for FlattenCompat<I, U>
 343 where
 344     I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 345     U: DoubleEndedIterator,
 346 {
 347     #[inline]
 348     fn next_back(&mut self) -> Option<U::Item> {
 349         loop {
 350             if let Some(ref mut inner) = self.backiter {
 351                 if let elt @ Some(_) = inner.next_back() {
 352                     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::from_ok(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 }