int_interval_set/isize.rs
1// -----------------------------------------------------------------------------
2// This file is generated by `cargo run -p codegen -- --signed`.
3// Do not edit manually.
4// -----------------------------------------------------------------------------
5
6#[cfg(test)]
7mod tests;
8
9use std::sync::Arc;
10
11use int_interval::IsizeCO;
12
13/// Read-only canonical interval set for `IsizeCO`.
14///
15/// A `IsizeCOSet` stores a normalized collection of half-open `IsizeCO` intervals:
16///
17/// - intervals are sorted by `start`;
18/// - intervals are non-overlapping;
19/// - adjacent intervals are merged;
20/// - all queries are performed against the sealed immutable array.
21///
22/// Construction is intentionally restricted. Use `IsizeCOSetBuilder` for normal
23/// construction.
24pub mod set {
25 use super::*;
26
27 /// Immutable canonical interval set.
28 ///
29 /// Internally this is an `Arc<[IsizeCO]>`, so cloning a `IsizeCOSet` is cheap.
30 ///
31 /// Canonical invariant:
32 ///
33 /// ```text
34 /// for every adjacent pair a, b:
35 /// a.end_excl() < b.start()
36 /// ```
37 ///
38 /// The strict `<` means both overlap and adjacency have already been merged.
39 #[repr(transparent)]
40 #[derive(Clone, Debug, Eq, PartialEq)]
41 pub struct IsizeCOSet {
42 intervals: Arc<[IsizeCO]>,
43 }
44
45 // ------------------------------------------------------------
46 // basic api: construction / accessors
47 // ------------------------------------------------------------
48
49 mod basic {
50 use super::*;
51
52 impl IsizeCOSet {
53 /// Builds a set from an already canonical interval vector.
54 ///
55 /// # Safety
56 ///
57 /// The caller must guarantee that `intervals` is canonical:
58 ///
59 /// - intervals are sorted by ascending `start`;
60 /// - intervals are non-overlapping;
61 /// - contiguous intervals have already been merged;
62 /// - therefore, for every adjacent pair `a, b`,
63 /// `a.end_excl() < b.start()` holds.
64 ///
65 /// Violating this invariant can make binary-search based queries
66 /// return incorrect results.
67 #[inline]
68 pub(in crate::isize) unsafe fn new_unchecked(intervals: Vec<IsizeCO>) -> Self {
69 debug_assert!(Self::is_canonical(&intervals));
70
71 Self {
72 intervals: Arc::from(intervals.into_boxed_slice()),
73 }
74 }
75
76 /// Checks the canonical invariant used by binary-search queries.
77 ///
78 /// `IsizeCO` itself already guarantees single-interval validity. This
79 /// function only checks the relationship between adjacent intervals.
80 #[inline]
81 fn is_canonical(intervals: &[IsizeCO]) -> bool {
82 intervals.windows(2).all(|w| w[0].end_excl() < w[1].start())
83 }
84 }
85
86 impl IsizeCOSet {
87 /// Returns the number of canonical intervals.
88 ///
89 /// For the `IsizeCO` domain, the maximum canonical interval count is 128,
90 /// e.g. alternating single-point intervals across `[isize::MIN, isize::MAX)`.
91 #[inline]
92 pub fn interval_count(&self) -> usize {
93 self.intervals.len() as usize
94 }
95
96 /// Returns whether the set contains no intervals.
97 #[inline]
98 pub fn is_empty(&self) -> bool {
99 self.intervals.is_empty()
100 }
101
102 /// Returns the canonical interval slice.
103 ///
104 /// The returned slice is sorted, non-overlapping, and contains no
105 /// adjacent intervals.
106 #[inline]
107 pub fn as_slice(&self) -> &[IsizeCO] {
108 &self.intervals
109 }
110
111 /// Iterates over canonical intervals by value.
112 #[inline]
113 pub fn iter_intervals(&self) -> impl Iterator<Item = IsizeCO> {
114 self.intervals.iter().copied()
115 }
116 }
117 }
118
119 // ------------------------------------------------------------
120 // predicate api: yes/no queries
121 // ------------------------------------------------------------
122
123 mod predicates {
124 use super::*;
125
126 impl IsizeCOSet {
127 /// Returns whether `x` is covered by any interval in the set.
128 ///
129 /// Complexity: `O(log n)`.
130 #[inline]
131 pub fn contains_point(&self, x: isize) -> bool {
132 let i = self.intervals.partition_point(|iv| iv.start() <= x);
133 i != 0 && self.intervals[i - 1].contains(x)
134 }
135
136 /// Returns whether `query` is fully contained by one interval.
137 ///
138 /// Since the set is canonical, a contained query interval can only
139 /// be contained by the interval immediately preceding or starting
140 /// at `query.start()`.
141 ///
142 /// Complexity: `O(log n)`.
143 #[inline]
144 pub fn contains_interval(&self, query: IsizeCO) -> bool {
145 let i = self
146 .intervals
147 .partition_point(|iv| iv.start() <= query.start());
148
149 i != 0 && self.intervals[i - 1].contains_interval(query)
150 }
151
152 /// Returns whether `query` intersects any interval in the set.
153 ///
154 /// Complexity: `O(log n)`.
155 #[inline]
156 pub fn intersects_interval(&self, query: IsizeCO) -> bool {
157 let i = self
158 .intervals
159 .partition_point(|iv| iv.end_excl() <= query.start());
160
161 self.intervals.get(i).is_some_and(|iv| iv.intersects(query))
162 }
163 }
164 }
165
166 // ------------------------------------------------------------
167 // search api: returning matched intervals
168 // ------------------------------------------------------------
169
170 mod search {
171 use super::*;
172
173 /// Point-based search APIs.
174 mod point {
175 use super::*;
176
177 impl IsizeCOSet {
178 /// Returns the unique interval containing `x`, if any.
179 ///
180 /// Because the set is canonical, at most one interval can
181 /// contain a single point.
182 ///
183 /// Complexity: `O(log n)`.
184 #[inline]
185 pub fn interval_containing_point(&self, x: isize) -> Option<IsizeCO> {
186 let i = self.intervals.partition_point(|iv| iv.start() <= x);
187
188 if i == 0 {
189 return None;
190 }
191
192 let iv = self.intervals[i - 1];
193 iv.contains(x).then_some(iv)
194 }
195 }
196 }
197
198 /// Interval-based search APIs.
199 mod interval {
200 use super::*;
201
202 impl IsizeCOSet {
203 /// Iterates over all canonical intervals intersecting `query`.
204 ///
205 /// The iterator yields original intervals stored in the set,
206 /// not clipped intersection segments.
207 ///
208 /// Complexity: `O(log n + k)`, where `k` is the number of
209 /// returned intervals.
210 #[inline]
211 pub fn intervals_intersecting(&self, query: IsizeCO) -> impl Iterator<Item = IsizeCO> {
212 let i = self
213 .intervals
214 .partition_point(|iv| iv.end_excl() <= query.start());
215
216 self.intervals[i..]
217 .iter()
218 .copied()
219 .take_while(move |iv| iv.start() < query.end_excl())
220 }
221
222 /// Iterates over clipped intersection segments with `query`.
223 ///
224 /// Example:
225 ///
226 /// ```text
227 /// set: [10, 20), [30, 40)
228 /// query: [15, 35)
229 /// out: [15, 20), [30, 35)
230 /// ```
231 ///
232 /// Complexity: `O(log n + k)`, where `k` is the number of
233 /// intersecting intervals.
234 #[inline]
235 pub fn intersections(&self, query: IsizeCO) -> impl Iterator<Item = IsizeCO> {
236 self.intervals_intersecting(query)
237 .filter_map(move |iv| iv.intersection(query))
238 }
239 }
240 }
241 }
242
243 // ------------------------------------------------------------
244 // coverage api: covered length / uncovered length / ratio
245 // ------------------------------------------------------------
246
247 mod coverage {
248 use super::*;
249
250 impl IsizeCOSet {
251 /// Returns the covered length inside `query`.
252 ///
253 /// Since `IsizeCOSet` is canonical, all intersection segments are
254 /// disjoint, so summing their lengths is valid.
255 ///
256 /// The result is always `<= query.len()`.
257 #[inline]
258 pub fn covered_len(&self, query: IsizeCO) -> usize {
259 self.intersections(query).map(|iv| iv.len()).sum()
260 }
261
262 /// Returns the uncovered length inside `query`.
263 #[inline]
264 pub fn uncovered_len(&self, query: IsizeCO) -> usize {
265 query.len() - self.covered_len(query)
266 }
267
268 /// Returns `covered_len(query) / query.len()` as `f32`.
269 ///
270 /// `query.len()` is non-zero because `IsizeCO` cannot represent an
271 /// empty interval.
272 #[inline]
273 pub fn coverage_ratio(&self, query: IsizeCO) -> f32 {
274 self.covered_len(query) as f32 / query.len() as f32
275 }
276 }
277 }
278}
279
280/// Concurrent builder for `IsizeCOSet`.
281///
282/// The builder accepts concurrent inserts into a skip list. During `seal`,
283/// raw intervals are scanned in sorted order and merged into a canonical
284/// immutable `IsizeCOSet`.
285pub mod builder {
286 use std::cmp::Ordering;
287
288 use crossbeam_skiplist::SkipSet;
289
290 use super::set::IsizeCOSet;
291 use super::*;
292
293 /// Private ordering key for storing `IsizeCO` inside `SkipSet`.
294 ///
295 /// `IsizeCO` does not need to implement `Ord` in its own crate. This wrapper
296 /// defines the ordering locally:
297 ///
298 /// ```text
299 /// (start, end_excl)
300 /// ```
301 ///
302 /// Because this is a set key, duplicate identical intervals are naturally
303 /// deduplicated during the build phase. That is correct for interval-set
304 /// semantics.
305 #[repr(transparent)]
306 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
307 struct Key(IsizeCO);
308
309 impl Ord for Key {
310 #[inline]
311 fn cmp(&self, other: &Self) -> Ordering {
312 self.0
313 .start()
314 .cmp(&other.0.start())
315 .then_with(|| self.0.end_excl().cmp(&other.0.end_excl()))
316 }
317 }
318
319 impl PartialOrd for Key {
320 #[inline]
321 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
322 Some(self.cmp(other))
323 }
324 }
325
326 /// Concurrent write-side builder for `IsizeCOSet`.
327 ///
328 /// Insertions are expected `O(log n)` through `crossbeam_skiplist`.
329 /// No merging is performed during insertion; normalization happens once
330 /// in `seal`.
331 #[repr(transparent)]
332 #[derive(Debug, Default)]
333 pub struct IsizeCOSetBuilder {
334 raw: SkipSet<Key>,
335 }
336
337 impl IsizeCOSetBuilder {
338 /// Creates an empty builder.
339 #[inline]
340 pub fn new() -> Self {
341 Self::default()
342 }
343
344 /// Inserts one interval into the builder.
345 ///
346 /// This method is safe to call concurrently through shared references.
347 /// Identical intervals are deduplicated by the underlying `SkipSet`.
348 #[inline]
349 pub fn insert(&self, iv: IsizeCO) {
350 self.raw.insert(Key(iv));
351 }
352
353 /// Consumes the builder and returns a canonical immutable set.
354 ///
355 /// The merge process is linear over the sorted skip-list iterator:
356 ///
357 /// - maintain one pending interval `cur`;
358 /// - if the next interval overlaps or is adjacent, replace `cur` with
359 /// its convex hull;
360 /// - otherwise, push `cur` and start a new pending interval;
361 /// - finally, push the last pending interval.
362 pub fn seal(self) -> IsizeCOSet {
363 let mut iter = self.raw.iter().map(|entry| entry.value().0);
364
365 let Some(mut cur) = iter.next() else {
366 // SAFETY:
367 // The empty interval list is canonical.
368 return unsafe { IsizeCOSet::new_unchecked(Vec::new()) };
369 };
370
371 let mut out = Vec::new();
372
373 for iv in iter {
374 if cur.is_contiguous_with(iv) {
375 cur = cur.convex_hull(iv);
376 } else {
377 out.push(cur);
378 cur = iv;
379 }
380 }
381
382 out.push(cur);
383
384 // SAFETY:
385 // `self.raw` iterates keys in ascending `(start, end_excl)` order.
386 // The loop maintains one pending merged interval `cur`.
387 //
388 // If `iv` is contiguous with or overlaps `cur`, both are replaced
389 // by their convex hull, so no overlap or adjacency is emitted.
390 //
391 // If `iv` is disjoint from `cur`, then sorted order plus the failed
392 // contiguity test imply `cur.end_excl() < iv.start()`. Pushing
393 // `cur` therefore preserves the canonical invariant.
394 //
395 // After the loop, the final pending interval is pushed. Therefore
396 // `out` is sorted, non-overlapping, and contains no adjacent
397 // intervals.
398 unsafe { IsizeCOSet::new_unchecked(out) }
399 }
400 }
401}