provenant/license_detection/models/
position_span.rs

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

provenant/license_detection/models/
position_span.rs
