src/librustc_data_structures/bitvec.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 std::iter;
  14 use std::marker::PhantomData;
  15 use std::slice;
  16
  17 pub type Word = u64;
  18 pub const WORD_BYTES: usize = ::std::mem::size_of::<Word>();
  19 pub const WORD_BITS: usize = WORD_BYTES * 8;
  20
  21 /// A very simple BitArray type.
  22 ///
  23 /// It does not support resizing after creation; use `BitVector` for that.
  24 #[derive(Clone, Debug, Eq, PartialEq)]
  25 pub struct BitArray<C: Idx> {
  26     data: Vec<Word>,
  27     marker: PhantomData<C>,
  28 }
  29
  30 impl<C: Idx> BitArray<C> {
  31     // Do not make this method public, instead switch your use case to BitVector.
  32     #[inline]
  33     fn grow(&mut self, num_bits: C) {
  34         let num_words = num_words(num_bits);
  35         if self.data.len() <= num_words {
  36             self.data.resize(num_words + 1, 0)
  37         }
  38     }
  39
  40     #[inline]
  41     pub fn new(num_bits: usize) -> BitArray<C> {
  42         BitArray::new_empty(num_bits)
  43     }
  44
  45     #[inline]
  46     pub fn new_empty(num_bits: usize) -> BitArray<C> {
  47         let num_words = num_words(num_bits);
  48         BitArray {
  49             data: vec![0; num_words],
  50             marker: PhantomData,
  51         }
  52     }
  53
  54     #[inline]
  55     pub fn new_filled(num_bits: usize) -> BitArray<C> {
  56         let num_words = num_words(num_bits);
  57         let mut result = BitArray {
  58             data: vec![!0; num_words],
  59             marker: PhantomData,
  60         };
  61         result.clear_above(num_bits);
  62         result
  63     }
  64
  65     #[inline]
  66     pub fn clear(&mut self) {
  67         for p in &mut self.data {
  68             *p = 0;
  69         }
  70     }
  71
  72     /// Sets all elements up to `num_bits`.
  73     pub fn set_up_to(&mut self, num_bits: usize) {
  74         for p in &mut self.data {
  75             *p = !0;
  76         }
  77         self.clear_above(num_bits);
  78     }
  79
  80     /// Clear all elements above `num_bits`.
  81     fn clear_above(&mut self, num_bits: usize) {
  82         let first_clear_block = num_bits / WORD_BITS;
  83
  84         if first_clear_block < self.data.len() {
  85             // Within `first_clear_block`, the `num_bits % WORD_BITS` LSBs
  86             // should remain.
  87             let mask = (1 << (num_bits % WORD_BITS)) - 1;
  88             self.data[first_clear_block] &= mask;
  89
  90             // All the blocks above `first_clear_block` are fully cleared.
  91             for b in &mut self.data[first_clear_block + 1..] {
  92                 *b = 0;
  93             }
  94         }
  95     }
  96
  97     pub fn count(&self) -> usize {
  98         self.data.iter().map(|e| e.count_ones() as usize).sum()
  99     }
 100
 101     /// True if `self` contains the bit `bit`.
 102     #[inline]
 103     pub fn contains(&self, bit: C) -> bool {
 104         let (word, mask) = word_mask(bit);
 105         (self.data[word] & mask) != 0
 106     }
 107
 108     /// True if `self` contains all the bits in `other`.
 109     ///
 110     /// The two vectors must have the same length.
 111     #[inline]
 112     pub fn contains_all(&self, other: &BitArray<C>) -> bool {
 113         assert_eq!(self.data.len(), other.data.len());
 114         self.data.iter().zip(&other.data).all(|(a, b)| (a & b) == *b)
 115     }
 116
 117     #[inline]
 118     pub fn is_empty(&self) -> bool {
 119         self.data.iter().all(|a| *a == 0)
 120     }
 121
 122     /// Returns true if the bit has changed.
 123     #[inline]
 124     pub fn insert(&mut self, bit: C) -> bool {
 125         let (word, mask) = word_mask(bit);
 126         let data = &mut self.data[word];
 127         let value = *data;
 128         let new_value = value | mask;
 129         *data = new_value;
 130         new_value != value
 131     }
 132
 133     /// Sets all bits to true.
 134     pub fn insert_all(&mut self) {
 135         for data in &mut self.data {
 136             *data = !0;
 137         }
 138     }
 139
 140     /// Returns true if the bit has changed.
 141     #[inline]
 142     pub fn remove(&mut self, bit: C) -> bool {
 143         let (word, mask) = word_mask(bit);
 144         let data = &mut self.data[word];
 145         let value = *data;
 146         let new_value = value & !mask;
 147         *data = new_value;
 148         new_value != value
 149     }
 150
 151     #[inline]
 152     pub fn merge(&mut self, all: &BitArray<C>) -> bool {
 153         assert!(self.data.len() == all.data.len());
 154         let mut changed = false;
 155         for (i, j) in self.data.iter_mut().zip(&all.data) {
 156             let value = *i;
 157             *i = value | *j;
 158             if value != *i {
 159                 changed = true;
 160             }
 161         }
 162         changed
 163     }
 164
 165     pub fn words(&self) -> &[Word] {
 166         &self.data
 167     }
 168
 169     pub fn words_mut(&mut self) -> &mut [Word] {
 170         &mut self.data
 171     }
 172
 173     /// Iterates over indexes of set bits in a sorted order
 174     #[inline]
 175     pub fn iter<'a>(&'a self) -> BitIter<'a, C> {
 176         BitIter {
 177             cur: None,
 178             iter: self.data.iter().enumerate(),
 179             marker: PhantomData,
 180         }
 181     }
 182 }
 183
 184 impl<T: Idx> rustc_serialize::Encodable for BitArray<T> {
 185     fn encode<E: rustc_serialize::Encoder>(&self, encoder: &mut E) -> Result<(), E::Error> {
 186         self.data.encode(encoder)
 187     }
 188 }
 189
 190 impl<T: Idx> rustc_serialize::Decodable for BitArray<T> {
 191     fn decode<D: rustc_serialize::Decoder>(d: &mut D) -> Result<BitArray<T>, D::Error> {
 192         let words: Vec<Word> = rustc_serialize::Decodable::decode(d)?;
 193         Ok(BitArray {
 194             data: words,
 195             marker: PhantomData,
 196         })
 197     }
 198 }
 199
 200 pub struct BitIter<'a, C: Idx> {
 201     cur: Option<(Word, usize)>,
 202     iter: iter::Enumerate<slice::Iter<'a, Word>>,
 203     marker: PhantomData<C>
 204 }
 205
 206 impl<'a, C: Idx> Iterator for BitIter<'a, C> {
 207     type Item = C;
 208     fn next(&mut self) -> Option<C> {
 209         loop {
 210             if let Some((ref mut word, offset)) = self.cur {
 211                 let bit_pos = word.trailing_zeros() as usize;
 212                 if bit_pos != WORD_BITS {
 213                     let bit = 1 << bit_pos;
 214                     *word ^= bit;
 215                     return Some(C::new(bit_pos + offset))
 216                 }
 217             }
 218
 219             let (i, word) = self.iter.next()?;
 220             self.cur = Some((*word, WORD_BITS * i));
 221         }
 222     }
 223 }
 224
 225 pub trait BitwiseOperator {
 226     /// Applies some bit-operation pointwise to each of the bits in the two inputs.
 227     fn join(&self, pred1: Word, pred2: Word) -> Word;
 228 }
 229
 230 #[inline]
 231 pub fn bitwise<Op: BitwiseOperator>(out_vec: &mut [Word], in_vec: &[Word], op: &Op) -> bool
 232 {
 233     assert_eq!(out_vec.len(), in_vec.len());
 234     let mut changed = false;
 235     for (out_elem, in_elem) in out_vec.iter_mut().zip(in_vec.iter()) {
 236         let old_val = *out_elem;
 237         let new_val = op.join(old_val, *in_elem);
 238         *out_elem = new_val;
 239         changed |= old_val != new_val;
 240     }
 241     changed
 242 }
 243
 244 pub struct Intersect;
 245 impl BitwiseOperator for Intersect {
 246     #[inline]
 247     fn join(&self, a: Word, b: Word) -> Word { a & b }
 248 }
 249
 250 pub struct Union;
 251 impl BitwiseOperator for Union {
 252     #[inline]
 253     fn join(&self, a: Word, b: Word) -> Word { a | b }
 254 }
 255
 256 pub struct Subtract;
 257 impl BitwiseOperator for Subtract {
 258     #[inline]
 259     fn join(&self, a: Word, b: Word) -> Word { a & !b }
 260 }
 261
 262 pub fn bits_to_string(words: &[Word], bits: usize) -> String {
 263     let mut result = String::new();
 264     let mut sep = '[';
 265
 266     // Note: this is a little endian printout of bytes.
 267
 268     // i tracks how many bits we have printed so far.
 269     let mut i = 0;
 270     for &word in words.iter() {
 271         let mut v = word;
 272         for _ in 0..WORD_BYTES { // for each byte in `v`:
 273             let remain = bits - i;
 274             // If less than a byte remains, then mask just that many bits.
 275             let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF };
 276             assert!(mask <= 0xFF);
 277             let byte = v & mask;
 278
 279             result.push_str(&format!("{}{:02x}", sep, byte));
 280
 281             if remain <= 8 { break; }
 282             v >>= 8;
 283             i += 8;
 284             sep = '-';
 285         }
 286         sep = '|';
 287     }
 288     result.push(']');
 289
 290     result
 291 }
 292
 293 /// A resizable BitVector type.
 294 #[derive(Clone, Debug, PartialEq)]
 295 pub struct BitVector<C: Idx> {
 296     data: BitArray<C>,
 297 }
 298
 299 impl<C: Idx> BitVector<C> {
 300     pub fn grow(&mut self, num_bits: C) {
 301         self.data.grow(num_bits)
 302     }
 303
 304     pub fn new() -> BitVector<C> {
 305         BitVector { data: BitArray::new(0) }
 306     }
 307
 308     pub fn with_capacity(bits: usize) -> BitVector<C> {
 309         BitVector { data: BitArray::new(bits) }
 310     }
 311
 312     /// Returns true if the bit has changed.
 313     #[inline]
 314     pub fn insert(&mut self, bit: C) -> bool {
 315         self.grow(bit);
 316         self.data.insert(bit)
 317     }
 318
 319     #[inline]
 320     pub fn contains(&self, bit: C) -> bool {
 321         let (word, mask) = word_mask(bit);
 322         if let Some(word) = self.data.data.get(word) {
 323             (word & mask) != 0
 324         } else {
 325             false
 326         }
 327     }
 328 }
 329
 330 /// A "bit matrix" is basically a matrix of booleans represented as
 331 /// one gigantic bitvector. In other words, it is as if you have
 332 /// `rows` bitvectors, each of length `columns`.
 333 #[derive(Clone, Debug)]
 334 pub struct BitMatrix<R: Idx, C: Idx> {
 335     columns: usize,
 336     vector: Vec<Word>,
 337     phantom: PhantomData<(R, C)>,
 338 }
 339
 340 impl<R: Idx, C: Idx> BitMatrix<R, C> {
 341     /// Create a new `rows x columns` matrix, initially empty.
 342     pub fn new(rows: usize, columns: usize) -> BitMatrix<R, C> {
 343         // For every element, we need one bit for every other
 344         // element. Round up to an even number of words.
 345         let words_per_row = num_words(columns);
 346         BitMatrix {
 347             columns,
 348             vector: vec![0; rows * words_per_row],
 349             phantom: PhantomData,
 350         }
 351     }
 352
 353     /// The range of bits for a given row.
 354     fn range(&self, row: R) -> (usize, usize) {
 355         let row = row.index();
 356         let words_per_row = num_words(self.columns);
 357         let start = row * words_per_row;
 358         (start, start + words_per_row)
 359     }
 360
 361     /// Sets the cell at `(row, column)` to true. Put another way, add
 362     /// `column` to the bitset for `row`.
 363     ///
 364     /// Returns true if this changed the matrix, and false otherwise.
 365     pub fn add(&mut self, row: R, column: R) -> bool {
 366         let (start, _) = self.range(row);
 367         let (word, mask) = word_mask(column);
 368         let vector = &mut self.vector[..];
 369         let v1 = vector[start + word];
 370         let v2 = v1 | mask;
 371         vector[start + word] = v2;
 372         v1 != v2
 373     }
 374
 375     /// Do the bits from `row` contain `column`? Put another way, is
 376     /// the matrix cell at `(row, column)` true?  Put yet another way,
 377     /// if the matrix represents (transitive) reachability, can
 378     /// `row` reach `column`?
 379     pub fn contains(&self, row: R, column: R) -> bool {
 380         let (start, _) = self.range(row);
 381         let (word, mask) = word_mask(column);
 382         (self.vector[start + word] & mask) != 0
 383     }
 384
 385     /// Returns those indices that are true in rows `a` and `b`.  This
 386     /// is an O(n) operation where `n` is the number of elements
 387     /// (somewhat independent from the actual size of the
 388     /// intersection, in particular).
 389     pub fn intersection(&self, a: R, b: R) -> Vec<C> {
 390         let (a_start, a_end) = self.range(a);
 391         let (b_start, b_end) = self.range(b);
 392         let mut result = Vec::with_capacity(self.columns);
 393         for (base, (i, j)) in (a_start..a_end).zip(b_start..b_end).enumerate() {
 394             let mut v = self.vector[i] & self.vector[j];
 395             for bit in 0..WORD_BITS {
 396                 if v == 0 {
 397                     break;
 398                 }
 399                 if v & 0x1 != 0 {
 400                     result.push(C::new(base * WORD_BITS + bit));
 401                 }
 402                 v >>= 1;
 403             }
 404         }
 405         result
 406     }
 407
 408     /// Add the bits from row `read` to the bits from row `write`,
 409     /// return true if anything changed.
 410     ///
 411     /// This is used when computing transitive reachability because if
 412     /// you have an edge `write -> read`, because in that case
 413     /// `write` can reach everything that `read` can (and
 414     /// potentially more).
 415     pub fn merge(&mut self, read: R, write: R) -> bool {
 416         let (read_start, read_end) = self.range(read);
 417         let (write_start, write_end) = self.range(write);
 418         let vector = &mut self.vector[..];
 419         let mut changed = false;
 420         for (read_index, write_index) in (read_start..read_end).zip(write_start..write_end) {
 421             let v1 = vector[write_index];
 422             let v2 = v1 | vector[read_index];
 423             vector[write_index] = v2;
 424             changed |= v1 != v2;
 425         }
 426         changed
 427     }
 428
 429     /// Iterates through all the columns set to true in a given row of
 430     /// the matrix.
 431     pub fn iter<'a>(&'a self, row: R) -> BitIter<'a, C> {
 432         let (start, end) = self.range(row);
 433         BitIter {
 434             cur: None,
 435             iter: self.vector[start..end].iter().enumerate(),
 436             marker: PhantomData,
 437         }
 438     }
 439 }
 440
 441 /// A moderately sparse bit matrix, in which rows are instantiated lazily.
 442 ///
 443 /// Initially, every row has no explicit representation. If any bit within a
 444 /// row is set, the entire row is instantiated as
 445 /// `Some(<full-column-width-BitArray>)`. Furthermore, any previously
 446 /// uninstantiated rows prior to it will be instantiated as `None`. Those prior
 447 /// rows may themselves become fully instantiated later on if any of their bits
 448 /// are set.
 449 #[derive(Clone, Debug)]
 450 pub struct SparseBitMatrix<R, C>
 451 where
 452     R: Idx,
 453     C: Idx,
 454 {
 455     num_columns: usize,
 456     rows: IndexVec<R, Option<BitArray<C>>>,
 457 }
 458
 459 impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
 460     /// Create a new empty sparse bit matrix with no rows or columns.
 461     pub fn new(num_columns: usize) -> Self {
 462         Self {
 463             num_columns,
 464             rows: IndexVec::new(),
 465         }
 466     }
 467
 468     fn ensure_row(&mut self, row: R) -> &mut BitArray<C> {
 469         // Instantiate any missing rows up to and including row `row` with an
 470         // empty BitArray.
 471         self.rows.ensure_contains_elem(row, || None);
 472
 473         // Then replace row `row` with a full BitArray if necessary.
 474         let num_columns = self.num_columns;
 475         self.rows[row].get_or_insert_with(|| BitArray::new(num_columns))
 476     }
 477
 478     /// Sets the cell at `(row, column)` to true. Put another way, insert
 479     /// `column` to the bitset for `row`.
 480     ///
 481     /// Returns true if this changed the matrix, and false otherwise.
 482     pub fn add(&mut self, row: R, column: C) -> bool {
 483         self.ensure_row(row).insert(column)
 484     }
 485
 486     /// Do the bits from `row` contain `column`? Put another way, is
 487     /// the matrix cell at `(row, column)` true?  Put yet another way,
 488     /// if the matrix represents (transitive) reachability, can
 489     /// `row` reach `column`?
 490     pub fn contains(&self, row: R, column: C) -> bool {
 491         self.row(row).map_or(false, |r| r.contains(column))
 492     }
 493
 494     /// Add the bits from row `read` to the bits from row `write`,
 495     /// return true if anything changed.
 496     ///
 497     /// This is used when computing transitive reachability because if
 498     /// you have an edge `write -> read`, because in that case
 499     /// `write` can reach everything that `read` can (and
 500     /// potentially more).
 501     pub fn merge(&mut self, read: R, write: R) -> bool {
 502         if read == write || self.row(read).is_none() {
 503             return false;
 504         }
 505
 506         self.ensure_row(write);
 507         if let (Some(bitvec_read), Some(bitvec_write)) = self.rows.pick2_mut(read, write) {
 508             bitvec_write.merge(bitvec_read)
 509         } else {
 510             unreachable!()
 511         }
 512     }
 513
 514     /// Merge a row, `from`, into the `into` row.
 515     pub fn merge_into(&mut self, into: R, from: &BitArray<C>) -> bool {
 516         self.ensure_row(into).merge(from)
 517     }
 518
 519     /// Add all bits to the given row.
 520     pub fn add_all(&mut self, row: R) {
 521         self.ensure_row(row).insert_all();
 522     }
 523
 524     pub fn rows(&self) -> impl Iterator<Item = R> {
 525         self.rows.indices()
 526     }
 527
 528     /// Iterates through all the columns set to true in a given row of
 529     /// the matrix.
 530     pub fn iter<'a>(&'a self, row: R) -> impl Iterator<Item = C> + 'a {
 531         self.row(row).into_iter().flat_map(|r| r.iter())
 532     }
 533
 534     pub fn row(&self, row: R) -> Option<&BitArray<C>> {
 535         if let Some(Some(row)) = self.rows.get(row) {
 536             Some(row)
 537         } else {
 538             None
 539         }
 540     }
 541 }
 542
 543 #[inline]
 544 fn num_words<C: Idx>(elements: C) -> usize {
 545     (elements.index() + WORD_BITS - 1) / WORD_BITS
 546 }
 547
 548 #[inline]
 549 fn word_mask<C: Idx>(index: C) -> (usize, Word) {
 550     let index = index.index();
 551     let word = index / WORD_BITS;
 552     let mask = 1 << (index % WORD_BITS);
 553     (word, mask)
 554 }
 555
 556 #[test]
 557 fn test_clear_above() {
 558     use std::cmp;
 559
 560     for i in 0..256 {
 561         let mut idx_buf: BitArray<usize> = BitArray::new_filled(128);
 562         idx_buf.clear_above(i);
 563
 564         let elems: Vec<usize> = idx_buf.iter().collect();
 565         let expected: Vec<usize> = (0..cmp::min(i, 128)).collect();
 566         assert_eq!(elems, expected);
 567     }
 568 }
 569
 570 #[test]
 571 fn test_set_up_to() {
 572     for i in 0..128 {
 573         for mut idx_buf in
 574             vec![BitArray::new_empty(128), BitArray::new_filled(128)]
 575             .into_iter()
 576         {
 577             idx_buf.set_up_to(i);
 578
 579             let elems: Vec<usize> = idx_buf.iter().collect();
 580             let expected: Vec<usize> = (0..i).collect();
 581             assert_eq!(elems, expected);
 582         }
 583     }
 584 }
 585
 586 #[test]
 587 fn test_new_filled() {
 588     for i in 0..128 {
 589         let idx_buf = BitArray::new_filled(i);
 590         let elems: Vec<usize> = idx_buf.iter().collect();
 591         let expected: Vec<usize> = (0..i).collect();
 592         assert_eq!(elems, expected);
 593     }
 594 }
 595
 596 #[test]
 597 fn bitvec_iter_works() {
 598     let mut bitvec: BitArray<usize> = BitArray::new(100);
 599     bitvec.insert(1);
 600     bitvec.insert(10);
 601     bitvec.insert(19);
 602     bitvec.insert(62);
 603     bitvec.insert(63);
 604     bitvec.insert(64);
 605     bitvec.insert(65);
 606     bitvec.insert(66);
 607     bitvec.insert(99);
 608     assert_eq!(
 609         bitvec.iter().collect::<Vec<_>>(),
 610         [1, 10, 19, 62, 63, 64, 65, 66, 99]
 611     );
 612 }
 613
 614 #[test]
 615 fn bitvec_iter_works_2() {
 616     let mut bitvec: BitArray<usize> = BitArray::new(319);
 617     bitvec.insert(0);
 618     bitvec.insert(127);
 619     bitvec.insert(191);
 620     bitvec.insert(255);
 621     bitvec.insert(319);
 622     assert_eq!(bitvec.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
 623 }
 624
 625 #[test]
 626 fn union_two_vecs() {
 627     let mut vec1: BitArray<usize> = BitArray::new(65);
 628     let mut vec2: BitArray<usize> = BitArray::new(65);
 629     assert!(vec1.insert(3));
 630     assert!(!vec1.insert(3));
 631     assert!(vec2.insert(5));
 632     assert!(vec2.insert(64));
 633     assert!(vec1.merge(&vec2));
 634     assert!(!vec1.merge(&vec2));
 635     assert!(vec1.contains(3));
 636     assert!(!vec1.contains(4));
 637     assert!(vec1.contains(5));
 638     assert!(!vec1.contains(63));
 639     assert!(vec1.contains(64));
 640 }
 641
 642 #[test]
 643 fn grow() {
 644     let mut vec1: BitVector<usize> = BitVector::with_capacity(65);
 645     for index in 0..65 {
 646         assert!(vec1.insert(index));
 647         assert!(!vec1.insert(index));
 648     }
 649     vec1.grow(128);
 650
 651     // Check if the bits set before growing are still set
 652     for index in 0..65 {
 653         assert!(vec1.contains(index));
 654     }
 655
 656     // Check if the new bits are all un-set
 657     for index in 65..128 {
 658         assert!(!vec1.contains(index));
 659     }
 660
 661     // Check that we can set all new bits without running out of bounds
 662     for index in 65..128 {
 663         assert!(vec1.insert(index));
 664         assert!(!vec1.insert(index));
 665     }
 666 }
 667
 668 #[test]
 669 fn matrix_intersection() {
 670     let mut vec1: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
 671
 672     // (*) Elements reachable from both 2 and 65.
 673
 674     vec1.add(2, 3);
 675     vec1.add(2, 6);
 676     vec1.add(2, 10); // (*)
 677     vec1.add(2, 64); // (*)
 678     vec1.add(2, 65);
 679     vec1.add(2, 130);
 680     vec1.add(2, 160); // (*)
 681
 682     vec1.add(64, 133);
 683
 684     vec1.add(65, 2);
 685     vec1.add(65, 8);
 686     vec1.add(65, 10); // (*)
 687     vec1.add(65, 64); // (*)
 688     vec1.add(65, 68);
 689     vec1.add(65, 133);
 690     vec1.add(65, 160); // (*)
 691
 692     let intersection = vec1.intersection(2, 64);
 693     assert!(intersection.is_empty());
 694
 695     let intersection = vec1.intersection(2, 65);
 696     assert_eq!(intersection, &[10, 64, 160]);
 697 }
 698
 699 #[test]
 700 fn matrix_iter() {
 701     let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
 702     matrix.add(3, 22);
 703     matrix.add(3, 75);
 704     matrix.add(2, 99);
 705     matrix.add(4, 0);
 706     matrix.merge(3, 5);
 707
 708     let expected = [99];
 709     let mut iter = expected.iter();
 710     for i in matrix.iter(2) {
 711         let j = *iter.next().unwrap();
 712         assert_eq!(i, j);
 713     }
 714     assert!(iter.next().is_none());
 715
 716     let expected = [22, 75];
 717     let mut iter = expected.iter();
 718     for i in matrix.iter(3) {
 719         let j = *iter.next().unwrap();
 720         assert_eq!(i, j);
 721     }
 722     assert!(iter.next().is_none());
 723
 724     let expected = [0];
 725     let mut iter = expected.iter();
 726     for i in matrix.iter(4) {
 727         let j = *iter.next().unwrap();
 728         assert_eq!(i, j);
 729     }
 730     assert!(iter.next().is_none());
 731
 732     let expected = [22, 75];
 733     let mut iter = expected.iter();
 734     for i in matrix.iter(5) {
 735         let j = *iter.next().unwrap();
 736         assert_eq!(i, j);
 737     }
 738     assert!(iter.next().is_none());
 739 }
 740
 741 #[test]
 742 fn sparse_matrix_iter() {
 743     let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
 744     matrix.add(3, 22);
 745     matrix.add(3, 75);
 746     matrix.add(2, 99);
 747     matrix.add(4, 0);
 748     matrix.merge(3, 5);
 749
 750     let expected = [99];
 751     let mut iter = expected.iter();
 752     for i in matrix.iter(2) {
 753         let j = *iter.next().unwrap();
 754         assert_eq!(i, j);
 755     }
 756     assert!(iter.next().is_none());
 757
 758     let expected = [22, 75];
 759     let mut iter = expected.iter();
 760     for i in matrix.iter(3) {
 761         let j = *iter.next().unwrap();
 762         assert_eq!(i, j);
 763     }
 764     assert!(iter.next().is_none());
 765
 766     let expected = [0];
 767     let mut iter = expected.iter();
 768     for i in matrix.iter(4) {
 769         let j = *iter.next().unwrap();
 770         assert_eq!(i, j);
 771     }
 772     assert!(iter.next().is_none());
 773
 774     let expected = [22, 75];
 775     let mut iter = expected.iter();
 776     for i in matrix.iter(5) {
 777         let j = *iter.next().unwrap();
 778         assert_eq!(i, j);
 779     }
 780     assert!(iter.next().is_none());
 781 }