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 core::iter::DoubleEndedIterator;
7use core::iter::ExactSizeIterator;
8use smallvec::SmallVec;
9
10use crate::iterator_wrapper::NormalizedRangeIterWrapper;
11use crate::Backing;
12use crate::Endpoint;
13use crate::NormalizedRangeIter;
14
15/// A [`RangeVec<T>`] is a normalized [`SmallVec`] of `(T, T)`,
16/// where the inline capacity is hardcoded to 2 ranges.
17///
18/// This branded wrapper around `SmallVec<[(T, T); 2]>` is the primary
19/// representation for ranges at rest in this [`crate`].
20///
21/// [`SmallVec`]: https://docs.rs/smallvec/latest/smallvec/struct.SmallVec.html
22#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd, Hash)]
23#[repr(transparent)]
24pub struct RangeVec<T: Endpoint> {
25    inner: Backing<T>,
26}
27
28impl<T: Endpoint> RangeVec<T> {
29    /// Returns an empty [`RangeVec`] (represents the empty set).
30    #[inline(always)]
31    pub fn new() -> Self {
32        Self {
33            inner: SmallVec::new(),
34        }
35    }
36
37    /// Blindly tags a container as normalized: it contains valid
38    /// (non-empty) closed ranges, the ranges don't overlap and aren't
39    /// even adjacent, and the ranges are sorted in ascending order.
40    ///
41    /// This operation takes constant time in release mode, and linear
42    /// time when debug assertions or internal checks are enabled.
43    ///
44    /// # Safety
45    ///
46    /// The caller must check that `inner` is normalized.
47    #[inline(always)]
48    pub unsafe fn new_unchecked(inner: Backing<T>) -> Self {
49        #[cfg(any(feature = "internal_checks", debug_assertions))]
50        assert!(crate::is_normalized(&inner[..]));
51        Self { inner }
52    }
53
54    /// Converts `inner` to a normalized [`RangeVec`] in place.
55    ///
56    /// This operation is in-place and takes \\(\mathcal{O}(n \log n)\\)
57    /// time.
58    #[inline(always)]
59    pub fn from_vec(inner: Vec<(T, T)>) -> Self {
60        crate::normalize_vec(inner)
61    }
62
63    /// Converts `inner` to a normalized [`RangeVec`] in place.
64    ///
65    /// This operation is in-place and takes \\(\mathcal{O}(n \log n)\\)
66    /// time.
67    #[inline(always)]
68    pub fn from_smallvec<const N: usize>(inner: SmallVec<[(T, T); N]>) -> Self {
69        crate::normalize_vec(inner)
70    }
71
72    /// Returns a reference to the underlying ranges.
73    #[inline(always)]
74    pub fn inner(&self) -> &[(T, T)] {
75        &self.inner
76    }
77
78    /// Extracts the underlying [`SmallVec`] of ranges.
79    ///
80    /// [`SmallVec`]: `smallvec::SmallVec`
81    #[inline(always)]
82    pub fn into_inner(self) -> Backing<T> {
83        self.inner
84    }
85
86    /// Extracts the underlying vector of ranges.
87    #[inline(always)]
88    pub fn into_vec(self) -> Vec<(T, T)> {
89        self.inner.into_vec()
90    }
91
92    /// Returns an iterator for the underlying normalized ranges.
93    #[inline(always)]
94    pub fn iter(
95        &self,
96    ) -> impl '_ + NormalizedRangeIter<Item = (T, T)> + DoubleEndedIterator + ExactSizeIterator
97    {
98        let iter = self.inner.iter().copied();
99        unsafe { NormalizedRangeIterWrapper::new_unchecked(iter) }
100    }
101
102    /// Determines whether these two [`RangeVec`]s represent the same
103    /// ranges.
104    ///
105    /// This operation takes constant space and time linear in the
106    /// shortest of the two inputs.
107    pub fn eqv(&self, other: &RangeVec<T>) -> bool {
108        self.iter().eqv(other.iter())
109    }
110}
111
112impl<T: Endpoint> Default for RangeVec<T> {
113    fn default() -> Self {
114        RangeVec::new()
115    }
116}
117
118impl<T: Endpoint> IntoIterator for RangeVec<T> {
119    type Item = (T, T);
120    type IntoIter = NormalizedRangeIterWrapper<<Backing<T> as IntoIterator>::IntoIter>;
121
122    #[inline(always)]
123    fn into_iter(self) -> Self::IntoIter {
124        let iter = self.inner.into_iter();
125        unsafe { NormalizedRangeIterWrapper::new_unchecked(iter) }
126    }
127}
128
129impl<'a, T: Endpoint> IntoIterator for &'a RangeVec<T> {
130    type Item = (T, T);
131    type IntoIter =
132        NormalizedRangeIterWrapper<core::iter::Copied<<&'a Backing<T> as IntoIterator>::IntoIter>>;
133
134    #[inline(always)]
135    fn into_iter(self) -> Self::IntoIter {
136        let iter = self.inner.iter().copied();
137        unsafe { NormalizedRangeIterWrapper::new_unchecked(iter) }
138    }
139}
140
141impl<T: Endpoint> core::ops::Deref for RangeVec<T> {
142    type Target = [(T, T)];
143
144    #[inline(always)]
145    fn deref(&self) -> &[(T, T)] {
146        <RangeVec<T>>::inner(self)
147    }
148}
149
150#[cfg_attr(coverage_nightly, coverage(off))]
151#[test]
152fn test_smoke() {
153    use smallvec::smallvec;
154
155    assert_eq!(RangeVec::<u8>::new(), Default::default());
156    assert_eq!(RangeVec::<u8>::new(), unsafe {
157        RangeVec::new_unchecked(smallvec![])
158    });
159    assert!(RangeVec::<u8>::new().is_empty());
160
161    let ranges = unsafe { RangeVec::new_unchecked(smallvec![(2u8, 4u8), (10u8, 20u8)]) };
162
163    assert_eq!(ranges[0], (2u8, 4u8));
164
165    assert_eq!(&ranges, &ranges.iter().collect_range_vec());
166
167    assert!(ranges.eqv(&ranges.iter().collect_range_vec()));
168    assert!(!ranges.eqv(&Default::default()));
169    assert!(!ranges.eqv(&unsafe { RangeVec::new_unchecked(smallvec![(2u8, 4u8), (11u8, 20u8)]) }));
170    assert!(!ranges.eqv(&unsafe {
171        RangeVec::new_unchecked(smallvec![(2u8, 4u8), (10u8, 20u8), (30u8, 30u8)])
172    }));
173    assert!(!ranges.eqv(&unsafe { RangeVec::new_unchecked(smallvec![(2u8, 4u8)]) }));
174
175    assert_eq!(ranges.inner(), &ranges.iter().collect::<Vec<_>>());
176
177    assert_eq!(ranges.inner(), &(&ranges).into_iter().collect::<Vec<_>>());
178    assert_eq!(
179        ranges.clone().into_vec(),
180        ranges.into_iter().collect::<Vec<_>>()
181    );
182}
closed_interval_set/range_vec.rs

closed_interval_set/
range_vec.rs
