diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-06-19 09:26:03 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-06-19 09:26:03 +0000 |
commit | 9918693037dce8aa4bb6f08741b6812923486c18 (patch) | |
tree | 21d2b40bec7e6a7ea664acee056eb3d08e15a1cf /vendor/itertools/src/merge_join.rs | |
parent | Releasing progress-linux version 1.75.0+dfsg1-5~progress7.99u1. (diff) | |
download | rustc-9918693037dce8aa4bb6f08741b6812923486c18.tar.xz rustc-9918693037dce8aa4bb6f08741b6812923486c18.zip |
Merging upstream version 1.76.0+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/itertools/src/merge_join.rs')
-rw-r--r-- | vendor/itertools/src/merge_join.rs | 229 |
1 files changed, 174 insertions, 55 deletions
diff --git a/vendor/itertools/src/merge_join.rs b/vendor/itertools/src/merge_join.rs index 84f7d0333..c83159186 100644 --- a/vendor/itertools/src/merge_join.rs +++ b/vendor/itertools/src/merge_join.rs @@ -1,40 +1,111 @@ use std::cmp::Ordering; -use std::iter::Fuse; use std::fmt; +use std::iter::{Fuse, FusedIterator}; +use std::marker::PhantomData; use either::Either; -use super::adaptors::{PutBack, put_back}; +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 */ +/// } +/// ``` +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, - T: OrderingOrBool<I::Item, J::Item>, +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, { - MergeJoinBy { + MergeBy { left: put_back(left.into_iter().fuse()), right: put_back(right.into_iter().fuse()), - cmp_fn, + 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. -#[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 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> { @@ -44,11 +115,11 @@ pub trait OrderingOrBool<L, R> { // "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 merge(&mut 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 { +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) @@ -56,8 +127,8 @@ impl<L, R> OrderingOrBool<L, R> for Ordering { fn right(right: R) -> Self::MergeResult { EitherOrBoth::Right(right) } - fn merge(self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) { - match self { + fn merge(&mut self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) { + match self.0(&left, &right) { Ordering::Equal => (None, None, EitherOrBoth::Both(left, right)), Ordering::Less => (None, Some(right), EitherOrBoth::Left(left)), Ordering::Greater => (Some(left), None, EitherOrBoth::Right(right)), @@ -75,7 +146,7 @@ impl<L, R> OrderingOrBool<L, R> for Ordering { } } -impl<L, R> OrderingOrBool<L, R> for bool { +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) @@ -83,8 +154,8 @@ impl<L, R> OrderingOrBool<L, R> for bool { fn right(right: R) -> Self::MergeResult { Either::Right(right) } - fn merge(self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) { - if self { + fn merge(&mut self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) { + if self.0(&left, &right) { (None, Some(right), Either::Left(left)) } else { (Some(left), None, Either::Right(right)) @@ -96,40 +167,84 @@ impl<L, R> OrderingOrBool<L, R> for bool { } } -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, +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<T>, Option<T>, Self::MergeResult) { + if self(&left, &right) { + (None, Some(right), left) + } else { + (Some(left), None, 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<T>, Option<T>, Self::MergeResult) { + if left <= right { + (None, Some(right), left) + } else { + (Some(left), None, 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 MergeJoinBy<I, J, F> - where I: Iterator + fmt::Debug, - I::Item: fmt::Debug, - J: Iterator + fmt::Debug, - J::Item: fmt::Debug, +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!(MergeJoinBy, left, right); + debug_fmt_fields!(MergeBy, 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>, +impl<I, J, F> Iterator for MergeBy<I, J, F> +where + I: Iterator, + J: Iterator, + F: OrderingOrBool<I::Item, J::Item>, { - type Item = T::MergeResult; + 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(T::left(left)), - (None, Some(right)) => Some(T::right(right)), + (Some(left), None) => Some(F::left(left)), + (None, Some(right)) => Some(F::right(right)), (Some(left), Some(right)) => { - let (left, right, next) = (self.cmp_fn)(&left, &right).merge(left, right); + let (left, right, next) = self.cmp_fn.merge(left, right); if let Some(left) = left { self.left.put_back(left); } @@ -142,7 +257,7 @@ impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F> } fn size_hint(&self) -> SizeHint { - T::size_hint(self.left.size_hint(), self.right.size_hint()) + F::size_hint(self.left.size_hint(), self.right.size_hint()) } fn count(mut self) -> usize { @@ -154,7 +269,7 @@ impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F> (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); + let (left, right, _) = self.cmp_fn.merge(left, right); if let Some(left) = left { self.left.put_back(left); } @@ -172,17 +287,13 @@ impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F> 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), - )) + break Some(F::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), - )) + break Some(F::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); + let (left, right, elem) = self.cmp_fn.merge(left, right); if let Some(left) = left { self.left.put_back(left); } @@ -203,10 +314,10 @@ impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F> 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), 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 (left, right, _) = (self.cmp_fn)(&left, &right).merge(left, right); + let (left, right, _) = self.cmp_fn.merge(left, right); if let Some(left) = left { self.left.put_back(left); } @@ -218,3 +329,11 @@ impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F> } } } + +impl<I, J, F> FusedIterator for MergeBy<I, J, F> +where + I: Iterator, + J: Iterator, + F: OrderingOrBool<I::Item, J::Item>, +{ +} |