range_set_blaze/
merge.rs

1use core::{fmt::Debug, iter::FusedIterator, ops::RangeInclusive};
2
3use itertools::{Itertools, KMergeBy, MergeBy};
4
5use crate::{Integer, SortedDisjoint, SortedStarts};
6
7/// Used internally by `UnionIter` and `SymDiffIter`.
8#[must_use = "iterators are lazy and do nothing unless consumed"]
9#[derive(Clone, Debug)]
10pub struct Merge<T, L, R>
11where
12    L: Iterator<Item: Debug + Clone>,
13    R: Iterator<Item: Debug + Clone>,
14{
15    #[allow(clippy::type_complexity)]
16    iter: MergeBy<L, R, fn(&RangeInclusive<T>, &RangeInclusive<T>) -> bool>,
17}
18
19impl<T, L, R> Merge<T, L, R>
20where
21    T: Integer,
22    L: SortedDisjoint<T>,
23    R: SortedDisjoint<T>,
24{
25    /// Creates a new [`Merge`] iterator from two [`SortedDisjoint`] iterators. See [`Merge`] for more details and examples.
26    ///
27    /// [SortedDisjoint]: crate::SortedDisjoint.html#table-of-contents
28    #[inline]
29    pub(crate) fn new(left: L, right: R) -> Self {
30        Self {
31            iter: left.merge_by(right, |a, b| a.start() < b.start()),
32        }
33    }
34}
35
36impl<T, L, R> FusedIterator for Merge<T, L, R>
37where
38    T: Integer,
39    L: SortedDisjoint<T>,
40    R: SortedDisjoint<T>,
41{
42}
43
44impl<T, L, R> Iterator for Merge<T, L, R>
45where
46    T: Integer,
47    L: SortedDisjoint<T>,
48    R: SortedDisjoint<T>,
49{
50    type Item = RangeInclusive<T>;
51
52    fn next(&mut self) -> Option<Self::Item> {
53        self.iter.next()
54    }
55
56    fn size_hint(&self) -> (usize, Option<usize>) {
57        self.iter.size_hint()
58    }
59}
60
61impl<T, L, R> SortedStarts<T> for Merge<T, L, R>
62where
63    T: Integer,
64    L: SortedDisjoint<T>,
65    R: SortedDisjoint<T>,
66{
67}
68
69/// Used internally by `UnionIter` and `SymDiffIter`.
70#[derive(Clone, Debug)]
71#[allow(clippy::module_name_repetitions)]
72#[must_use = "iterators are lazy and do nothing unless consumed"]
73pub struct KMerge<T, I>
74where
75    I: Iterator<Item: Debug + Clone>,
76{
77    #[allow(clippy::type_complexity)]
78    iter: KMergeBy<I, fn(&RangeInclusive<T>, &RangeInclusive<T>) -> bool>,
79}
80
81type RangeMergeIter<T, I> = KMergeBy<I, fn(&RangeInclusive<T>, &RangeInclusive<T>) -> bool>;
82
83impl<T, I> KMerge<T, I>
84where
85    T: Integer,
86    I: SortedDisjoint<T>,
87{
88    pub(crate) fn new<K>(iter: K) -> Self
89    where
90        K: IntoIterator<Item = I>,
91    {
92        let iter = iter.into_iter();
93        // Merge RangeValues by start with ties broken by priority
94        let iter: RangeMergeIter<T, I> = iter.kmerge_by(|a, b| a.start() < b.start());
95        Self { iter }
96    }
97}
98
99impl<T, I> FusedIterator for KMerge<T, I>
100where
101    T: Integer,
102    I: SortedDisjoint<T>,
103{
104}
105
106impl<T, I> Iterator for KMerge<T, I>
107where
108    T: Integer,
109    I: SortedDisjoint<T>,
110{
111    type Item = RangeInclusive<T>;
112
113    fn next(&mut self) -> Option<Self::Item> {
114        self.iter.next()
115    }
116
117    fn size_hint(&self) -> (usize, Option<usize>) {
118        self.iter.size_hint()
119    }
120}
121
122impl<T, I> SortedStarts<T> for KMerge<T, I>
123where
124    T: Integer,
125    I: SortedDisjoint<T>,
126{
127}
range_set_blaze/merge.rs

range_set_blaze/
merge.rs
