int_interval_set/int_co_set/
impls_for_construction.rs

1use super::*;
2
3use rayon::iter::{FromParallelIterator, IntoParallelIterator, ParallelIterator};
4
5use crate::int_co_set::funcs_for_canonicalization::{is_canonical, merge, normalize};
6
7const BATCH_SIZE: usize = 128;
8
9impl<I: IntCO> IntCOSet<I> {
10    /// Builds a set from an already canonical interval vector.
11    ///
12    /// # Safety
13    ///
14    /// The caller must guarantee that `intervals` is canonical:
15    ///
16    /// - intervals are sorted by ascending `start`;
17    /// - intervals are non-overlapping;
18    /// - contiguous intervals have already been merged;
19    /// - therefore, for every adjacent pair `a, b`,
20    ///   `a.end_excl() < b.start()` holds.
21    ///
22    /// Violating this invariant can make binary-search based queries
23    /// return incorrect results.
24    #[inline]
25    pub(super) unsafe fn new_unchecked(intervals: Vec<I>) -> Self {
26        debug_assert!(is_canonical(&intervals));
27
28        Self {
29            intervals: Arc::from(intervals.into_boxed_slice()),
30        }
31    }
32}
33
34impl<I: IntCO> FromIterator<I> for IntCOSet<I> {
35    fn from_iter<T>(iter: T) -> Self
36    where
37        T: IntoIterator<Item = I>,
38    {
39        let mut batch = Vec::with_capacity(BATCH_SIZE);
40        let mut reduced = Vec::new();
41
42        for iv in iter {
43            batch.push(iv);
44
45            if batch.len() == BATCH_SIZE {
46                let run = normalize(std::mem::replace(
47                    &mut batch,
48                    Vec::with_capacity(BATCH_SIZE),
49                ));
50
51                reduced = merge(reduced, run);
52            }
53        }
54
55        if !batch.is_empty() {
56            reduced = merge(reduced, normalize(batch));
57        }
58
59        // SAFETY:
60        // Each normalized batch is canonical. `merge` preserves sorted,
61        // non-overlapping, and non-adjacent interval invariants.
62        unsafe { IntCOSet::new_unchecked(reduced) }
63    }
64}
65
66impl<I> FromParallelIterator<I> for IntCOSet<I>
67where
68    I: IntCO + Send,
69{
70    fn from_par_iter<T>(iter: T) -> Self
71    where
72        T: IntoParallelIterator<Item = I>,
73    {
74        let reduced = iter
75            .into_par_iter()
76            .fold(
77                || (Vec::with_capacity(BATCH_SIZE), Vec::<I>::new()),
78                |(mut batch, mut reduced), iv| {
79                    batch.push(iv);
80
81                    if batch.len() == BATCH_SIZE {
82                        let run = normalize(std::mem::replace(
83                            &mut batch,
84                            Vec::with_capacity(BATCH_SIZE),
85                        ));
86
87                        reduced = merge(reduced, run);
88                    }
89
90                    (batch, reduced)
91                },
92            )
93            .map(|(batch, reduced)| {
94                if batch.is_empty() {
95                    reduced
96                } else {
97                    merge(reduced, normalize(batch))
98                }
99            })
100            .reduce(Vec::new, merge);
101
102        // SAFETY:
103        // Every parallel fold result is canonical, and `merge` preserves the
104        // canonical interval invariant during reduction.
105        unsafe { IntCOSet::new_unchecked(reduced) }
106    }
107}
108
109#[cfg(test)]
110mod tests_for_from_iter;
111#[cfg(test)]
112mod tests_for_from_par_iter;
int_interval_set/int_co_set/impls_for_construction.rs

int_interval_set/int_co_set/
impls_for_construction.rs
