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

closed_interval_set/
union.rs
