alloc/collections/btree/
merge_iter.rs
1use core::cmp::Ordering;
2use core::fmt::{self, Debug};
3use core::iter::FusedIterator;
4
5pub(super) struct MergeIterInner<I: Iterator> {
8 a: I,
9 b: I,
10 peeked: Option<Peeked<I>>,
11}
12
13#[derive(Clone, Debug)]
16enum Peeked<I: Iterator> {
17 A(I::Item),
18 B(I::Item),
19}
20
21impl<I: Iterator> Clone for MergeIterInner<I>
22where
23 I: Clone,
24 I::Item: Clone,
25{
26 fn clone(&self) -> Self {
27 Self { a: self.a.clone(), b: self.b.clone(), peeked: self.peeked.clone() }
28 }
29}
30
31impl<I: Iterator> Debug for MergeIterInner<I>
32where
33 I: Debug,
34 I::Item: Debug,
35{
36 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
37 f.debug_tuple("MergeIterInner").field(&self.a).field(&self.b).field(&self.peeked).finish()
38 }
39}
40
41impl<I: Iterator> MergeIterInner<I> {
42 pub(super) fn new(a: I, b: I) -> Self {
44 MergeIterInner { a, b, peeked: None }
45 }
46
47 pub(super) fn nexts<Cmp: Fn(&I::Item, &I::Item) -> Ordering>(
55 &mut self,
56 cmp: Cmp,
57 ) -> (Option<I::Item>, Option<I::Item>)
58 where
59 I: FusedIterator,
60 {
61 let mut a_next;
62 let mut b_next;
63 match self.peeked.take() {
64 Some(Peeked::A(next)) => {
65 a_next = Some(next);
66 b_next = self.b.next();
67 }
68 Some(Peeked::B(next)) => {
69 b_next = Some(next);
70 a_next = self.a.next();
71 }
72 None => {
73 a_next = self.a.next();
74 b_next = self.b.next();
75 }
76 }
77 if let (Some(a1), Some(b1)) = (&a_next, &b_next) {
78 match cmp(a1, b1) {
79 Ordering::Less => self.peeked = b_next.take().map(Peeked::B),
80 Ordering::Greater => self.peeked = a_next.take().map(Peeked::A),
81 Ordering::Equal => (),
82 }
83 }
84 (a_next, b_next)
85 }
86
87 pub(super) fn lens(&self) -> (usize, usize)
89 where
90 I: ExactSizeIterator,
91 {
92 match self.peeked {
93 Some(Peeked::A(_)) => (1 + self.a.len(), self.b.len()),
94 Some(Peeked::B(_)) => (self.a.len(), 1 + self.b.len()),
95 _ => (self.a.len(), self.b.len()),
96 }
97 }
98}