library/std/src/collections/hash/set/tests.rs

   1 use super::super::map::RandomState;
   2 use super::HashSet;
   3
   4 use crate::panic::{catch_unwind, AssertUnwindSafe};
   5 use crate::sync::atomic::{AtomicU32, Ordering};
   6
   7 #[test]
   8 fn test_zero_capacities() {
   9     type HS = HashSet<i32>;
  10
  11     let s = HS::new();
  12     assert_eq!(s.capacity(), 0);
  13
  14     let s = HS::default();
  15     assert_eq!(s.capacity(), 0);
  16
  17     let s = HS::with_hasher(RandomState::new());
  18     assert_eq!(s.capacity(), 0);
  19
  20     let s = HS::with_capacity(0);
  21     assert_eq!(s.capacity(), 0);
  22
  23     let s = HS::with_capacity_and_hasher(0, RandomState::new());
  24     assert_eq!(s.capacity(), 0);
  25
  26     let mut s = HS::new();
  27     s.insert(1);
  28     s.insert(2);
  29     s.remove(&1);
  30     s.remove(&2);
  31     s.shrink_to_fit();
  32     assert_eq!(s.capacity(), 0);
  33
  34     let mut s = HS::new();
  35     s.reserve(0);
  36     assert_eq!(s.capacity(), 0);
  37 }
  38
  39 #[test]
  40 fn test_disjoint() {
  41     let mut xs = HashSet::new();
  42     let mut ys = HashSet::new();
  43     assert!(xs.is_disjoint(&ys));
  44     assert!(ys.is_disjoint(&xs));
  45     assert!(xs.insert(5));
  46     assert!(ys.insert(11));
  47     assert!(xs.is_disjoint(&ys));
  48     assert!(ys.is_disjoint(&xs));
  49     assert!(xs.insert(7));
  50     assert!(xs.insert(19));
  51     assert!(xs.insert(4));
  52     assert!(ys.insert(2));
  53     assert!(ys.insert(-11));
  54     assert!(xs.is_disjoint(&ys));
  55     assert!(ys.is_disjoint(&xs));
  56     assert!(ys.insert(7));
  57     assert!(!xs.is_disjoint(&ys));
  58     assert!(!ys.is_disjoint(&xs));
  59 }
  60
  61 #[test]
  62 fn test_subset_and_superset() {
  63     let mut a = HashSet::new();
  64     assert!(a.insert(0));
  65     assert!(a.insert(5));
  66     assert!(a.insert(11));
  67     assert!(a.insert(7));
  68
  69     let mut b = HashSet::new();
  70     assert!(b.insert(0));
  71     assert!(b.insert(7));
  72     assert!(b.insert(19));
  73     assert!(b.insert(250));
  74     assert!(b.insert(11));
  75     assert!(b.insert(200));
  76
  77     assert!(!a.is_subset(&b));
  78     assert!(!a.is_superset(&b));
  79     assert!(!b.is_subset(&a));
  80     assert!(!b.is_superset(&a));
  81
  82     assert!(b.insert(5));
  83
  84     assert!(a.is_subset(&b));
  85     assert!(!a.is_superset(&b));
  86     assert!(!b.is_subset(&a));
  87     assert!(b.is_superset(&a));
  88 }
  89
  90 #[test]
  91 fn test_iterate() {
  92     let mut a = HashSet::new();
  93     for i in 0..32 {
  94         assert!(a.insert(i));
  95     }
  96     let mut observed: u32 = 0;
  97     for k in &a {
  98         observed |= 1 << *k;
  99     }
 100     assert_eq!(observed, 0xFFFF_FFFF);
 101 }
 102
 103 #[test]
 104 fn test_intersection() {
 105     let mut a = HashSet::new();
 106     let mut b = HashSet::new();
 107     assert!(a.intersection(&b).next().is_none());
 108
 109     assert!(a.insert(11));
 110     assert!(a.insert(1));
 111     assert!(a.insert(3));
 112     assert!(a.insert(77));
 113     assert!(a.insert(103));
 114     assert!(a.insert(5));
 115     assert!(a.insert(-5));
 116
 117     assert!(b.insert(2));
 118     assert!(b.insert(11));
 119     assert!(b.insert(77));
 120     assert!(b.insert(-9));
 121     assert!(b.insert(-42));
 122     assert!(b.insert(5));
 123     assert!(b.insert(3));
 124
 125     let mut i = 0;
 126     let expected = [3, 5, 11, 77];
 127     for x in a.intersection(&b) {
 128         assert!(expected.contains(x));
 129         i += 1
 130     }
 131     assert_eq!(i, expected.len());
 132
 133     assert!(a.insert(9)); // make a bigger than b
 134
 135     i = 0;
 136     for x in a.intersection(&b) {
 137         assert!(expected.contains(x));
 138         i += 1
 139     }
 140     assert_eq!(i, expected.len());
 141
 142     i = 0;
 143     for x in b.intersection(&a) {
 144         assert!(expected.contains(x));
 145         i += 1
 146     }
 147     assert_eq!(i, expected.len());
 148 }
 149
 150 #[test]
 151 fn test_difference() {
 152     let mut a = HashSet::new();
 153     let mut b = HashSet::new();
 154
 155     assert!(a.insert(1));
 156     assert!(a.insert(3));
 157     assert!(a.insert(5));
 158     assert!(a.insert(9));
 159     assert!(a.insert(11));
 160
 161     assert!(b.insert(3));
 162     assert!(b.insert(9));
 163
 164     let mut i = 0;
 165     let expected = [1, 5, 11];
 166     for x in a.difference(&b) {
 167         assert!(expected.contains(x));
 168         i += 1
 169     }
 170     assert_eq!(i, expected.len());
 171 }
 172
 173 #[test]
 174 fn test_symmetric_difference() {
 175     let mut a = HashSet::new();
 176     let mut b = HashSet::new();
 177
 178     assert!(a.insert(1));
 179     assert!(a.insert(3));
 180     assert!(a.insert(5));
 181     assert!(a.insert(9));
 182     assert!(a.insert(11));
 183
 184     assert!(b.insert(-2));
 185     assert!(b.insert(3));
 186     assert!(b.insert(9));
 187     assert!(b.insert(14));
 188     assert!(b.insert(22));
 189
 190     let mut i = 0;
 191     let expected = [-2, 1, 5, 11, 14, 22];
 192     for x in a.symmetric_difference(&b) {
 193         assert!(expected.contains(x));
 194         i += 1
 195     }
 196     assert_eq!(i, expected.len());
 197 }
 198
 199 #[test]
 200 fn test_union() {
 201     let mut a = HashSet::new();
 202     let mut b = HashSet::new();
 203     assert!(a.union(&b).next().is_none());
 204     assert!(b.union(&a).next().is_none());
 205
 206     assert!(a.insert(1));
 207     assert!(a.insert(3));
 208     assert!(a.insert(11));
 209     assert!(a.insert(16));
 210     assert!(a.insert(19));
 211     assert!(a.insert(24));
 212
 213     assert!(b.insert(-2));
 214     assert!(b.insert(1));
 215     assert!(b.insert(5));
 216     assert!(b.insert(9));
 217     assert!(b.insert(13));
 218     assert!(b.insert(19));
 219
 220     let mut i = 0;
 221     let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
 222     for x in a.union(&b) {
 223         assert!(expected.contains(x));
 224         i += 1
 225     }
 226     assert_eq!(i, expected.len());
 227
 228     assert!(a.insert(9)); // make a bigger than b
 229     assert!(a.insert(5));
 230
 231     i = 0;
 232     for x in a.union(&b) {
 233         assert!(expected.contains(x));
 234         i += 1
 235     }
 236     assert_eq!(i, expected.len());
 237
 238     i = 0;
 239     for x in b.union(&a) {
 240         assert!(expected.contains(x));
 241         i += 1
 242     }
 243     assert_eq!(i, expected.len());
 244 }
 245
 246 #[test]
 247 fn test_from_iter() {
 248     let xs = [1, 2, 2, 3, 4, 5, 6, 7, 8, 9];
 249
 250     let set: HashSet<_> = xs.iter().cloned().collect();
 251
 252     for x in &xs {
 253         assert!(set.contains(x));
 254     }
 255
 256     assert_eq!(set.iter().len(), xs.len() - 1);
 257 }
 258
 259 #[test]
 260 fn test_move_iter() {
 261     let hs = {
 262         let mut hs = HashSet::new();
 263
 264         hs.insert('a');
 265         hs.insert('b');
 266
 267         hs
 268     };
 269
 270     let v = hs.into_iter().collect::<Vec<char>>();
 271     assert!(v == ['a', 'b'] || v == ['b', 'a']);
 272 }
 273
 274 #[test]
 275 fn test_eq() {
 276     // These constants once happened to expose a bug in insert().
 277     // I'm keeping them around to prevent a regression.
 278     let mut s1 = HashSet::new();
 279
 280     s1.insert(1);
 281     s1.insert(2);
 282     s1.insert(3);
 283
 284     let mut s2 = HashSet::new();
 285
 286     s2.insert(1);
 287     s2.insert(2);
 288
 289     assert!(s1 != s2);
 290
 291     s2.insert(3);
 292
 293     assert_eq!(s1, s2);
 294 }
 295
 296 #[test]
 297 fn test_show() {
 298     let mut set = HashSet::new();
 299     let empty = HashSet::<i32>::new();
 300
 301     set.insert(1);
 302     set.insert(2);
 303
 304     let set_str = format!("{:?}", set);
 305
 306     assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
 307     assert_eq!(format!("{:?}", empty), "{}");
 308 }
 309
 310 #[test]
 311 fn test_trivial_drain() {
 312     let mut s = HashSet::<i32>::new();
 313     for _ in s.drain() {}
 314     assert!(s.is_empty());
 315     drop(s);
 316
 317     let mut s = HashSet::<i32>::new();
 318     drop(s.drain());
 319     assert!(s.is_empty());
 320 }
 321
 322 #[test]
 323 fn test_drain() {
 324     let mut s: HashSet<_> = (1..100).collect();
 325
 326     // try this a bunch of times to make sure we don't screw up internal state.
 327     for _ in 0..20 {
 328         assert_eq!(s.len(), 99);
 329
 330         {
 331             let mut last_i = 0;
 332             let mut d = s.drain();
 333             for (i, x) in d.by_ref().take(50).enumerate() {
 334                 last_i = i;
 335                 assert!(x != 0);
 336             }
 337             assert_eq!(last_i, 49);
 338         }
 339
 340         for _ in &s {
 341             panic!("s should be empty!");
 342         }
 343
 344         // reset to try again.
 345         s.extend(1..100);
 346     }
 347 }
 348
 349 #[test]
 350 fn test_replace() {
 351     use crate::hash;
 352
 353     #[derive(Debug)]
 354     struct Foo(&'static str, i32);
 355
 356     impl PartialEq for Foo {
 357         fn eq(&self, other: &Self) -> bool {
 358             self.0 == other.0
 359         }
 360     }
 361
 362     impl Eq for Foo {}
 363
 364     impl hash::Hash for Foo {
 365         fn hash<H: hash::Hasher>(&self, h: &mut H) {
 366             self.0.hash(h);
 367         }
 368     }
 369
 370     let mut s = HashSet::new();
 371     assert_eq!(s.replace(Foo("a", 1)), None);
 372     assert_eq!(s.len(), 1);
 373     assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
 374     assert_eq!(s.len(), 1);
 375
 376     let mut it = s.iter();
 377     assert_eq!(it.next(), Some(&Foo("a", 2)));
 378     assert_eq!(it.next(), None);
 379 }
 380
 381 #[test]
 382 fn test_extend_ref() {
 383     let mut a = HashSet::new();
 384     a.insert(1);
 385
 386     a.extend(&[2, 3, 4]);
 387
 388     assert_eq!(a.len(), 4);
 389     assert!(a.contains(&1));
 390     assert!(a.contains(&2));
 391     assert!(a.contains(&3));
 392     assert!(a.contains(&4));
 393
 394     let mut b = HashSet::new();
 395     b.insert(5);
 396     b.insert(6);
 397
 398     a.extend(&b);
 399
 400     assert_eq!(a.len(), 6);
 401     assert!(a.contains(&1));
 402     assert!(a.contains(&2));
 403     assert!(a.contains(&3));
 404     assert!(a.contains(&4));
 405     assert!(a.contains(&5));
 406     assert!(a.contains(&6));
 407 }
 408
 409 #[test]
 410 fn test_retain() {
 411     let xs = [1, 2, 3, 4, 5, 6];
 412     let mut set: HashSet<i32> = xs.iter().cloned().collect();
 413     set.retain(|&k| k % 2 == 0);
 414     assert_eq!(set.len(), 3);
 415     assert!(set.contains(&2));
 416     assert!(set.contains(&4));
 417     assert!(set.contains(&6));
 418 }
 419
 420 #[test]
 421 fn test_drain_filter() {
 422     let mut x: HashSet<_> = [1].iter().copied().collect();
 423     let mut y: HashSet<_> = [1].iter().copied().collect();
 424
 425     x.drain_filter(|_| true);
 426     y.drain_filter(|_| false);
 427     assert_eq!(x.len(), 0);
 428     assert_eq!(y.len(), 1);
 429 }
 430
 431 #[test]
 432 fn test_drain_filter_drop_panic_leak() {
 433     static PREDS: AtomicU32 = AtomicU32::new(0);
 434     static DROPS: AtomicU32 = AtomicU32::new(0);
 435
 436     #[derive(PartialEq, Eq, PartialOrd, Hash)]
 437     struct D(i32);
 438     impl Drop for D {
 439         fn drop(&mut self) {
 440             if DROPS.fetch_add(1, Ordering::SeqCst) == 1 {
 441                 panic!("panic in `drop`");
 442             }
 443         }
 444     }
 445
 446     let mut set = (0..3).map(|i| D(i)).collect::<HashSet<_>>();
 447
 448     catch_unwind(move || {
 449         drop(set.drain_filter(|_| {
 450             PREDS.fetch_add(1, Ordering::SeqCst);
 451             true
 452         }))
 453     })
 454     .ok();
 455
 456     assert_eq!(PREDS.load(Ordering::SeqCst), 3);
 457     assert_eq!(DROPS.load(Ordering::SeqCst), 3);
 458 }
 459
 460 #[test]
 461 fn test_drain_filter_pred_panic_leak() {
 462     static PREDS: AtomicU32 = AtomicU32::new(0);
 463     static DROPS: AtomicU32 = AtomicU32::new(0);
 464
 465     #[derive(PartialEq, Eq, PartialOrd, Hash)]
 466     struct D;
 467     impl Drop for D {
 468         fn drop(&mut self) {
 469             DROPS.fetch_add(1, Ordering::SeqCst);
 470         }
 471     }
 472
 473     let mut set: HashSet<_> = (0..3).map(|_| D).collect();
 474
 475     catch_unwind(AssertUnwindSafe(|| {
 476         drop(set.drain_filter(|_| match PREDS.fetch_add(1, Ordering::SeqCst) {
 477             0 => true,
 478             _ => panic!(),
 479         }))
 480     }))
 481     .ok();
 482
 483     assert_eq!(PREDS.load(Ordering::SeqCst), 1);
 484     assert_eq!(DROPS.load(Ordering::SeqCst), 3);
 485     assert_eq!(set.len(), 0);
 486 }