1use super::plumbing::*;
2use super::*;
3use std::cell::Cell;
4use std::iter::{self, Fuse};
5
6/// `Intersperse` is an iterator that inserts a particular item between each
7/// item of the adapted iterator. This struct is created by the
8/// [`intersperse()`] method on [`ParallelIterator`]
9///
10/// [`intersperse()`]: trait.ParallelIterator.html#method.intersperse
11/// [`ParallelIterator`]: trait.ParallelIterator.html
12#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
13#[derive(Clone, Debug)]
14pub struct Intersperse<I>
15where
16 I: ParallelIterator,
17 I::Item: Clone,
18{
19 base: I,
20 item: I::Item,
21}
22
23impl<I> Intersperse<I>
24where
25 I: ParallelIterator,
26 I::Item: Clone,
27{
28 /// Creates a new `Intersperse` iterator
29 pub(super) fn new(base: I, item: I::Item) -> Self {
30 Intersperse { base, item }
31 }
32}
33
34impl<I> ParallelIterator for Intersperse<I>
35where
36 I: ParallelIterator,
37 I::Item: Clone + Send,
38{
39 type Item = I::Item;
40
41 fn drive_unindexed<C>(self, consumer: C) -> C::Result
42 where
43 C: UnindexedConsumer<I::Item>,
44 {
45 let consumer1: IntersperseConsumer = IntersperseConsumer::new(base:consumer, self.item);
46 self.base.drive_unindexed(consumer:consumer1)
47 }
48
49 fn opt_len(&self) -> Option<usize> {
50 match self.base.opt_len()? {
51 0 => Some(0),
52 len: usize => len.checked_add(len - 1),
53 }
54 }
55}
56
57impl<I> IndexedParallelIterator for Intersperse<I>
58where
59 I: IndexedParallelIterator,
60 I::Item: Clone + Send,
61{
62 fn drive<C>(self, consumer: C) -> C::Result
63 where
64 C: Consumer<Self::Item>,
65 {
66 let consumer1 = IntersperseConsumer::new(consumer, self.item);
67 self.base.drive(consumer1)
68 }
69
70 fn len(&self) -> usize {
71 let len = self.base.len();
72 if len > 0 {
73 len.checked_add(len - 1).expect("overflow")
74 } else {
75 0
76 }
77 }
78
79 fn with_producer<CB>(self, callback: CB) -> CB::Output
80 where
81 CB: ProducerCallback<Self::Item>,
82 {
83 let len = self.len();
84 return self.base.with_producer(Callback {
85 callback,
86 item: self.item,
87 len,
88 });
89
90 struct Callback<CB, T> {
91 callback: CB,
92 item: T,
93 len: usize,
94 }
95
96 impl<T, CB> ProducerCallback<T> for Callback<CB, T>
97 where
98 CB: ProducerCallback<T>,
99 T: Clone + Send,
100 {
101 type Output = CB::Output;
102
103 fn callback<P>(self, base: P) -> CB::Output
104 where
105 P: Producer<Item = T>,
106 {
107 let producer = IntersperseProducer::new(base, self.item, self.len);
108 self.callback.callback(producer)
109 }
110 }
111 }
112}
113
114struct IntersperseProducer<P>
115where
116 P: Producer,
117{
118 base: P,
119 item: P::Item,
120 len: usize,
121 clone_first: bool,
122}
123
124impl<P> IntersperseProducer<P>
125where
126 P: Producer,
127{
128 fn new(base: P, item: P::Item, len: usize) -> Self {
129 IntersperseProducer {
130 base,
131 item,
132 len,
133 clone_first: false,
134 }
135 }
136}
137
138impl<P> Producer for IntersperseProducer<P>
139where
140 P: Producer,
141 P::Item: Clone + Send,
142{
143 type Item = P::Item;
144 type IntoIter = IntersperseIter<P::IntoIter>;
145
146 fn into_iter(self) -> Self::IntoIter {
147 IntersperseIter {
148 base: self.base.into_iter().fuse(),
149 item: self.item,
150 clone_first: self.len > 0 && self.clone_first,
151
152 // If there's more than one item, then even lengths end the opposite
153 // of how they started with respect to interspersed clones.
154 clone_last: self.len > 1 && ((self.len & 1 == 0) ^ self.clone_first),
155 }
156 }
157
158 fn min_len(&self) -> usize {
159 self.base.min_len()
160 }
161 fn max_len(&self) -> usize {
162 self.base.max_len()
163 }
164
165 fn split_at(self, index: usize) -> (Self, Self) {
166 debug_assert!(index <= self.len);
167
168 // The left needs half of the items from the base producer, and the
169 // other half will be our interspersed item. If we're not leading with
170 // a cloned item, then we need to round up the base number of items,
171 // otherwise round down.
172 let base_index = (index + !self.clone_first as usize) / 2;
173 let (left_base, right_base) = self.base.split_at(base_index);
174
175 let left = IntersperseProducer {
176 base: left_base,
177 item: self.item.clone(),
178 len: index,
179 clone_first: self.clone_first,
180 };
181
182 let right = IntersperseProducer {
183 base: right_base,
184 item: self.item,
185 len: self.len - index,
186
187 // If the index is odd, the right side toggles `clone_first`.
188 clone_first: (index & 1 == 1) ^ self.clone_first,
189 };
190
191 (left, right)
192 }
193
194 fn fold_with<F>(self, folder: F) -> F
195 where
196 F: Folder<Self::Item>,
197 {
198 let folder1 = IntersperseFolder {
199 base: folder,
200 item: self.item,
201 clone_first: self.clone_first,
202 };
203 self.base.fold_with(folder1).base
204 }
205}
206
207struct IntersperseIter<I>
208where
209 I: Iterator,
210{
211 base: Fuse<I>,
212 item: I::Item,
213 clone_first: bool,
214 clone_last: bool,
215}
216
217impl<I> Iterator for IntersperseIter<I>
218where
219 I: DoubleEndedIterator + ExactSizeIterator,
220 I::Item: Clone,
221{
222 type Item = I::Item;
223
224 fn next(&mut self) -> Option<Self::Item> {
225 if self.clone_first {
226 self.clone_first = false;
227 Some(self.item.clone())
228 } else if let next: Option @ Some(_) = self.base.next() {
229 // If there are any items left, we'll need another clone in front.
230 self.clone_first = self.base.len() != 0;
231 next
232 } else if self.clone_last {
233 self.clone_last = false;
234 Some(self.item.clone())
235 } else {
236 None
237 }
238 }
239
240 fn size_hint(&self) -> (usize, Option<usize>) {
241 let len: usize = self.len();
242 (len, Some(len))
243 }
244}
245
246impl<I> DoubleEndedIterator for IntersperseIter<I>
247where
248 I: DoubleEndedIterator + ExactSizeIterator,
249 I::Item: Clone,
250{
251 fn next_back(&mut self) -> Option<Self::Item> {
252 if self.clone_last {
253 self.clone_last = false;
254 Some(self.item.clone())
255 } else if let next_back: Option @ Some(_) = self.base.next_back() {
256 // If there are any items left, we'll need another clone in back.
257 self.clone_last = self.base.len() != 0;
258 next_back
259 } else if self.clone_first {
260 self.clone_first = false;
261 Some(self.item.clone())
262 } else {
263 None
264 }
265 }
266}
267
268impl<I> ExactSizeIterator for IntersperseIter<I>
269where
270 I: DoubleEndedIterator + ExactSizeIterator,
271 I::Item: Clone,
272{
273 fn len(&self) -> usize {
274 let len: usize = self.base.len();
275 len + len.saturating_sub(1) + self.clone_first as usize + self.clone_last as usize
276 }
277}
278
279struct IntersperseConsumer<C, T> {
280 base: C,
281 item: T,
282 clone_first: Cell<bool>,
283}
284
285impl<C, T> IntersperseConsumer<C, T>
286where
287 C: Consumer<T>,
288{
289 fn new(base: C, item: T) -> Self {
290 IntersperseConsumer {
291 base,
292 item,
293 clone_first: false.into(),
294 }
295 }
296}
297
298impl<C, T> Consumer<T> for IntersperseConsumer<C, T>
299where
300 C: Consumer<T>,
301 T: Clone + Send,
302{
303 type Folder = IntersperseFolder<C::Folder, T>;
304 type Reducer = C::Reducer;
305 type Result = C::Result;
306
307 fn split_at(mut self, index: usize) -> (Self, Self, Self::Reducer) {
308 // We'll feed twice as many items to the base consumer, except if we're
309 // not currently leading with a cloned item, then it's one less.
310 let base_index = index + index.saturating_sub(!self.clone_first.get() as usize);
311 let (left, right, reducer) = self.base.split_at(base_index);
312
313 let right = IntersperseConsumer {
314 base: right,
315 item: self.item.clone(),
316 clone_first: true.into(),
317 };
318 self.base = left;
319 (self, right, reducer)
320 }
321
322 fn into_folder(self) -> Self::Folder {
323 IntersperseFolder {
324 base: self.base.into_folder(),
325 item: self.item,
326 clone_first: self.clone_first.get(),
327 }
328 }
329
330 fn full(&self) -> bool {
331 self.base.full()
332 }
333}
334
335impl<C, T> UnindexedConsumer<T> for IntersperseConsumer<C, T>
336where
337 C: UnindexedConsumer<T>,
338 T: Clone + Send,
339{
340 fn split_off_left(&self) -> Self {
341 let left: IntersperseConsumer = IntersperseConsumer {
342 base: self.base.split_off_left(),
343 item: self.item.clone(),
344 clone_first: self.clone_first.clone(),
345 };
346 self.clone_first.set(val:true);
347 left
348 }
349
350 fn to_reducer(&self) -> Self::Reducer {
351 self.base.to_reducer()
352 }
353}
354
355struct IntersperseFolder<C, T> {
356 base: C,
357 item: T,
358 clone_first: bool,
359}
360
361impl<C, T> Folder<T> for IntersperseFolder<C, T>
362where
363 C: Folder<T>,
364 T: Clone,
365{
366 type Result = C::Result;
367
368 fn consume(mut self, item: T) -> Self {
369 if self.clone_first {
370 self.base = self.base.consume(self.item.clone());
371 if self.base.full() {
372 return self;
373 }
374 } else {
375 self.clone_first = true;
376 }
377 self.base = self.base.consume(item);
378 self
379 }
380
381 fn consume_iter<I>(self, iter: I) -> Self
382 where
383 I: IntoIterator<Item = T>,
384 {
385 let mut clone_first = self.clone_first;
386 let between_item = self.item;
387 let base = self.base.consume_iter(iter.into_iter().flat_map(|item| {
388 let first = if clone_first {
389 Some(between_item.clone())
390 } else {
391 clone_first = true;
392 None
393 };
394 first.into_iter().chain(iter::once(item))
395 }));
396 IntersperseFolder {
397 base,
398 item: between_item,
399 clone_first,
400 }
401 }
402
403 fn complete(self) -> C::Result {
404 self.base.complete()
405 }
406
407 fn full(&self) -> bool {
408 self.base.full()
409 }
410}
411