/rust/registry/src/index.crates.io-1949cf8c6b5b557f/rayon-1.10.0/src/iter/interleave.rs

Source
use super::plumbing::*;
use super::*;
use std::iter::Fuse;

/// `Interleave` is an iterator that interleaves elements of iterators
/// `i` and `j` in one continuous iterator. This struct is created by
/// the [`interleave()`] method on [`IndexedParallelIterator`]
///
/// [`interleave()`]: trait.IndexedParallelIterator.html#method.interleave
/// [`IndexedParallelIterator`]: trait.IndexedParallelIterator.html
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
#[derive(Debug, Clone)]
pub struct Interleave<I, J>
where
    I: IndexedParallelIterator,
    J: IndexedParallelIterator<Item = I::Item>,
{
    i: I,
    j: J,
}

impl<I, J> Interleave<I, J>
where
    I: IndexedParallelIterator,
    J: IndexedParallelIterator<Item = I::Item>,
{
    /// Creates a new `Interleave` iterator
    pub(super) fn new(i: I, j: J) -> Self {
        Interleave { i, j }
    }
}

impl<I, J> ParallelIterator for Interleave<I, J>
where
    I: IndexedParallelIterator,
    J: IndexedParallelIterator<Item = I::Item>,
{
    type Item = I::Item;

    fn drive_unindexed<C>(self, consumer: C) -> C::Result
    where
        C: Consumer<I::Item>,
    {
        bridge(self, consumer)
    }

    fn opt_len(&self) -> Option<usize> {
        Some(self.len())
    }
}

impl<I, J> IndexedParallelIterator for Interleave<I, J>
where
    I: IndexedParallelIterator,
    J: IndexedParallelIterator<Item = I::Item>,
{
    fn drive<C>(self, consumer: C) -> C::Result
    where
        C: Consumer<Self::Item>,
    {
        bridge(self, consumer)
    }

    fn len(&self) -> usize {
        self.i.len().checked_add(self.j.len()).expect("overflow")
    }

    fn with_producer<CB>(self, callback: CB) -> CB::Output
    where
        CB: ProducerCallback<Self::Item>,
    {
        let (i_len, j_len) = (self.i.len(), self.j.len());
        return self.i.with_producer(CallbackI {
            callback,
            i_len,
            j_len,
            i_next: false,
            j: self.j,
        });

        struct CallbackI<CB, J> {
            callback: CB,
            i_len: usize,
            j_len: usize,
            i_next: bool,
            j: J,
        }

        impl<CB, J> ProducerCallback<J::Item> for CallbackI<CB, J>
        where
            J: IndexedParallelIterator,
            CB: ProducerCallback<J::Item>,
        {
            type Output = CB::Output;

            fn callback<I>(self, i_producer: I) -> Self::Output
            where
                I: Producer<Item = J::Item>,
            {
                self.j.with_producer(CallbackJ {
                    i_producer,
                    i_len: self.i_len,
                    j_len: self.j_len,
                    i_next: self.i_next,
                    callback: self.callback,
                })
            }
        }

        struct CallbackJ<CB, I> {
            callback: CB,
            i_len: usize,
            j_len: usize,
            i_next: bool,
            i_producer: I,
        }

        impl<CB, I> ProducerCallback<I::Item> for CallbackJ<CB, I>
        where
            I: Producer,
            CB: ProducerCallback<I::Item>,
        {
            type Output = CB::Output;

            fn callback<J>(self, j_producer: J) -> Self::Output
            where
                J: Producer<Item = I::Item>,
            {
                let producer = InterleaveProducer::new(
                    self.i_producer,
                    j_producer,
                    self.i_len,
                    self.j_len,
                    self.i_next,
                );
                self.callback.callback(producer)
            }
        }
    }
}

struct InterleaveProducer<I, J>
where
    I: Producer,
    J: Producer<Item = I::Item>,
{
    i: I,
    j: J,
    i_len: usize,
    j_len: usize,
    i_next: bool,
}

impl<I, J> InterleaveProducer<I, J>
where
    I: Producer,
    J: Producer<Item = I::Item>,
{
    fn new(i: I, j: J, i_len: usize, j_len: usize, i_next: bool) -> InterleaveProducer<I, J> {
        InterleaveProducer {
            i,
            j,
            i_len,
            j_len,
            i_next,
        }
    }
}

impl<I, J> Producer for InterleaveProducer<I, J>
where
    I: Producer,
    J: Producer<Item = I::Item>,
{
    type Item = I::Item;
    type IntoIter = InterleaveSeq<I::IntoIter, J::IntoIter>;

    fn into_iter(self) -> Self::IntoIter {
        InterleaveSeq {
            i: self.i.into_iter().fuse(),
            j: self.j.into_iter().fuse(),
            i_next: self.i_next,
        }
    }

    fn min_len(&self) -> usize {
        Ord::max(self.i.min_len(), self.j.min_len())
    }

    fn max_len(&self) -> usize {
        Ord::min(self.i.max_len(), self.j.max_len())
    }

    /// We know 0 < index <= self.i_len + self.j_len
    ///
    /// Find a, b satisfying:
    ///
    ///  (1) 0 < a <= self.i_len
    ///  (2) 0 < b <= self.j_len
    ///  (3) a + b == index
    ///
    /// For even splits, set a = b = index/2.
    /// For odd splits, set a = (index/2)+1, b = index/2, if `i`
    /// should yield the next element, otherwise, if `j` should yield
    /// the next element, set a = index/2 and b = (index/2)+1
    fn split_at(self, index: usize) -> (Self, Self) {
        #[inline]
        fn odd_offset(flag: bool) -> usize {
            (!flag) as usize
        }

        let even = index % 2 == 0;
        let idx = index >> 1;

        // desired split
        let (i_idx, j_idx) = (
            idx + odd_offset(even || self.i_next),
            idx + odd_offset(even || !self.i_next),
        );

        let (i_split, j_split) = if self.i_len >= i_idx && self.j_len >= j_idx {
            (i_idx, j_idx)
        } else if self.i_len >= i_idx {
            // j too short
            (index - self.j_len, self.j_len)
        } else {
            // i too short
            (self.i_len, index - self.i_len)
        };

        let trailing_i_next = even == self.i_next;
        let (i_left, i_right) = self.i.split_at(i_split);
        let (j_left, j_right) = self.j.split_at(j_split);

        (
            InterleaveProducer::new(i_left, j_left, i_split, j_split, self.i_next),
            InterleaveProducer::new(
                i_right,
                j_right,
                self.i_len - i_split,
                self.j_len - j_split,
                trailing_i_next,
            ),
        )
    }
}

/// Wrapper for Interleave to implement DoubleEndedIterator and
/// ExactSizeIterator.
///
/// This iterator is fused.
struct InterleaveSeq<I, J> {
    i: Fuse<I>,
    j: Fuse<J>,

    /// Flag to control which iterator should provide the next element. When
    /// `false` then `i` produces the next element, otherwise `j` produces the
    /// next element.
    i_next: bool,
}

/// Iterator implementation for InterleaveSeq. This implementation is
/// taken more or less verbatim from itertools. It is replicated here
/// (instead of calling itertools directly), because we also need to
/// implement `DoubledEndedIterator` and `ExactSizeIterator`.
impl<I, J> Iterator for InterleaveSeq<I, J>
where
    I: Iterator,
    J: Iterator<Item = I::Item>,
{
    type Item = I::Item;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.i_next = !self.i_next;
        if self.i_next {
            match self.i.next() {
                None => self.j.next(),
                r => r,
            }
        } else {
            match self.j.next() {
                None => self.i.next(),
                r => r,
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let (ih, jh) = (self.i.size_hint(), self.j.size_hint());
        let min = ih.0.saturating_add(jh.0);
        let max = match (ih.1, jh.1) {
            (Some(x), Some(y)) => x.checked_add(y),
            _ => None,
        };
        (min, max)
    }
}

// The implementation for DoubleEndedIterator requires
// ExactSizeIterator to provide `next_back()`. The last element will
// come from the iterator that runs out last (ie has the most elements
// in it). If the iterators have the same number of elements, then the
// last iterator will provide the last element.
impl<I, J> DoubleEndedIterator for InterleaveSeq<I, J>
where
    I: DoubleEndedIterator + ExactSizeIterator,
    J: DoubleEndedIterator<Item = I::Item> + ExactSizeIterator<Item = I::Item>,
{
    #[inline]
    fn next_back(&mut self) -> Option<I::Item> {
        match self.i.len().cmp(&self.j.len()) {
            Ordering::Less => self.j.next_back(),
            Ordering::Equal => {
                if self.i_next {
                    self.i.next_back()
                } else {
                    self.j.next_back()
                }
            }
            Ordering::Greater => self.i.next_back(),
        }
    }
}

impl<I, J> ExactSizeIterator for InterleaveSeq<I, J>
where
    I: ExactSizeIterator,
    J: ExactSizeIterator<Item = I::Item>,
{
    #[inline]
    fn len(&self) -> usize {
        self.i.len() + self.j.len()
    }
}

Coverage Report

Created: 2026-02-14 06:16

Line	Count	Source
1		use super::plumbing::*;
2		use super::*;
3		use std::iter::Fuse;
4
5		/// `Interleave` is an iterator that interleaves elements of iterators
6		/// `i` and `j` in one continuous iterator. This struct is created by
7		/// the [`interleave()`] method on [`IndexedParallelIterator`]
8		///
9		/// [`interleave()`]: trait.IndexedParallelIterator.html#method.interleave
10		/// [`IndexedParallelIterator`]: trait.IndexedParallelIterator.html
11		#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
12		#[derive(Debug, Clone)]
13		pub struct Interleave<I, J>
14		where
15		I: IndexedParallelIterator,
16		J: IndexedParallelIterator<Item = I::Item>,
17		{
18		i: I,
19		j: J,
20		}
21
22		impl<I, J> Interleave<I, J>
23		where
24		I: IndexedParallelIterator,
25		J: IndexedParallelIterator<Item = I::Item>,
26		{
27		/// Creates a new `Interleave` iterator
28	0	pub(super) fn new(i: I, j: J) -> Self {
29	0	Interleave { i, j }
30	0	}
31		}
32
33		impl<I, J> ParallelIterator for Interleave<I, J>
34		where
35		I: IndexedParallelIterator,
36		J: IndexedParallelIterator<Item = I::Item>,
37		{
38		type Item = I::Item;
39
40	0	fn drive_unindexed<C>(self, consumer: C) -> C::Result
41	0	where
42	0	C: Consumer<I::Item>,
43		{
44	0	bridge(self, consumer)
45	0	}
46
47	0	fn opt_len(&self) -> Option<usize> {
48	0	Some(self.len())
49	0	}
50		}
51
52		impl<I, J> IndexedParallelIterator for Interleave<I, J>
53		where
54		I: IndexedParallelIterator,
55		J: IndexedParallelIterator<Item = I::Item>,
56		{
57	0	fn drive<C>(self, consumer: C) -> C::Result
58	0	where
59	0	C: Consumer<Self::Item>,
60		{
61	0	bridge(self, consumer)
62	0	}
63
64	0	fn len(&self) -> usize {
65	0	self.i.len().checked_add(self.j.len()).expect("overflow")
66	0	}
67
68	0	fn with_producer<CB>(self, callback: CB) -> CB::Output
69	0	where
70	0	CB: ProducerCallback<Self::Item>,
71		{
72	0	let (i_len, j_len) = (self.i.len(), self.j.len());
73	0	return self.i.with_producer(CallbackI {
74	0	callback,
75	0	i_len,
76	0	j_len,
77	0	i_next: false,
78	0	j: self.j,
79	0	});
80
81		struct CallbackI<CB, J> {
82		callback: CB,
83		i_len: usize,
84		j_len: usize,
85		i_next: bool,
86		j: J,
87		}
88
89		impl<CB, J> ProducerCallback<J::Item> for CallbackI<CB, J>
90		where
91		J: IndexedParallelIterator,
92		CB: ProducerCallback<J::Item>,
93		{
94		type Output = CB::Output;
95
96	0	fn callback<I>(self, i_producer: I) -> Self::Output
97	0	where
98	0	I: Producer<Item = J::Item>,
99		{
100	0	self.j.with_producer(CallbackJ {
101	0	i_producer,
102	0	i_len: self.i_len,
103	0	j_len: self.j_len,
104	0	i_next: self.i_next,
105	0	callback: self.callback,
106	0	})
107	0	}
108		}
109
110		struct CallbackJ<CB, I> {
111		callback: CB,
112		i_len: usize,
113		j_len: usize,
114		i_next: bool,
115		i_producer: I,
116		}
117
118		impl<CB, I> ProducerCallback<I::Item> for CallbackJ<CB, I>
119		where
120		I: Producer,
121		CB: ProducerCallback<I::Item>,
122		{
123		type Output = CB::Output;
124
125	0	fn callback<J>(self, j_producer: J) -> Self::Output
126	0	where
127	0	J: Producer<Item = I::Item>,
128		{
129	0	let producer = InterleaveProducer::new(
130	0	self.i_producer,
131	0	j_producer,
132	0	self.i_len,
133	0	self.j_len,
134	0	self.i_next,
135		);
136	0	self.callback.callback(producer)
137	0	}
138		}
139	0	}
140		}
141
142		struct InterleaveProducer<I, J>
143		where
144		I: Producer,
145		J: Producer<Item = I::Item>,
146		{
147		i: I,
148		j: J,
149		i_len: usize,
150		j_len: usize,
151		i_next: bool,
152		}
153
154		impl<I, J> InterleaveProducer<I, J>
155		where
156		I: Producer,
157		J: Producer<Item = I::Item>,
158		{
159	0	fn new(i: I, j: J, i_len: usize, j_len: usize, i_next: bool) -> InterleaveProducer<I, J> {
160	0	InterleaveProducer {
161	0	i,
162	0	j,
163	0	i_len,
164	0	j_len,
165	0	i_next,
166	0	}
167	0	}
168		}
169
170		impl<I, J> Producer for InterleaveProducer<I, J>
171		where
172		I: Producer,
173		J: Producer<Item = I::Item>,
174		{
175		type Item = I::Item;
176		type IntoIter = InterleaveSeq<I::IntoIter, J::IntoIter>;
177
178	0	fn into_iter(self) -> Self::IntoIter {
179	0	InterleaveSeq {
180	0	i: self.i.into_iter().fuse(),
181	0	j: self.j.into_iter().fuse(),
182	0	i_next: self.i_next,
183	0	}
184	0	}
185
186	0	fn min_len(&self) -> usize {
187	0	Ord::max(self.i.min_len(), self.j.min_len())
188	0	}
189
190	0	fn max_len(&self) -> usize {
191	0	Ord::min(self.i.max_len(), self.j.max_len())
192	0	}
193
194		/// We know 0 < index <= self.i_len + self.j_len
195		///
196		/// Find a, b satisfying:
197		///
198		/// (1) 0 < a <= self.i_len
199		/// (2) 0 < b <= self.j_len
200		/// (3) a + b == index
201		///
202		/// For even splits, set a = b = index/2.
203		/// For odd splits, set a = (index/2)+1, b = index/2, if `i`
204		/// should yield the next element, otherwise, if `j` should yield
205		/// the next element, set a = index/2 and b = (index/2)+1
206	0	fn split_at(self, index: usize) -> (Self, Self) {
207		#[inline]
208	0	fn odd_offset(flag: bool) -> usize {
209	0	(!flag) as usize
210	0	}
211
212	0	let even = index % 2 == 0;
213	0	let idx = index >> 1;
214
215		// desired split
216	0	let (i_idx, j_idx) = (
217	0	idx + odd_offset(even \|\| self.i_next),
218	0	idx + odd_offset(even \|\| !self.i_next),
219		);
220
221	0	let (i_split, j_split) = if self.i_len >= i_idx && self.j_len >= j_idx {
222	0	(i_idx, j_idx)
223	0	} else if self.i_len >= i_idx {
224		// j too short
225	0	(index - self.j_len, self.j_len)
226		} else {
227		// i too short
228	0	(self.i_len, index - self.i_len)
229		};
230
231	0	let trailing_i_next = even == self.i_next;
232	0	let (i_left, i_right) = self.i.split_at(i_split);
233	0	let (j_left, j_right) = self.j.split_at(j_split);
234
235	0	(
236	0	InterleaveProducer::new(i_left, j_left, i_split, j_split, self.i_next),
237	0	InterleaveProducer::new(
238	0	i_right,
239	0	j_right,
240	0	self.i_len - i_split,
241	0	self.j_len - j_split,
242	0	trailing_i_next,
243	0	),
244	0	)
245	0	}
246		}
247
248		/// Wrapper for Interleave to implement DoubleEndedIterator and
249		/// ExactSizeIterator.
250		///
251		/// This iterator is fused.
252		struct InterleaveSeq<I, J> {
253		i: Fuse<I>,
254		j: Fuse<J>,
255
256		/// Flag to control which iterator should provide the next element. When
257		/// `false` then `i` produces the next element, otherwise `j` produces the
258		/// next element.
259		i_next: bool,
260		}
261
262		/// Iterator implementation for InterleaveSeq. This implementation is
263		/// taken more or less verbatim from itertools. It is replicated here
264		/// (instead of calling itertools directly), because we also need to
265		/// implement `DoubledEndedIterator` and `ExactSizeIterator`.
266		impl<I, J> Iterator for InterleaveSeq<I, J>
267		where
268		I: Iterator,
269		J: Iterator<Item = I::Item>,
270		{
271		type Item = I::Item;
272
273		#[inline]
274	0	fn next(&mut self) -> Option<Self::Item> {
275	0	self.i_next = !self.i_next;
276	0	if self.i_next {
277	0	match self.i.next() {
278	0	None => self.j.next(),
279	0	r => r,
280		}
281		} else {
282	0	match self.j.next() {
283	0	None => self.i.next(),
284	0	r => r,
285		}
286		}
287	0	}
288
289	0	fn size_hint(&self) -> (usize, Option<usize>) {
290	0	let (ih, jh) = (self.i.size_hint(), self.j.size_hint());
291	0	let min = ih.0.saturating_add(jh.0);
292	0	let max = match (ih.1, jh.1) {
293	0	(Some(x), Some(y)) => x.checked_add(y),
294	0	_ => None,
295		};
296	0	(min, max)
297	0	}
298		}
299
300		// The implementation for DoubleEndedIterator requires
301		// ExactSizeIterator to provide `next_back()`. The last element will
302		// come from the iterator that runs out last (ie has the most elements
303		// in it). If the iterators have the same number of elements, then the
304		// last iterator will provide the last element.
305		impl<I, J> DoubleEndedIterator for InterleaveSeq<I, J>
306		where
307		I: DoubleEndedIterator + ExactSizeIterator,
308		J: DoubleEndedIterator<Item = I::Item> + ExactSizeIterator<Item = I::Item>,
309		{
310		#[inline]
311	0	fn next_back(&mut self) -> Option<I::Item> {
312	0	match self.i.len().cmp(&self.j.len()) {
313	0	Ordering::Less => self.j.next_back(),
314		Ordering::Equal => {
315	0	if self.i_next {
316	0	self.i.next_back()
317		} else {
318	0	self.j.next_back()
319		}
320		}
321	0	Ordering::Greater => self.i.next_back(),
322		}
323	0	}
324		}
325
326		impl<I, J> ExactSizeIterator for InterleaveSeq<I, J>
327		where
328		I: ExactSizeIterator,
329		J: ExactSizeIterator<Item = I::Item>,
330		{
331		#[inline]
332	0	fn len(&self) -> usize {
333	0	self.i.len() + self.j.len()
334	0	}
335		}