closed_interval_set/
union.rs

1use crate::Backing;
2use crate::ClosedRange;
3use crate::Endpoint;
4use crate::RangeCase;
5use crate::RangeVec;
6
7/// Computes the normalized union of `acc` and `src`.
8///
9/// There's no particularly smart way to do this (except maybe with a
10/// sorted merge, but hopefully the default [`slice::sort`] handles
11/// sorted runs): concatenate everything and normalize in place.
12///
13/// This operation reuses the storage from `acc` and takes
14/// \\(\mathcal{O}(n \log n)\\) time, where \\(n\\) is the total
15/// number of ranges in the two inputs.
16#[inline]
17#[must_use]
18pub fn union_vec<T: Endpoint>(
19    acc: impl Into<RangeCase<T>>,
20    src: impl IntoIterator<Item: ClosedRange<EndT = T>>,
21) -> RangeVec<T> {
22    fn doit<T: Endpoint>(
23        mut acc: Backing<T>,
24        src: impl Iterator<Item: ClosedRange<EndT = T>>,
25    ) -> RangeVec<T> {
26        acc.extend(src.map(|range| range.get()));
27        crate::normalize_vec(acc)
28    }
29
30    doit(acc.into().into_inner(), src.into_iter())
31}
32
33impl<T: Endpoint> RangeVec<T> {
34    /// Constructs the union of this [`RangeVec`] and any of a
35    /// [`RangeVec`], a [`SmallVec`], or a [`Vec`].
36    ///
37    /// This operation reuses the storage from `self` and takes
38    /// \\(\mathcal{O}(n \log n)\\) time, where \\(n\\) is the total
39    /// size of the two inputs. This is worse than the linear-time
40    /// [`RangeVec::union`], but the constant factors are pretty good.
41    ///
42    /// See [`union_vec`] for more general types.
43    ///
44    /// [`SmallVec`]: https://docs.rs/smallvec/latest/smallvec/struct.SmallVec.html
45    /// [`Vec`]: https://doc.rust-lang.org/std/vec/struct.Vec.html
46    #[inline(always)]
47    #[must_use]
48    pub fn into_union(self, other: impl Into<RangeCase<T>>) -> Self {
49        #[cfg(feature = "internal_checks")]
50        use crate::NormalizedRangeIter;
51
52        fn doit<T: Endpoint>(mut x: Backing<T>, mut y: Backing<T>) -> RangeVec<T> {
53            if y.len() > x.len() {
54                core::mem::swap(&mut x, &mut y);
55            }
56
57            // More efficient when the first argument is longer
58            debug_assert!(x.len() >= y.len());
59            union_vec(x, y)
60        }
61
62        let other = other.into().into_inner();
63
64        #[cfg(feature = "internal_checks")]
65        let expected = (
66            self.iter()
67                .union(RangeVec::from_smallvec(other.clone()))
68                .collect_range_vec(),
69            RangeVec::from_smallvec(other.clone())
70                .iter()
71                .union(self.iter())
72                .collect_range_vec(),
73        );
74
75        let ret = doit(self.into_inner(), other);
76
77        #[cfg(feature = "internal_checks")]
78        {
79            assert!(expected.0.eqv(&ret));
80            assert!(expected.1.eqv(&ret));
81        }
82
83        ret
84    }
85}
86
87#[cfg(test)]
88#[cfg_attr(coverage_nightly, coverage(off))]
89mod test {
90    use super::*;
91    use alloc::vec;
92    use alloc::vec::Vec;
93
94    #[test]
95    fn test_union_smoke() {
96        use crate::NormalizedRangeIter;
97
98        let acc = vec![(1u8, 4u8), (5u8, 1u8), (5u8, 10u8)];
99        let src = [(0u8, 2u8), (11u8, 15u8)];
100
101        assert_eq!(
102            crate::normalize_vec(acc.clone())
103                .into_union(src.to_vec())
104                .into_vec(),
105            vec![(0u8, 15u8)]
106        );
107
108        assert_eq!(
109            crate::normalize_vec(src.to_vec())
110                .union(crate::normalize_vec(vec![]))
111                .into_vec(),
112            src.to_vec()
113        );
114
115        let result = union_vec(acc, src);
116        assert_eq!(&*result, &vec![(0u8, 15u8)]);
117        assert_eq!(result.inner(), &vec![(0u8, 15u8)]);
118        assert_eq!(result.iter().collect::<Vec<_>>(), vec![(0u8, 15u8)]);
119        assert_eq!(
120            result.iter().collect_range_vec().into_vec(),
121            vec![(0u8, 15u8)]
122        );
123        assert_eq!(result.into_vec(), vec![(0u8, 15u8)]);
124    }
125
126    proptest::proptest! {
127        #[test]
128        fn test_union(xs: Vec<(u8, u8)>, ys: Vec<(u8, u8)>)
129        {
130            use crate::ranges_to_bits;
131
132            let bits = {
133                let mut all_ranges = xs.clone();
134                all_ranges.extend(&ys);
135                ranges_to_bits(&all_ranges)
136            };
137
138            // union_vec
139            {
140                let union = union_vec(xs.clone(), &ys);
141                assert_eq!(bits, ranges_to_bits(&union));
142            }
143
144            {
145                let union = union_vec(RangeVec::from_vec(xs.clone()), &ys);
146                assert_eq!(bits, ranges_to_bits(&union));
147            }
148
149            {
150                let union = union_vec(xs.clone(), RangeVec::from_vec(ys.clone()).iter());
151                assert_eq!(bits, ranges_to_bits(&union));
152            }
153
154            {
155                let union = union_vec(RangeVec::from_vec(xs.clone()), RangeVec::from_vec(ys.clone()).iter());
156                assert_eq!(bits, ranges_to_bits(&union));
157            }
158
159            // union
160            {
161                let union = RangeVec::from_vec(xs.clone()).into_union(ys.clone());
162                assert_eq!(bits, ranges_to_bits(&union));
163            }
164
165            {
166                let union = RangeVec::from_vec(ys.clone()).union(RangeVec::from_vec(xs.clone()));
167                assert_eq!(bits, ranges_to_bits(&union));
168            }
169        }
170    }
171}
closed_interval_set/union.rs

closed_interval_set/
union.rs
