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>
19where
20    T: Integer,
21    SS: SortedStarts<T>,
22{
23    iter: SS,
24    option_range: Option<RangeInclusive<T>>,
25}
26
27impl<T, I> Iterator for UnionIter<T, I>
28where
29    T: Integer,
30    I: SortedStarts<T>,
31{
32    type Item = RangeInclusive<T>;
33
34    fn next(&mut self) -> Option<RangeInclusive<T>> {
35        loop {
36            let Some(range) = self.iter.next() else {
37                return self.option_range.take();
38            };
39
40            let (start, end) = range.into_inner();
41            debug_assert!(start <= end); // real assert
42
43            let Some(current_range) = self.option_range.take() else {
44                self.option_range = Some(start..=end);
45                continue;
46            };
47
48            let (current_start, current_end) = current_range.into_inner();
49            debug_assert!(current_start <= start); // real assert
50            if start <= current_end
51                || (current_end < T::max_value() && start <= current_end.add_one())
52            {
53                self.option_range = Some(current_start..=max(current_end, end));
54                continue;
55            }
56
57            self.option_range = Some(start..=end);
58            return Some(current_start..=current_end);
59        }
60    }
61}
62
63impl<T, I> UnionIter<T, I>
64where
65    T: Integer,
66    I: SortedStarts<T>,
67{
68    /// Creates a new [`UnionIter`] from zero or more [`SortedStarts`] iterators. See [`UnionIter`] for more details and examples.
69    pub(crate) const fn new(iter: I) -> Self {
70        Self {
71            iter,
72            option_range: None,
73        }
74    }
75}
76
77impl<T, L, R> UnionMerge<T, L, R>
78where
79    T: Integer,
80    L: SortedDisjoint<T>,
81    R: SortedDisjoint<T>,
82{
83    #[inline]
84    pub(crate) fn new2(left: L, right: R) -> Self {
85        let iter: Merge<T, L, R> = Merge::new(left, right);
86        Self::new(iter)
87    }
88}
89
90impl<T, J> UnionKMerge<T, J>
91where
92    T: Integer,
93    J: SortedDisjoint<T>,
94{
95    #[inline]
96    pub(crate) fn new_k<K>(k: K) -> Self
97    where
98        K: IntoIterator<Item = J>,
99    {
100        let iter = KMerge::new(k);
101        Self::new(iter)
102    }
103}
104
105// from iter (T, VR) to UnionIter
106impl<T> FromIterator<RangeInclusive<T>> for UnionIter<T, SortedStartsInVec<T>>
107where
108    T: Integer,
109{
110    fn from_iter<I>(iter: I) -> Self
111    where
112        I: IntoIterator<Item = RangeInclusive<T>>,
113    {
114        let iter = iter.into_iter();
115        let iter = UnsortedDisjoint::new(iter);
116        let iter = iter.sorted_by(|a, b| a.start().cmp(b.start()));
117        let iter = AssumeSortedStarts::new(iter);
118        Self::new(iter)
119    }
120}
121
122impl<T, I> FusedIterator for UnionIter<T, I>
123where
124    T: Integer,
125    I: SortedStarts<T> + FusedIterator,
126{
127}
range_set_blaze/union_iter.rs

range_set_blaze/
union_iter.rs
