2 use crate::iter
::{DoubleEndedIterator, Fuse, FusedIterator, Iterator, Map, TrustedLen}
;
3 use crate::ops
::{ControlFlow, Try}
;
5 /// An iterator that maps each element to an iterator, and yields the elements
6 /// of the produced iterators.
8 /// This `struct` is created by [`Iterator::flat_map`]. See its documentation
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
>,
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)) }
22 #[stable(feature = "rust1", since = "1.0.0")]
23 impl<I
: Clone
, U
, F
: Clone
> Clone
for FlatMap
<I
, U
, F
>
25 U
: Clone
+ IntoIterator
<IntoIter
: Clone
>,
27 fn clone(&self) -> Self {
28 FlatMap { inner: self.inner.clone() }
32 #[stable(feature = "core_impl_debug", since = "1.9.0")]
33 impl<I
: fmt
::Debug
, U
, F
> fmt
::Debug
for FlatMap
<I
, U
, F
>
35 U
: IntoIterator
<IntoIter
: fmt
::Debug
>,
37 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
38 f
.debug_struct("FlatMap").field("inner", &self.inner
).finish()
42 #[stable(feature = "rust1", since = "1.0.0")]
43 impl<I
: Iterator
, U
: IntoIterator
, F
> Iterator
for FlatMap
<I
, U
, F
>
45 F
: FnMut(I
::Item
) -> U
,
50 fn next(&mut self) -> Option
<U
::Item
> {
55 fn size_hint(&self) -> (usize, Option
<usize>) {
56 self.inner
.size_hint()
60 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
63 Fold
: FnMut(Acc
, Self::Item
) -> R
,
66 self.inner
.try_fold(init
, fold
)
70 fn fold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
72 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
74 self.inner
.fold(init
, fold
)
78 fn advance_by(&mut self, n
: usize) -> Result
<(), usize> {
79 self.inner
.advance_by(n
)
83 fn count(self) -> usize {
88 fn last(self) -> Option
<Self::Item
> {
93 #[stable(feature = "rust1", since = "1.0.0")]
94 impl<I
: DoubleEndedIterator
, U
, F
> DoubleEndedIterator
for FlatMap
<I
, U
, F
>
96 F
: FnMut(I
::Item
) -> U
,
97 U
: IntoIterator
<IntoIter
: DoubleEndedIterator
>,
100 fn next_back(&mut self) -> Option
<U
::Item
> {
101 self.inner
.next_back()
105 fn try_rfold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
108 Fold
: FnMut(Acc
, Self::Item
) -> R
,
109 R
: Try
<Output
= Acc
>,
111 self.inner
.try_rfold(init
, fold
)
115 fn rfold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
117 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
119 self.inner
.rfold(init
, fold
)
123 fn advance_back_by(&mut self, n
: usize) -> Result
<(), usize> {
124 self.inner
.advance_back_by(n
)
128 #[stable(feature = "fused", since = "1.26.0")]
129 impl<I
, U
, F
> FusedIterator
for FlatMap
<I
, U
, F
>
133 F
: FnMut(I
::Item
) -> U
,
137 #[unstable(feature = "trusted_len", issue = "37572")]
138 unsafe impl<T
, I
, F
, const N
: usize> TrustedLen
for FlatMap
<I
, [T
; N
], F
>
141 F
: FnMut(I
::Item
) -> [T
; N
],
145 #[unstable(feature = "trusted_len", issue = "37572")]
146 unsafe impl<'a
, T
, I
, F
, const N
: usize> TrustedLen
for FlatMap
<I
, &'a
[T
; N
], F
>
149 F
: FnMut(I
::Item
) -> &'a
[T
; N
],
153 #[unstable(feature = "trusted_len", issue = "37572")]
154 unsafe impl<'a
, T
, I
, F
, const N
: usize> TrustedLen
for FlatMap
<I
, &'a
mut [T
; N
], F
>
157 F
: FnMut(I
::Item
) -> &'a
mut [T
; N
],
161 /// An iterator that flattens one level of nesting in an iterator of things
162 /// that can be turned into iterators.
164 /// This `struct` is created by the [`flatten`] method on [`Iterator`]. See its
165 /// documentation for more.
167 /// [`flatten`]: Iterator::flatten()
168 #[must_use = "iterators are lazy and do nothing unless consumed"]
169 #[stable(feature = "iterator_flatten", since = "1.29.0")]
170 pub struct Flatten
<I
: Iterator
<Item
: IntoIterator
>> {
171 inner
: FlattenCompat
<I
, <I
::Item
as IntoIterator
>::IntoIter
>,
174 impl<I
: Iterator
<Item
: IntoIterator
>> Flatten
<I
> {
175 pub(in super::super) fn new(iter
: I
) -> Flatten
<I
> {
176 Flatten { inner: FlattenCompat::new(iter) }
180 #[stable(feature = "iterator_flatten", since = "1.29.0")]
181 impl<I
, U
> fmt
::Debug
for Flatten
<I
>
183 I
: fmt
::Debug
+ Iterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
184 U
: fmt
::Debug
+ Iterator
,
186 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
187 f
.debug_struct("Flatten").field("inner", &self.inner
).finish()
191 #[stable(feature = "iterator_flatten", since = "1.29.0")]
192 impl<I
, U
> Clone
for Flatten
<I
>
194 I
: Clone
+ Iterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
197 fn clone(&self) -> Self {
198 Flatten { inner: self.inner.clone() }
202 #[stable(feature = "iterator_flatten", since = "1.29.0")]
203 impl<I
, U
> Iterator
for Flatten
<I
>
205 I
: Iterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
211 fn next(&mut self) -> Option
<U
::Item
> {
216 fn size_hint(&self) -> (usize, Option
<usize>) {
217 self.inner
.size_hint()
221 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
224 Fold
: FnMut(Acc
, Self::Item
) -> R
,
225 R
: Try
<Output
= Acc
>,
227 self.inner
.try_fold(init
, fold
)
231 fn fold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
233 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
235 self.inner
.fold(init
, fold
)
239 fn advance_by(&mut self, n
: usize) -> Result
<(), usize> {
240 self.inner
.advance_by(n
)
244 fn count(self) -> usize {
249 fn last(self) -> Option
<Self::Item
> {
254 #[stable(feature = "iterator_flatten", since = "1.29.0")]
255 impl<I
, U
> DoubleEndedIterator
for Flatten
<I
>
257 I
: DoubleEndedIterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
258 U
: DoubleEndedIterator
,
261 fn next_back(&mut self) -> Option
<U
::Item
> {
262 self.inner
.next_back()
266 fn try_rfold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
269 Fold
: FnMut(Acc
, Self::Item
) -> R
,
270 R
: Try
<Output
= Acc
>,
272 self.inner
.try_rfold(init
, fold
)
276 fn rfold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
278 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
280 self.inner
.rfold(init
, fold
)
284 fn advance_back_by(&mut self, n
: usize) -> Result
<(), usize> {
285 self.inner
.advance_back_by(n
)
289 #[stable(feature = "iterator_flatten", since = "1.29.0")]
290 impl<I
, U
> FusedIterator
for Flatten
<I
>
292 I
: FusedIterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
297 #[unstable(feature = "trusted_len", issue = "37572")]
298 unsafe impl<I
> TrustedLen
for Flatten
<I
>
301 <I
as Iterator
>::Item
: TrustedConstSize
,
305 /// Real logic of both `Flatten` and `FlatMap` which simply delegate to
307 #[derive(Clone, Debug)]
308 struct FlattenCompat
<I
, U
> {
310 frontiter
: Option
<U
>,
313 impl<I
, U
> FlattenCompat
<I
, U
>
317 /// Adapts an iterator by flattening it, for use in `flatten()` and `flat_map()`.
318 fn new(iter
: I
) -> FlattenCompat
<I
, U
> {
319 FlattenCompat { iter: iter.fuse(), frontiter: None, backiter: None }
323 impl<I
, U
> FlattenCompat
<I
, U
>
325 I
: Iterator
<Item
: IntoIterator
<IntoIter
= U
>>,
327 /// Folds the inner iterators into an accumulator by applying an operation.
329 /// Folds over the inner iterators, not over their elements. Is used by the `fold`, `count`,
330 /// and `last` methods.
332 fn iter_fold
<Acc
, Fold
>(self, mut acc
: Acc
, mut fold
: Fold
) -> Acc
334 Fold
: FnMut(Acc
, U
) -> Acc
,
337 fn flatten
<T
: IntoIterator
, Acc
>(
338 fold
: &mut impl FnMut(Acc
, T
::IntoIter
) -> Acc
,
339 ) -> impl FnMut(Acc
, T
) -> Acc
+ '_
{
340 move |acc
, iter
| fold(acc
, iter
.into_iter())
343 if let Some(iter
) = self.frontiter
{
344 acc
= fold(acc
, iter
);
347 acc
= self.iter
.fold(acc
, flatten(&mut fold
));
349 if let Some(iter
) = self.backiter
{
350 acc
= fold(acc
, iter
);
356 /// Folds over the inner iterators as long as the given function returns successfully,
357 /// always storing the most recent inner iterator in `self.frontiter`.
359 /// Folds over the inner iterators, not over their elements. Is used by the `try_fold` and
360 /// `advance_by` methods.
362 fn iter_try_fold
<Acc
, Fold
, R
>(&mut self, mut acc
: Acc
, mut fold
: Fold
) -> R
364 Fold
: FnMut(Acc
, &mut U
) -> R
,
365 R
: Try
<Output
= Acc
>,
368 fn flatten
<'a
, T
: IntoIterator
, Acc
, R
: Try
<Output
= Acc
>>(
369 frontiter
: &'a
mut Option
<T
::IntoIter
>,
370 fold
: &'a
mut impl FnMut(Acc
, &mut T
::IntoIter
) -> R
,
371 ) -> impl FnMut(Acc
, T
) -> R
+ 'a
{
372 move |acc
, iter
| fold(acc
, frontiter
.insert(iter
.into_iter()))
375 if let Some(iter
) = &mut self.frontiter
{
376 acc
= fold(acc
, iter
)?
;
378 self.frontiter
= None
;
380 acc
= self.iter
.try_fold(acc
, flatten(&mut self.frontiter
, &mut fold
))?
;
381 self.frontiter
= None
;
383 if let Some(iter
) = &mut self.backiter
{
384 acc
= fold(acc
, iter
)?
;
386 self.backiter
= None
;
392 impl<I
, U
> FlattenCompat
<I
, U
>
394 I
: DoubleEndedIterator
<Item
: IntoIterator
<IntoIter
= U
>>,
396 /// Folds the inner iterators into an accumulator by applying an operation, starting form the
399 /// Folds over the inner iterators, not over their elements. Is used by the `rfold` method.
401 fn iter_rfold
<Acc
, Fold
>(self, mut acc
: Acc
, mut fold
: Fold
) -> Acc
403 Fold
: FnMut(Acc
, U
) -> Acc
,
406 fn flatten
<T
: IntoIterator
, Acc
>(
407 fold
: &mut impl FnMut(Acc
, T
::IntoIter
) -> Acc
,
408 ) -> impl FnMut(Acc
, T
) -> Acc
+ '_
{
409 move |acc
, iter
| fold(acc
, iter
.into_iter())
412 if let Some(iter
) = self.backiter
{
413 acc
= fold(acc
, iter
);
416 acc
= self.iter
.rfold(acc
, flatten(&mut fold
));
418 if let Some(iter
) = self.frontiter
{
419 acc
= fold(acc
, iter
);
425 /// Folds over the inner iterators in reverse order as long as the given function returns
426 /// successfully, always storing the most recent inner iterator in `self.backiter`.
428 /// Folds over the inner iterators, not over their elements. Is used by the `try_rfold` and
429 /// `advance_back_by` methods.
431 fn iter_try_rfold
<Acc
, Fold
, R
>(&mut self, mut acc
: Acc
, mut fold
: Fold
) -> R
433 Fold
: FnMut(Acc
, &mut U
) -> R
,
434 R
: Try
<Output
= Acc
>,
437 fn flatten
<'a
, T
: IntoIterator
, Acc
, R
: Try
>(
438 backiter
: &'a
mut Option
<T
::IntoIter
>,
439 fold
: &'a
mut impl FnMut(Acc
, &mut T
::IntoIter
) -> R
,
440 ) -> impl FnMut(Acc
, T
) -> R
+ 'a
{
441 move |acc
, iter
| fold(acc
, backiter
.insert(iter
.into_iter()))
444 if let Some(iter
) = &mut self.backiter
{
445 acc
= fold(acc
, iter
)?
;
447 self.backiter
= None
;
449 acc
= self.iter
.try_rfold(acc
, flatten(&mut self.backiter
, &mut fold
))?
;
450 self.backiter
= None
;
452 if let Some(iter
) = &mut self.frontiter
{
453 acc
= fold(acc
, iter
)?
;
455 self.frontiter
= None
;
461 impl<I
, U
> Iterator
for FlattenCompat
<I
, U
>
463 I
: Iterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
469 fn next(&mut self) -> Option
<U
::Item
> {
471 if let elt @
Some(_
) = and_then_or_clear(&mut self.frontiter
, Iterator
::next
) {
474 match self.iter
.next() {
475 None
=> return and_then_or_clear(&mut self.backiter
, Iterator
::next
),
476 Some(inner
) => self.frontiter
= Some(inner
.into_iter()),
482 fn size_hint(&self) -> (usize, Option
<usize>) {
483 let (flo
, fhi
) = self.frontiter
.as_ref().map_or((0, Some(0)), U
::size_hint
);
484 let (blo
, bhi
) = self.backiter
.as_ref().map_or((0, Some(0)), U
::size_hint
);
485 let lo
= flo
.saturating_add(blo
);
487 if let Some(fixed_size
) = <<I
as Iterator
>::Item
as ConstSizeIntoIterator
>::size() {
488 let (lower
, upper
) = self.iter
.size_hint();
490 let lower
= lower
.saturating_mul(fixed_size
).saturating_add(lo
);
492 try { fhi?.checked_add(bhi?)?.checked_add(fixed_size.checked_mul(upper?)?)? }
;
494 return (lower
, upper
);
497 match (self.iter
.size_hint(), fhi
, bhi
) {
498 ((0, Some(0)), Some(a
), Some(b
)) => (lo
, a
.checked_add(b
)),
504 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
507 Fold
: FnMut(Acc
, Self::Item
) -> R
,
508 R
: Try
<Output
= Acc
>,
511 fn flatten
<U
: Iterator
, Acc
, R
: Try
<Output
= Acc
>>(
512 mut fold
: impl FnMut(Acc
, U
::Item
) -> R
,
513 ) -> impl FnMut(Acc
, &mut U
) -> R
{
514 move |acc
, iter
| iter
.try_fold(acc
, &mut fold
)
517 self.iter_try_fold(init
, flatten(fold
))
521 fn fold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
523 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
526 fn flatten
<U
: Iterator
, Acc
>(
527 mut fold
: impl FnMut(Acc
, U
::Item
) -> Acc
,
528 ) -> impl FnMut(Acc
, U
) -> Acc
{
529 move |acc
, iter
| iter
.fold(acc
, &mut fold
)
532 self.iter_fold(init
, flatten(fold
))
536 #[rustc_inherit_overflow_checks]
537 fn advance_by(&mut self, n
: usize) -> Result
<(), usize> {
539 #[rustc_inherit_overflow_checks]
540 fn advance
<U
: Iterator
>(n
: usize, iter
: &mut U
) -> ControlFlow
<(), usize> {
541 match iter
.advance_by(n
) {
542 Ok(()) => ControlFlow
::BREAK
,
543 Err(advanced
) => ControlFlow
::Continue(n
- advanced
),
547 match self.iter_try_fold(n
, advance
) {
548 ControlFlow
::Continue(remaining
) if remaining
> 0 => Err(n
- remaining
),
554 fn count(self) -> usize {
556 #[rustc_inherit_overflow_checks]
557 fn count
<U
: Iterator
>(acc
: usize, iter
: U
) -> usize {
561 self.iter_fold(0, count
)
565 fn last(self) -> Option
<Self::Item
> {
567 fn last
<U
: Iterator
>(last
: Option
<U
::Item
>, iter
: U
) -> Option
<U
::Item
> {
571 self.iter_fold(None
, last
)
575 impl<I
, U
> DoubleEndedIterator
for FlattenCompat
<I
, U
>
577 I
: DoubleEndedIterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
578 U
: DoubleEndedIterator
,
581 fn next_back(&mut self) -> Option
<U
::Item
> {
583 if let elt @
Some(_
) = and_then_or_clear(&mut self.backiter
, |b
| b
.next_back()) {
586 match self.iter
.next_back() {
587 None
=> return and_then_or_clear(&mut self.frontiter
, |f
| f
.next_back()),
588 Some(inner
) => self.backiter
= Some(inner
.into_iter()),
594 fn try_rfold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
597 Fold
: FnMut(Acc
, Self::Item
) -> R
,
598 R
: Try
<Output
= Acc
>,
601 fn flatten
<U
: DoubleEndedIterator
, Acc
, R
: Try
<Output
= Acc
>>(
602 mut fold
: impl FnMut(Acc
, U
::Item
) -> R
,
603 ) -> impl FnMut(Acc
, &mut U
) -> R
{
604 move |acc
, iter
| iter
.try_rfold(acc
, &mut fold
)
607 self.iter_try_rfold(init
, flatten(fold
))
611 fn rfold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
613 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
616 fn flatten
<U
: DoubleEndedIterator
, Acc
>(
617 mut fold
: impl FnMut(Acc
, U
::Item
) -> Acc
,
618 ) -> impl FnMut(Acc
, U
) -> Acc
{
619 move |acc
, iter
| iter
.rfold(acc
, &mut fold
)
622 self.iter_rfold(init
, flatten(fold
))
626 #[rustc_inherit_overflow_checks]
627 fn advance_back_by(&mut self, n
: usize) -> Result
<(), usize> {
629 #[rustc_inherit_overflow_checks]
630 fn advance
<U
: DoubleEndedIterator
>(n
: usize, iter
: &mut U
) -> ControlFlow
<(), usize> {
631 match iter
.advance_back_by(n
) {
632 Ok(()) => ControlFlow
::BREAK
,
633 Err(advanced
) => ControlFlow
::Continue(n
- advanced
),
637 match self.iter_try_rfold(n
, advance
) {
638 ControlFlow
::Continue(remaining
) if remaining
> 0 => Err(n
- remaining
),
644 trait ConstSizeIntoIterator
: IntoIterator
{
645 // FIXME(#31844): convert to an associated const once specialization supports that
646 fn size() -> Option
<usize>;
649 impl<T
> ConstSizeIntoIterator
for T
654 default fn size() -> Option
<usize> {
659 impl<T
, const N
: usize> ConstSizeIntoIterator
for [T
; N
] {
661 fn size() -> Option
<usize> {
666 impl<T
, const N
: usize> ConstSizeIntoIterator
for &[T
; N
] {
668 fn size() -> Option
<usize> {
673 impl<T
, const N
: usize> ConstSizeIntoIterator
for &mut [T
; N
] {
675 fn size() -> Option
<usize> {
681 #[unstable(feature = "std_internals", issue = "none")]
682 // FIXME(#20400): Instead of this helper trait there should be multiple impl TrustedLen for Flatten<>
683 // blocks with different bounds on Iterator::Item but the compiler erroneously considers them overlapping
684 pub unsafe trait TrustedConstSize
: IntoIterator {}
686 #[unstable(feature = "std_internals", issue = "none")]
687 unsafe impl<T
, const N
: usize> TrustedConstSize
for [T
; N
] {}
688 #[unstable(feature = "std_internals", issue = "none")]
689 unsafe impl<T
, const N
: usize> TrustedConstSize
for &'_
[T
; N
] {}
690 #[unstable(feature = "std_internals", issue = "none")]
691 unsafe impl<T
, const N
: usize> TrustedConstSize
for &'_
mut [T
; N
] {}
694 fn and_then_or_clear
<T
, U
>(opt
: &mut Option
<T
>, f
: impl FnOnce(&mut T
) -> Option
<U
>) -> Option
<U
> {
695 let x
= f(opt
.as_mut()?
);