1use super::size_hint;
2use std::iter::{Fuse, FusedIterator};
3
4pub trait IntersperseElement<Item> {
5 fn generate(&mut self) -> Item;
6}
7
8#[derive(Debug, Clone)]
9pub struct IntersperseElementSimple<Item>(Item);
10
11impl<Item: Clone> IntersperseElement<Item> for IntersperseElementSimple<Item> {
12 fn generate(&mut self) -> Item {
13 self.0.clone()
14 }
15}
16
17/// An iterator adaptor to insert a particular value
18/// between each element of the adapted iterator.
19///
20/// Iterator element type is `I::Item`
21///
22/// This iterator is *fused*.
23///
24/// See [`.intersperse()`](crate::Itertools::intersperse) for more information.
25pub type Intersperse<I> = IntersperseWith<I, IntersperseElementSimple<<I as Iterator>::Item>>;
26
27/// Create a new Intersperse iterator
28pub fn intersperse<I>(iter: I, elt: I::Item) -> Intersperse<I>
29where
30 I: Iterator,
31{
32 intersperse_with(iter, elt:IntersperseElementSimple(elt))
33}
34
35impl<Item, F: FnMut() -> Item> IntersperseElement<Item> for F {
36 fn generate(&mut self) -> Item {
37 self()
38 }
39}
40
41/// An iterator adaptor to insert a particular value created by a function
42/// between each element of the adapted iterator.
43///
44/// Iterator element type is `I::Item`
45///
46/// This iterator is *fused*.
47///
48/// See [`.intersperse_with()`](crate::Itertools::intersperse_with) for more information.
49#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
50#[derive(Clone, Debug)]
51pub struct IntersperseWith<I, ElemF>
52where
53 I: Iterator,
54{
55 element: ElemF,
56 iter: Fuse<I>,
57 /// `peek` is None while no item have been taken out of `iter` (at definition).
58 /// Then `peek` will alternatively be `Some(None)` and `Some(Some(item))`,
59 /// where `None` indicates it's time to generate from `element` (unless `iter` is empty).
60 peek: Option<Option<I::Item>>,
61}
62
63/// Create a new `IntersperseWith` iterator
64pub fn intersperse_with<I, ElemF>(iter: I, elt: ElemF) -> IntersperseWith<I, ElemF>
65where
66 I: Iterator,
67{
68 IntersperseWith {
69 peek: None,
70 iter: iter.fuse(),
71 element: elt,
72 }
73}
74
75impl<I, ElemF> Iterator for IntersperseWith<I, ElemF>
76where
77 I: Iterator,
78 ElemF: IntersperseElement<I::Item>,
79{
80 type Item = I::Item;
81 #[inline]
82 fn next(&mut self) -> Option<Self::Item> {
83 let Self {
84 element,
85 iter,
86 peek,
87 } = self;
88 match peek {
89 Some(item @ Some(_)) => item.take(),
90 Some(None) => match iter.next() {
91 new @ Some(_) => {
92 *peek = Some(new);
93 Some(element.generate())
94 }
95 None => None,
96 },
97 None => {
98 *peek = Some(None);
99 iter.next()
100 }
101 }
102 }
103
104 fn size_hint(&self) -> (usize, Option<usize>) {
105 let mut sh = self.iter.size_hint();
106 sh = size_hint::add(sh, sh);
107 match self.peek {
108 Some(Some(_)) => size_hint::add_scalar(sh, 1),
109 Some(None) => sh,
110 None => size_hint::sub_scalar(sh, 1),
111 }
112 }
113
114 fn fold<B, F>(self, init: B, mut f: F) -> B
115 where
116 Self: Sized,
117 F: FnMut(B, Self::Item) -> B,
118 {
119 let Self {
120 mut element,
121 mut iter,
122 peek,
123 } = self;
124 let mut accum = init;
125
126 if let Some(x) = peek.unwrap_or_else(|| iter.next()) {
127 accum = f(accum, x);
128 }
129
130 iter.fold(accum, |accum, x| {
131 let accum = f(accum, element.generate());
132 f(accum, x)
133 })
134 }
135}
136
137impl<I, ElemF> FusedIterator for IntersperseWith<I, ElemF>
138where
139 I: Iterator,
140 ElemF: IntersperseElement<I::Item>,
141{
142}
143