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

91 | sort!(par_sort_by, test_par_sort); |

92 | sort!(par_sort_unstable_by, test_par_sort_unstable); |

93 | |

94 | #[test] |

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] |

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] |

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

150 | #[test] |

151 | fn 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] |

159 | fn 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 |