provenant/license_detection/models/
position_span.rs

1// SPDX-FileCopyrightText: Provenant contributors
2// SPDX-License-Identifier: Apache-2.0
3
4//! Position span types for license detection.
5
6use crate::license_detection::position_set::PositionSet;
7
8pub enum SpanIter<'a> {
9    Range(std::ops::Range<usize>),
10    Slice(std::iter::Copied<std::slice::Iter<'a, usize>>),
11}
12
13impl<'a> Iterator for SpanIter<'a> {
14    type Item = usize;
15
16    fn next(&mut self) -> Option<Self::Item> {
17        match self {
18            SpanIter::Range(range) => range.next(),
19            SpanIter::Slice(iter) => iter.next(),
20        }
21    }
22
23    fn size_hint(&self) -> (usize, Option<usize>) {
24        match self {
25            SpanIter::Range(range) => range.size_hint(),
26            SpanIter::Slice(iter) => iter.size_hint(),
27        }
28    }
29}
30
31#[derive(Debug, Clone)]
32pub enum PositionSpan {
33    Range { start: usize, end: usize },
34    Discrete(Vec<usize>),
35}
36
37impl PartialEq for PositionSpan {
38    /// Compare two PositionSpans for semantic equality.
39    ///
40    /// Returns true if both spans contain exactly the same positions,
41    /// regardless of representation (Range vs Discrete).
42    ///
43    /// Performance:
44    /// - Range vs Range: O(1)
45    /// - Discrete vs Discrete: O(n)
46    /// - Range vs Discrete: O(n) with early exit on length mismatch
47    fn eq(&self, other: &Self) -> bool {
48        match (self, other) {
49            (
50                PositionSpan::Range { start: s1, end: e1 },
51                PositionSpan::Range { start: s2, end: e2 },
52            ) => s1 == s2 && e1 == e2,
53            (PositionSpan::Discrete(p1), PositionSpan::Discrete(p2)) => p1 == p2,
54            (PositionSpan::Range { start, end }, PositionSpan::Discrete(positions)) => {
55                let range_len = end.saturating_sub(*start);
56                if range_len != positions.len() {
57                    return false;
58                }
59                if positions.is_empty() {
60                    return true;
61                }
62                positions.iter().all(|&p| *start <= p && p < *end)
63            }
64            (PositionSpan::Discrete(_), PositionSpan::Range { .. }) => other == self,
65        }
66    }
67}
68
69impl PositionSpan {
70    pub fn range(start: usize, end: usize) -> Self {
71        Self::Range { start, end }
72    }
73
74    pub fn new(start: usize, end: usize) -> Self {
75        Self::range(start, end)
76    }
77
78    pub fn from_positions(positions: impl IntoIterator<Item = usize>) -> Self {
79        let mut iter = positions.into_iter();
80        let Some(first) = iter.next() else {
81            return Self::empty();
82        };
83
84        let mut positions = vec![first];
85        positions.extend(iter);
86
87        if positions.len() == 1 {
88            return Self::Range {
89                start: positions[0],
90                end: positions[0] + 1,
91            };
92        }
93
94        positions.sort_unstable();
95        positions.dedup();
96
97        let is_contiguous = positions.windows(2).all(|w| w[1] == w[0] + 1);
98
99        if is_contiguous {
100            Self::Range {
101                start: positions[0],
102                end: positions[positions.len() - 1] + 1,
103            }
104        } else {
105            Self::Discrete(positions)
106        }
107    }
108
109    pub fn empty() -> Self {
110        Self::Range { start: 0, end: 0 }
111    }
112
113    pub fn iter(&self) -> SpanIter<'_> {
114        match self {
115            PositionSpan::Range { start, end } => SpanIter::Range(*start..*end),
116            PositionSpan::Discrete(positions) => SpanIter::Slice(positions.iter().copied()),
117        }
118    }
119
120    pub fn len(&self) -> usize {
121        match self {
122            PositionSpan::Range { start, end } => end.saturating_sub(*start),
123            PositionSpan::Discrete(positions) => positions.len(),
124        }
125    }
126
127    pub fn is_empty(&self) -> bool {
128        self.len() == 0
129    }
130
131    pub fn bounds(&self) -> (usize, usize) {
132        match self {
133            PositionSpan::Range { start, end } => (*start, *end),
134            PositionSpan::Discrete(positions) => {
135                if positions.is_empty() {
136                    return (0, 0);
137                }
138                let min = positions.iter().copied().min().unwrap_or(0);
139                let max = positions.iter().copied().max().unwrap_or(0);
140                (min, max + 1)
141            }
142        }
143    }
144
145    pub fn contains(&self, pos: usize) -> bool {
146        match self {
147            PositionSpan::Range { start, end } => *start <= pos && pos < *end,
148            PositionSpan::Discrete(positions) => positions.binary_search(&pos).is_ok(),
149        }
150    }
151
152    pub fn overlaps_set(&self, set: &PositionSet) -> bool {
153        let (my_min, my_max) = self.bounds();
154        if self.is_empty() {
155            return false;
156        }
157        if !set.may_overlap_range(my_min, my_max) {
158            return false;
159        }
160        self.iter().any(|p| set.contains(p))
161    }
162
163    pub fn to_position_set(&self) -> PositionSet {
164        match self {
165            PositionSpan::Range { start, end } => (*start..*end).collect(),
166            PositionSpan::Discrete(positions) => positions.iter().copied().collect(),
167        }
168    }
169
170    pub fn to_vec(&self) -> Vec<usize> {
171        match self {
172            PositionSpan::Range { start, end } => (*start..*end).collect(),
173            PositionSpan::Discrete(positions) => positions.clone(),
174        }
175    }
176
177    /// Returns true if the positions form a contiguous range with no gaps.
178    /// This is always true for `Range` variants, and checks adjacency for `Discrete`.
179    pub fn is_contiguous(&self) -> bool {
180        match self {
181            PositionSpan::Range { .. } => true,
182            PositionSpan::Discrete(positions) => {
183                if positions.len() <= 1 {
184                    return true;
185                }
186                positions.windows(2).all(|w| w[1] == w[0] + 1)
187            }
188        }
189    }
190}
191
192#[cfg(test)]
193mod tests {
194    use super::*;
195
196    #[test]
197    fn test_range_creation() {
198        let span = PositionSpan::range(5, 10);
199        assert_eq!(span.len(), 5);
200        assert!(!span.is_empty());
201        assert_eq!(span.bounds(), (5, 10));
202        assert!(span.is_contiguous());
203    }
204
205    #[test]
206    fn test_new_backwards_compatible() {
207        let span = PositionSpan::new(3, 7);
208        assert_eq!(span.len(), 4);
209        assert_eq!(span.to_vec(), vec![3, 4, 5, 6]);
210    }
211
212    #[test]
213    fn test_empty() {
214        let span = PositionSpan::empty();
215        assert_eq!(span.len(), 0);
216        assert!(span.is_empty());
217        assert_eq!(span.bounds(), (0, 0));
218    }
219
220    #[test]
221    fn test_from_positions_empty() {
222        let span = PositionSpan::from_positions(vec![]);
223        assert!(span.is_empty());
224    }
225
226    #[test]
227    fn test_from_positions_single() {
228        let span = PositionSpan::from_positions(vec![5]);
229        assert_eq!(span.len(), 1);
230        assert!(span.is_contiguous());
231        assert!(span.contains(5));
232    }
233
234    #[test]
235    fn test_from_positions_contiguous() {
236        let span = PositionSpan::from_positions(vec![3, 4, 5]);
237        assert!(span.is_contiguous());
238        assert_eq!(span.len(), 3);
239        assert_eq!(span.bounds(), (3, 6));
240    }
241
242    #[test]
243    fn test_from_positions_non_contiguous() {
244        let span = PositionSpan::from_positions(vec![1, 3, 5]);
245        assert!(!span.is_contiguous());
246        assert_eq!(span.len(), 3);
247        assert_eq!(span.bounds(), (1, 6));
248    }
249
250    #[test]
251    fn test_from_positions_unsorted_with_duplicates() {
252        let span = PositionSpan::from_positions(vec![5, 3, 4, 3, 5]);
253        assert!(span.is_contiguous());
254        assert_eq!(span.to_vec(), vec![3, 4, 5]);
255    }
256
257    #[test]
258    fn test_contains_range() {
259        let span = PositionSpan::range(5, 10);
260        assert!(!span.contains(4));
261        assert!(span.contains(5));
262        assert!(span.contains(7));
263        assert!(span.contains(9));
264        assert!(!span.contains(10));
265    }
266
267    #[test]
268    fn test_contains_discrete() {
269        let span = PositionSpan::from_positions(vec![1, 3, 5]);
270        assert!(span.contains(1));
271        assert!(!span.contains(2));
272        assert!(span.contains(3));
273        assert!(!span.contains(4));
274        assert!(span.contains(5));
275    }
276
277    #[test]
278    fn test_iter_range() {
279        let span = PositionSpan::range(2, 5);
280        let positions: Vec<_> = span.iter().collect();
281        assert_eq!(positions, vec![2, 3, 4]);
282    }
283
284    #[test]
285    fn test_iter_discrete() {
286        let span = PositionSpan::from_positions(vec![1, 3, 5]);
287        let positions: Vec<_> = span.iter().collect();
288        assert_eq!(positions, vec![1, 3, 5]);
289    }
290
291    #[test]
292    fn test_to_vec_range() {
293        let span = PositionSpan::range(1, 4);
294        assert_eq!(span.to_vec(), vec![1, 2, 3]);
295    }
296
297    #[test]
298    fn test_to_vec_discrete() {
299        let span = PositionSpan::from_positions(vec![2, 4, 6]);
300        assert_eq!(span.to_vec(), vec![2, 4, 6]);
301    }
302
303    #[test]
304    fn test_to_position_set() {
305        let span = PositionSpan::range(1, 4);
306        let set = span.to_position_set();
307        assert_eq!(set.len(), 3);
308        assert!(set.contains(1));
309        assert!(set.contains(2));
310        assert!(set.contains(3));
311    }
312
313    #[test]
314    fn test_is_contiguous_discrete_single() {
315        let span = PositionSpan::from_positions(vec![5]);
316        assert!(span.is_contiguous());
317    }
318
319    #[test]
320    fn test_is_contiguous_discrete_gap() {
321        let span = PositionSpan::from_positions(vec![1, 2, 4]);
322        assert!(!span.is_contiguous());
323    }
324
325    // ============================================================
326    // Comprehensive equality tests: all 2x2 combinations
327    // ============================================================
328
329    // ---- Range vs Range ----
330
331    #[test]
332    fn test_eq_range_range_both_empty() {
333        let a = PositionSpan::range(0, 0);
334        let b = PositionSpan::range(0, 0);
335        assert_eq!(a, b);
336    }
337
338    #[test]
339    fn test_eq_range_range_one_empty() {
340        let a = PositionSpan::range(0, 0);
341        let b = PositionSpan::range(0, 3);
342        assert_ne!(a, b);
343    }
344
345    #[test]
346    fn test_eq_range_range_equal() {
347        let a = PositionSpan::range(2, 5);
348        let b = PositionSpan::range(2, 5);
349        assert_eq!(a, b);
350    }
351
352    #[test]
353    fn test_eq_range_range_disjoint() {
354        let a = PositionSpan::range(0, 3);
355        let b = PositionSpan::range(5, 8);
356        assert_ne!(a, b);
357    }
358
359    #[test]
360    fn test_eq_range_range_overlapping() {
361        let a = PositionSpan::range(0, 5);
362        let b = PositionSpan::range(3, 8);
363        assert_ne!(a, b);
364    }
365
366    // ---- Discrete vs Discrete ----
367
368    #[test]
369    fn test_eq_discrete_discrete_both_empty() {
370        let a = PositionSpan::Discrete(vec![]);
371        let b = PositionSpan::Discrete(vec![]);
372        assert_eq!(a, b);
373    }
374
375    #[test]
376    fn test_eq_discrete_discrete_one_empty() {
377        let a = PositionSpan::Discrete(vec![]);
378        let b = PositionSpan::Discrete(vec![0, 1, 2]);
379        assert_ne!(a, b);
380    }
381
382    #[test]
383    fn test_eq_discrete_discrete_equal() {
384        let a = PositionSpan::Discrete(vec![0, 1, 2]);
385        let b = PositionSpan::Discrete(vec![0, 1, 2]);
386        assert_eq!(a, b);
387    }
388
389    #[test]
390    fn test_eq_discrete_discrete_disjoint() {
391        let a = PositionSpan::Discrete(vec![0, 1, 2]);
392        let b = PositionSpan::Discrete(vec![5, 6, 7]);
393        assert_ne!(a, b);
394    }
395
396    #[test]
397    fn test_eq_discrete_discrete_overlapping() {
398        let a = PositionSpan::Discrete(vec![0, 1, 2, 3]);
399        let b = PositionSpan::Discrete(vec![2, 3, 4, 5]);
400        assert_ne!(a, b);
401    }
402
403    // ---- Range vs Discrete ----
404
405    #[test]
406    fn test_eq_range_discrete_both_empty() {
407        let range = PositionSpan::range(0, 0);
408        let discrete = PositionSpan::Discrete(vec![]);
409        assert_eq!(range, discrete);
410        assert_eq!(discrete, range);
411    }
412
413    #[test]
414    fn test_eq_range_discrete_range_empty() {
415        let range = PositionSpan::range(0, 0);
416        let discrete = PositionSpan::Discrete(vec![0, 1, 2]);
417        assert_ne!(range, discrete);
418        assert_ne!(discrete, range);
419    }
420
421    #[test]
422    fn test_eq_range_discrete_discrete_empty() {
423        let range = PositionSpan::range(0, 3);
424        let discrete = PositionSpan::Discrete(vec![]);
425        assert_ne!(range, discrete);
426        assert_ne!(discrete, range);
427    }
428
429    #[test]
430    fn test_eq_range_discrete_equal() {
431        let range = PositionSpan::range(2, 5);
432        let discrete = PositionSpan::Discrete(vec![2, 3, 4]);
433        assert_eq!(range, discrete);
434        assert_eq!(discrete, range);
435    }
436
437    #[test]
438    fn test_eq_range_discrete_disjoint() {
439        let range = PositionSpan::range(0, 3);
440        let discrete = PositionSpan::Discrete(vec![5, 6, 7]);
441        assert_ne!(range, discrete);
442        assert_ne!(discrete, range);
443    }
444
445    #[test]
446    fn test_eq_range_discrete_overlapping_partial() {
447        let range = PositionSpan::range(0, 5);
448        let discrete = PositionSpan::Discrete(vec![2, 3, 4, 5, 6]);
449        assert_ne!(range, discrete);
450        assert_ne!(discrete, range);
451    }
452
453    #[test]
454    fn test_eq_range_discrete_subset() {
455        // Discrete is subset of range
456        let range = PositionSpan::range(0, 10);
457        let discrete = PositionSpan::Discrete(vec![2, 3, 4]);
458        assert_ne!(range, discrete);
459        assert_ne!(discrete, range);
460    }
461
462    #[test]
463    fn test_eq_range_discrete_superset() {
464        // Discrete extends beyond range
465        let range = PositionSpan::range(5, 10);
466        let discrete = PositionSpan::Discrete(vec![3, 4, 5, 6, 7]);
467        assert_ne!(range, discrete);
468        assert_ne!(discrete, range);
469    }
470
471    // ---- Mixed empty tests ----
472
473    #[test]
474    fn test_eq_empty_different_representation() {
475        let a = PositionSpan::range(0, 0);
476        let b = PositionSpan::Discrete(vec![]);
477        assert_eq!(a, b);
478        assert_eq!(b, a);
479    }
480}
provenant/license_detection/models/position_span.rs

provenant/license_detection/models/
position_span.rs
