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: SmallVec::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    /// Converts `inner` to a normalized [`RangeVec`] in place.
53    ///
54    /// This operation is in-place and takes \\(\mathcal{O}(n \log n)\\)
55    /// time.
56    #[inline(always)]
57    pub fn from_vec(inner: Vec<(T, T)>) -> Self {
58        crate::normalize_vec(inner)
59    }
60
61    /// Converts `inner` to a normalized [`RangeVec`] in place.
62    ///
63    /// This operation is in-place and takes \\(\mathcal{O}(n \log n)\\)
64    /// time.
65    #[inline(always)]
66    pub fn from_smallvec<const N: usize>(inner: SmallVec<[(T, T); N]>) -> Self {
67        crate::normalize_vec(inner)
68    }
69
70    /// Returns a reference to the underlying ranges.
71    #[inline(always)]
72    pub fn inner(&self) -> &[(T, T)] {
73        &self.inner
74    }
75
76    /// Extracts the underlying [`SmallVec`] of ranges.
77    ///
78    /// [`SmallVec`]: `smallvec::SmallVec`
79    #[inline(always)]
80    pub fn into_inner(self) -> Backing<T> {
81        self.inner
82    }
83
84    /// Extracts the underlying vector of ranges.
85    #[inline(always)]
86    pub fn into_vec(self) -> Vec<(T, T)> {
87        self.inner.into_vec()
88    }
89
90    /// Returns an iterator for the underlying normalized ranges.
91    #[inline(always)]
92    pub fn iter(
93        &self,
94    ) -> NormalizedRangeIterWrapper<core::iter::Copied<<&'_ Backing<T> as IntoIterator>::IntoIter>>
95    {
96        let iter = self.inner.iter().copied();
97        unsafe { NormalizedRangeIterWrapper::new_unchecked(iter) }
98    }
99
100    /// Determines whether these two [`RangeVec`]s represent the same
101    /// ranges.
102    ///
103    /// This operation takes constant space and time linear in the
104    /// shortest of the two inputs.
105    pub fn eqv(&self, other: &RangeVec<T>) -> bool {
106        self.iter().eqv(other.iter())
107    }
108}
109
110impl<T: Endpoint> Default for RangeVec<T> {
111    fn default() -> Self {
112        RangeVec::new()
113    }
114}
115
116impl<T: Endpoint> IntoIterator for RangeVec<T> {
117    type Item = (T, T);
118    type IntoIter = NormalizedRangeIterWrapper<<Backing<T> as IntoIterator>::IntoIter>;
119
120    #[inline(always)]
121    fn into_iter(self) -> Self::IntoIter {
122        let iter = self.inner.into_iter();
123        unsafe { NormalizedRangeIterWrapper::new_unchecked(iter) }
124    }
125}
126
127impl<'a, T: Endpoint> IntoIterator for &'a RangeVec<T> {
128    type Item = (T, T);
129    type IntoIter =
130        NormalizedRangeIterWrapper<core::iter::Copied<<&'a Backing<T> as IntoIterator>::IntoIter>>;
131
132    #[inline(always)]
133    fn into_iter(self) -> Self::IntoIter {
134        let iter = self.inner.iter().copied();
135        unsafe { NormalizedRangeIterWrapper::new_unchecked(iter) }
136    }
137}
138
139impl<T: Endpoint> core::ops::Deref for RangeVec<T> {
140    type Target = [(T, T)];
141
142    #[inline(always)]
143    fn deref(&self) -> &[(T, T)] {
144        <RangeVec<T>>::inner(self)
145    }
146}
147
148#[cfg_attr(coverage_nightly, coverage(off))]
149#[test]
150fn test_smoke() {
151    use smallvec::smallvec;
152
153    assert_eq!(RangeVec::<u8>::new(), Default::default());
154    assert_eq!(RangeVec::<u8>::new(), unsafe {
155        RangeVec::new_unchecked(smallvec![])
156    });
157    assert!(RangeVec::<u8>::new().is_empty());
158
159    let ranges = unsafe { RangeVec::new_unchecked(smallvec![(2u8, 4u8), (10u8, 20u8)]) };
160
161    assert_eq!(ranges[0], (2u8, 4u8));
162
163    assert_eq!(&ranges, &ranges.iter().collect_range_vec());
164
165    assert!(ranges.eqv(&ranges.iter().collect_range_vec()));
166    assert!(!ranges.eqv(&Default::default()));
167    assert!(!ranges.eqv(&unsafe { RangeVec::new_unchecked(smallvec![(2u8, 4u8), (11u8, 20u8)]) }));
168    assert!(!ranges.eqv(&unsafe {
169        RangeVec::new_unchecked(smallvec![(2u8, 4u8), (10u8, 20u8), (30u8, 30u8)])
170    }));
171    assert!(!ranges.eqv(&unsafe { RangeVec::new_unchecked(smallvec![(2u8, 4u8)]) }));
172
173    assert_eq!(ranges.inner(), &ranges.iter().collect::<Vec<_>>());
174
175    assert_eq!(ranges.inner(), &(&ranges).into_iter().collect::<Vec<_>>());
176    assert_eq!(
177        ranges.clone().into_vec(),
178        ranges.into_iter().collect::<Vec<_>>()
179    );
180}
closed_interval_set/range_vec.rs

closed_interval_set/
range_vec.rs
