| 1 |
#![cfg(test)] |
| 2 |
|
| 3 |
use crate::prelude::*; |
| 4 |
use rand::distributions::Uniform; |
| 5 |
use rand::seq::SliceRandom; |
| 6 |
use rand::{thread_rng, Rng}; |
| 7 |
use std::cmp::Ordering::{Equal, Greater, Less}; |
| 8 |
use std::sync::atomic::{AtomicUsize, Ordering::Relaxed}; |
| 9 |
|
| 10 |
macro_rules! sort { |
| 11 |
($f:ident, $name:ident) => { |
| 12 |
#[test] |
| 13 |
fn $name() { |
| 14 |
let rng = &mut thread_rng(); |
| 15 |
|
| 16 |
for len in (0..25).chain(500..501) { |
| 17 |
for &modulus in &[5, 10, 100] { |
| 18 |
let dist = Uniform::new(0, modulus); |
| 19 |
for _ in 0..100 { |
| 20 |
let v: Vec<i32> = rng.sample_iter(&dist).take(len).collect(); |
| 21 |
|
| 22 |
// Test sort using `<` operator. |
| 23 |
let mut tmp = v.clone(); |
| 24 |
tmp.$f(|a, b| a.cmp(b)); |
| 25 |
assert!(tmp.windows(2).all(|w| w[0] <= w[1])); |
| 26 |
|
| 27 |
// Test sort using `>` operator. |
| 28 |
let mut tmp = v.clone(); |
| 29 |
tmp.$f(|a, b| b.cmp(a)); |
| 30 |
assert!(tmp.windows(2).all(|w| w[0] >= w[1])); |
| 31 |
} |
| 32 |
} |
| 33 |
} |
| 34 |
|
| 35 |
// Test sort with many duplicates. |
| 36 |
for &len in &[1_000, 10_000, 100_000] { |
| 37 |
for &modulus in &[5, 10, 100, 10_000] { |
| 38 |
let dist = Uniform::new(0, modulus); |
| 39 |
let mut v: Vec<i32> = rng.sample_iter(&dist).take(len).collect(); |
| 40 |
|
| 41 |
v.$f(|a, b| a.cmp(b)); |
| 42 |
assert!(v.windows(2).all(|w| w[0] <= w[1])); |
| 43 |
} |
| 44 |
} |
| 45 |
|
| 46 |
// Test sort with many pre-sorted runs. |
| 47 |
for &len in &[1_000, 10_000, 100_000] { |
| 48 |
let len_dist = Uniform::new(0, len); |
| 49 |
for &modulus in &[5, 10, 1000, 50_000] { |
| 50 |
let dist = Uniform::new(0, modulus); |
| 51 |
let mut v: Vec<i32> = rng.sample_iter(&dist).take(len).collect(); |
| 52 |
|
| 53 |
v.sort(); |
| 54 |
v.reverse(); |
| 55 |
|
| 56 |
for _ in 0..5 { |
| 57 |
let a = rng.sample(&len_dist); |
| 58 |
let b = rng.sample(&len_dist); |
| 59 |
if a < b { |
| 60 |
v[a..b].reverse(); |
| 61 |
} else { |
| 62 |
v.swap(a, b); |
| 63 |
} |
| 64 |
} |
| 65 |
|
| 66 |
v.$f(|a, b| a.cmp(b)); |
| 67 |
assert!(v.windows(2).all(|w| w[0] <= w[1])); |
| 68 |
} |
| 69 |
} |
| 70 |
|
| 71 |
// Sort using a completely random comparison function. |
| 72 |
// This will reorder the elements *somehow*, but won't panic. |
| 73 |
let mut v: Vec<_> = (0..100).collect(); |
| 74 |
v.$f(|_, _| *[Less, Equal, Greater].choose(&mut thread_rng()).unwrap()); |
| 75 |
v.$f(|a, b| a.cmp(b)); |
| 76 |
for i in 0..v.len() { |
| 77 |
assert_eq!(v[i], i); |
| 78 |
} |
| 79 |
|
| 80 |
// Should not panic. |
| 81 |
[0i32; 0].$f(|a, b| a.cmp(b)); |
| 82 |
[(); 10].$f(|a, b| a.cmp(b)); |
| 83 |
[(); 100].$f(|a, b| a.cmp(b)); |
| 84 |
|
| 85 |
let mut v = [0xDEAD_BEEFu64]; |
| 86 |
v.$f(|a, b| a.cmp(b)); |
| 87 |
assert!(v == [0xDEAD_BEEF]); |
| 88 |
} |
| 89 |
}; |
| 90 |
} |
| 91 |
|
| 92 |
sort!(par_sort_by, test_par_sort); |
| 93 |
sort!(par_sort_unstable_by, test_par_sort_unstable); |
| 94 |
|
| 95 |
#[test] |
| 96 |
fn test_par_sort_stability() { |
| 97 |
for len in (2..25).chain(500..510).chain(50_000..50_010) { |
| 98 |
for _ in 0..10 { |
| 99 |
let mut counts = [0; 10]; |
| 100 |
|
| 101 |
// Create a vector like [(6, 1), (5, 1), (6, 2), ...], |
| 102 |
// where the first item of each tuple is random, but |
| 103 |
// the second item represents which occurrence of that |
| 104 |
// number this element is, i.e. the second elements |
| 105 |
// will occur in sorted order. |
| 106 |
let mut rng = thread_rng(); |
| 107 |
let mut v: Vec<_> = (0..len) |
| 108 |
.map(|_| { |
| 109 |
let n: usize = rng.gen_range(0..10); |
| 110 |
counts[n] += 1; |
| 111 |
(n, counts[n]) |
| 112 |
}) |
| 113 |
.collect(); |
| 114 |
|
| 115 |
// Only sort on the first element, so an unstable sort |
| 116 |
// may mix up the counts. |
| 117 |
v.par_sort_by(|&(a, _), &(b, _)| a.cmp(&b)); |
| 118 |
|
| 119 |
// This comparison includes the count (the second item |
| 120 |
// of the tuple), so elements with equal first items |
| 121 |
// will need to be ordered with increasing |
| 122 |
// counts... i.e. exactly asserting that this sort is |
| 123 |
// stable. |
| 124 |
assert!(v.windows(2).all(|w| w[0] <= w[1])); |
| 125 |
} |
| 126 |
} |
| 127 |
} |
| 128 |
|
| 129 |
#[test] |
| 130 |
fn test_par_chunks_exact_remainder() { |
| 131 |
let v: &[i32] = &[0, 1, 2, 3, 4]; |
| 132 |
let c = v.par_chunks_exact(2); |
| 133 |
assert_eq!(c.remainder(), &[4]); |
| 134 |
assert_eq!(c.len(), 2); |
| 135 |
} |
| 136 |
|
| 137 |
#[test] |
| 138 |
fn test_par_chunks_exact_mut_remainder() { |
| 139 |
let v: &mut [i32] = &mut [0, 1, 2, 3, 4]; |
| 140 |
let mut c = v.par_chunks_exact_mut(2); |
| 141 |
assert_eq!(c.remainder(), &[4]); |
| 142 |
assert_eq!(c.len(), 2); |
| 143 |
assert_eq!(c.into_remainder(), &[4]); |
| 144 |
|
| 145 |
let mut c = v.par_chunks_exact_mut(2); |
| 146 |
assert_eq!(c.take_remainder(), &[4]); |
| 147 |
assert_eq!(c.take_remainder(), &[]); |
| 148 |
assert_eq!(c.len(), 2); |
| 149 |
} |
| 150 |
|
| 151 |
#[test] |
| 152 |
fn test_par_rchunks_exact_remainder() { |
| 153 |
let v: &[i32] = &[0, 1, 2, 3, 4]; |
| 154 |
let c = v.par_rchunks_exact(2); |
| 155 |
assert_eq!(c.remainder(), &[0]); |
| 156 |
assert_eq!(c.len(), 2); |
| 157 |
} |
| 158 |
|
| 159 |
#[test] |
| 160 |
fn test_par_rchunks_exact_mut_remainder() { |
| 161 |
let v: &mut [i32] = &mut [0, 1, 2, 3, 4]; |
| 162 |
let mut c = v.par_rchunks_exact_mut(2); |
| 163 |
assert_eq!(c.remainder(), &[0]); |
| 164 |
assert_eq!(c.len(), 2); |
| 165 |
assert_eq!(c.into_remainder(), &[0]); |
| 166 |
|
| 167 |
let mut c = v.par_rchunks_exact_mut(2); |
| 168 |
assert_eq!(c.take_remainder(), &[0]); |
| 169 |
assert_eq!(c.take_remainder(), &[]); |
| 170 |
assert_eq!(c.len(), 2); |
| 171 |
} |
| 172 |
|
| 173 |
#[test] |
| 174 |
fn slice_chunk_by() { |
| 175 |
let v: Vec<_> = (0..1000).collect(); |
| 176 |
assert_eq!(v[..0].par_chunk_by(|_, _| todo!()).count(), 0); |
| 177 |
assert_eq!(v[..1].par_chunk_by(|_, _| todo!()).count(), 1); |
| 178 |
assert_eq!(v[..2].par_chunk_by(|_, _| true).count(), 1); |
| 179 |
assert_eq!(v[..2].par_chunk_by(|_, _| false).count(), 2); |
| 180 |
|
| 181 |
let count = AtomicUsize::new(0); |
| 182 |
let par: Vec<_> = v |
| 183 |
.par_chunk_by(|x, y| { |
| 184 |
count.fetch_add(1, Relaxed); |
| 185 |
(x % 10 < 3) == (y % 10 < 3) |
| 186 |
}) |
| 187 |
.collect(); |
| 188 |
assert_eq!(count.into_inner(), v.len() - 1); |
| 189 |
|
| 190 |
let seq: Vec<_> = v.chunk_by(|x, y| (x % 10 < 3) == (y % 10 < 3)).collect(); |
| 191 |
assert_eq!(par, seq); |
| 192 |
} |
| 193 |
|
| 194 |
#[test] |
| 195 |
fn slice_chunk_by_mut() { |
| 196 |
let mut v: Vec<_> = (0..1000).collect(); |
| 197 |
assert_eq!(v[..0].par_chunk_by_mut(|_, _| todo!()).count(), 0); |
| 198 |
assert_eq!(v[..1].par_chunk_by_mut(|_, _| todo!()).count(), 1); |
| 199 |
assert_eq!(v[..2].par_chunk_by_mut(|_, _| true).count(), 1); |
| 200 |
assert_eq!(v[..2].par_chunk_by_mut(|_, _| false).count(), 2); |
| 201 |
|
| 202 |
let mut v2 = v.clone(); |
| 203 |
let count = AtomicUsize::new(0); |
| 204 |
let par: Vec<_> = v |
| 205 |
.par_chunk_by_mut(|x, y| { |
| 206 |
count.fetch_add(1, Relaxed); |
| 207 |
(x % 10 < 3) == (y % 10 < 3) |
| 208 |
}) |
| 209 |
.collect(); |
| 210 |
assert_eq!(count.into_inner(), v2.len() - 1); |
| 211 |
|
| 212 |
let seq: Vec<_> = v2 |
| 213 |
.chunk_by_mut(|x, y| (x % 10 < 3) == (y % 10 < 3)) |
| 214 |
.collect(); |
| 215 |
assert_eq!(par, seq); |
| 216 |
} |