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 
9 macro_rules! sort {
10     ($f:ident, $name:ident) => {
11         #[test]
12         fn $name() {
13             let mut rng = 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 
91 sort!(par_sort_by, test_par_sort);
92 sort!(par_sort_unstable_by, test_par_sort_unstable);
93 
94 #[test]
test_par_sort_stability()95 fn 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]
test_par_chunks_exact_remainder()129 fn 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]
test_par_chunks_exact_mut_remainder()137 fn 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