Debian Codegraph @

.cargo/vendor/itertools/src/merge_join.rs

raw
1 use std::cmp::Ordering;
2 use std::fmt;
3 use std::iter::{Fuse, FusedIterator};
4 use std::marker::PhantomData;
5
6 use either::Either;
7
8 use super::adaptors::{put_back, PutBack};
9 use crate::either_or_both::EitherOrBoth;
10 use crate::size_hint::{self, SizeHint};
11 #[cfg(doc)]
12 use crate::Itertools;
13
14 #[derive(Clone, Debug)]
15 pub struct MergeLte;
16
17 /// An iterator adaptor that merges the two base iterators in ascending order.
18 /// If both base iterators are sorted (ascending), the result is sorted.
19 ///
20 /// Iterator element type is `I::Item`.
21 ///
22 /// See [`.merge()`](crate::Itertools::merge_by) for more information.
23 pub type Merge<I, J> = MergeBy<I, J, MergeLte>;
24
25 /// Create an iterator that merges elements in `i` and `j`.
26 ///
27 /// [`IntoIterator`] enabled version of [`Itertools::merge`](crate::Itertools::merge).
28 ///
29 /// ```
30 /// use itertools::merge;
31 ///
32 /// for elt in merge(&[1, 2, 3], &[2, 3, 4]) {
33 /// /* loop body */
34 /// # let _ = elt;
35 /// }
36 /// ```
37 pub fn merge<I, J>(
38 i: I,
39 j: J,
40 ) -> Merge<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter>
41 where
42 I: IntoIterator,
43 J: IntoIterator<Item = I::Item>,
44 I::Item: PartialOrd,
45 {
46 merge_by_new(i, j, MergeLte)
47 }
48
49 /// An iterator adaptor that merges the two base iterators in ascending order.
50 /// If both base iterators are sorted (ascending), the result is sorted.
51 ///
52 /// Iterator element type is `I::Item`.
53 ///
54 /// See [`.merge_by()`](crate::Itertools::merge_by) for more information.
55 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
56 pub struct MergeBy<I: Iterator, J: Iterator, F> {
57 left: PutBack<Fuse<I>>,
58 right: PutBack<Fuse<J>>,
59 cmp_fn: F,
60 }
61
62 /// Create a `MergeBy` iterator.
63 pub fn merge_by_new<I, J, F>(a: I, b: J, cmp: F) -> MergeBy<I::IntoIter, J::IntoIter, F>
64 where
65 I: IntoIterator,
66 J: IntoIterator<Item = I::Item>,
67 {
68 MergeBy {
69 left: put_back(a.into_iter().fuse()),
70 right: put_back(b.into_iter().fuse()),
71 cmp_fn: cmp,
72 }
73 }
74
75 /// Return an iterator adaptor that merge-joins items from the two base iterators in ascending order.
76 ///
77 /// [`IntoIterator`] enabled version of [`Itertools::merge_join_by`].
78 pub fn merge_join_by<I, J, F, T>(
79 left: I,
80 right: J,
81 cmp_fn: F,
82 ) -> MergeJoinBy<I::IntoIter, J::IntoIter, F>
83 where
84 I: IntoIterator,
85 J: IntoIterator,
86 F: FnMut(&I::Item, &J::Item) -> T,
87 {
88 MergeBy {
89 left: put_back(left.into_iter().fuse()),
90 right: put_back(right.into_iter().fuse()),
91 cmp_fn: MergeFuncLR(cmp_fn, PhantomData),
92 }
93 }
94
95 /// An iterator adaptor that merge-joins items from the two base iterators in ascending order.
96 ///
97 /// See [`.merge_join_by()`](crate::Itertools::merge_join_by) for more information.
98 pub type MergeJoinBy<I, J, F> =
99 MergeBy<I, J, MergeFuncLR<F, <F as FuncLR<<I as Iterator>::Item, <J as Iterator>::Item>>::T>>;
100
101 #[derive(Clone, Debug)]
102 pub struct MergeFuncLR<F, T>(F, PhantomData<T>);
103
104 pub trait FuncLR<L, R> {
105 type T;
106 }
107
108 impl<L, R, T, F: FnMut(&L, &R) -> T> FuncLR<L, R> for F {
109 type T = T;
110 }
111
112 pub trait OrderingOrBool<L, R> {
113 type MergeResult;
114 fn left(left: L) -> Self::MergeResult;
115 fn right(right: R) -> Self::MergeResult;
116 // "merge" never returns (Some(...), Some(...), ...) so Option<Either<I::Item, J::Item>>
117 // is appealing but it is always followed by two put_backs, so we think the compiler is
118 // smart enough to optimize it. Or we could move put_backs into "merge".
119 fn merge(&mut self, left: L, right: R) -> (Option<Either<L, R>>, Self::MergeResult);
120 fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint;
121 }
122
123 impl<L, R, F: FnMut(&L, &R) -> Ordering> OrderingOrBool<L, R> for MergeFuncLR<F, Ordering> {
124 type MergeResult = EitherOrBoth<L, R>;
125 fn left(left: L) -> Self::MergeResult {
126 EitherOrBoth::Left(left)
127 }
128 fn right(right: R) -> Self::MergeResult {
129 EitherOrBoth::Right(right)
130 }
131 fn merge(&mut self, left: L, right: R) -> (Option<Either<L, R>>, Self::MergeResult) {
132 match self.0(&left, &right) {
133 Ordering::Equal => (None, EitherOrBoth::Both(left, right)),
134 Ordering::Less => (Some(Either::Right(right)), EitherOrBoth::Left(left)),
135 Ordering::Greater => (Some(Either::Left(left)), EitherOrBoth::Right(right)),
136 }
137 }
138 fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
139 let (a_lower, a_upper) = left;
140 let (b_lower, b_upper) = right;
141 let lower = ::std::cmp::max(a_lower, b_lower);
142 let upper = match (a_upper, b_upper) {
143 (Some(x), Some(y)) => x.checked_add(y),
144 _ => None,
145 };
146 (lower, upper)
147 }
148 }
149
150 impl<L, R, F: FnMut(&L, &R) -> bool> OrderingOrBool<L, R> for MergeFuncLR<F, bool> {
151 type MergeResult = Either<L, R>;
152 fn left(left: L) -> Self::MergeResult {
153 Either::Left(left)
154 }
155 fn right(right: R) -> Self::MergeResult {
156 Either::Right(right)
157 }
158 fn merge(&mut self, left: L, right: R) -> (Option<Either<L, R>>, Self::MergeResult) {
159 if self.0(&left, &right) {
160 (Some(Either::Right(right)), Either::Left(left))
161 } else {
162 (Some(Either::Left(left)), Either::Right(right))
163 }
164 }
165 fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
166 // Not ExactSizeIterator because size may be larger than usize
167 size_hint::add(left, right)
168 }
169 }
170
171 impl<T, F: FnMut(&T, &T) -> bool> OrderingOrBool<T, T> for F {
172 type MergeResult = T;
173 fn left(left: T) -> Self::MergeResult {
174 left
175 }
176 fn right(right: T) -> Self::MergeResult {
177 right
178 }
179 fn merge(&mut self, left: T, right: T) -> (Option<Either<T, T>>, Self::MergeResult) {
180 if self(&left, &right) {
181 (Some(Either::Right(right)), left)
182 } else {
183 (Some(Either::Left(left)), right)
184 }
185 }
186 fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
187 // Not ExactSizeIterator because size may be larger than usize
188 size_hint::add(left, right)
189 }
190 }
191
192 impl<T: PartialOrd> OrderingOrBool<T, T> for MergeLte {
193 type MergeResult = T;
194 fn left(left: T) -> Self::MergeResult {
195 left
196 }
197 fn right(right: T) -> Self::MergeResult {
198 right
199 }
200 fn merge(&mut self, left: T, right: T) -> (Option<Either<T, T>>, Self::MergeResult) {
201 if left <= right {
202 (Some(Either::Right(right)), left)
203 } else {
204 (Some(Either::Left(left)), right)
205 }
206 }
207 fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
208 // Not ExactSizeIterator because size may be larger than usize
209 size_hint::add(left, right)
210 }
211 }
212
213 impl<I, J, F> Clone for MergeBy<I, J, F>
214 where
215 I: Iterator,
216 J: Iterator,
217 PutBack<Fuse<I>>: Clone,
218 PutBack<Fuse<J>>: Clone,
219 F: Clone,
220 {
221 clone_fields!(left, right, cmp_fn);
222 }
223
224 impl<I, J, F> fmt::Debug for MergeBy<I, J, F>
225 where
226 I: Iterator + fmt::Debug,
227 I::Item: fmt::Debug,
228 J: Iterator + fmt::Debug,
229 J::Item: fmt::Debug,
230 {
231 debug_fmt_fields!(MergeBy, left, right);
232 }
233
234 impl<I, J, F> Iterator for MergeBy<I, J, F>
235 where
236 I: Iterator,
237 J: Iterator,
238 F: OrderingOrBool<I::Item, J::Item>,
239 {
240 type Item = F::MergeResult;
241
242 fn next(&mut self) -> Option<Self::Item> {
243 match (self.left.next(), self.right.next()) {
244 (None, None) => None,
245 (Some(left), None) => Some(F::left(left)),
246 (None, Some(right)) => Some(F::right(right)),
247 (Some(left), Some(right)) => {
248 let (not_next, next) = self.cmp_fn.merge(left, right);
249 match not_next {
250 Some(Either::Left(l)) => {
251 self.left.put_back(l);
252 }
253 Some(Either::Right(r)) => {
254 self.right.put_back(r);
255 }
256 None => (),
257 }
258
259 Some(next)
260 }
261 }
262 }
263
264 fn fold<B, G>(mut self, init: B, mut f: G) -> B
265 where
266 Self: Sized,
267 G: FnMut(B, Self::Item) -> B,
268 {
269 let mut acc = init;
270 let mut left = self.left.next();
271 let mut right = self.right.next();
272
273 loop {
274 match (left, right) {
275 (Some(l), Some(r)) => match self.cmp_fn.merge(l, r) {
276 (Some(Either::Right(r)), x) => {
277 acc = f(acc, x);
278 left = self.left.next();
279 right = Some(r);
280 }
281 (Some(Either::Left(l)), x) => {
282 acc = f(acc, x);
283 left = Some(l);
284 right = self.right.next();
285 }
286 (None, x) => {
287 acc = f(acc, x);
288 left = self.left.next();
289 right = self.right.next();
290 }
291 },
292 (Some(l), None) => {
293 self.left.put_back(l);
294 acc = self.left.fold(acc, |acc, x| f(acc, F::left(x)));
295 break;
296 }
297 (None, Some(r)) => {
298 self.right.put_back(r);
299 acc = self.right.fold(acc, |acc, x| f(acc, F::right(x)));
300 break;
301 }
302 (None, None) => {
303 break;
304 }
305 }
306 }
307
308 acc
309 }
310
311 fn size_hint(&self) -> SizeHint {
312 F::size_hint(self.left.size_hint(), self.right.size_hint())
313 }
314
315 fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
316 loop {
317 if n == 0 {
318 break self.next();
319 }
320 n -= 1;
321 match (self.left.next(), self.right.next()) {
322 (None, None) => break None,
323 (Some(_left), None) => break self.left.nth(n).map(F::left),
324 (None, Some(_right)) => break self.right.nth(n).map(F::right),
325 (Some(left), Some(right)) => {
326 let (not_next, _) = self.cmp_fn.merge(left, right);
327 match not_next {
328 Some(Either::Left(l)) => {
329 self.left.put_back(l);
330 }
331 Some(Either::Right(r)) => {
332 self.right.put_back(r);
333 }
334 None => (),
335 }
336 }
337 }
338 }
339 }
340 }
341
342 impl<I, J, F> FusedIterator for MergeBy<I, J, F>
343 where
344 I: Iterator,
345 J: Iterator,
346 F: OrderingOrBool<I::Item, J::Item>,
347 {
348 }