src/librustc_data_structures/bit_set.rs

   1 use crate::indexed_vec::{Idx, IndexVec};
   2 use smallvec::SmallVec;
   3 use std::fmt;
   4 use std::iter;
   5 use std::marker::PhantomData;
   6 use std::mem;
   7 use std::slice;
   8 #[cfg(test)]
   9 extern crate test;
  10 #[cfg(test)]
  11 use test::Bencher;
  12
  13 pub type Word = u64;
  14 pub const WORD_BYTES: usize = mem::size_of::<Word>();
  15 pub const WORD_BITS: usize = WORD_BYTES * 8;
  16
  17 /// A fixed-size bitset type with a dense representation. It does not support
  18 /// resizing after creation; use `GrowableBitSet` for that.
  19 ///
  20 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
  21 /// just be `usize`.
  22 ///
  23 /// All operations that involve an element will panic if the element is equal
  24 /// to or greater than the domain size. All operations that involve two bitsets
  25 /// will panic if the bitsets have differing domain sizes.
  26 #[derive(Clone, Eq, PartialEq, RustcDecodable, RustcEncodable)]
  27 pub struct BitSet<T: Idx> {
  28     domain_size: usize,
  29     words: Vec<Word>,
  30     marker: PhantomData<T>,
  31 }
  32
  33 impl<T: Idx> BitSet<T> {
  34     /// Creates a new, empty bitset with a given `domain_size`.
  35     #[inline]
  36     pub fn new_empty(domain_size: usize) -> BitSet<T> {
  37         let num_words = num_words(domain_size);
  38         BitSet {
  39             domain_size,
  40             words: vec![0; num_words],
  41             marker: PhantomData,
  42         }
  43     }
  44
  45     /// Creates a new, filled bitset with a given `domain_size`.
  46     #[inline]
  47     pub fn new_filled(domain_size: usize) -> BitSet<T> {
  48         let num_words = num_words(domain_size);
  49         let mut result = BitSet {
  50             domain_size,
  51             words: vec![!0; num_words],
  52             marker: PhantomData,
  53         };
  54         result.clear_excess_bits();
  55         result
  56     }
  57
  58     /// Gets the domain size.
  59     pub fn domain_size(&self) -> usize {
  60         self.domain_size
  61     }
  62
  63     /// Clear all elements.
  64     #[inline]
  65     pub fn clear(&mut self) {
  66         for word in &mut self.words {
  67             *word = 0;
  68         }
  69     }
  70
  71     /// Clear excess bits in the final word.
  72     fn clear_excess_bits(&mut self) {
  73         let num_bits_in_final_word = self.domain_size % WORD_BITS;
  74         if num_bits_in_final_word > 0 {
  75             let mask = (1 << num_bits_in_final_word) - 1;
  76             let final_word_idx = self.words.len() - 1;
  77             self.words[final_word_idx] &= mask;
  78         }
  79     }
  80
  81     /// Efficiently overwrite `self` with `other`.
  82     pub fn overwrite(&mut self, other: &BitSet<T>) {
  83         assert!(self.domain_size == other.domain_size);
  84         self.words.clone_from_slice(&other.words);
  85     }
  86
  87     /// Count the number of set bits in the set.
  88     pub fn count(&self) -> usize {
  89         self.words.iter().map(|e| e.count_ones() as usize).sum()
  90     }
  91
  92     /// Returns `true` if `self` contains `elem`.
  93     #[inline]
  94     pub fn contains(&self, elem: T) -> bool {
  95         assert!(elem.index() < self.domain_size);
  96         let (word_index, mask) = word_index_and_mask(elem);
  97         (self.words[word_index] & mask) != 0
  98     }
  99
 100     /// Is `self` is a (non-strict) superset of `other`?
 101     #[inline]
 102     pub fn superset(&self, other: &BitSet<T>) -> bool {
 103         assert_eq!(self.domain_size, other.domain_size);
 104         self.words.iter().zip(&other.words).all(|(a, b)| (a & b) == *b)
 105     }
 106
 107     /// Is the set empty?
 108     #[inline]
 109     pub fn is_empty(&self) -> bool {
 110         self.words.iter().all(|a| *a == 0)
 111     }
 112
 113     /// Insert `elem`. Returns whether the set has changed.
 114     #[inline]
 115     pub fn insert(&mut self, elem: T) -> bool {
 116         assert!(elem.index() < self.domain_size);
 117         let (word_index, mask) = word_index_and_mask(elem);
 118         let word_ref = &mut self.words[word_index];
 119         let word = *word_ref;
 120         let new_word = word | mask;
 121         *word_ref = new_word;
 122         new_word != word
 123     }
 124
 125     /// Sets all bits to true.
 126     pub fn insert_all(&mut self) {
 127         for word in &mut self.words {
 128             *word = !0;
 129         }
 130         self.clear_excess_bits();
 131     }
 132
 133     /// Returns `true` if the set has changed.
 134     #[inline]
 135     pub fn remove(&mut self, elem: T) -> bool {
 136         assert!(elem.index() < self.domain_size);
 137         let (word_index, mask) = word_index_and_mask(elem);
 138         let word_ref = &mut self.words[word_index];
 139         let word = *word_ref;
 140         let new_word = word & !mask;
 141         *word_ref = new_word;
 142         new_word != word
 143     }
 144
 145     /// Sets `self = self | other` and returns `true` if `self` changed
 146     /// (i.e., if new bits were added).
 147     pub fn union(&mut self, other: &impl UnionIntoBitSet<T>) -> bool {
 148         other.union_into(self)
 149     }
 150
 151     /// Sets `self = self - other` and returns `true` if `self` changed.
 152     /// (i.e., if any bits were removed).
 153     pub fn subtract(&mut self, other: &impl SubtractFromBitSet<T>) -> bool {
 154         other.subtract_from(self)
 155     }
 156
 157     /// Sets `self = self & other` and return `true` if `self` changed.
 158     /// (i.e., if any bits were removed).
 159     pub fn intersect(&mut self, other: &BitSet<T>) -> bool {
 160         assert_eq!(self.domain_size, other.domain_size);
 161         bitwise(&mut self.words, &other.words, |a, b| { a & b })
 162     }
 163
 164     /// Gets a slice of the underlying words.
 165     pub fn words(&self) -> &[Word] {
 166         &self.words
 167     }
 168
 169     /// Iterates over the indices of set bits in a sorted order.
 170     #[inline]
 171     pub fn iter(&self) -> BitIter<'_, T> {
 172         BitIter {
 173             cur: None,
 174             iter: self.words.iter().enumerate(),
 175             marker: PhantomData,
 176         }
 177     }
 178
 179     /// Duplicates the set as a hybrid set.
 180     pub fn to_hybrid(&self) -> HybridBitSet<T> {
 181         // Note: we currently don't bother trying to make a Sparse set.
 182         HybridBitSet::Dense(self.to_owned())
 183     }
 184
 185     /// Set `self = self | other`. In contrast to `union` returns `true` if the set contains at
 186     /// least one bit that is not in `other` (i.e. `other` is not a superset of `self`).
 187     ///
 188     /// This is an optimization for union of a hybrid bitset.
 189     fn reverse_union_sparse(&mut self, sparse: &SparseBitSet<T>) -> bool {
 190         assert!(sparse.domain_size == self.domain_size);
 191         self.clear_excess_bits();
 192
 193         let mut not_already = false;
 194         // Index of the current word not yet merged.
 195         let mut current_index = 0;
 196         // Mask of bits that came from the sparse set in the current word.
 197         let mut new_bit_mask = 0;
 198         for (word_index, mask) in sparse.iter().map(|x| word_index_and_mask(*x)) {
 199             // Next bit is in a word not inspected yet.
 200             if word_index > current_index {
 201                 self.words[current_index] |= new_bit_mask;
 202                 // Were there any bits in the old word that did not occur in the sparse set?
 203                 not_already |= (self.words[current_index] ^ new_bit_mask) != 0;
 204                 // Check all words we skipped for any set bit.
 205                 not_already |= self.words[current_index+1..word_index].iter().any(|&x| x != 0);
 206                 // Update next word.
 207                 current_index = word_index;
 208                 // Reset bit mask, no bits have been merged yet.
 209                 new_bit_mask = 0;
 210             }
 211             // Add bit and mark it as coming from the sparse set.
 212             // self.words[word_index] |= mask;
 213             new_bit_mask |= mask;
 214         }
 215         self.words[current_index] |= new_bit_mask;
 216         // Any bits in the last inspected word that were not in the sparse set?
 217         not_already |= (self.words[current_index] ^ new_bit_mask) != 0;
 218         // Any bits in the tail? Note `clear_excess_bits` before.
 219         not_already |= self.words[current_index+1..].iter().any(|&x| x != 0);
 220
 221         not_already
 222     }
 223 }
 224
 225 /// This is implemented by all the bitsets so that BitSet::union() can be
 226 /// passed any type of bitset.
 227 pub trait UnionIntoBitSet<T: Idx> {
 228     // Performs `other = other | self`.
 229     fn union_into(&self, other: &mut BitSet<T>) -> bool;
 230 }
 231
 232 /// This is implemented by all the bitsets so that BitSet::subtract() can be
 233 /// passed any type of bitset.
 234 pub trait SubtractFromBitSet<T: Idx> {
 235     // Performs `other = other - self`.
 236     fn subtract_from(&self, other: &mut BitSet<T>) -> bool;
 237 }
 238
 239 impl<T: Idx> UnionIntoBitSet<T> for BitSet<T> {
 240     fn union_into(&self, other: &mut BitSet<T>) -> bool {
 241         assert_eq!(self.domain_size, other.domain_size);
 242         bitwise(&mut other.words, &self.words, |a, b| { a | b })
 243     }
 244 }
 245
 246 impl<T: Idx> SubtractFromBitSet<T> for BitSet<T> {
 247     fn subtract_from(&self, other: &mut BitSet<T>) -> bool {
 248         assert_eq!(self.domain_size, other.domain_size);
 249         bitwise(&mut other.words, &self.words, |a, b| { a & !b })
 250     }
 251 }
 252
 253 impl<T: Idx> fmt::Debug for BitSet<T> {
 254     fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result {
 255         w.debug_list()
 256          .entries(self.iter())
 257          .finish()
 258     }
 259 }
 260
 261 impl<T: Idx> ToString for BitSet<T> {
 262     fn to_string(&self) -> String {
 263         let mut result = String::new();
 264         let mut sep = '[';
 265
 266         // Note: this is a little endian printout of bytes.
 267
 268         // i tracks how many bits we have printed so far.
 269         let mut i = 0;
 270         for word in &self.words {
 271             let mut word = *word;
 272             for _ in 0..WORD_BYTES { // for each byte in `word`:
 273                 let remain = self.domain_size - i;
 274                 // If less than a byte remains, then mask just that many bits.
 275                 let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF };
 276                 assert!(mask <= 0xFF);
 277                 let byte = word & mask;
 278
 279                 result.push_str(&format!("{}{:02x}", sep, byte));
 280
 281                 if remain <= 8 { break; }
 282                 word >>= 8;
 283                 i += 8;
 284                 sep = '-';
 285             }
 286             sep = '|';
 287         }
 288         result.push(']');
 289
 290         result
 291     }
 292 }
 293
 294 pub struct BitIter<'a, T: Idx> {
 295     cur: Option<(Word, usize)>,
 296     iter: iter::Enumerate<slice::Iter<'a, Word>>,
 297     marker: PhantomData<T>
 298 }
 299
 300 impl<'a, T: Idx> Iterator for BitIter<'a, T> {
 301     type Item = T;
 302     fn next(&mut self) -> Option<T> {
 303         loop {
 304             if let Some((ref mut word, offset)) = self.cur {
 305                 let bit_pos = word.trailing_zeros() as usize;
 306                 if bit_pos != WORD_BITS {
 307                     let bit = 1 << bit_pos;
 308                     *word ^= bit;
 309                     return Some(T::new(bit_pos + offset))
 310                 }
 311             }
 312
 313             let (i, word) = self.iter.next()?;
 314             self.cur = Some((*word, WORD_BITS * i));
 315         }
 316     }
 317 }
 318
 319 #[inline]
 320 fn bitwise<Op>(out_vec: &mut [Word], in_vec: &[Word], op: Op) -> bool
 321     where Op: Fn(Word, Word) -> Word
 322 {
 323     assert_eq!(out_vec.len(), in_vec.len());
 324     let mut changed = false;
 325     for (out_elem, in_elem) in out_vec.iter_mut().zip(in_vec.iter()) {
 326         let old_val = *out_elem;
 327         let new_val = op(old_val, *in_elem);
 328         *out_elem = new_val;
 329         changed |= old_val != new_val;
 330     }
 331     changed
 332 }
 333
 334 const SPARSE_MAX: usize = 8;
 335
 336 /// A fixed-size bitset type with a sparse representation and a maximum of
 337 /// `SPARSE_MAX` elements. The elements are stored as a sorted `SmallVec` with
 338 /// no duplicates; although `SmallVec` can spill its elements to the heap, that
 339 /// never happens within this type because of the `SPARSE_MAX` limit.
 340 ///
 341 /// This type is used by `HybridBitSet`; do not use directly.
 342 #[derive(Clone, Debug)]
 343 pub struct SparseBitSet<T: Idx> {
 344     domain_size: usize,
 345     elems: SmallVec<[T; SPARSE_MAX]>,
 346 }
 347
 348 impl<T: Idx> SparseBitSet<T> {
 349     fn new_empty(domain_size: usize) -> Self {
 350         SparseBitSet {
 351             domain_size,
 352             elems: SmallVec::new()
 353         }
 354     }
 355
 356     fn len(&self) -> usize {
 357         self.elems.len()
 358     }
 359
 360     fn is_empty(&self) -> bool {
 361         self.elems.len() == 0
 362     }
 363
 364     fn contains(&self, elem: T) -> bool {
 365         assert!(elem.index() < self.domain_size);
 366         self.elems.contains(&elem)
 367     }
 368
 369     fn insert(&mut self, elem: T) -> bool {
 370         assert!(elem.index() < self.domain_size);
 371         let changed = if let Some(i) = self.elems.iter().position(|&e| e >= elem) {
 372             if self.elems[i] == elem {
 373                 // `elem` is already in the set.
 374                 false
 375             } else {
 376                 // `elem` is smaller than one or more existing elements.
 377                 self.elems.insert(i, elem);
 378                 true
 379             }
 380         } else {
 381             // `elem` is larger than all existing elements.
 382             self.elems.push(elem);
 383             true
 384         };
 385         assert!(self.len() <= SPARSE_MAX);
 386         changed
 387     }
 388
 389     fn remove(&mut self, elem: T) -> bool {
 390         assert!(elem.index() < self.domain_size);
 391         if let Some(i) = self.elems.iter().position(|&e| e == elem) {
 392             self.elems.remove(i);
 393             true
 394         } else {
 395             false
 396         }
 397     }
 398
 399     fn to_dense(&self) -> BitSet<T> {
 400         let mut dense = BitSet::new_empty(self.domain_size);
 401         for elem in self.elems.iter() {
 402             dense.insert(*elem);
 403         }
 404         dense
 405     }
 406
 407     fn iter(&self) -> slice::Iter<'_, T> {
 408         self.elems.iter()
 409     }
 410 }
 411
 412 impl<T: Idx> UnionIntoBitSet<T> for SparseBitSet<T> {
 413     fn union_into(&self, other: &mut BitSet<T>) -> bool {
 414         assert_eq!(self.domain_size, other.domain_size);
 415         let mut changed = false;
 416         for elem in self.iter() {
 417             changed |= other.insert(*elem);
 418         }
 419         changed
 420     }
 421 }
 422
 423 impl<T: Idx> SubtractFromBitSet<T> for SparseBitSet<T> {
 424     fn subtract_from(&self, other: &mut BitSet<T>) -> bool {
 425         assert_eq!(self.domain_size, other.domain_size);
 426         let mut changed = false;
 427         for elem in self.iter() {
 428             changed |= other.remove(*elem);
 429         }
 430         changed
 431     }
 432 }
 433
 434 /// A fixed-size bitset type with a hybrid representation: sparse when there
 435 /// are up to a `SPARSE_MAX` elements in the set, but dense when there are more
 436 /// than `SPARSE_MAX`.
 437 ///
 438 /// This type is especially efficient for sets that typically have a small
 439 /// number of elements, but a large `domain_size`, and are cleared frequently.
 440 ///
 441 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
 442 /// just be `usize`.
 443 ///
 444 /// All operations that involve an element will panic if the element is equal
 445 /// to or greater than the domain size. All operations that involve two bitsets
 446 /// will panic if the bitsets have differing domain sizes.
 447 #[derive(Clone, Debug)]
 448 pub enum HybridBitSet<T: Idx> {
 449     Sparse(SparseBitSet<T>),
 450     Dense(BitSet<T>),
 451 }
 452
 453 impl<T: Idx> HybridBitSet<T> {
 454     pub fn new_empty(domain_size: usize) -> Self {
 455         HybridBitSet::Sparse(SparseBitSet::new_empty(domain_size))
 456     }
 457
 458     fn domain_size(&self) -> usize {
 459         match self {
 460             HybridBitSet::Sparse(sparse) => sparse.domain_size,
 461             HybridBitSet::Dense(dense) => dense.domain_size,
 462         }
 463     }
 464
 465     pub fn clear(&mut self) {
 466         let domain_size = self.domain_size();
 467         *self = HybridBitSet::new_empty(domain_size);
 468     }
 469
 470     pub fn contains(&self, elem: T) -> bool {
 471         match self {
 472             HybridBitSet::Sparse(sparse) => sparse.contains(elem),
 473             HybridBitSet::Dense(dense) => dense.contains(elem),
 474         }
 475     }
 476
 477     pub fn superset(&self, other: &HybridBitSet<T>) -> bool {
 478         match (self, other) {
 479             (HybridBitSet::Dense(self_dense), HybridBitSet::Dense(other_dense)) => {
 480                 self_dense.superset(other_dense)
 481             }
 482             _ => {
 483                 assert!(self.domain_size() == other.domain_size());
 484                 other.iter().all(|elem| self.contains(elem))
 485             }
 486         }
 487     }
 488
 489     pub fn is_empty(&self) -> bool {
 490         match self {
 491             HybridBitSet::Sparse(sparse) => sparse.is_empty(),
 492             HybridBitSet::Dense(dense) => dense.is_empty(),
 493         }
 494     }
 495
 496     pub fn insert(&mut self, elem: T) -> bool {
 497         // No need to check `elem` against `self.domain_size` here because all
 498         // the match cases check it, one way or another.
 499         match self {
 500             HybridBitSet::Sparse(sparse) if sparse.len() < SPARSE_MAX => {
 501                 // The set is sparse and has space for `elem`.
 502                 sparse.insert(elem)
 503             }
 504             HybridBitSet::Sparse(sparse) if sparse.contains(elem) => {
 505                 // The set is sparse and does not have space for `elem`, but
 506                 // that doesn't matter because `elem` is already present.
 507                 false
 508             }
 509             HybridBitSet::Sparse(sparse) => {
 510                 // The set is sparse and full. Convert to a dense set.
 511                 let mut dense = sparse.to_dense();
 512                 let changed = dense.insert(elem);
 513                 assert!(changed);
 514                 *self = HybridBitSet::Dense(dense);
 515                 changed
 516             }
 517             HybridBitSet::Dense(dense) => dense.insert(elem),
 518         }
 519     }
 520
 521     pub fn insert_all(&mut self) {
 522         let domain_size = self.domain_size();
 523         match self {
 524             HybridBitSet::Sparse(_) => {
 525                 *self = HybridBitSet::Dense(BitSet::new_filled(domain_size));
 526             }
 527             HybridBitSet::Dense(dense) => dense.insert_all(),
 528         }
 529     }
 530
 531     pub fn remove(&mut self, elem: T) -> bool {
 532         // Note: we currently don't bother going from Dense back to Sparse.
 533         match self {
 534             HybridBitSet::Sparse(sparse) => sparse.remove(elem),
 535             HybridBitSet::Dense(dense) => dense.remove(elem),
 536         }
 537     }
 538
 539     pub fn union(&mut self, other: &HybridBitSet<T>) -> bool {
 540         match self {
 541             HybridBitSet::Sparse(self_sparse) => {
 542                 match other {
 543                     HybridBitSet::Sparse(other_sparse) => {
 544                         // Both sets are sparse. Add the elements in
 545                         // `other_sparse` to `self` one at a time. This
 546                         // may or may not cause `self` to be densified.
 547                         assert_eq!(self.domain_size(), other.domain_size());
 548                         let mut changed = false;
 549                         for elem in other_sparse.iter() {
 550                             changed |= self.insert(*elem);
 551                         }
 552                         changed
 553                     }
 554                     HybridBitSet::Dense(other_dense) => {
 555                         // `self` is sparse and `other` is dense. To
 556                         // merge them, we have two available strategies:
 557                         // * Densify `self` then merge other
 558                         // * Clone other then integrate bits from `self`
 559                         // The second strategy requires dedicated method
 560                         // since the usual `union` returns the wrong
 561                         // result. In the dedicated case the computation
 562                         // is slightly faster if the bits of the sparse
 563                         // bitset map to only few words of the dense
 564                         // representation, i.e. indices are near each
 565                         // other.
 566                         //
 567                         // Benchmarking seems to suggest that the second
 568                         // option is worth it.
 569                         let mut new_dense = other_dense.clone();
 570                         let changed = new_dense.reverse_union_sparse(self_sparse);
 571                         *self = HybridBitSet::Dense(new_dense);
 572                         changed
 573                     }
 574                 }
 575             }
 576
 577             HybridBitSet::Dense(self_dense) => self_dense.union(other),
 578         }
 579     }
 580
 581     /// Converts to a dense set, consuming itself in the process.
 582     pub fn to_dense(self) -> BitSet<T> {
 583         match self {
 584             HybridBitSet::Sparse(sparse) => sparse.to_dense(),
 585             HybridBitSet::Dense(dense) => dense,
 586         }
 587     }
 588
 589     pub fn iter(&self) -> HybridIter<'_, T> {
 590         match self {
 591             HybridBitSet::Sparse(sparse) => HybridIter::Sparse(sparse.iter()),
 592             HybridBitSet::Dense(dense) => HybridIter::Dense(dense.iter()),
 593         }
 594     }
 595 }
 596
 597 impl<T: Idx> UnionIntoBitSet<T> for HybridBitSet<T> {
 598     fn union_into(&self, other: &mut BitSet<T>) -> bool {
 599         match self {
 600             HybridBitSet::Sparse(sparse) => sparse.union_into(other),
 601             HybridBitSet::Dense(dense) => dense.union_into(other),
 602         }
 603     }
 604 }
 605
 606 impl<T: Idx> SubtractFromBitSet<T> for HybridBitSet<T> {
 607     fn subtract_from(&self, other: &mut BitSet<T>) -> bool {
 608         match self {
 609             HybridBitSet::Sparse(sparse) => sparse.subtract_from(other),
 610             HybridBitSet::Dense(dense) => dense.subtract_from(other),
 611         }
 612     }
 613 }
 614
 615 pub enum HybridIter<'a, T: Idx> {
 616     Sparse(slice::Iter<'a, T>),
 617     Dense(BitIter<'a, T>),
 618 }
 619
 620 impl<'a, T: Idx> Iterator for HybridIter<'a, T> {
 621     type Item = T;
 622
 623     fn next(&mut self) -> Option<T> {
 624         match self {
 625             HybridIter::Sparse(sparse) => sparse.next().map(|e| *e),
 626             HybridIter::Dense(dense) => dense.next(),
 627         }
 628     }
 629 }
 630
 631 /// A resizable bitset type with a dense representation.
 632 ///
 633 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
 634 /// just be `usize`.
 635 ///
 636 /// All operations that involve an element will panic if the element is equal
 637 /// to or greater than the domain size.
 638 #[derive(Clone, Debug, PartialEq)]
 639 pub struct GrowableBitSet<T: Idx> {
 640     bit_set: BitSet<T>,
 641 }
 642
 643 impl<T: Idx> GrowableBitSet<T> {
 644     /// Ensure that the set can hold at least `min_domain_size` elements.
 645     pub fn ensure(&mut self, min_domain_size: usize) {
 646         if self.bit_set.domain_size < min_domain_size {
 647             self.bit_set.domain_size = min_domain_size;
 648         }
 649
 650         let min_num_words = num_words(min_domain_size);
 651         if self.bit_set.words.len() < min_num_words {
 652             self.bit_set.words.resize(min_num_words, 0)
 653         }
 654     }
 655
 656     pub fn new_empty() -> GrowableBitSet<T> {
 657         GrowableBitSet { bit_set: BitSet::new_empty(0) }
 658     }
 659
 660     pub fn with_capacity(capacity: usize) -> GrowableBitSet<T> {
 661         GrowableBitSet { bit_set: BitSet::new_empty(capacity) }
 662     }
 663
 664     /// Returns `true` if the set has changed.
 665     #[inline]
 666     pub fn insert(&mut self, elem: T) -> bool {
 667         self.ensure(elem.index() + 1);
 668         self.bit_set.insert(elem)
 669     }
 670
 671     #[inline]
 672     pub fn contains(&self, elem: T) -> bool {
 673         let (word_index, mask) = word_index_and_mask(elem);
 674         if let Some(word) = self.bit_set.words.get(word_index) {
 675             (word & mask) != 0
 676         } else {
 677             false
 678         }
 679     }
 680 }
 681
 682 /// A fixed-size 2D bit matrix type with a dense representation.
 683 ///
 684 /// `R` and `C` are index types used to identify rows and columns respectively;
 685 /// typically newtyped `usize` wrappers, but they can also just be `usize`.
 686 ///
 687 /// All operations that involve a row and/or column index will panic if the
 688 /// index exceeds the relevant bound.
 689 #[derive(Clone, Debug, Eq, PartialEq, RustcDecodable, RustcEncodable)]
 690 pub struct BitMatrix<R: Idx, C: Idx> {
 691     num_rows: usize,
 692     num_columns: usize,
 693     words: Vec<Word>,
 694     marker: PhantomData<(R, C)>,
 695 }
 696
 697 impl<R: Idx, C: Idx> BitMatrix<R, C> {
 698     /// Creates a new `rows x columns` matrix, initially empty.
 699     pub fn new(num_rows: usize, num_columns: usize) -> BitMatrix<R, C> {
 700         // For every element, we need one bit for every other
 701         // element. Round up to an even number of words.
 702         let words_per_row = num_words(num_columns);
 703         BitMatrix {
 704             num_rows,
 705             num_columns,
 706             words: vec![0; num_rows * words_per_row],
 707             marker: PhantomData,
 708         }
 709     }
 710
 711     /// Creates a new matrix, with `row` used as the value for every row.
 712     pub fn from_row_n(row: &BitSet<C>, num_rows: usize) -> BitMatrix<R, C> {
 713         let num_columns = row.domain_size();
 714         let words_per_row = num_words(num_columns);
 715         assert_eq!(words_per_row, row.words().len());
 716         BitMatrix {
 717             num_rows,
 718             num_columns,
 719             words: iter::repeat(row.words()).take(num_rows).flatten().cloned().collect(),
 720             marker: PhantomData,
 721         }
 722     }
 723
 724     pub fn rows(&self) -> impl Iterator<Item = R> {
 725         (0..self.num_rows).map(R::new)
 726     }
 727
 728     /// The range of bits for a given row.
 729     fn range(&self, row: R) -> (usize, usize) {
 730         let words_per_row = num_words(self.num_columns);
 731         let start = row.index() * words_per_row;
 732         (start, start + words_per_row)
 733     }
 734
 735     /// Sets the cell at `(row, column)` to true. Put another way, insert
 736     /// `column` to the bitset for `row`.
 737     ///
 738     /// Returns `true` if this changed the matrix.
 739     pub fn insert(&mut self, row: R, column: C) -> bool {
 740         assert!(row.index() < self.num_rows && column.index() < self.num_columns);
 741         let (start, _) = self.range(row);
 742         let (word_index, mask) = word_index_and_mask(column);
 743         let words = &mut self.words[..];
 744         let word = words[start + word_index];
 745         let new_word = word | mask;
 746         words[start + word_index] = new_word;
 747         word != new_word
 748     }
 749
 750     /// Do the bits from `row` contain `column`? Put another way, is
 751     /// the matrix cell at `(row, column)` true?  Put yet another way,
 752     /// if the matrix represents (transitive) reachability, can
 753     /// `row` reach `column`?
 754     pub fn contains(&self, row: R, column: C) -> bool {
 755         assert!(row.index() < self.num_rows && column.index() < self.num_columns);
 756         let (start, _) = self.range(row);
 757         let (word_index, mask) = word_index_and_mask(column);
 758         (self.words[start + word_index] & mask) != 0
 759     }
 760
 761     /// Returns those indices that are true in rows `a` and `b`. This
 762     /// is an O(n) operation where `n` is the number of elements
 763     /// (somewhat independent from the actual size of the
 764     /// intersection, in particular).
 765     pub fn intersect_rows(&self, row1: R, row2: R) -> Vec<C> {
 766         assert!(row1.index() < self.num_rows && row2.index() < self.num_rows);
 767         let (row1_start, row1_end) = self.range(row1);
 768         let (row2_start, row2_end) = self.range(row2);
 769         let mut result = Vec::with_capacity(self.num_columns);
 770         for (base, (i, j)) in (row1_start..row1_end).zip(row2_start..row2_end).enumerate() {
 771             let mut v = self.words[i] & self.words[j];
 772             for bit in 0..WORD_BITS {
 773                 if v == 0 {
 774                     break;
 775                 }
 776                 if v & 0x1 != 0 {
 777                     result.push(C::new(base * WORD_BITS + bit));
 778                 }
 779                 v >>= 1;
 780             }
 781         }
 782         result
 783     }
 784
 785     /// Adds the bits from row `read` to the bits from row `write`, and
 786     /// returns `true` if anything changed.
 787     ///
 788     /// This is used when computing transitive reachability because if
 789     /// you have an edge `write -> read`, because in that case
 790     /// `write` can reach everything that `read` can (and
 791     /// potentially more).
 792     pub fn union_rows(&mut self, read: R, write: R) -> bool {
 793         assert!(read.index() < self.num_rows && write.index() < self.num_rows);
 794         let (read_start, read_end) = self.range(read);
 795         let (write_start, write_end) = self.range(write);
 796         let words = &mut self.words[..];
 797         let mut changed = false;
 798         for (read_index, write_index) in (read_start..read_end).zip(write_start..write_end) {
 799             let word = words[write_index];
 800             let new_word = word | words[read_index];
 801             words[write_index] = new_word;
 802             changed |= word != new_word;
 803         }
 804         changed
 805     }
 806
 807     /// Adds the bits from `with` to the bits from row `write`, and
 808     /// returns `true` if anything changed.
 809     pub fn union_row_with(&mut self, with: &BitSet<C>, write: R) -> bool {
 810         assert!(write.index() < self.num_rows);
 811         assert_eq!(with.domain_size(), self.num_columns);
 812         let (write_start, write_end) = self.range(write);
 813         let mut changed = false;
 814         for (read_index, write_index) in (0..with.words().len()).zip(write_start..write_end) {
 815             let word = self.words[write_index];
 816             let new_word = word | with.words()[read_index];
 817             self.words[write_index] = new_word;
 818             changed |= word != new_word;
 819         }
 820         changed
 821     }
 822
 823     /// Sets every cell in `row` to true.
 824     pub fn insert_all_into_row(&mut self, row: R) {
 825         assert!(row.index() < self.num_rows);
 826         let (start, end) = self.range(row);
 827         let words = &mut self.words[..];
 828         for index in start..end {
 829             words[index] = !0;
 830         }
 831         self.clear_excess_bits(row);
 832     }
 833
 834     /// Clear excess bits in the final word of the row.
 835     fn clear_excess_bits(&mut self, row: R) {
 836         let num_bits_in_final_word = self.num_columns % WORD_BITS;
 837         if num_bits_in_final_word > 0 {
 838             let mask = (1 << num_bits_in_final_word) - 1;
 839             let (_, end) = self.range(row);
 840             let final_word_idx = end - 1;
 841             self.words[final_word_idx] &= mask;
 842         }
 843     }
 844
 845     /// Gets a slice of the underlying words.
 846     pub fn words(&self) -> &[Word] {
 847         &self.words
 848     }
 849
 850     /// Iterates through all the columns set to true in a given row of
 851     /// the matrix.
 852     pub fn iter(&self, row: R) -> BitIter<'_, C> {
 853         assert!(row.index() < self.num_rows);
 854         let (start, end) = self.range(row);
 855         BitIter {
 856             cur: None,
 857             iter: self.words[start..end].iter().enumerate(),
 858             marker: PhantomData,
 859         }
 860     }
 861
 862     /// Returns the number of elements in `row`.
 863     pub fn count(&self, row: R) -> usize {
 864         let (start, end) = self.range(row);
 865         self.words[start..end].iter().map(|e| e.count_ones() as usize).sum()
 866     }
 867 }
 868
 869 /// A fixed-column-size, variable-row-size 2D bit matrix with a moderately
 870 /// sparse representation.
 871 ///
 872 /// Initially, every row has no explicit representation. If any bit within a
 873 /// row is set, the entire row is instantiated as `Some(<HybridBitSet>)`.
 874 /// Furthermore, any previously uninstantiated rows prior to it will be
 875 /// instantiated as `None`. Those prior rows may themselves become fully
 876 /// instantiated later on if any of their bits are set.
 877 ///
 878 /// `R` and `C` are index types used to identify rows and columns respectively;
 879 /// typically newtyped `usize` wrappers, but they can also just be `usize`.
 880 #[derive(Clone, Debug)]
 881 pub struct SparseBitMatrix<R, C>
 882 where
 883     R: Idx,
 884     C: Idx,
 885 {
 886     num_columns: usize,
 887     rows: IndexVec<R, Option<HybridBitSet<C>>>,
 888 }
 889
 890 impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
 891     /// Creates a new empty sparse bit matrix with no rows or columns.
 892     pub fn new(num_columns: usize) -> Self {
 893         Self {
 894             num_columns,
 895             rows: IndexVec::new(),
 896         }
 897     }
 898
 899     fn ensure_row(&mut self, row: R) -> &mut HybridBitSet<C> {
 900         // Instantiate any missing rows up to and including row `row` with an
 901         // empty HybridBitSet.
 902         self.rows.ensure_contains_elem(row, || None);
 903
 904         // Then replace row `row` with a full HybridBitSet if necessary.
 905         let num_columns = self.num_columns;
 906         self.rows[row].get_or_insert_with(|| HybridBitSet::new_empty(num_columns))
 907     }
 908
 909     /// Sets the cell at `(row, column)` to true. Put another way, insert
 910     /// `column` to the bitset for `row`.
 911     ///
 912     /// Returns `true` if this changed the matrix.
 913     pub fn insert(&mut self, row: R, column: C) -> bool {
 914         self.ensure_row(row).insert(column)
 915     }
 916
 917     /// Do the bits from `row` contain `column`? Put another way, is
 918     /// the matrix cell at `(row, column)` true?  Put yet another way,
 919     /// if the matrix represents (transitive) reachability, can
 920     /// `row` reach `column`?
 921     pub fn contains(&self, row: R, column: C) -> bool {
 922         self.row(row).map_or(false, |r| r.contains(column))
 923     }
 924
 925     /// Adds the bits from row `read` to the bits from row `write`, and
 926     /// returns `true` if anything changed.
 927     ///
 928     /// This is used when computing transitive reachability because if
 929     /// you have an edge `write -> read`, because in that case
 930     /// `write` can reach everything that `read` can (and
 931     /// potentially more).
 932     pub fn union_rows(&mut self, read: R, write: R) -> bool {
 933         if read == write || self.row(read).is_none() {
 934             return false;
 935         }
 936
 937         self.ensure_row(write);
 938         if let (Some(read_row), Some(write_row)) = self.rows.pick2_mut(read, write) {
 939             write_row.union(read_row)
 940         } else {
 941             unreachable!()
 942         }
 943     }
 944
 945     /// Union a row, `from`, into the `into` row.
 946     pub fn union_into_row(&mut self, into: R, from: &HybridBitSet<C>) -> bool {
 947         self.ensure_row(into).union(from)
 948     }
 949
 950     /// Insert all bits in the given row.
 951     pub fn insert_all_into_row(&mut self, row: R) {
 952         self.ensure_row(row).insert_all();
 953     }
 954
 955     pub fn rows(&self) -> impl Iterator<Item = R> {
 956         self.rows.indices()
 957     }
 958
 959     /// Iterates through all the columns set to true in a given row of
 960     /// the matrix.
 961     pub fn iter<'a>(&'a self, row: R) -> impl Iterator<Item = C> + 'a {
 962         self.row(row).into_iter().flat_map(|r| r.iter())
 963     }
 964
 965     pub fn row(&self, row: R) -> Option<&HybridBitSet<C>> {
 966         if let Some(Some(row)) = self.rows.get(row) {
 967             Some(row)
 968         } else {
 969             None
 970         }
 971     }
 972 }
 973
 974 #[inline]
 975 fn num_words<T: Idx>(domain_size: T) -> usize {
 976     (domain_size.index() + WORD_BITS - 1) / WORD_BITS
 977 }
 978
 979 #[inline]
 980 fn word_index_and_mask<T: Idx>(elem: T) -> (usize, Word) {
 981     let elem = elem.index();
 982     let word_index = elem / WORD_BITS;
 983     let mask = 1 << (elem % WORD_BITS);
 984     (word_index, mask)
 985 }
 986
 987 #[test]
 988 fn test_new_filled() {
 989     for i in 0..128 {
 990         let idx_buf = BitSet::new_filled(i);
 991         let elems: Vec<usize> = idx_buf.iter().collect();
 992         let expected: Vec<usize> = (0..i).collect();
 993         assert_eq!(elems, expected);
 994     }
 995 }
 996
 997 #[test]
 998 fn bitset_iter_works() {
 999     let mut bitset: BitSet<usize> = BitSet::new_empty(100);
1000     bitset.insert(1);
1001     bitset.insert(10);
1002     bitset.insert(19);
1003     bitset.insert(62);
1004     bitset.insert(63);
1005     bitset.insert(64);
1006     bitset.insert(65);
1007     bitset.insert(66);
1008     bitset.insert(99);
1009     assert_eq!(
1010         bitset.iter().collect::<Vec<_>>(),
1011         [1, 10, 19, 62, 63, 64, 65, 66, 99]
1012     );
1013 }
1014
1015 #[test]
1016 fn bitset_iter_works_2() {
1017     let mut bitset: BitSet<usize> = BitSet::new_empty(320);
1018     bitset.insert(0);
1019     bitset.insert(127);
1020     bitset.insert(191);
1021     bitset.insert(255);
1022     bitset.insert(319);
1023     assert_eq!(bitset.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
1024 }
1025
1026 #[test]
1027 fn union_two_sets() {
1028     let mut set1: BitSet<usize> = BitSet::new_empty(65);
1029     let mut set2: BitSet<usize> = BitSet::new_empty(65);
1030     assert!(set1.insert(3));
1031     assert!(!set1.insert(3));
1032     assert!(set2.insert(5));
1033     assert!(set2.insert(64));
1034     assert!(set1.union(&set2));
1035     assert!(!set1.union(&set2));
1036     assert!(set1.contains(3));
1037     assert!(!set1.contains(4));
1038     assert!(set1.contains(5));
1039     assert!(!set1.contains(63));
1040     assert!(set1.contains(64));
1041 }
1042
1043 #[test]
1044 fn hybrid_bitset() {
1045     let mut sparse038: HybridBitSet<usize> = HybridBitSet::new_empty(256);
1046     assert!(sparse038.is_empty());
1047     assert!(sparse038.insert(0));
1048     assert!(sparse038.insert(1));
1049     assert!(sparse038.insert(8));
1050     assert!(sparse038.insert(3));
1051     assert!(!sparse038.insert(3));
1052     assert!(sparse038.remove(1));
1053     assert!(!sparse038.is_empty());
1054     assert_eq!(sparse038.iter().collect::<Vec<_>>(), [0, 3, 8]);
1055
1056     for i in 0..256 {
1057         if i == 0 || i == 3 || i == 8 {
1058             assert!(sparse038.contains(i));
1059         } else {
1060             assert!(!sparse038.contains(i));
1061         }
1062     }
1063
1064     let mut sparse01358 = sparse038.clone();
1065     assert!(sparse01358.insert(1));
1066     assert!(sparse01358.insert(5));
1067     assert_eq!(sparse01358.iter().collect::<Vec<_>>(), [0, 1, 3, 5, 8]);
1068
1069     let mut dense10 = HybridBitSet::new_empty(256);
1070     for i in 0..10 {
1071         assert!(dense10.insert(i));
1072     }
1073     assert!(!dense10.is_empty());
1074     assert_eq!(dense10.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1075
1076     let mut dense256 = HybridBitSet::new_empty(256);
1077     assert!(dense256.is_empty());
1078     dense256.insert_all();
1079     assert!(!dense256.is_empty());
1080     for i in 0..256 {
1081         assert!(dense256.contains(i));
1082     }
1083
1084     assert!(sparse038.superset(&sparse038));    // sparse + sparse (self)
1085     assert!(sparse01358.superset(&sparse038));  // sparse + sparse
1086     assert!(dense10.superset(&sparse038));      // dense + sparse
1087     assert!(dense10.superset(&dense10));        // dense + dense (self)
1088     assert!(dense256.superset(&dense10));       // dense + dense
1089
1090     let mut hybrid = sparse038;
1091     assert!(!sparse01358.union(&hybrid));       // no change
1092     assert!(hybrid.union(&sparse01358));
1093     assert!(hybrid.superset(&sparse01358) && sparse01358.superset(&hybrid));
1094     assert!(!dense10.union(&sparse01358));
1095     assert!(!dense256.union(&dense10));
1096     let mut dense = dense10;
1097     assert!(dense.union(&dense256));
1098     assert!(dense.superset(&dense256) && dense256.superset(&dense));
1099     assert!(hybrid.union(&dense256));
1100     assert!(hybrid.superset(&dense256) && dense256.superset(&hybrid));
1101
1102     assert_eq!(dense256.iter().count(), 256);
1103     let mut dense0 = dense256;
1104     for i in 0..256 {
1105         assert!(dense0.remove(i));
1106     }
1107     assert!(!dense0.remove(0));
1108     assert!(dense0.is_empty());
1109 }
1110
1111 #[test]
1112 fn grow() {
1113     let mut set: GrowableBitSet<usize> = GrowableBitSet::with_capacity(65);
1114     for index in 0..65 {
1115         assert!(set.insert(index));
1116         assert!(!set.insert(index));
1117     }
1118     set.ensure(128);
1119
1120     // Check if the bits set before growing are still set
1121     for index in 0..65 {
1122         assert!(set.contains(index));
1123     }
1124
1125     // Check if the new bits are all un-set
1126     for index in 65..128 {
1127         assert!(!set.contains(index));
1128     }
1129
1130     // Check that we can set all new bits without running out of bounds
1131     for index in 65..128 {
1132         assert!(set.insert(index));
1133         assert!(!set.insert(index));
1134     }
1135 }
1136
1137 #[test]
1138 fn matrix_intersection() {
1139     let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
1140
1141     // (*) Elements reachable from both 2 and 65.
1142
1143     matrix.insert(2, 3);
1144     matrix.insert(2, 6);
1145     matrix.insert(2, 10); // (*)
1146     matrix.insert(2, 64); // (*)
1147     matrix.insert(2, 65);
1148     matrix.insert(2, 130);
1149     matrix.insert(2, 160); // (*)
1150
1151     matrix.insert(64, 133);
1152
1153     matrix.insert(65, 2);
1154     matrix.insert(65, 8);
1155     matrix.insert(65, 10); // (*)
1156     matrix.insert(65, 64); // (*)
1157     matrix.insert(65, 68);
1158     matrix.insert(65, 133);
1159     matrix.insert(65, 160); // (*)
1160
1161     let intersection = matrix.intersect_rows(2, 64);
1162     assert!(intersection.is_empty());
1163
1164     let intersection = matrix.intersect_rows(2, 65);
1165     assert_eq!(intersection, &[10, 64, 160]);
1166 }
1167
1168 #[test]
1169 fn matrix_iter() {
1170     let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
1171     matrix.insert(3, 22);
1172     matrix.insert(3, 75);
1173     matrix.insert(2, 99);
1174     matrix.insert(4, 0);
1175     matrix.union_rows(3, 5);
1176     matrix.insert_all_into_row(6);
1177
1178     let expected = [99];
1179     let mut iter = expected.iter();
1180     for i in matrix.iter(2) {
1181         let j = *iter.next().unwrap();
1182         assert_eq!(i, j);
1183     }
1184     assert!(iter.next().is_none());
1185
1186     let expected = [22, 75];
1187     let mut iter = expected.iter();
1188     assert_eq!(matrix.count(3), expected.len());
1189     for i in matrix.iter(3) {
1190         let j = *iter.next().unwrap();
1191         assert_eq!(i, j);
1192     }
1193     assert!(iter.next().is_none());
1194
1195     let expected = [0];
1196     let mut iter = expected.iter();
1197     assert_eq!(matrix.count(4), expected.len());
1198     for i in matrix.iter(4) {
1199         let j = *iter.next().unwrap();
1200         assert_eq!(i, j);
1201     }
1202     assert!(iter.next().is_none());
1203
1204     let expected = [22, 75];
1205     let mut iter = expected.iter();
1206     assert_eq!(matrix.count(5), expected.len());
1207     for i in matrix.iter(5) {
1208         let j = *iter.next().unwrap();
1209         assert_eq!(i, j);
1210     }
1211     assert!(iter.next().is_none());
1212
1213     assert_eq!(matrix.count(6), 100);
1214     let mut count = 0;
1215     for (idx, i) in matrix.iter(6).enumerate() {
1216         assert_eq!(idx, i);
1217         count += 1;
1218     }
1219     assert_eq!(count, 100);
1220
1221     if let Some(i) = matrix.iter(7).next() {
1222         panic!("expected no elements in row, but contains element {:?}", i);
1223     }
1224 }
1225
1226 #[test]
1227 fn sparse_matrix_iter() {
1228     let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
1229     matrix.insert(3, 22);
1230     matrix.insert(3, 75);
1231     matrix.insert(2, 99);
1232     matrix.insert(4, 0);
1233     matrix.union_rows(3, 5);
1234
1235     let expected = [99];
1236     let mut iter = expected.iter();
1237     for i in matrix.iter(2) {
1238         let j = *iter.next().unwrap();
1239         assert_eq!(i, j);
1240     }
1241     assert!(iter.next().is_none());
1242
1243     let expected = [22, 75];
1244     let mut iter = expected.iter();
1245     for i in matrix.iter(3) {
1246         let j = *iter.next().unwrap();
1247         assert_eq!(i, j);
1248     }
1249     assert!(iter.next().is_none());
1250
1251     let expected = [0];
1252     let mut iter = expected.iter();
1253     for i in matrix.iter(4) {
1254         let j = *iter.next().unwrap();
1255         assert_eq!(i, j);
1256     }
1257     assert!(iter.next().is_none());
1258
1259     let expected = [22, 75];
1260     let mut iter = expected.iter();
1261     for i in matrix.iter(5) {
1262         let j = *iter.next().unwrap();
1263         assert_eq!(i, j);
1264     }
1265     assert!(iter.next().is_none());
1266 }
1267
1268 /// Merge dense hybrid set into empty sparse hybrid set.
1269 #[bench]
1270 fn union_hybrid_sparse_empty_to_dense(b: &mut Bencher) {
1271     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
1272     for i in 0..10 {
1273         assert!(pre_dense.insert(i));
1274     }
1275     let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
1276     b.iter(|| {
1277         let dense = pre_dense.clone();
1278         let mut sparse = pre_sparse.clone();
1279         sparse.union(&dense);
1280     })
1281 }
1282
1283 /// Merge dense hybrid set into full hybrid set with same indices.
1284 #[bench]
1285 fn union_hybrid_sparse_full_to_dense(b: &mut Bencher) {
1286     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
1287     for i in 0..10 {
1288         assert!(pre_dense.insert(i));
1289     }
1290     let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
1291     for i in 0..SPARSE_MAX {
1292         assert!(pre_sparse.insert(i));
1293     }
1294     b.iter(|| {
1295         let dense = pre_dense.clone();
1296         let mut sparse = pre_sparse.clone();
1297         sparse.union(&dense);
1298     })
1299 }
1300
1301 /// Merge dense hybrid set into full hybrid set with indices over the whole domain.
1302 #[bench]
1303 fn union_hybrid_sparse_domain_to_dense(b: &mut Bencher) {
1304     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX*64);
1305     for i in 0..10 {
1306         assert!(pre_dense.insert(i));
1307     }
1308     let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX*64);
1309     for i in 0..SPARSE_MAX {
1310         assert!(pre_sparse.insert(i*64));
1311     }
1312     b.iter(|| {
1313         let dense = pre_dense.clone();
1314         let mut sparse = pre_sparse.clone();
1315         sparse.union(&dense);
1316     })
1317 }
1318
1319 /// Merge dense hybrid set into empty hybrid set where the domain is very small.
1320 #[bench]
1321 fn union_hybrid_sparse_empty_small_domain(b: &mut Bencher) {
1322     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
1323     for i in 0..SPARSE_MAX {
1324         assert!(pre_dense.insert(i));
1325     }
1326     let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
1327     b.iter(|| {
1328         let dense = pre_dense.clone();
1329         let mut sparse = pre_sparse.clone();
1330         sparse.union(&dense);
1331     })
1332 }
1333
1334 /// Merge dense hybrid set into full hybrid set where the domain is very small.
1335 #[bench]
1336 fn union_hybrid_sparse_full_small_domain(b: &mut Bencher) {
1337     let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
1338     for i in 0..SPARSE_MAX {
1339         assert!(pre_dense.insert(i));
1340     }
1341     let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
1342     for i in 0..SPARSE_MAX {
1343         assert!(pre_sparse.insert(i));
1344     }
1345     b.iter(|| {
1346         let dense = pre_dense.clone();
1347         let mut sparse = pre_sparse.clone();
1348         sparse.union(&dense);
1349     })
1350 }