-// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
use std::collections::BTreeSet;
-
use std::iter::FromIterator;
+
use super::DeterministicRng;
#[test]
m.insert(1);
m.insert(2);
- assert!(m.clone() == m);
+ assert_eq!(m.clone(), m);
}
#[test]
fn test_hash() {
+ use crate::hash;
+
let mut x = BTreeSet::new();
let mut y = BTreeSet::new();
y.insert(2);
y.insert(1);
- assert!(::hash(&x) == ::hash(&y));
+ assert_eq!(hash(&x), hash(&y));
}
fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F)
f(&set_a,
&set_b,
&mut |&x| {
- assert_eq!(x, expected[i]);
+ if i < expected.len() {
+ assert_eq!(x, expected[i]);
+ }
i += 1;
true
});
check_intersection(&[11, 1, 3, 77, 103, 5, -5],
&[2, 11, 77, -9, -42, 5, 3],
&[3, 5, 11, 77]);
+
+ if cfg!(miri) { // Miri is too slow
+ return;
+ }
+
+ let large = (0..100).collect::<Vec<_>>();
+ check_intersection(&[], &large, &[]);
+ check_intersection(&large, &[], &[]);
+ check_intersection(&[-1], &large, &[]);
+ check_intersection(&large, &[-1], &[]);
+ check_intersection(&[0], &large, &[0]);
+ check_intersection(&large, &[0], &[0]);
+ check_intersection(&[99], &large, &[99]);
+ check_intersection(&large, &[99], &[99]);
+ check_intersection(&[100], &large, &[]);
+ check_intersection(&large, &[100], &[]);
+ check_intersection(&[11, 5000, 1, 3, 77, 8924],
+ &large,
+ &[1, 3, 11, 77]);
+}
+
+#[test]
+fn test_intersection_size_hint() {
+ let x: BTreeSet<i32> = [3, 4].iter().copied().collect();
+ let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
+ let mut iter = x.intersection(&y);
+ assert_eq!(iter.size_hint(), (1, Some(1)));
+ assert_eq!(iter.next(), Some(&3));
+ assert_eq!(iter.size_hint(), (0, Some(0)));
+ assert_eq!(iter.next(), None);
+
+ iter = y.intersection(&y);
+ assert_eq!(iter.size_hint(), (0, Some(3)));
+ assert_eq!(iter.next(), Some(&1));
+ assert_eq!(iter.size_hint(), (0, Some(2)));
}
#[test]
check_difference(&[1, 12], &[], &[1, 12]);
check_difference(&[], &[1, 2, 3, 9], &[]);
check_difference(&[1, 3, 5, 9, 11], &[3, 9], &[1, 5, 11]);
+ check_difference(&[1, 3, 5, 9, 11], &[3, 6, 9], &[1, 5, 11]);
+ check_difference(&[1, 3, 5, 9, 11], &[0, 1], &[3, 5, 9, 11]);
+ check_difference(&[1, 3, 5, 9, 11], &[11, 12], &[1, 3, 5, 9]);
check_difference(&[-5, 11, 22, 33, 40, 42],
&[-12, -5, 14, 23, 34, 38, 39, 50],
&[11, 22, 33, 40, 42]);
+
+ if cfg!(miri) { // Miri is too slow
+ return;
+ }
+
+ let large = (0..100).collect::<Vec<_>>();
+ check_difference(&[], &large, &[]);
+ check_difference(&[-1], &large, &[-1]);
+ check_difference(&[0], &large, &[]);
+ check_difference(&[99], &large, &[]);
+ check_difference(&[100], &large, &[100]);
+ check_difference(&[11, 5000, 1, 3, 77, 8924],
+ &large,
+ &[5000, 8924]);
+ check_difference(&large, &[], &large);
+ check_difference(&large, &[-1], &large);
+ check_difference(&large, &[100], &large);
+}
+
+#[test]
+fn test_difference_size_hint() {
+ let s246: BTreeSet<i32> = [2, 4, 6].iter().copied().collect();
+ let s23456: BTreeSet<i32> = (2..=6).collect();
+ let mut iter = s246.difference(&s23456);
+ assert_eq!(iter.size_hint(), (0, Some(3)));
+ assert_eq!(iter.next(), None);
+
+ let s12345: BTreeSet<i32> = (1..=5).collect();
+ iter = s246.difference(&s12345);
+ assert_eq!(iter.size_hint(), (0, Some(3)));
+ assert_eq!(iter.next(), Some(&6));
+ assert_eq!(iter.size_hint(), (0, Some(0)));
+ assert_eq!(iter.next(), None);
+
+ let s34567: BTreeSet<i32> = (3..=7).collect();
+ iter = s246.difference(&s34567);
+ assert_eq!(iter.size_hint(), (0, Some(3)));
+ assert_eq!(iter.next(), Some(&2));
+ assert_eq!(iter.size_hint(), (0, Some(2)));
+ assert_eq!(iter.next(), None);
+
+ let s1: BTreeSet<i32> = (-9..=1).collect();
+ iter = s246.difference(&s1);
+ assert_eq!(iter.size_hint(), (3, Some(3)));
+
+ let s2: BTreeSet<i32> = (-9..=2).collect();
+ iter = s246.difference(&s2);
+ assert_eq!(iter.size_hint(), (2, Some(2)));
+ assert_eq!(iter.next(), Some(&4));
+ assert_eq!(iter.size_hint(), (1, Some(1)));
+
+ let s23: BTreeSet<i32> = (2..=3).collect();
+ iter = s246.difference(&s23);
+ assert_eq!(iter.size_hint(), (1, Some(3)));
+ assert_eq!(iter.next(), Some(&4));
+ assert_eq!(iter.size_hint(), (1, Some(1)));
+
+ let s4: BTreeSet<i32> = (4..=4).collect();
+ iter = s246.difference(&s4);
+ assert_eq!(iter.size_hint(), (2, Some(3)));
+ assert_eq!(iter.next(), Some(&2));
+ assert_eq!(iter.size_hint(), (1, Some(2)));
+ assert_eq!(iter.next(), Some(&6));
+ assert_eq!(iter.size_hint(), (0, Some(0)));
+ assert_eq!(iter.next(), None);
+
+ let s56: BTreeSet<i32> = (5..=6).collect();
+ iter = s246.difference(&s56);
+ assert_eq!(iter.size_hint(), (1, Some(3)));
+ assert_eq!(iter.next(), Some(&2));
+ assert_eq!(iter.size_hint(), (0, Some(2)));
+
+ let s6: BTreeSet<i32> = (6..=19).collect();
+ iter = s246.difference(&s6);
+ assert_eq!(iter.size_hint(), (2, Some(2)));
+ assert_eq!(iter.next(), Some(&2));
+ assert_eq!(iter.size_hint(), (1, Some(1)));
+
+ let s7: BTreeSet<i32> = (7..=19).collect();
+ iter = s246.difference(&s7);
+ assert_eq!(iter.size_hint(), (3, Some(3)));
}
#[test]
&[-2, 1, 5, 11, 14, 22]);
}
+#[test]
+fn test_symmetric_difference_size_hint() {
+ let x: BTreeSet<i32> = [2, 4].iter().copied().collect();
+ let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
+ let mut iter = x.symmetric_difference(&y);
+ assert_eq!(iter.size_hint(), (0, Some(5)));
+ assert_eq!(iter.next(), Some(&1));
+ assert_eq!(iter.size_hint(), (0, Some(4)));
+ assert_eq!(iter.next(), Some(&3));
+ assert_eq!(iter.size_hint(), (0, Some(1)));
+}
+
#[test]
fn test_union() {
fn check_union(a: &[i32], b: &[i32], expected: &[i32]) {
&[-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]);
}
+#[test]
+fn test_union_size_hint() {
+ let x: BTreeSet<i32> = [2, 4].iter().copied().collect();
+ let y: BTreeSet<i32> = [1, 2, 3].iter().copied().collect();
+ let mut iter = x.union(&y);
+ assert_eq!(iter.size_hint(), (3, Some(5)));
+ assert_eq!(iter.next(), Some(&1));
+ assert_eq!(iter.size_hint(), (2, Some(4)));
+ assert_eq!(iter.next(), Some(&2));
+ assert_eq!(iter.size_hint(), (1, Some(2)));
+}
+
+#[test]
+// Only tests the simple function definition with respect to intersection
+fn test_is_disjoint() {
+ let one = [1].iter().collect::<BTreeSet<_>>();
+ let two = [2].iter().collect::<BTreeSet<_>>();
+ assert!(one.is_disjoint(&two));
+}
+
+#[test]
+// Also implicitly tests the trivial function definition of is_superset
+fn test_is_subset() {
+ fn is_subset(a: &[i32], b: &[i32]) -> bool {
+ let set_a = a.iter().collect::<BTreeSet<_>>();
+ let set_b = b.iter().collect::<BTreeSet<_>>();
+ set_a.is_subset(&set_b)
+ }
+
+ assert_eq!(is_subset(&[], &[]), true);
+ assert_eq!(is_subset(&[], &[1, 2]), true);
+ assert_eq!(is_subset(&[0], &[1, 2]), false);
+ assert_eq!(is_subset(&[1], &[1, 2]), true);
+ assert_eq!(is_subset(&[2], &[1, 2]), true);
+ assert_eq!(is_subset(&[3], &[1, 2]), false);
+ assert_eq!(is_subset(&[1, 2], &[1]), false);
+ assert_eq!(is_subset(&[1, 2], &[1, 2]), true);
+ assert_eq!(is_subset(&[1, 2], &[2, 3]), false);
+ assert_eq!(is_subset(&[-5, 11, 22, 33, 40, 42],
+ &[-12, -5, 11, 14, 22, 23, 33, 34, 38, 39, 40, 42]),
+ true);
+ assert_eq!(is_subset(&[-5, 11, 22, 33, 40, 42],
+ &[-12, -5, 11, 14, 22, 23, 34, 38]),
+ false);
+
+ if cfg!(miri) { // Miri is too slow
+ return;
+ }
+
+ let large = (0..100).collect::<Vec<_>>();
+ assert_eq!(is_subset(&[], &large), true);
+ assert_eq!(is_subset(&large, &[]), false);
+ assert_eq!(is_subset(&[-1], &large), false);
+ assert_eq!(is_subset(&[0], &large), true);
+ assert_eq!(is_subset(&[1, 2], &large), true);
+ assert_eq!(is_subset(&[99, 100], &large), false);
+}
+
#[test]
fn test_zip() {
let mut x = BTreeSet::new();
assert_eq!(a.contains(&5), true);
}
+#[test]
+fn test_first_last() {
+ let mut a = BTreeSet::new();
+ assert_eq!(a.first(), None);
+ assert_eq!(a.last(), None);
+ a.insert(1);
+ assert_eq!(a.first(), Some(&1));
+ assert_eq!(a.last(), Some(&1));
+ a.insert(2);
+ assert_eq!(a.first(), Some(&1));
+ assert_eq!(a.last(), Some(&2));
+ a.insert(3);
+ assert_eq!(a.first(), Some(&1));
+ assert_eq!(a.last(), Some(&3));
+
+ assert_eq!(a.len(), 3);
+ assert_eq!(a.pop_first(), Some(1));
+ assert_eq!(a.len(), 2);
+ assert_eq!(a.pop_last(), Some(3));
+ assert_eq!(a.len(), 1);
+ assert_eq!(a.pop_first(), Some(2));
+ assert_eq!(a.len(), 0);
+ assert_eq!(a.pop_last(), None);
+ assert_eq!(a.len(), 0);
+ assert_eq!(a.pop_first(), None);
+ assert_eq!(a.len(), 0);
+}
+
fn rand_data(len: usize) -> Vec<u32> {
let mut rng = DeterministicRng::new();
Vec::from_iter((0..len).map(|_| rng.next()))
#[test]
fn test_split_off_large_random_sorted() {
+ #[cfg(not(miri))] // Miri is too slow
let mut data = rand_data(1529);
+ #[cfg(miri)]
+ let mut data = rand_data(529);
// special case with maximum height.
data.sort();