1 use super::*;
2 use crate::testing::crash_test::{CrashTestDummy, Panic};
3 use crate::testing::rng::DeterministicRng;
4 use crate::vec::Vec;
5 use std::cmp::Ordering;
6 use std::hash::{Hash, Hasher};
7 use std::ops::Bound::{Excluded, Included};
8 use std::panic::{catch_unwind, AssertUnwindSafe};
9
10 #[test]
test_clone_eq()11 fn test_clone_eq() {
12 let mut m = BTreeSet::new();
13
14 m.insert(1);
15 m.insert(2);
16
17 assert_eq!(m.clone(), m);
18 }
19
20 #[test]
test_iter_min_max()21 fn test_iter_min_max() {
22 let mut a = BTreeSet::new();
23 assert_eq!(a.iter().min(), None);
24 assert_eq!(a.iter().max(), None);
25 assert_eq!(a.range(..).min(), None);
26 assert_eq!(a.range(..).max(), None);
27 assert_eq!(a.difference(&BTreeSet::new()).min(), None);
28 assert_eq!(a.difference(&BTreeSet::new()).max(), None);
29 assert_eq!(a.intersection(&a).min(), None);
30 assert_eq!(a.intersection(&a).max(), None);
31 assert_eq!(a.symmetric_difference(&BTreeSet::new()).min(), None);
32 assert_eq!(a.symmetric_difference(&BTreeSet::new()).max(), None);
33 assert_eq!(a.union(&a).min(), None);
34 assert_eq!(a.union(&a).max(), None);
35 a.insert(1);
36 a.insert(2);
37 assert_eq!(a.iter().min(), Some(&1));
38 assert_eq!(a.iter().max(), Some(&2));
39 assert_eq!(a.range(..).min(), Some(&1));
40 assert_eq!(a.range(..).max(), Some(&2));
41 assert_eq!(a.difference(&BTreeSet::new()).min(), Some(&1));
42 assert_eq!(a.difference(&BTreeSet::new()).max(), Some(&2));
43 assert_eq!(a.intersection(&a).min(), Some(&1));
44 assert_eq!(a.intersection(&a).max(), Some(&2));
45 assert_eq!(a.symmetric_difference(&BTreeSet::new()).min(), Some(&1));
46 assert_eq!(a.symmetric_difference(&BTreeSet::new()).max(), Some(&2));
47 assert_eq!(a.union(&a).min(), Some(&1));
48 assert_eq!(a.union(&a).max(), Some(&2));
49 }
50
check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F) where F: FnOnce(&BTreeSet<i32>, &BTreeSet<i32>, &mut dyn FnMut(&i32) -> bool) -> bool,51 fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F)
52 where
53 F: FnOnce(&BTreeSet<i32>, &BTreeSet<i32>, &mut dyn FnMut(&i32) -> bool) -> bool,
54 {
55 let mut set_a = BTreeSet::new();
56 let mut set_b = BTreeSet::new();
57
58 for x in a {
59 assert!(set_a.insert(*x))
60 }
61 for y in b {
62 assert!(set_b.insert(*y))
63 }
64
65 let mut i = 0;
66 f(&set_a, &set_b, &mut |&x| {
67 if i < expected.len() {
68 assert_eq!(x, expected[i]);
69 }
70 i += 1;
71 true
72 });
73 assert_eq!(i, expected.len());
74 }
75
76 #[test]
test_intersection()77 fn test_intersection() {
78 fn check_intersection(a: &[i32], b: &[i32], expected: &[i32]) {
79 check(a, b, expected, |x, y, f| x.intersection(y).all(f))
80 }
81
82 check_intersection(&[], &[], &[]);
83 check_intersection(&[1, 2, 3], &[], &[]);
84 check_intersection(&[], &[1, 2, 3], &[]);
85 check_intersection(&[2], &[1, 2, 3], &[2]);
86 check_intersection(&[1, 2, 3], &[2], &[2]);
87 check_intersection(&[11, 1, 3, 77, 103, 5, -5], &[2, 11, 77, -9, -42, 5, 3], &[3, 5, 11, 77]);
88
89 if cfg!(miri) {
90 // Miri is too slow
91 return;
92 }
93
94 let large = Vec::from_iter(0..100);
95 check_intersection(&[], &large, &[]);
96 check_intersection(&large, &[], &[]);
97 check_intersection(&[-1], &large, &[]);
98 check_intersection(&large, &[-1], &[]);
99 check_intersection(&[0], &large, &[0]);
100 check_intersection(&large, &[0], &[0]);
101 check_intersection(&[99], &large, &[99]);
102 check_intersection(&large, &[99], &[99]);
103 check_intersection(&[100], &large, &[]);
104 check_intersection(&large, &[100], &[]);
105 check_intersection(&[11, 5000, 1, 3, 77, 8924], &large, &[1, 3, 11, 77]);
106 }
107
108 #[test]
test_intersection_size_hint()109 fn test_intersection_size_hint() {
110 let x = BTreeSet::from([3, 4]);
111 let y = BTreeSet::from([1, 2, 3]);
112 let mut iter = x.intersection(&y);
113 assert_eq!(iter.size_hint(), (1, Some(1)));
114 assert_eq!(iter.next(), Some(&3));
115 assert_eq!(iter.size_hint(), (0, Some(0)));
116 assert_eq!(iter.next(), None);
117
118 iter = y.intersection(&y);
119 assert_eq!(iter.size_hint(), (0, Some(3)));
120 assert_eq!(iter.next(), Some(&1));
121 assert_eq!(iter.size_hint(), (0, Some(2)));
122 }
123
124 #[test]
test_difference()125 fn test_difference() {
126 fn check_difference(a: &[i32], b: &[i32], expected: &[i32]) {
127 check(a, b, expected, |x, y, f| x.difference(y).all(f))
128 }
129
130 check_difference(&[], &[], &[]);
131 check_difference(&[1, 12], &[], &[1, 12]);
132 check_difference(&[], &[1, 2, 3, 9], &[]);
133 check_difference(&[1, 3, 5, 9, 11], &[3, 9], &[1, 5, 11]);
134 check_difference(&[1, 3, 5, 9, 11], &[3, 6, 9], &[1, 5, 11]);
135 check_difference(&[1, 3, 5, 9, 11], &[0, 1], &[3, 5, 9, 11]);
136 check_difference(&[1, 3, 5, 9, 11], &[11, 12], &[1, 3, 5, 9]);
137 check_difference(
138 &[-5, 11, 22, 33, 40, 42],
139 &[-12, -5, 14, 23, 34, 38, 39, 50],
140 &[11, 22, 33, 40, 42],
141 );
142
143 if cfg!(miri) {
144 // Miri is too slow
145 return;
146 }
147
148 let large = Vec::from_iter(0..100);
149 check_difference(&[], &large, &[]);
150 check_difference(&[-1], &large, &[-1]);
151 check_difference(&[0], &large, &[]);
152 check_difference(&[99], &large, &[]);
153 check_difference(&[100], &large, &[100]);
154 check_difference(&[11, 5000, 1, 3, 77, 8924], &large, &[5000, 8924]);
155 check_difference(&large, &[], &large);
156 check_difference(&large, &[-1], &large);
157 check_difference(&large, &[100], &large);
158 }
159
160 #[test]
test_difference_size_hint()161 fn test_difference_size_hint() {
162 let s246 = BTreeSet::from([2, 4, 6]);
163 let s23456 = BTreeSet::from_iter(2..=6);
164 let mut iter = s246.difference(&s23456);
165 assert_eq!(iter.size_hint(), (0, Some(3)));
166 assert_eq!(iter.next(), None);
167
168 let s12345 = BTreeSet::from_iter(1..=5);
169 iter = s246.difference(&s12345);
170 assert_eq!(iter.size_hint(), (0, Some(3)));
171 assert_eq!(iter.next(), Some(&6));
172 assert_eq!(iter.size_hint(), (0, Some(0)));
173 assert_eq!(iter.next(), None);
174
175 let s34567 = BTreeSet::from_iter(3..=7);
176 iter = s246.difference(&s34567);
177 assert_eq!(iter.size_hint(), (0, Some(3)));
178 assert_eq!(iter.next(), Some(&2));
179 assert_eq!(iter.size_hint(), (0, Some(2)));
180 assert_eq!(iter.next(), None);
181
182 let s1 = BTreeSet::from_iter(-9..=1);
183 iter = s246.difference(&s1);
184 assert_eq!(iter.size_hint(), (3, Some(3)));
185
186 let s2 = BTreeSet::from_iter(-9..=2);
187 iter = s246.difference(&s2);
188 assert_eq!(iter.size_hint(), (2, Some(2)));
189 assert_eq!(iter.next(), Some(&4));
190 assert_eq!(iter.size_hint(), (1, Some(1)));
191
192 let s23 = BTreeSet::from([2, 3]);
193 iter = s246.difference(&s23);
194 assert_eq!(iter.size_hint(), (1, Some(3)));
195 assert_eq!(iter.next(), Some(&4));
196 assert_eq!(iter.size_hint(), (1, Some(1)));
197
198 let s4 = BTreeSet::from([4]);
199 iter = s246.difference(&s4);
200 assert_eq!(iter.size_hint(), (2, Some(3)));
201 assert_eq!(iter.next(), Some(&2));
202 assert_eq!(iter.size_hint(), (1, Some(2)));
203 assert_eq!(iter.next(), Some(&6));
204 assert_eq!(iter.size_hint(), (0, Some(0)));
205 assert_eq!(iter.next(), None);
206
207 let s56 = BTreeSet::from([5, 6]);
208 iter = s246.difference(&s56);
209 assert_eq!(iter.size_hint(), (1, Some(3)));
210 assert_eq!(iter.next(), Some(&2));
211 assert_eq!(iter.size_hint(), (0, Some(2)));
212
213 let s6 = BTreeSet::from_iter(6..=19);
214 iter = s246.difference(&s6);
215 assert_eq!(iter.size_hint(), (2, Some(2)));
216 assert_eq!(iter.next(), Some(&2));
217 assert_eq!(iter.size_hint(), (1, Some(1)));
218
219 let s7 = BTreeSet::from_iter(7..=19);
220 iter = s246.difference(&s7);
221 assert_eq!(iter.size_hint(), (3, Some(3)));
222 }
223
224 #[test]
test_symmetric_difference()225 fn test_symmetric_difference() {
226 fn check_symmetric_difference(a: &[i32], b: &[i32], expected: &[i32]) {
227 check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f))
228 }
229
230 check_symmetric_difference(&[], &[], &[]);
231 check_symmetric_difference(&[1, 2, 3], &[2], &[1, 3]);
232 check_symmetric_difference(&[2], &[1, 2, 3], &[1, 3]);
233 check_symmetric_difference(&[1, 3, 5, 9, 11], &[-2, 3, 9, 14, 22], &[-2, 1, 5, 11, 14, 22]);
234 }
235
236 #[test]
test_symmetric_difference_size_hint()237 fn test_symmetric_difference_size_hint() {
238 let x = BTreeSet::from([2, 4]);
239 let y = BTreeSet::from([1, 2, 3]);
240 let mut iter = x.symmetric_difference(&y);
241 assert_eq!(iter.size_hint(), (0, Some(5)));
242 assert_eq!(iter.next(), Some(&1));
243 assert_eq!(iter.size_hint(), (0, Some(4)));
244 assert_eq!(iter.next(), Some(&3));
245 assert_eq!(iter.size_hint(), (0, Some(1)));
246 }
247
248 #[test]
test_union()249 fn test_union() {
250 fn check_union(a: &[i32], b: &[i32], expected: &[i32]) {
251 check(a, b, expected, |x, y, f| x.union(y).all(f))
252 }
253
254 check_union(&[], &[], &[]);
255 check_union(&[1, 2, 3], &[2], &[1, 2, 3]);
256 check_union(&[2], &[1, 2, 3], &[1, 2, 3]);
257 check_union(
258 &[1, 3, 5, 9, 11, 16, 19, 24],
259 &[-2, 1, 5, 9, 13, 19],
260 &[-2, 1, 3, 5, 9, 11, 13, 16, 19, 24],
261 );
262 }
263
264 #[test]
test_union_size_hint()265 fn test_union_size_hint() {
266 let x = BTreeSet::from([2, 4]);
267 let y = BTreeSet::from([1, 2, 3]);
268 let mut iter = x.union(&y);
269 assert_eq!(iter.size_hint(), (3, Some(5)));
270 assert_eq!(iter.next(), Some(&1));
271 assert_eq!(iter.size_hint(), (2, Some(4)));
272 assert_eq!(iter.next(), Some(&2));
273 assert_eq!(iter.size_hint(), (1, Some(2)));
274 }
275
276 #[test]
277 // Only tests the simple function definition with respect to intersection
test_is_disjoint()278 fn test_is_disjoint() {
279 let one = BTreeSet::from([1]);
280 let two = BTreeSet::from([2]);
281 assert!(one.is_disjoint(&two));
282 }
283
284 #[test]
285 // Also implicitly tests the trivial function definition of is_superset
test_is_subset()286 fn test_is_subset() {
287 fn is_subset(a: &[i32], b: &[i32]) -> bool {
288 let set_a = BTreeSet::from_iter(a.iter());
289 let set_b = BTreeSet::from_iter(b.iter());
290 set_a.is_subset(&set_b)
291 }
292
293 assert_eq!(is_subset(&[], &[]), true);
294 assert_eq!(is_subset(&[], &[1, 2]), true);
295 assert_eq!(is_subset(&[0], &[1, 2]), false);
296 assert_eq!(is_subset(&[1], &[1, 2]), true);
297 assert_eq!(is_subset(&[2], &[1, 2]), true);
298 assert_eq!(is_subset(&[3], &[1, 2]), false);
299 assert_eq!(is_subset(&[1, 2], &[1]), false);
300 assert_eq!(is_subset(&[1, 2], &[1, 2]), true);
301 assert_eq!(is_subset(&[1, 2], &[2, 3]), false);
302 assert_eq!(
303 is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 33, 34, 38, 39, 40, 42]),
304 true
305 );
306 assert_eq!(is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 34, 38]), false);
307
308 if cfg!(miri) {
309 // Miri is too slow
310 return;
311 }
312
313 let large = Vec::from_iter(0..100);
314 assert_eq!(is_subset(&[], &large), true);
315 assert_eq!(is_subset(&large, &[]), false);
316 assert_eq!(is_subset(&[-1], &large), false);
317 assert_eq!(is_subset(&[0], &large), true);
318 assert_eq!(is_subset(&[1, 2], &large), true);
319 assert_eq!(is_subset(&[99, 100], &large), false);
320 }
321
322 #[test]
test_is_superset()323 fn test_is_superset() {
324 fn is_superset(a: &[i32], b: &[i32]) -> bool {
325 let set_a = BTreeSet::from_iter(a.iter());
326 let set_b = BTreeSet::from_iter(b.iter());
327 set_a.is_superset(&set_b)
328 }
329
330 assert_eq!(is_superset(&[], &[]), true);
331 assert_eq!(is_superset(&[], &[1, 2]), false);
332 assert_eq!(is_superset(&[0], &[1, 2]), false);
333 assert_eq!(is_superset(&[1], &[1, 2]), false);
334 assert_eq!(is_superset(&[4], &[1, 2]), false);
335 assert_eq!(is_superset(&[1, 4], &[1, 2]), false);
336 assert_eq!(is_superset(&[1, 2], &[1, 2]), true);
337 assert_eq!(is_superset(&[1, 2, 3], &[1, 3]), true);
338 assert_eq!(is_superset(&[1, 2, 3], &[]), true);
339 assert_eq!(is_superset(&[-1, 1, 2, 3], &[-1, 3]), true);
340
341 if cfg!(miri) {
342 // Miri is too slow
343 return;
344 }
345
346 let large = Vec::from_iter(0..100);
347 assert_eq!(is_superset(&[], &large), false);
348 assert_eq!(is_superset(&large, &[]), true);
349 assert_eq!(is_superset(&large, &[1]), true);
350 assert_eq!(is_superset(&large, &[50, 99]), true);
351 assert_eq!(is_superset(&large, &[100]), false);
352 assert_eq!(is_superset(&large, &[0, 99]), true);
353 assert_eq!(is_superset(&[-1], &large), false);
354 assert_eq!(is_superset(&[0], &large), false);
355 assert_eq!(is_superset(&[99, 100], &large), false);
356 }
357
358 #[test]
test_retain()359 fn test_retain() {
360 let mut set = BTreeSet::from([1, 2, 3, 4, 5, 6]);
361 set.retain(|&k| k % 2 == 0);
362 assert_eq!(set.len(), 3);
363 assert!(set.contains(&2));
364 assert!(set.contains(&4));
365 assert!(set.contains(&6));
366 }
367
368 #[test]
test_extract_if()369 fn test_extract_if() {
370 let mut x = BTreeSet::from([1]);
371 let mut y = BTreeSet::from([1]);
372
373 x.extract_if(|_| true).for_each(drop);
374 y.extract_if(|_| false).for_each(drop);
375 assert_eq!(x.len(), 0);
376 assert_eq!(y.len(), 1);
377 }
378
379 #[test]
380 #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
test_extract_if_drop_panic_leak()381 fn test_extract_if_drop_panic_leak() {
382 let a = CrashTestDummy::new(0);
383 let b = CrashTestDummy::new(1);
384 let c = CrashTestDummy::new(2);
385 let mut set = BTreeSet::new();
386 set.insert(a.spawn(Panic::Never));
387 set.insert(b.spawn(Panic::InDrop));
388 set.insert(c.spawn(Panic::Never));
389
390 catch_unwind(move || set.extract_if(|dummy| dummy.query(true)).for_each(drop)).ok();
391
392 assert_eq!(a.queried(), 1);
393 assert_eq!(b.queried(), 1);
394 assert_eq!(c.queried(), 0);
395 assert_eq!(a.dropped(), 1);
396 assert_eq!(b.dropped(), 1);
397 assert_eq!(c.dropped(), 1);
398 }
399
400 #[test]
401 #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")]
test_extract_if_pred_panic_leak()402 fn test_extract_if_pred_panic_leak() {
403 let a = CrashTestDummy::new(0);
404 let b = CrashTestDummy::new(1);
405 let c = CrashTestDummy::new(2);
406 let mut set = BTreeSet::new();
407 set.insert(a.spawn(Panic::Never));
408 set.insert(b.spawn(Panic::InQuery));
409 set.insert(c.spawn(Panic::InQuery));
410
411 catch_unwind(AssertUnwindSafe(|| set.extract_if(|dummy| dummy.query(true)).for_each(drop)))
412 .ok();
413
414 assert_eq!(a.queried(), 1);
415 assert_eq!(b.queried(), 1);
416 assert_eq!(c.queried(), 0);
417 assert_eq!(a.dropped(), 1);
418 assert_eq!(b.dropped(), 0);
419 assert_eq!(c.dropped(), 0);
420 assert_eq!(set.len(), 2);
421 assert_eq!(set.first().unwrap().id(), 1);
422 assert_eq!(set.last().unwrap().id(), 2);
423 }
424
425 #[test]
test_clear()426 fn test_clear() {
427 let mut x = BTreeSet::new();
428 x.insert(1);
429
430 x.clear();
431 assert!(x.is_empty());
432 }
433 #[test]
test_remove()434 fn test_remove() {
435 let mut x = BTreeSet::new();
436 assert!(x.is_empty());
437
438 x.insert(1);
439 x.insert(2);
440 x.insert(3);
441 x.insert(4);
442
443 assert_eq!(x.remove(&2), true);
444 assert_eq!(x.remove(&0), false);
445 assert_eq!(x.remove(&5), false);
446 assert_eq!(x.remove(&1), true);
447 assert_eq!(x.remove(&2), false);
448 assert_eq!(x.remove(&3), true);
449 assert_eq!(x.remove(&4), true);
450 assert_eq!(x.remove(&4), false);
451 assert!(x.is_empty());
452 }
453
454 #[test]
test_zip()455 fn test_zip() {
456 let mut x = BTreeSet::new();
457 x.insert(5);
458 x.insert(12);
459 x.insert(11);
460
461 let mut y = BTreeSet::new();
462 y.insert("foo");
463 y.insert("bar");
464
465 let x = x;
466 let y = y;
467 let mut z = x.iter().zip(&y);
468
469 assert_eq!(z.next().unwrap(), (&5, &("bar")));
470 assert_eq!(z.next().unwrap(), (&11, &("foo")));
471 assert!(z.next().is_none());
472 }
473
474 #[test]
test_from_iter()475 fn test_from_iter() {
476 let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
477
478 let set = BTreeSet::from_iter(xs.iter());
479
480 for x in &xs {
481 assert!(set.contains(x));
482 }
483 }
484
485 #[test]
test_show()486 fn test_show() {
487 let mut set = BTreeSet::new();
488 let empty = BTreeSet::<i32>::new();
489
490 set.insert(1);
491 set.insert(2);
492
493 let set_str = format!("{set:?}");
494
495 assert_eq!(set_str, "{1, 2}");
496 assert_eq!(format!("{empty:?}"), "{}");
497 }
498
499 #[test]
test_extend_ref()500 fn test_extend_ref() {
501 let mut a = BTreeSet::new();
502 a.insert(1);
503
504 a.extend(&[2, 3, 4]);
505
506 assert_eq!(a.len(), 4);
507 assert!(a.contains(&1));
508 assert!(a.contains(&2));
509 assert!(a.contains(&3));
510 assert!(a.contains(&4));
511
512 let mut b = BTreeSet::new();
513 b.insert(5);
514 b.insert(6);
515
516 a.extend(&b);
517
518 assert_eq!(a.len(), 6);
519 assert!(a.contains(&1));
520 assert!(a.contains(&2));
521 assert!(a.contains(&3));
522 assert!(a.contains(&4));
523 assert!(a.contains(&5));
524 assert!(a.contains(&6));
525 }
526
527 #[test]
test_recovery()528 fn test_recovery() {
529 #[derive(Debug)]
530 struct Foo(&'static str, i32);
531
532 impl PartialEq for Foo {
533 fn eq(&self, other: &Self) -> bool {
534 self.0 == other.0
535 }
536 }
537
538 impl Eq for Foo {}
539
540 impl PartialOrd for Foo {
541 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
542 self.0.partial_cmp(&other.0)
543 }
544 }
545
546 impl Ord for Foo {
547 fn cmp(&self, other: &Self) -> Ordering {
548 self.0.cmp(&other.0)
549 }
550 }
551
552 let mut s = BTreeSet::new();
553 assert_eq!(s.replace(Foo("a", 1)), None);
554 assert_eq!(s.len(), 1);
555 assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
556 assert_eq!(s.len(), 1);
557
558 {
559 let mut it = s.iter();
560 assert_eq!(it.next(), Some(&Foo("a", 2)));
561 assert_eq!(it.next(), None);
562 }
563
564 assert_eq!(s.get(&Foo("a", 1)), Some(&Foo("a", 2)));
565 assert_eq!(s.take(&Foo("a", 1)), Some(Foo("a", 2)));
566 assert_eq!(s.len(), 0);
567
568 assert_eq!(s.get(&Foo("a", 1)), None);
569 assert_eq!(s.take(&Foo("a", 1)), None);
570
571 assert_eq!(s.iter().next(), None);
572 }
573
574 #[allow(dead_code)]
assert_covariance()575 fn assert_covariance() {
576 fn set<'new>(v: BTreeSet<&'static str>) -> BTreeSet<&'new str> {
577 v
578 }
579 fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
580 v
581 }
582 fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
583 v
584 }
585 fn range<'a, 'new>(v: Range<'a, &'static str>) -> Range<'a, &'new str> {
586 v
587 }
588 // not applied to Difference, Intersection, SymmetricDifference, Union
589 }
590
591 #[allow(dead_code)]
assert_sync()592 fn assert_sync() {
593 fn set<T: Sync>(v: &BTreeSet<T>) -> impl Sync + '_ {
594 v
595 }
596
597 fn iter<T: Sync>(v: &BTreeSet<T>) -> impl Sync + '_ {
598 v.iter()
599 }
600
601 fn into_iter<T: Sync>(v: BTreeSet<T>) -> impl Sync {
602 v.into_iter()
603 }
604
605 fn range<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
606 v.range(..)
607 }
608
609 fn extract_if<T: Sync + Ord>(v: &mut BTreeSet<T>) -> impl Sync + '_ {
610 v.extract_if(|_| false)
611 }
612
613 fn difference<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
614 v.difference(&v)
615 }
616
617 fn intersection<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
618 v.intersection(&v)
619 }
620
621 fn symmetric_difference<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
622 v.symmetric_difference(&v)
623 }
624
625 fn union<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
626 v.union(&v)
627 }
628 }
629
630 #[allow(dead_code)]
assert_send()631 fn assert_send() {
632 fn set<T: Send>(v: BTreeSet<T>) -> impl Send {
633 v
634 }
635
636 fn iter<T: Send + Sync>(v: &BTreeSet<T>) -> impl Send + '_ {
637 v.iter()
638 }
639
640 fn into_iter<T: Send>(v: BTreeSet<T>) -> impl Send {
641 v.into_iter()
642 }
643
644 fn range<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
645 v.range(..)
646 }
647
648 fn extract_if<T: Send + Ord>(v: &mut BTreeSet<T>) -> impl Send + '_ {
649 v.extract_if(|_| false)
650 }
651
652 fn difference<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
653 v.difference(&v)
654 }
655
656 fn intersection<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
657 v.intersection(&v)
658 }
659
660 fn symmetric_difference<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
661 v.symmetric_difference(&v)
662 }
663
664 fn union<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
665 v.union(&v)
666 }
667 }
668
669 #[allow(dead_code)]
670 // Check that the member-like functions conditionally provided by #[derive()]
671 // are not overridden by genuine member functions with a different signature.
assert_derives()672 fn assert_derives() {
673 fn hash<T: Hash, H: Hasher>(v: BTreeSet<T>, state: &mut H) {
674 v.hash(state);
675 // Tested much more thoroughly outside the crate in btree_set_hash.rs
676 }
677 fn eq<T: PartialEq>(v: BTreeSet<T>) {
678 let _ = v.eq(&v);
679 }
680 fn ne<T: PartialEq>(v: BTreeSet<T>) {
681 let _ = v.ne(&v);
682 }
683 fn cmp<T: Ord>(v: BTreeSet<T>) {
684 let _ = v.cmp(&v);
685 }
686 fn min<T: Ord>(v: BTreeSet<T>, w: BTreeSet<T>) {
687 let _ = v.min(w);
688 }
689 fn max<T: Ord>(v: BTreeSet<T>, w: BTreeSet<T>) {
690 let _ = v.max(w);
691 }
692 fn clamp<T: Ord>(v: BTreeSet<T>, w: BTreeSet<T>, x: BTreeSet<T>) {
693 let _ = v.clamp(w, x);
694 }
695 fn partial_cmp<T: PartialOrd>(v: &BTreeSet<T>) {
696 let _ = v.partial_cmp(&v);
697 }
698 }
699
700 #[test]
test_ord_absence()701 fn test_ord_absence() {
702 fn set<K>(mut set: BTreeSet<K>) {
703 let _ = set.is_empty();
704 let _ = set.len();
705 set.clear();
706 let _ = set.iter();
707 let _ = set.into_iter();
708 }
709
710 fn set_debug<K: Debug>(set: BTreeSet<K>) {
711 format!("{set:?}");
712 format!("{:?}", set.iter());
713 format!("{:?}", set.into_iter());
714 }
715
716 fn set_clone<K: Clone>(mut set: BTreeSet<K>) {
717 set.clone_from(&set.clone());
718 }
719
720 #[derive(Debug, Clone)]
721 struct NonOrd;
722 set(BTreeSet::<NonOrd>::new());
723 set_debug(BTreeSet::<NonOrd>::new());
724 set_clone(BTreeSet::<NonOrd>::default());
725 }
726
727 #[test]
test_append()728 fn test_append() {
729 let mut a = BTreeSet::new();
730 a.insert(1);
731 a.insert(2);
732 a.insert(3);
733
734 let mut b = BTreeSet::new();
735 b.insert(3);
736 b.insert(4);
737 b.insert(5);
738
739 a.append(&mut b);
740
741 assert_eq!(a.len(), 5);
742 assert_eq!(b.len(), 0);
743
744 assert_eq!(a.contains(&1), true);
745 assert_eq!(a.contains(&2), true);
746 assert_eq!(a.contains(&3), true);
747 assert_eq!(a.contains(&4), true);
748 assert_eq!(a.contains(&5), true);
749 }
750
751 #[test]
test_first_last()752 fn test_first_last() {
753 let mut a = BTreeSet::new();
754 assert_eq!(a.first(), None);
755 assert_eq!(a.last(), None);
756 a.insert(1);
757 assert_eq!(a.first(), Some(&1));
758 assert_eq!(a.last(), Some(&1));
759 a.insert(2);
760 assert_eq!(a.first(), Some(&1));
761 assert_eq!(a.last(), Some(&2));
762 for i in 3..=12 {
763 a.insert(i);
764 }
765 assert_eq!(a.first(), Some(&1));
766 assert_eq!(a.last(), Some(&12));
767 assert_eq!(a.pop_first(), Some(1));
768 assert_eq!(a.pop_last(), Some(12));
769 assert_eq!(a.pop_first(), Some(2));
770 assert_eq!(a.pop_last(), Some(11));
771 assert_eq!(a.pop_first(), Some(3));
772 assert_eq!(a.pop_last(), Some(10));
773 assert_eq!(a.pop_first(), Some(4));
774 assert_eq!(a.pop_first(), Some(5));
775 assert_eq!(a.pop_first(), Some(6));
776 assert_eq!(a.pop_first(), Some(7));
777 assert_eq!(a.pop_first(), Some(8));
778 assert_eq!(a.clone().pop_last(), Some(9));
779 assert_eq!(a.pop_first(), Some(9));
780 assert_eq!(a.pop_first(), None);
781 assert_eq!(a.pop_last(), None);
782 }
783
784 // Unlike the function with the same name in map/tests, returns no values.
785 // Which also means it returns different predetermined pseudo-random keys,
786 // and the test cases using this function explore slightly different trees.
rand_data(len: usize) -> Vec<u32>787 fn rand_data(len: usize) -> Vec<u32> {
788 let mut rng = DeterministicRng::new();
789 Vec::from_iter((0..len).map(|_| rng.next()))
790 }
791
792 #[test]
test_split_off_empty_right()793 fn test_split_off_empty_right() {
794 let mut data = rand_data(173);
795
796 let mut set = BTreeSet::from_iter(data.clone());
797 let right = set.split_off(&(data.iter().max().unwrap() + 1));
798
799 data.sort();
800 assert!(set.into_iter().eq(data));
801 assert!(right.into_iter().eq(None));
802 }
803
804 #[test]
test_split_off_empty_left()805 fn test_split_off_empty_left() {
806 let mut data = rand_data(314);
807
808 let mut set = BTreeSet::from_iter(data.clone());
809 let right = set.split_off(data.iter().min().unwrap());
810
811 data.sort();
812 assert!(set.into_iter().eq(None));
813 assert!(right.into_iter().eq(data));
814 }
815
816 #[test]
test_split_off_large_random_sorted()817 fn test_split_off_large_random_sorted() {
818 // Miri is too slow
819 let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) };
820 // special case with maximum height.
821 data.sort();
822
823 let mut set = BTreeSet::from_iter(data.clone());
824 let key = data[data.len() / 2];
825 let right = set.split_off(&key);
826
827 assert!(set.into_iter().eq(data.clone().into_iter().filter(|x| *x < key)));
828 assert!(right.into_iter().eq(data.into_iter().filter(|x| *x >= key)));
829 }
830
831 #[test]
from_array()832 fn from_array() {
833 let set = BTreeSet::from([1, 2, 3, 4]);
834 let unordered_duplicates = BTreeSet::from([4, 1, 4, 3, 2]);
835 assert_eq!(set, unordered_duplicates);
836 }
837
838 #[should_panic(expected = "range start is greater than range end in BTreeSet")]
839 #[test]
test_range_panic_1()840 fn test_range_panic_1() {
841 let mut set = BTreeSet::new();
842 set.insert(3);
843 set.insert(5);
844 set.insert(8);
845
846 let _invalid_range = set.range((Included(&8), Included(&3)));
847 }
848
849 #[should_panic(expected = "range start and end are equal and excluded in BTreeSet")]
850 #[test]
test_range_panic_2()851 fn test_range_panic_2() {
852 let mut set = BTreeSet::new();
853 set.insert(3);
854 set.insert(5);
855 set.insert(8);
856
857 let _invalid_range = set.range((Excluded(&5), Excluded(&5)));
858 }
859