covguard_ranges/
lib.rs

1//! Range merging utilities for covguard.
2
3use std::ops::RangeInclusive;
4
5/// Merge overlapping or adjacent ranges into a minimal set.
6///
7/// Input ranges do not need to be sorted; output will be sorted and
8/// contain no overlapping or adjacent ranges.
9///
10/// # Examples
11///
12/// ```
13/// use covguard_ranges::merge_ranges;
14///
15/// // These ranges are all adjacent/overlapping: 1..=4 (from 1..=3, 2..=4),
16/// // then 5..=7 is adjacent to 1..=4, and 8..=10 is adjacent to 5..=7,
17/// // so everything merges into one range.
18/// let ranges = vec![1..=3, 5..=7, 2..=4, 8..=10];
19/// let merged = merge_ranges(ranges);
20/// assert_eq!(merged, vec![1..=10]);
21///
22/// // Non-adjacent ranges stay separate
23/// let ranges = vec![1..=3, 10..=15];
24/// let merged = merge_ranges(ranges);
25/// assert_eq!(merged, vec![1..=3, 10..=15]);
26/// ```
27pub fn merge_ranges(mut ranges: Vec<RangeInclusive<u32>>) -> Vec<RangeInclusive<u32>> {
28    if ranges.is_empty() {
29        return Vec::new();
30    }
31
32    // Sort by start, then by end
33    ranges.sort_by(|a, b| a.start().cmp(b.start()).then(a.end().cmp(b.end())));
34
35    let mut merged: Vec<RangeInclusive<u32>> = Vec::with_capacity(ranges.len());
36
37    for range in ranges {
38        if let Some(last) = merged.last_mut() {
39            // Check if ranges overlap or are adjacent
40            // Adjacent: last.end + 1 == range.start
41            // Overlapping: range.start <= last.end
42            if *range.start() <= last.end().saturating_add(1) {
43                // Extend the last range if needed
44                if *range.end() > *last.end() {
45                    *last = *last.start()..=*range.end();
46                }
47            } else {
48                merged.push(range);
49            }
50        } else {
51            merged.push(range);
52        }
53    }
54
55    merged
56}
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_merge_ranges_empty() {
64        let result = merge_ranges(vec![]);
65        assert!(result.is_empty());
66    }
67
68    #[test]
69    fn test_merge_ranges_single() {
70        let result = merge_ranges(vec![1..=5]);
71        assert_eq!(result, vec![1..=5]);
72    }
73
74    #[test]
75    fn test_merge_ranges_non_overlapping() {
76        let result = merge_ranges(vec![1..=3, 7..=10]);
77        assert_eq!(result, vec![1..=3, 7..=10]);
78    }
79
80    #[test]
81    fn test_merge_ranges_overlapping() {
82        let result = merge_ranges(vec![1..=5, 3..=8]);
83        assert_eq!(result, vec![1..=8]);
84    }
85
86    #[test]
87    fn test_merge_ranges_adjacent() {
88        let result = merge_ranges(vec![1..=3, 4..=6]);
89        assert_eq!(result, vec![1..=6]);
90    }
91
92    #[test]
93    fn test_merge_ranges_unsorted() {
94        // After sorting and merging: 1..=3, 2..=4 -> 1..=4
95        // 5..=7, 8..=10 are adjacent (7+1=8), so merge to 5..=10
96        // 1..=4 and 5..=10 are adjacent (4+1=5), so merge to 1..=10
97        let result = merge_ranges(vec![5..=7, 1..=3, 2..=4, 8..=10]);
98        assert_eq!(result, vec![1..=10]);
99    }
100
101    #[test]
102    fn test_merge_ranges_contained() {
103        let result = merge_ranges(vec![1..=10, 3..=5]);
104        assert_eq!(result, vec![1..=10]);
105    }
106}
107
108// ============================================================================
109// Property Tests
110// ============================================================================
111
112#[cfg(test)]
113mod proptests {
114    use super::*;
115    use proptest::prelude::*;
116
117    proptest! {
118        #[test]
119        fn merge_ranges_produces_sorted_output(ranges in prop::collection::vec(1u32..1000, 0..50)) {
120            let input: Vec<RangeInclusive<u32>> = ranges.iter().map(|&x| x..=x).collect();
121            let merged = merge_ranges(input);
122
123            // Check sorted
124            for window in merged.windows(2) {
125                prop_assert!(window[0].end() < window[1].start());
126            }
127        }
128
129        #[test]
130        fn merge_ranges_produces_non_overlapping_output(ranges in prop::collection::vec((1u32..500, 1u32..500), 0..30)) {
131            let input: Vec<RangeInclusive<u32>> = ranges
132                .into_iter()
133                .map(|(start, len)| start..=(start + len))
134                .collect();
135            let merged = merge_ranges(input);
136
137            // Check non-overlapping and non-adjacent
138            for window in merged.windows(2) {
139                let gap = *window[1].start() as i64 - *window[0].end() as i64;
140                prop_assert!(gap >= 2, "Ranges should not be adjacent or overlapping: gap={}", gap);
141            }
142        }
143
144        #[test]
145        fn merge_ranges_is_idempotent(ranges in prop::collection::vec((1u32..500, 1u32..100), 0..20)) {
146            let input: Vec<RangeInclusive<u32>> = ranges
147                .into_iter()
148                .map(|(start, len)| start..=(start + len))
149                .collect();
150
151            let merged_once = merge_ranges(input.clone());
152            let merged_twice = merge_ranges(merged_once.clone());
153
154            prop_assert_eq!(merged_once, merged_twice, "merge_ranges should be idempotent");
155        }
156
157        #[test]
158        fn merge_ranges_preserves_all_values(values in prop::collection::vec(1u32..1000, 1..50)) {
159            let input: Vec<RangeInclusive<u32>> = values.iter().map(|&x| x..=x).collect();
160            let merged = merge_ranges(input);
161
162            // Every input value should be contained in some output range
163            for val in &values {
164                let contained = merged.iter().any(|r| r.contains(val));
165                prop_assert!(contained, "Value {} should be in merged ranges", val);
166            }
167        }
168    }
169}
covguard_ranges/lib.rs

covguard_ranges/
lib.rs
