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 => match self.backiter.as_mut()?.next() {
 269                     None => {
 270                         self.backiter = None;
 271                         return None;
 272                     }
 273                     elt @ Some(_) => return elt,
 274                 },
 275                 Some(inner) => self.frontiter = Some(inner.into_iter()),
 276             }
 277         }
 278     }
 279
 280     #[inline]
 281     fn size_hint(&self) -> (usize, Option<usize>) {
 282         let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), U::size_hint);
 283         let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), U::size_hint);
 284         let lo = flo.saturating_add(blo);
 285         match (self.iter.size_hint(), fhi, bhi) {
 286             ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
 287             _ => (lo, None),
 288         }
 289     }
 290
 291     #[inline]
 292     fn try_fold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
 293     where
 294         Self: Sized,
 295         Fold: FnMut(Acc, Self::Item) -> R,
 296         R: Try<Ok = Acc>,
 297     {
 298         #[inline]
 299         fn flatten<'a, T: IntoIterator, Acc, R: Try<Ok = Acc>>(
 300             frontiter: &'a mut Option<T::IntoIter>,
 301             fold: &'a mut impl FnMut(Acc, T::Item) -> R,
 302         ) -> impl FnMut(Acc, T) -> R + 'a {
 303             move |acc, x| {
 304                 let mut mid = x.into_iter();
 305                 let r = mid.try_fold(acc, &mut *fold);
 306                 *frontiter = Some(mid);
 307                 r
 308             }
 309         }
 310
 311         if let Some(ref mut front) = self.frontiter {
 312             init = front.try_fold(init, &mut fold)?;
 313         }
 314         self.frontiter = None;
 315
 316         init = self.iter.try_fold(init, flatten(&mut self.frontiter, &mut fold))?;
 317         self.frontiter = None;
 318
 319         if let Some(ref mut back) = self.backiter {
 320             init = back.try_fold(init, &mut fold)?;
 321         }
 322         self.backiter = None;
 323
 324         try { init }
 325     }
 326
 327     #[inline]
 328     fn fold<Acc, Fold>(self, mut init: Acc, mut fold: Fold) -> Acc
 329     where
 330         Fold: FnMut(Acc, Self::Item) -> Acc,
 331     {
 332         #[inline]
 333         fn flatten<T: IntoIterator, Acc>(
 334             fold: &mut impl FnMut(Acc, T::Item) -> Acc,
 335         ) -> impl FnMut(Acc, T) -> Acc + '_ {
 336             move |acc, x| x.into_iter().fold(acc, &mut *fold)
 337         }
 338
 339         if let Some(front) = self.frontiter {
 340             init = front.fold(init, &mut fold);
 341         }
 342
 343         init = self.iter.fold(init, flatten(&mut fold));
 344
 345         if let Some(back) = self.backiter {
 346             init = back.fold(init, &mut fold);
 347         }
 348
 349         init
 350     }
 351 }
 352
 353 impl<I, U> DoubleEndedIterator for FlattenCompat<I, U>
 354 where
 355     I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
 356     U: DoubleEndedIterator,
 357 {
 358     #[inline]
 359     fn next_back(&mut self) -> Option<U::Item> {
 360         loop {
 361             if let Some(ref mut inner) = self.backiter {
 362                 match inner.next_back() {
 363                     None => self.backiter = None,
 364                     elt @ Some(_) => return elt,
 365                 }
 366             }
 367             match self.iter.next_back() {
 368                 None => match self.frontiter.as_mut()?.next_back() {
 369                     None => {
 370                         self.frontiter = None;
 371                         return None;
 372                     }
 373                     elt @ Some(_) => return elt,
 374                 },
 375                 next => self.backiter = next.map(IntoIterator::into_iter),
 376             }
 377         }
 378     }
 379
 380     #[inline]
 381     fn try_rfold<Acc, Fold, R>(&mut self, mut init: Acc, mut fold: Fold) -> R
 382     where
 383         Self: Sized,
 384         Fold: FnMut(Acc, Self::Item) -> R,
 385         R: Try<Ok = Acc>,
 386     {
 387         #[inline]
 388         fn flatten<'a, T: IntoIterator, Acc, R: Try<Ok = Acc>>(
 389             backiter: &'a mut Option<T::IntoIter>,
 390             fold: &'a mut impl FnMut(Acc, T::Item) -> R,
 391         ) -> impl FnMut(Acc, T) -> R + 'a
 392         where
 393             T::IntoIter: DoubleEndedIterator,
 394         {
 395             move |acc, x| {
 396                 let mut mid = x.into_iter();
 397                 let r = mid.try_rfold(acc, &mut *fold);
 398                 *backiter = Some(mid);
 399                 r
 400             }
 401         }
 402
 403         if let Some(ref mut back) = self.backiter {
 404             init = back.try_rfold(init, &mut fold)?;
 405         }
 406         self.backiter = None;
 407
 408         init = self.iter.try_rfold(init, flatten(&mut self.backiter, &mut fold))?;
 409         self.backiter = None;
 410
 411         if let Some(ref mut front) = self.frontiter {
 412             init = front.try_rfold(init, &mut fold)?;
 413         }
 414         self.frontiter = None;
 415
 416         try { init }
 417     }
 418
 419     #[inline]
 420     fn rfold<Acc, Fold>(self, mut init: Acc, mut fold: Fold) -> Acc
 421     where
 422         Fold: FnMut(Acc, Self::Item) -> Acc,
 423     {
 424         #[inline]
 425         fn flatten<T: IntoIterator, Acc>(
 426             fold: &mut impl FnMut(Acc, T::Item) -> Acc,
 427         ) -> impl FnMut(Acc, T) -> Acc + '_
 428         where
 429             T::IntoIter: DoubleEndedIterator,
 430         {
 431             move |acc, x| x.into_iter().rfold(acc, &mut *fold)
 432         }
 433
 434         if let Some(back) = self.backiter {
 435             init = back.rfold(init, &mut fold);
 436         }
 437
 438         init = self.iter.rfold(init, flatten(&mut fold));
 439
 440         if let Some(front) = self.frontiter {
 441             init = front.rfold(init, &mut fold);
 442         }
 443
 444         init
 445     }
 446 }