/rust/registry/src/index.crates.io-1949cf8c6b5b557f/itertools-0.14.0/src/merge_join.rs

Source
use std::cmp::Ordering;
use std::fmt;
use std::iter::{Fuse, FusedIterator};
use std::marker::PhantomData;

use either::Either;

use super::adaptors::{put_back, PutBack};
use crate::either_or_both::EitherOrBoth;
use crate::size_hint::{self, SizeHint};
#[cfg(doc)]
use crate::Itertools;

#[derive(Clone, Debug)]
pub struct MergeLte;

/// An iterator adaptor that merges the two base iterators in ascending order.
/// If both base iterators are sorted (ascending), the result is sorted.
///
/// Iterator element type is `I::Item`.
///
/// See [`.merge()`](crate::Itertools::merge_by) for more information.
pub type Merge<I, J> = MergeBy<I, J, MergeLte>;

/// Create an iterator that merges elements in `i` and `j`.
///
/// [`IntoIterator`] enabled version of [`Itertools::merge`](crate::Itertools::merge).
///
/// ```
/// use itertools::merge;
///
/// for elt in merge(&[1, 2, 3], &[2, 3, 4]) {
///     /* loop body */
///     # let _ = elt;
/// }
/// ```
pub fn merge<I, J>(
    i: I,
    j: J,
) -> Merge<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter>
where
    I: IntoIterator,
    J: IntoIterator<Item = I::Item>,
    I::Item: PartialOrd,
{
    merge_by_new(i, j, MergeLte)
}

/// An iterator adaptor that merges the two base iterators in ascending order.
/// If both base iterators are sorted (ascending), the result is sorted.
///
/// Iterator element type is `I::Item`.
///
/// See [`.merge_by()`](crate::Itertools::merge_by) for more information.
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
pub struct MergeBy<I: Iterator, J: Iterator, F> {
    left: PutBack<Fuse<I>>,
    right: PutBack<Fuse<J>>,
    cmp_fn: F,
}

/// Create a `MergeBy` iterator.
pub fn merge_by_new<I, J, F>(a: I, b: J, cmp: F) -> MergeBy<I::IntoIter, J::IntoIter, F>
where
    I: IntoIterator,
    J: IntoIterator<Item = I::Item>,
{
    MergeBy {
        left: put_back(a.into_iter().fuse()),
        right: put_back(b.into_iter().fuse()),
        cmp_fn: cmp,
    }
}

/// Return an iterator adaptor that merge-joins items from the two base iterators in ascending order.
///
/// [`IntoIterator`] enabled version of [`Itertools::merge_join_by`].
pub fn merge_join_by<I, J, F, T>(
    left: I,
    right: J,
    cmp_fn: F,
) -> MergeJoinBy<I::IntoIter, J::IntoIter, F>
where
    I: IntoIterator,
    J: IntoIterator,
    F: FnMut(&I::Item, &J::Item) -> T,
{
    MergeBy {
        left: put_back(left.into_iter().fuse()),
        right: put_back(right.into_iter().fuse()),
        cmp_fn: MergeFuncLR(cmp_fn, PhantomData),
    }
}

/// An iterator adaptor that merge-joins items from the two base iterators in ascending order.
///
/// See [`.merge_join_by()`](crate::Itertools::merge_join_by) for more information.
pub type MergeJoinBy<I, J, F> =
    MergeBy<I, J, MergeFuncLR<F, <F as FuncLR<<I as Iterator>::Item, <J as Iterator>::Item>>::T>>;

#[derive(Clone, Debug)]
pub struct MergeFuncLR<F, T>(F, PhantomData<T>);

pub trait FuncLR<L, R> {
    type T;
}

impl<L, R, T, F: FnMut(&L, &R) -> T> FuncLR<L, R> for F {
    type T = T;
}

pub trait OrderingOrBool<L, R> {
    type MergeResult;
    fn left(left: L) -> Self::MergeResult;
    fn right(right: R) -> Self::MergeResult;
    // "merge" never returns (Some(...), Some(...), ...) so Option<Either<I::Item, J::Item>>
    // is appealing but it is always followed by two put_backs, so we think the compiler is
    // smart enough to optimize it. Or we could move put_backs into "merge".
    fn merge(&mut self, left: L, right: R) -> (Option<Either<L, R>>, Self::MergeResult);
    fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint;
}

impl<L, R, F: FnMut(&L, &R) -> Ordering> OrderingOrBool<L, R> for MergeFuncLR<F, Ordering> {
    type MergeResult = EitherOrBoth<L, R>;
    fn left(left: L) -> Self::MergeResult {
        EitherOrBoth::Left(left)
    }
    fn right(right: R) -> Self::MergeResult {
        EitherOrBoth::Right(right)
    }
    fn merge(&mut self, left: L, right: R) -> (Option<Either<L, R>>, Self::MergeResult) {
        match self.0(&left, &right) {
            Ordering::Equal => (None, EitherOrBoth::Both(left, right)),
            Ordering::Less => (Some(Either::Right(right)), EitherOrBoth::Left(left)),
            Ordering::Greater => (Some(Either::Left(left)), EitherOrBoth::Right(right)),
        }
    }
    fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
        let (a_lower, a_upper) = left;
        let (b_lower, b_upper) = right;
        let lower = ::std::cmp::max(a_lower, b_lower);
        let upper = match (a_upper, b_upper) {
            (Some(x), Some(y)) => x.checked_add(y),
            _ => None,
        };
        (lower, upper)
    }
}

impl<L, R, F: FnMut(&L, &R) -> bool> OrderingOrBool<L, R> for MergeFuncLR<F, bool> {
    type MergeResult = Either<L, R>;
    fn left(left: L) -> Self::MergeResult {
        Either::Left(left)
    }
    fn right(right: R) -> Self::MergeResult {
        Either::Right(right)
    }
    fn merge(&mut self, left: L, right: R) -> (Option<Either<L, R>>, Self::MergeResult) {
        if self.0(&left, &right) {
            (Some(Either::Right(right)), Either::Left(left))
        } else {
            (Some(Either::Left(left)), Either::Right(right))
        }
    }
    fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
        // Not ExactSizeIterator because size may be larger than usize
        size_hint::add(left, right)
    }
}

impl<T, F: FnMut(&T, &T) -> bool> OrderingOrBool<T, T> for F {
    type MergeResult = T;
    fn left(left: T) -> Self::MergeResult {
        left
    }
    fn right(right: T) -> Self::MergeResult {
        right
    }
    fn merge(&mut self, left: T, right: T) -> (Option<Either<T, T>>, Self::MergeResult) {
        if self(&left, &right) {
            (Some(Either::Right(right)), left)
        } else {
            (Some(Either::Left(left)), right)
        }
    }
    fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
        // Not ExactSizeIterator because size may be larger than usize
        size_hint::add(left, right)
    }
}

impl<T: PartialOrd> OrderingOrBool<T, T> for MergeLte {
    type MergeResult = T;
    fn left(left: T) -> Self::MergeResult {
        left
    }
    fn right(right: T) -> Self::MergeResult {
        right
    }
    fn merge(&mut self, left: T, right: T) -> (Option<Either<T, T>>, Self::MergeResult) {
        if left <= right {
            (Some(Either::Right(right)), left)
        } else {
            (Some(Either::Left(left)), right)
        }
    }
    fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
        // Not ExactSizeIterator because size may be larger than usize
        size_hint::add(left, right)
    }
}

impl<I, J, F> Clone for MergeBy<I, J, F>
where
    I: Iterator,
    J: Iterator,
    PutBack<Fuse<I>>: Clone,
    PutBack<Fuse<J>>: Clone,
    F: Clone,
{
    clone_fields!(left, right, cmp_fn);
}

impl<I, J, F> fmt::Debug for MergeBy<I, J, F>
where
    I: Iterator + fmt::Debug,
    I::Item: fmt::Debug,
    J: Iterator + fmt::Debug,
    J::Item: fmt::Debug,
{
    debug_fmt_fields!(MergeBy, left, right);
}

impl<I, J, F> Iterator for MergeBy<I, J, F>
where
    I: Iterator,
    J: Iterator,
    F: OrderingOrBool<I::Item, J::Item>,
{
    type Item = F::MergeResult;

    fn next(&mut self) -> Option<Self::Item> {
        match (self.left.next(), self.right.next()) {
            (None, None) => None,
            (Some(left), None) => Some(F::left(left)),
            (None, Some(right)) => Some(F::right(right)),
            (Some(left), Some(right)) => {
                let (not_next, next) = self.cmp_fn.merge(left, right);
                match not_next {
                    Some(Either::Left(l)) => {
                        self.left.put_back(l);
                    }
                    Some(Either::Right(r)) => {
                        self.right.put_back(r);
                    }
                    None => (),
                }

                Some(next)
            }
        }
    }

    fn fold<B, G>(mut self, init: B, mut f: G) -> B
    where
        Self: Sized,
        G: FnMut(B, Self::Item) -> B,
    {
        let mut acc = init;
        let mut left = self.left.next();
        let mut right = self.right.next();

        loop {
            match (left, right) {
                (Some(l), Some(r)) => match self.cmp_fn.merge(l, r) {
                    (Some(Either::Right(r)), x) => {
                        acc = f(acc, x);
                        left = self.left.next();
                        right = Some(r);
                    }
                    (Some(Either::Left(l)), x) => {
                        acc = f(acc, x);
                        left = Some(l);
                        right = self.right.next();
                    }
                    (None, x) => {
                        acc = f(acc, x);
                        left = self.left.next();
                        right = self.right.next();
                    }
                },
                (Some(l), None) => {
                    self.left.put_back(l);
                    acc = self.left.fold(acc, |acc, x| f(acc, F::left(x)));
                    break;
                }
                (None, Some(r)) => {
                    self.right.put_back(r);
                    acc = self.right.fold(acc, |acc, x| f(acc, F::right(x)));
                    break;
                }
                (None, None) => {
                    break;
                }
            }
        }

        acc
    }

    fn size_hint(&self) -> SizeHint {
        F::size_hint(self.left.size_hint(), self.right.size_hint())
    }

    fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
        loop {
            if n == 0 {
                break self.next();
            }
            n -= 1;
            match (self.left.next(), self.right.next()) {
                (None, None) => break None,
                (Some(_left), None) => break self.left.nth(n).map(F::left),
                (None, Some(_right)) => break self.right.nth(n).map(F::right),
                (Some(left), Some(right)) => {
                    let (not_next, _) = self.cmp_fn.merge(left, right);
                    match not_next {
                        Some(Either::Left(l)) => {
                            self.left.put_back(l);
                        }
                        Some(Either::Right(r)) => {
                            self.right.put_back(r);
                        }
                        None => (),
                    }
                }
            }
        }
    }
}

impl<I, J, F> FusedIterator for MergeBy<I, J, F>
where
    I: Iterator,
    J: Iterator,
    F: OrderingOrBool<I::Item, J::Item>,
{
}

Coverage Report

Created: 2026-07-16 07:16

Line	Count	Source
1		use std::cmp::Ordering;
2		use std::fmt;
3		use std::iter::{Fuse, FusedIterator};
4		use std::marker::PhantomData;
5
6		use either::Either;
7
8		use super::adaptors::{put_back, PutBack};
9		use crate::either_or_both::EitherOrBoth;
10		use crate::size_hint::{self, SizeHint};
11		#[cfg(doc)]
12		use crate::Itertools;
13
14		#[derive(Clone, Debug)]
15		pub struct MergeLte;
16
17		/// An iterator adaptor that merges the two base iterators in ascending order.
18		/// If both base iterators are sorted (ascending), the result is sorted.
19		///
20		/// Iterator element type is `I::Item`.
21		///
22		/// See [`.merge()`](crate::Itertools::merge_by) for more information.
23		pub type Merge<I, J> = MergeBy<I, J, MergeLte>;
24
25		/// Create an iterator that merges elements in `i` and `j`.
26		///
27		/// [`IntoIterator`] enabled version of [`Itertools::merge`](crate::Itertools::merge).
28		///
29		/// ```
30		/// use itertools::merge;
31		///
32		/// for elt in merge(&[1, 2, 3], &[2, 3, 4]) {
33		/// /* loop body */
34		/// # let _ = elt;
35		/// }
36		/// ```
37	0	pub fn merge<I, J>(
38	0	i: I,
39	0	j: J,
40	0	) -> Merge<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter>
41	0	where
42	0	I: IntoIterator,
43	0	J: IntoIterator<Item = I::Item>,
44	0	I::Item: PartialOrd,
45		{
46	0	merge_by_new(i, j, MergeLte)
47	0	}
48
49		/// An iterator adaptor that merges the two base iterators in ascending order.
50		/// If both base iterators are sorted (ascending), the result is sorted.
51		///
52		/// Iterator element type is `I::Item`.
53		///
54		/// See [`.merge_by()`](crate::Itertools::merge_by) for more information.
55		#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
56		pub struct MergeBy<I: Iterator, J: Iterator, F> {
57		left: PutBack<Fuse<I>>,
58		right: PutBack<Fuse<J>>,
59		cmp_fn: F,
60		}
61
62		/// Create a `MergeBy` iterator.
63	0	pub fn merge_by_new<I, J, F>(a: I, b: J, cmp: F) -> MergeBy<I::IntoIter, J::IntoIter, F>
64	0	where
65	0	I: IntoIterator,
66	0	J: IntoIterator<Item = I::Item>,
67		{
68	0	MergeBy {
69	0	left: put_back(a.into_iter().fuse()),
70	0	right: put_back(b.into_iter().fuse()),
71	0	cmp_fn: cmp,
72	0	}
73	0	}
74
75		/// Return an iterator adaptor that merge-joins items from the two base iterators in ascending order.
76		///
77		/// [`IntoIterator`] enabled version of [`Itertools::merge_join_by`].
78	0	pub fn merge_join_by<I, J, F, T>(
79	0	left: I,
80	0	right: J,
81	0	cmp_fn: F,
82	0	) -> MergeJoinBy<I::IntoIter, J::IntoIter, F>
83	0	where
84	0	I: IntoIterator,
85	0	J: IntoIterator,
86	0	F: FnMut(&I::Item, &J::Item) -> T,
87		{
88	0	MergeBy {
89	0	left: put_back(left.into_iter().fuse()),
90	0	right: put_back(right.into_iter().fuse()),
91	0	cmp_fn: MergeFuncLR(cmp_fn, PhantomData),
92	0	}
93	0	}
94
95		/// An iterator adaptor that merge-joins items from the two base iterators in ascending order.
96		///
97		/// See [`.merge_join_by()`](crate::Itertools::merge_join_by) for more information.
98		pub type MergeJoinBy<I, J, F> =
99		MergeBy<I, J, MergeFuncLR<F, <F as FuncLR<<I as Iterator>::Item, <J as Iterator>::Item>>::T>>;
100
101		#[derive(Clone, Debug)]
102		pub struct MergeFuncLR<F, T>(F, PhantomData<T>);
103
104		pub trait FuncLR<L, R> {
105		type T;
106		}
107
108		impl<L, R, T, F: FnMut(&L, &R) -> T> FuncLR<L, R> for F {
109		type T = T;
110		}
111
112		pub trait OrderingOrBool<L, R> {
113		type MergeResult;
114		fn left(left: L) -> Self::MergeResult;
115		fn right(right: R) -> Self::MergeResult;
116		// "merge" never returns (Some(...), Some(...), ...) so Option<Either<I::Item, J::Item>>
117		// is appealing but it is always followed by two put_backs, so we think the compiler is
118		// smart enough to optimize it. Or we could move put_backs into "merge".
119		fn merge(&mut self, left: L, right: R) -> (Option<Either<L, R>>, Self::MergeResult);
120		fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint;
121		}
122
123		impl<L, R, F: FnMut(&L, &R) -> Ordering> OrderingOrBool<L, R> for MergeFuncLR<F, Ordering> {
124		type MergeResult = EitherOrBoth<L, R>;
125	0	fn left(left: L) -> Self::MergeResult {
126	0	EitherOrBoth::Left(left)
127	0	}
128	0	fn right(right: R) -> Self::MergeResult {
129	0	EitherOrBoth::Right(right)
130	0	}
131	0	fn merge(&mut self, left: L, right: R) -> (Option<Either<L, R>>, Self::MergeResult) {
132	0	match self.0(&left, &right) {
133	0	Ordering::Equal => (None, EitherOrBoth::Both(left, right)),
134	0	Ordering::Less => (Some(Either::Right(right)), EitherOrBoth::Left(left)),
135	0	Ordering::Greater => (Some(Either::Left(left)), EitherOrBoth::Right(right)),
136		}
137	0	}
138	0	fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
139	0	let (a_lower, a_upper) = left;
140	0	let (b_lower, b_upper) = right;
141	0	let lower = ::std::cmp::max(a_lower, b_lower);
142	0	let upper = match (a_upper, b_upper) {
143	0	(Some(x), Some(y)) => x.checked_add(y),
144	0	_ => None,
145		};
146	0	(lower, upper)
147	0	}
148		}
149
150		impl<L, R, F: FnMut(&L, &R) -> bool> OrderingOrBool<L, R> for MergeFuncLR<F, bool> {
151		type MergeResult = Either<L, R>;
152	0	fn left(left: L) -> Self::MergeResult {
153	0	Either::Left(left)
154	0	}
155	0	fn right(right: R) -> Self::MergeResult {
156	0	Either::Right(right)
157	0	}
158	0	fn merge(&mut self, left: L, right: R) -> (Option<Either<L, R>>, Self::MergeResult) {
159	0	if self.0(&left, &right) {
160	0	(Some(Either::Right(right)), Either::Left(left))
161		} else {
162	0	(Some(Either::Left(left)), Either::Right(right))
163		}
164	0	}
165	0	fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
166		// Not ExactSizeIterator because size may be larger than usize
167	0	size_hint::add(left, right)
168	0	}
169		}
170
171		impl<T, F: FnMut(&T, &T) -> bool> OrderingOrBool<T, T> for F {
172		type MergeResult = T;
173	0	fn left(left: T) -> Self::MergeResult {
174	0	left
175	0	}
176	0	fn right(right: T) -> Self::MergeResult {
177	0	right
178	0	}
179	0	fn merge(&mut self, left: T, right: T) -> (Option<Either<T, T>>, Self::MergeResult) {
180	0	if self(&left, &right) {
181	0	(Some(Either::Right(right)), left)
182		} else {
183	0	(Some(Either::Left(left)), right)
184		}
185	0	}
186	0	fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
187		// Not ExactSizeIterator because size may be larger than usize
188	0	size_hint::add(left, right)
189	0	}
190		}
191
192		impl<T: PartialOrd> OrderingOrBool<T, T> for MergeLte {
193		type MergeResult = T;
194	0	fn left(left: T) -> Self::MergeResult {
195	0	left
196	0	}
197	0	fn right(right: T) -> Self::MergeResult {
198	0	right
199	0	}
200	0	fn merge(&mut self, left: T, right: T) -> (Option<Either<T, T>>, Self::MergeResult) {
201	0	if left <= right {
202	0	(Some(Either::Right(right)), left)
203		} else {
204	0	(Some(Either::Left(left)), right)
205		}
206	0	}
207	0	fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
208		// Not ExactSizeIterator because size may be larger than usize
209	0	size_hint::add(left, right)
210	0	}
211		}
212
213		impl<I, J, F> Clone for MergeBy<I, J, F>
214		where
215		I: Iterator,
216		J: Iterator,
217		PutBack<Fuse<I>>: Clone,
218		PutBack<Fuse<J>>: Clone,
219		F: Clone,
220		{
221		clone_fields!(left, right, cmp_fn);
222		}
223
224		impl<I, J, F> fmt::Debug for MergeBy<I, J, F>
225		where
226		I: Iterator + fmt::Debug,
227		I::Item: fmt::Debug,
228		J: Iterator + fmt::Debug,
229		J::Item: fmt::Debug,
230		{
231		debug_fmt_fields!(MergeBy, left, right);
232		}
233
234		impl<I, J, F> Iterator for MergeBy<I, J, F>
235		where
236		I: Iterator,
237		J: Iterator,
238		F: OrderingOrBool<I::Item, J::Item>,
239		{
240		type Item = F::MergeResult;
241
242	0	fn next(&mut self) -> Option<Self::Item> {
243	0	match (self.left.next(), self.right.next()) {
244	0	(None, None) => None,
245	0	(Some(left), None) => Some(F::left(left)),
246	0	(None, Some(right)) => Some(F::right(right)),
247	0	(Some(left), Some(right)) => {
248	0	let (not_next, next) = self.cmp_fn.merge(left, right);
249	0	match not_next {
250	0	Some(Either::Left(l)) => {
251	0	self.left.put_back(l);
252	0	}
253	0	Some(Either::Right(r)) => {
254	0	self.right.put_back(r);
255	0	}
256	0	None => (),
257		}
258
259	0	Some(next)
260		}
261		}
262	0	}
263
264	0	fn fold<B, G>(mut self, init: B, mut f: G) -> B
265	0	where
266	0	Self: Sized,
267	0	G: FnMut(B, Self::Item) -> B,
268		{
269	0	let mut acc = init;
270	0	let mut left = self.left.next();
271	0	let mut right = self.right.next();
272
273		loop {
274	0	match (left, right) {
275	0	(Some(l), Some(r)) => match self.cmp_fn.merge(l, r) {
276	0	(Some(Either::Right(r)), x) => {
277	0	acc = f(acc, x);
278	0	left = self.left.next();
279	0	right = Some(r);
280	0	}
281	0	(Some(Either::Left(l)), x) => {
282	0	acc = f(acc, x);
283	0	left = Some(l);
284	0	right = self.right.next();
285	0	}
286	0	(None, x) => {
287	0	acc = f(acc, x);
288	0	left = self.left.next();
289	0	right = self.right.next();
290	0	}
291		},
292	0	(Some(l), None) => {
293	0	self.left.put_back(l);
294	0	acc = self.left.fold(acc, \|acc, x\| f(acc, F::left(x)));
295	0	break;
296		}
297	0	(None, Some(r)) => {
298	0	self.right.put_back(r);
299	0	acc = self.right.fold(acc, \|acc, x\| f(acc, F::right(x)));
300	0	break;
301		}
302		(None, None) => {
303	0	break;
304		}
305		}
306		}
307
308	0	acc
309	0	}
310
311	0	fn size_hint(&self) -> SizeHint {
312	0	F::size_hint(self.left.size_hint(), self.right.size_hint())
313	0	}
314
315	0	fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
316		loop {
317	0	if n == 0 {
318	0	break self.next();
319	0	}
320	0	n -= 1;
321	0	match (self.left.next(), self.right.next()) {
322	0	(None, None) => break None,
323	0	(Some(_left), None) => break self.left.nth(n).map(F::left),
324	0	(None, Some(_right)) => break self.right.nth(n).map(F::right),
325	0	(Some(left), Some(right)) => {
326	0	let (not_next, _) = self.cmp_fn.merge(left, right);
327	0	match not_next {
328	0	Some(Either::Left(l)) => {
329	0	self.left.put_back(l);
330	0	}
331	0	Some(Either::Right(r)) => {
332	0	self.right.put_back(r);
333	0	}
334	0	None => (),
335		}
336		}
337		}
338		}
339	0	}
340		}
341
342		impl<I, J, F> FusedIterator for MergeBy<I, J, F>
343		where
344		I: Iterator,
345		J: Iterator,
346		F: OrderingOrBool<I::Item, J::Item>,
347		{
348		}