more_iter/merge/
mod.rs

1#[cfg(test)] mod merge_pairs_test;
2
3pub mod merge_pairs_ext;
4
5use std::iter::Peekable;
6
7/// Merge two **sorted** [`Iterator`] of `(key, value)` pairs in **ascending** order into a single
8/// iterator. Duplicate keys are reduce by the provided `merge_value()` function.
9///
10/// The provided `merge_value(V,V)->MERGED` function determines how to merge two values with the
11/// same key.
12///
13/// # Type Parameters
14/// - `K`: The key type, which must implement [`Ord`] for ordering.
15/// - `V`: The value type.
16/// - `L`: The iterator type for the left input, where `Item = (K, V)`.
17/// - `R`: The iterator type for the right input, where `Item = (K, V)`.
18/// - `MERGED`: The merge result type. By default it is the same as `V`.
19///
20/// # Examples
21///
22/// Merge two `(key, value)` iterators by key, keeping the largest value:
23/// ```
24/// # use more_iter::MergePairs;
25/// let a = [(1, 10), (3, 30), (4, 40)];
26/// let b = [(2, 200), (3, 300)];
27///
28/// let merged = MergePairs::merge(a, Some(b), std::cmp::max).collect::<Vec<_>>();
29/// assert_eq!(vec![(1, 10), (2, 200), (3, 300), (4, 40)], merged);
30/// ```
31pub struct MergePairs<K, V, L, R, MERGED = V>
32where
33    K: Ord,
34    L: Iterator<Item = (K, V)>,
35    R: Iterator<Item = (K, V)>,
36{
37    left: Peekable<L>,
38    right: Option<Peekable<R>>,
39    merge_value: fn(V, V) -> MERGED,
40}
41
42impl<K, V, L, R, MERGED> MergePairs<K, V, L, R, MERGED>
43where
44    K: Ord,
45    L: Iterator<Item = (K, V)>,
46    R: Iterator<Item = (K, V)>,
47{
48    /// Creates a new `Merge` instance that merges the `left` and `right` iterators.
49    ///
50    /// The `merge` function is used to decide which value to keep when duplicate keys are
51    /// encountered.
52    pub fn merge<IL, IR>(left: IL, right: Option<IR>, merge_value: fn(V, V) -> MERGED) -> Self
53    where
54        IL: IntoIterator<Item = (K, V), IntoIter = L>,
55        IR: IntoIterator<Item = (K, V), IntoIter = R>,
56    {
57        MergePairs {
58            left: left.into_iter().peekable(),
59            right: right.map(|x| x.into_iter().peekable()),
60            merge_value,
61        }
62    }
63}
64
65impl<K, V, L, MERGED> MergePairs<K, V, L, L, MERGED>
66where
67    K: Ord,
68    L: Iterator<Item = (K, V)>,
69{
70    /// Creates a new `Merge` instance that merges the `left` and `right` iterators.
71    ///
72    /// The `merge` function is used to decide which value to keep when duplicate keys are
73    /// encountered.
74    pub fn single<IL, IR>(left: IL, merge_value: fn(V, V) -> MERGED) -> Self
75    where IL: IntoIterator<Item = (K, V), IntoIter = L> {
76        MergePairs {
77            left: left.into_iter().peekable(),
78            right: None,
79            merge_value,
80        }
81    }
82}
83
84impl<K, V, L, R> Iterator for MergePairs<K, V, L, R>
85where
86    K: Ord,
87    L: Iterator<Item = (K, V)>,
88    R: Iterator<Item = (K, V)>,
89{
90    type Item = (K, V);
91
92    fn next(&mut self) -> Option<Self::Item> {
93        let right = if let Some(right) = &mut self.right {
94            right
95        } else {
96            return self.left.next();
97        };
98
99        // Left iterator is exhausted, return right iterator
100        let left_key = if let Some((k, _)) = self.left.peek() {
101            k
102        } else {
103            return right.next();
104        };
105
106        // Right iterator is exhausted, return left iterator
107        let right_key = if let Some((k, _)) = right.peek() {
108            k
109        } else {
110            return self.left.next();
111        };
112
113        // Both iterators have values, return the one with smaller key
114
115        if left_key < right_key {
116            return self.left.next();
117        }
118
119        if left_key > right_key {
120            return right.next();
121        }
122
123        // Same key, merge the values
124
125        let (k, left_value): (K, V) = self.left.next().unwrap();
126        let (_, right_value): (K, V) = right.next().unwrap();
127
128        let v = (self.merge_value)(left_value, right_value);
129        Some((k, v))
130    }
131}
more_iter/merge/mod.rs

more_iter/merge/
mod.rs
