]>
Commit | Line | Data |
---|---|---|
c34b1796 | 1 | use std::collections::BTreeSet; |
3157f602 | 2 | use std::iter::FromIterator; |
9fa01778 | 3 | |
3157f602 XL |
4 | use super::DeterministicRng; |
5 | ||
c34b1796 AL |
6 | #[test] |
7 | fn test_clone_eq() { | |
c30ab7b3 | 8 | let mut m = BTreeSet::new(); |
c34b1796 | 9 | |
c30ab7b3 SL |
10 | m.insert(1); |
11 | m.insert(2); | |
c34b1796 | 12 | |
416331ca | 13 | assert_eq!(m.clone(), m); |
c34b1796 AL |
14 | } |
15 | ||
16 | #[test] | |
17 | fn test_hash() { | |
9fa01778 XL |
18 | use crate::hash; |
19 | ||
c30ab7b3 SL |
20 | let mut x = BTreeSet::new(); |
21 | let mut y = BTreeSet::new(); | |
c34b1796 | 22 | |
c30ab7b3 SL |
23 | x.insert(1); |
24 | x.insert(2); | |
25 | x.insert(3); | |
c34b1796 | 26 | |
c30ab7b3 SL |
27 | y.insert(3); |
28 | y.insert(2); | |
29 | y.insert(1); | |
c34b1796 | 30 | |
416331ca | 31 | assert_eq!(hash(&x), hash(&y)); |
c34b1796 AL |
32 | } |
33 | ||
c30ab7b3 | 34 | fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F) |
8faf50e0 | 35 | where F: FnOnce(&BTreeSet<i32>, &BTreeSet<i32>, &mut dyn FnMut(&i32) -> bool) -> bool |
c34b1796 AL |
36 | { |
37 | let mut set_a = BTreeSet::new(); | |
38 | let mut set_b = BTreeSet::new(); | |
39 | ||
c30ab7b3 SL |
40 | for x in a { |
41 | assert!(set_a.insert(*x)) | |
42 | } | |
43 | for y in b { | |
44 | assert!(set_b.insert(*y)) | |
45 | } | |
c34b1796 AL |
46 | |
47 | let mut i = 0; | |
c30ab7b3 SL |
48 | f(&set_a, |
49 | &set_b, | |
50 | &mut |&x| { | |
e74abb32 XL |
51 | if i < expected.len() { |
52 | assert_eq!(x, expected[i]); | |
53 | } | |
c30ab7b3 SL |
54 | i += 1; |
55 | true | |
56 | }); | |
c34b1796 AL |
57 | assert_eq!(i, expected.len()); |
58 | } | |
59 | ||
60 | #[test] | |
61 | fn test_intersection() { | |
62 | fn check_intersection(a: &[i32], b: &[i32], expected: &[i32]) { | |
63 | check(a, b, expected, |x, y, f| x.intersection(y).all(f)) | |
64 | } | |
65 | ||
66 | check_intersection(&[], &[], &[]); | |
67 | check_intersection(&[1, 2, 3], &[], &[]); | |
68 | check_intersection(&[], &[1, 2, 3], &[]); | |
69 | check_intersection(&[2], &[1, 2, 3], &[2]); | |
70 | check_intersection(&[1, 2, 3], &[2], &[2]); | |
71 | check_intersection(&[11, 1, 3, 77, 103, 5, -5], | |
72 | &[2, 11, 77, -9, -42, 5, 3], | |
73 | &[3, 5, 11, 77]); | |
416331ca XL |
74 | |
75 | if cfg!(miri) { // Miri is too slow | |
76 | return; | |
77 | } | |
78 | ||
e74abb32 | 79 | let large = (0..100).collect::<Vec<_>>(); |
532ac7d7 XL |
80 | check_intersection(&[], &large, &[]); |
81 | check_intersection(&large, &[], &[]); | |
82 | check_intersection(&[-1], &large, &[]); | |
83 | check_intersection(&large, &[-1], &[]); | |
84 | check_intersection(&[0], &large, &[0]); | |
85 | check_intersection(&large, &[0], &[0]); | |
e74abb32 XL |
86 | check_intersection(&[99], &large, &[99]); |
87 | check_intersection(&large, &[99], &[99]); | |
88 | check_intersection(&[100], &large, &[]); | |
89 | check_intersection(&large, &[100], &[]); | |
90 | check_intersection(&[11, 5000, 1, 3, 77, 8924], | |
532ac7d7 | 91 | &large, |
e74abb32 | 92 | &[1, 3, 11, 77]); |
c34b1796 AL |
93 | } |
94 | ||
e1599b0c XL |
95 | #[test] |
96 | fn test_intersection_size_hint() { | |
97 | let x: BTreeSet<i32> = [3, 4].iter().copied().collect(); | |
98 | let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect(); | |
99 | let mut iter = x.intersection(&y); | |
e74abb32 | 100 | assert_eq!(iter.size_hint(), (1, Some(1))); |
e1599b0c XL |
101 | assert_eq!(iter.next(), Some(&3)); |
102 | assert_eq!(iter.size_hint(), (0, Some(0))); | |
103 | assert_eq!(iter.next(), None); | |
e74abb32 XL |
104 | |
105 | iter = y.intersection(&y); | |
106 | assert_eq!(iter.size_hint(), (0, Some(3))); | |
107 | assert_eq!(iter.next(), Some(&1)); | |
108 | assert_eq!(iter.size_hint(), (0, Some(2))); | |
e1599b0c XL |
109 | } |
110 | ||
c34b1796 AL |
111 | #[test] |
112 | fn test_difference() { | |
113 | fn check_difference(a: &[i32], b: &[i32], expected: &[i32]) { | |
114 | check(a, b, expected, |x, y, f| x.difference(y).all(f)) | |
115 | } | |
116 | ||
117 | check_difference(&[], &[], &[]); | |
118 | check_difference(&[1, 12], &[], &[1, 12]); | |
119 | check_difference(&[], &[1, 2, 3, 9], &[]); | |
c30ab7b3 | 120 | check_difference(&[1, 3, 5, 9, 11], &[3, 9], &[1, 5, 11]); |
e74abb32 XL |
121 | check_difference(&[1, 3, 5, 9, 11], &[3, 6, 9], &[1, 5, 11]); |
122 | check_difference(&[1, 3, 5, 9, 11], &[0, 1], &[3, 5, 9, 11]); | |
123 | check_difference(&[1, 3, 5, 9, 11], &[11, 12], &[1, 3, 5, 9]); | |
c34b1796 AL |
124 | check_difference(&[-5, 11, 22, 33, 40, 42], |
125 | &[-12, -5, 14, 23, 34, 38, 39, 50], | |
126 | &[11, 22, 33, 40, 42]); | |
416331ca XL |
127 | |
128 | if cfg!(miri) { // Miri is too slow | |
129 | return; | |
130 | } | |
131 | ||
e74abb32 | 132 | let large = (0..100).collect::<Vec<_>>(); |
532ac7d7 XL |
133 | check_difference(&[], &large, &[]); |
134 | check_difference(&[-1], &large, &[-1]); | |
135 | check_difference(&[0], &large, &[]); | |
e74abb32 XL |
136 | check_difference(&[99], &large, &[]); |
137 | check_difference(&[100], &large, &[100]); | |
138 | check_difference(&[11, 5000, 1, 3, 77, 8924], | |
532ac7d7 XL |
139 | &large, |
140 | &[5000, 8924]); | |
141 | check_difference(&large, &[], &large); | |
142 | check_difference(&large, &[-1], &large); | |
e74abb32 XL |
143 | check_difference(&large, &[100], &large); |
144 | } | |
145 | ||
146 | #[test] | |
147 | fn test_difference_size_hint() { | |
148 | let s246: BTreeSet<i32> = [2, 4, 6].iter().copied().collect(); | |
149 | let s23456: BTreeSet<i32> = (2..=6).collect(); | |
150 | let mut iter = s246.difference(&s23456); | |
151 | assert_eq!(iter.size_hint(), (0, Some(3))); | |
152 | assert_eq!(iter.next(), None); | |
153 | ||
154 | let s12345: BTreeSet<i32> = (1..=5).collect(); | |
155 | iter = s246.difference(&s12345); | |
156 | assert_eq!(iter.size_hint(), (0, Some(3))); | |
157 | assert_eq!(iter.next(), Some(&6)); | |
158 | assert_eq!(iter.size_hint(), (0, Some(0))); | |
159 | assert_eq!(iter.next(), None); | |
160 | ||
161 | let s34567: BTreeSet<i32> = (3..=7).collect(); | |
162 | iter = s246.difference(&s34567); | |
163 | assert_eq!(iter.size_hint(), (0, Some(3))); | |
164 | assert_eq!(iter.next(), Some(&2)); | |
165 | assert_eq!(iter.size_hint(), (0, Some(2))); | |
166 | assert_eq!(iter.next(), None); | |
167 | ||
168 | let s1: BTreeSet<i32> = (-9..=1).collect(); | |
169 | iter = s246.difference(&s1); | |
170 | assert_eq!(iter.size_hint(), (3, Some(3))); | |
171 | ||
172 | let s2: BTreeSet<i32> = (-9..=2).collect(); | |
173 | iter = s246.difference(&s2); | |
174 | assert_eq!(iter.size_hint(), (2, Some(2))); | |
175 | assert_eq!(iter.next(), Some(&4)); | |
176 | assert_eq!(iter.size_hint(), (1, Some(1))); | |
177 | ||
178 | let s23: BTreeSet<i32> = (2..=3).collect(); | |
179 | iter = s246.difference(&s23); | |
180 | assert_eq!(iter.size_hint(), (1, Some(3))); | |
181 | assert_eq!(iter.next(), Some(&4)); | |
182 | assert_eq!(iter.size_hint(), (1, Some(1))); | |
183 | ||
184 | let s4: BTreeSet<i32> = (4..=4).collect(); | |
185 | iter = s246.difference(&s4); | |
186 | assert_eq!(iter.size_hint(), (2, Some(3))); | |
187 | assert_eq!(iter.next(), Some(&2)); | |
188 | assert_eq!(iter.size_hint(), (1, Some(2))); | |
189 | assert_eq!(iter.next(), Some(&6)); | |
190 | assert_eq!(iter.size_hint(), (0, Some(0))); | |
191 | assert_eq!(iter.next(), None); | |
192 | ||
193 | let s56: BTreeSet<i32> = (5..=6).collect(); | |
194 | iter = s246.difference(&s56); | |
195 | assert_eq!(iter.size_hint(), (1, Some(3))); | |
196 | assert_eq!(iter.next(), Some(&2)); | |
197 | assert_eq!(iter.size_hint(), (0, Some(2))); | |
198 | ||
199 | let s6: BTreeSet<i32> = (6..=19).collect(); | |
200 | iter = s246.difference(&s6); | |
201 | assert_eq!(iter.size_hint(), (2, Some(2))); | |
202 | assert_eq!(iter.next(), Some(&2)); | |
203 | assert_eq!(iter.size_hint(), (1, Some(1))); | |
204 | ||
205 | let s7: BTreeSet<i32> = (7..=19).collect(); | |
206 | iter = s246.difference(&s7); | |
207 | assert_eq!(iter.size_hint(), (3, Some(3))); | |
c34b1796 AL |
208 | } |
209 | ||
210 | #[test] | |
211 | fn test_symmetric_difference() { | |
212 | fn check_symmetric_difference(a: &[i32], b: &[i32], expected: &[i32]) { | |
213 | check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f)) | |
214 | } | |
215 | ||
216 | check_symmetric_difference(&[], &[], &[]); | |
217 | check_symmetric_difference(&[1, 2, 3], &[2], &[1, 3]); | |
218 | check_symmetric_difference(&[2], &[1, 2, 3], &[1, 3]); | |
219 | check_symmetric_difference(&[1, 3, 5, 9, 11], | |
220 | &[-2, 3, 9, 14, 22], | |
221 | &[-2, 1, 5, 11, 14, 22]); | |
222 | } | |
223 | ||
e74abb32 XL |
224 | #[test] |
225 | fn test_symmetric_difference_size_hint() { | |
226 | let x: BTreeSet<i32> = [2, 4].iter().copied().collect(); | |
227 | let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect(); | |
228 | let mut iter = x.symmetric_difference(&y); | |
229 | assert_eq!(iter.size_hint(), (0, Some(5))); | |
230 | assert_eq!(iter.next(), Some(&1)); | |
231 | assert_eq!(iter.size_hint(), (0, Some(4))); | |
232 | assert_eq!(iter.next(), Some(&3)); | |
233 | assert_eq!(iter.size_hint(), (0, Some(1))); | |
234 | } | |
235 | ||
c34b1796 AL |
236 | #[test] |
237 | fn test_union() { | |
238 | fn check_union(a: &[i32], b: &[i32], expected: &[i32]) { | |
239 | check(a, b, expected, |x, y, f| x.union(y).all(f)) | |
240 | } | |
241 | ||
242 | check_union(&[], &[], &[]); | |
243 | check_union(&[1, 2, 3], &[2], &[1, 2, 3]); | |
244 | check_union(&[2], &[1, 2, 3], &[1, 2, 3]); | |
245 | check_union(&[1, 3, 5, 9, 11, 16, 19, 24], | |
246 | &[-2, 1, 5, 9, 13, 19], | |
247 | &[-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]); | |
248 | } | |
249 | ||
e74abb32 XL |
250 | #[test] |
251 | fn test_union_size_hint() { | |
252 | let x: BTreeSet<i32> = [2, 4].iter().copied().collect(); | |
253 | let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect(); | |
254 | let mut iter = x.union(&y); | |
255 | assert_eq!(iter.size_hint(), (3, Some(5))); | |
256 | assert_eq!(iter.next(), Some(&1)); | |
257 | assert_eq!(iter.size_hint(), (2, Some(4))); | |
258 | assert_eq!(iter.next(), Some(&2)); | |
259 | assert_eq!(iter.size_hint(), (1, Some(2))); | |
260 | } | |
261 | ||
532ac7d7 XL |
262 | #[test] |
263 | // Only tests the simple function definition with respect to intersection | |
264 | fn test_is_disjoint() { | |
48663c56 XL |
265 | let one = [1].iter().collect::<BTreeSet<_>>(); |
266 | let two = [2].iter().collect::<BTreeSet<_>>(); | |
532ac7d7 XL |
267 | assert!(one.is_disjoint(&two)); |
268 | } | |
269 | ||
270 | #[test] | |
e74abb32 | 271 | // Also implicitly tests the trivial function definition of is_superset |
532ac7d7 XL |
272 | fn test_is_subset() { |
273 | fn is_subset(a: &[i32], b: &[i32]) -> bool { | |
274 | let set_a = a.iter().collect::<BTreeSet<_>>(); | |
275 | let set_b = b.iter().collect::<BTreeSet<_>>(); | |
276 | set_a.is_subset(&set_b) | |
277 | } | |
278 | ||
279 | assert_eq!(is_subset(&[], &[]), true); | |
280 | assert_eq!(is_subset(&[], &[1, 2]), true); | |
281 | assert_eq!(is_subset(&[0], &[1, 2]), false); | |
282 | assert_eq!(is_subset(&[1], &[1, 2]), true); | |
283 | assert_eq!(is_subset(&[2], &[1, 2]), true); | |
284 | assert_eq!(is_subset(&[3], &[1, 2]), false); | |
285 | assert_eq!(is_subset(&[1, 2], &[1]), false); | |
286 | assert_eq!(is_subset(&[1, 2], &[1, 2]), true); | |
287 | assert_eq!(is_subset(&[1, 2], &[2, 3]), false); | |
416331ca | 288 | assert_eq!(is_subset(&[-5, 11, 22, 33, 40, 42], |
e74abb32 | 289 | &[-12, -5, 11, 14, 22, 23, 33, 34, 38, 39, 40, 42]), |
416331ca XL |
290 | true); |
291 | assert_eq!(is_subset(&[-5, 11, 22, 33, 40, 42], | |
e74abb32 | 292 | &[-12, -5, 11, 14, 22, 23, 34, 38]), |
416331ca XL |
293 | false); |
294 | ||
295 | if cfg!(miri) { // Miri is too slow | |
296 | return; | |
297 | } | |
298 | ||
e74abb32 | 299 | let large = (0..100).collect::<Vec<_>>(); |
532ac7d7 XL |
300 | assert_eq!(is_subset(&[], &large), true); |
301 | assert_eq!(is_subset(&large, &[]), false); | |
302 | assert_eq!(is_subset(&[-1], &large), false); | |
303 | assert_eq!(is_subset(&[0], &large), true); | |
304 | assert_eq!(is_subset(&[1, 2], &large), true); | |
e74abb32 | 305 | assert_eq!(is_subset(&[99, 100], &large), false); |
532ac7d7 XL |
306 | } |
307 | ||
c34b1796 AL |
308 | #[test] |
309 | fn test_zip() { | |
310 | let mut x = BTreeSet::new(); | |
311 | x.insert(5); | |
312 | x.insert(12); | |
313 | x.insert(11); | |
314 | ||
315 | let mut y = BTreeSet::new(); | |
316 | y.insert("foo"); | |
317 | y.insert("bar"); | |
318 | ||
319 | let x = x; | |
320 | let y = y; | |
62682a34 | 321 | let mut z = x.iter().zip(&y); |
c34b1796 | 322 | |
b039eaaf SL |
323 | assert_eq!(z.next().unwrap(), (&5, &("bar"))); |
324 | assert_eq!(z.next().unwrap(), (&11, &("foo"))); | |
325 | assert!(z.next().is_none()); | |
c34b1796 AL |
326 | } |
327 | ||
328 | #[test] | |
329 | fn test_from_iter() { | |
330 | let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9]; | |
331 | ||
332 | let set: BTreeSet<_> = xs.iter().cloned().collect(); | |
333 | ||
334 | for x in &xs { | |
335 | assert!(set.contains(x)); | |
336 | } | |
337 | } | |
338 | ||
339 | #[test] | |
340 | fn test_show() { | |
341 | let mut set = BTreeSet::new(); | |
342 | let empty = BTreeSet::<i32>::new(); | |
343 | ||
344 | set.insert(1); | |
345 | set.insert(2); | |
346 | ||
347 | let set_str = format!("{:?}", set); | |
348 | ||
349 | assert_eq!(set_str, "{1, 2}"); | |
350 | assert_eq!(format!("{:?}", empty), "{}"); | |
351 | } | |
62682a34 SL |
352 | |
353 | #[test] | |
354 | fn test_extend_ref() { | |
355 | let mut a = BTreeSet::new(); | |
356 | a.insert(1); | |
357 | ||
358 | a.extend(&[2, 3, 4]); | |
359 | ||
360 | assert_eq!(a.len(), 4); | |
361 | assert!(a.contains(&1)); | |
362 | assert!(a.contains(&2)); | |
363 | assert!(a.contains(&3)); | |
364 | assert!(a.contains(&4)); | |
365 | ||
366 | let mut b = BTreeSet::new(); | |
367 | b.insert(5); | |
368 | b.insert(6); | |
369 | ||
370 | a.extend(&b); | |
371 | ||
372 | assert_eq!(a.len(), 6); | |
373 | assert!(a.contains(&1)); | |
374 | assert!(a.contains(&2)); | |
375 | assert!(a.contains(&3)); | |
376 | assert!(a.contains(&4)); | |
377 | assert!(a.contains(&5)); | |
378 | assert!(a.contains(&6)); | |
379 | } | |
e9174d1e SL |
380 | |
381 | #[test] | |
382 | fn test_recovery() { | |
383 | use std::cmp::Ordering; | |
384 | ||
385 | #[derive(Debug)] | |
386 | struct Foo(&'static str, i32); | |
387 | ||
388 | impl PartialEq for Foo { | |
389 | fn eq(&self, other: &Self) -> bool { | |
390 | self.0 == other.0 | |
391 | } | |
392 | } | |
393 | ||
394 | impl Eq for Foo {} | |
395 | ||
396 | impl PartialOrd for Foo { | |
397 | fn partial_cmp(&self, other: &Self) -> Option<Ordering> { | |
398 | self.0.partial_cmp(&other.0) | |
399 | } | |
400 | } | |
401 | ||
402 | impl Ord for Foo { | |
403 | fn cmp(&self, other: &Self) -> Ordering { | |
404 | self.0.cmp(&other.0) | |
405 | } | |
406 | } | |
407 | ||
408 | let mut s = BTreeSet::new(); | |
409 | assert_eq!(s.replace(Foo("a", 1)), None); | |
410 | assert_eq!(s.len(), 1); | |
411 | assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1))); | |
412 | assert_eq!(s.len(), 1); | |
413 | ||
414 | { | |
415 | let mut it = s.iter(); | |
416 | assert_eq!(it.next(), Some(&Foo("a", 2))); | |
417 | assert_eq!(it.next(), None); | |
418 | } | |
419 | ||
420 | assert_eq!(s.get(&Foo("a", 1)), Some(&Foo("a", 2))); | |
421 | assert_eq!(s.take(&Foo("a", 1)), Some(Foo("a", 2))); | |
422 | assert_eq!(s.len(), 0); | |
423 | ||
424 | assert_eq!(s.get(&Foo("a", 1)), None); | |
425 | assert_eq!(s.take(&Foo("a", 1)), None); | |
426 | ||
427 | assert_eq!(s.iter().next(), None); | |
428 | } | |
9cc50fc6 SL |
429 | |
430 | #[test] | |
7453a54e | 431 | #[allow(dead_code)] |
9cc50fc6 SL |
432 | fn test_variance() { |
433 | use std::collections::btree_set::{IntoIter, Iter, Range}; | |
434 | ||
c30ab7b3 SL |
435 | fn set<'new>(v: BTreeSet<&'static str>) -> BTreeSet<&'new str> { |
436 | v | |
437 | } | |
438 | fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> { | |
439 | v | |
440 | } | |
441 | fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> { | |
442 | v | |
443 | } | |
444 | fn range<'a, 'new>(v: Range<'a, &'static str>) -> Range<'a, &'new str> { | |
445 | v | |
446 | } | |
9cc50fc6 | 447 | } |
a7813a04 XL |
448 | |
449 | #[test] | |
450 | fn test_append() { | |
451 | let mut a = BTreeSet::new(); | |
452 | a.insert(1); | |
453 | a.insert(2); | |
454 | a.insert(3); | |
455 | ||
456 | let mut b = BTreeSet::new(); | |
457 | b.insert(3); | |
458 | b.insert(4); | |
459 | b.insert(5); | |
460 | ||
461 | a.append(&mut b); | |
462 | ||
463 | assert_eq!(a.len(), 5); | |
464 | assert_eq!(b.len(), 0); | |
465 | ||
466 | assert_eq!(a.contains(&1), true); | |
467 | assert_eq!(a.contains(&2), true); | |
468 | assert_eq!(a.contains(&3), true); | |
469 | assert_eq!(a.contains(&4), true); | |
470 | assert_eq!(a.contains(&5), true); | |
471 | } | |
3157f602 | 472 | |
60c5eb7d XL |
473 | #[test] |
474 | fn test_first_last() { | |
475 | let mut a = BTreeSet::new(); | |
476 | assert_eq!(a.first(), None); | |
477 | assert_eq!(a.last(), None); | |
478 | a.insert(1); | |
479 | assert_eq!(a.first(), Some(&1)); | |
480 | assert_eq!(a.last(), Some(&1)); | |
481 | a.insert(2); | |
482 | assert_eq!(a.first(), Some(&1)); | |
483 | assert_eq!(a.last(), Some(&2)); | |
484 | a.insert(3); | |
485 | assert_eq!(a.first(), Some(&1)); | |
486 | assert_eq!(a.last(), Some(&3)); | |
487 | ||
488 | assert_eq!(a.len(), 3); | |
489 | assert_eq!(a.pop_first(), Some(1)); | |
490 | assert_eq!(a.len(), 2); | |
491 | assert_eq!(a.pop_last(), Some(3)); | |
492 | assert_eq!(a.len(), 1); | |
493 | assert_eq!(a.pop_first(), Some(2)); | |
494 | assert_eq!(a.len(), 0); | |
495 | assert_eq!(a.pop_last(), None); | |
496 | assert_eq!(a.len(), 0); | |
497 | assert_eq!(a.pop_first(), None); | |
498 | assert_eq!(a.len(), 0); | |
499 | } | |
500 | ||
3157f602 XL |
501 | fn rand_data(len: usize) -> Vec<u32> { |
502 | let mut rng = DeterministicRng::new(); | |
c30ab7b3 | 503 | Vec::from_iter((0..len).map(|_| rng.next())) |
3157f602 XL |
504 | } |
505 | ||
506 | #[test] | |
507 | fn test_split_off_empty_right() { | |
508 | let mut data = rand_data(173); | |
509 | ||
510 | let mut set = BTreeSet::from_iter(data.clone()); | |
511 | let right = set.split_off(&(data.iter().max().unwrap() + 1)); | |
512 | ||
513 | data.sort(); | |
514 | assert!(set.into_iter().eq(data)); | |
515 | assert!(right.into_iter().eq(None)); | |
516 | } | |
517 | ||
518 | #[test] | |
519 | fn test_split_off_empty_left() { | |
520 | let mut data = rand_data(314); | |
521 | ||
522 | let mut set = BTreeSet::from_iter(data.clone()); | |
523 | let right = set.split_off(data.iter().min().unwrap()); | |
524 | ||
525 | data.sort(); | |
526 | assert!(set.into_iter().eq(None)); | |
527 | assert!(right.into_iter().eq(data)); | |
528 | } | |
529 | ||
530 | #[test] | |
531 | fn test_split_off_large_random_sorted() { | |
416331ca | 532 | #[cfg(not(miri))] // Miri is too slow |
3157f602 | 533 | let mut data = rand_data(1529); |
416331ca XL |
534 | #[cfg(miri)] |
535 | let mut data = rand_data(529); | |
3157f602 XL |
536 | // special case with maximum height. |
537 | data.sort(); | |
538 | ||
539 | let mut set = BTreeSet::from_iter(data.clone()); | |
540 | let key = data[data.len() / 2]; | |
541 | let right = set.split_off(&key); | |
542 | ||
543 | assert!(set.into_iter().eq(data.clone().into_iter().filter(|x| *x < key))); | |
544 | assert!(right.into_iter().eq(data.into_iter().filter(|x| *x >= key))); | |
545 | } |