range_set_blaze/
union_iter.rs

1use crate::merge::KMerge;
2use crate::union_iter_map::SortedStartsInVec;
3use crate::unsorted_disjoint::UnsortedDisjoint;
4use crate::{AssumeSortedStarts, Merge, SortedDisjoint, SortedStarts, UnionKMerge};
5use crate::{Integer, UnionMerge};
6use core::cmp::max;
7use core::iter::FusedIterator;
8use core::ops::RangeInclusive;
9use itertools::Itertools;
10
11/// This `struct` is created by the [`union`] method on [`SortedStarts`]. See [`union`]'s
12/// documentation for more.
13///
14/// [`SortedStarts`]: crate::SortedStarts
15/// [`union`]: crate::SortedDisjoint::union
16#[derive(Clone, Debug)]
17#[must_use = "iterators are lazy and do nothing unless consumed"]
18pub struct UnionIter<T, SS> {
19    iter: SS,
20    option_range: Option<RangeInclusive<T>>,
21}
22
23impl<T, I> Iterator for UnionIter<T, I>
24where
25    T: Integer,
26    I: SortedStarts<T>,
27{
28    type Item = RangeInclusive<T>;
29
30    fn next(&mut self) -> Option<RangeInclusive<T>> {
31        loop {
32            let Some(range) = self.iter.next() else {
33                return self.option_range.take();
34            };
35
36            let (start, end) = range.into_inner();
37            debug_assert!(start <= end); // real assert
38
39            let Some(current_range) = self.option_range.take() else {
40                self.option_range = Some(start..=end);
41                continue;
42            };
43
44            let (current_start, current_end) = current_range.into_inner();
45            debug_assert!(current_start <= start); // real assert
46            if start <= current_end
47                || (current_end < T::max_value() && start <= current_end.add_one())
48            {
49                self.option_range = Some(current_start..=max(current_end, end));
50                continue;
51            }
52
53            self.option_range = Some(start..=end);
54            return Some(current_start..=current_end);
55        }
56    }
57}
58
59impl<T, I> UnionIter<T, I>
60where
61    T: Integer,
62    I: SortedStarts<T>,
63{
64    /// Creates a new [`UnionIter`] from zero or more [`SortedStarts`] iterators. See [`UnionIter`] for more details and examples.
65    pub(crate) const fn new(iter: I) -> Self {
66        Self {
67            iter,
68            option_range: None,
69        }
70    }
71}
72
73impl<T, L, R> UnionMerge<T, L, R>
74where
75    T: Integer,
76    L: SortedDisjoint<T>,
77    R: SortedDisjoint<T>,
78{
79    #[inline]
80    pub(crate) fn new2(left: L, right: R) -> Self {
81        let iter: Merge<T, L, R> = Merge::new(left, right);
82        Self::new(iter)
83    }
84}
85
86impl<T, J> UnionKMerge<T, J>
87where
88    T: Integer,
89    J: SortedDisjoint<T>,
90{
91    #[inline]
92    pub(crate) fn new_k<K>(k: K) -> Self
93    where
94        K: IntoIterator<Item = J>,
95    {
96        let iter = KMerge::new(k);
97        Self::new(iter)
98    }
99}
100
101// from iter (T, VR) to UnionIter
102impl<T: Integer> FromIterator<RangeInclusive<T>> for UnionIter<T, SortedStartsInVec<T>> {
103    fn from_iter<I>(iter: I) -> Self
104    where
105        I: IntoIterator<Item = RangeInclusive<T>>,
106    {
107        let iter = iter.into_iter();
108        let iter = UnsortedDisjoint::new(iter);
109        let iter = iter.sorted_by(|a, b| a.start().cmp(b.start()));
110        let iter = AssumeSortedStarts::new(iter);
111        Self::new(iter)
112    }
113}
114
115impl<T, I> FusedIterator for UnionIter<T, I>
116where
117    T: Integer,
118    I: SortedStarts<T> + FusedIterator,
119{
120}
range_set_blaze/union_iter.rs

range_set_blaze/
union_iter.rs
