1 use std::collections::BTreeSet;
2 use std::iter::FromIterator;
3 use std::panic::{catch_unwind, AssertUnwindSafe};
4 use std::sync::atomic::{AtomicU32, Ordering};
6 use super::DeterministicRng;
10 let mut m = BTreeSet::new();
15 assert_eq!(m.clone(), m);
22 let mut x = BTreeSet::new();
23 let mut y = BTreeSet::new();
33 assert_eq!(hash(&x), hash(&y));
36 fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F)
38 F: FnOnce(&BTreeSet<i32>, &BTreeSet<i32>, &mut dyn FnMut(&i32) -> bool) -> bool,
40 let mut set_a = BTreeSet::new();
41 let mut set_b = BTreeSet::new();
44 assert!(set_a.insert(*x))
47 assert!(set_b.insert(*y))
51 f(&set_a, &set_b, &mut |&x| {
52 if i < expected.len() {
53 assert_eq!(x, expected[i]);
58 assert_eq!(i, expected.len());
62 fn test_intersection() {
63 fn check_intersection(a: &[i32], b: &[i32], expected: &[i32]) {
64 check(a, b, expected, |x, y, f| x.intersection(y).all(f))
67 check_intersection(&[], &[], &[]);
68 check_intersection(&[1, 2, 3], &[], &[]);
69 check_intersection(&[], &[1, 2, 3], &[]);
70 check_intersection(&[2], &[1, 2, 3], &[2]);
71 check_intersection(&[1, 2, 3], &[2], &[2]);
72 check_intersection(&[11, 1, 3, 77, 103, 5, -5], &[2, 11, 77, -9, -42, 5, 3], &[3, 5, 11, 77]);
79 let large = (0..100).collect::<Vec<_>>();
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]);
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], &large, &[1, 3, 11, 77]);
94 fn test_intersection_size_hint() {
95 let x: BTreeSet<i32> = [3, 4].iter().copied().collect();
96 let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
97 let mut iter = x.intersection(&y);
98 assert_eq!(iter.size_hint(), (1, Some(1)));
99 assert_eq!(iter.next(), Some(&3));
100 assert_eq!(iter.size_hint(), (0, Some(0)));
101 assert_eq!(iter.next(), None);
103 iter = y.intersection(&y);
104 assert_eq!(iter.size_hint(), (0, Some(3)));
105 assert_eq!(iter.next(), Some(&1));
106 assert_eq!(iter.size_hint(), (0, Some(2)));
110 fn test_difference() {
111 fn check_difference(a: &[i32], b: &[i32], expected: &[i32]) {
112 check(a, b, expected, |x, y, f| x.difference(y).all(f))
115 check_difference(&[], &[], &[]);
116 check_difference(&[1, 12], &[], &[1, 12]);
117 check_difference(&[], &[1, 2, 3, 9], &[]);
118 check_difference(&[1, 3, 5, 9, 11], &[3, 9], &[1, 5, 11]);
119 check_difference(&[1, 3, 5, 9, 11], &[3, 6, 9], &[1, 5, 11]);
120 check_difference(&[1, 3, 5, 9, 11], &[0, 1], &[3, 5, 9, 11]);
121 check_difference(&[1, 3, 5, 9, 11], &[11, 12], &[1, 3, 5, 9]);
123 &[-5, 11, 22, 33, 40, 42],
124 &[-12, -5, 14, 23, 34, 38, 39, 50],
125 &[11, 22, 33, 40, 42],
133 let large = (0..100).collect::<Vec<_>>();
134 check_difference(&[], &large, &[]);
135 check_difference(&[-1], &large, &[-1]);
136 check_difference(&[0], &large, &[]);
137 check_difference(&[99], &large, &[]);
138 check_difference(&[100], &large, &[100]);
139 check_difference(&[11, 5000, 1, 3, 77, 8924], &large, &[5000, 8924]);
140 check_difference(&large, &[], &large);
141 check_difference(&large, &[-1], &large);
142 check_difference(&large, &[100], &large);
146 fn test_difference_size_hint() {
147 let s246: BTreeSet<i32> = [2, 4, 6].iter().copied().collect();
148 let s23456: BTreeSet<i32> = (2..=6).collect();
149 let mut iter = s246.difference(&s23456);
150 assert_eq!(iter.size_hint(), (0, Some(3)));
151 assert_eq!(iter.next(), None);
153 let s12345: BTreeSet<i32> = (1..=5).collect();
154 iter = s246.difference(&s12345);
155 assert_eq!(iter.size_hint(), (0, Some(3)));
156 assert_eq!(iter.next(), Some(&6));
157 assert_eq!(iter.size_hint(), (0, Some(0)));
158 assert_eq!(iter.next(), None);
160 let s34567: BTreeSet<i32> = (3..=7).collect();
161 iter = s246.difference(&s34567);
162 assert_eq!(iter.size_hint(), (0, Some(3)));
163 assert_eq!(iter.next(), Some(&2));
164 assert_eq!(iter.size_hint(), (0, Some(2)));
165 assert_eq!(iter.next(), None);
167 let s1: BTreeSet<i32> = (-9..=1).collect();
168 iter = s246.difference(&s1);
169 assert_eq!(iter.size_hint(), (3, Some(3)));
171 let s2: BTreeSet<i32> = (-9..=2).collect();
172 iter = s246.difference(&s2);
173 assert_eq!(iter.size_hint(), (2, Some(2)));
174 assert_eq!(iter.next(), Some(&4));
175 assert_eq!(iter.size_hint(), (1, Some(1)));
177 let s23: BTreeSet<i32> = (2..=3).collect();
178 iter = s246.difference(&s23);
179 assert_eq!(iter.size_hint(), (1, Some(3)));
180 assert_eq!(iter.next(), Some(&4));
181 assert_eq!(iter.size_hint(), (1, Some(1)));
183 let s4: BTreeSet<i32> = (4..=4).collect();
184 iter = s246.difference(&s4);
185 assert_eq!(iter.size_hint(), (2, Some(3)));
186 assert_eq!(iter.next(), Some(&2));
187 assert_eq!(iter.size_hint(), (1, Some(2)));
188 assert_eq!(iter.next(), Some(&6));
189 assert_eq!(iter.size_hint(), (0, Some(0)));
190 assert_eq!(iter.next(), None);
192 let s56: BTreeSet<i32> = (5..=6).collect();
193 iter = s246.difference(&s56);
194 assert_eq!(iter.size_hint(), (1, Some(3)));
195 assert_eq!(iter.next(), Some(&2));
196 assert_eq!(iter.size_hint(), (0, Some(2)));
198 let s6: BTreeSet<i32> = (6..=19).collect();
199 iter = s246.difference(&s6);
200 assert_eq!(iter.size_hint(), (2, Some(2)));
201 assert_eq!(iter.next(), Some(&2));
202 assert_eq!(iter.size_hint(), (1, Some(1)));
204 let s7: BTreeSet<i32> = (7..=19).collect();
205 iter = s246.difference(&s7);
206 assert_eq!(iter.size_hint(), (3, Some(3)));
210 fn test_symmetric_difference() {
211 fn check_symmetric_difference(a: &[i32], b: &[i32], expected: &[i32]) {
212 check(a, b, expected, |x, y, f| x.symmetric_difference(y).all(f))
215 check_symmetric_difference(&[], &[], &[]);
216 check_symmetric_difference(&[1, 2, 3], &[2], &[1, 3]);
217 check_symmetric_difference(&[2], &[1, 2, 3], &[1, 3]);
218 check_symmetric_difference(&[1, 3, 5, 9, 11], &[-2, 3, 9, 14, 22], &[-2, 1, 5, 11, 14, 22]);
222 fn test_symmetric_difference_size_hint() {
223 let x: BTreeSet<i32> = [2, 4].iter().copied().collect();
224 let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
225 let mut iter = x.symmetric_difference(&y);
226 assert_eq!(iter.size_hint(), (0, Some(5)));
227 assert_eq!(iter.next(), Some(&1));
228 assert_eq!(iter.size_hint(), (0, Some(4)));
229 assert_eq!(iter.next(), Some(&3));
230 assert_eq!(iter.size_hint(), (0, Some(1)));
235 fn check_union(a: &[i32], b: &[i32], expected: &[i32]) {
236 check(a, b, expected, |x, y, f| x.union(y).all(f))
239 check_union(&[], &[], &[]);
240 check_union(&[1, 2, 3], &[2], &[1, 2, 3]);
241 check_union(&[2], &[1, 2, 3], &[1, 2, 3]);
243 &[1, 3, 5, 9, 11, 16, 19, 24],
244 &[-2, 1, 5, 9, 13, 19],
245 &[-2, 1, 3, 5, 9, 11, 13, 16, 19, 24],
250 fn test_union_size_hint() {
251 let x: BTreeSet<i32> = [2, 4].iter().copied().collect();
252 let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
253 let mut iter = x.union(&y);
254 assert_eq!(iter.size_hint(), (3, Some(5)));
255 assert_eq!(iter.next(), Some(&1));
256 assert_eq!(iter.size_hint(), (2, Some(4)));
257 assert_eq!(iter.next(), Some(&2));
258 assert_eq!(iter.size_hint(), (1, Some(2)));
262 // Only tests the simple function definition with respect to intersection
263 fn test_is_disjoint() {
264 let one = [1].iter().collect::<BTreeSet<_>>();
265 let two = [2].iter().collect::<BTreeSet<_>>();
266 assert!(one.is_disjoint(&two));
270 // Also implicitly tests the trivial function definition of is_superset
271 fn test_is_subset() {
272 fn is_subset(a: &[i32], b: &[i32]) -> bool {
273 let set_a = a.iter().collect::<BTreeSet<_>>();
274 let set_b = b.iter().collect::<BTreeSet<_>>();
275 set_a.is_subset(&set_b)
278 assert_eq!(is_subset(&[], &[]), true);
279 assert_eq!(is_subset(&[], &[1, 2]), true);
280 assert_eq!(is_subset(&[0], &[1, 2]), false);
281 assert_eq!(is_subset(&[1], &[1, 2]), true);
282 assert_eq!(is_subset(&[2], &[1, 2]), true);
283 assert_eq!(is_subset(&[3], &[1, 2]), false);
284 assert_eq!(is_subset(&[1, 2], &[1]), false);
285 assert_eq!(is_subset(&[1, 2], &[1, 2]), true);
286 assert_eq!(is_subset(&[1, 2], &[2, 3]), false);
288 is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 33, 34, 38, 39, 40, 42]),
291 assert_eq!(is_subset(&[-5, 11, 22, 33, 40, 42], &[-12, -5, 11, 14, 22, 23, 34, 38]), false);
298 let large = (0..100).collect::<Vec<_>>();
299 assert_eq!(is_subset(&[], &large), true);
300 assert_eq!(is_subset(&large, &[]), false);
301 assert_eq!(is_subset(&[-1], &large), false);
302 assert_eq!(is_subset(&[0], &large), true);
303 assert_eq!(is_subset(&[1, 2], &large), true);
304 assert_eq!(is_subset(&[99, 100], &large), false);
308 fn test_drain_filter() {
309 let mut x: BTreeSet<_> = [1].iter().copied().collect();
310 let mut y: BTreeSet<_> = [1].iter().copied().collect();
312 x.drain_filter(|_| true);
313 y.drain_filter(|_| false);
314 assert_eq!(x.len(), 0);
315 assert_eq!(y.len(), 1);
319 fn test_drain_filter_drop_panic_leak() {
320 static PREDS: AtomicU32 = AtomicU32::new(0);
321 static DROPS: AtomicU32 = AtomicU32::new(0);
323 #[derive(PartialEq, Eq, PartialOrd, Ord)]
327 if DROPS.fetch_add(1, Ordering::SeqCst) == 1 {
328 panic!("panic in `drop`");
333 let mut set = BTreeSet::new();
338 catch_unwind(move || {
339 drop(set.drain_filter(|d| {
340 PREDS.fetch_add(1u32 << d.0, Ordering::SeqCst);
346 assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
347 assert_eq!(DROPS.load(Ordering::SeqCst), 3);
351 fn test_drain_filter_pred_panic_leak() {
352 static PREDS: AtomicU32 = AtomicU32::new(0);
353 static DROPS: AtomicU32 = AtomicU32::new(0);
355 #[derive(PartialEq, Eq, PartialOrd, Ord)]
359 DROPS.fetch_add(1, Ordering::SeqCst);
363 let mut set = BTreeSet::new();
368 catch_unwind(AssertUnwindSafe(|| {
369 drop(set.drain_filter(|d| {
370 PREDS.fetch_add(1u32 << d.0, Ordering::SeqCst);
379 assert_eq!(PREDS.load(Ordering::SeqCst), 0x011);
380 assert_eq!(DROPS.load(Ordering::SeqCst), 1);
381 assert_eq!(set.len(), 2);
382 assert_eq!(set.first().unwrap().0, 4);
383 assert_eq!(set.last().unwrap().0, 8);
388 let mut x = BTreeSet::new();
392 assert!(x.is_empty());
397 let mut x = BTreeSet::new();
402 let mut y = BTreeSet::new();
408 let mut z = x.iter().zip(&y);
410 assert_eq!(z.next().unwrap(), (&5, &("bar")));
411 assert_eq!(z.next().unwrap(), (&11, &("foo")));
412 assert!(z.next().is_none());
416 fn test_from_iter() {
417 let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
419 let set: BTreeSet<_> = xs.iter().cloned().collect();
422 assert!(set.contains(x));
428 let mut set = BTreeSet::new();
429 let empty = BTreeSet::<i32>::new();
434 let set_str = format!("{:?}", set);
436 assert_eq!(set_str, "{1, 2}");
437 assert_eq!(format!("{:?}", empty), "{}");
441 fn test_extend_ref() {
442 let mut a = BTreeSet::new();
445 a.extend(&[2, 3, 4]);
447 assert_eq!(a.len(), 4);
448 assert!(a.contains(&1));
449 assert!(a.contains(&2));
450 assert!(a.contains(&3));
451 assert!(a.contains(&4));
453 let mut b = BTreeSet::new();
459 assert_eq!(a.len(), 6);
460 assert!(a.contains(&1));
461 assert!(a.contains(&2));
462 assert!(a.contains(&3));
463 assert!(a.contains(&4));
464 assert!(a.contains(&5));
465 assert!(a.contains(&6));
470 use std::cmp::Ordering;
473 struct Foo(&'static str, i32);
475 impl PartialEq for Foo {
476 fn eq(&self, other: &Self) -> bool {
483 impl PartialOrd for Foo {
484 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
485 self.0.partial_cmp(&other.0)
490 fn cmp(&self, other: &Self) -> Ordering {
495 let mut s = BTreeSet::new();
496 assert_eq!(s.replace(Foo("a", 1)), None);
497 assert_eq!(s.len(), 1);
498 assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
499 assert_eq!(s.len(), 1);
502 let mut it = s.iter();
503 assert_eq!(it.next(), Some(&Foo("a", 2)));
504 assert_eq!(it.next(), None);
507 assert_eq!(s.get(&Foo("a", 1)), Some(&Foo("a", 2)));
508 assert_eq!(s.take(&Foo("a", 1)), Some(Foo("a", 2)));
509 assert_eq!(s.len(), 0);
511 assert_eq!(s.get(&Foo("a", 1)), None);
512 assert_eq!(s.take(&Foo("a", 1)), None);
514 assert_eq!(s.iter().next(), None);
520 use std::collections::btree_set::{IntoIter, Iter, Range};
522 fn set<'new>(v: BTreeSet<&'static str>) -> BTreeSet<&'new str> {
525 fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
528 fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
531 fn range<'a, 'new>(v: Range<'a, &'static str>) -> Range<'a, &'new str> {
538 let mut a = BTreeSet::new();
543 let mut b = BTreeSet::new();
550 assert_eq!(a.len(), 5);
551 assert_eq!(b.len(), 0);
553 assert_eq!(a.contains(&1), true);
554 assert_eq!(a.contains(&2), true);
555 assert_eq!(a.contains(&3), true);
556 assert_eq!(a.contains(&4), true);
557 assert_eq!(a.contains(&5), true);
561 fn test_first_last() {
562 let mut a = BTreeSet::new();
563 assert_eq!(a.first(), None);
564 assert_eq!(a.last(), None);
566 assert_eq!(a.first(), Some(&1));
567 assert_eq!(a.last(), Some(&1));
569 assert_eq!(a.first(), Some(&1));
570 assert_eq!(a.last(), Some(&2));
574 assert_eq!(a.first(), Some(&1));
575 assert_eq!(a.last(), Some(&12));
576 assert_eq!(a.pop_first(), Some(1));
577 assert_eq!(a.pop_last(), Some(12));
578 assert_eq!(a.pop_first(), Some(2));
579 assert_eq!(a.pop_last(), Some(11));
580 assert_eq!(a.pop_first(), Some(3));
581 assert_eq!(a.pop_last(), Some(10));
582 assert_eq!(a.pop_first(), Some(4));
583 assert_eq!(a.pop_first(), Some(5));
584 assert_eq!(a.pop_first(), Some(6));
585 assert_eq!(a.pop_first(), Some(7));
586 assert_eq!(a.pop_first(), Some(8));
587 assert_eq!(a.clone().pop_last(), Some(9));
588 assert_eq!(a.pop_first(), Some(9));
589 assert_eq!(a.pop_first(), None);
590 assert_eq!(a.pop_last(), None);
593 fn rand_data(len: usize) -> Vec<u32> {
594 let mut rng = DeterministicRng::new();
595 Vec::from_iter((0..len).map(|_| rng.next()))
599 fn test_split_off_empty_right() {
600 let mut data = rand_data(173);
602 let mut set = BTreeSet::from_iter(data.clone());
603 let right = set.split_off(&(data.iter().max().unwrap() + 1));
606 assert!(set.into_iter().eq(data));
607 assert!(right.into_iter().eq(None));
611 fn test_split_off_empty_left() {
612 let mut data = rand_data(314);
614 let mut set = BTreeSet::from_iter(data.clone());
615 let right = set.split_off(data.iter().min().unwrap());
618 assert!(set.into_iter().eq(None));
619 assert!(right.into_iter().eq(data));
623 fn test_split_off_large_random_sorted() {
625 let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) };
626 // special case with maximum height.
629 let mut set = BTreeSet::from_iter(data.clone());
630 let key = data[data.len() / 2];
631 let right = set.split_off(&key);
633 assert!(set.into_iter().eq(data.clone().into_iter().filter(|x| *x < key)));
634 assert!(right.into_iter().eq(data.into_iter().filter(|x| *x >= key)));