/rust/registry/src/index.crates.io-1949cf8c6b5b557f/rayon-1.11.0/src/iter/intersperse.rs

Source
use super::plumbing::*;
use super::*;
use std::cell::Cell;
use std::iter::{self, Fuse};

/// `Intersperse` is an iterator that inserts a particular item between each
/// item of the adapted iterator.  This struct is created by the
/// [`intersperse()`] method on [`ParallelIterator`]
///
/// [`intersperse()`]: ParallelIterator::intersperse()
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[derive(Clone, Debug)]
pub struct Intersperse<I>
where
    I: ParallelIterator,
{
    base: I,
    item: I::Item,
}

impl<I> Intersperse<I>
where
    I: ParallelIterator<Item: Clone>,
{
    /// Creates a new `Intersperse` iterator
    pub(super) fn new(base: I, item: I::Item) -> Self {
        Intersperse { base, item }
    }
}

impl<I> ParallelIterator for Intersperse<I>
where
    I: ParallelIterator<Item: Clone>,
{
    type Item = I::Item;

    fn drive_unindexed<C>(self, consumer: C) -> C::Result
    where
        C: UnindexedConsumer<I::Item>,
    {
        let consumer1 = IntersperseConsumer::new(consumer, self.item);
        self.base.drive_unindexed(consumer1)
    }

    fn opt_len(&self) -> Option<usize> {
        match self.base.opt_len()? {
            0 => Some(0),
            len => len.checked_add(len - 1),
        }
    }
}

impl<I> IndexedParallelIterator for Intersperse<I>
where
    I: IndexedParallelIterator<Item: Clone>,
{
    fn drive<C>(self, consumer: C) -> C::Result
    where
        C: Consumer<Self::Item>,
    {
        let consumer1 = IntersperseConsumer::new(consumer, self.item);
        self.base.drive(consumer1)
    }

    fn len(&self) -> usize {
        let len = self.base.len();
        if len > 0 {
            len.checked_add(len - 1).expect("overflow")
        } else {
            0
        }
    }

    fn with_producer<CB>(self, callback: CB) -> CB::Output
    where
        CB: ProducerCallback<Self::Item>,
    {
        let len = self.len();
        return self.base.with_producer(Callback {
            callback,
            item: self.item,
            len,
        });

        struct Callback<CB, T> {
            callback: CB,
            item: T,
            len: usize,
        }

        impl<T, CB> ProducerCallback<T> for Callback<CB, T>
        where
            CB: ProducerCallback<T>,
            T: Clone + Send,
        {
            type Output = CB::Output;

            fn callback<P>(self, base: P) -> CB::Output
            where
                P: Producer<Item = T>,
            {
                let producer = IntersperseProducer::new(base, self.item, self.len);
                self.callback.callback(producer)
            }
        }
    }
}

struct IntersperseProducer<P>
where
    P: Producer,
{
    base: P,
    item: P::Item,
    len: usize,
    clone_first: bool,
}

impl<P> IntersperseProducer<P>
where
    P: Producer,
{
    fn new(base: P, item: P::Item, len: usize) -> Self {
        IntersperseProducer {
            base,
            item,
            len,
            clone_first: false,
        }
    }
}

impl<P> Producer for IntersperseProducer<P>
where
    P: Producer<Item: Clone + Send>,
{
    type Item = P::Item;
    type IntoIter = IntersperseIter<P::IntoIter>;

    fn into_iter(self) -> Self::IntoIter {
        IntersperseIter {
            base: self.base.into_iter().fuse(),
            item: self.item,
            clone_first: self.len > 0 && self.clone_first,

            // If there's more than one item, then even lengths end the opposite
            // of how they started with respect to interspersed clones.
            clone_last: self.len > 1 && ((self.len & 1 == 0) ^ self.clone_first),
        }
    }

    fn min_len(&self) -> usize {
        self.base.min_len()
    }
    fn max_len(&self) -> usize {
        self.base.max_len()
    }

    fn split_at(self, index: usize) -> (Self, Self) {
        debug_assert!(index <= self.len);

        // The left needs half of the items from the base producer, and the
        // other half will be our interspersed item.  If we're not leading with
        // a cloned item, then we need to round up the base number of items,
        // otherwise round down.
        let base_index = (index + !self.clone_first as usize) / 2;
        let (left_base, right_base) = self.base.split_at(base_index);

        let left = IntersperseProducer {
            base: left_base,
            item: self.item.clone(),
            len: index,
            clone_first: self.clone_first,
        };

        let right = IntersperseProducer {
            base: right_base,
            item: self.item,
            len: self.len - index,

            // If the index is odd, the right side toggles `clone_first`.
            clone_first: (index & 1 == 1) ^ self.clone_first,
        };

        (left, right)
    }

    fn fold_with<F>(self, folder: F) -> F
    where
        F: Folder<Self::Item>,
    {
        let folder1 = IntersperseFolder {
            base: folder,
            item: self.item,
            clone_first: self.clone_first,
        };
        self.base.fold_with(folder1).base
    }
}

struct IntersperseIter<I>
where
    I: Iterator,
{
    base: Fuse<I>,
    item: I::Item,
    clone_first: bool,
    clone_last: bool,
}

impl<I> Iterator for IntersperseIter<I>
where
    I: DoubleEndedIterator<Item: Clone> + ExactSizeIterator,
{
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        if self.clone_first {
            self.clone_first = false;
            Some(self.item.clone())
        } else if let next @ Some(_) = self.base.next() {
            // If there are any items left, we'll need another clone in front.
            self.clone_first = self.base.len() != 0;
            next
        } else if self.clone_last {
            self.clone_last = false;
            Some(self.item.clone())
        } else {
            None
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.len();
        (len, Some(len))
    }
}

impl<I> DoubleEndedIterator for IntersperseIter<I>
where
    I: DoubleEndedIterator<Item: Clone> + ExactSizeIterator,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.clone_last {
            self.clone_last = false;
            Some(self.item.clone())
        } else if let next_back @ Some(_) = self.base.next_back() {
            // If there are any items left, we'll need another clone in back.
            self.clone_last = self.base.len() != 0;
            next_back
        } else if self.clone_first {
            self.clone_first = false;
            Some(self.item.clone())
        } else {
            None
        }
    }
}

impl<I> ExactSizeIterator for IntersperseIter<I>
where
    I: DoubleEndedIterator<Item: Clone> + ExactSizeIterator,
{
    fn len(&self) -> usize {
        let len = self.base.len();
        len + len.saturating_sub(1) + self.clone_first as usize + self.clone_last as usize
    }
}

struct IntersperseConsumer<C, T> {
    base: C,
    item: T,
    clone_first: Cell<bool>,
}

impl<C, T> IntersperseConsumer<C, T>
where
    C: Consumer<T>,
{
    fn new(base: C, item: T) -> Self {
        IntersperseConsumer {
            base,
            item,
            clone_first: false.into(),
        }
    }
}

impl<C, T> Consumer<T> for IntersperseConsumer<C, T>
where
    C: Consumer<T>,
    T: Clone + Send,
{
    type Folder = IntersperseFolder<C::Folder, T>;
    type Reducer = C::Reducer;
    type Result = C::Result;

    fn split_at(mut self, index: usize) -> (Self, Self, Self::Reducer) {
        // We'll feed twice as many items to the base consumer, except if we're
        // not currently leading with a cloned item, then it's one less.
        let base_index = index + index.saturating_sub(!self.clone_first.get() as usize);
        let (left, right, reducer) = self.base.split_at(base_index);

        let right = IntersperseConsumer {
            base: right,
            item: self.item.clone(),
            clone_first: true.into(),
        };
        self.base = left;
        (self, right, reducer)
    }

    fn into_folder(self) -> Self::Folder {
        IntersperseFolder {
            base: self.base.into_folder(),
            item: self.item,
            clone_first: self.clone_first.get(),
        }
    }

    fn full(&self) -> bool {
        self.base.full()
    }
}

impl<C, T> UnindexedConsumer<T> for IntersperseConsumer<C, T>
where
    C: UnindexedConsumer<T>,
    T: Clone + Send,
{
    fn split_off_left(&self) -> Self {
        let left = IntersperseConsumer {
            base: self.base.split_off_left(),
            item: self.item.clone(),
            clone_first: self.clone_first.clone(),
        };
        self.clone_first.set(true);
        left
    }

    fn to_reducer(&self) -> Self::Reducer {
        self.base.to_reducer()
    }
}

struct IntersperseFolder<C, T> {
    base: C,
    item: T,
    clone_first: bool,
}

impl<C, T> Folder<T> for IntersperseFolder<C, T>
where
    C: Folder<T>,
    T: Clone,
{
    type Result = C::Result;

    fn consume(mut self, item: T) -> Self {
        if self.clone_first {
            self.base = self.base.consume(self.item.clone());
            if self.base.full() {
                return self;
            }
        } else {
            self.clone_first = true;
        }
        self.base = self.base.consume(item);
        self
    }

    fn consume_iter<I>(self, iter: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut clone_first = self.clone_first;
        let between_item = self.item;
        let base = self.base.consume_iter(iter.into_iter().flat_map(|item| {
            let first = if clone_first {
                Some(between_item.clone())
            } else {
                clone_first = true;
                None
            };
            first.into_iter().chain(iter::once(item))
        }));
        IntersperseFolder {
            base,
            item: between_item,
            clone_first,
        }
    }

    fn complete(self) -> C::Result {
        self.base.complete()
    }

    fn full(&self) -> bool {
        self.base.full()
    }
}

Coverage Report

Created: 2026-02-26 07:34

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