2 use crate::iter
::{DoubleEndedIterator, Fuse, FusedIterator, Iterator, Map, TrustedLen}
;
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 #[stable(feature = "rust1", since = "1.0.0")]
79 impl<I
: DoubleEndedIterator
, U
, F
> DoubleEndedIterator
for FlatMap
<I
, U
, F
>
81 F
: FnMut(I
::Item
) -> U
,
82 U
: IntoIterator
<IntoIter
: DoubleEndedIterator
>,
85 fn next_back(&mut self) -> Option
<U
::Item
> {
86 self.inner
.next_back()
90 fn try_rfold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
93 Fold
: FnMut(Acc
, Self::Item
) -> R
,
96 self.inner
.try_rfold(init
, fold
)
100 fn rfold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
102 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
104 self.inner
.rfold(init
, fold
)
108 #[stable(feature = "fused", since = "1.26.0")]
109 impl<I
, U
, F
> FusedIterator
for FlatMap
<I
, U
, F
>
113 F
: FnMut(I
::Item
) -> U
,
117 #[unstable(feature = "trusted_len", issue = "37572")]
118 unsafe impl<T
, I
, F
, const N
: usize> TrustedLen
for FlatMap
<I
, [T
; N
], F
>
121 F
: FnMut(I
::Item
) -> [T
; N
],
125 #[unstable(feature = "trusted_len", issue = "37572")]
126 unsafe impl<'a
, T
, I
, F
, const N
: usize> TrustedLen
for FlatMap
<I
, &'a
[T
; N
], F
>
129 F
: FnMut(I
::Item
) -> &'a
[T
; N
],
133 #[unstable(feature = "trusted_len", issue = "37572")]
134 unsafe impl<'a
, T
, I
, F
, const N
: usize> TrustedLen
for FlatMap
<I
, &'a
mut [T
; N
], F
>
137 F
: FnMut(I
::Item
) -> &'a
mut [T
; N
],
141 /// An iterator that flattens one level of nesting in an iterator of things
142 /// that can be turned into iterators.
144 /// This `struct` is created by the [`flatten`] method on [`Iterator`]. See its
145 /// documentation for more.
147 /// [`flatten`]: Iterator::flatten()
148 #[must_use = "iterators are lazy and do nothing unless consumed"]
149 #[stable(feature = "iterator_flatten", since = "1.29.0")]
150 pub struct Flatten
<I
: Iterator
<Item
: IntoIterator
>> {
151 inner
: FlattenCompat
<I
, <I
::Item
as IntoIterator
>::IntoIter
>,
154 impl<I
: Iterator
<Item
: IntoIterator
>> Flatten
<I
> {
155 pub(in super::super) fn new(iter
: I
) -> Flatten
<I
> {
156 Flatten { inner: FlattenCompat::new(iter) }
160 #[stable(feature = "iterator_flatten", since = "1.29.0")]
161 impl<I
, U
> fmt
::Debug
for Flatten
<I
>
163 I
: fmt
::Debug
+ Iterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
164 U
: fmt
::Debug
+ Iterator
,
166 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
167 f
.debug_struct("Flatten").field("inner", &self.inner
).finish()
171 #[stable(feature = "iterator_flatten", since = "1.29.0")]
172 impl<I
, U
> Clone
for Flatten
<I
>
174 I
: Clone
+ Iterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
177 fn clone(&self) -> Self {
178 Flatten { inner: self.inner.clone() }
182 #[stable(feature = "iterator_flatten", since = "1.29.0")]
183 impl<I
, U
> Iterator
for Flatten
<I
>
185 I
: Iterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
191 fn next(&mut self) -> Option
<U
::Item
> {
196 fn size_hint(&self) -> (usize, Option
<usize>) {
197 self.inner
.size_hint()
201 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
204 Fold
: FnMut(Acc
, Self::Item
) -> R
,
205 R
: Try
<Output
= Acc
>,
207 self.inner
.try_fold(init
, fold
)
211 fn fold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
213 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
215 self.inner
.fold(init
, fold
)
219 #[stable(feature = "iterator_flatten", since = "1.29.0")]
220 impl<I
, U
> DoubleEndedIterator
for Flatten
<I
>
222 I
: DoubleEndedIterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
223 U
: DoubleEndedIterator
,
226 fn next_back(&mut self) -> Option
<U
::Item
> {
227 self.inner
.next_back()
231 fn try_rfold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
234 Fold
: FnMut(Acc
, Self::Item
) -> R
,
235 R
: Try
<Output
= Acc
>,
237 self.inner
.try_rfold(init
, fold
)
241 fn rfold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
243 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
245 self.inner
.rfold(init
, fold
)
249 #[stable(feature = "iterator_flatten", since = "1.29.0")]
250 impl<I
, U
> FusedIterator
for Flatten
<I
>
252 I
: FusedIterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
257 #[unstable(feature = "trusted_len", issue = "37572")]
258 unsafe impl<I
> TrustedLen
for Flatten
<I
>
261 <I
as Iterator
>::Item
: TrustedConstSize
,
265 /// Real logic of both `Flatten` and `FlatMap` which simply delegate to
267 #[derive(Clone, Debug)]
268 struct FlattenCompat
<I
, U
> {
270 frontiter
: Option
<U
>,
273 impl<I
, U
> FlattenCompat
<I
, U
>
277 /// Adapts an iterator by flattening it, for use in `flatten()` and `flat_map()`.
278 fn new(iter
: I
) -> FlattenCompat
<I
, U
> {
279 FlattenCompat { iter: iter.fuse(), frontiter: None, backiter: None }
283 impl<I
, U
> Iterator
for FlattenCompat
<I
, U
>
285 I
: Iterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
291 fn next(&mut self) -> Option
<U
::Item
> {
293 if let Some(ref mut inner
) = self.frontiter
{
295 None
=> self.frontiter
= None
,
296 elt @
Some(_
) => return elt
,
299 match self.iter
.next() {
300 None
=> match self.backiter
.as_mut()?
.next() {
302 self.backiter
= None
;
305 elt @
Some(_
) => return elt
,
307 Some(inner
) => self.frontiter
= Some(inner
.into_iter()),
313 fn size_hint(&self) -> (usize, Option
<usize>) {
314 let (flo
, fhi
) = self.frontiter
.as_ref().map_or((0, Some(0)), U
::size_hint
);
315 let (blo
, bhi
) = self.backiter
.as_ref().map_or((0, Some(0)), U
::size_hint
);
316 let lo
= flo
.saturating_add(blo
);
318 if let Some(fixed_size
) = <<I
as Iterator
>::Item
as ConstSizeIntoIterator
>::size() {
319 let (lower
, upper
) = self.iter
.size_hint();
321 let lower
= lower
.saturating_mul(fixed_size
).saturating_add(lo
);
323 try { fhi?.checked_add(bhi?)?.checked_add(fixed_size.checked_mul(upper?)?)? }
;
325 return (lower
, upper
);
328 match (self.iter
.size_hint(), fhi
, bhi
) {
329 ((0, Some(0)), Some(a
), Some(b
)) => (lo
, a
.checked_add(b
)),
335 fn try_fold
<Acc
, Fold
, R
>(&mut self, mut init
: Acc
, mut fold
: Fold
) -> R
338 Fold
: FnMut(Acc
, Self::Item
) -> R
,
339 R
: Try
<Output
= Acc
>,
342 fn flatten
<'a
, T
: IntoIterator
, Acc
, R
: Try
<Output
= Acc
>>(
343 frontiter
: &'a
mut Option
<T
::IntoIter
>,
344 fold
: &'a
mut impl FnMut(Acc
, T
::Item
) -> R
,
345 ) -> impl FnMut(Acc
, T
) -> R
+ 'a
{
347 let mut mid
= x
.into_iter();
348 let r
= mid
.try_fold(acc
, &mut *fold
);
349 *frontiter
= Some(mid
);
354 if let Some(ref mut front
) = self.frontiter
{
355 init
= front
.try_fold(init
, &mut fold
)?
;
357 self.frontiter
= None
;
359 init
= self.iter
.try_fold(init
, flatten(&mut self.frontiter
, &mut fold
))?
;
360 self.frontiter
= None
;
362 if let Some(ref mut back
) = self.backiter
{
363 init
= back
.try_fold(init
, &mut fold
)?
;
365 self.backiter
= None
;
371 fn fold
<Acc
, Fold
>(self, mut init
: Acc
, mut fold
: Fold
) -> Acc
373 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
376 fn flatten
<T
: IntoIterator
, Acc
>(
377 fold
: &mut impl FnMut(Acc
, T
::Item
) -> Acc
,
378 ) -> impl FnMut(Acc
, T
) -> Acc
+ '_
{
379 move |acc
, x
| x
.into_iter().fold(acc
, &mut *fold
)
382 if let Some(front
) = self.frontiter
{
383 init
= front
.fold(init
, &mut fold
);
386 init
= self.iter
.fold(init
, flatten(&mut fold
));
388 if let Some(back
) = self.backiter
{
389 init
= back
.fold(init
, &mut fold
);
396 impl<I
, U
> DoubleEndedIterator
for FlattenCompat
<I
, U
>
398 I
: DoubleEndedIterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
399 U
: DoubleEndedIterator
,
402 fn next_back(&mut self) -> Option
<U
::Item
> {
404 if let Some(ref mut inner
) = self.backiter
{
405 match inner
.next_back() {
406 None
=> self.backiter
= None
,
407 elt @
Some(_
) => return elt
,
410 match self.iter
.next_back() {
411 None
=> match self.frontiter
.as_mut()?
.next_back() {
413 self.frontiter
= None
;
416 elt @
Some(_
) => return elt
,
418 next
=> self.backiter
= next
.map(IntoIterator
::into_iter
),
424 fn try_rfold
<Acc
, Fold
, R
>(&mut self, mut init
: Acc
, mut fold
: Fold
) -> R
427 Fold
: FnMut(Acc
, Self::Item
) -> R
,
428 R
: Try
<Output
= Acc
>,
431 fn flatten
<'a
, T
: IntoIterator
, Acc
, R
: Try
<Output
= Acc
>>(
432 backiter
: &'a
mut Option
<T
::IntoIter
>,
433 fold
: &'a
mut impl FnMut(Acc
, T
::Item
) -> R
,
434 ) -> impl FnMut(Acc
, T
) -> R
+ 'a
436 T
::IntoIter
: DoubleEndedIterator
,
439 let mut mid
= x
.into_iter();
440 let r
= mid
.try_rfold(acc
, &mut *fold
);
441 *backiter
= Some(mid
);
446 if let Some(ref mut back
) = self.backiter
{
447 init
= back
.try_rfold(init
, &mut fold
)?
;
449 self.backiter
= None
;
451 init
= self.iter
.try_rfold(init
, flatten(&mut self.backiter
, &mut fold
))?
;
452 self.backiter
= None
;
454 if let Some(ref mut front
) = self.frontiter
{
455 init
= front
.try_rfold(init
, &mut fold
)?
;
457 self.frontiter
= None
;
463 fn rfold
<Acc
, Fold
>(self, mut init
: Acc
, mut fold
: Fold
) -> Acc
465 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
468 fn flatten
<T
: IntoIterator
, Acc
>(
469 fold
: &mut impl FnMut(Acc
, T
::Item
) -> Acc
,
470 ) -> impl FnMut(Acc
, T
) -> Acc
+ '_
472 T
::IntoIter
: DoubleEndedIterator
,
474 move |acc
, x
| x
.into_iter().rfold(acc
, &mut *fold
)
477 if let Some(back
) = self.backiter
{
478 init
= back
.rfold(init
, &mut fold
);
481 init
= self.iter
.rfold(init
, flatten(&mut fold
));
483 if let Some(front
) = self.frontiter
{
484 init
= front
.rfold(init
, &mut fold
);
491 trait ConstSizeIntoIterator
: IntoIterator
{
492 // FIXME(#31844): convert to an associated const once specialization supports that
493 fn size() -> Option
<usize>;
496 impl<T
> ConstSizeIntoIterator
for T
501 default fn size() -> Option
<usize> {
506 impl<T
, const N
: usize> ConstSizeIntoIterator
for [T
; N
] {
508 fn size() -> Option
<usize> {
513 impl<T
, const N
: usize> ConstSizeIntoIterator
for &[T
; N
] {
515 fn size() -> Option
<usize> {
520 impl<T
, const N
: usize> ConstSizeIntoIterator
for &mut [T
; N
] {
522 fn size() -> Option
<usize> {
528 #[unstable(feature = "std_internals", issue = "none")]
529 // FIXME(#20400): Instead of this helper trait there should be multiple impl TrustedLen for Flatten<>
530 // blocks with different bounds on Iterator::Item but the compiler erroneously considers them overlapping
531 pub unsafe trait TrustedConstSize
: IntoIterator {}
533 #[unstable(feature = "std_internals", issue = "none")]
534 unsafe impl<T
, const N
: usize> TrustedConstSize
for [T
; N
] {}
535 #[unstable(feature = "std_internals", issue = "none")]
536 unsafe impl<T
, const N
: usize> TrustedConstSize
for &'_
[T
; N
] {}
537 #[unstable(feature = "std_internals", issue = "none")]
538 unsafe impl<T
, const N
: usize> TrustedConstSize
for &'_
mut [T
; N
] {}