Debian Codegraph @

.cargo/vendor/rayon/src/slice/test.rs

raw
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 }