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 /// [`Iterator`]: trait.Iterator.html
 125 #[must_use = "iterators are lazy and do nothing unless consumed"]
 126 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 127 pub struct Flatten<I: Iterator<Item: IntoIterator>> {
 128     inner: FlattenCompat<I, <I::Item as IntoIterator>::IntoIter>,
 129 }
 130
 131 impl<I: Iterator<Item: IntoIterator>> Flatten<I> {
 132     pub(in super::super) fn new(iter: I) -> Flatten<I> {
 133         Flatten { inner: FlattenCompat::new(iter) }
 134     }
 135 }
 136
 137 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 138 impl<I, U> fmt::Debug for Flatten<I>
 139 where
 140     I: fmt::Debug + Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 141     U: fmt::Debug + Iterator,
 142 {
 143     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 144         f.debug_struct("Flatten").field("inner", &self.inner).finish()
 145     }
 146 }
 147
 148 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 149 impl<I, U> Clone for Flatten<I>
 150 where
 151     I: Clone + Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 152     U: Clone + Iterator,
 153 {
 154     fn clone(&self) -> Self {
 155         Flatten { inner: self.inner.clone() }
 156     }
 157 }
 158
 159 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 160 impl<I, U> Iterator for Flatten<I>
 161 where
 162     I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 163     U: Iterator,
 164 {
 165     type Item = U::Item;
 166
 167     #[inline]
 168     fn next(&mut self) -> Option<U::Item> {
 169         self.inner.next()
 170     }
 171
 172     #[inline]
 173     fn size_hint(&self) -> (usize, Option<usize>) {
 174         self.inner.size_hint()
 175     }
 176
 177     #[inline]
 178     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
 179     where
 180         Self: Sized,
 181         Fold: FnMut(Acc, Self::Item) -> R,
 182         R: Try<Ok = Acc>,
 183     {
 184         self.inner.try_fold(init, fold)
 185     }
 186
 187     #[inline]
 188     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 189     where
 190         Fold: FnMut(Acc, Self::Item) -> Acc,
 191     {
 192         self.inner.fold(init, fold)
 193     }
 194 }
 195
 196 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 197 impl<I, U> DoubleEndedIterator for Flatten<I>
 198 where
 199     I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 200     U: DoubleEndedIterator,
 201 {
 202     #[inline]
 203     fn next_back(&mut self) -> Option<U::Item> {
 204         self.inner.next_back()
 205     }
 206
 207     #[inline]
 208     fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
 209     where
 210         Self: Sized,
 211         Fold: FnMut(Acc, Self::Item) -> R,
 212         R: Try<Ok = Acc>,
 213     {
 214         self.inner.try_rfold(init, fold)
 215     }
 216
 217     #[inline]
 218     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 219     where
 220         Fold: FnMut(Acc, Self::Item) -> Acc,
 221     {
 222         self.inner.rfold(init, fold)
 223     }
 224 }
 225
 226 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 227 impl<I, U> FusedIterator for Flatten<I>
 228 where
 229     I: FusedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 230     U: Iterator,
 231 {
 232 }
 233
 234 /// Real logic of both `Flatten` and `FlatMap` which simply delegate to
 235 /// this type.
 236 #[derive(Clone, Debug)]
 237 struct FlattenCompat<I, U> {
 238     iter: Fuse<I>,
 239     frontiter: Option<U>,
 240     backiter: Option<U>,
 241 }
 242 impl<I, U> FlattenCompat<I, U>
 243 where
 244     I: Iterator,
 245 {
 246     /// Adapts an iterator by flattening it, for use in `flatten()` and `flat_map()`.
 247     fn new(iter: I) -> FlattenCompat<I, U> {
 248         FlattenCompat { iter: iter.fuse(), frontiter: None, backiter: None }
 249     }
 250 }
 251
 252 impl<I, U> Iterator for FlattenCompat<I, U>
 253 where
 254     I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 255     U: Iterator,
 256 {
 257     type Item = U::Item;
 258
 259     #[inline]
 260     fn next(&mut self) -> Option<U::Item> {
 261         loop {
 262             if let Some(ref mut inner) = self.frontiter {
 263                 match inner.next() {
 264                     None => self.frontiter = None,
 265                     elt @ Some(_) => 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 { 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                 match inner.next_back() {
 352                     None => self.backiter = None,
 353                     elt @ Some(_) => return elt,
 354                 }
 355             }
 356             match self.iter.next_back() {
 357                 None => return self.frontiter.as_mut()?.next_back(),
 358                 next => self.backiter = next.map(IntoIterator::into_iter),
 359             }
 360         }
 361     }
 362
 363     #[inline]
 364     fn try_rfold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
 365     where
 366         Self: Sized,
 367         Fold: FnMut(Acc, Self::Item) -> R,
 368         R: Try<Ok = Acc>,
 369     {
 370         #[inline]
 371         fn flatten<'a, T: IntoIterator, Acc, R: Try<Ok = Acc>>(
 372             backiter: &'a mut Option<T::IntoIter>,
 373             fold: &'a mut impl FnMut(Acc, T::Item) -> R,
 374         ) -> impl FnMut(Acc, T) -> R + 'a
 375         where
 376             T::IntoIter: DoubleEndedIterator,
 377         {
 378             move |acc, x| {
 379                 let mut mid = x.into_iter();
 380                 let r = mid.try_rfold(acc, &mut *fold);
 381                 *backiter = Some(mid);
 382                 r
 383             }
 384         }
 385
 386         if let Some(ref mut back) = self.backiter {
 387             init = back.try_rfold(init, &mut fold)?;
 388         }
 389         self.backiter = None;
 390
 391         init = self.iter.try_rfold(init, flatten(&mut self.backiter, &mut fold))?;
 392         self.backiter = None;
 393
 394         if let Some(ref mut front) = self.frontiter {
 395             init = front.try_rfold(init, &mut fold)?;
 396         }
 397         self.frontiter = None;
 398
 399         try { init }
 400     }
 401
 402     #[inline]
 403     fn rfold<Acc, Fold>(self, init: Acc, ref mut fold: Fold) -> Acc
 404     where
 405         Fold: FnMut(Acc, Self::Item) -> Acc,
 406     {
 407         #[inline]
 408         fn flatten<U: DoubleEndedIterator, Acc>(
 409             fold: &mut impl FnMut(Acc, U::Item) -> Acc,
 410         ) -> impl FnMut(Acc, U) -> Acc + '_ {
 411             move |acc, iter| iter.rfold(acc, &mut *fold)
 412         }
 413
 414         self.frontiter
 415             .into_iter()
 416             .chain(self.iter.map(IntoIterator::into_iter))
 417             .chain(self.backiter)
 418             .rfold(init, flatten(fold))
 419     }
 420 }