/rust/registry/src/index.crates.io-6f17d22bba15001f/itertools-0.11.0/src/merge_join.rs

Source (jump to first uncovered line)
use std::cmp::Ordering;
use std::iter::Fuse;
use std::fmt;

use either::Either;

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

/// 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,
          T: OrderingOrBool<I::Item, J::Item>,
{
    MergeJoinBy {
        left: put_back(left.into_iter().fuse()),
        right: put_back(right.into_iter().fuse()),
        cmp_fn,
    }
}

/// 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.
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
pub struct MergeJoinBy<I: Iterator, J: Iterator, F> {
    left: PutBack<Fuse<I>>,
    right: PutBack<Fuse<J>>,
    cmp_fn: F,
}

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(self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult);
    fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint;
}

impl<L, R> OrderingOrBool<L, R> for 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(self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) {
        match self {
            Ordering::Equal => (None, None, EitherOrBoth::Both(left, right)),
            Ordering::Less => (None, Some(right), EitherOrBoth::Left(left)),
            Ordering::Greater => (Some(left), None, 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> OrderingOrBool<L, R> for 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(self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) {
        if self {
            (None, Some(right), Either::Left(left))
        } else {
            (Some(left), None, 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<I, J, F> Clone for MergeJoinBy<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 MergeJoinBy<I, J, F>
    where I: Iterator + fmt::Debug,
          I::Item: fmt::Debug,
          J: Iterator + fmt::Debug,
          J::Item: fmt::Debug,
{
    debug_fmt_fields!(MergeJoinBy, left, right);
}

impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F>
    where I: Iterator,
          J: Iterator,
          F: FnMut(&I::Item, &J::Item) -> T,
          T: OrderingOrBool<I::Item, J::Item>,
{
    type Item = T::MergeResult;

    fn next(&mut self) -> Option<Self::Item> {
        match (self.left.next(), self.right.next()) {
            (None, None) => None,
            (Some(left), None) => Some(T::left(left)),
            (None, Some(right)) => Some(T::right(right)),
            (Some(left), Some(right)) => {
                let (left, right, next) = (self.cmp_fn)(&left, &right).merge(left, right);
                if let Some(left) = left {
                    self.left.put_back(left);
                }
                if let Some(right) = right {
                    self.right.put_back(right);
                }
                Some(next)
            }
        }
    }

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

    fn count(mut self) -> usize {
        let mut count = 0;
        loop {
            match (self.left.next(), self.right.next()) {
                (None, None) => break count,
                (Some(_left), None) => break count + 1 + self.left.into_parts().1.count(),
                (None, Some(_right)) => break count + 1 + self.right.into_parts().1.count(),
                (Some(left), Some(right)) => {
                    count += 1;
                    let (left, right, _) = (self.cmp_fn)(&left, &right).merge(left, right);
                    if let Some(left) = left {
                        self.left.put_back(left);
                    }
                    if let Some(right) = right {
                        self.right.put_back(right);
                    }
                }
            }
        }
    }

    fn last(mut self) -> Option<Self::Item> {
        let mut previous_element = None;
        loop {
            match (self.left.next(), self.right.next()) {
                (None, None) => break previous_element,
                (Some(left), None) => {
                    break Some(T::left(
                        self.left.into_parts().1.last().unwrap_or(left),
                    ))
                }
                (None, Some(right)) => {
                    break Some(T::right(
                        self.right.into_parts().1.last().unwrap_or(right),
                    ))
                }
                (Some(left), Some(right)) => {
                    let (left, right, elem) = (self.cmp_fn)(&left, &right).merge(left, right);
                    if let Some(left) = left {
                        self.left.put_back(left);
                    }
                    if let Some(right) = right {
                        self.right.put_back(right);
                    }
                    previous_element = Some(elem);
                }
            }
        }
    }

    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(T::left),
                (None, Some(_right)) => break self.right.nth(n).map(T::right),
                (Some(left), Some(right)) => {
                    let (left, right, _) = (self.cmp_fn)(&left, &right).merge(left, right);
                    if let Some(left) = left {
                        self.left.put_back(left);
                    }
                    if let Some(right) = right {
                        self.right.put_back(right);
                    }
                }
            }
        }
    }
}

Coverage Report

Created: 2025-02-21 07:11

Line	Count	Source (jump to first uncovered line)
1		use std::cmp::Ordering;
2		use std::iter::Fuse;
3		use std::fmt;
4
5		use either::Either;
6
7		use super::adaptors::{PutBack, put_back};
8		use crate::either_or_both::EitherOrBoth;
9		use crate::size_hint::{self, SizeHint};
10		#[cfg(doc)]
11		use crate::Itertools;
12
13		/// Return an iterator adaptor that merge-joins items from the two base iterators in ascending order.
14		///
15		/// [`IntoIterator`] enabled version of [`Itertools::merge_join_by`].
16	0	pub fn merge_join_by<I, J, F, T>(left: I, right: J, cmp_fn: F)
17	0	-> MergeJoinBy<I::IntoIter, J::IntoIter, F>
18	0	where I: IntoIterator,
19	0	J: IntoIterator,
20	0	F: FnMut(&I::Item, &J::Item) -> T,
21	0	T: OrderingOrBool<I::Item, J::Item>,
22	0	{
23	0	MergeJoinBy {
24	0	left: put_back(left.into_iter().fuse()),
25	0	right: put_back(right.into_iter().fuse()),
26	0	cmp_fn,
27	0	}
28	0	}
29
30		/// An iterator adaptor that merge-joins items from the two base iterators in ascending order.
31		///
32		/// See [`.merge_join_by()`](crate::Itertools::merge_join_by) for more information.
33		#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
34		pub struct MergeJoinBy<I: Iterator, J: Iterator, F> {
35		left: PutBack<Fuse<I>>,
36		right: PutBack<Fuse<J>>,
37		cmp_fn: F,
38		}
39
40		pub trait OrderingOrBool<L, R> {
41		type MergeResult;
42		fn left(left: L) -> Self::MergeResult;
43		fn right(right: R) -> Self::MergeResult;
44		// "merge" never returns (Some(...), Some(...), ...) so Option<Either<I::Item, J::Item>>
45		// is appealing but it is always followed by two put_backs, so we think the compiler is
46		// smart enough to optimize it. Or we could move put_backs into "merge".
47		fn merge(self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult);
48		fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint;
49		}
50
51		impl<L, R> OrderingOrBool<L, R> for Ordering {
52		type MergeResult = EitherOrBoth<L, R>;
53	0	fn left(left: L) -> Self::MergeResult {
54	0	EitherOrBoth::Left(left)
55	0	}
56	0	fn right(right: R) -> Self::MergeResult {
57	0	EitherOrBoth::Right(right)
58	0	}
59	0	fn merge(self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) {
60	0	match self {
61	0	Ordering::Equal => (None, None, EitherOrBoth::Both(left, right)),
62	0	Ordering::Less => (None, Some(right), EitherOrBoth::Left(left)),
63	0	Ordering::Greater => (Some(left), None, EitherOrBoth::Right(right)),
64		}
65	0	}
66	0	fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
67	0	let (a_lower, a_upper) = left;
68	0	let (b_lower, b_upper) = right;
69	0	let lower = ::std::cmp::max(a_lower, b_lower);
70	0	let upper = match (a_upper, b_upper) {
71	0	(Some(x), Some(y)) => x.checked_add(y),
72	0	_ => None,
73		};
74	0	(lower, upper)
75	0	}
76		}
77
78		impl<L, R> OrderingOrBool<L, R> for bool {
79		type MergeResult = Either<L, R>;
80	0	fn left(left: L) -> Self::MergeResult {
81	0	Either::Left(left)
82	0	}
83	0	fn right(right: R) -> Self::MergeResult {
84	0	Either::Right(right)
85	0	}
86	0	fn merge(self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) {
87	0	if self {
88	0	(None, Some(right), Either::Left(left))
89		} else {
90	0	(Some(left), None, Either::Right(right))
91		}
92	0	}
93	0	fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
94	0	// Not ExactSizeIterator because size may be larger than usize
95	0	size_hint::add(left, right)
96	0	}
97		}
98
99		impl<I, J, F> Clone for MergeJoinBy<I, J, F>
100		where I: Iterator,
101		J: Iterator,
102		PutBack<Fuse<I>>: Clone,
103		PutBack<Fuse<J>>: Clone,
104		F: Clone,
105		{
106		clone_fields!(left, right, cmp_fn);
107		}
108
109		impl<I, J, F> fmt::Debug for MergeJoinBy<I, J, F>
110		where I: Iterator + fmt::Debug,
111		I::Item: fmt::Debug,
112		J: Iterator + fmt::Debug,
113		J::Item: fmt::Debug,
114		{
115		debug_fmt_fields!(MergeJoinBy, left, right);
116		}
117
118		impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F>
119		where I: Iterator,
120		J: Iterator,
121		F: FnMut(&I::Item, &J::Item) -> T,
122		T: OrderingOrBool<I::Item, J::Item>,
123		{
124		type Item = T::MergeResult;
125
126	0	fn next(&mut self) -> Option<Self::Item> {
127	0	match (self.left.next(), self.right.next()) {
128	0	(None, None) => None,
129	0	(Some(left), None) => Some(T::left(left)),
130	0	(None, Some(right)) => Some(T::right(right)),
131	0	(Some(left), Some(right)) => {
132	0	let (left, right, next) = (self.cmp_fn)(&left, &right).merge(left, right);
133	0	if let Some(left) = left {
134	0	self.left.put_back(left);
135	0	}
136	0	if let Some(right) = right {
137	0	self.right.put_back(right);
138	0	}
139	0	Some(next)
140		}
141		}
142	0	}
143
144	0	fn size_hint(&self) -> SizeHint {
145	0	T::size_hint(self.left.size_hint(), self.right.size_hint())
146	0	}
147
148	0	fn count(mut self) -> usize {
149	0	let mut count = 0;
150		loop {
151	0	match (self.left.next(), self.right.next()) {
152	0	(None, None) => break count,
153	0	(Some(_left), None) => break count + 1 + self.left.into_parts().1.count(),
154	0	(None, Some(_right)) => break count + 1 + self.right.into_parts().1.count(),
155	0	(Some(left), Some(right)) => {
156	0	count += 1;
157	0	let (left, right, _) = (self.cmp_fn)(&left, &right).merge(left, right);
158	0	if let Some(left) = left {
159	0	self.left.put_back(left);
160	0	}
161	0	if let Some(right) = right {
162	0	self.right.put_back(right);
163	0	}
164		}
165		}
166		}
167	0	}
168
169	0	fn last(mut self) -> Option<Self::Item> {
170	0	let mut previous_element = None;
171		loop {
172	0	match (self.left.next(), self.right.next()) {
173	0	(None, None) => break previous_element,
174	0	(Some(left), None) => {
175	0	break Some(T::left(
176	0	self.left.into_parts().1.last().unwrap_or(left),
177	0	))
178		}
179	0	(None, Some(right)) => {
180	0	break Some(T::right(
181	0	self.right.into_parts().1.last().unwrap_or(right),
182	0	))
183		}
184	0	(Some(left), Some(right)) => {
185	0	let (left, right, elem) = (self.cmp_fn)(&left, &right).merge(left, right);
186	0	if let Some(left) = left {
187	0	self.left.put_back(left);
188	0	}
189	0	if let Some(right) = right {
190	0	self.right.put_back(right);
191	0	}
192	0	previous_element = Some(elem);
193		}
194		}
195		}
196	0	}
197
198	0	fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
199		loop {
200	0	if n == 0 {
201	0	break self.next();
202	0	}
203	0	n -= 1;
204	0	match (self.left.next(), self.right.next()) {
205	0	(None, None) => break None,
206	0	(Some(_left), None) => break self.left.nth(n).map(T::left),
207	0	(None, Some(_right)) => break self.right.nth(n).map(T::right),
208	0	(Some(left), Some(right)) => {
209	0	let (left, right, _) = (self.cmp_fn)(&left, &right).merge(left, right);
210	0	if let Some(left) = left {
211	0	self.left.put_back(left);
212	0	}
213	0	if let Some(right) = right {
214	0	self.right.put_back(right);
215	0	}
216		}
217		}
218		}
219	0	}
220		}