closed_interval_set/
range_vec.rs

1//! Type wrappers to keep / lose track of the normalized status of
2//! containers (vectors) and iterators of ranges.  A normalized
3//! sequence of ranges is known to contain sorted and disjoint
4//! non-empty ranges.
5use alloc::vec::Vec;
6use smallvec::SmallVec;
7
8use crate::iterator_wrapper::NormalizedRangeIterWrapper;
9use crate::Backing;
10use crate::Endpoint;
11use crate::NormalizedRangeIter;
12
13/// A [`RangeVec<T>`] is a normalized [`SmallVec`] of `(T, T)`,
14/// where the inline capacity is hardcoded to 2 ranges.
15///
16/// This branded wrapper around `SmallVec<[(T, T); 2]>` is the primary
17/// representation for ranges at rest in this [`crate`].
18///
19/// [`SmallVec`]: https://docs.rs/smallvec/latest/smallvec/struct.SmallVec.html
20#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd, Hash)]
21#[repr(transparent)]
22pub struct RangeVec<T: Endpoint> {
23    inner: Backing<T>,
24}
25
26impl<T: Endpoint> RangeVec<T> {
27    /// Returns an empty [`RangeVec`] (represents the empty set).
28    #[inline(always)]
29    pub fn new() -> Self {
30        Self {
31            inner: Backing::new(),
32        }
33    }
34
35    /// Blindly tags a container as normalized: it contains valid
36    /// (non-empty) closed ranges, the ranges don't overlap and aren't
37    /// even adjacent, and the ranges are sorted in ascending order.
38    ///
39    /// This operation takes constant time in release mode, and linear
40    /// time when debug assertions or internal checks are enabled.
41    ///
42    /// # Safety
43    ///
44    /// The caller must check that `inner` is normalized.
45    #[inline(always)]
46    pub unsafe fn new_unchecked(inner: Backing<T>) -> Self {
47        #[cfg(any(feature = "internal_checks", debug_assertions))]
48        assert!(crate::is_normalized(&inner[..]));
49        Self { inner }
50    }
51
52    /// Returns an empty `RangeVec`.
53    #[inline(always)]
54    pub fn empty_set() -> Self {
55        Default::default()
56    }
57
58    /// Returns a `RangeVec` that covers the whole universe of `T`s.
59    #[inline(always)]
60    pub fn universal_set() -> Self {
61        Self::singleton((T::min_value(), T::max_value()))
62    }
63
64    /// Returns a `RangeVec` that represents the input `range` if it
65    /// is a valid range (inclusing start endpoint less than or equal
66    /// to the inclusive stop endpoint), and the empty set otherwise.
67    ///
68    /// This constructor may intrinsically return an empty set, so it
69    /// accepts anything that may be converted to `Option<(T, T)>`,
70    /// including ranges `(T, T)`.
71    #[inline(always)]
72    pub fn singleton(range: impl Into<Option<(T, T)>>) -> Self {
73        fn doit<T: Endpoint>(maybe_range: Option<(T, T)>) -> RangeVec<T> {
74            let mut inner = Backing::new();
75
76            if let Some((lo, hi)) = maybe_range {
77                if lo.cmp_end(hi) <= core::cmp::Ordering::Equal {
78                    inner.push((lo, hi));
79                }
80            }
81
82            unsafe { RangeVec::new_unchecked(inner) }
83        }
84
85        doit(range.into())
86    }
87
88    /// Normalizes this sequence of ranges into a fresh `RangeVec`.
89    ///
90    /// This operation takes \\(\mathcal{O}(n \log n)\\) time, where
91    /// \\(n\\) is the number of ranges in the `ranges` argument.
92    #[inline(always)]
93    pub fn from(ranges: impl Into<crate::RangeCase<T>>) -> Self {
94        crate::normalize_vec(ranges.into())
95    }
96
97    /// Converts `inner` to a normalized [`RangeVec`] in place.
98    ///
99    /// This operation is in-place and takes \\(\mathcal{O}(n \log n)\\)
100    /// time.
101    #[inline(always)]
102    pub fn from_vec(inner: Vec<(T, T)>) -> Self {
103        Self::from(inner)
104    }
105
106    /// Converts `inner` to a normalized [`RangeVec`] in place.
107    ///
108    /// This operation is in-place and takes \\(\mathcal{O}(n \log n)\\)
109    /// time.
110    #[inline(always)]
111    pub fn from_smallvec<const N: usize>(inner: SmallVec<[(T, T); N]>) -> Self {
112        Self::from(inner)
113    }
114
115    /// Returns a reference to the underlying ranges.
116    #[inline(always)]
117    pub fn inner(&self) -> &[(T, T)] {
118        &self.inner
119    }
120
121    /// Extracts the underlying [`SmallVec`] of ranges.
122    ///
123    /// [`SmallVec`]: `smallvec::SmallVec`
124    #[inline(always)]
125    pub fn into_inner(self) -> Backing<T> {
126        self.inner
127    }
128
129    /// Extracts the underlying vector of ranges.
130    #[inline(always)]
131    pub fn into_vec(self) -> Vec<(T, T)> {
132        self.inner.into_vec()
133    }
134
135    /// Returns an iterator for the underlying normalized ranges.
136    #[inline(always)]
137    pub fn iter(
138        &self,
139    ) -> NormalizedRangeIterWrapper<core::iter::Copied<<&'_ Backing<T> as IntoIterator>::IntoIter>>
140    {
141        let iter = self.inner.iter().copied();
142        unsafe { NormalizedRangeIterWrapper::new_unchecked(iter) }
143    }
144
145    /// Determines whether these two [`RangeVec`]s represent the same
146    /// ranges.
147    ///
148    /// This operation takes constant space and time linear in the
149    /// shortest of the two inputs.
150    pub fn eqv(&self, other: &RangeVec<T>) -> bool {
151        self.iter().eqv(other.iter())
152    }
153}
154
155impl<T: Endpoint> Default for RangeVec<T> {
156    #[inline(always)]
157    fn default() -> Self {
158        RangeVec::new()
159    }
160}
161
162impl<T: Endpoint> IntoIterator for RangeVec<T> {
163    type Item = (T, T);
164    type IntoIter = NormalizedRangeIterWrapper<<Backing<T> as IntoIterator>::IntoIter>;
165
166    #[inline(always)]
167    fn into_iter(self) -> Self::IntoIter {
168        let iter = self.inner.into_iter();
169        unsafe { NormalizedRangeIterWrapper::new_unchecked(iter) }
170    }
171}
172
173impl<'a, T: Endpoint> IntoIterator for &'a RangeVec<T> {
174    type Item = (T, T);
175    type IntoIter =
176        NormalizedRangeIterWrapper<core::iter::Copied<<&'a Backing<T> as IntoIterator>::IntoIter>>;
177
178    #[inline(always)]
179    fn into_iter(self) -> Self::IntoIter {
180        let iter = self.inner.iter().copied();
181        unsafe { NormalizedRangeIterWrapper::new_unchecked(iter) }
182    }
183}
184
185impl<T: Endpoint> core::ops::Deref for RangeVec<T> {
186    type Target = [(T, T)];
187
188    #[inline(always)]
189    fn deref(&self) -> &[(T, T)] {
190        <RangeVec<T>>::inner(self)
191    }
192}
193
194#[cfg_attr(coverage_nightly, coverage(off))]
195#[test]
196fn test_smoke() {
197    use smallvec::smallvec;
198
199    assert_eq!(RangeVec::<u8>::new(), Default::default());
200    assert_eq!(RangeVec::<u8>::new(), unsafe {
201        RangeVec::new_unchecked(smallvec![])
202    });
203    assert!(RangeVec::<u8>::empty_set().is_empty());
204
205    // Exercise a few other ways to generate the empty set
206    assert_eq!(RangeVec::<u8>::singleton(None), RangeVec::empty_set());
207    assert_eq!(RangeVec::<u8>::singleton((1u8, 0u8)), RangeVec::empty_set());
208    assert_eq!(
209        RangeVec::<u8>::singleton(Some((1u8, 0u8))),
210        RangeVec::empty_set()
211    );
212
213    assert_eq!(
214        RangeVec::<u8>::universal_set(),
215        RangeVec::singleton((0u8, 255u8))
216    );
217
218    assert_eq!(
219        RangeVec::<u8>::universal_set(),
220        RangeVec::from([(0u8, 255u8)])
221    );
222    let ranges = unsafe { RangeVec::new_unchecked(smallvec![(2u8, 4u8), (10u8, 20u8)]) };
223
224    assert_eq!(ranges[0], (2u8, 4u8));
225
226    assert_eq!(&ranges, &ranges.iter().collect_range_vec());
227
228    assert!(ranges.eqv(&ranges.iter().collect_range_vec()));
229    assert!(!ranges.eqv(&Default::default()));
230    assert!(!ranges.eqv(&unsafe { RangeVec::new_unchecked(smallvec![(2u8, 4u8), (11u8, 20u8)]) }));
231    assert!(!ranges.eqv(&unsafe {
232        RangeVec::new_unchecked(smallvec![(2u8, 4u8), (10u8, 20u8), (30u8, 30u8)])
233    }));
234    assert!(!ranges.eqv(&unsafe { RangeVec::new_unchecked(smallvec![(2u8, 4u8)]) }));
235
236    assert_eq!(ranges.inner(), &ranges.iter().collect::<Vec<_>>());
237
238    assert_eq!(ranges.inner(), &(&ranges).into_iter().collect::<Vec<_>>());
239    assert_eq!(
240        ranges.clone().into_vec(),
241        ranges.into_iter().collect::<Vec<_>>()
242    );
243}
closed_interval_set/range_vec.rs

closed_interval_set/
range_vec.rs
