1 // Copyright 2012-2014 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.
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.
11 // FIXME(Gankro): BitVec and BitSet are very tightly coupled. Ideally (for
12 // maintenance), they should be in separate files/modules, with BitSet only
13 // using BitVec's public API. This will be hard for performance though, because
14 // `BitVec` will not want to leak its internal representation while its internal
15 // representation as `u32`s must be assumed for best performance.
17 // FIXME(tbu-): `BitVec`'s methods shouldn't be `union`, `intersection`, but
18 // rather `or` and `and`.
20 // (1) Be careful, most things can overflow here because the amount of bits in
21 // memory can overflow `usize`.
22 // (2) Make sure that the underlying vector has no excess length:
23 // E. g. `nbits == 16`, `storage.len() == 2` would be excess length,
24 // because the last word isn't used at all. This is important because some
25 // methods rely on it (for *CORRECTNESS*).
26 // (3) Make sure that the unused bits in the last word are zeroed out, again
27 // other methods rely on it for *CORRECTNESS*.
28 // (4) `BitSet` is tightly coupled with `BitVec`, so any changes you make in
29 // `BitVec` will need to be reflected in `BitSet`.
31 //! Collections implemented with bit vectors.
35 //! This is a simple example of the [Sieve of Eratosthenes][sieve]
36 //! which calculates prime numbers up to a given limit.
38 //! [sieve]: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
41 //! # #![feature(bitset, bitvec, range_inclusive, step_by)]
42 //! use std::collections::{BitSet, BitVec};
45 //! let max_prime = 10000;
47 //! // Store the primes as a BitSet
49 //! // Assume all numbers are prime to begin, and then we
50 //! // cross off non-primes progressively
51 //! let mut bv = BitVec::from_elem(max_prime, true);
53 //! // Neither 0 nor 1 are prime
57 //! for i in iter::range_inclusive(2, (max_prime as f64).sqrt() as usize) {
58 //! // if i is a prime
60 //! // Mark all multiples of i as non-prime (any multiples below i * i
61 //! // will have been marked as non-prime previously)
62 //! for j in (i * i..max_prime).step_by(i) { bv.set(j, false) }
65 //! BitSet::from_bit_vec(bv)
68 //! // Simple primality tests below our max bound
69 //! let print_primes = 20;
70 //! print!("The primes below {} are: ", print_primes);
71 //! for x in 0..print_primes {
72 //! if primes.contains(&x) {
78 //! // We can manipulate the internal BitVec
79 //! let num_primes = primes.get_ref().iter().filter(|x| *x).count();
80 //! println!("There are {} primes below {}", num_primes, max_prime);
85 use core
::cmp
::Ordering
;
90 use core
::iter
::RandomAccessIterator
;
91 use core
::iter
::{Chain, Enumerate, Repeat, Skip, Take, repeat, Cloned}
;
92 use core
::iter
::{self, FromIterator}
;
96 use core
::{u8, u32, usize}
;
97 use bit_set
; //so meta
101 type Blocks
<'a
> = Cloned
<slice
::Iter
<'a
, u32>>;
102 type MutBlocks
<'a
> = slice
::IterMut
<'a
, u32>;
103 type MatchWords
<'a
> = Chain
<Enumerate
<Blocks
<'a
>>, Skip
<Take
<Enumerate
<Repeat
<u32>>>>>;
105 fn reverse_bits(byte
: u8) -> u8 {
107 for i
in 0..u8::BITS
{
108 result
|= ((byte
>> i
) & 1) << (u8::BITS
- 1 - i
);
113 // Take two BitVec's, and return iterators of their words, where the shorter one
114 // has been padded with 0's
115 fn match_words
<'a
,'b
>(a
: &'a BitVec
, b
: &'b BitVec
) -> (MatchWords
<'a
>, MatchWords
<'b
>) {
116 let a_len
= a
.storage
.len();
117 let b_len
= b
.storage
.len();
119 // have to uselessly pretend to pad the longer one for type matching
121 (a
.blocks().enumerate().chain(iter
::repeat(0).enumerate().take(b_len
).skip(a_len
)),
122 b
.blocks().enumerate().chain(iter
::repeat(0).enumerate().take(0).skip(0)))
124 (a
.blocks().enumerate().chain(iter
::repeat(0).enumerate().take(0).skip(0)),
125 b
.blocks().enumerate().chain(iter
::repeat(0).enumerate().take(a_len
).skip(b_len
)))
129 const TRUE
: &'
static bool
= &true;
130 const FALSE
: &'
static bool
= &false;
132 /// The bitvector type.
137 /// # #![feature(bitvec)]
138 /// use std::collections::BitVec;
140 /// let mut bv = BitVec::from_elem(10, false);
142 /// // insert all primes less than 10
147 /// println!("{:?}", bv);
148 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
150 /// // flip all values in bitvector, producing non-primes less than 10
152 /// println!("{:?}", bv);
153 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
155 /// // reset bitvector to empty
157 /// println!("{:?}", bv);
158 /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count());
160 #[unstable(feature = "bitvec", reason = "RFC 509")]
162 /// Internal representation of the bit vector
164 /// The number of valid bits in the internal representation
168 // FIXME(Gankro): NopeNopeNopeNopeNope (wait for IndexGet to be a thing)
169 impl Index
<usize> for BitVec
{
173 fn index(&self, i
: usize) -> &bool
{
174 if self.get(i
).expect("index out of bounds") {
182 /// Computes how many blocks are needed to store that many bits
183 fn blocks_for_bits(bits
: usize) -> usize {
184 // If we want 17 bits, dividing by 32 will produce 0. So we add 1 to make
185 // sure we reserve enough. But if we want exactly a multiple of 32, this
186 // will actually allocate one too many. So we need to check if that's the
187 // case. We can do that by computing if bitwise AND by `32 - 1` is 0. But
188 // LLVM should be able to optimize the semantically superior modulo operator
189 // on a power of two to this.
191 // Note that we can technically avoid this branch with the expression
192 // `(nbits + u32::BITS - 1) / 32::BITS`, but if nbits is almost usize::MAX
193 // this will overflow.
194 if bits
% u32::BITS
== 0 {
201 /// Computes the bitmask for the final word of the vector
202 fn mask_for_bits(bits
: usize) -> u32 {
203 // Note especially that a perfect multiple of u32::BITS should mask all 1s.
204 !0 >> (u32::BITS
- bits
% u32::BITS
) % u32::BITS
207 #[unstable(feature = "bitvec", reason = "RFC 509")]
209 /// Applies the given operation to the blocks of self and other, and sets
210 /// self to be the result. This relies on the caller not to corrupt the
213 fn process
<F
>(&mut self, other
: &BitVec
, mut op
: F
) -> bool
where F
: FnMut(u32, u32) -> u32 {
214 assert_eq
!(self.len(), other
.len());
215 // This could theoretically be a `debug_assert!`.
216 assert_eq
!(self.storage
.len(), other
.storage
.len());
217 let mut changed_bits
= 0;
218 for (a
, b
) in self.blocks_mut().zip(other
.blocks()) {
220 changed_bits
|= *a ^ w
;
226 /// Iterator over mutable refs to the underlying blocks of data.
227 fn blocks_mut(&mut self) -> MutBlocks
{
229 self.storage
.iter_mut()
232 /// Iterator over the underlying blocks of data
233 fn blocks(&self) -> Blocks
{
235 self.storage
.iter().cloned()
238 /// An operation might screw up the unused bits in the last block of the
239 /// `BitVec`. As per (3), it's assumed to be all 0s. This method fixes it up.
240 fn fix_last_block(&mut self) {
241 let extra_bits
= self.len() % u32::BITS
;
243 let mask
= (1 << extra_bits
) - 1;
244 let storage_len
= self.storage
.len();
245 self.storage
[storage_len
- 1] &= mask
;
249 /// Creates an empty `BitVec`.
254 /// # #![feature(bitvec)]
255 /// use std::collections::BitVec;
256 /// let mut bv = BitVec::new();
258 #[stable(feature = "rust1", since = "1.0.0")]
259 pub fn new() -> BitVec
{
260 BitVec { storage: Vec::new(), nbits: 0 }
263 /// Creates a `BitVec` that holds `nbits` elements, setting each element
269 /// # #![feature(bitvec)]
270 /// use std::collections::BitVec;
272 /// let bv = BitVec::from_elem(10, false);
273 /// assert_eq!(bv.len(), 10);
275 /// assert_eq!(x, false);
278 pub fn from_elem(nbits
: usize, bit
: bool
) -> BitVec
{
279 let nblocks
= blocks_for_bits(nbits
);
280 let mut bit_vec
= BitVec
{
281 storage
: repeat(if bit { !0 }
else { 0 }
).take(nblocks
).collect(),
284 bit_vec
.fix_last_block();
288 /// Constructs a new, empty `BitVec` with the specified capacity.
290 /// The bitvector will be able to hold at least `capacity` bits without
291 /// reallocating. If `capacity` is 0, it will not allocate.
293 /// It is important to note that this function does not specify the
294 /// *length* of the returned bitvector, but only the *capacity*.
295 #[stable(feature = "rust1", since = "1.0.0")]
296 pub fn with_capacity(nbits
: usize) -> BitVec
{
298 storage
: Vec
::with_capacity(blocks_for_bits(nbits
)),
303 /// Transforms a byte-vector into a `BitVec`. Each byte becomes eight bits,
304 /// with the most significant bits of each byte coming first. Each
305 /// bit becomes `true` if equal to 1 or `false` if equal to 0.
310 /// # #![feature(bitvec)]
311 /// use std::collections::BitVec;
313 /// let bv = BitVec::from_bytes(&[0b10100000, 0b00010010]);
314 /// assert!(bv.eq_vec(&[true, false, true, false,
315 /// false, false, false, false,
316 /// false, false, false, true,
317 /// false, false, true, false]));
319 pub fn from_bytes(bytes
: &[u8]) -> BitVec
{
320 let len
= bytes
.len().checked_mul(u8::BITS
).expect("capacity overflow");
321 let mut bit_vec
= BitVec
::with_capacity(len
);
322 let complete_words
= bytes
.len() / 4;
323 let extra_bytes
= bytes
.len() % 4;
327 for i
in 0..complete_words
{
328 bit_vec
.storage
.push(
329 ((reverse_bits(bytes
[i
* 4 + 0]) as u32) << 0) |
330 ((reverse_bits(bytes
[i
* 4 + 1]) as u32) << 8) |
331 ((reverse_bits(bytes
[i
* 4 + 2]) as u32) << 16) |
332 ((reverse_bits(bytes
[i
* 4 + 3]) as u32) << 24)
337 let mut last_word
= 0;
338 for (i
, &byte
) in bytes
[complete_words
*4..].iter().enumerate() {
339 last_word
|= (reverse_bits(byte
) as u32) << (i
* 8);
341 bit_vec
.storage
.push(last_word
);
347 /// Creates a `BitVec` of the specified length where the value at each index
353 /// # #![feature(bitvec)]
354 /// use std::collections::BitVec;
356 /// let bv = BitVec::from_fn(5, |i| { i % 2 == 0 });
357 /// assert!(bv.eq_vec(&[true, false, true, false, true]));
359 pub fn from_fn
<F
>(len
: usize, mut f
: F
) -> BitVec
where F
: FnMut(usize) -> bool
{
360 let mut bit_vec
= BitVec
::from_elem(len
, false);
362 bit_vec
.set(i
, f(i
));
367 /// Retrieves the value at index `i`, or `None` if the index is out of bounds.
372 /// # #![feature(bitvec)]
373 /// use std::collections::BitVec;
375 /// let bv = BitVec::from_bytes(&[0b01100000]);
376 /// assert_eq!(bv.get(0), Some(false));
377 /// assert_eq!(bv.get(1), Some(true));
378 /// assert_eq!(bv.get(100), None);
380 /// // Can also use array indexing
381 /// assert_eq!(bv[1], true);
384 #[stable(feature = "rust1", since = "1.0.0")]
385 pub fn get(&self, i
: usize) -> Option
<bool
> {
389 let w
= i
/ u32::BITS
;
390 let b
= i
% u32::BITS
;
391 self.storage
.get(w
).map(|&block
|
392 (block
& (1 << b
)) != 0
396 /// Sets the value of a bit at an index `i`.
400 /// Panics if `i` is out of bounds.
405 /// # #![feature(bitvec)]
406 /// use std::collections::BitVec;
408 /// let mut bv = BitVec::from_elem(5, false);
410 /// assert_eq!(bv[3], true);
413 pub fn set(&mut self, i
: usize, x
: bool
) {
414 assert
!(i
< self.nbits
);
415 let w
= i
/ u32::BITS
;
416 let b
= i
% u32::BITS
;
418 let val
= if x { self.storage[w] | flag }
419 else { self.storage[w] & !flag }
;
420 self.storage
[w
] = val
;
423 /// Sets all bits to 1.
428 /// # #![feature(bitvec)]
429 /// use std::collections::BitVec;
431 /// let before = 0b01100000;
432 /// let after = 0b11111111;
434 /// let mut bv = BitVec::from_bytes(&[before]);
436 /// assert_eq!(bv, BitVec::from_bytes(&[after]));
439 pub fn set_all(&mut self) {
440 for w
in &mut self.storage { *w = !0; }
441 self.fix_last_block();
449 /// # #![feature(bitvec)]
450 /// use std::collections::BitVec;
452 /// let before = 0b01100000;
453 /// let after = 0b10011111;
455 /// let mut bv = BitVec::from_bytes(&[before]);
457 /// assert_eq!(bv, BitVec::from_bytes(&[after]));
460 pub fn negate(&mut self) {
461 for w
in &mut self.storage { *w = !*w; }
462 self.fix_last_block();
465 /// Calculates the union of two bitvectors. This acts like the bitwise `or`
468 /// Sets `self` to the union of `self` and `other`. Both bitvectors must be
469 /// the same length. Returns `true` if `self` changed.
473 /// Panics if the bitvectors are of different lengths.
478 /// # #![feature(bitvec)]
479 /// use std::collections::BitVec;
481 /// let a = 0b01100100;
482 /// let b = 0b01011010;
483 /// let res = 0b01111110;
485 /// let mut a = BitVec::from_bytes(&[a]);
486 /// let b = BitVec::from_bytes(&[b]);
488 /// assert!(a.union(&b));
489 /// assert_eq!(a, BitVec::from_bytes(&[res]));
492 pub fn union(&mut self, other
: &BitVec
) -> bool
{
493 self.process(other
, |w1
, w2
| w1
| w2
)
496 /// Calculates the intersection of two bitvectors. This acts like the
497 /// bitwise `and` function.
499 /// Sets `self` to the intersection of `self` and `other`. Both bitvectors
500 /// must be the same length. Returns `true` if `self` changed.
504 /// Panics if the bitvectors are of different lengths.
509 /// # #![feature(bitvec)]
510 /// use std::collections::BitVec;
512 /// let a = 0b01100100;
513 /// let b = 0b01011010;
514 /// let res = 0b01000000;
516 /// let mut a = BitVec::from_bytes(&[a]);
517 /// let b = BitVec::from_bytes(&[b]);
519 /// assert!(a.intersect(&b));
520 /// assert_eq!(a, BitVec::from_bytes(&[res]));
523 pub fn intersect(&mut self, other
: &BitVec
) -> bool
{
524 self.process(other
, |w1
, w2
| w1
& w2
)
527 /// Calculates the difference between two bitvectors.
529 /// Sets each element of `self` to the value of that element minus the
530 /// element of `other` at the same index. Both bitvectors must be the same
531 /// length. Returns `true` if `self` changed.
535 /// Panics if the bitvectors are of different length.
540 /// # #![feature(bitvec)]
541 /// use std::collections::BitVec;
543 /// let a = 0b01100100;
544 /// let b = 0b01011010;
545 /// let a_b = 0b00100100; // a - b
546 /// let b_a = 0b00011010; // b - a
548 /// let mut bva = BitVec::from_bytes(&[a]);
549 /// let bvb = BitVec::from_bytes(&[b]);
551 /// assert!(bva.difference(&bvb));
552 /// assert_eq!(bva, BitVec::from_bytes(&[a_b]));
554 /// let bva = BitVec::from_bytes(&[a]);
555 /// let mut bvb = BitVec::from_bytes(&[b]);
557 /// assert!(bvb.difference(&bva));
558 /// assert_eq!(bvb, BitVec::from_bytes(&[b_a]));
561 pub fn difference(&mut self, other
: &BitVec
) -> bool
{
562 self.process(other
, |w1
, w2
| w1
& !w2
)
565 /// Returns `true` if all bits are 1.
570 /// # #![feature(bitvec)]
571 /// use std::collections::BitVec;
573 /// let mut bv = BitVec::from_elem(5, true);
574 /// assert_eq!(bv.all(), true);
576 /// bv.set(1, false);
577 /// assert_eq!(bv.all(), false);
579 pub fn all(&self) -> bool
{
580 let mut last_word
= !0;
581 // Check that every block but the last is all-ones...
582 self.blocks().all(|elem
| {
586 // and then check the last one has enough ones
587 }) && (last_word
== mask_for_bits(self.nbits
))
590 /// Returns an iterator over the elements of the vector in order.
595 /// # #![feature(bitvec)]
596 /// use std::collections::BitVec;
598 /// let bv = BitVec::from_bytes(&[0b01110100, 0b10010010]);
599 /// assert_eq!(bv.iter().filter(|x| *x).count(), 7);
602 #[stable(feature = "rust1", since = "1.0.0")]
603 pub fn iter(&self) -> Iter
{
604 Iter { bit_vec: self, next_idx: 0, end_idx: self.nbits }
607 /// Moves all bits from `other` into `Self`, leaving `other` empty.
612 /// # #![feature(bitvec, append)]
613 /// use std::collections::BitVec;
615 /// let mut a = BitVec::from_bytes(&[0b10000000]);
616 /// let mut b = BitVec::from_bytes(&[0b01100001]);
618 /// a.append(&mut b);
620 /// assert_eq!(a.len(), 16);
621 /// assert_eq!(b.len(), 0);
622 /// assert!(a.eq_vec(&[true, false, false, false, false, false, false, false,
623 /// false, true, true, false, false, false, false, true]));
625 #[unstable(feature = "append",
626 reason
= "recently added as part of collections reform 2")]
627 pub fn append(&mut self, other
: &mut Self) {
628 let b
= self.len() % u32::BITS
;
630 self.nbits
+= other
.len();
634 self.storage
.append(&mut other
.storage
);
636 self.storage
.reserve(other
.storage
.len());
638 for block
in other
.storage
.drain(..) {
639 *(self.storage
.last_mut().unwrap()) |= block
<< b
;
640 self.storage
.push(block
>> (u32::BITS
- b
));
645 /// Splits the `BitVec` into two at the given bit,
646 /// retaining the first half in-place and returning the second one.
650 /// Panics if `at` is out of bounds.
655 /// # #![feature(bitvec, split_off)]
656 /// use std::collections::BitVec;
657 /// let mut a = BitVec::new();
663 /// let b = a.split_off(2);
665 /// assert_eq!(a.len(), 2);
666 /// assert_eq!(b.len(), 2);
667 /// assert!(a.eq_vec(&[true, false]));
668 /// assert!(b.eq_vec(&[false, true]));
670 #[unstable(feature = "split_off",
671 reason
= "recently added as part of collections reform 2")]
672 pub fn split_off(&mut self, at
: usize) -> Self {
673 assert
!(at
<= self.len(), "`at` out of bounds");
675 let mut other
= BitVec
::new();
678 swap(self, &mut other
);
680 } else if at
== self.len() {
684 let w
= at
/ u32::BITS
;
685 let b
= at
% u32::BITS
;
686 other
.nbits
= self.nbits
- at
;
689 // Split at block boundary
690 other
.storage
= self.storage
.split_off(w
);
692 other
.storage
.reserve(self.storage
.len() - w
);
695 let mut iter
= self.storage
[w
..].iter();
696 let mut last
= *iter
.next().unwrap();
698 other
.storage
.push((last
>> b
) | (cur
<< (u32::BITS
- b
)));
701 other
.storage
.push(last
>> b
);
704 self.storage
.truncate(w
+1);
705 self.fix_last_block();
711 /// Returns `true` if all bits are 0.
716 /// # #![feature(bitvec)]
717 /// use std::collections::BitVec;
719 /// let mut bv = BitVec::from_elem(10, false);
720 /// assert_eq!(bv.none(), true);
723 /// assert_eq!(bv.none(), false);
725 pub fn none(&self) -> bool
{
726 self.blocks().all(|w
| w
== 0)
729 /// Returns `true` if any bit is 1.
734 /// # #![feature(bitvec)]
735 /// use std::collections::BitVec;
737 /// let mut bv = BitVec::from_elem(10, false);
738 /// assert_eq!(bv.any(), false);
741 /// assert_eq!(bv.any(), true);
744 pub fn any(&self) -> bool
{
748 /// Organises the bits into bytes, such that the first bit in the
749 /// `BitVec` becomes the high-order bit of the first byte. If the
750 /// size of the `BitVec` is not a multiple of eight then trailing bits
751 /// will be filled-in with `false`.
756 /// # #![feature(bitvec)]
757 /// use std::collections::BitVec;
759 /// let mut bv = BitVec::from_elem(3, true);
760 /// bv.set(1, false);
762 /// assert_eq!(bv.to_bytes(), [0b10100000]);
764 /// let mut bv = BitVec::from_elem(9, false);
768 /// assert_eq!(bv.to_bytes(), [0b00100000, 0b10000000]);
770 pub fn to_bytes(&self) -> Vec
<u8> {
771 fn bit(bit_vec
: &BitVec
, byte
: usize, bit
: usize) -> u8 {
772 let offset
= byte
* 8 + bit
;
773 if offset
>= bit_vec
.nbits
{
776 (bit_vec
[offset
] as u8) << (7 - bit
)
780 let len
= self.nbits
/8 +
781 if self.nbits
% 8 == 0 { 0 }
else { 1 }
;
794 /// Compares a `BitVec` to a slice of `bool`s.
795 /// Both the `BitVec` and slice must have the same length.
799 /// Panics if the `BitVec` and slice are of different length.
804 /// # #![feature(bitvec)]
805 /// use std::collections::BitVec;
807 /// let bv = BitVec::from_bytes(&[0b10100000]);
809 /// assert!(bv.eq_vec(&[true, false, true, false,
810 /// false, false, false, false]));
812 pub fn eq_vec(&self, v
: &[bool
]) -> bool
{
813 assert_eq
!(self.nbits
, v
.len());
814 iter
::order
::eq(self.iter(), v
.iter().cloned())
817 /// Shortens a `BitVec`, dropping excess elements.
819 /// If `len` is greater than the vector's current length, this has no
825 /// # #![feature(bitvec)]
826 /// use std::collections::BitVec;
828 /// let mut bv = BitVec::from_bytes(&[0b01001011]);
830 /// assert!(bv.eq_vec(&[false, true]));
832 #[stable(feature = "rust1", since = "1.0.0")]
833 pub fn truncate(&mut self, len
: usize) {
834 if len
< self.len() {
837 self.storage
.truncate(blocks_for_bits(len
));
838 self.fix_last_block();
842 /// Reserves capacity for at least `additional` more bits to be inserted in the given
843 /// `BitVec`. The collection may reserve more space to avoid frequent reallocations.
847 /// Panics if the new capacity overflows `usize`.
852 /// # #![feature(bitvec)]
853 /// use std::collections::BitVec;
855 /// let mut bv = BitVec::from_elem(3, false);
857 /// assert_eq!(bv.len(), 3);
858 /// assert!(bv.capacity() >= 13);
860 #[stable(feature = "rust1", since = "1.0.0")]
861 pub fn reserve(&mut self, additional
: usize) {
862 let desired_cap
= self.len().checked_add(additional
).expect("capacity overflow");
863 let storage_len
= self.storage
.len();
864 if desired_cap
> self.capacity() {
865 self.storage
.reserve(blocks_for_bits(desired_cap
) - storage_len
);
869 /// Reserves the minimum capacity for exactly `additional` more bits to be inserted in the
870 /// given `BitVec`. Does nothing if the capacity is already sufficient.
872 /// Note that the allocator may give the collection more space than it requests. Therefore
873 /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
874 /// insertions are expected.
878 /// Panics if the new capacity overflows `usize`.
883 /// # #![feature(bitvec)]
884 /// use std::collections::BitVec;
886 /// let mut bv = BitVec::from_elem(3, false);
888 /// assert_eq!(bv.len(), 3);
889 /// assert!(bv.capacity() >= 13);
891 #[stable(feature = "rust1", since = "1.0.0")]
892 pub fn reserve_exact(&mut self, additional
: usize) {
893 let desired_cap
= self.len().checked_add(additional
).expect("capacity overflow");
894 let storage_len
= self.storage
.len();
895 if desired_cap
> self.capacity() {
896 self.storage
.reserve_exact(blocks_for_bits(desired_cap
) - storage_len
);
900 /// Returns the capacity in bits for this bit vector. Inserting any
901 /// element less than this amount will not trigger a resizing.
906 /// # #![feature(bitvec)]
907 /// use std::collections::BitVec;
909 /// let mut bv = BitVec::new();
911 /// assert!(bv.capacity() >= 10);
914 #[stable(feature = "rust1", since = "1.0.0")]
915 pub fn capacity(&self) -> usize {
916 self.storage
.capacity().checked_mul(u32::BITS
).unwrap_or(usize::MAX
)
919 /// Grows the `BitVec` in-place, adding `n` copies of `value` to the `BitVec`.
923 /// Panics if the new len overflows a `usize`.
928 /// # #![feature(bitvec)]
929 /// use std::collections::BitVec;
931 /// let mut bv = BitVec::from_bytes(&[0b01001011]);
932 /// bv.grow(2, true);
933 /// assert_eq!(bv.len(), 10);
934 /// assert_eq!(bv.to_bytes(), [0b01001011, 0b11000000]);
936 pub fn grow(&mut self, n
: usize, value
: bool
) {
937 // Note: we just bulk set all the bits in the last word in this fn in multiple places
938 // which is technically wrong if not all of these bits are to be used. However, at the end
939 // of this fn we call `fix_last_block` at the end of this fn, which should fix this.
941 let new_nbits
= self.nbits
.checked_add(n
).expect("capacity overflow");
942 let new_nblocks
= blocks_for_bits(new_nbits
);
943 let full_value
= if value { !0 }
else { 0 }
;
945 // Correct the old tail word, setting or clearing formerly unused bits
946 let num_cur_blocks
= blocks_for_bits(self.nbits
);
947 if self.nbits
% u32::BITS
> 0 {
948 let mask
= mask_for_bits(self.nbits
);
950 self.storage
[num_cur_blocks
- 1] |= !mask
;
952 // Extra bits are already zero by invariant.
956 // Fill in words after the old tail word
957 let stop_idx
= cmp
::min(self.storage
.len(), new_nblocks
);
958 for idx
in num_cur_blocks
..stop_idx
{
959 self.storage
[idx
] = full_value
;
962 // Allocate new words, if needed
963 if new_nblocks
> self.storage
.len() {
964 let to_add
= new_nblocks
- self.storage
.len();
965 self.storage
.extend(repeat(full_value
).take(to_add
));
968 // Adjust internal bit count
969 self.nbits
= new_nbits
;
971 self.fix_last_block();
974 /// Removes the last bit from the BitVec, and returns it. Returns None if the BitVec is empty.
979 /// # #![feature(bitvec)]
980 /// use std::collections::BitVec;
982 /// let mut bv = BitVec::from_bytes(&[0b01001001]);
983 /// assert_eq!(bv.pop(), Some(true));
984 /// assert_eq!(bv.pop(), Some(false));
985 /// assert_eq!(bv.len(), 6);
987 #[stable(feature = "rust1", since = "1.0.0")]
988 pub fn pop(&mut self) -> Option
<bool
> {
992 let i
= self.nbits
- 1;
997 if self.nbits
% u32::BITS
== 0 {
1005 /// Pushes a `bool` onto the end.
1010 /// # #![feature(bitvec)]
1011 /// use std::collections::BitVec;
1013 /// let mut bv = BitVec::new();
1016 /// assert!(bv.eq_vec(&[true, false]));
1018 #[stable(feature = "rust1", since = "1.0.0")]
1019 pub fn push(&mut self, elem
: bool
) {
1020 if self.nbits
% u32::BITS
== 0 {
1021 self.storage
.push(0);
1023 let insert_pos
= self.nbits
;
1024 self.nbits
= self.nbits
.checked_add(1).expect("Capacity overflow");
1025 self.set(insert_pos
, elem
);
1028 /// Returns the total number of bits in this vector
1030 #[stable(feature = "rust1", since = "1.0.0")]
1031 pub fn len(&self) -> usize { self.nbits }
1033 /// Returns true if there are no bits in this vector
1035 #[stable(feature = "rust1", since = "1.0.0")]
1036 pub fn is_empty(&self) -> bool { self.len() == 0 }
1038 /// Clears all bits in this vector.
1040 #[stable(feature = "rust1", since = "1.0.0")]
1041 pub fn clear(&mut self) {
1042 for w
in &mut self.storage { *w = 0; }
1046 #[stable(feature = "rust1", since = "1.0.0")]
1047 impl Default
for BitVec
{
1049 fn default() -> BitVec { BitVec::new() }
1052 #[stable(feature = "rust1", since = "1.0.0")]
1053 impl FromIterator
<bool
> for BitVec
{
1054 fn from_iter
<I
: IntoIterator
<Item
=bool
>>(iter
: I
) -> BitVec
{
1055 let mut ret
= BitVec
::new();
1061 #[stable(feature = "rust1", since = "1.0.0")]
1062 impl Extend
<bool
> for BitVec
{
1064 fn extend
<I
: IntoIterator
<Item
=bool
>>(&mut self, iterable
: I
) {
1065 let iterator
= iterable
.into_iter();
1066 let (min
, _
) = iterator
.size_hint();
1068 for element
in iterator
{
1074 #[stable(feature = "extend_ref", since = "1.2.0")]
1075 impl<'a
> Extend
<&'a bool
> for BitVec
{
1076 fn extend
<I
: IntoIterator
<Item
=&'a bool
>>(&mut self, iter
: I
) {
1077 self.extend(iter
.into_iter().cloned());
1081 #[stable(feature = "rust1", since = "1.0.0")]
1082 impl Clone
for BitVec
{
1084 fn clone(&self) -> BitVec
{
1085 BitVec { storage: self.storage.clone(), nbits: self.nbits }
1089 fn clone_from(&mut self, source
: &BitVec
) {
1090 self.nbits
= source
.nbits
;
1091 self.storage
.clone_from(&source
.storage
);
1095 #[stable(feature = "rust1", since = "1.0.0")]
1096 impl PartialOrd
for BitVec
{
1098 fn partial_cmp(&self, other
: &BitVec
) -> Option
<Ordering
> {
1099 iter
::order
::partial_cmp(self.iter(), other
.iter())
1103 #[stable(feature = "rust1", since = "1.0.0")]
1104 impl Ord
for BitVec
{
1106 fn cmp(&self, other
: &BitVec
) -> Ordering
{
1107 iter
::order
::cmp(self.iter(), other
.iter())
1111 #[stable(feature = "rust1", since = "1.0.0")]
1112 impl fmt
::Debug
for BitVec
{
1113 fn fmt(&self, fmt
: &mut fmt
::Formatter
) -> fmt
::Result
{
1115 try
!(write
!(fmt
, "{}", if bit { 1 }
else { 0 }
));
1121 #[stable(feature = "rust1", since = "1.0.0")]
1122 impl hash
::Hash
for BitVec
{
1123 fn hash
<H
: hash
::Hasher
>(&self, state
: &mut H
) {
1124 self.nbits
.hash(state
);
1125 for elem
in self.blocks() {
1131 #[stable(feature = "rust1", since = "1.0.0")]
1132 impl cmp
::PartialEq
for BitVec
{
1134 fn eq(&self, other
: &BitVec
) -> bool
{
1135 if self.nbits
!= other
.nbits
{
1138 self.blocks().zip(other
.blocks()).all(|(w1
, w2
)| w1
== w2
)
1142 #[stable(feature = "rust1", since = "1.0.0")]
1143 impl cmp
::Eq
for BitVec {}
1145 /// An iterator for `BitVec`.
1146 #[stable(feature = "rust1", since = "1.0.0")]
1148 pub struct Iter
<'a
> {
1149 bit_vec
: &'a BitVec
,
1154 #[stable(feature = "rust1", since = "1.0.0")]
1155 impl<'a
> Iterator
for Iter
<'a
> {
1159 fn next(&mut self) -> Option
<bool
> {
1160 if self.next_idx
!= self.end_idx
{
1161 let idx
= self.next_idx
;
1163 Some(self.bit_vec
[idx
])
1169 fn size_hint(&self) -> (usize, Option
<usize>) {
1170 let rem
= self.end_idx
- self.next_idx
;
1175 #[stable(feature = "rust1", since = "1.0.0")]
1176 impl<'a
> DoubleEndedIterator
for Iter
<'a
> {
1178 fn next_back(&mut self) -> Option
<bool
> {
1179 if self.next_idx
!= self.end_idx
{
1181 Some(self.bit_vec
[self.end_idx
])
1188 #[stable(feature = "rust1", since = "1.0.0")]
1189 impl<'a
> ExactSizeIterator
for Iter
<'a
> {}
1191 #[stable(feature = "rust1", since = "1.0.0")]
1192 #[allow(deprecated)]
1193 impl<'a
> RandomAccessIterator
for Iter
<'a
> {
1195 fn indexable(&self) -> usize {
1196 self.end_idx
- self.next_idx
1200 fn idx(&mut self, index
: usize) -> Option
<bool
> {
1201 if index
>= self.indexable() {
1204 Some(self.bit_vec
[index
])
1209 #[stable(feature = "rust1", since = "1.0.0")]
1210 impl<'a
> IntoIterator
for &'a BitVec
{
1212 type IntoIter
= Iter
<'a
>;
1214 fn into_iter(self) -> Iter
<'a
> {
1219 /// An implementation of a set using a bit vector as an underlying
1220 /// representation for holding unsigned numerical elements.
1222 /// It should also be noted that the amount of storage necessary for holding a
1223 /// set of objects is proportional to the maximum of the objects when viewed
1229 /// # #![feature(bitvec, bitset)]
1230 /// use std::collections::{BitSet, BitVec};
1232 /// // It's a regular set
1233 /// let mut s = BitSet::new();
1240 /// if !s.contains(&7) {
1241 /// println!("There is no 7");
1244 /// // Can initialize from a `BitVec`
1245 /// let other = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11010000]));
1247 /// s.union_with(&other);
1249 /// // Print 0, 1, 3 in some order
1251 /// println!("{}", x);
1254 /// // Can convert back to a `BitVec`
1255 /// let bv: BitVec = s.into_bit_vec();
1259 #[unstable(feature = "bitset", reason = "RFC 509")]
1264 #[stable(feature = "rust1", since = "1.0.0")]
1265 impl Default
for BitSet
{
1267 fn default() -> BitSet { BitSet::new() }
1270 #[stable(feature = "rust1", since = "1.0.0")]
1271 impl FromIterator
<usize> for BitSet
{
1272 fn from_iter
<I
: IntoIterator
<Item
=usize>>(iter
: I
) -> BitSet
{
1273 let mut ret
= BitSet
::new();
1279 #[stable(feature = "rust1", since = "1.0.0")]
1280 impl Extend
<usize> for BitSet
{
1282 fn extend
<I
: IntoIterator
<Item
=usize>>(&mut self, iter
: I
) {
1289 #[stable(feature = "extend_ref", since = "1.2.0")]
1290 impl<'a
> Extend
<&'a
usize> for BitSet
{
1291 fn extend
<I
: IntoIterator
<Item
=&'a
usize>>(&mut self, iter
: I
) {
1292 self.extend(iter
.into_iter().cloned());
1296 #[stable(feature = "rust1", since = "1.0.0")]
1297 impl PartialOrd
for BitSet
{
1299 fn partial_cmp(&self, other
: &BitSet
) -> Option
<Ordering
> {
1300 let (a_iter
, b_iter
) = match_words(self.get_ref(), other
.get_ref());
1301 iter
::order
::partial_cmp(a_iter
, b_iter
)
1305 #[stable(feature = "rust1", since = "1.0.0")]
1306 impl Ord
for BitSet
{
1308 fn cmp(&self, other
: &BitSet
) -> Ordering
{
1309 let (a_iter
, b_iter
) = match_words(self.get_ref(), other
.get_ref());
1310 iter
::order
::cmp(a_iter
, b_iter
)
1314 #[stable(feature = "rust1", since = "1.0.0")]
1315 impl cmp
::PartialEq
for BitSet
{
1317 fn eq(&self, other
: &BitSet
) -> bool
{
1318 let (a_iter
, b_iter
) = match_words(self.get_ref(), other
.get_ref());
1319 iter
::order
::eq(a_iter
, b_iter
)
1323 #[stable(feature = "rust1", since = "1.0.0")]
1324 impl cmp
::Eq
for BitSet {}
1326 #[unstable(feature = "bitset", reason = "RFC 509")]
1328 /// Creates a new empty `BitSet`.
1333 /// # #![feature(bitset)]
1334 /// use std::collections::BitSet;
1336 /// let mut s = BitSet::new();
1339 #[stable(feature = "rust1", since = "1.0.0")]
1340 pub fn new() -> BitSet
{
1341 BitSet { bit_vec: BitVec::new() }
1344 /// Creates a new `BitSet` with initially no contents, able to
1345 /// hold `nbits` elements without resizing.
1350 /// # #![feature(bitset)]
1351 /// use std::collections::BitSet;
1353 /// let mut s = BitSet::with_capacity(100);
1354 /// assert!(s.capacity() >= 100);
1357 #[stable(feature = "rust1", since = "1.0.0")]
1358 pub fn with_capacity(nbits
: usize) -> BitSet
{
1359 let bit_vec
= BitVec
::from_elem(nbits
, false);
1360 BitSet
::from_bit_vec(bit_vec
)
1363 /// Creates a new `BitSet` from the given bit vector.
1368 /// # #![feature(bitset, bitvec)]
1369 /// use std::collections::{BitVec, BitSet};
1371 /// let bv = BitVec::from_bytes(&[0b01100000]);
1372 /// let s = BitSet::from_bit_vec(bv);
1374 /// // Print 1, 2 in arbitrary order
1376 /// println!("{}", x);
1380 pub fn from_bit_vec(bit_vec
: BitVec
) -> BitSet
{
1381 BitSet { bit_vec: bit_vec }
1384 /// Returns the capacity in bits for this bit vector. Inserting any
1385 /// element less than this amount will not trigger a resizing.
1390 /// # #![feature(bitset)]
1391 /// use std::collections::BitSet;
1393 /// let mut s = BitSet::with_capacity(100);
1394 /// assert!(s.capacity() >= 100);
1397 #[stable(feature = "rust1", since = "1.0.0")]
1398 pub fn capacity(&self) -> usize {
1399 self.bit_vec
.capacity()
1402 /// Reserves capacity for the given `BitSet` to contain `len` distinct
1403 /// elements. In the case of `BitSet` this means reallocations will not
1404 /// occur as long as all inserted elements are less than `len`.
1406 /// The collection may reserve more space to avoid frequent reallocations.
1412 /// # #![feature(bitset)]
1413 /// use std::collections::BitSet;
1415 /// let mut s = BitSet::new();
1416 /// s.reserve_len(10);
1417 /// assert!(s.capacity() >= 10);
1419 #[stable(feature = "rust1", since = "1.0.0")]
1420 pub fn reserve_len(&mut self, len
: usize) {
1421 let cur_len
= self.bit_vec
.len();
1423 self.bit_vec
.reserve(len
- cur_len
);
1427 /// Reserves the minimum capacity for the given `BitSet` to contain `len`
1428 /// distinct elements. In the case of `BitSet` this means reallocations
1429 /// will not occur as long as all inserted elements are less than `len`.
1431 /// Note that the allocator may give the collection more space than it
1432 /// requests. Therefore capacity can not be relied upon to be precisely
1433 /// minimal. Prefer `reserve_len` if future insertions are expected.
1439 /// # #![feature(bitset)]
1440 /// use std::collections::BitSet;
1442 /// let mut s = BitSet::new();
1443 /// s.reserve_len_exact(10);
1444 /// assert!(s.capacity() >= 10);
1446 #[stable(feature = "rust1", since = "1.0.0")]
1447 pub fn reserve_len_exact(&mut self, len
: usize) {
1448 let cur_len
= self.bit_vec
.len();
1450 self.bit_vec
.reserve_exact(len
- cur_len
);
1455 /// Consumes this set to return the underlying bit vector.
1460 /// # #![feature(bitset)]
1461 /// use std::collections::BitSet;
1463 /// let mut s = BitSet::new();
1467 /// let bv = s.into_bit_vec();
1472 pub fn into_bit_vec(self) -> BitVec
{
1476 /// Returns a reference to the underlying bit vector.
1481 /// # #![feature(bitset)]
1482 /// use std::collections::BitSet;
1484 /// let mut s = BitSet::new();
1487 /// let bv = s.get_ref();
1488 /// assert_eq!(bv[0], true);
1491 pub fn get_ref(&self) -> &BitVec
{
1496 fn other_op
<F
>(&mut self, other
: &BitSet
, mut f
: F
) where F
: FnMut(u32, u32) -> u32 {
1498 let self_bit_vec
= &mut self.bit_vec
;
1499 let other_bit_vec
= &other
.bit_vec
;
1501 let self_len
= self_bit_vec
.len();
1502 let other_len
= other_bit_vec
.len();
1504 // Expand the vector if necessary
1505 if self_len
< other_len
{
1506 self_bit_vec
.grow(other_len
- self_len
, false);
1509 // virtually pad other with 0's for equal lengths
1511 let (_
, result
) = match_words(self_bit_vec
, other_bit_vec
);
1515 // Apply values found in other
1516 for (i
, w
) in other_words
{
1517 let old
= self_bit_vec
.storage
[i
];
1518 let new
= f(old
, w
);
1519 self_bit_vec
.storage
[i
] = new
;
1523 /// Truncates the underlying vector to the least length required.
1528 /// # #![feature(bitset)]
1529 /// use std::collections::BitSet;
1531 /// let mut s = BitSet::new();
1532 /// s.insert(32183231);
1533 /// s.remove(&32183231);
1535 /// // Internal storage will probably be bigger than necessary
1536 /// println!("old capacity: {}", s.capacity());
1538 /// // Now should be smaller
1539 /// s.shrink_to_fit();
1540 /// println!("new capacity: {}", s.capacity());
1543 #[stable(feature = "rust1", since = "1.0.0")]
1544 pub fn shrink_to_fit(&mut self) {
1545 let bit_vec
= &mut self.bit_vec
;
1546 // Obtain original length
1547 let old_len
= bit_vec
.storage
.len();
1548 // Obtain coarse trailing zero length
1549 let n
= bit_vec
.storage
.iter().rev().take_while(|&&n
| n
== 0).count();
1551 let trunc_len
= cmp
::max(old_len
- n
, 1);
1552 bit_vec
.storage
.truncate(trunc_len
);
1553 bit_vec
.nbits
= trunc_len
* u32::BITS
;
1556 /// Iterator over each usize stored in the `BitSet`.
1561 /// # #![feature(bitset, bitvec)]
1562 /// use std::collections::{BitVec, BitSet};
1564 /// let s = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01001010]));
1566 /// // Print 1, 4, 6 in arbitrary order
1567 /// for x in s.iter() {
1568 /// println!("{}", x);
1572 #[stable(feature = "rust1", since = "1.0.0")]
1573 pub fn iter(&self) -> bit_set
::Iter
{
1574 SetIter(BlockIter
::from_blocks(self.bit_vec
.blocks()))
1577 /// Iterator over each usize stored in `self` union `other`.
1578 /// See [union_with](#method.union_with) for an efficient in-place version.
1583 /// # #![feature(bitset, bitvec)]
1584 /// use std::collections::{BitVec, BitSet};
1586 /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
1587 /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));
1589 /// // Print 0, 1, 2, 4 in arbitrary order
1590 /// for x in a.union(&b) {
1591 /// println!("{}", x);
1595 #[stable(feature = "rust1", since = "1.0.0")]
1596 pub fn union<'a
>(&'a
self, other
: &'a BitSet
) -> Union
<'a
> {
1597 fn or(w1
: u32, w2
: u32) -> u32 { w1 | w2 }
1599 Union(BlockIter
::from_blocks(TwoBitPositions
{
1600 set
: self.bit_vec
.blocks(),
1601 other
: other
.bit_vec
.blocks(),
1606 /// Iterator over each usize stored in `self` intersect `other`.
1607 /// See [intersect_with](#method.intersect_with) for an efficient in-place
1613 /// # #![feature(bitset, bitvec)]
1614 /// use std::collections::{BitVec, BitSet};
1616 /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
1617 /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));
1620 /// for x in a.intersection(&b) {
1621 /// println!("{}", x);
1625 #[stable(feature = "rust1", since = "1.0.0")]
1626 pub fn intersection
<'a
>(&'a
self, other
: &'a BitSet
) -> Intersection
<'a
> {
1627 fn bitand(w1
: u32, w2
: u32) -> u32 { w1 & w2 }
1628 let min
= cmp
::min(self.bit_vec
.len(), other
.bit_vec
.len());
1630 Intersection(BlockIter
::from_blocks(TwoBitPositions
{
1631 set
: self.bit_vec
.blocks(),
1632 other
: other
.bit_vec
.blocks(),
1637 /// Iterator over each usize stored in the `self` setminus `other`.
1638 /// See [difference_with](#method.difference_with) for an efficient in-place
1644 /// # #![feature(bitset, bitvec)]
1645 /// use std::collections::{BitSet, BitVec};
1647 /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
1648 /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));
1650 /// // Print 1, 4 in arbitrary order
1651 /// for x in a.difference(&b) {
1652 /// println!("{}", x);
1655 /// // Note that difference is not symmetric,
1656 /// // and `b - a` means something else.
1657 /// // This prints 0
1658 /// for x in b.difference(&a) {
1659 /// println!("{}", x);
1663 #[stable(feature = "rust1", since = "1.0.0")]
1664 pub fn difference
<'a
>(&'a
self, other
: &'a BitSet
) -> Difference
<'a
> {
1665 fn diff(w1
: u32, w2
: u32) -> u32 { w1 & !w2 }
1667 Difference(BlockIter
::from_blocks(TwoBitPositions
{
1668 set
: self.bit_vec
.blocks(),
1669 other
: other
.bit_vec
.blocks(),
1674 /// Iterator over each usize stored in the symmetric difference of `self`
1675 /// and `other`. See
1676 /// [symmetric_difference_with](#method.symmetric_difference_with) for an
1677 /// efficient in-place version.
1682 /// # #![feature(bitset, bitvec)]
1683 /// use std::collections::{BitSet, BitVec};
1685 /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
1686 /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));
1688 /// // Print 0, 1, 4 in arbitrary order
1689 /// for x in a.symmetric_difference(&b) {
1690 /// println!("{}", x);
1694 #[stable(feature = "rust1", since = "1.0.0")]
1695 pub fn symmetric_difference
<'a
>(&'a
self, other
: &'a BitSet
) -> SymmetricDifference
<'a
> {
1696 fn bitxor(w1
: u32, w2
: u32) -> u32 { w1 ^ w2 }
1698 SymmetricDifference(BlockIter
::from_blocks(TwoBitPositions
{
1699 set
: self.bit_vec
.blocks(),
1700 other
: other
.bit_vec
.blocks(),
1705 /// Unions in-place with the specified other bit vector.
1710 /// # #![feature(bitset, bitvec)]
1711 /// use std::collections::{BitSet, BitVec};
1713 /// let a = 0b01101000;
1714 /// let b = 0b10100000;
1715 /// let res = 0b11101000;
1717 /// let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
1718 /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
1719 /// let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res]));
1721 /// a.union_with(&b);
1722 /// assert_eq!(a, res);
1725 pub fn union_with(&mut self, other
: &BitSet
) {
1726 self.other_op(other
, |w1
, w2
| w1
| w2
);
1729 /// Intersects in-place with the specified other bit vector.
1734 /// # #![feature(bitset, bitvec)]
1735 /// use std::collections::{BitSet, BitVec};
1737 /// let a = 0b01101000;
1738 /// let b = 0b10100000;
1739 /// let res = 0b00100000;
1741 /// let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
1742 /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
1743 /// let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res]));
1745 /// a.intersect_with(&b);
1746 /// assert_eq!(a, res);
1749 pub fn intersect_with(&mut self, other
: &BitSet
) {
1750 self.other_op(other
, |w1
, w2
| w1
& w2
);
1753 /// Makes this bit vector the difference with the specified other bit vector
1759 /// # #![feature(bitset, bitvec)]
1760 /// use std::collections::{BitSet, BitVec};
1762 /// let a = 0b01101000;
1763 /// let b = 0b10100000;
1764 /// let a_b = 0b01001000; // a - b
1765 /// let b_a = 0b10000000; // b - a
1767 /// let mut bva = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
1768 /// let bvb = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
1769 /// let bva_b = BitSet::from_bit_vec(BitVec::from_bytes(&[a_b]));
1770 /// let bvb_a = BitSet::from_bit_vec(BitVec::from_bytes(&[b_a]));
1772 /// bva.difference_with(&bvb);
1773 /// assert_eq!(bva, bva_b);
1775 /// let bva = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
1776 /// let mut bvb = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
1778 /// bvb.difference_with(&bva);
1779 /// assert_eq!(bvb, bvb_a);
1782 pub fn difference_with(&mut self, other
: &BitSet
) {
1783 self.other_op(other
, |w1
, w2
| w1
& !w2
);
1786 /// Makes this bit vector the symmetric difference with the specified other
1787 /// bit vector in-place.
1792 /// # #![feature(bitset, bitvec)]
1793 /// use std::collections::{BitSet, BitVec};
1795 /// let a = 0b01101000;
1796 /// let b = 0b10100000;
1797 /// let res = 0b11001000;
1799 /// let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
1800 /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
1801 /// let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res]));
1803 /// a.symmetric_difference_with(&b);
1804 /// assert_eq!(a, res);
1807 pub fn symmetric_difference_with(&mut self, other
: &BitSet
) {
1808 self.other_op(other
, |w1
, w2
| w1 ^ w2
);
1811 /// Moves all elements from `other` into `Self`, leaving `other` empty.
1816 /// # #![feature(bitset, bitvec, append)]
1817 /// use std::collections::{BitVec, BitSet};
1819 /// let mut a = BitSet::new();
1823 /// let mut b = BitSet::new();
1828 /// a.append(&mut b);
1830 /// assert_eq!(a.len(), 4);
1831 /// assert_eq!(b.len(), 0);
1832 /// assert_eq!(a, BitSet::from_bit_vec(BitVec::from_bytes(&[0b01110010])));
1834 #[unstable(feature = "append",
1835 reason
= "recently added as part of collections reform 2")]
1836 pub fn append(&mut self, other
: &mut Self) {
1837 self.union_with(other
);
1841 /// Splits the `BitSet` into two at the given key including the key.
1842 /// Retains the first part in-place while returning the second part.
1847 /// # #![feature(bitset, bitvec, split_off)]
1848 /// use std::collections::{BitSet, BitVec};
1849 /// let mut a = BitSet::new();
1855 /// let b = a.split_off(3);
1857 /// assert_eq!(a.len(), 2);
1858 /// assert_eq!(b.len(), 2);
1859 /// assert_eq!(a, BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100000])));
1860 /// assert_eq!(b, BitSet::from_bit_vec(BitVec::from_bytes(&[0b00010010])));
1862 #[unstable(feature = "split_off",
1863 reason
= "recently added as part of collections reform 2")]
1864 pub fn split_off(&mut self, at
: usize) -> Self {
1865 let mut other
= BitSet
::new();
1868 swap(self, &mut other
);
1870 } else if at
>= self.bit_vec
.len() {
1874 // Calculate block and bit at which to split
1875 let w
= at
/ u32::BITS
;
1876 let b
= at
% u32::BITS
;
1878 // Pad `other` with `w` zero blocks,
1879 // append `self`'s blocks in the range from `w` to the end to `other`
1880 other
.bit_vec
.storage
.extend(repeat(0u32).take(w
)
1881 .chain(self.bit_vec
.storage
[w
..].iter().cloned()));
1882 other
.bit_vec
.nbits
= self.bit_vec
.nbits
;
1885 other
.bit_vec
.storage
[w
] &= !0 << b
;
1888 // Sets `bit_vec.len()` and fixes the last block as well
1889 self.bit_vec
.truncate(at
);
1894 /// Returns the number of set bits in this set.
1896 #[stable(feature = "rust1", since = "1.0.0")]
1897 pub fn len(&self) -> usize {
1898 self.bit_vec
.blocks().fold(0, |acc
, n
| acc
+ n
.count_ones() as usize)
1901 /// Returns whether there are no bits set in this set
1903 #[stable(feature = "rust1", since = "1.0.0")]
1904 pub fn is_empty(&self) -> bool
{
1908 /// Clears all bits in this set
1910 #[stable(feature = "rust1", since = "1.0.0")]
1911 pub fn clear(&mut self) {
1912 self.bit_vec
.clear();
1915 /// Returns `true` if this set contains the specified integer.
1917 #[stable(feature = "rust1", since = "1.0.0")]
1918 pub fn contains(&self, value
: &usize) -> bool
{
1919 let bit_vec
= &self.bit_vec
;
1920 *value
< bit_vec
.nbits
&& bit_vec
[*value
]
1923 /// Returns `true` if the set has no elements in common with `other`.
1924 /// This is equivalent to checking for an empty intersection.
1926 #[stable(feature = "rust1", since = "1.0.0")]
1927 pub fn is_disjoint(&self, other
: &BitSet
) -> bool
{
1928 self.intersection(other
).next().is_none()
1931 /// Returns `true` if the set is a subset of another.
1933 #[stable(feature = "rust1", since = "1.0.0")]
1934 pub fn is_subset(&self, other
: &BitSet
) -> bool
{
1935 let self_bit_vec
= &self.bit_vec
;
1936 let other_bit_vec
= &other
.bit_vec
;
1937 let other_blocks
= blocks_for_bits(other_bit_vec
.len());
1939 // Check that `self` intersect `other` is self
1940 self_bit_vec
.blocks().zip(other_bit_vec
.blocks()).all(|(w1
, w2
)| w1
& w2
== w1
) &&
1941 // Make sure if `self` has any more blocks than `other`, they're all 0
1942 self_bit_vec
.blocks().skip(other_blocks
).all(|w
| w
== 0)
1945 /// Returns `true` if the set is a superset of another.
1947 #[stable(feature = "rust1", since = "1.0.0")]
1948 pub fn is_superset(&self, other
: &BitSet
) -> bool
{
1949 other
.is_subset(self)
1952 /// Adds a value to the set. Returns `true` if the value was not already
1953 /// present in the set.
1954 #[stable(feature = "rust1", since = "1.0.0")]
1955 pub fn insert(&mut self, value
: usize) -> bool
{
1956 if self.contains(&value
) {
1960 // Ensure we have enough space to hold the new element
1961 let len
= self.bit_vec
.len();
1963 self.bit_vec
.grow(value
- len
+ 1, false)
1966 self.bit_vec
.set(value
, true);
1970 /// Removes a value from the set. Returns `true` if the value was
1971 /// present in the set.
1972 #[stable(feature = "rust1", since = "1.0.0")]
1973 pub fn remove(&mut self, value
: &usize) -> bool
{
1974 if !self.contains(value
) {
1978 self.bit_vec
.set(*value
, false);
1984 #[stable(feature = "rust1", since = "1.0.0")]
1985 impl fmt
::Debug
for BitSet
{
1986 fn fmt(&self, fmt
: &mut fmt
::Formatter
) -> fmt
::Result
{
1987 try
!(write
!(fmt
, "{{"));
1988 let mut first
= true;
1991 try
!(write
!(fmt
, ", "));
1993 try
!(write
!(fmt
, "{:?}", n
));
2000 #[stable(feature = "rust1", since = "1.0.0")]
2001 impl hash
::Hash
for BitSet
{
2002 fn hash
<H
: hash
::Hasher
>(&self, state
: &mut H
) {
2010 #[stable(feature = "rust1", since = "1.0.0")]
2011 struct BlockIter
<T
> where T
: Iterator
<Item
=u32> {
2017 impl<'a
, T
> BlockIter
<T
> where T
: Iterator
<Item
=u32> {
2018 fn from_blocks(mut blocks
: T
) -> BlockIter
<T
> {
2019 let h
= blocks
.next().unwrap_or(0);
2020 BlockIter {tail: blocks, head: h, head_offset: 0}
2024 /// An iterator combining two `BitSet` iterators.
2026 struct TwoBitPositions
<'a
> {
2029 merge
: fn(u32, u32) -> u32,
2032 /// An iterator for `BitSet`.
2034 #[stable(feature = "rust1", since = "1.0.0")]
2035 pub struct SetIter
<'a
>(BlockIter
<Blocks
<'a
>>);
2037 #[stable(feature = "rust1", since = "1.0.0")]
2038 pub struct Union
<'a
>(BlockIter
<TwoBitPositions
<'a
>>);
2040 #[stable(feature = "rust1", since = "1.0.0")]
2041 pub struct Intersection
<'a
>(Take
<BlockIter
<TwoBitPositions
<'a
>>>);
2043 #[stable(feature = "rust1", since = "1.0.0")]
2044 pub struct Difference
<'a
>(BlockIter
<TwoBitPositions
<'a
>>);
2046 #[stable(feature = "rust1", since = "1.0.0")]
2047 pub struct SymmetricDifference
<'a
>(BlockIter
<TwoBitPositions
<'a
>>);
2049 #[stable(feature = "rust1", since = "1.0.0")]
2050 impl<'a
, T
> Iterator
for BlockIter
<T
> where T
: Iterator
<Item
=u32> {
2053 fn next(&mut self) -> Option
<usize> {
2054 while self.head
== 0 {
2055 match self.tail
.next() {
2056 Some(w
) => self.head
= w
,
2059 self.head_offset
+= u32::BITS
;
2062 // from the current block, isolate the
2063 // LSB and subtract 1, producing k:
2064 // a block with a number of set bits
2065 // equal to the index of the LSB
2066 let k
= (self.head
& (!self.head
+ 1)) - 1;
2067 // update block, removing the LSB
2068 self.head
&= self.head
- 1;
2069 // return offset + (index of LSB)
2070 Some(self.head_offset
+ (u32::count_ones(k
) as usize))
2074 fn size_hint(&self) -> (usize, Option
<usize>) {
2075 match self.tail
.size_hint() {
2076 (_
, Some(h
)) => (0, Some(1 + h
* (u32::BITS
as usize))),
2082 #[stable(feature = "rust1", since = "1.0.0")]
2083 impl<'a
> Iterator
for TwoBitPositions
<'a
> {
2086 fn next(&mut self) -> Option
<u32> {
2087 match (self.set
.next(), self.other
.next()) {
2088 (Some(a
), Some(b
)) => Some((self.merge
)(a
, b
)),
2089 (Some(a
), None
) => Some((self.merge
)(a
, 0)),
2090 (None
, Some(b
)) => Some((self.merge
)(0, b
)),
2096 fn size_hint(&self) -> (usize, Option
<usize>) {
2097 let (a
, au
) = self.set
.size_hint();
2098 let (b
, bu
) = self.other
.size_hint();
2100 let upper
= match (au
, bu
) {
2101 (Some(au
), Some(bu
)) => Some(cmp
::max(au
, bu
)),
2105 (cmp
::max(a
, b
), upper
)
2109 #[stable(feature = "rust1", since = "1.0.0")]
2110 impl<'a
> Iterator
for SetIter
<'a
> {
2113 #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
2114 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
2117 #[stable(feature = "rust1", since = "1.0.0")]
2118 impl<'a
> Iterator
for Union
<'a
> {
2121 #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
2122 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
2125 #[stable(feature = "rust1", since = "1.0.0")]
2126 impl<'a
> Iterator
for Intersection
<'a
> {
2129 #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
2130 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
2133 #[stable(feature = "rust1", since = "1.0.0")]
2134 impl<'a
> Iterator
for Difference
<'a
> {
2137 #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
2138 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
2141 #[stable(feature = "rust1", since = "1.0.0")]
2142 impl<'a
> Iterator
for SymmetricDifference
<'a
> {
2145 #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
2146 #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
2149 #[stable(feature = "rust1", since = "1.0.0")]
2150 impl<'a
> IntoIterator
for &'a BitSet
{
2152 type IntoIter
= SetIter
<'a
>;
2154 fn into_iter(self) -> SetIter
<'a
> {