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