core/iter/adapters/
intersperse.rs

1use crate::fmt;
2use crate::iter::{Fuse, FusedIterator};
3
4/// An iterator adapter that places a separator between all elements.
5///
6/// This `struct` is created by [`Iterator::intersperse`]. See its documentation
7/// for more information.
8#[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
9#[derive(Debug, Clone)]
10pub struct Intersperse<I: Iterator>
11where
12    I::Item: Clone,
13{
14    started: bool,
15    separator: I::Item,
16    next_item: Option<I::Item>,
17    iter: Fuse<I>,
18}
19
20#[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
21impl<I> FusedIterator for Intersperse<I>
22where
23    I: FusedIterator,
24    I::Item: Clone,
25{
26}
27
28impl<I: Iterator> Intersperse<I>
29where
30    I::Item: Clone,
31{
32    pub(in crate::iter) fn new(iter: I, separator: I::Item) -> Self {
33        Self { started: false, separator, next_item: None, iter: iter.fuse() }
34    }
35}
36
37#[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
38impl<I> Iterator for Intersperse<I>
39where
40    I: Iterator,
41    I::Item: Clone,
42{
43    type Item = I::Item;
44
45    #[inline]
46    fn next(&mut self) -> Option<Self::Item> {
47        if self.started {
48            if let Some(v) = self.next_item.take() {
49                Some(v)
50            } else {
51                let next_item = self.iter.next();
52                if next_item.is_some() {
53                    self.next_item = next_item;
54                    Some(self.separator.clone())
55                } else {
56                    None
57                }
58            }
59        } else {
60            self.started = true;
61            self.iter.next()
62        }
63    }
64
65    fn size_hint(&self) -> (usize, Option<usize>) {
66        intersperse_size_hint(&self.iter, self.started, self.next_item.is_some())
67    }
68
69    fn fold<B, F>(self, init: B, f: F) -> B
70    where
71        Self: Sized,
72        F: FnMut(B, Self::Item) -> B,
73    {
74        let separator = self.separator;
75        intersperse_fold(
76            self.iter,
77            init,
78            f,
79            move || separator.clone(),
80            self.started,
81            self.next_item,
82        )
83    }
84}
85
86/// An iterator adapter that places a separator between all elements.
87///
88/// This `struct` is created by [`Iterator::intersperse_with`]. See its
89/// documentation for more information.
90#[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
91pub struct IntersperseWith<I, G>
92where
93    I: Iterator,
94{
95    started: bool,
96    separator: G,
97    next_item: Option<I::Item>,
98    iter: Fuse<I>,
99}
100
101#[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
102impl<I, G> FusedIterator for IntersperseWith<I, G>
103where
104    I: FusedIterator,
105    G: FnMut() -> I::Item,
106{
107}
108
109#[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
110impl<I, G> fmt::Debug for IntersperseWith<I, G>
111where
112    I: Iterator + fmt::Debug,
113    I::Item: fmt::Debug,
114    G: fmt::Debug,
115{
116    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
117        f.debug_struct("IntersperseWith")
118            .field("started", &self.started)
119            .field("separator", &self.separator)
120            .field("iter", &self.iter)
121            .field("next_item", &self.next_item)
122            .finish()
123    }
124}
125
126#[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
127impl<I, G> Clone for IntersperseWith<I, G>
128where
129    I: Iterator + Clone,
130    I::Item: Clone,
131    G: Clone,
132{
133    fn clone(&self) -> Self {
134        Self {
135            started: self.started,
136            separator: self.separator.clone(),
137            iter: self.iter.clone(),
138            next_item: self.next_item.clone(),
139        }
140    }
141}
142
143impl<I, G> IntersperseWith<I, G>
144where
145    I: Iterator,
146    G: FnMut() -> I::Item,
147{
148    pub(in crate::iter) fn new(iter: I, separator: G) -> Self {
149        Self { started: false, separator, next_item: None, iter: iter.fuse() }
150    }
151}
152
153#[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
154impl<I, G> Iterator for IntersperseWith<I, G>
155where
156    I: Iterator,
157    G: FnMut() -> I::Item,
158{
159    type Item = I::Item;
160
161    #[inline]
162    fn next(&mut self) -> Option<Self::Item> {
163        if self.started {
164            if let Some(v) = self.next_item.take() {
165                Some(v)
166            } else {
167                let next_item = self.iter.next();
168                if next_item.is_some() {
169                    self.next_item = next_item;
170                    Some((self.separator)())
171                } else {
172                    None
173                }
174            }
175        } else {
176            self.started = true;
177            self.iter.next()
178        }
179    }
180
181    fn size_hint(&self) -> (usize, Option<usize>) {
182        intersperse_size_hint(&self.iter, self.started, self.next_item.is_some())
183    }
184
185    fn fold<B, F>(self, init: B, f: F) -> B
186    where
187        Self: Sized,
188        F: FnMut(B, Self::Item) -> B,
189    {
190        intersperse_fold(self.iter, init, f, self.separator, self.started, self.next_item)
191    }
192}
193
194fn intersperse_size_hint<I>(iter: &I, started: bool, next_is_some: bool) -> (usize, Option<usize>)
195where
196    I: Iterator,
197{
198    let (lo, hi) = iter.size_hint();
199    (
200        lo.saturating_sub(!started as usize)
201            .saturating_add(next_is_some as usize)
202            .saturating_add(lo),
203        hi.and_then(|hi| {
204            hi.saturating_sub(!started as usize)
205                .saturating_add(next_is_some as usize)
206                .checked_add(hi)
207        }),
208    )
209}
210
211fn intersperse_fold<I, B, F, G>(
212    mut iter: I,
213    init: B,
214    mut f: F,
215    mut separator: G,
216    started: bool,
217    mut next_item: Option<I::Item>,
218) -> B
219where
220    I: Iterator,
221    F: FnMut(B, I::Item) -> B,
222    G: FnMut() -> I::Item,
223{
224    let mut accum = init;
225
226    let first = if started { next_item.take() } else { iter.next() };
227    if let Some(x) = first {
228        accum = f(accum, x);
229    }
230
231    iter.fold(accum, |mut accum, x| {
232        accum = f(accum, separator());
233        accum = f(accum, x);
234        accum
235    })
236}