utils/
slice.rs

1//! Slice helpers.
2use std::cmp::Ordering;
3
4/// Merges a sorted deduped [`Vec`] in place with a sorted deduped slice.
5///
6/// This is equivalent to a set union on sorted data.
7///
8/// Both inputs **must** be sorted and contain no duplicates.
9///
10/// # Examples
11/// ```
12/// # use utils::slice::merge_sorted_deduped_in_place;
13/// let mut v = vec![1, 3, 5];
14/// merge_sorted_deduped_in_place(&mut v, &[2, 3, 4]);
15/// assert_eq!(v, [1, 2, 3, 4, 5]);
16///
17/// // Elements at start and end
18/// let mut v = vec![1, 2, 3, 4, 5];
19/// merge_sorted_deduped_in_place(&mut v, &[0, 6]);
20/// assert_eq!(v, [0, 1, 2, 3, 4, 5, 6]);
21///
22/// // Complete overlap
23/// let mut v = vec![1, 2, 3];
24/// merge_sorted_deduped_in_place(&mut v, &[1, 2, 3]);
25/// assert_eq!(v, [1, 2, 3]);
26///
27/// // No overlap
28/// let mut v = vec![1, 2];
29/// merge_sorted_deduped_in_place(&mut v, &[3, 4]);
30/// assert_eq!(v, [1, 2, 3, 4]);
31///
32/// let mut v = vec![24, 53];
33/// merge_sorted_deduped_in_place(&mut v, &[6]);
34/// assert_eq!(v, [6, 24, 53]);
35///
36/// // Partial overlap
37/// let mut v = vec![10, 11, 12, 13];
38/// merge_sorted_deduped_in_place(&mut v, &[13, 14]);
39/// assert_eq!(v, [10, 11, 12, 13, 14]);
40///
41/// let mut v = vec![300, 400, 500];
42/// merge_sorted_deduped_in_place(&mut v, &[100, 200, 300]);
43/// assert_eq!(v, [100, 200, 300, 400, 500]);
44///
45/// // Empty inputs
46/// let mut v = Vec::new();
47/// merge_sorted_deduped_in_place(&mut v, &[5]);
48/// assert_eq!(v, [5]);
49///
50/// let mut v = vec![6];
51/// merge_sorted_deduped_in_place(&mut v, &[]);
52/// assert_eq!(v, [6]);
53///
54/// let mut v: Vec<u32> = Vec::new();
55/// merge_sorted_deduped_in_place(&mut v, &[]);
56/// assert_eq!(v, []);
57/// ```
58#[inline]
59pub fn merge_sorted_deduped_in_place<T: Copy + Ord + Default>(a: &mut Vec<T>, b: &[T]) {
60    debug_assert!(a.windows(2).all(|w| w[0] < w[1]));
61    debug_assert!(b.windows(2).all(|w| w[0] < w[1]));
62
63    let mut new = 0;
64    let (mut i, mut j) = (0, 0);
65    while i < a.len() && j < b.len() {
66        match a[i].cmp(&b[j]) {
67            Ordering::Less => i += 1,
68            Ordering::Equal => {
69                i += 1;
70                j += 1;
71            }
72            Ordering::Greater => {
73                new += 1;
74                j += 1;
75            }
76        }
77    }
78    new += b.len() - j;
79
80    if new == 0 {
81        return;
82    }
83
84    let (mut i, mut j, mut write) = (a.len(), b.len(), a.len() + new);
85    a.resize(a.len() + new, T::default());
86
87    while i > 0 && j > 0 {
88        write -= 1;
89        a[write] = match a[i - 1].cmp(&b[j - 1]) {
90            Ordering::Less => {
91                j -= 1;
92                b[j]
93            }
94            Ordering::Equal => {
95                i -= 1;
96                j -= 1;
97                a[i]
98            }
99            Ordering::Greater => {
100                i -= 1;
101                a[i]
102            }
103        }
104    }
105
106    a[..j].copy_from_slice(&b[..j]);
107}
utils/slice.rs

utils/
slice.rs
