src/librustc_index/bit_set.rs

   1 use crate::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
   9 #[cfg(test)]
  10 mod tests;
  11
  12 pub type Word = u64;
  13 pub const WORD_BYTES: usize = mem::size_of::<Word>();
  14 pub const WORD_BITS: usize = WORD_BYTES * 8;
  15
  16 /// A fixed-size bitset type with a dense representation.
  17 ///
  18 /// NOTE: Use [`GrowableBitSet`] if you need support for resizing after creation.
  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 ///
  27 /// [`GrowableBitSet`]: struct.GrowableBitSet.html
  28 #[derive(Clone, Eq, PartialEq, RustcDecodable, RustcEncodable)]
  29 pub struct BitSet<T: Idx> {
  30     domain_size: usize,
  31     words: Vec<Word>,
  32     marker: PhantomData<T>,
  33 }
  34
  35 impl<T: Idx> BitSet<T> {
  36     /// Creates a new, empty bitset with a given `domain_size`.
  37     #[inline]
  38     pub fn new_empty(domain_size: usize) -> BitSet<T> {
  39         let num_words = num_words(domain_size);
  40         BitSet {
  41             domain_size,
  42             words: vec![0; num_words],
  43             marker: PhantomData,
  44         }
  45     }
  46
  47     /// Creates a new, filled bitset with a given `domain_size`.
  48     #[inline]
  49     pub fn new_filled(domain_size: usize) -> BitSet<T> {
  50         let num_words = num_words(domain_size);
  51         let mut result = BitSet {
  52             domain_size,
  53             words: vec![!0; num_words],
  54             marker: PhantomData,
  55         };
  56         result.clear_excess_bits();
  57         result
  58     }
  59
  60     /// Gets the domain size.
  61     pub fn domain_size(&self) -> usize {
  62         self.domain_size
  63     }
  64
  65     /// Clear all elements.
  66     #[inline]
  67     pub fn clear(&mut self) {
  68         for word in &mut self.words {
  69             *word = 0;
  70         }
  71     }
  72
  73     /// Clear excess bits in the final word.
  74     fn clear_excess_bits(&mut self) {
  75         let num_bits_in_final_word = self.domain_size % WORD_BITS;
  76         if num_bits_in_final_word > 0 {
  77             let mask = (1 << num_bits_in_final_word) - 1;
  78             let final_word_idx = self.words.len() - 1;
  79             self.words[final_word_idx] &= mask;
  80         }
  81     }
  82
  83     /// Efficiently overwrite `self` with `other`.
  84     pub fn overwrite(&mut self, other: &BitSet<T>) {
  85         assert!(self.domain_size == other.domain_size);
  86         self.words.clone_from_slice(&other.words);
  87     }
  88
  89     /// Count the number of set bits in the set.
  90     pub fn count(&self) -> usize {
  91         self.words.iter().map(|e| e.count_ones() as usize).sum()
  92     }
  93
  94     /// Returns `true` if `self` contains `elem`.
  95     #[inline]
  96     pub fn contains(&self, elem: T) -> bool {
  97         assert!(elem.index() < self.domain_size);
  98         let (word_index, mask) = word_index_and_mask(elem);
  99         (self.words[word_index] & mask) != 0
 100     }
 101
 102     /// Is `self` is a (non-strict) superset of `other`?
 103     #[inline]
 104     pub fn superset(&self, other: &BitSet<T>) -> bool {
 105         assert_eq!(self.domain_size, other.domain_size);
 106         self.words.iter().zip(&other.words).all(|(a, b)| (a & b) == *b)
 107     }
 108
 109     /// Is the set empty?
 110     #[inline]
 111     pub fn is_empty(&self) -> bool {
 112         self.words.iter().all(|a| *a == 0)
 113     }
 114
 115     /// Insert `elem`. Returns whether the set has changed.
 116     #[inline]
 117     pub fn insert(&mut self, elem: T) -> bool {
 118         assert!(elem.index() < self.domain_size);
 119         let (word_index, mask) = word_index_and_mask(elem);
 120         let word_ref = &mut self.words[word_index];
 121         let word = *word_ref;
 122         let new_word = word | mask;
 123         *word_ref = new_word;
 124         new_word != word
 125     }
 126
 127     /// Sets all bits to true.
 128     pub fn insert_all(&mut self) {
 129         for word in &mut self.words {
 130             *word = !0;
 131         }
 132         self.clear_excess_bits();
 133     }
 134
 135     /// Returns `true` if the set has changed.
 136     #[inline]
 137     pub fn remove(&mut self, elem: T) -> bool {
 138         assert!(elem.index() < self.domain_size);
 139         let (word_index, mask) = word_index_and_mask(elem);
 140         let word_ref = &mut self.words[word_index];
 141         let word = *word_ref;
 142         let new_word = word & !mask;
 143         *word_ref = new_word;
 144         new_word != word
 145     }
 146
 147     /// Sets `self = self | other` and returns `true` if `self` changed
 148     /// (i.e., if new bits were added).
 149     pub fn union(&mut self, other: &impl UnionIntoBitSet<T>) -> bool {
 150         other.union_into(self)
 151     }
 152
 153     /// Sets `self = self - other` and returns `true` if `self` changed.
 154     /// (i.e., if any bits were removed).
 155     pub fn subtract(&mut self, other: &impl SubtractFromBitSet<T>) -> bool {
 156         other.subtract_from(self)
 157     }
 158
 159     /// Sets `self = self & other` and return `true` if `self` changed.
 160     /// (i.e., if any bits were removed).
 161     pub fn intersect(&mut self, other: &BitSet<T>) -> bool {
 162         assert_eq!(self.domain_size, other.domain_size);
 163         bitwise(&mut self.words, &other.words, |a, b| { a & b })
 164     }
 165
 166     /// Gets a slice of the underlying words.
 167     pub fn words(&self) -> &[Word] {
 168         &self.words
 169     }
 170
 171     /// Iterates over the indices of set bits in a sorted order.
 172     #[inline]
 173     pub fn iter(&self) -> BitIter<'_, T> {
 174         BitIter::new(&self.words)
 175     }
 176
 177     /// Duplicates the set as a hybrid set.
 178     pub fn to_hybrid(&self) -> HybridBitSet<T> {
 179         // Note: we currently don't bother trying to make a Sparse set.
 180         HybridBitSet::Dense(self.to_owned())
 181     }
 182
 183     /// Set `self = self | other`. In contrast to `union` returns `true` if the set contains at
 184     /// least one bit that is not in `other` (i.e. `other` is not a superset of `self`).
 185     ///
 186     /// This is an optimization for union of a hybrid bitset.
 187     fn reverse_union_sparse(&mut self, sparse: &SparseBitSet<T>) -> bool {
 188         assert!(sparse.domain_size == self.domain_size);
 189         self.clear_excess_bits();
 190
 191         let mut not_already = false;
 192         // Index of the current word not yet merged.
 193         let mut current_index = 0;
 194         // Mask of bits that came from the sparse set in the current word.
 195         let mut new_bit_mask = 0;
 196         for (word_index, mask) in sparse.iter().map(|x| word_index_and_mask(*x)) {
 197             // Next bit is in a word not inspected yet.
 198             if word_index > current_index {
 199                 self.words[current_index] |= new_bit_mask;
 200                 // Were there any bits in the old word that did not occur in the sparse set?
 201                 not_already |= (self.words[current_index] ^ new_bit_mask) != 0;
 202                 // Check all words we skipped for any set bit.
 203                 not_already |= self.words[current_index+1..word_index].iter().any(|&x| x != 0);
 204                 // Update next word.
 205                 current_index = word_index;
 206                 // Reset bit mask, no bits have been merged yet.
 207                 new_bit_mask = 0;
 208             }
 209             // Add bit and mark it as coming from the sparse set.
 210             // self.words[word_index] |= mask;
 211             new_bit_mask |= mask;
 212         }
 213         self.words[current_index] |= new_bit_mask;
 214         // Any bits in the last inspected word that were not in the sparse set?
 215         not_already |= (self.words[current_index] ^ new_bit_mask) != 0;
 216         // Any bits in the tail? Note `clear_excess_bits` before.
 217         not_already |= self.words[current_index+1..].iter().any(|&x| x != 0);
 218
 219         not_already
 220     }
 221 }
 222
 223 /// This is implemented by all the bitsets so that BitSet::union() can be
 224 /// passed any type of bitset.
 225 pub trait UnionIntoBitSet<T: Idx> {
 226     // Performs `other = other | self`.
 227     fn union_into(&self, other: &mut BitSet<T>) -> bool;
 228 }
 229
 230 /// This is implemented by all the bitsets so that BitSet::subtract() can be
 231 /// passed any type of bitset.
 232 pub trait SubtractFromBitSet<T: Idx> {
 233     // Performs `other = other - self`.
 234     fn subtract_from(&self, other: &mut BitSet<T>) -> bool;
 235 }
 236
 237 impl<T: Idx> UnionIntoBitSet<T> for BitSet<T> {
 238     fn union_into(&self, other: &mut BitSet<T>) -> bool {
 239         assert_eq!(self.domain_size, other.domain_size);
 240         bitwise(&mut other.words, &self.words, |a, b| { a | b })
 241     }
 242 }
 243
 244 impl<T: Idx> SubtractFromBitSet<T> for BitSet<T> {
 245     fn subtract_from(&self, other: &mut BitSet<T>) -> bool {
 246         assert_eq!(self.domain_size, other.domain_size);
 247         bitwise(&mut other.words, &self.words, |a, b| { a & !b })
 248     }
 249 }
 250
 251 impl<T: Idx> fmt::Debug for BitSet<T> {
 252     fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result {
 253         w.debug_list()
 254          .entries(self.iter())
 255          .finish()
 256     }
 257 }
 258
 259 impl<T: Idx> ToString for BitSet<T> {
 260     fn to_string(&self) -> String {
 261         let mut result = String::new();
 262         let mut sep = '[';
 263
 264         // Note: this is a little endian printout of bytes.
 265
 266         // i tracks how many bits we have printed so far.
 267         let mut i = 0;
 268         for word in &self.words {
 269             let mut word = *word;
 270             for _ in 0..WORD_BYTES { // for each byte in `word`:
 271                 let remain = self.domain_size - i;
 272                 // If less than a byte remains, then mask just that many bits.
 273                 let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF };
 274                 assert!(mask <= 0xFF);
 275                 let byte = word & mask;
 276
 277                 result.push_str(&format!("{}{:02x}", sep, byte));
 278
 279                 if remain <= 8 { break; }
 280                 word >>= 8;
 281                 i += 8;
 282                 sep = '-';
 283             }
 284             sep = '|';
 285         }
 286         result.push(']');
 287
 288         result
 289     }
 290 }
 291
 292 pub struct BitIter<'a, T: Idx> {
 293     /// A copy of the current word, but with any already-visited bits cleared.
 294     /// (This lets us use `trailing_zeros()` to find the next set bit.) When it
 295     /// is reduced to 0, we move onto the next word.
 296     word: Word,
 297
 298     /// The offset (measured in bits) of the current word.
 299     offset: usize,
 300
 301     /// Underlying iterator over the words.
 302     iter: slice::Iter<'a, Word>,
 303
 304     marker: PhantomData<T>
 305 }
 306
 307 impl<'a, T: Idx> BitIter<'a, T> {
 308     #[inline]
 309     fn new(words: &'a [Word]) -> BitIter<'a, T> {
 310         // We initialize `word` and `offset` to degenerate values. On the first
 311         // call to `next()` we will fall through to getting the first word from
 312         // `iter`, which sets `word` to the first word (if there is one) and
 313         // `offset` to 0. Doing it this way saves us from having to maintain
 314         // additional state about whether we have started.
 315         BitIter {
 316             word: 0,
 317             offset: std::usize::MAX - (WORD_BITS - 1),
 318             iter: words.iter(),
 319             marker: PhantomData,
 320         }
 321     }
 322 }
 323
 324 impl<'a, T: Idx> Iterator for BitIter<'a, T> {
 325     type Item = T;
 326     fn next(&mut self) -> Option<T> {
 327         loop {
 328             if self.word != 0 {
 329                 // Get the position of the next set bit in the current word,
 330                 // then clear the bit.
 331                 let bit_pos = self.word.trailing_zeros() as usize;
 332                 let bit = 1 << bit_pos;
 333                 self.word ^= bit;
 334                 return Some(T::new(bit_pos + self.offset))
 335             }
 336
 337             // Move onto the next word. `wrapping_add()` is needed to handle
 338             // the degenerate initial value given to `offset` in `new()`.
 339             let word = self.iter.next()?;
 340             self.word = *word;
 341             self.offset = self.offset.wrapping_add(WORD_BITS);
 342         }
 343     }
 344 }
 345
 346 #[inline]
 347 fn bitwise<Op>(out_vec: &mut [Word], in_vec: &[Word], op: Op) -> bool
 348     where Op: Fn(Word, Word) -> Word
 349 {
 350     assert_eq!(out_vec.len(), in_vec.len());
 351     let mut changed = false;
 352     for (out_elem, in_elem) in out_vec.iter_mut().zip(in_vec.iter()) {
 353         let old_val = *out_elem;
 354         let new_val = op(old_val, *in_elem);
 355         *out_elem = new_val;
 356         changed |= old_val != new_val;
 357     }
 358     changed
 359 }
 360
 361 const SPARSE_MAX: usize = 8;
 362
 363 /// A fixed-size bitset type with a sparse representation and a maximum of
 364 /// `SPARSE_MAX` elements. The elements are stored as a sorted `SmallVec` with
 365 /// no duplicates; although `SmallVec` can spill its elements to the heap, that
 366 /// never happens within this type because of the `SPARSE_MAX` limit.
 367 ///
 368 /// This type is used by `HybridBitSet`; do not use directly.
 369 #[derive(Clone, Debug)]
 370 pub struct SparseBitSet<T: Idx> {
 371     domain_size: usize,
 372     elems: SmallVec<[T; SPARSE_MAX]>,
 373 }
 374
 375 impl<T: Idx> SparseBitSet<T> {
 376     fn new_empty(domain_size: usize) -> Self {
 377         SparseBitSet {
 378             domain_size,
 379             elems: SmallVec::new()
 380         }
 381     }
 382
 383     fn len(&self) -> usize {
 384         self.elems.len()
 385     }
 386
 387     fn is_empty(&self) -> bool {
 388         self.elems.len() == 0
 389     }
 390
 391     fn contains(&self, elem: T) -> bool {
 392         assert!(elem.index() < self.domain_size);
 393         self.elems.contains(&elem)
 394     }
 395
 396     fn insert(&mut self, elem: T) -> bool {
 397         assert!(elem.index() < self.domain_size);
 398         let changed = if let Some(i) = self.elems.iter().position(|&e| e >= elem) {
 399             if self.elems[i] == elem {
 400                 // `elem` is already in the set.
 401                 false
 402             } else {
 403                 // `elem` is smaller than one or more existing elements.
 404                 self.elems.insert(i, elem);
 405                 true
 406             }
 407         } else {
 408             // `elem` is larger than all existing elements.
 409             self.elems.push(elem);
 410             true
 411         };
 412         assert!(self.len() <= SPARSE_MAX);
 413         changed
 414     }
 415
 416     fn remove(&mut self, elem: T) -> bool {
 417         assert!(elem.index() < self.domain_size);
 418         if let Some(i) = self.elems.iter().position(|&e| e == elem) {
 419             self.elems.remove(i);
 420             true
 421         } else {
 422             false
 423         }
 424     }
 425
 426     fn to_dense(&self) -> BitSet<T> {
 427         let mut dense = BitSet::new_empty(self.domain_size);
 428         for elem in self.elems.iter() {
 429             dense.insert(*elem);
 430         }
 431         dense
 432     }
 433
 434     fn iter(&self) -> slice::Iter<'_, T> {
 435         self.elems.iter()
 436     }
 437 }
 438
 439 impl<T: Idx> UnionIntoBitSet<T> for SparseBitSet<T> {
 440     fn union_into(&self, other: &mut BitSet<T>) -> bool {
 441         assert_eq!(self.domain_size, other.domain_size);
 442         let mut changed = false;
 443         for elem in self.iter() {
 444             changed |= other.insert(*elem);
 445         }
 446         changed
 447     }
 448 }
 449
 450 impl<T: Idx> SubtractFromBitSet<T> for SparseBitSet<T> {
 451     fn subtract_from(&self, other: &mut BitSet<T>) -> bool {
 452         assert_eq!(self.domain_size, other.domain_size);
 453         let mut changed = false;
 454         for elem in self.iter() {
 455             changed |= other.remove(*elem);
 456         }
 457         changed
 458     }
 459 }
 460
 461 /// A fixed-size bitset type with a hybrid representation: sparse when there
 462 /// are up to a `SPARSE_MAX` elements in the set, but dense when there are more
 463 /// than `SPARSE_MAX`.
 464 ///
 465 /// This type is especially efficient for sets that typically have a small
 466 /// number of elements, but a large `domain_size`, and are cleared frequently.
 467 ///
 468 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
 469 /// just be `usize`.
 470 ///
 471 /// All operations that involve an element will panic if the element is equal
 472 /// to or greater than the domain size. All operations that involve two bitsets
 473 /// will panic if the bitsets have differing domain sizes.
 474 #[derive(Clone, Debug)]
 475 pub enum HybridBitSet<T: Idx> {
 476     Sparse(SparseBitSet<T>),
 477     Dense(BitSet<T>),
 478 }
 479
 480 impl<T: Idx> HybridBitSet<T> {
 481     pub fn new_empty(domain_size: usize) -> Self {
 482         HybridBitSet::Sparse(SparseBitSet::new_empty(domain_size))
 483     }
 484
 485     fn domain_size(&self) -> usize {
 486         match self {
 487             HybridBitSet::Sparse(sparse) => sparse.domain_size,
 488             HybridBitSet::Dense(dense) => dense.domain_size,
 489         }
 490     }
 491
 492     pub fn clear(&mut self) {
 493         let domain_size = self.domain_size();
 494         *self = HybridBitSet::new_empty(domain_size);
 495     }
 496
 497     pub fn contains(&self, elem: T) -> bool {
 498         match self {
 499             HybridBitSet::Sparse(sparse) => sparse.contains(elem),
 500             HybridBitSet::Dense(dense) => dense.contains(elem),
 501         }
 502     }
 503
 504     pub fn superset(&self, other: &HybridBitSet<T>) -> bool {
 505         match (self, other) {
 506             (HybridBitSet::Dense(self_dense), HybridBitSet::Dense(other_dense)) => {
 507                 self_dense.superset(other_dense)
 508             }
 509             _ => {
 510                 assert!(self.domain_size() == other.domain_size());
 511                 other.iter().all(|elem| self.contains(elem))
 512             }
 513         }
 514     }
 515
 516     pub fn is_empty(&self) -> bool {
 517         match self {
 518             HybridBitSet::Sparse(sparse) => sparse.is_empty(),
 519             HybridBitSet::Dense(dense) => dense.is_empty(),
 520         }
 521     }
 522
 523     pub fn insert(&mut self, elem: T) -> bool {
 524         // No need to check `elem` against `self.domain_size` here because all
 525         // the match cases check it, one way or another.
 526         match self {
 527             HybridBitSet::Sparse(sparse) if sparse.len() < SPARSE_MAX => {
 528                 // The set is sparse and has space for `elem`.
 529                 sparse.insert(elem)
 530             }
 531             HybridBitSet::Sparse(sparse) if sparse.contains(elem) => {
 532                 // The set is sparse and does not have space for `elem`, but
 533                 // that doesn't matter because `elem` is already present.
 534                 false
 535             }
 536             HybridBitSet::Sparse(sparse) => {
 537                 // The set is sparse and full. Convert to a dense set.
 538                 let mut dense = sparse.to_dense();
 539                 let changed = dense.insert(elem);
 540                 assert!(changed);
 541                 *self = HybridBitSet::Dense(dense);
 542                 changed
 543             }
 544             HybridBitSet::Dense(dense) => dense.insert(elem),
 545         }
 546     }
 547
 548     pub fn insert_all(&mut self) {
 549         let domain_size = self.domain_size();
 550         match self {
 551             HybridBitSet::Sparse(_) => {
 552                 *self = HybridBitSet::Dense(BitSet::new_filled(domain_size));
 553             }
 554             HybridBitSet::Dense(dense) => dense.insert_all(),
 555         }
 556     }
 557
 558     pub fn remove(&mut self, elem: T) -> bool {
 559         // Note: we currently don't bother going from Dense back to Sparse.
 560         match self {
 561             HybridBitSet::Sparse(sparse) => sparse.remove(elem),
 562             HybridBitSet::Dense(dense) => dense.remove(elem),
 563         }
 564     }
 565
 566     pub fn union(&mut self, other: &HybridBitSet<T>) -> bool {
 567         match self {
 568             HybridBitSet::Sparse(self_sparse) => {
 569                 match other {
 570                     HybridBitSet::Sparse(other_sparse) => {
 571                         // Both sets are sparse. Add the elements in
 572                         // `other_sparse` to `self` one at a time. This
 573                         // may or may not cause `self` to be densified.
 574                         assert_eq!(self.domain_size(), other.domain_size());
 575                         let mut changed = false;
 576                         for elem in other_sparse.iter() {
 577                             changed |= self.insert(*elem);
 578                         }
 579                         changed
 580                     }
 581                     HybridBitSet::Dense(other_dense) => {
 582                         // `self` is sparse and `other` is dense. To
 583                         // merge them, we have two available strategies:
 584                         // * Densify `self` then merge other
 585                         // * Clone other then integrate bits from `self`
 586                         // The second strategy requires dedicated method
 587                         // since the usual `union` returns the wrong
 588                         // result. In the dedicated case the computation
 589                         // is slightly faster if the bits of the sparse
 590                         // bitset map to only few words of the dense
 591                         // representation, i.e. indices are near each
 592                         // other.
 593                         //
 594                         // Benchmarking seems to suggest that the second
 595                         // option is worth it.
 596                         let mut new_dense = other_dense.clone();
 597                         let changed = new_dense.reverse_union_sparse(self_sparse);
 598                         *self = HybridBitSet::Dense(new_dense);
 599                         changed
 600                     }
 601                 }
 602             }
 603
 604             HybridBitSet::Dense(self_dense) => self_dense.union(other),
 605         }
 606     }
 607
 608     /// Converts to a dense set, consuming itself in the process.
 609     pub fn to_dense(self) -> BitSet<T> {
 610         match self {
 611             HybridBitSet::Sparse(sparse) => sparse.to_dense(),
 612             HybridBitSet::Dense(dense) => dense,
 613         }
 614     }
 615
 616     pub fn iter(&self) -> HybridIter<'_, T> {
 617         match self {
 618             HybridBitSet::Sparse(sparse) => HybridIter::Sparse(sparse.iter()),
 619             HybridBitSet::Dense(dense) => HybridIter::Dense(dense.iter()),
 620         }
 621     }
 622 }
 623
 624 impl<T: Idx> UnionIntoBitSet<T> for HybridBitSet<T> {
 625     fn union_into(&self, other: &mut BitSet<T>) -> bool {
 626         match self {
 627             HybridBitSet::Sparse(sparse) => sparse.union_into(other),
 628             HybridBitSet::Dense(dense) => dense.union_into(other),
 629         }
 630     }
 631 }
 632
 633 impl<T: Idx> SubtractFromBitSet<T> for HybridBitSet<T> {
 634     fn subtract_from(&self, other: &mut BitSet<T>) -> bool {
 635         match self {
 636             HybridBitSet::Sparse(sparse) => sparse.subtract_from(other),
 637             HybridBitSet::Dense(dense) => dense.subtract_from(other),
 638         }
 639     }
 640 }
 641
 642 pub enum HybridIter<'a, T: Idx> {
 643     Sparse(slice::Iter<'a, T>),
 644     Dense(BitIter<'a, T>),
 645 }
 646
 647 impl<'a, T: Idx> Iterator for HybridIter<'a, T> {
 648     type Item = T;
 649
 650     fn next(&mut self) -> Option<T> {
 651         match self {
 652             HybridIter::Sparse(sparse) => sparse.next().copied(),
 653             HybridIter::Dense(dense) => dense.next(),
 654         }
 655     }
 656 }
 657
 658 /// A resizable bitset type with a dense representation.
 659 ///
 660 /// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
 661 /// just be `usize`.
 662 ///
 663 /// All operations that involve an element will panic if the element is equal
 664 /// to or greater than the domain size.
 665 #[derive(Clone, Debug, PartialEq)]
 666 pub struct GrowableBitSet<T: Idx> {
 667     bit_set: BitSet<T>,
 668 }
 669
 670 impl<T: Idx> GrowableBitSet<T> {
 671     /// Ensure that the set can hold at least `min_domain_size` elements.
 672     pub fn ensure(&mut self, min_domain_size: usize) {
 673         if self.bit_set.domain_size < min_domain_size {
 674             self.bit_set.domain_size = min_domain_size;
 675         }
 676
 677         let min_num_words = num_words(min_domain_size);
 678         if self.bit_set.words.len() < min_num_words {
 679             self.bit_set.words.resize(min_num_words, 0)
 680         }
 681     }
 682
 683     pub fn new_empty() -> GrowableBitSet<T> {
 684         GrowableBitSet { bit_set: BitSet::new_empty(0) }
 685     }
 686
 687     pub fn with_capacity(capacity: usize) -> GrowableBitSet<T> {
 688         GrowableBitSet { bit_set: BitSet::new_empty(capacity) }
 689     }
 690
 691     /// Returns `true` if the set has changed.
 692     #[inline]
 693     pub fn insert(&mut self, elem: T) -> bool {
 694         self.ensure(elem.index() + 1);
 695         self.bit_set.insert(elem)
 696     }
 697
 698     #[inline]
 699     pub fn contains(&self, elem: T) -> bool {
 700         let (word_index, mask) = word_index_and_mask(elem);
 701         if let Some(word) = self.bit_set.words.get(word_index) {
 702             (word & mask) != 0
 703         } else {
 704             false
 705         }
 706     }
 707 }
 708
 709 /// A fixed-size 2D bit matrix type with a dense representation.
 710 ///
 711 /// `R` and `C` are index types used to identify rows and columns respectively;
 712 /// typically newtyped `usize` wrappers, but they can also just be `usize`.
 713 ///
 714 /// All operations that involve a row and/or column index will panic if the
 715 /// index exceeds the relevant bound.
 716 #[derive(Clone, Debug, Eq, PartialEq, RustcDecodable, RustcEncodable)]
 717 pub struct BitMatrix<R: Idx, C: Idx> {
 718     num_rows: usize,
 719     num_columns: usize,
 720     words: Vec<Word>,
 721     marker: PhantomData<(R, C)>,
 722 }
 723
 724 impl<R: Idx, C: Idx> BitMatrix<R, C> {
 725     /// Creates a new `rows x columns` matrix, initially empty.
 726     pub fn new(num_rows: usize, num_columns: usize) -> BitMatrix<R, C> {
 727         // For every element, we need one bit for every other
 728         // element. Round up to an even number of words.
 729         let words_per_row = num_words(num_columns);
 730         BitMatrix {
 731             num_rows,
 732             num_columns,
 733             words: vec![0; num_rows * words_per_row],
 734             marker: PhantomData,
 735         }
 736     }
 737
 738     /// Creates a new matrix, with `row` used as the value for every row.
 739     pub fn from_row_n(row: &BitSet<C>, num_rows: usize) -> BitMatrix<R, C> {
 740         let num_columns = row.domain_size();
 741         let words_per_row = num_words(num_columns);
 742         assert_eq!(words_per_row, row.words().len());
 743         BitMatrix {
 744             num_rows,
 745             num_columns,
 746             words: iter::repeat(row.words()).take(num_rows).flatten().cloned().collect(),
 747             marker: PhantomData,
 748         }
 749     }
 750
 751     pub fn rows(&self) -> impl Iterator<Item = R> {
 752         (0..self.num_rows).map(R::new)
 753     }
 754
 755     /// The range of bits for a given row.
 756     fn range(&self, row: R) -> (usize, usize) {
 757         let words_per_row = num_words(self.num_columns);
 758         let start = row.index() * words_per_row;
 759         (start, start + words_per_row)
 760     }
 761
 762     /// Sets the cell at `(row, column)` to true. Put another way, insert
 763     /// `column` to the bitset for `row`.
 764     ///
 765     /// Returns `true` if this changed the matrix.
 766     pub fn insert(&mut self, row: R, column: C) -> bool {
 767         assert!(row.index() < self.num_rows && column.index() < self.num_columns);
 768         let (start, _) = self.range(row);
 769         let (word_index, mask) = word_index_and_mask(column);
 770         let words = &mut self.words[..];
 771         let word = words[start + word_index];
 772         let new_word = word | mask;
 773         words[start + word_index] = new_word;
 774         word != new_word
 775     }
 776
 777     /// Do the bits from `row` contain `column`? Put another way, is
 778     /// the matrix cell at `(row, column)` true?  Put yet another way,
 779     /// if the matrix represents (transitive) reachability, can
 780     /// `row` reach `column`?
 781     pub fn contains(&self, row: R, column: C) -> bool {
 782         assert!(row.index() < self.num_rows && column.index() < self.num_columns);
 783         let (start, _) = self.range(row);
 784         let (word_index, mask) = word_index_and_mask(column);
 785         (self.words[start + word_index] & mask) != 0
 786     }
 787
 788     /// Returns those indices that are true in rows `a` and `b`. This
 789     /// is an O(n) operation where `n` is the number of elements
 790     /// (somewhat independent from the actual size of the
 791     /// intersection, in particular).
 792     pub fn intersect_rows(&self, row1: R, row2: R) -> Vec<C> {
 793         assert!(row1.index() < self.num_rows && row2.index() < self.num_rows);
 794         let (row1_start, row1_end) = self.range(row1);
 795         let (row2_start, row2_end) = self.range(row2);
 796         let mut result = Vec::with_capacity(self.num_columns);
 797         for (base, (i, j)) in (row1_start..row1_end).zip(row2_start..row2_end).enumerate() {
 798             let mut v = self.words[i] & self.words[j];
 799             for bit in 0..WORD_BITS {
 800                 if v == 0 {
 801                     break;
 802                 }
 803                 if v & 0x1 != 0 {
 804                     result.push(C::new(base * WORD_BITS + bit));
 805                 }
 806                 v >>= 1;
 807             }
 808         }
 809         result
 810     }
 811
 812     /// Adds the bits from row `read` to the bits from row `write`, and
 813     /// returns `true` if anything changed.
 814     ///
 815     /// This is used when computing transitive reachability because if
 816     /// you have an edge `write -> read`, because in that case
 817     /// `write` can reach everything that `read` can (and
 818     /// potentially more).
 819     pub fn union_rows(&mut self, read: R, write: R) -> bool {
 820         assert!(read.index() < self.num_rows && write.index() < self.num_rows);
 821         let (read_start, read_end) = self.range(read);
 822         let (write_start, write_end) = self.range(write);
 823         let words = &mut self.words[..];
 824         let mut changed = false;
 825         for (read_index, write_index) in (read_start..read_end).zip(write_start..write_end) {
 826             let word = words[write_index];
 827             let new_word = word | words[read_index];
 828             words[write_index] = new_word;
 829             changed |= word != new_word;
 830         }
 831         changed
 832     }
 833
 834     /// Adds the bits from `with` to the bits from row `write`, and
 835     /// returns `true` if anything changed.
 836     pub fn union_row_with(&mut self, with: &BitSet<C>, write: R) -> bool {
 837         assert!(write.index() < self.num_rows);
 838         assert_eq!(with.domain_size(), self.num_columns);
 839         let (write_start, write_end) = self.range(write);
 840         let mut changed = false;
 841         for (read_index, write_index) in (0..with.words().len()).zip(write_start..write_end) {
 842             let word = self.words[write_index];
 843             let new_word = word | with.words()[read_index];
 844             self.words[write_index] = new_word;
 845             changed |= word != new_word;
 846         }
 847         changed
 848     }
 849
 850     /// Sets every cell in `row` to true.
 851     pub fn insert_all_into_row(&mut self, row: R) {
 852         assert!(row.index() < self.num_rows);
 853         let (start, end) = self.range(row);
 854         let words = &mut self.words[..];
 855         for index in start..end {
 856             words[index] = !0;
 857         }
 858         self.clear_excess_bits(row);
 859     }
 860
 861     /// Clear excess bits in the final word of the row.
 862     fn clear_excess_bits(&mut self, row: R) {
 863         let num_bits_in_final_word = self.num_columns % WORD_BITS;
 864         if num_bits_in_final_word > 0 {
 865             let mask = (1 << num_bits_in_final_word) - 1;
 866             let (_, end) = self.range(row);
 867             let final_word_idx = end - 1;
 868             self.words[final_word_idx] &= mask;
 869         }
 870     }
 871
 872     /// Gets a slice of the underlying words.
 873     pub fn words(&self) -> &[Word] {
 874         &self.words
 875     }
 876
 877     /// Iterates through all the columns set to true in a given row of
 878     /// the matrix.
 879     pub fn iter(&self, row: R) -> BitIter<'_, C> {
 880         assert!(row.index() < self.num_rows);
 881         let (start, end) = self.range(row);
 882         BitIter::new(&self.words[start..end])
 883     }
 884
 885     /// Returns the number of elements in `row`.
 886     pub fn count(&self, row: R) -> usize {
 887         let (start, end) = self.range(row);
 888         self.words[start..end].iter().map(|e| e.count_ones() as usize).sum()
 889     }
 890 }
 891
 892 /// A fixed-column-size, variable-row-size 2D bit matrix with a moderately
 893 /// sparse representation.
 894 ///
 895 /// Initially, every row has no explicit representation. If any bit within a
 896 /// row is set, the entire row is instantiated as `Some(<HybridBitSet>)`.
 897 /// Furthermore, any previously uninstantiated rows prior to it will be
 898 /// instantiated as `None`. Those prior rows may themselves become fully
 899 /// instantiated later on if any of their bits are set.
 900 ///
 901 /// `R` and `C` are index types used to identify rows and columns respectively;
 902 /// typically newtyped `usize` wrappers, but they can also just be `usize`.
 903 #[derive(Clone, Debug)]
 904 pub struct SparseBitMatrix<R, C>
 905 where
 906     R: Idx,
 907     C: Idx,
 908 {
 909     num_columns: usize,
 910     rows: IndexVec<R, Option<HybridBitSet<C>>>,
 911 }
 912
 913 impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
 914     /// Creates a new empty sparse bit matrix with no rows or columns.
 915     pub fn new(num_columns: usize) -> Self {
 916         Self {
 917             num_columns,
 918             rows: IndexVec::new(),
 919         }
 920     }
 921
 922     fn ensure_row(&mut self, row: R) -> &mut HybridBitSet<C> {
 923         // Instantiate any missing rows up to and including row `row` with an
 924         // empty HybridBitSet.
 925         self.rows.ensure_contains_elem(row, || None);
 926
 927         // Then replace row `row` with a full HybridBitSet if necessary.
 928         let num_columns = self.num_columns;
 929         self.rows[row].get_or_insert_with(|| HybridBitSet::new_empty(num_columns))
 930     }
 931
 932     /// Sets the cell at `(row, column)` to true. Put another way, insert
 933     /// `column` to the bitset for `row`.
 934     ///
 935     /// Returns `true` if this changed the matrix.
 936     pub fn insert(&mut self, row: R, column: C) -> bool {
 937         self.ensure_row(row).insert(column)
 938     }
 939
 940     /// Do the bits from `row` contain `column`? Put another way, is
 941     /// the matrix cell at `(row, column)` true?  Put yet another way,
 942     /// if the matrix represents (transitive) reachability, can
 943     /// `row` reach `column`?
 944     pub fn contains(&self, row: R, column: C) -> bool {
 945         self.row(row).map_or(false, |r| r.contains(column))
 946     }
 947
 948     /// Adds the bits from row `read` to the bits from row `write`, and
 949     /// returns `true` if anything changed.
 950     ///
 951     /// This is used when computing transitive reachability because if
 952     /// you have an edge `write -> read`, because in that case
 953     /// `write` can reach everything that `read` can (and
 954     /// potentially more).
 955     pub fn union_rows(&mut self, read: R, write: R) -> bool {
 956         if read == write || self.row(read).is_none() {
 957             return false;
 958         }
 959
 960         self.ensure_row(write);
 961         if let (Some(read_row), Some(write_row)) = self.rows.pick2_mut(read, write) {
 962             write_row.union(read_row)
 963         } else {
 964             unreachable!()
 965         }
 966     }
 967
 968     /// Union a row, `from`, into the `into` row.
 969     pub fn union_into_row(&mut self, into: R, from: &HybridBitSet<C>) -> bool {
 970         self.ensure_row(into).union(from)
 971     }
 972
 973     /// Insert all bits in the given row.
 974     pub fn insert_all_into_row(&mut self, row: R) {
 975         self.ensure_row(row).insert_all();
 976     }
 977
 978     pub fn rows(&self) -> impl Iterator<Item = R> {
 979         self.rows.indices()
 980     }
 981
 982     /// Iterates through all the columns set to true in a given row of
 983     /// the matrix.
 984     pub fn iter<'a>(&'a self, row: R) -> impl Iterator<Item = C> + 'a {
 985         self.row(row).into_iter().flat_map(|r| r.iter())
 986     }
 987
 988     pub fn row(&self, row: R) -> Option<&HybridBitSet<C>> {
 989         if let Some(Some(row)) = self.rows.get(row) {
 990             Some(row)
 991         } else {
 992             None
 993         }
 994     }
 995 }
 996
 997 #[inline]
 998 fn num_words<T: Idx>(domain_size: T) -> usize {
 999     (domain_size.index() + WORD_BITS - 1) / WORD_BITS
1000 }
1001
1002 #[inline]
1003 fn word_index_and_mask<T: Idx>(elem: T) -> (usize, Word) {
1004     let elem = elem.index();
1005     let word_index = elem / WORD_BITS;
1006     let mask = 1 << (elem % WORD_BITS);
1007     (word_index, mask)
1008 }