metrale_grammar/support/
int_set.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// Integer-set utilities — port of `cpp/support/int_set.h`.
4//
5// Both operations assume their inputs are sorted ascending and treat
6// the vectors as mathematical sets. They mutate `lhs` in place,
7// matching the C++ `IntsetUnion` / `IntsetIntersection` signatures.
8
9/// Replace `lhs` with the sorted union of `lhs` and `rhs`.
10///
11/// Both inputs must already be sorted ascending; duplicates within an
12/// input are collapsed in the result. Runs in `O(n + m)`.
13pub fn intset_union(lhs: &mut Vec<i32>, rhs: &[i32]) {
14    // Merge two sorted slices, then dedup — equivalent in observable
15    // behavior to the C++ in-place reverse merge + std::unique.
16    let mut merged: Vec<i32> = Vec::with_capacity(lhs.len() + rhs.len());
17    let mut i = 0;
18    let mut j = 0;
19    while i < lhs.len() && j < rhs.len() {
20        match lhs[i].cmp(&rhs[j]) {
21            std::cmp::Ordering::Less => {
22                merged.push(lhs[i]);
23                i += 1;
24            }
25            std::cmp::Ordering::Greater => {
26                merged.push(rhs[j]);
27                j += 1;
28            }
29            std::cmp::Ordering::Equal => {
30                merged.push(lhs[i]);
31                i += 1;
32                j += 1;
33            }
34        }
35    }
36    merged.extend_from_slice(&lhs[i..]);
37    merged.extend_from_slice(&rhs[j..]);
38    merged.dedup();
39    *lhs = merged;
40}
41
42/// Replace `lhs` with the sorted intersection of `lhs` and `rhs`.
43///
44/// Both inputs must already be sorted ascending. As a special case,
45/// `lhs == [-1]` is treated as the universal set, so the result
46/// becomes `rhs`. Runs in `O(n + m)`.
47pub fn intset_intersection(lhs: &mut Vec<i32>, rhs: &[i32]) {
48    if lhs.len() == 1 && lhs[0] == -1 {
49        *lhs = rhs.to_vec();
50        return;
51    }
52
53    let mut write = 0;
54    let mut i = 0;
55    let mut j = 0;
56    while i < lhs.len() && j < rhs.len() {
57        match lhs[i].cmp(&rhs[j]) {
58            std::cmp::Ordering::Less => i += 1,
59            std::cmp::Ordering::Greater => j += 1,
60            std::cmp::Ordering::Equal => {
61                lhs[write] = lhs[i];
62                write += 1;
63                i += 1;
64                j += 1;
65            }
66        }
67    }
68    lhs.truncate(write);
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn union_disjoint() {
77        let mut lhs = vec![1, 3, 5];
78        intset_union(&mut lhs, &[2, 4, 6]);
79        assert_eq!(lhs, vec![1, 2, 3, 4, 5, 6]);
80    }
81
82    #[test]
83    fn union_overlapping() {
84        let mut lhs = vec![1, 2, 3];
85        intset_union(&mut lhs, &[2, 3, 4]);
86        assert_eq!(lhs, vec![1, 2, 3, 4]);
87    }
88
89    #[test]
90    fn union_with_empty() {
91        let mut lhs = vec![1, 2, 3];
92        intset_union(&mut lhs, &[]);
93        assert_eq!(lhs, vec![1, 2, 3]);
94
95        let mut empty: Vec<i32> = vec![];
96        intset_union(&mut empty, &[4, 5]);
97        assert_eq!(empty, vec![4, 5]);
98    }
99
100    #[test]
101    fn union_identical() {
102        let mut lhs = vec![1, 2, 3];
103        intset_union(&mut lhs, &[1, 2, 3]);
104        assert_eq!(lhs, vec![1, 2, 3]);
105    }
106
107    #[test]
108    fn union_dedups_input_duplicates() {
109        let mut lhs = vec![1, 1, 2];
110        intset_union(&mut lhs, &[2, 2, 3]);
111        assert_eq!(lhs, vec![1, 2, 3]);
112    }
113
114    #[test]
115    fn intersection_basic() {
116        let mut lhs = vec![1, 2, 3, 4];
117        intset_intersection(&mut lhs, &[2, 4, 6]);
118        assert_eq!(lhs, vec![2, 4]);
119    }
120
121    #[test]
122    fn intersection_disjoint() {
123        let mut lhs = vec![1, 3, 5];
124        intset_intersection(&mut lhs, &[2, 4, 6]);
125        assert_eq!(lhs, Vec::<i32>::new());
126    }
127
128    #[test]
129    fn intersection_universal_set() {
130        let mut lhs = vec![-1];
131        intset_intersection(&mut lhs, &[7, 8, 9]);
132        assert_eq!(lhs, vec![7, 8, 9]);
133    }
134
135    #[test]
136    fn intersection_with_empty() {
137        let mut lhs = vec![1, 2, 3];
138        intset_intersection(&mut lhs, &[]);
139        assert_eq!(lhs, Vec::<i32>::new());
140    }
141
142    #[test]
143    fn intersection_negative_one_not_universal_when_longer() {
144        // [-1, 2] is a real set, not the universal sentinel.
145        let mut lhs = vec![-1, 2];
146        intset_intersection(&mut lhs, &[-1, 5]);
147        assert_eq!(lhs, vec![-1]);
148    }
149}
metrale_grammar/support/int_set.rs

metrale_grammar/support/
int_set.rs
