Skip to content

Instantly share code, notes, and snippets.

@m1el

m1el/swap_ranges.rs

Last active Aug 11, 2020
Embed
What would you like to do?
fn swap_ranges_copy(vec: &mut [u8], offset1: usize, offset2: usize, len: usize) {
let tmp = vec.to_vec();
vec[offset1..offset1+len].copy_from_slice(&tmp[offset2..offset2+len]);
vec[offset2..offset2+len].copy_from_slice(&tmp[offset1..offset1+len]);
}
fn swap_ranges(vec: &mut [u8], mut offset1: usize, mut offset2: usize, mut len: usize) {
if offset1 < offset2 && offset1 + len >= offset2 {
// The ranges have the following layout here:
// [o1--------]
// [o2--------]
let tail = offset2 - offset1;
// Copy the tail from offset1 into offset2
// [o1-][tail1]
// [o2-][tail2]
// This needs to happen in the reverse order so that the later values
// at offset1 are not mangled in the process of copying. See memmove.
for ii in (tail..len).rev() {
vec[offset2 + ii] = vec[offset1 + ii];
}
// After this, the layout is the following:
// [o1-][xxxxx]
// [o2-][tail1]
len = tail;
} else if offset2 < offset1 && offset2 + len >= offset1 {
// The ranges have the following layout here:
// [o1--------]
// [o2--------]
let head = len - (offset1 - offset2);
// Copy the head from offset1 into offset2
// [head1][o1-]
// [head2][o2-]
for ii in 0..head {
vec[offset2 + ii] = vec[offset1 + ii];
}
// After this, the layout is the following:
// [xxxxx][o1-]
// [head1][o2-]
offset1 += head;
offset2 += head;
len -= head;
}
// At this point, the ranges are non-overlapping
// and the swap can be done in a naive way.
for ii in 0..len {
vec.swap(offset1 + ii, offset2 + ii);
}
}
fn main() {
let vec = vec![1,2,3,4,5];
for o1 in 0..5 {
for o2 in 0..5 {
let maxlen = vec.len() - o1.max(o2);
for len in 1..=maxlen {
{
let mut a = vec.clone();
let mut b = vec.clone();
print!("{} {} {}\n", o1, o2, len);
swap_ranges_copy(&mut a, o1, o2, len);
swap_ranges(&mut b, o1, o2, len);
assert_eq!(a, b);
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment