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