src/librustc_index/bit_set/tests.rs

   1 use super::*;
   2
   3 extern crate test;
   4 use test::Bencher;
   5
   6 #[test]
   7 fn test_new_filled() {
   8     for i in 0..128 {
   9         let idx_buf = BitSet::new_filled(i);
  10         let elems: Vec<usize> = idx_buf.iter().collect();
  11         let expected: Vec<usize> = (0..i).collect();
  12         assert_eq!(elems, expected);
  13     }
  14 }
  15
  16 #[test]
  17 fn bitset_iter_works() {
  18     let mut bitset: BitSet<usize> = BitSet::new_empty(100);
  19     bitset.insert(1);
  20     bitset.insert(10);
  21     bitset.insert(19);
  22     bitset.insert(62);
  23     bitset.insert(63);
  24     bitset.insert(64);
  25     bitset.insert(65);
  26     bitset.insert(66);
  27     bitset.insert(99);
  28     assert_eq!(bitset.iter().collect::<Vec<_>>(), [1, 10, 19, 62, 63, 64, 65, 66, 99]);
  29 }
  30
  31 #[test]
  32 fn bitset_iter_works_2() {
  33     let mut bitset: BitSet<usize> = BitSet::new_empty(320);
  34     bitset.insert(0);
  35     bitset.insert(127);
  36     bitset.insert(191);
  37     bitset.insert(255);
  38     bitset.insert(319);
  39     assert_eq!(bitset.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
  40 }
  41
  42 #[test]
  43 fn union_two_sets() {
  44     let mut set1: BitSet<usize> = BitSet::new_empty(65);
  45     let mut set2: BitSet<usize> = BitSet::new_empty(65);
  46     assert!(set1.insert(3));
  47     assert!(!set1.insert(3));
  48     assert!(set2.insert(5));
  49     assert!(set2.insert(64));
  50     assert!(set1.union(&set2));
  51     assert!(!set1.union(&set2));
  52     assert!(set1.contains(3));
  53     assert!(!set1.contains(4));
  54     assert!(set1.contains(5));
  55     assert!(!set1.contains(63));
  56     assert!(set1.contains(64));
  57 }
  58
  59 #[test]
  60 fn hybrid_bitset() {
  61     let mut sparse038: HybridBitSet<usize> = HybridBitSet::new_empty(256);
  62     assert!(sparse038.is_empty());
  63     assert!(sparse038.insert(0));
  64     assert!(sparse038.insert(1));
  65     assert!(sparse038.insert(8));
  66     assert!(sparse038.insert(3));
  67     assert!(!sparse038.insert(3));
  68     assert!(sparse038.remove(1));
  69     assert!(!sparse038.is_empty());
  70     assert_eq!(sparse038.iter().collect::<Vec<_>>(), [0, 3, 8]);
  71
  72     for i in 0..256 {
  73         if i == 0 || i == 3 || i == 8 {
  74             assert!(sparse038.contains(i));
  75         } else {
  76             assert!(!sparse038.contains(i));
  77         }
  78     }
  79
  80     let mut sparse01358 = sparse038.clone();
  81     assert!(sparse01358.insert(1));
  82     assert!(sparse01358.insert(5));
  83     assert_eq!(sparse01358.iter().collect::<Vec<_>>(), [0, 1, 3, 5, 8]);
  84
  85     let mut dense10 = HybridBitSet::new_empty(256);
  86     for i in 0..10 {
  87         assert!(dense10.insert(i));
  88     }
  89     assert!(!dense10.is_empty());
  90     assert_eq!(dense10.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
  91
  92     let mut dense256 = HybridBitSet::new_empty(256);
  93     assert!(dense256.is_empty());
  94     dense256.insert_all();
  95     assert!(!dense256.is_empty());
  96     for i in 0..256 {
  97         assert!(dense256.contains(i));
  98     }
  99
 100     assert!(sparse038.superset(&sparse038)); // sparse + sparse (self)
 101     assert!(sparse01358.superset(&sparse038)); // sparse + sparse
 102     assert!(dense10.superset(&sparse038)); // dense + sparse
 103     assert!(dense10.superset(&dense10)); // dense + dense (self)
 104     assert!(dense256.superset(&dense10)); // dense + dense
 105
 106     let mut hybrid = sparse038;
 107     assert!(!sparse01358.union(&hybrid)); // no change
 108     assert!(hybrid.union(&sparse01358));
 109     assert!(hybrid.superset(&sparse01358) && sparse01358.superset(&hybrid));
 110     assert!(!dense10.union(&sparse01358));
 111     assert!(!dense256.union(&dense10));
 112     let mut dense = dense10;
 113     assert!(dense.union(&dense256));
 114     assert!(dense.superset(&dense256) && dense256.superset(&dense));
 115     assert!(hybrid.union(&dense256));
 116     assert!(hybrid.superset(&dense256) && dense256.superset(&hybrid));
 117
 118     assert_eq!(dense256.iter().count(), 256);
 119     let mut dense0 = dense256;
 120     for i in 0..256 {
 121         assert!(dense0.remove(i));
 122     }
 123     assert!(!dense0.remove(0));
 124     assert!(dense0.is_empty());
 125 }
 126
 127 #[test]
 128 fn grow() {
 129     let mut set: GrowableBitSet<usize> = GrowableBitSet::with_capacity(65);
 130     for index in 0..65 {
 131         assert!(set.insert(index));
 132         assert!(!set.insert(index));
 133     }
 134     set.ensure(128);
 135
 136     // Check if the bits set before growing are still set
 137     for index in 0..65 {
 138         assert!(set.contains(index));
 139     }
 140
 141     // Check if the new bits are all un-set
 142     for index in 65..128 {
 143         assert!(!set.contains(index));
 144     }
 145
 146     // Check that we can set all new bits without running out of bounds
 147     for index in 65..128 {
 148         assert!(set.insert(index));
 149         assert!(!set.insert(index));
 150     }
 151 }
 152
 153 #[test]
 154 fn matrix_intersection() {
 155     let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
 156
 157     // (*) Elements reachable from both 2 and 65.
 158
 159     matrix.insert(2, 3);
 160     matrix.insert(2, 6);
 161     matrix.insert(2, 10); // (*)
 162     matrix.insert(2, 64); // (*)
 163     matrix.insert(2, 65);
 164     matrix.insert(2, 130);
 165     matrix.insert(2, 160); // (*)
 166
 167     matrix.insert(64, 133);
 168
 169     matrix.insert(65, 2);
 170     matrix.insert(65, 8);
 171     matrix.insert(65, 10); // (*)
 172     matrix.insert(65, 64); // (*)
 173     matrix.insert(65, 68);
 174     matrix.insert(65, 133);
 175     matrix.insert(65, 160); // (*)
 176
 177     let intersection = matrix.intersect_rows(2, 64);
 178     assert!(intersection.is_empty());
 179
 180     let intersection = matrix.intersect_rows(2, 65);
 181     assert_eq!(intersection, &[10, 64, 160]);
 182 }
 183
 184 #[test]
 185 fn matrix_iter() {
 186     let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
 187     matrix.insert(3, 22);
 188     matrix.insert(3, 75);
 189     matrix.insert(2, 99);
 190     matrix.insert(4, 0);
 191     matrix.union_rows(3, 5);
 192     matrix.insert_all_into_row(6);
 193
 194     let expected = [99];
 195     let mut iter = expected.iter();
 196     for i in matrix.iter(2) {
 197         let j = *iter.next().unwrap();
 198         assert_eq!(i, j);
 199     }
 200     assert!(iter.next().is_none());
 201
 202     let expected = [22, 75];
 203     let mut iter = expected.iter();
 204     assert_eq!(matrix.count(3), expected.len());
 205     for i in matrix.iter(3) {
 206         let j = *iter.next().unwrap();
 207         assert_eq!(i, j);
 208     }
 209     assert!(iter.next().is_none());
 210
 211     let expected = [0];
 212     let mut iter = expected.iter();
 213     assert_eq!(matrix.count(4), expected.len());
 214     for i in matrix.iter(4) {
 215         let j = *iter.next().unwrap();
 216         assert_eq!(i, j);
 217     }
 218     assert!(iter.next().is_none());
 219
 220     let expected = [22, 75];
 221     let mut iter = expected.iter();
 222     assert_eq!(matrix.count(5), expected.len());
 223     for i in matrix.iter(5) {
 224         let j = *iter.next().unwrap();
 225         assert_eq!(i, j);
 226     }
 227     assert!(iter.next().is_none());
 228
 229     assert_eq!(matrix.count(6), 100);
 230     let mut count = 0;
 231     for (idx, i) in matrix.iter(6).enumerate() {
 232         assert_eq!(idx, i);
 233         count += 1;
 234     }
 235     assert_eq!(count, 100);
 236
 237     if let Some(i) = matrix.iter(7).next() {
 238         panic!("expected no elements in row, but contains element {:?}", i);
 239     }
 240 }
 241
 242 #[test]
 243 fn sparse_matrix_iter() {
 244     let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
 245     matrix.insert(3, 22);
 246     matrix.insert(3, 75);
 247     matrix.insert(2, 99);
 248     matrix.insert(4, 0);
 249     matrix.union_rows(3, 5);
 250
 251     let expected = [99];
 252     let mut iter = expected.iter();
 253     for i in matrix.iter(2) {
 254         let j = *iter.next().unwrap();
 255         assert_eq!(i, j);
 256     }
 257     assert!(iter.next().is_none());
 258
 259     let expected = [22, 75];
 260     let mut iter = expected.iter();
 261     for i in matrix.iter(3) {
 262         let j = *iter.next().unwrap();
 263         assert_eq!(i, j);
 264     }
 265     assert!(iter.next().is_none());
 266
 267     let expected = [0];
 268     let mut iter = expected.iter();
 269     for i in matrix.iter(4) {
 270         let j = *iter.next().unwrap();
 271         assert_eq!(i, j);
 272     }
 273     assert!(iter.next().is_none());
 274
 275     let expected = [22, 75];
 276     let mut iter = expected.iter();
 277     for i in matrix.iter(5) {
 278         let j = *iter.next().unwrap();
 279         assert_eq!(i, j);
 280     }
 281     assert!(iter.next().is_none());
 282 }
 283
 284 /// Merge dense hybrid set into empty sparse hybrid set.
 285 #[bench]
 286 fn union_hybrid_sparse_empty_to_dense(b: &mut Bencher) {
 287     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
 288     for i in 0..10 {
 289         assert!(pre_dense.insert(i));
 290     }
 291     let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
 292     b.iter(|| {
 293         let dense = pre_dense.clone();
 294         let mut sparse = pre_sparse.clone();
 295         sparse.union(&dense);
 296     })
 297 }
 298
 299 /// Merge dense hybrid set into full hybrid set with same indices.
 300 #[bench]
 301 fn union_hybrid_sparse_full_to_dense(b: &mut Bencher) {
 302     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
 303     for i in 0..10 {
 304         assert!(pre_dense.insert(i));
 305     }
 306     let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
 307     for i in 0..SPARSE_MAX {
 308         assert!(pre_sparse.insert(i));
 309     }
 310     b.iter(|| {
 311         let dense = pre_dense.clone();
 312         let mut sparse = pre_sparse.clone();
 313         sparse.union(&dense);
 314     })
 315 }
 316
 317 /// Merge dense hybrid set into full hybrid set with indices over the whole domain.
 318 #[bench]
 319 fn union_hybrid_sparse_domain_to_dense(b: &mut Bencher) {
 320     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64);
 321     for i in 0..10 {
 322         assert!(pre_dense.insert(i));
 323     }
 324     let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64);
 325     for i in 0..SPARSE_MAX {
 326         assert!(pre_sparse.insert(i * 64));
 327     }
 328     b.iter(|| {
 329         let dense = pre_dense.clone();
 330         let mut sparse = pre_sparse.clone();
 331         sparse.union(&dense);
 332     })
 333 }
 334
 335 /// Merge dense hybrid set into empty hybrid set where the domain is very small.
 336 #[bench]
 337 fn union_hybrid_sparse_empty_small_domain(b: &mut Bencher) {
 338     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
 339     for i in 0..SPARSE_MAX {
 340         assert!(pre_dense.insert(i));
 341     }
 342     let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
 343     b.iter(|| {
 344         let dense = pre_dense.clone();
 345         let mut sparse = pre_sparse.clone();
 346         sparse.union(&dense);
 347     })
 348 }
 349
 350 /// Merge dense hybrid set into full hybrid set where the domain is very small.
 351 #[bench]
 352 fn union_hybrid_sparse_full_small_domain(b: &mut Bencher) {
 353     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
 354     for i in 0..SPARSE_MAX {
 355         assert!(pre_dense.insert(i));
 356     }
 357     let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
 358     for i in 0..SPARSE_MAX {
 359         assert!(pre_sparse.insert(i));
 360     }
 361     b.iter(|| {
 362         let dense = pre_dense.clone();
 363         let mut sparse = pre_sparse.clone();
 364         sparse.union(&dense);
 365     })
 366 }