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