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/// Works with [`UnionIter`] to turn any number of [`SortedDisjoint`] iterators into a [`SortedDisjoint`] iterator of their union,
8/// i.e., all the integers in any input iterator, as sorted & disjoint ranges.
9///
10/// Also see [`KMerge`].
11///
12/// [`SortedDisjoint`]: crate::SortedDisjoint
13/// [`UnionIter`]: crate::UnionIter
14///
15/// # Examples
16///
17/// ```
18/// use itertools::Itertools;
19/// use range_set_blaze::{UnionIter, Merge, SortedDisjoint, CheckSortedDisjoint};
20///
21/// let a = CheckSortedDisjoint::new(vec![1..=2, 5..=100]);
22/// let b = CheckSortedDisjoint::from([2..=6]);
23/// let union = UnionIter::new(Merge::new(a, b));
24/// assert_eq!(union.to_string(), "1..=100");
25///
26/// // Or, equivalently:
27/// let a = CheckSortedDisjoint::new(vec![1..=2, 5..=100]);
28/// let b = CheckSortedDisjoint::from([2..=6]);
29/// let c = a | b;
30/// assert_eq!(c.to_string(), "1..=100")
31/// ```
32#[derive(Clone, Debug)]
33#[must_use = "iterators are lazy and do nothing unless consumed"]
34pub struct Merge<T, L, R>
35where
36    T: Integer,
37    L: SortedDisjoint<T>,
38    R: SortedDisjoint<T>,
39{
40    #[allow(clippy::type_complexity)]
41    iter: MergeBy<L, R, fn(&RangeInclusive<T>, &RangeInclusive<T>) -> bool>,
42}
43
44impl<T, L, R> Merge<T, L, R>
45where
46    T: Integer,
47    L: SortedDisjoint<T>,
48    R: SortedDisjoint<T>,
49{
50    /// Creates a new [`Merge`] iterator from two [`SortedDisjoint`] iterators. See [`Merge`] for more details and examples.
51    pub fn new(left: L, right: R) -> Self {
52        Self {
53            iter: left.merge_by(right, |a, b| a.start() < b.start()),
54        }
55    }
56}
57
58impl<T, L, R> FusedIterator for Merge<T, L, R>
59where
60    T: Integer,
61    L: SortedDisjoint<T>,
62    R: SortedDisjoint<T>,
63{
64}
65
66impl<T, L, R> Iterator for Merge<T, L, R>
67where
68    T: Integer,
69    L: SortedDisjoint<T>,
70    R: SortedDisjoint<T>,
71{
72    type Item = RangeInclusive<T>;
73
74    fn next(&mut self) -> Option<Self::Item> {
75        self.iter.next()
76    }
77
78    fn size_hint(&self) -> (usize, Option<usize>) {
79        self.iter.size_hint()
80    }
81}
82
83impl<T, L, R> SortedStarts<T> for Merge<T, L, R>
84where
85    T: Integer,
86    L: SortedDisjoint<T>,
87    R: SortedDisjoint<T>,
88{
89}
90
91/// Works with [`UnionIter`] to turn two [`SortedDisjoint`] iterators into a [`SortedDisjoint`] iterator of their union,
92/// i.e., all the integers in any input iterator, as sorted & disjoint ranges.
93///
94/// Also see [`Merge`].
95///
96/// [`SortedDisjoint`]: crate::SortedDisjoint
97/// [`UnionIter`]: crate::UnionIter
98///
99/// # Examples
100///
101/// ```
102/// use itertools::Itertools;
103/// use range_set_blaze::{UnionIter, KMerge, MultiwaySortedDisjoint, SortedDisjoint, CheckSortedDisjoint};
104///
105/// let a = CheckSortedDisjoint::new(vec![1..=2, 5..=100]);
106/// let b = CheckSortedDisjoint::new(vec![2..=6]);
107/// let c = CheckSortedDisjoint::new(vec![-1..=-1]);
108/// let union = UnionIter::new(KMerge::new([a, b, c]));
109/// assert_eq!(union.to_string(), "-1..=-1, 1..=100");
110///
111/// // Or, equivalently:
112/// let a = CheckSortedDisjoint::new(vec![1..=2, 5..=100]);
113/// let b = CheckSortedDisjoint::new(vec![2..=6]);
114/// let c = CheckSortedDisjoint::new(vec![-1..=-1]);
115/// let union = [a, b, c].union();
116/// assert_eq!(union.to_string(), "-1..=-1, 1..=100");
117/// ```
118#[derive(Clone, Debug)]
119#[must_use = "iterators are lazy and do nothing unless consumed"]
120pub struct KMerge<T, I>
121where
122    T: Integer,
123    I: SortedDisjoint<T>,
124{
125    #[allow(clippy::type_complexity)]
126    iter: KMergeBy<I, fn(&RangeInclusive<T>, &RangeInclusive<T>) -> bool>,
127}
128
129impl<T, I> KMerge<T, I>
130where
131    T: Integer,
132    I: SortedDisjoint<T>,
133{
134    /// Creates a new [`KMerge`] iterator from zero or more [`SortedDisjoint`] iterators. See [`KMerge`] for more details and examples.
135    pub fn new<J>(iter: J) -> Self
136    where
137        J: IntoIterator<Item = I>,
138    {
139        Self {
140            iter: iter.into_iter().kmerge_by(|a, b| a.start() < b.start()),
141        }
142    }
143}
144
145impl<T, I> FusedIterator for KMerge<T, I>
146where
147    T: Integer,
148    I: SortedDisjoint<T>,
149{
150}
151
152impl<T, I> Iterator for KMerge<T, I>
153where
154    T: Integer,
155    I: SortedDisjoint<T>,
156{
157    type Item = RangeInclusive<T>;
158
159    fn next(&mut self) -> Option<Self::Item> {
160        self.iter.next()
161    }
162
163    fn size_hint(&self) -> (usize, Option<usize>) {
164        self.iter.size_hint()
165    }
166}
167
168impl<T, I> SortedStarts<T> for KMerge<T, I>
169where
170    T: Integer,
171    I: SortedDisjoint<T>,
172{
173}
range_set_blaze/merge.rs

range_set_blaze/
merge.rs
