range_set_blaze/
merge.rs

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

range_set_blaze/
merge.rs
