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    /// Determines whether `self` fully contains `other`.
136    pub fn contains(&self, other: &RangeVec<T>) -> bool {
137        // other \in self <==> other /\ -self == emptyset
138        self.iter()
139            .complement()
140            .intersect_vec(other)
141            .into_empty_flag()
142    }
143
144    /// Returns an iterator for the underlying normalized ranges.
145    #[inline(always)]
146    pub fn iter(
147        &self,
148    ) -> NormalizedRangeIterWrapper<core::iter::Copied<<&'_ Backing<T> as IntoIterator>::IntoIter>>
149    {
150        let iter = self.inner.iter().copied();
151        unsafe { NormalizedRangeIterWrapper::new_unchecked(iter) }
152    }
153
154    /// Determines whether these two [`RangeVec`]s represent the same
155    /// ranges.
156    ///
157    /// This operation takes constant space and time linear in the
158    /// shortest of the two inputs.
159    pub fn eqv(&self, other: &RangeVec<T>) -> bool {
160        self.iter().eqv(other.iter())
161    }
162}
163
164impl<T: Endpoint> Default for RangeVec<T> {
165    #[inline(always)]
166    fn default() -> Self {
167        RangeVec::new()
168    }
169}
170
171impl<T: Endpoint, Item> core::iter::FromIterator<Item> for RangeVec<T>
172where
173    Item: crate::ClosedRange<EndT = T>,
174{
175    #[inline(always)]
176    fn from_iter<It: IntoIterator<Item = Item>>(iter: It) -> Self {
177        Self::from(crate::RangeCase::from_iter(iter))
178    }
179}
180
181impl<T: Endpoint> IntoIterator for RangeVec<T> {
182    type Item = (T, T);
183    type IntoIter = NormalizedRangeIterWrapper<<Backing<T> as IntoIterator>::IntoIter>;
184
185    #[inline(always)]
186    fn into_iter(self) -> Self::IntoIter {
187        let iter = self.inner.into_iter();
188        unsafe { NormalizedRangeIterWrapper::new_unchecked(iter) }
189    }
190}
191
192impl<'a, T: Endpoint> IntoIterator for &'a RangeVec<T> {
193    type Item = (T, T);
194    type IntoIter =
195        NormalizedRangeIterWrapper<core::iter::Copied<<&'a Backing<T> as IntoIterator>::IntoIter>>;
196
197    #[inline(always)]
198    fn into_iter(self) -> Self::IntoIter {
199        let iter = self.inner.iter().copied();
200        unsafe { NormalizedRangeIterWrapper::new_unchecked(iter) }
201    }
202}
203
204impl<T: Endpoint> core::ops::Deref for RangeVec<T> {
205    type Target = [(T, T)];
206
207    #[inline(always)]
208    fn deref(&self) -> &[(T, T)] {
209        <RangeVec<T>>::inner(self)
210    }
211}
212
213#[cfg_attr(coverage_nightly, coverage(off))]
214#[test]
215fn test_smoke() {
216    use smallvec::smallvec;
217
218    assert_eq!(RangeVec::<u8>::new(), Default::default());
219    assert_eq!(RangeVec::<u8>::new(), unsafe {
220        RangeVec::new_unchecked(smallvec![])
221    });
222    assert!(RangeVec::<u8>::empty_set().is_empty());
223
224    // Exercise a few other ways to generate the empty set
225    assert_eq!(RangeVec::<u8>::singleton(None), RangeVec::empty_set());
226    assert_eq!(RangeVec::<u8>::singleton((1u8, 0u8)), RangeVec::empty_set());
227    assert_eq!(
228        RangeVec::<u8>::singleton(Some((1u8, 0u8))),
229        RangeVec::empty_set()
230    );
231
232    assert_eq!(
233        RangeVec::<u8>::universal_set(),
234        RangeVec::singleton((0u8, 255u8))
235    );
236
237    assert_eq!(
238        RangeVec::<u8>::universal_set(),
239        RangeVec::from([(0u8, 255u8)])
240    );
241    let ranges = unsafe { RangeVec::new_unchecked(smallvec![(2u8, 4u8), (10u8, 20u8)]) };
242
243    assert_eq!(ranges[0], (2u8, 4u8));
244
245    assert_eq!(&ranges, &RangeVec::from_iter([(2u8, 4u8), (10u8, 20u8)]));
246    assert_eq!(&ranges, &ranges.iter().collect_range_vec());
247
248    assert!(ranges.eqv(&ranges.iter().collect_range_vec()));
249    assert!(!ranges.eqv(&Default::default()));
250    assert!(!ranges.eqv(&unsafe { RangeVec::new_unchecked(smallvec![(2u8, 4u8), (11u8, 20u8)]) }));
251    assert!(!ranges.eqv(&unsafe {
252        RangeVec::new_unchecked(smallvec![(2u8, 4u8), (10u8, 20u8), (30u8, 30u8)])
253    }));
254    assert!(!ranges.eqv(&unsafe { RangeVec::new_unchecked(smallvec![(2u8, 4u8)]) }));
255
256    assert_eq!(ranges.inner(), &ranges.iter().collect::<Vec<_>>());
257
258    assert_eq!(ranges.inner(), &(&ranges).into_iter().collect::<Vec<_>>());
259    assert_eq!(
260        ranges.clone().into_vec(),
261        ranges.into_iter().collect::<Vec<_>>()
262    );
263
264    assert!(RangeVec::singleton((1u8, 10u8)).contains(&RangeVec::singleton((2u8, 4u8))));
265    assert!(!RangeVec::singleton((1u8, 10u8)).contains(&RangeVec::singleton((2u8, 11u8))));
266}
closed_interval_set/range_vec.rs

closed_interval_set/
range_vec.rs
