/rust/registry/src/index.crates.io-6f17d22bba15001f/itertools-0.10.5/src/merge_join.rs
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 super::adaptors::{PutBack, put_back}; |
6 | | use crate::either_or_both::EitherOrBoth; |
7 | | #[cfg(doc)] |
8 | | use crate::Itertools; |
9 | | |
10 | | /// Return an iterator adaptor that merge-joins items from the two base iterators in ascending order. |
11 | | /// |
12 | | /// [`IntoIterator`] enabled version of [`Itertools::merge_join_by`]. |
13 | 0 | pub fn merge_join_by<I, J, F>(left: I, right: J, cmp_fn: F) |
14 | 0 | -> MergeJoinBy<I::IntoIter, J::IntoIter, F> |
15 | 0 | where I: IntoIterator, |
16 | 0 | J: IntoIterator, |
17 | 0 | F: FnMut(&I::Item, &J::Item) -> Ordering |
18 | 0 | { |
19 | 0 | MergeJoinBy { |
20 | 0 | left: put_back(left.into_iter().fuse()), |
21 | 0 | right: put_back(right.into_iter().fuse()), |
22 | 0 | cmp_fn, |
23 | 0 | } |
24 | 0 | } |
25 | | |
26 | | /// An iterator adaptor that merge-joins items from the two base iterators in ascending order. |
27 | | /// |
28 | | /// See [`.merge_join_by()`](crate::Itertools::merge_join_by) for more information. |
29 | | #[must_use = "iterator adaptors are lazy and do nothing unless consumed"] |
30 | | pub struct MergeJoinBy<I: Iterator, J: Iterator, F> { |
31 | | left: PutBack<Fuse<I>>, |
32 | | right: PutBack<Fuse<J>>, |
33 | | cmp_fn: F |
34 | | } |
35 | | |
36 | | impl<I, J, F> Clone for MergeJoinBy<I, J, F> |
37 | | where I: Iterator, |
38 | | J: Iterator, |
39 | | PutBack<Fuse<I>>: Clone, |
40 | | PutBack<Fuse<J>>: Clone, |
41 | | F: Clone, |
42 | | { |
43 | | clone_fields!(left, right, cmp_fn); |
44 | | } |
45 | | |
46 | | impl<I, J, F> fmt::Debug for MergeJoinBy<I, J, F> |
47 | | where I: Iterator + fmt::Debug, |
48 | | I::Item: fmt::Debug, |
49 | | J: Iterator + fmt::Debug, |
50 | | J::Item: fmt::Debug, |
51 | | { |
52 | | debug_fmt_fields!(MergeJoinBy, left, right); |
53 | | } |
54 | | |
55 | | impl<I, J, F> Iterator for MergeJoinBy<I, J, F> |
56 | | where I: Iterator, |
57 | | J: Iterator, |
58 | | F: FnMut(&I::Item, &J::Item) -> Ordering |
59 | | { |
60 | | type Item = EitherOrBoth<I::Item, J::Item>; |
61 | | |
62 | 0 | fn next(&mut self) -> Option<Self::Item> { |
63 | 0 | match (self.left.next(), self.right.next()) { |
64 | 0 | (None, None) => None, |
65 | 0 | (Some(left), None) => |
66 | 0 | Some(EitherOrBoth::Left(left)), |
67 | 0 | (None, Some(right)) => |
68 | 0 | Some(EitherOrBoth::Right(right)), |
69 | 0 | (Some(left), Some(right)) => { |
70 | 0 | match (self.cmp_fn)(&left, &right) { |
71 | | Ordering::Equal => |
72 | 0 | Some(EitherOrBoth::Both(left, right)), |
73 | | Ordering::Less => { |
74 | 0 | self.right.put_back(right); |
75 | 0 | Some(EitherOrBoth::Left(left)) |
76 | | }, |
77 | | Ordering::Greater => { |
78 | 0 | self.left.put_back(left); |
79 | 0 | Some(EitherOrBoth::Right(right)) |
80 | | } |
81 | | } |
82 | | } |
83 | | } |
84 | 0 | } |
85 | | |
86 | 0 | fn size_hint(&self) -> (usize, Option<usize>) { |
87 | 0 | let (a_lower, a_upper) = self.left.size_hint(); |
88 | 0 | let (b_lower, b_upper) = self.right.size_hint(); |
89 | 0 |
|
90 | 0 | let lower = ::std::cmp::max(a_lower, b_lower); |
91 | | |
92 | 0 | let upper = match (a_upper, b_upper) { |
93 | 0 | (Some(x), Some(y)) => x.checked_add(y), |
94 | 0 | _ => None, |
95 | | }; |
96 | | |
97 | 0 | (lower, upper) |
98 | 0 | } |
99 | | |
100 | 0 | fn count(mut self) -> usize { |
101 | 0 | let mut count = 0; |
102 | | loop { |
103 | 0 | match (self.left.next(), self.right.next()) { |
104 | 0 | (None, None) => break count, |
105 | 0 | (Some(_left), None) => break count + 1 + self.left.into_parts().1.count(), |
106 | 0 | (None, Some(_right)) => break count + 1 + self.right.into_parts().1.count(), |
107 | 0 | (Some(left), Some(right)) => { |
108 | 0 | count += 1; |
109 | 0 | match (self.cmp_fn)(&left, &right) { |
110 | 0 | Ordering::Equal => {} |
111 | 0 | Ordering::Less => self.right.put_back(right), |
112 | 0 | Ordering::Greater => self.left.put_back(left), |
113 | | } |
114 | | } |
115 | | } |
116 | | } |
117 | 0 | } |
118 | | |
119 | 0 | fn last(mut self) -> Option<Self::Item> { |
120 | 0 | let mut previous_element = None; |
121 | | loop { |
122 | 0 | match (self.left.next(), self.right.next()) { |
123 | 0 | (None, None) => break previous_element, |
124 | 0 | (Some(left), None) => { |
125 | 0 | break Some(EitherOrBoth::Left( |
126 | 0 | self.left.into_parts().1.last().unwrap_or(left), |
127 | 0 | )) |
128 | | } |
129 | 0 | (None, Some(right)) => { |
130 | 0 | break Some(EitherOrBoth::Right( |
131 | 0 | self.right.into_parts().1.last().unwrap_or(right), |
132 | 0 | )) |
133 | | } |
134 | 0 | (Some(left), Some(right)) => { |
135 | 0 | previous_element = match (self.cmp_fn)(&left, &right) { |
136 | 0 | Ordering::Equal => Some(EitherOrBoth::Both(left, right)), |
137 | | Ordering::Less => { |
138 | 0 | self.right.put_back(right); |
139 | 0 | Some(EitherOrBoth::Left(left)) |
140 | | } |
141 | | Ordering::Greater => { |
142 | 0 | self.left.put_back(left); |
143 | 0 | Some(EitherOrBoth::Right(right)) |
144 | | } |
145 | | } |
146 | | } |
147 | | } |
148 | | } |
149 | 0 | } |
150 | | |
151 | 0 | fn nth(&mut self, mut n: usize) -> Option<Self::Item> { |
152 | 0 | loop { |
153 | 0 | if n == 0 { |
154 | 0 | break self.next(); |
155 | 0 | } |
156 | 0 | n -= 1; |
157 | 0 | match (self.left.next(), self.right.next()) { |
158 | 0 | (None, None) => break None, |
159 | 0 | (Some(_left), None) => break self.left.nth(n).map(EitherOrBoth::Left), |
160 | 0 | (None, Some(_right)) => break self.right.nth(n).map(EitherOrBoth::Right), |
161 | 0 | (Some(left), Some(right)) => match (self.cmp_fn)(&left, &right) { |
162 | 0 | Ordering::Equal => {} |
163 | 0 | Ordering::Less => self.right.put_back(right), |
164 | 0 | Ordering::Greater => self.left.put_back(left), |
165 | | }, |
166 | | } |
167 | | } |
168 | 0 | } |
169 | | } |