src/librustc_data_structures/bit_set.rs

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