src/libcollectionstest/bit/set.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use std::cmp::Ordering::{Equal, Greater, Less};
  12 use std::collections::{BitSet, BitVec};
  13
  14 #[test]
  15 fn test_bit_set_show() {
  16     let mut s = BitSet::new();
  17     s.insert(1);
  18     s.insert(10);
  19     s.insert(50);
  20     s.insert(2);
  21     assert_eq!("{1, 2, 10, 50}", format!("{:?}", s));
  22 }
  23
  24 #[test]
  25 fn test_bit_set_from_usizes() {
  26     let usizes = vec![0, 2, 2, 3];
  27     let a: BitSet = usizes.into_iter().collect();
  28     let mut b = BitSet::new();
  29     b.insert(0);
  30     b.insert(2);
  31     b.insert(3);
  32     assert_eq!(a, b);
  33 }
  34
  35 #[test]
  36 fn test_bit_set_iterator() {
  37     let usizes = vec![0, 2, 2, 3];
  38     let bit_vec: BitSet = usizes.into_iter().collect();
  39
  40     let idxs: Vec<_> = bit_vec.iter().collect();
  41     assert_eq!(idxs, [0, 2, 3]);
  42
  43     let long: BitSet = (0..10000).filter(|&n| n % 2 == 0).collect();
  44     let real: Vec<_> = (0..10000).step_by(2).collect();
  45
  46     let idxs: Vec<_> = long.iter().collect();
  47     assert_eq!(idxs, real);
  48 }
  49
  50 #[test]
  51 fn test_bit_set_frombit_vec_init() {
  52     let bools = [true, false];
  53     let lengths = [10, 64, 100];
  54     for &b in &bools {
  55         for &l in &lengths {
  56             let bitset = BitSet::from_bit_vec(BitVec::from_elem(l, b));
  57             assert_eq!(bitset.contains(&1), b);
  58             assert_eq!(bitset.contains(&(l-1)), b);
  59             assert!(!bitset.contains(&l));
  60         }
  61     }
  62 }
  63
  64 #[test]
  65 fn test_bit_vec_masking() {
  66     let b = BitVec::from_elem(140, true);
  67     let mut bs = BitSet::from_bit_vec(b);
  68     assert!(bs.contains(&139));
  69     assert!(!bs.contains(&140));
  70     assert!(bs.insert(150));
  71     assert!(!bs.contains(&140));
  72     assert!(!bs.contains(&149));
  73     assert!(bs.contains(&150));
  74     assert!(!bs.contains(&151));
  75 }
  76
  77 #[test]
  78 fn test_bit_set_basic() {
  79     let mut b = BitSet::new();
  80     assert!(b.insert(3));
  81     assert!(!b.insert(3));
  82     assert!(b.contains(&3));
  83     assert!(b.insert(4));
  84     assert!(!b.insert(4));
  85     assert!(b.contains(&3));
  86     assert!(b.insert(400));
  87     assert!(!b.insert(400));
  88     assert!(b.contains(&400));
  89     assert_eq!(b.len(), 3);
  90 }
  91
  92 #[test]
  93 fn test_bit_set_intersection() {
  94     let mut a = BitSet::new();
  95     let mut b = BitSet::new();
  96
  97     assert!(a.insert(11));
  98     assert!(a.insert(1));
  99     assert!(a.insert(3));
 100     assert!(a.insert(77));
 101     assert!(a.insert(103));
 102     assert!(a.insert(5));
 103
 104     assert!(b.insert(2));
 105     assert!(b.insert(11));
 106     assert!(b.insert(77));
 107     assert!(b.insert(5));
 108     assert!(b.insert(3));
 109
 110     let expected = [3, 5, 11, 77];
 111     let actual: Vec<_> = a.intersection(&b).collect();
 112     assert_eq!(actual, expected);
 113 }
 114
 115 #[test]
 116 fn test_bit_set_difference() {
 117     let mut a = BitSet::new();
 118     let mut b = BitSet::new();
 119
 120     assert!(a.insert(1));
 121     assert!(a.insert(3));
 122     assert!(a.insert(5));
 123     assert!(a.insert(200));
 124     assert!(a.insert(500));
 125
 126     assert!(b.insert(3));
 127     assert!(b.insert(200));
 128
 129     let expected = [1, 5, 500];
 130     let actual: Vec<_> = a.difference(&b).collect();
 131     assert_eq!(actual, expected);
 132 }
 133
 134 #[test]
 135 fn test_bit_set_symmetric_difference() {
 136     let mut a = BitSet::new();
 137     let mut b = BitSet::new();
 138
 139     assert!(a.insert(1));
 140     assert!(a.insert(3));
 141     assert!(a.insert(5));
 142     assert!(a.insert(9));
 143     assert!(a.insert(11));
 144
 145     assert!(b.insert(3));
 146     assert!(b.insert(9));
 147     assert!(b.insert(14));
 148     assert!(b.insert(220));
 149
 150     let expected = [1, 5, 11, 14, 220];
 151     let actual: Vec<_> = a.symmetric_difference(&b).collect();
 152     assert_eq!(actual, expected);
 153 }
 154
 155 #[test]
 156 fn test_bit_set_union() {
 157     let mut a = BitSet::new();
 158     let mut b = BitSet::new();
 159     assert!(a.insert(1));
 160     assert!(a.insert(3));
 161     assert!(a.insert(5));
 162     assert!(a.insert(9));
 163     assert!(a.insert(11));
 164     assert!(a.insert(160));
 165     assert!(a.insert(19));
 166     assert!(a.insert(24));
 167     assert!(a.insert(200));
 168
 169     assert!(b.insert(1));
 170     assert!(b.insert(5));
 171     assert!(b.insert(9));
 172     assert!(b.insert(13));
 173     assert!(b.insert(19));
 174
 175     let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160, 200];
 176     let actual: Vec<_> = a.union(&b).collect();
 177     assert_eq!(actual, expected);
 178 }
 179
 180 #[test]
 181 fn test_bit_set_subset() {
 182     let mut set1 = BitSet::new();
 183     let mut set2 = BitSet::new();
 184
 185     assert!(set1.is_subset(&set2)); //  {}  {}
 186     set2.insert(100);
 187     assert!(set1.is_subset(&set2)); //  {}  { 1 }
 188     set2.insert(200);
 189     assert!(set1.is_subset(&set2)); //  {}  { 1, 2 }
 190     set1.insert(200);
 191     assert!(set1.is_subset(&set2)); //  { 2 }  { 1, 2 }
 192     set1.insert(300);
 193     assert!(!set1.is_subset(&set2)); // { 2, 3 }  { 1, 2 }
 194     set2.insert(300);
 195     assert!(set1.is_subset(&set2)); // { 2, 3 }  { 1, 2, 3 }
 196     set2.insert(400);
 197     assert!(set1.is_subset(&set2)); // { 2, 3 }  { 1, 2, 3, 4 }
 198     set2.remove(&100);
 199     assert!(set1.is_subset(&set2)); // { 2, 3 }  { 2, 3, 4 }
 200     set2.remove(&300);
 201     assert!(!set1.is_subset(&set2)); // { 2, 3 }  { 2, 4 }
 202     set1.remove(&300);
 203     assert!(set1.is_subset(&set2)); // { 2 }  { 2, 4 }
 204 }
 205
 206 #[test]
 207 fn test_bit_set_is_disjoint() {
 208     let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
 209     let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01000000]));
 210     let c = BitSet::new();
 211     let d = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00110000]));
 212
 213     assert!(!a.is_disjoint(&d));
 214     assert!(!d.is_disjoint(&a));
 215
 216     assert!(a.is_disjoint(&b));
 217     assert!(a.is_disjoint(&c));
 218     assert!(b.is_disjoint(&a));
 219     assert!(b.is_disjoint(&c));
 220     assert!(c.is_disjoint(&a));
 221     assert!(c.is_disjoint(&b));
 222 }
 223
 224 #[test]
 225 fn test_bit_set_union_with() {
 226     //a should grow to include larger elements
 227     let mut a = BitSet::new();
 228     a.insert(0);
 229     let mut b = BitSet::new();
 230     b.insert(5);
 231     let expected = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10000100]));
 232     a.union_with(&b);
 233     assert_eq!(a, expected);
 234
 235     // Standard
 236     let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
 237     let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100010]));
 238     let c = a.clone();
 239     a.union_with(&b);
 240     b.union_with(&c);
 241     assert_eq!(a.len(), 4);
 242     assert_eq!(b.len(), 4);
 243 }
 244
 245 #[test]
 246 fn test_bit_set_intersect_with() {
 247     // Explicitly 0'ed bits
 248     let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
 249     let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000]));
 250     let c = a.clone();
 251     a.intersect_with(&b);
 252     b.intersect_with(&c);
 253     assert!(a.is_empty());
 254     assert!(b.is_empty());
 255
 256     // Uninitialized bits should behave like 0's
 257     let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
 258     let mut b = BitSet::new();
 259     let c = a.clone();
 260     a.intersect_with(&b);
 261     b.intersect_with(&c);
 262     assert!(a.is_empty());
 263     assert!(b.is_empty());
 264
 265     // Standard
 266     let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
 267     let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100010]));
 268     let c = a.clone();
 269     a.intersect_with(&b);
 270     b.intersect_with(&c);
 271     assert_eq!(a.len(), 2);
 272     assert_eq!(b.len(), 2);
 273 }
 274
 275 #[test]
 276 fn test_bit_set_difference_with() {
 277     // Explicitly 0'ed bits
 278     let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000]));
 279     let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
 280     a.difference_with(&b);
 281     assert!(a.is_empty());
 282
 283     // Uninitialized bits should behave like 0's
 284     let mut a = BitSet::new();
 285     let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11111111]));
 286     a.difference_with(&b);
 287     assert!(a.is_empty());
 288
 289     // Standard
 290     let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
 291     let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100010]));
 292     let c = a.clone();
 293     a.difference_with(&b);
 294     b.difference_with(&c);
 295     assert_eq!(a.len(), 1);
 296     assert_eq!(b.len(), 1);
 297 }
 298
 299 #[test]
 300 fn test_bit_set_symmetric_difference_with() {
 301     //a should grow to include larger elements
 302     let mut a = BitSet::new();
 303     a.insert(0);
 304     a.insert(1);
 305     let mut b = BitSet::new();
 306     b.insert(1);
 307     b.insert(5);
 308     let expected = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10000100]));
 309     a.symmetric_difference_with(&b);
 310     assert_eq!(a, expected);
 311
 312     let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
 313     let b = BitSet::new();
 314     let c = a.clone();
 315     a.symmetric_difference_with(&b);
 316     assert_eq!(a, c);
 317
 318     // Standard
 319     let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11100010]));
 320     let mut b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101010]));
 321     let c = a.clone();
 322     a.symmetric_difference_with(&b);
 323     b.symmetric_difference_with(&c);
 324     assert_eq!(a.len(), 2);
 325     assert_eq!(b.len(), 2);
 326 }
 327
 328 #[test]
 329 fn test_bit_set_eq() {
 330     let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
 331     let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000]));
 332     let c = BitSet::new();
 333
 334     assert!(a == a);
 335     assert!(a != b);
 336     assert!(a != c);
 337     assert!(b == b);
 338     assert!(b == c);
 339     assert!(c == c);
 340 }
 341
 342 #[test]
 343 fn test_bit_set_cmp() {
 344     let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100010]));
 345     let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b00000000]));
 346     let c = BitSet::new();
 347
 348     assert_eq!(a.cmp(&b), Greater);
 349     assert_eq!(a.cmp(&c), Greater);
 350     assert_eq!(b.cmp(&a), Less);
 351     assert_eq!(b.cmp(&c), Equal);
 352     assert_eq!(c.cmp(&a), Less);
 353     assert_eq!(c.cmp(&b), Equal);
 354 }
 355
 356 #[test]
 357 fn test_bit_vec_remove() {
 358     let mut a = BitSet::new();
 359
 360     assert!(a.insert(1));
 361     assert!(a.remove(&1));
 362
 363     assert!(a.insert(100));
 364     assert!(a.remove(&100));
 365
 366     assert!(a.insert(1000));
 367     assert!(a.remove(&1000));
 368     a.shrink_to_fit();
 369 }
 370
 371 #[test]
 372 fn test_bit_vec_clone() {
 373     let mut a = BitSet::new();
 374
 375     assert!(a.insert(1));
 376     assert!(a.insert(100));
 377     assert!(a.insert(1000));
 378
 379     let mut b = a.clone();
 380
 381     assert!(a == b);
 382
 383     assert!(b.remove(&1));
 384     assert!(a.contains(&1));
 385
 386     assert!(a.remove(&1000));
 387     assert!(b.contains(&1000));
 388 }
 389
 390 #[test]
 391 fn test_bit_set_append() {
 392     let mut a = BitSet::new();
 393     a.insert(2);
 394     a.insert(6);
 395
 396     let mut b = BitSet::new();
 397     b.insert(1);
 398     b.insert(3);
 399     b.insert(6);
 400
 401     a.append(&mut b);
 402
 403     assert_eq!(a.len(), 4);
 404     assert_eq!(b.len(), 0);
 405     assert!(b.capacity() >= 6);
 406
 407     assert_eq!(a, BitSet::from_bit_vec(BitVec::from_bytes(&[0b01110010])));
 408 }
 409
 410 #[test]
 411 fn test_bit_set_split_off() {
 412     // Split at 0
 413     let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
 414                                                           0b00110011, 0b01101011, 0b10101101]));
 415
 416     let b = a.split_off(0);
 417
 418     assert_eq!(a.len(), 0);
 419     assert_eq!(b.len(), 21);
 420
 421     assert_eq!(b, BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
 422                                                             0b00110011, 0b01101011, 0b10101101])));
 423
 424     // Split behind last element
 425     let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
 426                                                           0b00110011, 0b01101011, 0b10101101]));
 427
 428     let b = a.split_off(50);
 429
 430     assert_eq!(a.len(), 21);
 431     assert_eq!(b.len(), 0);
 432
 433     assert_eq!(a, BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
 434                                                             0b00110011, 0b01101011, 0b10101101])));
 435
 436     // Split at arbitrary element
 437     let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
 438                                                           0b00110011, 0b01101011, 0b10101101]));
 439
 440     let b = a.split_off(34);
 441
 442     assert_eq!(a.len(), 12);
 443     assert_eq!(b.len(), 9);
 444
 445     assert_eq!(a, BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
 446                                                             0b00110011, 0b01000000])));
 447     assert_eq!(b, BitSet::from_bit_vec(BitVec::from_bytes(&[0, 0, 0, 0,
 448                                                             0b00101011, 0b10101101])));
 449 }
 450
 451 #[test]
 452 fn test_bit_set_extend_ref() {
 453     let mut a = BitSet::new();
 454     a.insert(3);
 455
 456     a.extend(&[5, 7, 10]);
 457
 458     assert_eq!(a.len(), 4);
 459     assert_eq!(a, BitSet::from_bit_vec(BitVec::from_bytes(&[0b00010101,0b00100000])));
 460
 461     let mut b = BitSet::new();
 462     b.insert(11);
 463     b.insert(15);
 464
 465     a.extend(&b);
 466
 467     assert_eq!(a.len(), 6);
 468     assert_eq!(a, BitSet::from_bit_vec(BitVec::from_bytes(&[0b00010101,0b00110001])));
 469 }
 470
 471 mod bench {
 472     use std::collections::{BitSet, BitVec};
 473     use std::__rand::{Rng, thread_rng, ThreadRng};
 474     use std::u32;
 475
 476     use test::{Bencher, black_box};
 477
 478     const BENCH_BITS : usize = 1 << 14;
 479
 480     fn rng() -> ThreadRng {
 481         thread_rng()
 482     }
 483
 484     #[bench]
 485     fn bench_bit_vecset_small(b: &mut Bencher) {
 486         let mut r = rng();
 487         let mut bit_vec = BitSet::new();
 488         b.iter(|| {
 489             for _ in 0..100 {
 490                 bit_vec.insert((r.next_u32() as usize) % u32::BITS);
 491             }
 492             black_box(&bit_vec);
 493         });
 494     }
 495
 496     #[bench]
 497     fn bench_bit_vecset_big(b: &mut Bencher) {
 498         let mut r = rng();
 499         let mut bit_vec = BitSet::new();
 500         b.iter(|| {
 501             for _ in 0..100 {
 502                 bit_vec.insert((r.next_u32() as usize) % BENCH_BITS);
 503             }
 504             black_box(&bit_vec);
 505         });
 506     }
 507
 508     #[bench]
 509     fn bench_bit_vecset_iter(b: &mut Bencher) {
 510         let bit_vec = BitSet::from_bit_vec(BitVec::from_fn(BENCH_BITS,
 511                                               |idx| {idx % 3 == 0}));
 512         b.iter(|| {
 513             let mut sum = 0;
 514             for idx in &bit_vec {
 515                 sum += idx as usize;
 516             }
 517             sum
 518         })
 519     }
 520 }