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 [`Iterator::flat_map`]. See its documentation
  11 /// for more.
  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>,
  16 }
  17
  18 impl<I: Iterator, U: IntoIterator, F: FnMut(I::Item) -> U> FlatMap<I, U, F> {
  19     pub(in crate::iter) fn new(iter: I, f: F) -> FlatMap<I, U, F> {
  20         FlatMap { inner: FlattenCompat::new(iter.map(f)) }
  21     }
  22 }
  23
  24 #[stable(feature = "rust1", since = "1.0.0")]
  25 impl<I: Clone, U, F: Clone> Clone for FlatMap<I, U, F>
  26 where
  27     U: Clone + IntoIterator<IntoIter: Clone>,
  28 {
  29     fn clone(&self) -> Self {
  30         FlatMap { inner: self.inner.clone() }
  31     }
  32 }
  33
  34 #[stable(feature = "core_impl_debug", since = "1.9.0")]
  35 impl<I: fmt::Debug, U, F> fmt::Debug for FlatMap<I, U, F>
  36 where
  37     U: IntoIterator<IntoIter: fmt::Debug>,
  38 {
  39     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  40         f.debug_struct("FlatMap").field("inner", &self.inner).finish()
  41     }
  42 }
  43
  44 #[stable(feature = "rust1", since = "1.0.0")]
  45 impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F>
  46 where
  47     F: FnMut(I::Item) -> U,
  48 {
  49     type Item = U::Item;
  50
  51     #[inline]
  52     fn next(&mut self) -> Option<U::Item> {
  53         self.inner.next()
  54     }
  55
  56     #[inline]
  57     fn size_hint(&self) -> (usize, Option<usize>) {
  58         self.inner.size_hint()
  59     }
  60
  61     #[inline]
  62     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
  63     where
  64         Self: Sized,
  65         Fold: FnMut(Acc, Self::Item) -> R,
  66         R: Try<Ok = Acc>,
  67     {
  68         self.inner.try_fold(init, fold)
  69     }
  70
  71     #[inline]
  72     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
  73     where
  74         Fold: FnMut(Acc, Self::Item) -> Acc,
  75     {
  76         self.inner.fold(init, fold)
  77     }
  78 }
  79
  80 #[stable(feature = "rust1", since = "1.0.0")]
  81 impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F>
  82 where
  83     F: FnMut(I::Item) -> U,
  84     U: IntoIterator<IntoIter: DoubleEndedIterator>,
  85 {
  86     #[inline]
  87     fn next_back(&mut self) -> Option<U::Item> {
  88         self.inner.next_back()
  89     }
  90
  91     #[inline]
  92     fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
  93     where
  94         Self: Sized,
  95         Fold: FnMut(Acc, Self::Item) -> R,
  96         R: Try<Ok = Acc>,
  97     {
  98         self.inner.try_rfold(init, fold)
  99     }
 100
 101     #[inline]
 102     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 103     where
 104         Fold: FnMut(Acc, Self::Item) -> Acc,
 105     {
 106         self.inner.rfold(init, fold)
 107     }
 108 }
 109
 110 #[stable(feature = "fused", since = "1.26.0")]
 111 impl<I, U, F> FusedIterator for FlatMap<I, U, F>
 112 where
 113     I: FusedIterator,
 114     U: IntoIterator,
 115     F: FnMut(I::Item) -> U,
 116 {
 117 }
 118
 119 /// An iterator that flattens one level of nesting in an iterator of things
 120 /// that can be turned into iterators.
 121 ///
 122 /// This `struct` is created by the [`flatten`] method on [`Iterator`]. See its
 123 /// documentation for more.
 124 ///
 125 /// [`flatten`]: Iterator::flatten
 126 /// [`Iterator`]: trait.Iterator.html
 127 #[must_use = "iterators are lazy and do nothing unless consumed"]
 128 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 129 pub struct Flatten<I: Iterator<Item: IntoIterator>> {
 130     inner: FlattenCompat<I, <I::Item as IntoIterator>::IntoIter>,
 131 }
 132
 133 impl<I: Iterator<Item: IntoIterator>> Flatten<I> {
 134     pub(in super::super) fn new(iter: I) -> Flatten<I> {
 135         Flatten { inner: FlattenCompat::new(iter) }
 136     }
 137 }
 138
 139 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 140 impl<I, U> fmt::Debug for Flatten<I>
 141 where
 142     I: fmt::Debug + Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 143     U: fmt::Debug + Iterator,
 144 {
 145     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 146         f.debug_struct("Flatten").field("inner", &self.inner).finish()
 147     }
 148 }
 149
 150 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 151 impl<I, U> Clone for Flatten<I>
 152 where
 153     I: Clone + Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 154     U: Clone + Iterator,
 155 {
 156     fn clone(&self) -> Self {
 157         Flatten { inner: self.inner.clone() }
 158     }
 159 }
 160
 161 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 162 impl<I, U> Iterator for Flatten<I>
 163 where
 164     I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 165     U: Iterator,
 166 {
 167     type Item = U::Item;
 168
 169     #[inline]
 170     fn next(&mut self) -> Option<U::Item> {
 171         self.inner.next()
 172     }
 173
 174     #[inline]
 175     fn size_hint(&self) -> (usize, Option<usize>) {
 176         self.inner.size_hint()
 177     }
 178
 179     #[inline]
 180     fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
 181     where
 182         Self: Sized,
 183         Fold: FnMut(Acc, Self::Item) -> R,
 184         R: Try<Ok = Acc>,
 185     {
 186         self.inner.try_fold(init, fold)
 187     }
 188
 189     #[inline]
 190     fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 191     where
 192         Fold: FnMut(Acc, Self::Item) -> Acc,
 193     {
 194         self.inner.fold(init, fold)
 195     }
 196 }
 197
 198 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 199 impl<I, U> DoubleEndedIterator for Flatten<I>
 200 where
 201     I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 202     U: DoubleEndedIterator,
 203 {
 204     #[inline]
 205     fn next_back(&mut self) -> Option<U::Item> {
 206         self.inner.next_back()
 207     }
 208
 209     #[inline]
 210     fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
 211     where
 212         Self: Sized,
 213         Fold: FnMut(Acc, Self::Item) -> R,
 214         R: Try<Ok = Acc>,
 215     {
 216         self.inner.try_rfold(init, fold)
 217     }
 218
 219     #[inline]
 220     fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
 221     where
 222         Fold: FnMut(Acc, Self::Item) -> Acc,
 223     {
 224         self.inner.rfold(init, fold)
 225     }
 226 }
 227
 228 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 229 impl<I, U> FusedIterator for Flatten<I>
 230 where
 231     I: FusedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 232     U: Iterator,
 233 {
 234 }
 235
 236 /// Real logic of both `Flatten` and `FlatMap` which simply delegate to
 237 /// this type.
 238 #[derive(Clone, Debug)]
 239 struct FlattenCompat<I, U> {
 240     iter: Fuse<I>,
 241     frontiter: Option<U>,
 242     backiter: Option<U>,
 243 }
 244 impl<I, U> FlattenCompat<I, U>
 245 where
 246     I: Iterator,
 247 {
 248     /// Adapts an iterator by flattening it, for use in `flatten()` and `flat_map()`.
 249     fn new(iter: I) -> FlattenCompat<I, U> {
 250         FlattenCompat { iter: iter.fuse(), frontiter: None, backiter: None }
 251     }
 252 }
 253
 254 impl<I, U> Iterator for FlattenCompat<I, U>
 255 where
 256     I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 257     U: Iterator,
 258 {
 259     type Item = U::Item;
 260
 261     #[inline]
 262     fn next(&mut self) -> Option<U::Item> {
 263         loop {
 264             if let Some(ref mut inner) = self.frontiter {
 265                 match inner.next() {
 266                     None => self.frontiter = None,
 267                     elt @ Some(_) => return elt,
 268                 }
 269             }
 270             match self.iter.next() {
 271                 None => return self.backiter.as_mut()?.next(),
 272                 Some(inner) => self.frontiter = Some(inner.into_iter()),
 273             }
 274         }
 275     }
 276
 277     #[inline]
 278     fn size_hint(&self) -> (usize, Option<usize>) {
 279         let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), U::size_hint);
 280         let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), U::size_hint);
 281         let lo = flo.saturating_add(blo);
 282         match (self.iter.size_hint(), fhi, bhi) {
 283             ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
 284             _ => (lo, None),
 285         }
 286     }
 287
 288     #[inline]
 289     fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
 290     where
 291         Self: Sized,
 292         Fold: FnMut(Acc, Self::Item) -> R,
 293         R: Try<Ok = Acc>,
 294     {
 295         #[inline]
 296         fn flatten<'a, T: IntoIterator, Acc, R: Try<Ok = Acc>>(
 297             frontiter: &'a mut Option<T::IntoIter>,
 298             fold: &'a mut impl FnMut(Acc, T::Item) -> R,
 299         ) -> impl FnMut(Acc, T) -> R + 'a {
 300             move |acc, x| {
 301                 let mut mid = x.into_iter();
 302                 let r = mid.try_fold(acc, &mut *fold);
 303                 *frontiter = Some(mid);
 304                 r
 305             }
 306         }
 307
 308         if let Some(ref mut front) = self.frontiter {
 309             init = front.try_fold(init, &mut fold)?;
 310         }
 311         self.frontiter = None;
 312
 313         init = self.iter.try_fold(init, flatten(&mut self.frontiter, &mut fold))?;
 314         self.frontiter = None;
 315
 316         if let Some(ref mut back) = self.backiter {
 317             init = back.try_fold(init, &mut fold)?;
 318         }
 319         self.backiter = None;
 320
 321         try { init }
 322     }
 323
 324     #[inline]
 325     fn fold<Acc, Fold>(self, init: Acc, ref mut fold: Fold) -> Acc
 326     where
 327         Fold: FnMut(Acc, Self::Item) -> Acc,
 328     {
 329         #[inline]
 330         fn flatten<U: Iterator, Acc>(
 331             fold: &mut impl FnMut(Acc, U::Item) -> Acc,
 332         ) -> impl FnMut(Acc, U) -> Acc + '_ {
 333             move |acc, iter| iter.fold(acc, &mut *fold)
 334         }
 335
 336         self.frontiter
 337             .into_iter()
 338             .chain(self.iter.map(IntoIterator::into_iter))
 339             .chain(self.backiter)
 340             .fold(init, flatten(fold))
 341     }
 342 }
 343
 344 impl<I, U> DoubleEndedIterator for FlattenCompat<I, U>
 345 where
 346     I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 347     U: DoubleEndedIterator,
 348 {
 349     #[inline]
 350     fn next_back(&mut self) -> Option<U::Item> {
 351         loop {
 352             if let Some(ref mut inner) = self.backiter {
 353                 match inner.next_back() {
 354                     None => self.backiter = None,
 355                     elt @ Some(_) => return elt,
 356                 }
 357             }
 358             match self.iter.next_back() {
 359                 None => return self.frontiter.as_mut()?.next_back(),
 360                 next => self.backiter = next.map(IntoIterator::into_iter),
 361             }
 362         }
 363     }
 364
 365     #[inline]
 366     fn try_rfold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
 367     where
 368         Self: Sized,
 369         Fold: FnMut(Acc, Self::Item) -> R,
 370         R: Try<Ok = Acc>,
 371     {
 372         #[inline]
 373         fn flatten<'a, T: IntoIterator, Acc, R: Try<Ok = Acc>>(
 374             backiter: &'a mut Option<T::IntoIter>,
 375             fold: &'a mut impl FnMut(Acc, T::Item) -> R,
 376         ) -> impl FnMut(Acc, T) -> R + 'a
 377         where
 378             T::IntoIter: DoubleEndedIterator,
 379         {
 380             move |acc, x| {
 381                 let mut mid = x.into_iter();
 382                 let r = mid.try_rfold(acc, &mut *fold);
 383                 *backiter = Some(mid);
 384                 r
 385             }
 386         }
 387
 388         if let Some(ref mut back) = self.backiter {
 389             init = back.try_rfold(init, &mut fold)?;
 390         }
 391         self.backiter = None;
 392
 393         init = self.iter.try_rfold(init, flatten(&mut self.backiter, &mut fold))?;
 394         self.backiter = None;
 395
 396         if let Some(ref mut front) = self.frontiter {
 397             init = front.try_rfold(init, &mut fold)?;
 398         }
 399         self.frontiter = None;
 400
 401         try { init }
 402     }
 403
 404     #[inline]
 405     fn rfold<Acc, Fold>(self, init: Acc, ref mut fold: Fold) -> Acc
 406     where
 407         Fold: FnMut(Acc, Self::Item) -> Acc,
 408     {
 409         #[inline]
 410         fn flatten<U: DoubleEndedIterator, Acc>(
 411             fold: &mut impl FnMut(Acc, U::Item) -> Acc,
 412         ) -> impl FnMut(Acc, U) -> Acc + '_ {
 413             move |acc, iter| iter.rfold(acc, &mut *fold)
 414         }
 415
 416         self.frontiter
 417             .into_iter()
 418             .chain(self.iter.map(IntoIterator::into_iter))
 419             .chain(self.backiter)
 420             .rfold(init, flatten(fold))
 421     }
 422 }