4 use super::super::{DoubleEndedIterator, FusedIterator, Iterator}
;
7 /// An iterator that maps each element to an iterator, and yields the elements
8 /// of the produced iterators.
10 /// This `struct` is created by the [`flat_map`] method on [`Iterator`]. See its
11 /// documentation for more.
13 /// [`flat_map`]: trait.Iterator.html#method.flat_map
14 /// [`Iterator`]: trait.Iterator.html
15 #[must_use = "iterators are lazy and do nothing unless consumed"]
16 #[stable(feature = "rust1", since = "1.0.0")]
17 pub struct FlatMap
<I
, U
: IntoIterator
, F
> {
18 inner
: FlattenCompat
<Map
<I
, F
>, <U
as IntoIterator
>::IntoIter
>,
20 impl<I
: Iterator
, U
: IntoIterator
, F
: FnMut(I
::Item
) -> U
> FlatMap
<I
, U
, F
> {
21 pub(in super::super) fn new(iter
: I
, f
: F
) -> FlatMap
<I
, U
, F
> {
22 FlatMap { inner: FlattenCompat::new(iter.map(f)) }
26 #[stable(feature = "rust1", since = "1.0.0")]
27 impl<I
: Clone
, U
, F
: Clone
> Clone
for FlatMap
<I
, U
, F
>
29 U
: Clone
+ IntoIterator
<IntoIter
: Clone
>,
31 fn clone(&self) -> Self {
32 FlatMap { inner: self.inner.clone() }
36 #[stable(feature = "core_impl_debug", since = "1.9.0")]
37 impl<I
: fmt
::Debug
, U
, F
> fmt
::Debug
for FlatMap
<I
, U
, F
>
39 U
: IntoIterator
<IntoIter
: fmt
::Debug
>,
41 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
42 f
.debug_struct("FlatMap").field("inner", &self.inner
).finish()
46 #[stable(feature = "rust1", since = "1.0.0")]
47 impl<I
: Iterator
, U
: IntoIterator
, F
> Iterator
for FlatMap
<I
, U
, F
>
49 F
: FnMut(I
::Item
) -> U
,
54 fn next(&mut self) -> Option
<U
::Item
> {
59 fn size_hint(&self) -> (usize, Option
<usize>) {
60 self.inner
.size_hint()
64 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
67 Fold
: FnMut(Acc
, Self::Item
) -> R
,
70 self.inner
.try_fold(init
, fold
)
74 fn fold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
76 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
78 self.inner
.fold(init
, fold
)
82 #[stable(feature = "rust1", since = "1.0.0")]
83 impl<I
: DoubleEndedIterator
, U
, F
> DoubleEndedIterator
for FlatMap
<I
, U
, F
>
85 F
: FnMut(I
::Item
) -> U
,
86 U
: IntoIterator
<IntoIter
: DoubleEndedIterator
>,
89 fn next_back(&mut self) -> Option
<U
::Item
> {
90 self.inner
.next_back()
94 fn try_rfold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
97 Fold
: FnMut(Acc
, Self::Item
) -> R
,
100 self.inner
.try_rfold(init
, fold
)
104 fn rfold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
106 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
108 self.inner
.rfold(init
, fold
)
112 #[stable(feature = "fused", since = "1.26.0")]
113 impl<I
, U
, F
> FusedIterator
for FlatMap
<I
, U
, F
>
117 F
: FnMut(I
::Item
) -> U
,
121 /// An iterator that flattens one level of nesting in an iterator of things
122 /// that can be turned into iterators.
124 /// This `struct` is created by the [`flatten`] method on [`Iterator`]. See its
125 /// documentation for more.
127 /// [`flatten`]: trait.Iterator.html#method.flatten
128 /// [`Iterator`]: trait.Iterator.html
129 #[must_use = "iterators are lazy and do nothing unless consumed"]
130 #[stable(feature = "iterator_flatten", since = "1.29.0")]
131 pub struct Flatten
<I
: Iterator
<Item
: IntoIterator
>> {
132 inner
: FlattenCompat
<I
, <I
::Item
as IntoIterator
>::IntoIter
>,
135 impl<I
: Iterator
<Item
: IntoIterator
>> Flatten
<I
> {
136 pub(in super::super) fn new(iter
: I
) -> Flatten
<I
> {
137 Flatten { inner: FlattenCompat::new(iter) }
141 #[stable(feature = "iterator_flatten", since = "1.29.0")]
142 impl<I
, U
> fmt
::Debug
for Flatten
<I
>
144 I
: fmt
::Debug
+ Iterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
145 U
: fmt
::Debug
+ Iterator
,
147 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
148 f
.debug_struct("Flatten").field("inner", &self.inner
).finish()
152 #[stable(feature = "iterator_flatten", since = "1.29.0")]
153 impl<I
, U
> Clone
for Flatten
<I
>
155 I
: Clone
+ Iterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
158 fn clone(&self) -> Self {
159 Flatten { inner: self.inner.clone() }
163 #[stable(feature = "iterator_flatten", since = "1.29.0")]
164 impl<I
, U
> Iterator
for Flatten
<I
>
166 I
: Iterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
172 fn next(&mut self) -> Option
<U
::Item
> {
177 fn size_hint(&self) -> (usize, Option
<usize>) {
178 self.inner
.size_hint()
182 fn try_fold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
185 Fold
: FnMut(Acc
, Self::Item
) -> R
,
188 self.inner
.try_fold(init
, fold
)
192 fn fold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
194 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
196 self.inner
.fold(init
, fold
)
200 #[stable(feature = "iterator_flatten", since = "1.29.0")]
201 impl<I
, U
> DoubleEndedIterator
for Flatten
<I
>
203 I
: DoubleEndedIterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
204 U
: DoubleEndedIterator
,
207 fn next_back(&mut self) -> Option
<U
::Item
> {
208 self.inner
.next_back()
212 fn try_rfold
<Acc
, Fold
, R
>(&mut self, init
: Acc
, fold
: Fold
) -> R
215 Fold
: FnMut(Acc
, Self::Item
) -> R
,
218 self.inner
.try_rfold(init
, fold
)
222 fn rfold
<Acc
, Fold
>(self, init
: Acc
, fold
: Fold
) -> Acc
224 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
226 self.inner
.rfold(init
, fold
)
230 #[stable(feature = "iterator_flatten", since = "1.29.0")]
231 impl<I
, U
> FusedIterator
for Flatten
<I
>
233 I
: FusedIterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
238 /// Real logic of both `Flatten` and `FlatMap` which simply delegate to
240 #[derive(Clone, Debug)]
241 struct FlattenCompat
<I
, U
> {
243 frontiter
: Option
<U
>,
246 impl<I
, U
> FlattenCompat
<I
, U
> {
247 /// Adapts an iterator by flattening it, for use in `flatten()` and `flat_map()`.
248 fn new(iter
: I
) -> FlattenCompat
<I
, U
> {
249 FlattenCompat { iter, frontiter: None, backiter: None }
253 impl<I
, U
> Iterator
for FlattenCompat
<I
, U
>
255 I
: Iterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
261 fn next(&mut self) -> Option
<U
::Item
> {
263 if let Some(ref mut inner
) = self.frontiter
{
264 if let elt @
Some(_
) = inner
.next() {
268 match self.iter
.next() {
269 None
=> return self.backiter
.as_mut()?
.next(),
270 Some(inner
) => self.frontiter
= Some(inner
.into_iter()),
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
)),
287 fn try_fold
<Acc
, Fold
, R
>(&mut self, mut init
: Acc
, mut fold
: Fold
) -> R
290 Fold
: FnMut(Acc
, Self::Item
) -> R
,
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
{
299 let mut mid
= x
.into_iter();
300 let r
= mid
.try_fold(acc
, &mut *fold
);
301 *frontiter
= Some(mid
);
306 if let Some(ref mut front
) = self.frontiter
{
307 init
= front
.try_fold(init
, &mut fold
)?
;
309 self.frontiter
= None
;
311 init
= self.iter
.try_fold(init
, flatten(&mut self.frontiter
, &mut fold
))?
;
312 self.frontiter
= None
;
314 if let Some(ref mut back
) = self.backiter
{
315 init
= back
.try_fold(init
, &mut fold
)?
;
317 self.backiter
= None
;
323 fn fold
<Acc
, Fold
>(self, init
: Acc
, ref mut fold
: Fold
) -> Acc
325 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
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
)
336 .chain(self.iter
.map(IntoIterator
::into_iter
))
337 .chain(self.backiter
)
338 .fold(init
, flatten(fold
))
342 impl<I
, U
> DoubleEndedIterator
for FlattenCompat
<I
, U
>
344 I
: DoubleEndedIterator
<Item
: IntoIterator
<IntoIter
= U
, Item
= U
::Item
>>,
345 U
: DoubleEndedIterator
,
348 fn next_back(&mut self) -> Option
<U
::Item
> {
350 if let Some(ref mut inner
) = self.backiter
{
351 if let elt @
Some(_
) = inner
.next_back() {
355 match self.iter
.next_back() {
356 None
=> return self.frontiter
.as_mut()?
.next_back(),
357 next
=> self.backiter
= next
.map(IntoIterator
::into_iter
),
363 fn try_rfold
<Acc
, Fold
, R
>(&mut self, mut init
: Acc
, mut fold
: Fold
) -> R
366 Fold
: FnMut(Acc
, Self::Item
) -> R
,
370 fn flatten
<'a
, T
: IntoIterator
, Acc
, R
: Try
<Ok
= Acc
>>(
371 backiter
: &'a
mut Option
<T
::IntoIter
>,
372 fold
: &'a
mut impl FnMut(Acc
, T
::Item
) -> R
,
373 ) -> impl FnMut(Acc
, T
) -> R
+ 'a
375 T
::IntoIter
: DoubleEndedIterator
,
378 let mut mid
= x
.into_iter();
379 let r
= mid
.try_rfold(acc
, &mut *fold
);
380 *backiter
= Some(mid
);
385 if let Some(ref mut back
) = self.backiter
{
386 init
= back
.try_rfold(init
, &mut fold
)?
;
388 self.backiter
= None
;
390 init
= self.iter
.try_rfold(init
, flatten(&mut self.backiter
, &mut fold
))?
;
391 self.backiter
= None
;
393 if let Some(ref mut front
) = self.frontiter
{
394 init
= front
.try_rfold(init
, &mut fold
)?
;
396 self.frontiter
= None
;
402 fn rfold
<Acc
, Fold
>(self, init
: Acc
, ref mut fold
: Fold
) -> Acc
404 Fold
: FnMut(Acc
, Self::Item
) -> Acc
,
407 fn flatten
<U
: DoubleEndedIterator
, Acc
>(
408 fold
: &mut impl FnMut(Acc
, U
::Item
) -> Acc
,
409 ) -> impl FnMut(Acc
, U
) -> Acc
+ '_
{
410 move |acc
, iter
| iter
.rfold(acc
, &mut *fold
)
415 .chain(self.iter
.map(IntoIterator
::into_iter
))
416 .chain(self.backiter
)
417 .rfold(init
, flatten(fold
))