1 use super::super::testing::crash_test::{CrashTestDummy, Panic};
2 use super::super::testing::rng::DeterministicRng;
5 use std::cmp::Ordering;
6 use std::hash::{Hash, Hasher};
7 use std::iter::FromIterator;
8 use std::panic::{catch_unwind, AssertUnwindSafe};
12 let mut m = BTreeSet::new();
17 assert_eq!(m.clone(), m);
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);
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));
51 fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F)
53 F: FnOnce(&BTreeSet<i32>, &BTreeSet<i32>, &mut dyn FnMut(&i32) -> bool) -> bool,
55 let mut set_a = BTreeSet::new();
56 let mut set_b = BTreeSet::new();
59 assert!(set_a.insert(*x))
62 assert!(set_b.insert(*y))
66 f(&set_a, &set_b, &mut |&x| {
67 if i < expected.len() {
68 assert_eq!(x, expected[i]);
73 assert_eq!(i, expected.len());
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))
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]);
94 let large = (0..100).collect::<Vec<_>>();
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]);
109 fn test_intersection_size_hint() {
110 let x: BTreeSet<i32> = [3, 4].iter().copied().collect();
111 let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
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);
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)));
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))
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]);
138 &[-5, 11, 22, 33, 40, 42],
139 &[-12, -5, 14, 23, 34, 38, 39, 50],
140 &[11, 22, 33, 40, 42],
148 let large = (0..100).collect::<Vec<_>>();
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);
161 fn test_difference_size_hint() {
162 let s246: BTreeSet<i32> = [2, 4, 6].iter().copied().collect();
163 let s23456: BTreeSet<i32> = (2..=6).collect();
164 let mut iter = s246.difference(&s23456);
165 assert_eq!(iter.size_hint(), (0, Some(3)));
166 assert_eq!(iter.next(), None);
168 let s12345: BTreeSet<i32> = (1..=5).collect();
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);
175 let s34567: BTreeSet<i32> = (3..=7).collect();
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);
182 let s1: BTreeSet<i32> = (-9..=1).collect();
183 iter = s246.difference(&s1);
184 assert_eq!(iter.size_hint(), (3, Some(3)));
186 let s2: BTreeSet<i32> = (-9..=2).collect();
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)));
192 let s23: BTreeSet<i32> = (2..=3).collect();
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)));
198 let s4: BTreeSet<i32> = (4..=4).collect();
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);
207 let s56: BTreeSet<i32> = (5..=6).collect();
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)));
213 let s6: BTreeSet<i32> = (6..=19).collect();
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)));
219 let s7: BTreeSet<i32> = (7..=19).collect();
220 iter = s246.difference(&s7);
221 assert_eq!(iter.size_hint(), (3, Some(3)));
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))
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]);
237 fn test_symmetric_difference_size_hint() {
238 let x: BTreeSet<i32> = [2, 4].iter().copied().collect();
239 let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
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)));
250 fn check_union(a: &[i32], b: &[i32], expected: &[i32]) {
251 check(a, b, expected, |x, y, f| x.union(y).all(f))
254 check_union(&[], &[], &[]);
255 check_union(&[1, 2, 3], &[2], &[1, 2, 3]);
256 check_union(&[2], &[1, 2, 3], &[1, 2, 3]);
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],
265 fn test_union_size_hint() {
266 let x: BTreeSet<i32> = [2, 4].iter().copied().collect();
267 let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
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)));
277 // Only tests the simple function definition with respect to intersection
278 fn test_is_disjoint() {
279 let one = [1].iter().collect::<BTreeSet<_>>();
280 let two = [2].iter().collect::<BTreeSet<_>>();
281 assert!(one.is_disjoint(&two));
285 // Also implicitly tests the trivial function definition of is_superset
286 fn test_is_subset() {
287 fn is_subset(a: &[i32], b: &[i32]) -> bool {
288 let set_a = a.iter().collect::<BTreeSet<_>>();
289 let set_b = b.iter().collect::<BTreeSet<_>>();
290 set_a.is_subset(&set_b)
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);
303 is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 33, 34, 38, 39, 40, 42]),
306 assert_eq!(is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 34, 38]), false);
313 let large = (0..100).collect::<Vec<_>>();
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);
324 let xs = [1, 2, 3, 4, 5, 6];
325 let mut set: BTreeSet<i32> = xs.iter().cloned().collect();
326 set.retain(|&k| k % 2 == 0);
327 assert_eq!(set.len(), 3);
328 assert!(set.contains(&2));
329 assert!(set.contains(&4));
330 assert!(set.contains(&6));
334 fn test_drain_filter() {
335 let mut x: BTreeSet<_> = [1].iter().copied().collect();
336 let mut y: BTreeSet<_> = [1].iter().copied().collect();
338 x.drain_filter(|_| true);
339 y.drain_filter(|_| false);
340 assert_eq!(x.len(), 0);
341 assert_eq!(y.len(), 1);
345 fn test_drain_filter_drop_panic_leak() {
346 let a = CrashTestDummy::new(0);
347 let b = CrashTestDummy::new(1);
348 let c = CrashTestDummy::new(2);
349 let mut set = BTreeSet::new();
350 set.insert(a.spawn(Panic::Never));
351 set.insert(b.spawn(Panic::InDrop));
352 set.insert(c.spawn(Panic::Never));
354 catch_unwind(move || drop(set.drain_filter(|dummy| dummy.query(true)))).ok();
356 assert_eq!(a.queried(), 1);
357 assert_eq!(b.queried(), 1);
358 assert_eq!(c.queried(), 0);
359 assert_eq!(a.dropped(), 1);
360 assert_eq!(b.dropped(), 1);
361 assert_eq!(c.dropped(), 1);
365 fn test_drain_filter_pred_panic_leak() {
366 let a = CrashTestDummy::new(0);
367 let b = CrashTestDummy::new(1);
368 let c = CrashTestDummy::new(2);
369 let mut set = BTreeSet::new();
370 set.insert(a.spawn(Panic::Never));
371 set.insert(b.spawn(Panic::InQuery));
372 set.insert(c.spawn(Panic::InQuery));
374 catch_unwind(AssertUnwindSafe(|| drop(set.drain_filter(|dummy| dummy.query(true))))).ok();
376 assert_eq!(a.queried(), 1);
377 assert_eq!(b.queried(), 1);
378 assert_eq!(c.queried(), 0);
379 assert_eq!(a.dropped(), 1);
380 assert_eq!(b.dropped(), 0);
381 assert_eq!(c.dropped(), 0);
382 assert_eq!(set.len(), 2);
383 assert_eq!(set.first().unwrap().id(), 1);
384 assert_eq!(set.last().unwrap().id(), 2);
389 let mut x = BTreeSet::new();
393 assert!(x.is_empty());
398 let mut x = BTreeSet::new();
403 let mut y = BTreeSet::new();
409 let mut z = x.iter().zip(&y);
411 assert_eq!(z.next().unwrap(), (&5, &("bar")));
412 assert_eq!(z.next().unwrap(), (&11, &("foo")));
413 assert!(z.next().is_none());
417 fn test_from_iter() {
418 let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
420 let set: BTreeSet<_> = xs.iter().cloned().collect();
423 assert!(set.contains(x));
429 let mut set = BTreeSet::new();
430 let empty = BTreeSet::<i32>::new();
435 let set_str = format!("{:?}", set);
437 assert_eq!(set_str, "{1, 2}");
438 assert_eq!(format!("{:?}", empty), "{}");
442 fn test_extend_ref() {
443 let mut a = BTreeSet::new();
446 a.extend(&[2, 3, 4]);
448 assert_eq!(a.len(), 4);
449 assert!(a.contains(&1));
450 assert!(a.contains(&2));
451 assert!(a.contains(&3));
452 assert!(a.contains(&4));
454 let mut b = BTreeSet::new();
460 assert_eq!(a.len(), 6);
461 assert!(a.contains(&1));
462 assert!(a.contains(&2));
463 assert!(a.contains(&3));
464 assert!(a.contains(&4));
465 assert!(a.contains(&5));
466 assert!(a.contains(&6));
472 struct Foo(&'static str, i32);
474 impl PartialEq for Foo {
475 fn eq(&self, other: &Self) -> bool {
482 impl PartialOrd for Foo {
483 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
484 self.0.partial_cmp(&other.0)
489 fn cmp(&self, other: &Self) -> Ordering {
494 let mut s = BTreeSet::new();
495 assert_eq!(s.replace(Foo("a", 1)), None);
496 assert_eq!(s.len(), 1);
497 assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
498 assert_eq!(s.len(), 1);
501 let mut it = s.iter();
502 assert_eq!(it.next(), Some(&Foo("a", 2)));
503 assert_eq!(it.next(), None);
506 assert_eq!(s.get(&Foo("a", 1)), Some(&Foo("a", 2)));
507 assert_eq!(s.take(&Foo("a", 1)), Some(Foo("a", 2)));
508 assert_eq!(s.len(), 0);
510 assert_eq!(s.get(&Foo("a", 1)), None);
511 assert_eq!(s.take(&Foo("a", 1)), None);
513 assert_eq!(s.iter().next(), None);
517 fn assert_covariance() {
518 fn set<'new>(v: BTreeSet<&'static str>) -> BTreeSet<&'new str> {
521 fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
524 fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
527 fn range<'a, 'new>(v: Range<'a, &'static str>) -> Range<'a, &'new str> {
530 // not applied to Difference, Intersection, SymmetricDifference, Union
535 fn set<T: Sync>(v: &BTreeSet<T>) -> impl Sync + '_ {
539 fn iter<T: Sync>(v: &BTreeSet<T>) -> impl Sync + '_ {
543 fn into_iter<T: Sync>(v: BTreeSet<T>) -> impl Sync {
547 fn range<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
551 fn drain_filter<T: Sync + Ord>(v: &mut BTreeSet<T>) -> impl Sync + '_ {
552 v.drain_filter(|_| false)
555 fn difference<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
559 fn intersection<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
563 fn symmetric_difference<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
564 v.symmetric_difference(&v)
567 fn union<T: Sync + Ord>(v: &BTreeSet<T>) -> impl Sync + '_ {
574 fn set<T: Send>(v: BTreeSet<T>) -> impl Send {
578 fn iter<T: Send + Sync>(v: &BTreeSet<T>) -> impl Send + '_ {
582 fn into_iter<T: Send>(v: BTreeSet<T>) -> impl Send {
586 fn range<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
590 fn drain_filter<T: Send + Ord>(v: &mut BTreeSet<T>) -> impl Send + '_ {
591 v.drain_filter(|_| false)
594 fn difference<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
598 fn intersection<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
602 fn symmetric_difference<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
603 v.symmetric_difference(&v)
606 fn union<T: Send + Sync + Ord>(v: &BTreeSet<T>) -> impl Send + '_ {
612 // Check that the member-like functions conditionally provided by #[derive()]
613 // are not overriden by genuine member functions with a different signature.
614 fn assert_derives() {
615 fn hash<T: Hash, H: Hasher>(v: BTreeSet<T>, state: &mut H) {
617 // Tested much more thoroughly outside the crate in btree_set_hash.rs
619 fn eq<T: PartialEq>(v: BTreeSet<T>) {
622 fn ne<T: PartialEq>(v: BTreeSet<T>) {
625 fn cmp<T: Ord>(v: BTreeSet<T>) {
628 fn min<T: Ord>(v: BTreeSet<T>, w: BTreeSet<T>) {
631 fn max<T: Ord>(v: BTreeSet<T>, w: BTreeSet<T>) {
634 fn clamp<T: Ord>(v: BTreeSet<T>, w: BTreeSet<T>, x: BTreeSet<T>) {
635 let _ = v.clamp(w, x);
637 fn partial_cmp<T: PartialOrd>(v: &BTreeSet<T>) {
638 let _ = v.partial_cmp(&v);
643 fn test_ord_absence() {
644 fn set<K>(mut set: BTreeSet<K>) {
645 let _ = set.is_empty();
649 let _ = set.into_iter();
652 fn set_debug<K: Debug>(set: BTreeSet<K>) {
653 format!("{:?}", set);
654 format!("{:?}", set.iter());
655 format!("{:?}", set.into_iter());
658 fn set_clone<K: Clone>(mut set: BTreeSet<K>) {
659 set.clone_from(&set.clone());
662 #[derive(Debug, Clone)]
664 set(BTreeSet::<NonOrd>::new());
665 set_debug(BTreeSet::<NonOrd>::new());
666 set_clone(BTreeSet::<NonOrd>::default());
671 let mut a = BTreeSet::new();
676 let mut b = BTreeSet::new();
683 assert_eq!(a.len(), 5);
684 assert_eq!(b.len(), 0);
686 assert_eq!(a.contains(&1), true);
687 assert_eq!(a.contains(&2), true);
688 assert_eq!(a.contains(&3), true);
689 assert_eq!(a.contains(&4), true);
690 assert_eq!(a.contains(&5), true);
694 fn test_first_last() {
695 let mut a = BTreeSet::new();
696 assert_eq!(a.first(), None);
697 assert_eq!(a.last(), None);
699 assert_eq!(a.first(), Some(&1));
700 assert_eq!(a.last(), Some(&1));
702 assert_eq!(a.first(), Some(&1));
703 assert_eq!(a.last(), Some(&2));
707 assert_eq!(a.first(), Some(&1));
708 assert_eq!(a.last(), Some(&12));
709 assert_eq!(a.pop_first(), Some(1));
710 assert_eq!(a.pop_last(), Some(12));
711 assert_eq!(a.pop_first(), Some(2));
712 assert_eq!(a.pop_last(), Some(11));
713 assert_eq!(a.pop_first(), Some(3));
714 assert_eq!(a.pop_last(), Some(10));
715 assert_eq!(a.pop_first(), Some(4));
716 assert_eq!(a.pop_first(), Some(5));
717 assert_eq!(a.pop_first(), Some(6));
718 assert_eq!(a.pop_first(), Some(7));
719 assert_eq!(a.pop_first(), Some(8));
720 assert_eq!(a.clone().pop_last(), Some(9));
721 assert_eq!(a.pop_first(), Some(9));
722 assert_eq!(a.pop_first(), None);
723 assert_eq!(a.pop_last(), None);
726 // Unlike the function with the same name in map/tests, returns no values.
727 // Which also means it returns different predetermined pseudo-random keys,
728 // and the test cases using this function explore slightly different trees.
729 fn rand_data(len: usize) -> Vec<u32> {
730 let mut rng = DeterministicRng::new();
731 Vec::from_iter((0..len).map(|_| rng.next()))
735 fn test_split_off_empty_right() {
736 let mut data = rand_data(173);
738 let mut set = BTreeSet::from_iter(data.clone());
739 let right = set.split_off(&(data.iter().max().unwrap() + 1));
742 assert!(set.into_iter().eq(data));
743 assert!(right.into_iter().eq(None));
747 fn test_split_off_empty_left() {
748 let mut data = rand_data(314);
750 let mut set = BTreeSet::from_iter(data.clone());
751 let right = set.split_off(data.iter().min().unwrap());
754 assert!(set.into_iter().eq(None));
755 assert!(right.into_iter().eq(data));
759 fn test_split_off_large_random_sorted() {
761 let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) };
762 // special case with maximum height.
765 let mut set = BTreeSet::from_iter(data.clone());
766 let key = data[data.len() / 2];
767 let right = set.split_off(&key);
769 assert!(set.into_iter().eq(data.clone().into_iter().filter(|x| *x < key)));
770 assert!(right.into_iter().eq(data.into_iter().filter(|x| *x >= key)));
775 let set = BTreeSet::from([1, 2, 3, 4]);
776 let unordered_duplicates = BTreeSet::from([4, 1, 4, 3, 2]);
777 assert_eq!(set, unordered_duplicates);