array_rotation/
lib.rs

1//! Rotate arrays and elements.
2//!
3//! # Examples
4//! ```
5//! use std::mem::MaybeUninit;
6//!
7//! use array_rotation::array_rotate_2;
8//!
9//! fn uninit_array<T, const N: usize>() -> [MaybeUninit<T>; N] {
10//!     unsafe { MaybeUninit::<[MaybeUninit<T>; N]>::uninit().assume_init() }
11//! }
12//!
13//! let mut left = uninit_array::<String, 10>();
14//! left[0].write("A".to_owned());
15//! left[1].write("B".to_owned());
16//! left[2].write("C".to_owned());
17//! left[3].write("D".to_owned());
18//! let mut right = uninit_array::<String, 10>();
19//! right[0].write("E".to_owned());
20//!
21//! let leftlen_old = 4;
22//! let rightlen_old = 1;
23//! let leftlen_new = 2;
24//! let rightlen_new = unsafe {
25//!     array_rotate_2(&mut left, &mut right, leftlen_old, rightlen_old, leftlen_new)
26//! };
27//!
28//! assert_eq!(rightlen_new, 3);
29//! unsafe {
30//!     let left = &*(&left[..leftlen_new] as *const [_] as *const [String]);
31//!     assert_eq!(left, ["A", "B"]);
32//!     let right = &*(&right[..rightlen_new] as *const [_] as *const [String]);
33//!     assert_eq!(right, ["C", "D", "E"]);
34//! }
35//!
36//! unsafe {
37//!     array_rotate_2(&mut left, &mut right, leftlen_new, rightlen_new, 0);
38//!     for e in &mut right[..leftlen_new + rightlen_new] {
39//!         e.assume_init_drop();
40//!     }
41//! }
42//! ```
43//!
44//! ```
45//! use std::mem::MaybeUninit;
46//!
47//! use array_rotation::array_rotate_3;
48//!
49//! fn uninit_array<T, const N: usize>() -> [MaybeUninit<T>; N] {
50//!     unsafe { MaybeUninit::<[MaybeUninit<T>; N]>::uninit().assume_init() }
51//! }
52//!
53//! let mut left = uninit_array::<String, 10>();
54//! left[0].write("A".to_owned());
55//! left[1].write("B".to_owned());
56//! left[2].write("C".to_owned());
57//! left[3].write("D".to_owned());
58//! let mut mid = MaybeUninit::new("E".to_owned());
59//! let mut right = uninit_array::<String, 10>();
60//! right[0].write("F".to_owned());
61//!
62//! let leftlen_old = 4;
63//! let rightlen_old = 1;
64//! let leftlen_new = 2;
65//! let rightlen_new = unsafe {
66//!     array_rotate_3(&mut left, &mut mid, &mut right, leftlen_old, rightlen_old, leftlen_new)
67//! };
68//!
69//! assert_eq!(rightlen_new, 3);
70//! unsafe {
71//!     let left = &*(&left[..leftlen_new] as *const [_] as *const [String]);
72//!     assert_eq!(left, ["A", "B"]);
73//!     assert_eq!(mid.assume_init_ref(), "C");
74//!     let right = &*(&right[..rightlen_new] as *const [_] as *const [String]);
75//!     assert_eq!(right, ["D", "E", "F"]);
76//! }
77//!
78//! unsafe {
79//!     array_rotate_3(&mut left, &mut mid, &mut right, leftlen_new, rightlen_new, 0);
80//!     mid.assume_init_drop();
81//!     for e in &mut right[..leftlen_new + rightlen_new] {
82//!         e.assume_init_drop();
83//!     }
84//! }
85//! ```
86
87use std::{mem::MaybeUninit, ptr};
88
89/// Rotate two arrays.
90///
91/// # Safety
92/// - `(left|right)len_(old|new) in 0..=N`,
93/// - `left[..leftlen_old]` is initialized,
94/// - `left[leftlen_old..]` is uninitialized,
95/// - `right[..rightlen_old]` is initialized, and
96/// - `right[rightlen_old..]` is uninitialized.
97pub unsafe fn array_rotate_2<T, const N: usize>(
98    left: &mut [MaybeUninit<T>; N],
99    right: &mut [MaybeUninit<T>; N],
100    leftlen_old: usize,
101    rightlen_old: usize,
102    leftlen_new: usize,
103) -> usize {
104    debug_assert!(leftlen_old <= N && rightlen_old <= N);
105    debug_assert!(leftlen_new <= N);
106    debug_assert!(leftlen_new <= leftlen_old + rightlen_old);
107    let rightlen_new = leftlen_old + rightlen_old - leftlen_new;
108    debug_assert!(rightlen_new <= N);
109    if leftlen_old < leftlen_new {
110        let left_diff = leftlen_new - leftlen_old;
111        // [A, B, C] ++ [D, E, F, G, H, I]
112        let count = left_diff;
113        let src = right[..count].as_ptr();
114        let dst = left[leftlen_old..][..count].as_mut_ptr();
115        ptr::copy_nonoverlapping(src, dst, count);
116        // [A, B, C, D, E] ++ [_, _, F, G, H, I]
117        let count = rightlen_new;
118        let dst = right[..count].as_mut_ptr();
119        // Overlapping `src` should be after `dst` for Stacked Borrows.
120        let src = right[left_diff..][..count].as_ptr();
121        ptr::copy(src, dst, count);
122        // [A, B, C, D, E] ++ [F, G, H, I]
123    } else if leftlen_old > leftlen_new {
124        let right_diff = rightlen_new - rightlen_old;
125        // [A, B, C, D, E, F] ++ [G, H, I]
126        let count = rightlen_old;
127        let dst = right[right_diff..][..count].as_mut_ptr();
128        let src = right[..count].as_ptr();
129        ptr::copy(src, dst, count);
130        // [A, B, C, D, E, F] ++ [_, _, G, H, I]
131        let count = right_diff;
132        let src = left[leftlen_new..][..count].as_ptr();
133        let dst = right[..count].as_mut_ptr();
134        ptr::copy_nonoverlapping(src, dst, count);
135        // [A, B, C, D] ++ [E, F, G, H, I]
136    }
137    rightlen_new
138}
139
140/// Rotate two arrays and one element.
141///
142/// # Safety
143/// - `(left|right)len_(old|new) in 0..=N`,
144/// - `left[..leftlen_old]` is initialized,
145/// - `left[leftlen_old..]` is uninitialized,
146/// - `right[..rightlen_old]` is initialized,
147/// - `right[rightlen_old..]` is uninitialized, and
148/// - `mid` is initialized.
149pub unsafe fn array_rotate_3<T, const N: usize>(
150    left: &mut [MaybeUninit<T>; N],
151    mid: &mut MaybeUninit<T>,
152    right: &mut [MaybeUninit<T>; N],
153    leftlen_old: usize,
154    rightlen_old: usize,
155    leftlen_new: usize,
156) -> usize {
157    debug_assert!(leftlen_old <= N && rightlen_old <= N);
158    debug_assert!(leftlen_new <= N);
159    debug_assert!(leftlen_new <= leftlen_old + rightlen_old);
160    let rightlen_new = leftlen_old + rightlen_old - leftlen_new;
161    debug_assert!(rightlen_new <= N);
162    if leftlen_old < leftlen_new {
163        let mid_elt = unsafe { mid.assume_init_read() };
164        // [A, B, C] ++ [D] ++ [E, F, G, H, I, J, K, L]
165        left[leftlen_old].write(mid_elt);
166        // [A, B, C, D] ++ [_] ++ [E, F, G, H, I, J, K, L]
167        let left_diff = leftlen_new - leftlen_old;
168        let count = left_diff - 1;
169        let src = right[..count].as_ptr();
170        let dst = left[leftlen_old + 1..][..count].as_mut_ptr();
171        ptr::copy_nonoverlapping(src, dst, count);
172        // [A, B, C, D, E, F] ++ [_] ++ [_, _, G, H, I, J, K, L]
173        let new_mid_elt = unsafe { right[left_diff - 1].assume_init_read() };
174        mid.write(new_mid_elt);
175        // [A, B, C, D, E, F] ++ [G] ++ [_, _, _, H, I, J, K, L]
176        let count = rightlen_new;
177        let dst = right[..count].as_mut_ptr();
178        let src = right[left_diff..][..count].as_ptr();
179        ptr::copy(src, dst, count);
180        // [A, B, C, D, E, F] ++ [G] ++ [H, I, J, K, L]
181    } else if leftlen_old > leftlen_new {
182        let mid_elt = unsafe { mid.assume_init_read() };
183        // [A, B, C, D, E, F, G, H] ++ [I] ++ [J, K, L]
184        let right_diff = rightlen_new - rightlen_old;
185        let count = rightlen_old;
186        let dst = right[right_diff..][..count].as_mut_ptr();
187        let src = right[..count].as_ptr();
188        ptr::copy(src, dst, count);
189        // [A, B, C, D, E, F, G, H] ++ [I] ++ [_, _, _, J, K, L]
190        right[right_diff - 1].write(mid_elt);
191        // [A, B, C, D, E, F, G, H] ++ [_] ++ [_, _, I, J, K, L]
192        let count = right_diff - 1;
193        let src = left[leftlen_new + 1..][..count].as_ptr();
194        let dst = right[..count].as_mut_ptr();
195        ptr::copy_nonoverlapping(src, dst, count);
196        // [A, B, C, D, E, F] ++ [_] ++ [G, H, I, J, K, L]
197        let new_mid_elt = unsafe { left[leftlen_new].assume_init_read() };
198        mid.write(new_mid_elt);
199        // [A, B, C, D, E] ++ [F] ++ [G, H, I, J, K, L]
200    }
201    rightlen_new
202}
203
204#[cfg(test)]
205mod tests {
206    use std::mem::MaybeUninit;
207
208    use super::*;
209
210    #[cfg(test)]
211    fn uninit_array<T, const N: usize>() -> [MaybeUninit<T>; N] {
212        // polyfill of `std::mem::MaybeUninit::transpose()`
213        unsafe { MaybeUninit::<[MaybeUninit<T>; N]>::uninit().assume_init() }
214    }
215
216    #[cfg(test)]
217    unsafe fn assume_init_collect<'a, I, E, O>(iter: I) -> O
218    where
219        I: IntoIterator<Item = &'a MaybeUninit<E>>,
220        E: 'a + Clone,
221        O: FromIterator<E>,
222    {
223        iter.into_iter()
224            .map(|e| unsafe { e.assume_init_ref() }.clone())
225            .collect()
226    }
227
228    #[test]
229    fn sanity_check_2_few() {
230        let mut left = uninit_array::<String, 10>();
231        left[0].write("A".to_owned());
232        left[1].write("B".to_owned());
233        left[2].write("C".to_owned());
234        left[3].write("D".to_owned());
235        left[4].write("E".to_owned());
236        left[5].write("F".to_owned());
237        left[6].write("G".to_owned());
238        left[7].write("H".to_owned());
239        left[8].write("I".to_owned());
240        let mut right = uninit_array::<String, 10>();
241
242        let leftlen_old = 9;
243        let rightlen_old = 0;
244
245        let expected: String =
246            unsafe { assume_init_collect(&left[..leftlen_old]) };
247
248        let (mut leftlen_old, mut rightlen_old) = (leftlen_old, rightlen_old);
249        for &leftlen_new in &[3, 7, 9, 0, 2, 1, 5, 5, 8, 6] {
250            let rightlen_new = unsafe {
251                array_rotate_2(
252                    &mut left,
253                    &mut right,
254                    leftlen_old,
255                    rightlen_old,
256                    leftlen_new,
257                )
258            };
259
260            let left: String =
261                unsafe { assume_init_collect(&left[..leftlen_new]) };
262            let right: String =
263                unsafe { assume_init_collect(&right[..rightlen_new]) };
264            assert_eq!(left, &expected[..leftlen_new]);
265            assert_eq!(right, &expected[leftlen_new..]);
266
267            leftlen_old = leftlen_new;
268            rightlen_old = rightlen_new;
269        }
270
271        unsafe {
272            for e in &mut left[..leftlen_old] {
273                e.assume_init_drop();
274            }
275            for e in &mut right[..rightlen_old] {
276                e.assume_init_drop();
277            }
278        }
279    }
280
281    #[test]
282    fn sanity_check_2_many() {
283        let mut left = uninit_array::<String, 10>();
284        left[0].write("A".to_owned());
285        left[1].write("B".to_owned());
286        left[2].write("C".to_owned());
287        left[3].write("D".to_owned());
288        left[4].write("E".to_owned());
289        left[5].write("F".to_owned());
290        left[6].write("G".to_owned());
291        left[7].write("H".to_owned());
292        left[8].write("I".to_owned());
293        let mut right = uninit_array::<String, 10>();
294        right[0].write("J".to_owned());
295        right[1].write("K".to_owned());
296        right[2].write("L".to_owned());
297        right[3].write("M".to_owned());
298        right[4].write("N".to_owned());
299        right[5].write("O".to_owned());
300
301        let leftlen_old = 9;
302        let rightlen_old = 6;
303
304        let expected = {
305            let left: String =
306                unsafe { assume_init_collect(&left[..leftlen_old]) };
307            let right: String =
308                unsafe { assume_init_collect(&right[..rightlen_old]) };
309            left + &right
310        };
311
312        let (mut leftlen_old, mut rightlen_old) = (leftlen_old, rightlen_old);
313        for &leftlen_new in &[5, 9, 7, 8, 6, 8, 8] {
314            let rightlen_new = unsafe {
315                array_rotate_2(
316                    &mut left,
317                    &mut right,
318                    leftlen_old,
319                    rightlen_old,
320                    leftlen_new,
321                )
322            };
323
324            let left: String =
325                unsafe { assume_init_collect(&left[..leftlen_new]) };
326            let right: String =
327                unsafe { assume_init_collect(&right[..rightlen_new]) };
328            assert_eq!(left, &expected[..leftlen_new]);
329            assert_eq!(right, &expected[leftlen_new..]);
330
331            leftlen_old = leftlen_new;
332            rightlen_old = rightlen_new;
333        }
334
335        unsafe {
336            for e in &mut left[..leftlen_old] {
337                e.assume_init_drop();
338            }
339            for e in &mut right[..rightlen_old] {
340                e.assume_init_drop();
341            }
342        }
343    }
344
345    #[test]
346    fn sanity_check_3_few() {
347        let mut left = uninit_array::<String, 10>();
348        left[0].write("A".to_owned());
349        left[1].write("B".to_owned());
350        left[2].write("C".to_owned());
351        left[3].write("D".to_owned());
352        left[4].write("E".to_owned());
353        left[5].write("F".to_owned());
354        left[6].write("G".to_owned());
355        left[7].write("H".to_owned());
356        left[8].write("I".to_owned());
357        let mut mid = MaybeUninit::new("J".to_owned());
358        let mut right = uninit_array::<String, 10>();
359
360        let leftlen_old = 9;
361        let rightlen_old = 0;
362
363        let expected = {
364            let left: String =
365                unsafe { assume_init_collect(&left[..leftlen_old]) };
366            left + unsafe { &mid.assume_init_ref() }
367        };
368
369        let (mut leftlen_old, mut rightlen_old) = (leftlen_old, rightlen_old);
370        for &leftlen_new in &[3, 7, 9, 0, 2, 1, 5, 5, 8, 6] {
371            let rightlen_new = unsafe {
372                array_rotate_3(
373                    &mut left,
374                    &mut mid,
375                    &mut right,
376                    leftlen_old,
377                    rightlen_old,
378                    leftlen_new,
379                )
380            };
381
382            let left: String =
383                unsafe { assume_init_collect(&left[..leftlen_new]) };
384            let mid = unsafe { mid.assume_init_ref().clone() };
385            let right: String =
386                unsafe { assume_init_collect(&right[..rightlen_new]) };
387            assert_eq!(left, &expected[..leftlen_new]);
388            assert_eq!(mid, &expected[leftlen_new..leftlen_new + 1]);
389            assert_eq!(right, &expected[leftlen_new + 1..]);
390
391            leftlen_old = leftlen_new;
392            rightlen_old = rightlen_new;
393        }
394
395        unsafe {
396            for e in &mut left[..leftlen_old] {
397                e.assume_init_drop();
398            }
399            for e in &mut right[..rightlen_old] {
400                e.assume_init_drop();
401            }
402            mid.assume_init_drop();
403        }
404    }
405
406    #[test]
407    fn sanity_check_3_many() {
408        let mut left = uninit_array::<String, 10>();
409        left[0].write("A".to_owned());
410        left[1].write("B".to_owned());
411        left[2].write("C".to_owned());
412        left[3].write("D".to_owned());
413        left[4].write("E".to_owned());
414        left[5].write("F".to_owned());
415        left[6].write("G".to_owned());
416        left[7].write("H".to_owned());
417        left[8].write("I".to_owned());
418        let mut mid = MaybeUninit::new("J".to_owned());
419        let mut right = uninit_array::<String, 10>();
420        right[0].write("K".to_owned());
421        right[1].write("L".to_owned());
422        right[2].write("M".to_owned());
423        right[3].write("N".to_owned());
424        right[4].write("O".to_owned());
425        right[5].write("P".to_owned());
426
427        let leftlen_old = 9;
428        let rightlen_old = 6;
429
430        let expected = {
431            let left: String =
432                unsafe { assume_init_collect(&left[..leftlen_old]) };
433            let right: String =
434                unsafe { assume_init_collect(&right[..rightlen_old]) };
435            left + unsafe { &mid.assume_init_ref() } + &right
436        };
437
438        let (mut leftlen_old, mut rightlen_old) = (leftlen_old, rightlen_old);
439        for &leftlen_new in &[7, 9, 9, 8, 7, 8, 6, 8] {
440            let rightlen_new = unsafe {
441                array_rotate_3(
442                    &mut left,
443                    &mut mid,
444                    &mut right,
445                    leftlen_old,
446                    rightlen_old,
447                    leftlen_new,
448                )
449            };
450
451            let left: String =
452                unsafe { assume_init_collect(&left[..leftlen_new]) };
453            let mid = unsafe { mid.assume_init_ref().clone() };
454            let right: String =
455                unsafe { assume_init_collect(&right[..rightlen_new]) };
456            assert_eq!(left, &expected[..leftlen_new]);
457            assert_eq!(mid, &expected[leftlen_new..leftlen_new + 1]);
458            assert_eq!(right, &expected[leftlen_new + 1..]);
459
460            leftlen_old = leftlen_new;
461            rightlen_old = rightlen_new;
462        }
463
464        unsafe {
465            for e in &mut left[..leftlen_old] {
466                e.assume_init_drop();
467            }
468            for e in &mut right[..rightlen_old] {
469                e.assume_init_drop();
470            }
471            mid.assume_init_drop();
472        }
473    }
474}
array_rotation/lib.rs

array_rotation/
lib.rs
