diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:02:58 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:02:58 +0000 |
commit | 698f8c2f01ea549d77d7dc3338a12e04c11057b9 (patch) | |
tree | 173a775858bd501c378080a10dca74132f05bc50 /library/alloc/src/collections/btree/merge_iter.rs | |
parent | Initial commit. (diff) | |
download | rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.tar.xz rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.zip |
Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | library/alloc/src/collections/btree/merge_iter.rs | 98 |
1 files changed, 98 insertions, 0 deletions
diff --git a/library/alloc/src/collections/btree/merge_iter.rs b/library/alloc/src/collections/btree/merge_iter.rs new file mode 100644 index 000000000..7f23d93b9 --- /dev/null +++ b/library/alloc/src/collections/btree/merge_iter.rs @@ -0,0 +1,98 @@ +use core::cmp::Ordering; +use core::fmt::{self, Debug}; +use core::iter::FusedIterator; + +/// Core of an iterator that merges the output of two strictly ascending iterators, +/// for instance a union or a symmetric difference. +pub struct MergeIterInner<I: Iterator> { + a: I, + b: I, + peeked: Option<Peeked<I>>, +} + +/// Benchmarks faster than wrapping both iterators in a Peekable, +/// probably because we can afford to impose a FusedIterator bound. +#[derive(Clone, Debug)] +enum Peeked<I: Iterator> { + A(I::Item), + B(I::Item), +} + +impl<I: Iterator> Clone for MergeIterInner<I> +where + I: Clone, + I::Item: Clone, +{ + fn clone(&self) -> Self { + Self { a: self.a.clone(), b: self.b.clone(), peeked: self.peeked.clone() } + } +} + +impl<I: Iterator> Debug for MergeIterInner<I> +where + I: Debug, + I::Item: Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("MergeIterInner").field(&self.a).field(&self.b).field(&self.peeked).finish() + } +} + +impl<I: Iterator> MergeIterInner<I> { + /// Creates a new core for an iterator merging a pair of sources. + pub fn new(a: I, b: I) -> Self { + MergeIterInner { a, b, peeked: None } + } + + /// Returns the next pair of items stemming from the pair of sources + /// being merged. If both returned options contain a value, that value + /// is equal and occurs in both sources. If one of the returned options + /// contains a value, that value doesn't occur in the other source (or + /// the sources are not strictly ascending). If neither returned option + /// contains a value, iteration has finished and subsequent calls will + /// return the same empty pair. + pub fn nexts<Cmp: Fn(&I::Item, &I::Item) -> Ordering>( + &mut self, + cmp: Cmp, + ) -> (Option<I::Item>, Option<I::Item>) + where + I: FusedIterator, + { + let mut a_next; + let mut b_next; + match self.peeked.take() { + Some(Peeked::A(next)) => { + a_next = Some(next); + b_next = self.b.next(); + } + Some(Peeked::B(next)) => { + b_next = Some(next); + a_next = self.a.next(); + } + None => { + a_next = self.a.next(); + b_next = self.b.next(); + } + } + if let (Some(ref a1), Some(ref b1)) = (&a_next, &b_next) { + match cmp(a1, b1) { + Ordering::Less => self.peeked = b_next.take().map(Peeked::B), + Ordering::Greater => self.peeked = a_next.take().map(Peeked::A), + Ordering::Equal => (), + } + } + (a_next, b_next) + } + + /// Returns a pair of upper bounds for the `size_hint` of the final iterator. + pub fn lens(&self) -> (usize, usize) + where + I: ExactSizeIterator, + { + match self.peeked { + Some(Peeked::A(_)) => (1 + self.a.len(), self.b.len()), + Some(Peeked::B(_)) => (self.a.len(), 1 + self.b.len()), + _ => (self.a.len(), self.b.len()), + } + } +} |