range_set_blaze/
ranges.rs

1use alloc::collections::btree_map;
2use core::{
3    iter::FusedIterator,
4    ops::{self, RangeInclusive},
5};
6
7use itertools::Itertools;
8
9use crate::{
10    BitAndMerge, BitOrMerge, BitSubMerge, BitXOr, BitXOrTee, Integer, NotIter, SortedDisjoint,
11    SortedStarts,
12};
13
14/// An iterator that visits the ranges in the [`RangeSetBlaze`],
15/// i.e., the integers as sorted & disjoint ranges.
16///
17/// This `struct` is created by the [`ranges`] method on [`RangeSetBlaze`]. See [`ranges`]'s
18/// documentation for more.
19///
20/// [`RangeSetBlaze`]: crate::RangeSetBlaze
21/// [`ranges`]: crate::RangeSetBlaze::ranges
22#[derive(Clone, Debug)]
23#[must_use = "iterators are lazy and do nothing unless consumed"]
24pub struct RangesIter<'a, T: Integer> {
25    pub(crate) iter: btree_map::Iter<'a, T, T>,
26}
27
28impl<'a, T: Integer> AsRef<RangesIter<'a, T>> for RangesIter<'a, T> {
29    fn as_ref(&self) -> &Self {
30        // Self is RangesIter<'a>, the type for which we impl AsRef
31        self
32    }
33}
34
35// RangesIter (one of the iterators from RangeSetBlaze) is SortedDisjoint
36impl<T: Integer> SortedStarts<T> for RangesIter<'_, T> {}
37impl<T: Integer> SortedDisjoint<T> for RangesIter<'_, T> {}
38
39impl<T: Integer> ExactSizeIterator for RangesIter<'_, T> {
40    #[must_use]
41    fn len(&self) -> usize {
42        self.iter.len()
43    }
44}
45
46impl<'a, T: Integer> FusedIterator for RangesIter<'a, T> {}
47
48// Range's iterator is just the inside BTreeMap iterator as values
49impl<'a, T: Integer> Iterator for RangesIter<'a, T> {
50    type Item = RangeInclusive<T>;
51
52    fn next(&mut self) -> Option<Self::Item> {
53        self.iter.next().map(|(start, end)| *start..=*end)
54    }
55
56    fn size_hint(&self) -> (usize, Option<usize>) {
57        self.iter.size_hint()
58    }
59}
60
61impl<T: Integer> DoubleEndedIterator for RangesIter<'_, T> {
62    fn next_back(&mut self) -> Option<Self::Item> {
63        self.iter.next_back()
64            .map(|(start, end)| *start..=*end)
65    }
66}
67
68#[must_use = "iterators are lazy and do nothing unless consumed"]
69/// An iterator that moves out the ranges in the [`RangeSetBlaze`],
70/// i.e., the integers as sorted & disjoint ranges.
71///
72/// This `struct` is created by the [`into_ranges`] method on [`RangeSetBlaze`]. See [`into_ranges`]'s
73/// documentation for more.
74///
75/// [`RangeSetBlaze`]: crate::RangeSetBlaze
76/// [`into_ranges`]: crate::RangeSetBlaze::into_ranges
77#[derive(Debug)]
78pub struct IntoRangesIter<T: Integer> {
79    pub(crate) iter: alloc::collections::btree_map::IntoIter<T, T>,
80}
81
82impl<T: Integer> SortedStarts<T> for IntoRangesIter<T> {}
83impl<T: Integer> SortedDisjoint<T> for IntoRangesIter<T> {}
84
85impl<T: Integer> ExactSizeIterator for IntoRangesIter<T> {
86    #[must_use]
87    fn len(&self) -> usize {
88        self.iter.len()
89    }
90}
91
92impl<T: Integer> FusedIterator for IntoRangesIter<T> {}
93
94// Range's iterator is just the inside BTreeMap iterator as values
95impl<T: Integer> Iterator for IntoRangesIter<T> {
96    type Item = RangeInclusive<T>;
97
98    fn next(&mut self) -> Option<Self::Item> {
99        self.iter.next().map(|(start, end)| start..=end)
100    }
101
102    fn size_hint(&self) -> (usize, Option<usize>) {
103        self.iter.size_hint()
104    }
105}
106
107impl<T: Integer> DoubleEndedIterator for IntoRangesIter<T> {
108    fn next_back(&mut self) -> Option<Self::Item> {
109        self.iter.next_back()
110            .map(|(start, end)| start..=end)
111    }
112}
113
114
115impl<T: Integer> ops::Not for RangesIter<'_, T> {
116    type Output = NotIter<T, Self>;
117
118    fn not(self) -> Self::Output {
119        self.complement()
120    }
121}
122
123impl<T: Integer> ops::Not for IntoRangesIter<T> {
124    type Output = NotIter<T, Self>;
125
126    fn not(self) -> Self::Output {
127        self.complement()
128    }
129}
130
131impl<T: Integer, I> ops::BitOr<I> for RangesIter<'_, T>
132where
133    I: SortedDisjoint<T>,
134{
135    type Output = BitOrMerge<T, Self, I>;
136
137    fn bitor(self, other: I) -> Self::Output {
138        SortedDisjoint::union(self, other)
139    }
140}
141
142impl<T: Integer, I> ops::BitOr<I> for IntoRangesIter<T>
143where
144    I: SortedDisjoint<T>,
145{
146    type Output = BitOrMerge<T, Self, I>;
147
148    fn bitor(self, other: I) -> Self::Output {
149        SortedDisjoint::union(self, other)
150    }
151}
152
153impl<T: Integer, I> ops::Sub<I> for RangesIter<'_, T>
154where
155    I: SortedDisjoint<T>,
156{
157    type Output = BitSubMerge<T, Self, I>;
158
159    fn sub(self, other: I) -> Self::Output {
160        SortedDisjoint::difference(self, other)
161    }
162}
163
164impl<T: Integer, I> ops::Sub<I> for IntoRangesIter<T>
165where
166    I: SortedDisjoint<T>,
167{
168    type Output = BitSubMerge<T, Self, I>;
169
170    fn sub(self, other: I) -> Self::Output {
171        SortedDisjoint::difference(self, other)
172    }
173}
174
175impl<T: Integer, I> ops::BitXor<I> for RangesIter<'_, T>
176where
177    I: SortedDisjoint<T>,
178{
179    type Output = BitXOr<T, Self, I>;
180
181    #[allow(clippy::suspicious_arithmetic_impl)]
182    fn bitxor(self, other: I) -> Self::Output {
183        // We optimize by using self.clone() instead of tee
184        let lhs1 = self.clone();
185        let (rhs0, rhs1) = other.tee();
186        (self - rhs0) | (rhs1.difference(lhs1))
187    }
188}
189
190impl<T: Integer, I> ops::BitXor<I> for IntoRangesIter<T>
191where
192    I: SortedDisjoint<T>,
193{
194    type Output = BitXOrTee<T, Self, I>;
195
196    #[allow(clippy::suspicious_arithmetic_impl)]
197    fn bitxor(self, other: I) -> Self::Output {
198        SortedDisjoint::symmetric_difference(self, other)
199    }
200}
201
202impl<T: Integer, I> ops::BitAnd<I> for RangesIter<'_, T>
203where
204    I: SortedDisjoint<T>,
205{
206    type Output = BitAndMerge<T, Self, I>;
207
208    #[allow(clippy::suspicious_arithmetic_impl)]
209    fn bitand(self, other: I) -> Self::Output {
210        SortedDisjoint::intersection(self, other)
211    }
212}
213
214impl<T: Integer, I> ops::BitAnd<I> for IntoRangesIter<T>
215where
216    I: SortedDisjoint<T>,
217{
218    type Output = BitAndMerge<T, Self, I>;
219
220    #[allow(clippy::suspicious_arithmetic_impl)]
221    fn bitand(self, other: I) -> Self::Output {
222        SortedDisjoint::intersection(self, other)
223    }
224}
range_set_blaze/ranges.rs

range_set_blaze/
ranges.rs
