New upstream version 1.41.1+dfsg1

[rustc.git] / src / liballoc / tests / btree / set.rs

diff --git a/src/liballoc/tests/btree/set.rs b/src/liballoc/tests/btree/set.rs
index 989beb3b1bfd90afbfd55626953080d31016bb39..13cd26280227ec62931762f138a55d177564696a 100644 (file)
--- a/src/liballoc/tests/btree/set.rs
+++ b/src/liballoc/tests/btree/set.rs
@@ -10,7 +10,7 @@ fn test_clone_eq() {
     m.insert(1);
     m.insert(2);
 
-    assert!(m.clone() == m);
+    assert_eq!(m.clone(), m);
 }
 
 #[test]
@@ -28,7 +28,7 @@ fn test_hash() {
     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)
@@ -48,7 +48,9 @@ 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
       });
@@ -69,20 +71,41 @@ fn test_intersection() {
     check_intersection(&[11, 1, 3, 77, 103, 5, -5],
                        &[2, 11, 77, -9, -42, 5, 3],
                        &[3, 5, 11, 77]);
-    let large = (0..1000).collect::<Vec<_>>();
+
+    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(&[999], &large, &[999]);
-    check_intersection(&large, &[999], &[999]);
-    check_intersection(&[1000], &large, &[]);
-    check_intersection(&large, &[1000], &[]);
-    check_intersection(&[11, 5000, 1, 3, 77, 8924, 103],
+    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, 103]);
+                       &[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]
@@ -95,21 +118,93 @@ fn test_difference() {
     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]);
-    let large = (0..1000).collect::<Vec<_>>();
+
+    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(&[999], &large, &[]);
-    check_difference(&[1000], &large, &[1000]);
-    check_difference(&[11, 5000, 1, 3, 77, 8924, 103],
+    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, &[1000], &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]
@@ -126,6 +221,18 @@ fn test_symmetric_difference() {
                                &[-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]) {
@@ -140,6 +247,18 @@ fn test_union() {
                 &[-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() {
@@ -149,7 +268,7 @@ fn test_is_disjoint() {
 }
 
 #[test]
-// Also tests the trivial function definition of is_superset
+// 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<_>>();
@@ -166,13 +285,24 @@ fn test_is_subset() {
     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);
-    let large = (0..1000).collect::<Vec<_>>();
+    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(&[999, 1000], &large), false);
+    assert_eq!(is_subset(&[99, 100], &large), false);
 }
 
 #[test]
@@ -340,6 +470,34 @@ fn test_append() {
     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()))
@@ -371,7 +529,10 @@ fn test_split_off_empty_left() {
 
 #[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();