]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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. | |
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 | ||
85aaf69f SL |
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 | |
1a4d82fc JJ |
15 | // representation as `u32`s must be assumed for best performance. |
16 | ||
85aaf69f | 17 | // FIXME(tbu-): `BitVec`'s methods shouldn't be `union`, `intersection`, but |
1a4d82fc JJ |
18 | // rather `or` and `and`. |
19 | ||
20 | // (1) Be careful, most things can overflow here because the amount of bits in | |
85aaf69f | 21 | // memory can overflow `usize`. |
1a4d82fc JJ |
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*. | |
85aaf69f SL |
28 | // (4) `BitSet` is tightly coupled with `BitVec`, so any changes you make in |
29 | // `BitVec` will need to be reflected in `BitSet`. | |
1a4d82fc JJ |
30 | |
31 | //! Collections implemented with bit vectors. | |
32 | //! | |
33 | //! # Examples | |
34 | //! | |
35 | //! This is a simple example of the [Sieve of Eratosthenes][sieve] | |
36 | //! which calculates prime numbers up to a given limit. | |
37 | //! | |
38 | //! [sieve]: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes | |
39 | //! | |
40 | //! ``` | |
62682a34 | 41 | //! # #![feature(bitset, bitvec, range_inclusive, step_by)] |
85aaf69f | 42 | //! use std::collections::{BitSet, BitVec}; |
1a4d82fc JJ |
43 | //! use std::iter; |
44 | //! | |
45 | //! let max_prime = 10000; | |
46 | //! | |
85aaf69f | 47 | //! // Store the primes as a BitSet |
1a4d82fc JJ |
48 | //! let primes = { |
49 | //! // Assume all numbers are prime to begin, and then we | |
50 | //! // cross off non-primes progressively | |
85aaf69f | 51 | //! let mut bv = BitVec::from_elem(max_prime, true); |
1a4d82fc JJ |
52 | //! |
53 | //! // Neither 0 nor 1 are prime | |
54 | //! bv.set(0, false); | |
55 | //! bv.set(1, false); | |
56 | //! | |
85aaf69f | 57 | //! for i in iter::range_inclusive(2, (max_prime as f64).sqrt() as usize) { |
1a4d82fc JJ |
58 | //! // if i is a prime |
59 | //! if bv[i] { | |
60 | //! // Mark all multiples of i as non-prime (any multiples below i * i | |
61 | //! // will have been marked as non-prime previously) | |
c34b1796 | 62 | //! for j in (i * i..max_prime).step_by(i) { bv.set(j, false) } |
1a4d82fc JJ |
63 | //! } |
64 | //! } | |
85aaf69f | 65 | //! BitSet::from_bit_vec(bv) |
1a4d82fc JJ |
66 | //! }; |
67 | //! | |
68 | //! // Simple primality tests below our max bound | |
69 | //! let print_primes = 20; | |
70 | //! print!("The primes below {} are: ", print_primes); | |
85aaf69f | 71 | //! for x in 0..print_primes { |
1a4d82fc JJ |
72 | //! if primes.contains(&x) { |
73 | //! print!("{} ", x); | |
74 | //! } | |
75 | //! } | |
76 | //! println!(""); | |
77 | //! | |
85aaf69f | 78 | //! // We can manipulate the internal BitVec |
1a4d82fc JJ |
79 | //! let num_primes = primes.get_ref().iter().filter(|x| *x).count(); |
80 | //! println!("There are {} primes below {}", num_primes, max_prime); | |
81 | //! ``` | |
82 | ||
83 | use core::prelude::*; | |
84 | ||
85 | use core::cmp::Ordering; | |
86 | use core::cmp; | |
1a4d82fc JJ |
87 | use core::fmt; |
88 | use core::hash; | |
62682a34 | 89 | #[allow(deprecated)] |
1a4d82fc JJ |
90 | use core::iter::RandomAccessIterator; |
91 | use core::iter::{Chain, Enumerate, Repeat, Skip, Take, repeat, Cloned}; | |
9346a6ac | 92 | use core::iter::{self, FromIterator}; |
d9579d0f | 93 | use core::mem::swap; |
1a4d82fc JJ |
94 | use core::ops::Index; |
95 | use core::slice; | |
85aaf69f SL |
96 | use core::{u8, u32, usize}; |
97 | use bit_set; //so meta | |
1a4d82fc JJ |
98 | |
99 | use Vec; | |
100 | ||
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>>>>>; | |
104 | ||
105 | fn reverse_bits(byte: u8) -> u8 { | |
106 | let mut result = 0; | |
85aaf69f | 107 | for i in 0..u8::BITS { |
1a4d82fc JJ |
108 | result |= ((byte >> i) & 1) << (u8::BITS - 1 - i); |
109 | } | |
110 | result | |
111 | } | |
112 | ||
c34b1796 | 113 | // Take two BitVec's, and return iterators of their words, where the shorter one |
1a4d82fc | 114 | // has been padded with 0's |
85aaf69f | 115 | fn match_words <'a,'b>(a: &'a BitVec, b: &'b BitVec) -> (MatchWords<'a>, MatchWords<'b>) { |
1a4d82fc JJ |
116 | let a_len = a.storage.len(); |
117 | let b_len = b.storage.len(); | |
118 | ||
119 | // have to uselessly pretend to pad the longer one for type matching | |
120 | if a_len < b_len { | |
c34b1796 AL |
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))) | |
1a4d82fc | 123 | } else { |
c34b1796 AL |
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))) | |
1a4d82fc JJ |
126 | } |
127 | } | |
128 | ||
62682a34 SL |
129 | const TRUE: &'static bool = &true; |
130 | const FALSE: &'static bool = &false; | |
1a4d82fc JJ |
131 | |
132 | /// The bitvector type. | |
133 | /// | |
134 | /// # Examples | |
135 | /// | |
c34b1796 | 136 | /// ``` |
62682a34 | 137 | /// # #![feature(bitvec)] |
85aaf69f | 138 | /// use std::collections::BitVec; |
1a4d82fc | 139 | /// |
85aaf69f | 140 | /// let mut bv = BitVec::from_elem(10, false); |
1a4d82fc JJ |
141 | /// |
142 | /// // insert all primes less than 10 | |
143 | /// bv.set(2, true); | |
144 | /// bv.set(3, true); | |
145 | /// bv.set(5, true); | |
146 | /// bv.set(7, true); | |
147 | /// println!("{:?}", bv); | |
148 | /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count()); | |
149 | /// | |
150 | /// // flip all values in bitvector, producing non-primes less than 10 | |
151 | /// bv.negate(); | |
152 | /// println!("{:?}", bv); | |
153 | /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count()); | |
154 | /// | |
155 | /// // reset bitvector to empty | |
156 | /// bv.clear(); | |
157 | /// println!("{:?}", bv); | |
158 | /// println!("total bits set to true: {}", bv.iter().filter(|x| *x).count()); | |
159 | /// ``` | |
62682a34 | 160 | #[unstable(feature = "bitvec", reason = "RFC 509")] |
85aaf69f | 161 | pub struct BitVec { |
1a4d82fc JJ |
162 | /// Internal representation of the bit vector |
163 | storage: Vec<u32>, | |
164 | /// The number of valid bits in the internal representation | |
85aaf69f | 165 | nbits: usize |
1a4d82fc JJ |
166 | } |
167 | ||
168 | // FIXME(Gankro): NopeNopeNopeNopeNope (wait for IndexGet to be a thing) | |
85aaf69f | 169 | impl Index<usize> for BitVec { |
1a4d82fc JJ |
170 | type Output = bool; |
171 | ||
172 | #[inline] | |
c34b1796 AL |
173 | fn index(&self, i: usize) -> &bool { |
174 | if self.get(i).expect("index out of bounds") { | |
62682a34 | 175 | TRUE |
1a4d82fc | 176 | } else { |
62682a34 | 177 | FALSE |
1a4d82fc JJ |
178 | } |
179 | } | |
180 | } | |
181 | ||
182 | /// Computes how many blocks are needed to store that many bits | |
85aaf69f | 183 | fn blocks_for_bits(bits: usize) -> usize { |
62682a34 SL |
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. | |
1a4d82fc JJ |
190 | // |
191 | // Note that we can technically avoid this branch with the expression | |
62682a34 SL |
192 | // `(nbits + u32::BITS - 1) / 32::BITS`, but if nbits is almost usize::MAX |
193 | // this will overflow. | |
9346a6ac AL |
194 | if bits % u32::BITS == 0 { |
195 | bits / u32::BITS | |
1a4d82fc | 196 | } else { |
9346a6ac | 197 | bits / u32::BITS + 1 |
1a4d82fc JJ |
198 | } |
199 | } | |
200 | ||
201 | /// Computes the bitmask for the final word of the vector | |
85aaf69f | 202 | fn mask_for_bits(bits: usize) -> u32 { |
1a4d82fc | 203 | // Note especially that a perfect multiple of u32::BITS should mask all 1s. |
9346a6ac | 204 | !0 >> (u32::BITS - bits % u32::BITS) % u32::BITS |
1a4d82fc JJ |
205 | } |
206 | ||
62682a34 | 207 | #[unstable(feature = "bitvec", reason = "RFC 509")] |
85aaf69f | 208 | impl BitVec { |
1a4d82fc JJ |
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 | |
211 | /// last word. | |
212 | #[inline] | |
85aaf69f | 213 | fn process<F>(&mut self, other: &BitVec, mut op: F) -> bool where F: FnMut(u32, u32) -> u32 { |
1a4d82fc JJ |
214 | assert_eq!(self.len(), other.len()); |
215 | // This could theoretically be a `debug_assert!`. | |
216 | assert_eq!(self.storage.len(), other.storage.len()); | |
d9579d0f | 217 | let mut changed_bits = 0; |
1a4d82fc JJ |
218 | for (a, b) in self.blocks_mut().zip(other.blocks()) { |
219 | let w = op(*a, b); | |
d9579d0f AL |
220 | changed_bits |= *a ^ w; |
221 | *a = w; | |
1a4d82fc | 222 | } |
d9579d0f | 223 | changed_bits != 0 |
1a4d82fc JJ |
224 | } |
225 | ||
226 | /// Iterator over mutable refs to the underlying blocks of data. | |
227 | fn blocks_mut(&mut self) -> MutBlocks { | |
228 | // (2) | |
229 | self.storage.iter_mut() | |
230 | } | |
231 | ||
232 | /// Iterator over the underlying blocks of data | |
233 | fn blocks(&self) -> Blocks { | |
234 | // (2) | |
235 | self.storage.iter().cloned() | |
236 | } | |
237 | ||
238 | /// An operation might screw up the unused bits in the last block of the | |
85aaf69f | 239 | /// `BitVec`. As per (3), it's assumed to be all 0s. This method fixes it up. |
1a4d82fc | 240 | fn fix_last_block(&mut self) { |
9346a6ac | 241 | let extra_bits = self.len() % u32::BITS; |
1a4d82fc JJ |
242 | if extra_bits > 0 { |
243 | let mask = (1 << extra_bits) - 1; | |
244 | let storage_len = self.storage.len(); | |
245 | self.storage[storage_len - 1] &= mask; | |
246 | } | |
247 | } | |
248 | ||
85aaf69f | 249 | /// Creates an empty `BitVec`. |
1a4d82fc JJ |
250 | /// |
251 | /// # Examples | |
252 | /// | |
253 | /// ``` | |
62682a34 | 254 | /// # #![feature(bitvec)] |
85aaf69f SL |
255 | /// use std::collections::BitVec; |
256 | /// let mut bv = BitVec::new(); | |
1a4d82fc | 257 | /// ``` |
85aaf69f SL |
258 | #[stable(feature = "rust1", since = "1.0.0")] |
259 | pub fn new() -> BitVec { | |
260 | BitVec { storage: Vec::new(), nbits: 0 } | |
1a4d82fc JJ |
261 | } |
262 | ||
85aaf69f | 263 | /// Creates a `BitVec` that holds `nbits` elements, setting each element |
1a4d82fc JJ |
264 | /// to `bit`. |
265 | /// | |
266 | /// # Examples | |
267 | /// | |
268 | /// ``` | |
62682a34 | 269 | /// # #![feature(bitvec)] |
85aaf69f | 270 | /// use std::collections::BitVec; |
1a4d82fc | 271 | /// |
62682a34 | 272 | /// let bv = BitVec::from_elem(10, false); |
85aaf69f | 273 | /// assert_eq!(bv.len(), 10); |
62682a34 | 274 | /// for x in &bv { |
1a4d82fc JJ |
275 | /// assert_eq!(x, false); |
276 | /// } | |
277 | /// ``` | |
85aaf69f | 278 | pub fn from_elem(nbits: usize, bit: bool) -> BitVec { |
1a4d82fc | 279 | let nblocks = blocks_for_bits(nbits); |
85aaf69f | 280 | let mut bit_vec = BitVec { |
c34b1796 | 281 | storage: repeat(if bit { !0 } else { 0 }).take(nblocks).collect(), |
1a4d82fc JJ |
282 | nbits: nbits |
283 | }; | |
85aaf69f SL |
284 | bit_vec.fix_last_block(); |
285 | bit_vec | |
1a4d82fc JJ |
286 | } |
287 | ||
85aaf69f | 288 | /// Constructs a new, empty `BitVec` with the specified capacity. |
1a4d82fc JJ |
289 | /// |
290 | /// The bitvector will be able to hold at least `capacity` bits without | |
291 | /// reallocating. If `capacity` is 0, it will not allocate. | |
292 | /// | |
293 | /// It is important to note that this function does not specify the | |
294 | /// *length* of the returned bitvector, but only the *capacity*. | |
85aaf69f SL |
295 | #[stable(feature = "rust1", since = "1.0.0")] |
296 | pub fn with_capacity(nbits: usize) -> BitVec { | |
297 | BitVec { | |
1a4d82fc JJ |
298 | storage: Vec::with_capacity(blocks_for_bits(nbits)), |
299 | nbits: 0, | |
300 | } | |
301 | } | |
302 | ||
85aaf69f | 303 | /// Transforms a byte-vector into a `BitVec`. Each byte becomes eight bits, |
1a4d82fc JJ |
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. | |
306 | /// | |
307 | /// # Examples | |
308 | /// | |
309 | /// ``` | |
62682a34 | 310 | /// # #![feature(bitvec)] |
85aaf69f | 311 | /// use std::collections::BitVec; |
1a4d82fc | 312 | /// |
85aaf69f | 313 | /// let bv = BitVec::from_bytes(&[0b10100000, 0b00010010]); |
1a4d82fc JJ |
314 | /// assert!(bv.eq_vec(&[true, false, true, false, |
315 | /// false, false, false, false, | |
316 | /// false, false, false, true, | |
317 | /// false, false, true, false])); | |
318 | /// ``` | |
85aaf69f | 319 | pub fn from_bytes(bytes: &[u8]) -> BitVec { |
9346a6ac | 320 | let len = bytes.len().checked_mul(u8::BITS).expect("capacity overflow"); |
85aaf69f | 321 | let mut bit_vec = BitVec::with_capacity(len); |
1a4d82fc JJ |
322 | let complete_words = bytes.len() / 4; |
323 | let extra_bytes = bytes.len() % 4; | |
324 | ||
85aaf69f | 325 | bit_vec.nbits = len; |
1a4d82fc | 326 | |
85aaf69f SL |
327 | for i in 0..complete_words { |
328 | bit_vec.storage.push( | |
1a4d82fc JJ |
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) | |
333 | ); | |
334 | } | |
335 | ||
336 | if extra_bytes > 0 { | |
c34b1796 | 337 | let mut last_word = 0; |
85aaf69f | 338 | for (i, &byte) in bytes[complete_words*4..].iter().enumerate() { |
1a4d82fc JJ |
339 | last_word |= (reverse_bits(byte) as u32) << (i * 8); |
340 | } | |
85aaf69f | 341 | bit_vec.storage.push(last_word); |
1a4d82fc JJ |
342 | } |
343 | ||
85aaf69f | 344 | bit_vec |
1a4d82fc JJ |
345 | } |
346 | ||
85aaf69f | 347 | /// Creates a `BitVec` of the specified length where the value at each index |
1a4d82fc JJ |
348 | /// is `f(index)`. |
349 | /// | |
350 | /// # Examples | |
351 | /// | |
352 | /// ``` | |
62682a34 | 353 | /// # #![feature(bitvec)] |
85aaf69f | 354 | /// use std::collections::BitVec; |
1a4d82fc | 355 | /// |
85aaf69f | 356 | /// let bv = BitVec::from_fn(5, |i| { i % 2 == 0 }); |
1a4d82fc JJ |
357 | /// assert!(bv.eq_vec(&[true, false, true, false, true])); |
358 | /// ``` | |
85aaf69f SL |
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); | |
361 | for i in 0..len { | |
362 | bit_vec.set(i, f(i)); | |
1a4d82fc | 363 | } |
85aaf69f | 364 | bit_vec |
1a4d82fc JJ |
365 | } |
366 | ||
367 | /// Retrieves the value at index `i`, or `None` if the index is out of bounds. | |
368 | /// | |
369 | /// # Examples | |
370 | /// | |
371 | /// ``` | |
62682a34 | 372 | /// # #![feature(bitvec)] |
85aaf69f | 373 | /// use std::collections::BitVec; |
1a4d82fc | 374 | /// |
85aaf69f | 375 | /// let bv = BitVec::from_bytes(&[0b01100000]); |
1a4d82fc JJ |
376 | /// assert_eq!(bv.get(0), Some(false)); |
377 | /// assert_eq!(bv.get(1), Some(true)); | |
378 | /// assert_eq!(bv.get(100), None); | |
379 | /// | |
380 | /// // Can also use array indexing | |
381 | /// assert_eq!(bv[1], true); | |
382 | /// ``` | |
383 | #[inline] | |
85aaf69f SL |
384 | #[stable(feature = "rust1", since = "1.0.0")] |
385 | pub fn get(&self, i: usize) -> Option<bool> { | |
1a4d82fc JJ |
386 | if i >= self.nbits { |
387 | return None; | |
388 | } | |
9346a6ac AL |
389 | let w = i / u32::BITS; |
390 | let b = i % u32::BITS; | |
1a4d82fc JJ |
391 | self.storage.get(w).map(|&block| |
392 | (block & (1 << b)) != 0 | |
393 | ) | |
394 | } | |
395 | ||
396 | /// Sets the value of a bit at an index `i`. | |
397 | /// | |
398 | /// # Panics | |
399 | /// | |
400 | /// Panics if `i` is out of bounds. | |
401 | /// | |
402 | /// # Examples | |
403 | /// | |
404 | /// ``` | |
62682a34 | 405 | /// # #![feature(bitvec)] |
85aaf69f | 406 | /// use std::collections::BitVec; |
1a4d82fc | 407 | /// |
85aaf69f | 408 | /// let mut bv = BitVec::from_elem(5, false); |
1a4d82fc JJ |
409 | /// bv.set(3, true); |
410 | /// assert_eq!(bv[3], true); | |
411 | /// ``` | |
412 | #[inline] | |
85aaf69f | 413 | pub fn set(&mut self, i: usize, x: bool) { |
1a4d82fc | 414 | assert!(i < self.nbits); |
9346a6ac AL |
415 | let w = i / u32::BITS; |
416 | let b = i % u32::BITS; | |
1a4d82fc JJ |
417 | let flag = 1 << b; |
418 | let val = if x { self.storage[w] | flag } | |
419 | else { self.storage[w] & !flag }; | |
420 | self.storage[w] = val; | |
421 | } | |
422 | ||
423 | /// Sets all bits to 1. | |
424 | /// | |
425 | /// # Examples | |
426 | /// | |
427 | /// ``` | |
62682a34 | 428 | /// # #![feature(bitvec)] |
85aaf69f | 429 | /// use std::collections::BitVec; |
1a4d82fc JJ |
430 | /// |
431 | /// let before = 0b01100000; | |
432 | /// let after = 0b11111111; | |
433 | /// | |
85aaf69f | 434 | /// let mut bv = BitVec::from_bytes(&[before]); |
1a4d82fc | 435 | /// bv.set_all(); |
85aaf69f | 436 | /// assert_eq!(bv, BitVec::from_bytes(&[after])); |
1a4d82fc JJ |
437 | /// ``` |
438 | #[inline] | |
439 | pub fn set_all(&mut self) { | |
c34b1796 | 440 | for w in &mut self.storage { *w = !0; } |
1a4d82fc JJ |
441 | self.fix_last_block(); |
442 | } | |
443 | ||
444 | /// Flips all bits. | |
445 | /// | |
446 | /// # Examples | |
447 | /// | |
448 | /// ``` | |
62682a34 | 449 | /// # #![feature(bitvec)] |
85aaf69f | 450 | /// use std::collections::BitVec; |
1a4d82fc JJ |
451 | /// |
452 | /// let before = 0b01100000; | |
453 | /// let after = 0b10011111; | |
454 | /// | |
85aaf69f | 455 | /// let mut bv = BitVec::from_bytes(&[before]); |
1a4d82fc | 456 | /// bv.negate(); |
85aaf69f | 457 | /// assert_eq!(bv, BitVec::from_bytes(&[after])); |
1a4d82fc JJ |
458 | /// ``` |
459 | #[inline] | |
460 | pub fn negate(&mut self) { | |
85aaf69f | 461 | for w in &mut self.storage { *w = !*w; } |
1a4d82fc JJ |
462 | self.fix_last_block(); |
463 | } | |
464 | ||
465 | /// Calculates the union of two bitvectors. This acts like the bitwise `or` | |
466 | /// function. | |
467 | /// | |
468 | /// Sets `self` to the union of `self` and `other`. Both bitvectors must be | |
469 | /// the same length. Returns `true` if `self` changed. | |
470 | /// | |
471 | /// # Panics | |
472 | /// | |
473 | /// Panics if the bitvectors are of different lengths. | |
474 | /// | |
475 | /// # Examples | |
476 | /// | |
477 | /// ``` | |
62682a34 | 478 | /// # #![feature(bitvec)] |
85aaf69f | 479 | /// use std::collections::BitVec; |
1a4d82fc JJ |
480 | /// |
481 | /// let a = 0b01100100; | |
482 | /// let b = 0b01011010; | |
483 | /// let res = 0b01111110; | |
484 | /// | |
85aaf69f SL |
485 | /// let mut a = BitVec::from_bytes(&[a]); |
486 | /// let b = BitVec::from_bytes(&[b]); | |
1a4d82fc JJ |
487 | /// |
488 | /// assert!(a.union(&b)); | |
85aaf69f | 489 | /// assert_eq!(a, BitVec::from_bytes(&[res])); |
1a4d82fc JJ |
490 | /// ``` |
491 | #[inline] | |
85aaf69f | 492 | pub fn union(&mut self, other: &BitVec) -> bool { |
1a4d82fc JJ |
493 | self.process(other, |w1, w2| w1 | w2) |
494 | } | |
495 | ||
496 | /// Calculates the intersection of two bitvectors. This acts like the | |
497 | /// bitwise `and` function. | |
498 | /// | |
499 | /// Sets `self` to the intersection of `self` and `other`. Both bitvectors | |
500 | /// must be the same length. Returns `true` if `self` changed. | |
501 | /// | |
502 | /// # Panics | |
503 | /// | |
504 | /// Panics if the bitvectors are of different lengths. | |
505 | /// | |
506 | /// # Examples | |
507 | /// | |
508 | /// ``` | |
62682a34 | 509 | /// # #![feature(bitvec)] |
85aaf69f | 510 | /// use std::collections::BitVec; |
1a4d82fc JJ |
511 | /// |
512 | /// let a = 0b01100100; | |
513 | /// let b = 0b01011010; | |
514 | /// let res = 0b01000000; | |
515 | /// | |
85aaf69f SL |
516 | /// let mut a = BitVec::from_bytes(&[a]); |
517 | /// let b = BitVec::from_bytes(&[b]); | |
1a4d82fc JJ |
518 | /// |
519 | /// assert!(a.intersect(&b)); | |
85aaf69f | 520 | /// assert_eq!(a, BitVec::from_bytes(&[res])); |
1a4d82fc JJ |
521 | /// ``` |
522 | #[inline] | |
85aaf69f | 523 | pub fn intersect(&mut self, other: &BitVec) -> bool { |
1a4d82fc JJ |
524 | self.process(other, |w1, w2| w1 & w2) |
525 | } | |
526 | ||
527 | /// Calculates the difference between two bitvectors. | |
528 | /// | |
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. | |
532 | /// | |
533 | /// # Panics | |
534 | /// | |
535 | /// Panics if the bitvectors are of different length. | |
536 | /// | |
537 | /// # Examples | |
538 | /// | |
539 | /// ``` | |
62682a34 | 540 | /// # #![feature(bitvec)] |
85aaf69f | 541 | /// use std::collections::BitVec; |
1a4d82fc JJ |
542 | /// |
543 | /// let a = 0b01100100; | |
544 | /// let b = 0b01011010; | |
545 | /// let a_b = 0b00100100; // a - b | |
546 | /// let b_a = 0b00011010; // b - a | |
547 | /// | |
85aaf69f SL |
548 | /// let mut bva = BitVec::from_bytes(&[a]); |
549 | /// let bvb = BitVec::from_bytes(&[b]); | |
1a4d82fc JJ |
550 | /// |
551 | /// assert!(bva.difference(&bvb)); | |
85aaf69f | 552 | /// assert_eq!(bva, BitVec::from_bytes(&[a_b])); |
1a4d82fc | 553 | /// |
85aaf69f SL |
554 | /// let bva = BitVec::from_bytes(&[a]); |
555 | /// let mut bvb = BitVec::from_bytes(&[b]); | |
1a4d82fc JJ |
556 | /// |
557 | /// assert!(bvb.difference(&bva)); | |
85aaf69f | 558 | /// assert_eq!(bvb, BitVec::from_bytes(&[b_a])); |
1a4d82fc JJ |
559 | /// ``` |
560 | #[inline] | |
85aaf69f | 561 | pub fn difference(&mut self, other: &BitVec) -> bool { |
1a4d82fc JJ |
562 | self.process(other, |w1, w2| w1 & !w2) |
563 | } | |
564 | ||
565 | /// Returns `true` if all bits are 1. | |
566 | /// | |
567 | /// # Examples | |
568 | /// | |
569 | /// ``` | |
62682a34 | 570 | /// # #![feature(bitvec)] |
85aaf69f | 571 | /// use std::collections::BitVec; |
1a4d82fc | 572 | /// |
85aaf69f | 573 | /// let mut bv = BitVec::from_elem(5, true); |
1a4d82fc JJ |
574 | /// assert_eq!(bv.all(), true); |
575 | /// | |
576 | /// bv.set(1, false); | |
577 | /// assert_eq!(bv.all(), false); | |
578 | /// ``` | |
579 | pub fn all(&self) -> bool { | |
c34b1796 | 580 | let mut last_word = !0; |
1a4d82fc JJ |
581 | // Check that every block but the last is all-ones... |
582 | self.blocks().all(|elem| { | |
583 | let tmp = last_word; | |
584 | last_word = elem; | |
c34b1796 | 585 | tmp == !0 |
1a4d82fc JJ |
586 | // and then check the last one has enough ones |
587 | }) && (last_word == mask_for_bits(self.nbits)) | |
588 | } | |
589 | ||
590 | /// Returns an iterator over the elements of the vector in order. | |
591 | /// | |
592 | /// # Examples | |
593 | /// | |
594 | /// ``` | |
62682a34 | 595 | /// # #![feature(bitvec)] |
85aaf69f | 596 | /// use std::collections::BitVec; |
1a4d82fc | 597 | /// |
85aaf69f | 598 | /// let bv = BitVec::from_bytes(&[0b01110100, 0b10010010]); |
1a4d82fc JJ |
599 | /// assert_eq!(bv.iter().filter(|x| *x).count(), 7); |
600 | /// ``` | |
601 | #[inline] | |
85aaf69f | 602 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 603 | pub fn iter(&self) -> Iter { |
85aaf69f | 604 | Iter { bit_vec: self, next_idx: 0, end_idx: self.nbits } |
1a4d82fc JJ |
605 | } |
606 | ||
d9579d0f AL |
607 | /// Moves all bits from `other` into `Self`, leaving `other` empty. |
608 | /// | |
609 | /// # Examples | |
610 | /// | |
611 | /// ``` | |
62682a34 | 612 | /// # #![feature(bitvec, append)] |
d9579d0f AL |
613 | /// use std::collections::BitVec; |
614 | /// | |
615 | /// let mut a = BitVec::from_bytes(&[0b10000000]); | |
616 | /// let mut b = BitVec::from_bytes(&[0b01100001]); | |
617 | /// | |
618 | /// a.append(&mut b); | |
619 | /// | |
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])); | |
624 | /// ``` | |
62682a34 | 625 | #[unstable(feature = "append", |
d9579d0f AL |
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; | |
629 | ||
630 | self.nbits += other.len(); | |
631 | other.nbits = 0; | |
632 | ||
633 | if b == 0 { | |
634 | self.storage.append(&mut other.storage); | |
635 | } else { | |
636 | self.storage.reserve(other.storage.len()); | |
637 | ||
638 | for block in other.storage.drain(..) { | |
639 | *(self.storage.last_mut().unwrap()) |= block << b; | |
640 | self.storage.push(block >> (u32::BITS - b)); | |
641 | } | |
642 | } | |
643 | } | |
644 | ||
645 | /// Splits the `BitVec` into two at the given bit, | |
646 | /// retaining the first half in-place and returning the second one. | |
647 | /// | |
648 | /// # Panics | |
649 | /// | |
650 | /// Panics if `at` is out of bounds. | |
651 | /// | |
652 | /// # Examples | |
653 | /// | |
654 | /// ``` | |
62682a34 | 655 | /// # #![feature(bitvec, split_off)] |
d9579d0f AL |
656 | /// use std::collections::BitVec; |
657 | /// let mut a = BitVec::new(); | |
658 | /// a.push(true); | |
659 | /// a.push(false); | |
660 | /// a.push(false); | |
661 | /// a.push(true); | |
662 | /// | |
663 | /// let b = a.split_off(2); | |
664 | /// | |
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])); | |
669 | /// ``` | |
62682a34 | 670 | #[unstable(feature = "split_off", |
d9579d0f AL |
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"); | |
674 | ||
675 | let mut other = BitVec::new(); | |
676 | ||
677 | if at == 0 { | |
678 | swap(self, &mut other); | |
679 | return other; | |
680 | } else if at == self.len() { | |
681 | return other; | |
682 | } | |
683 | ||
684 | let w = at / u32::BITS; | |
685 | let b = at % u32::BITS; | |
686 | other.nbits = self.nbits - at; | |
687 | self.nbits = at; | |
688 | if b == 0 { | |
689 | // Split at block boundary | |
690 | other.storage = self.storage.split_off(w); | |
691 | } else { | |
692 | other.storage.reserve(self.storage.len() - w); | |
693 | ||
694 | { | |
695 | let mut iter = self.storage[w..].iter(); | |
696 | let mut last = *iter.next().unwrap(); | |
697 | for &cur in iter { | |
698 | other.storage.push((last >> b) | (cur << (u32::BITS - b))); | |
699 | last = cur; | |
700 | } | |
701 | other.storage.push(last >> b); | |
702 | } | |
703 | ||
704 | self.storage.truncate(w+1); | |
705 | self.fix_last_block(); | |
706 | } | |
707 | ||
708 | other | |
709 | } | |
710 | ||
1a4d82fc JJ |
711 | /// Returns `true` if all bits are 0. |
712 | /// | |
713 | /// # Examples | |
714 | /// | |
715 | /// ``` | |
62682a34 | 716 | /// # #![feature(bitvec)] |
85aaf69f | 717 | /// use std::collections::BitVec; |
1a4d82fc | 718 | /// |
85aaf69f | 719 | /// let mut bv = BitVec::from_elem(10, false); |
1a4d82fc JJ |
720 | /// assert_eq!(bv.none(), true); |
721 | /// | |
722 | /// bv.set(3, true); | |
723 | /// assert_eq!(bv.none(), false); | |
724 | /// ``` | |
725 | pub fn none(&self) -> bool { | |
726 | self.blocks().all(|w| w == 0) | |
727 | } | |
728 | ||
729 | /// Returns `true` if any bit is 1. | |
730 | /// | |
731 | /// # Examples | |
732 | /// | |
733 | /// ``` | |
62682a34 | 734 | /// # #![feature(bitvec)] |
85aaf69f | 735 | /// use std::collections::BitVec; |
1a4d82fc | 736 | /// |
85aaf69f | 737 | /// let mut bv = BitVec::from_elem(10, false); |
1a4d82fc JJ |
738 | /// assert_eq!(bv.any(), false); |
739 | /// | |
740 | /// bv.set(3, true); | |
741 | /// assert_eq!(bv.any(), true); | |
742 | /// ``` | |
743 | #[inline] | |
744 | pub fn any(&self) -> bool { | |
745 | !self.none() | |
746 | } | |
747 | ||
748 | /// Organises the bits into bytes, such that the first bit in the | |
85aaf69f SL |
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 | |
1a4d82fc JJ |
751 | /// will be filled-in with `false`. |
752 | /// | |
753 | /// # Examples | |
754 | /// | |
755 | /// ``` | |
62682a34 | 756 | /// # #![feature(bitvec)] |
85aaf69f | 757 | /// use std::collections::BitVec; |
1a4d82fc | 758 | /// |
85aaf69f | 759 | /// let mut bv = BitVec::from_elem(3, true); |
1a4d82fc JJ |
760 | /// bv.set(1, false); |
761 | /// | |
c34b1796 | 762 | /// assert_eq!(bv.to_bytes(), [0b10100000]); |
1a4d82fc | 763 | /// |
85aaf69f | 764 | /// let mut bv = BitVec::from_elem(9, false); |
1a4d82fc JJ |
765 | /// bv.set(2, true); |
766 | /// bv.set(8, true); | |
767 | /// | |
c34b1796 | 768 | /// assert_eq!(bv.to_bytes(), [0b00100000, 0b10000000]); |
1a4d82fc JJ |
769 | /// ``` |
770 | pub fn to_bytes(&self) -> Vec<u8> { | |
85aaf69f | 771 | fn bit(bit_vec: &BitVec, byte: usize, bit: usize) -> u8 { |
1a4d82fc | 772 | let offset = byte * 8 + bit; |
85aaf69f | 773 | if offset >= bit_vec.nbits { |
1a4d82fc JJ |
774 | 0 |
775 | } else { | |
85aaf69f | 776 | (bit_vec[offset] as u8) << (7 - bit) |
1a4d82fc JJ |
777 | } |
778 | } | |
779 | ||
780 | let len = self.nbits/8 + | |
781 | if self.nbits % 8 == 0 { 0 } else { 1 }; | |
85aaf69f | 782 | (0..len).map(|i| |
1a4d82fc JJ |
783 | bit(self, i, 0) | |
784 | bit(self, i, 1) | | |
785 | bit(self, i, 2) | | |
786 | bit(self, i, 3) | | |
787 | bit(self, i, 4) | | |
788 | bit(self, i, 5) | | |
789 | bit(self, i, 6) | | |
790 | bit(self, i, 7) | |
791 | ).collect() | |
792 | } | |
793 | ||
85aaf69f SL |
794 | /// Compares a `BitVec` to a slice of `bool`s. |
795 | /// Both the `BitVec` and slice must have the same length. | |
1a4d82fc JJ |
796 | /// |
797 | /// # Panics | |
798 | /// | |
85aaf69f | 799 | /// Panics if the `BitVec` and slice are of different length. |
1a4d82fc JJ |
800 | /// |
801 | /// # Examples | |
802 | /// | |
803 | /// ``` | |
62682a34 | 804 | /// # #![feature(bitvec)] |
85aaf69f | 805 | /// use std::collections::BitVec; |
1a4d82fc | 806 | /// |
85aaf69f | 807 | /// let bv = BitVec::from_bytes(&[0b10100000]); |
1a4d82fc JJ |
808 | /// |
809 | /// assert!(bv.eq_vec(&[true, false, true, false, | |
810 | /// false, false, false, false])); | |
811 | /// ``` | |
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()) | |
815 | } | |
816 | ||
85aaf69f | 817 | /// Shortens a `BitVec`, dropping excess elements. |
1a4d82fc JJ |
818 | /// |
819 | /// If `len` is greater than the vector's current length, this has no | |
820 | /// effect. | |
821 | /// | |
822 | /// # Examples | |
823 | /// | |
824 | /// ``` | |
62682a34 | 825 | /// # #![feature(bitvec)] |
85aaf69f | 826 | /// use std::collections::BitVec; |
1a4d82fc | 827 | /// |
85aaf69f | 828 | /// let mut bv = BitVec::from_bytes(&[0b01001011]); |
1a4d82fc JJ |
829 | /// bv.truncate(2); |
830 | /// assert!(bv.eq_vec(&[false, true])); | |
831 | /// ``` | |
85aaf69f SL |
832 | #[stable(feature = "rust1", since = "1.0.0")] |
833 | pub fn truncate(&mut self, len: usize) { | |
1a4d82fc JJ |
834 | if len < self.len() { |
835 | self.nbits = len; | |
836 | // This fixes (2). | |
837 | self.storage.truncate(blocks_for_bits(len)); | |
838 | self.fix_last_block(); | |
839 | } | |
840 | } | |
841 | ||
842 | /// Reserves capacity for at least `additional` more bits to be inserted in the given | |
85aaf69f | 843 | /// `BitVec`. The collection may reserve more space to avoid frequent reallocations. |
1a4d82fc JJ |
844 | /// |
845 | /// # Panics | |
846 | /// | |
85aaf69f | 847 | /// Panics if the new capacity overflows `usize`. |
1a4d82fc JJ |
848 | /// |
849 | /// # Examples | |
850 | /// | |
851 | /// ``` | |
62682a34 | 852 | /// # #![feature(bitvec)] |
85aaf69f | 853 | /// use std::collections::BitVec; |
1a4d82fc | 854 | /// |
85aaf69f | 855 | /// let mut bv = BitVec::from_elem(3, false); |
1a4d82fc JJ |
856 | /// bv.reserve(10); |
857 | /// assert_eq!(bv.len(), 3); | |
858 | /// assert!(bv.capacity() >= 13); | |
859 | /// ``` | |
85aaf69f SL |
860 | #[stable(feature = "rust1", since = "1.0.0")] |
861 | pub fn reserve(&mut self, additional: usize) { | |
1a4d82fc JJ |
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); | |
866 | } | |
867 | } | |
868 | ||
869 | /// Reserves the minimum capacity for exactly `additional` more bits to be inserted in the | |
85aaf69f | 870 | /// given `BitVec`. Does nothing if the capacity is already sufficient. |
1a4d82fc JJ |
871 | /// |
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. | |
875 | /// | |
876 | /// # Panics | |
877 | /// | |
85aaf69f | 878 | /// Panics if the new capacity overflows `usize`. |
1a4d82fc JJ |
879 | /// |
880 | /// # Examples | |
881 | /// | |
882 | /// ``` | |
62682a34 | 883 | /// # #![feature(bitvec)] |
85aaf69f | 884 | /// use std::collections::BitVec; |
1a4d82fc | 885 | /// |
85aaf69f | 886 | /// let mut bv = BitVec::from_elem(3, false); |
1a4d82fc JJ |
887 | /// bv.reserve(10); |
888 | /// assert_eq!(bv.len(), 3); | |
889 | /// assert!(bv.capacity() >= 13); | |
890 | /// ``` | |
85aaf69f SL |
891 | #[stable(feature = "rust1", since = "1.0.0")] |
892 | pub fn reserve_exact(&mut self, additional: usize) { | |
1a4d82fc JJ |
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); | |
897 | } | |
898 | } | |
899 | ||
900 | /// Returns the capacity in bits for this bit vector. Inserting any | |
901 | /// element less than this amount will not trigger a resizing. | |
902 | /// | |
903 | /// # Examples | |
904 | /// | |
905 | /// ``` | |
62682a34 | 906 | /// # #![feature(bitvec)] |
85aaf69f | 907 | /// use std::collections::BitVec; |
1a4d82fc | 908 | /// |
85aaf69f | 909 | /// let mut bv = BitVec::new(); |
1a4d82fc JJ |
910 | /// bv.reserve(10); |
911 | /// assert!(bv.capacity() >= 10); | |
912 | /// ``` | |
913 | #[inline] | |
85aaf69f SL |
914 | #[stable(feature = "rust1", since = "1.0.0")] |
915 | pub fn capacity(&self) -> usize { | |
9346a6ac | 916 | self.storage.capacity().checked_mul(u32::BITS).unwrap_or(usize::MAX) |
1a4d82fc JJ |
917 | } |
918 | ||
85aaf69f | 919 | /// Grows the `BitVec` in-place, adding `n` copies of `value` to the `BitVec`. |
1a4d82fc JJ |
920 | /// |
921 | /// # Panics | |
922 | /// | |
85aaf69f | 923 | /// Panics if the new len overflows a `usize`. |
1a4d82fc JJ |
924 | /// |
925 | /// # Examples | |
926 | /// | |
927 | /// ``` | |
62682a34 | 928 | /// # #![feature(bitvec)] |
85aaf69f | 929 | /// use std::collections::BitVec; |
1a4d82fc | 930 | /// |
85aaf69f | 931 | /// let mut bv = BitVec::from_bytes(&[0b01001011]); |
1a4d82fc JJ |
932 | /// bv.grow(2, true); |
933 | /// assert_eq!(bv.len(), 10); | |
c34b1796 | 934 | /// assert_eq!(bv.to_bytes(), [0b01001011, 0b11000000]); |
1a4d82fc | 935 | /// ``` |
85aaf69f | 936 | pub fn grow(&mut self, n: usize, value: bool) { |
1a4d82fc JJ |
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. | |
940 | ||
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 }; | |
944 | ||
945 | // Correct the old tail word, setting or clearing formerly unused bits | |
c34b1796 | 946 | let num_cur_blocks = blocks_for_bits(self.nbits); |
9346a6ac | 947 | if self.nbits % u32::BITS > 0 { |
1a4d82fc JJ |
948 | let mask = mask_for_bits(self.nbits); |
949 | if value { | |
c34b1796 | 950 | self.storage[num_cur_blocks - 1] |= !mask; |
1a4d82fc JJ |
951 | } else { |
952 | // Extra bits are already zero by invariant. | |
953 | } | |
954 | } | |
955 | ||
956 | // Fill in words after the old tail word | |
957 | let stop_idx = cmp::min(self.storage.len(), new_nblocks); | |
c34b1796 | 958 | for idx in num_cur_blocks..stop_idx { |
1a4d82fc JJ |
959 | self.storage[idx] = full_value; |
960 | } | |
961 | ||
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)); | |
966 | } | |
967 | ||
968 | // Adjust internal bit count | |
969 | self.nbits = new_nbits; | |
970 | ||
971 | self.fix_last_block(); | |
972 | } | |
973 | ||
85aaf69f | 974 | /// Removes the last bit from the BitVec, and returns it. Returns None if the BitVec is empty. |
1a4d82fc JJ |
975 | /// |
976 | /// # Examples | |
977 | /// | |
978 | /// ``` | |
62682a34 | 979 | /// # #![feature(bitvec)] |
85aaf69f | 980 | /// use std::collections::BitVec; |
1a4d82fc | 981 | /// |
85aaf69f | 982 | /// let mut bv = BitVec::from_bytes(&[0b01001001]); |
1a4d82fc JJ |
983 | /// assert_eq!(bv.pop(), Some(true)); |
984 | /// assert_eq!(bv.pop(), Some(false)); | |
985 | /// assert_eq!(bv.len(), 6); | |
986 | /// ``` | |
85aaf69f | 987 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
988 | pub fn pop(&mut self) -> Option<bool> { |
989 | if self.is_empty() { | |
990 | None | |
991 | } else { | |
992 | let i = self.nbits - 1; | |
993 | let ret = self[i]; | |
994 | // (3) | |
995 | self.set(i, false); | |
996 | self.nbits = i; | |
9346a6ac | 997 | if self.nbits % u32::BITS == 0 { |
1a4d82fc JJ |
998 | // (2) |
999 | self.storage.pop(); | |
1000 | } | |
1001 | Some(ret) | |
1002 | } | |
1003 | } | |
1004 | ||
1005 | /// Pushes a `bool` onto the end. | |
1006 | /// | |
1007 | /// # Examples | |
1008 | /// | |
1009 | /// ``` | |
62682a34 | 1010 | /// # #![feature(bitvec)] |
85aaf69f | 1011 | /// use std::collections::BitVec; |
1a4d82fc | 1012 | /// |
85aaf69f | 1013 | /// let mut bv = BitVec::new(); |
1a4d82fc JJ |
1014 | /// bv.push(true); |
1015 | /// bv.push(false); | |
1016 | /// assert!(bv.eq_vec(&[true, false])); | |
1017 | /// ``` | |
85aaf69f | 1018 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1019 | pub fn push(&mut self, elem: bool) { |
9346a6ac | 1020 | if self.nbits % u32::BITS == 0 { |
1a4d82fc JJ |
1021 | self.storage.push(0); |
1022 | } | |
1023 | let insert_pos = self.nbits; | |
1024 | self.nbits = self.nbits.checked_add(1).expect("Capacity overflow"); | |
1025 | self.set(insert_pos, elem); | |
1026 | } | |
1027 | ||
9346a6ac | 1028 | /// Returns the total number of bits in this vector |
1a4d82fc | 1029 | #[inline] |
85aaf69f SL |
1030 | #[stable(feature = "rust1", since = "1.0.0")] |
1031 | pub fn len(&self) -> usize { self.nbits } | |
1a4d82fc JJ |
1032 | |
1033 | /// Returns true if there are no bits in this vector | |
1034 | #[inline] | |
85aaf69f | 1035 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1036 | pub fn is_empty(&self) -> bool { self.len() == 0 } |
1037 | ||
1038 | /// Clears all bits in this vector. | |
1039 | #[inline] | |
85aaf69f | 1040 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1041 | pub fn clear(&mut self) { |
c34b1796 | 1042 | for w in &mut self.storage { *w = 0; } |
1a4d82fc JJ |
1043 | } |
1044 | } | |
1045 | ||
85aaf69f SL |
1046 | #[stable(feature = "rust1", since = "1.0.0")] |
1047 | impl Default for BitVec { | |
1a4d82fc | 1048 | #[inline] |
85aaf69f | 1049 | fn default() -> BitVec { BitVec::new() } |
1a4d82fc JJ |
1050 | } |
1051 | ||
85aaf69f SL |
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(); | |
1056 | ret.extend(iter); | |
1a4d82fc JJ |
1057 | ret |
1058 | } | |
1059 | } | |
1060 | ||
85aaf69f SL |
1061 | #[stable(feature = "rust1", since = "1.0.0")] |
1062 | impl Extend<bool> for BitVec { | |
1a4d82fc | 1063 | #[inline] |
85aaf69f SL |
1064 | fn extend<I: IntoIterator<Item=bool>>(&mut self, iterable: I) { |
1065 | let iterator = iterable.into_iter(); | |
1a4d82fc JJ |
1066 | let (min, _) = iterator.size_hint(); |
1067 | self.reserve(min); | |
1068 | for element in iterator { | |
1069 | self.push(element) | |
1070 | } | |
1071 | } | |
1072 | } | |
1073 | ||
62682a34 SL |
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()); | |
1078 | } | |
1079 | } | |
1080 | ||
85aaf69f SL |
1081 | #[stable(feature = "rust1", since = "1.0.0")] |
1082 | impl Clone for BitVec { | |
1a4d82fc | 1083 | #[inline] |
85aaf69f SL |
1084 | fn clone(&self) -> BitVec { |
1085 | BitVec { storage: self.storage.clone(), nbits: self.nbits } | |
1a4d82fc JJ |
1086 | } |
1087 | ||
1088 | #[inline] | |
85aaf69f | 1089 | fn clone_from(&mut self, source: &BitVec) { |
1a4d82fc JJ |
1090 | self.nbits = source.nbits; |
1091 | self.storage.clone_from(&source.storage); | |
1092 | } | |
1093 | } | |
1094 | ||
85aaf69f SL |
1095 | #[stable(feature = "rust1", since = "1.0.0")] |
1096 | impl PartialOrd for BitVec { | |
1a4d82fc | 1097 | #[inline] |
85aaf69f | 1098 | fn partial_cmp(&self, other: &BitVec) -> Option<Ordering> { |
1a4d82fc JJ |
1099 | iter::order::partial_cmp(self.iter(), other.iter()) |
1100 | } | |
1101 | } | |
1102 | ||
85aaf69f SL |
1103 | #[stable(feature = "rust1", since = "1.0.0")] |
1104 | impl Ord for BitVec { | |
1a4d82fc | 1105 | #[inline] |
85aaf69f | 1106 | fn cmp(&self, other: &BitVec) -> Ordering { |
1a4d82fc JJ |
1107 | iter::order::cmp(self.iter(), other.iter()) |
1108 | } | |
1109 | } | |
1110 | ||
85aaf69f SL |
1111 | #[stable(feature = "rust1", since = "1.0.0")] |
1112 | impl fmt::Debug for BitVec { | |
1a4d82fc | 1113 | fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { |
85aaf69f | 1114 | for bit in self { |
c34b1796 | 1115 | try!(write!(fmt, "{}", if bit { 1 } else { 0 })); |
1a4d82fc JJ |
1116 | } |
1117 | Ok(()) | |
1118 | } | |
1119 | } | |
1120 | ||
85aaf69f | 1121 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f SL |
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() { | |
1126 | elem.hash(state); | |
1127 | } | |
1128 | } | |
1129 | } | |
1a4d82fc | 1130 | |
85aaf69f SL |
1131 | #[stable(feature = "rust1", since = "1.0.0")] |
1132 | impl cmp::PartialEq for BitVec { | |
1a4d82fc | 1133 | #[inline] |
85aaf69f | 1134 | fn eq(&self, other: &BitVec) -> bool { |
1a4d82fc JJ |
1135 | if self.nbits != other.nbits { |
1136 | return false; | |
1137 | } | |
1138 | self.blocks().zip(other.blocks()).all(|(w1, w2)| w1 == w2) | |
1139 | } | |
1140 | } | |
1141 | ||
85aaf69f SL |
1142 | #[stable(feature = "rust1", since = "1.0.0")] |
1143 | impl cmp::Eq for BitVec {} | |
1a4d82fc | 1144 | |
85aaf69f SL |
1145 | /// An iterator for `BitVec`. |
1146 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc JJ |
1147 | #[derive(Clone)] |
1148 | pub struct Iter<'a> { | |
85aaf69f SL |
1149 | bit_vec: &'a BitVec, |
1150 | next_idx: usize, | |
1151 | end_idx: usize, | |
1a4d82fc JJ |
1152 | } |
1153 | ||
85aaf69f | 1154 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1155 | impl<'a> Iterator for Iter<'a> { |
1156 | type Item = bool; | |
1157 | ||
1158 | #[inline] | |
1159 | fn next(&mut self) -> Option<bool> { | |
1160 | if self.next_idx != self.end_idx { | |
1161 | let idx = self.next_idx; | |
1162 | self.next_idx += 1; | |
85aaf69f | 1163 | Some(self.bit_vec[idx]) |
1a4d82fc JJ |
1164 | } else { |
1165 | None | |
1166 | } | |
1167 | } | |
1168 | ||
85aaf69f | 1169 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
1170 | let rem = self.end_idx - self.next_idx; |
1171 | (rem, Some(rem)) | |
1172 | } | |
1173 | } | |
1174 | ||
85aaf69f | 1175 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1176 | impl<'a> DoubleEndedIterator for Iter<'a> { |
1177 | #[inline] | |
1178 | fn next_back(&mut self) -> Option<bool> { | |
1179 | if self.next_idx != self.end_idx { | |
1180 | self.end_idx -= 1; | |
85aaf69f | 1181 | Some(self.bit_vec[self.end_idx]) |
1a4d82fc JJ |
1182 | } else { |
1183 | None | |
1184 | } | |
1185 | } | |
1186 | } | |
1187 | ||
85aaf69f | 1188 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1189 | impl<'a> ExactSizeIterator for Iter<'a> {} |
1190 | ||
85aaf69f | 1191 | #[stable(feature = "rust1", since = "1.0.0")] |
62682a34 | 1192 | #[allow(deprecated)] |
1a4d82fc JJ |
1193 | impl<'a> RandomAccessIterator for Iter<'a> { |
1194 | #[inline] | |
85aaf69f | 1195 | fn indexable(&self) -> usize { |
1a4d82fc JJ |
1196 | self.end_idx - self.next_idx |
1197 | } | |
1198 | ||
1199 | #[inline] | |
85aaf69f | 1200 | fn idx(&mut self, index: usize) -> Option<bool> { |
1a4d82fc JJ |
1201 | if index >= self.indexable() { |
1202 | None | |
1203 | } else { | |
85aaf69f | 1204 | Some(self.bit_vec[index]) |
1a4d82fc JJ |
1205 | } |
1206 | } | |
1207 | } | |
1208 | ||
85aaf69f SL |
1209 | #[stable(feature = "rust1", since = "1.0.0")] |
1210 | impl<'a> IntoIterator for &'a BitVec { | |
1211 | type Item = bool; | |
1212 | type IntoIter = Iter<'a>; | |
1213 | ||
1214 | fn into_iter(self) -> Iter<'a> { | |
1215 | self.iter() | |
1216 | } | |
1217 | } | |
1218 | ||
1a4d82fc JJ |
1219 | /// An implementation of a set using a bit vector as an underlying |
1220 | /// representation for holding unsigned numerical elements. | |
1221 | /// | |
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 | |
85aaf69f | 1224 | /// as a `usize`. |
1a4d82fc JJ |
1225 | /// |
1226 | /// # Examples | |
1227 | /// | |
1228 | /// ``` | |
62682a34 | 1229 | /// # #![feature(bitvec, bitset)] |
85aaf69f | 1230 | /// use std::collections::{BitSet, BitVec}; |
1a4d82fc JJ |
1231 | /// |
1232 | /// // It's a regular set | |
85aaf69f | 1233 | /// let mut s = BitSet::new(); |
1a4d82fc JJ |
1234 | /// s.insert(0); |
1235 | /// s.insert(3); | |
1236 | /// s.insert(7); | |
1237 | /// | |
1238 | /// s.remove(&7); | |
1239 | /// | |
1240 | /// if !s.contains(&7) { | |
1241 | /// println!("There is no 7"); | |
1242 | /// } | |
1243 | /// | |
85aaf69f SL |
1244 | /// // Can initialize from a `BitVec` |
1245 | /// let other = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11010000])); | |
1a4d82fc JJ |
1246 | /// |
1247 | /// s.union_with(&other); | |
1248 | /// | |
1249 | /// // Print 0, 1, 3 in some order | |
62682a34 | 1250 | /// for x in &s { |
1a4d82fc JJ |
1251 | /// println!("{}", x); |
1252 | /// } | |
1253 | /// | |
85aaf69f SL |
1254 | /// // Can convert back to a `BitVec` |
1255 | /// let bv: BitVec = s.into_bit_vec(); | |
1a4d82fc JJ |
1256 | /// assert!(bv[3]); |
1257 | /// ``` | |
1258 | #[derive(Clone)] | |
62682a34 | 1259 | #[unstable(feature = "bitset", reason = "RFC 509")] |
85aaf69f SL |
1260 | pub struct BitSet { |
1261 | bit_vec: BitVec, | |
1a4d82fc JJ |
1262 | } |
1263 | ||
85aaf69f SL |
1264 | #[stable(feature = "rust1", since = "1.0.0")] |
1265 | impl Default for BitSet { | |
1a4d82fc | 1266 | #[inline] |
85aaf69f | 1267 | fn default() -> BitSet { BitSet::new() } |
1a4d82fc JJ |
1268 | } |
1269 | ||
85aaf69f SL |
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(); | |
1274 | ret.extend(iter); | |
1a4d82fc JJ |
1275 | ret |
1276 | } | |
1277 | } | |
1278 | ||
85aaf69f SL |
1279 | #[stable(feature = "rust1", since = "1.0.0")] |
1280 | impl Extend<usize> for BitSet { | |
1a4d82fc | 1281 | #[inline] |
85aaf69f SL |
1282 | fn extend<I: IntoIterator<Item=usize>>(&mut self, iter: I) { |
1283 | for i in iter { | |
1a4d82fc JJ |
1284 | self.insert(i); |
1285 | } | |
1286 | } | |
1287 | } | |
1288 | ||
62682a34 SL |
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()); | |
1293 | } | |
1294 | } | |
1295 | ||
85aaf69f SL |
1296 | #[stable(feature = "rust1", since = "1.0.0")] |
1297 | impl PartialOrd for BitSet { | |
1a4d82fc | 1298 | #[inline] |
85aaf69f | 1299 | fn partial_cmp(&self, other: &BitSet) -> Option<Ordering> { |
1a4d82fc JJ |
1300 | let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref()); |
1301 | iter::order::partial_cmp(a_iter, b_iter) | |
1302 | } | |
1303 | } | |
1304 | ||
85aaf69f SL |
1305 | #[stable(feature = "rust1", since = "1.0.0")] |
1306 | impl Ord for BitSet { | |
1a4d82fc | 1307 | #[inline] |
85aaf69f | 1308 | fn cmp(&self, other: &BitSet) -> Ordering { |
1a4d82fc JJ |
1309 | let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref()); |
1310 | iter::order::cmp(a_iter, b_iter) | |
1311 | } | |
1312 | } | |
1313 | ||
85aaf69f SL |
1314 | #[stable(feature = "rust1", since = "1.0.0")] |
1315 | impl cmp::PartialEq for BitSet { | |
1a4d82fc | 1316 | #[inline] |
85aaf69f | 1317 | fn eq(&self, other: &BitSet) -> bool { |
1a4d82fc JJ |
1318 | let (a_iter, b_iter) = match_words(self.get_ref(), other.get_ref()); |
1319 | iter::order::eq(a_iter, b_iter) | |
1320 | } | |
1321 | } | |
1322 | ||
85aaf69f SL |
1323 | #[stable(feature = "rust1", since = "1.0.0")] |
1324 | impl cmp::Eq for BitSet {} | |
1a4d82fc | 1325 | |
62682a34 | 1326 | #[unstable(feature = "bitset", reason = "RFC 509")] |
85aaf69f SL |
1327 | impl BitSet { |
1328 | /// Creates a new empty `BitSet`. | |
1a4d82fc JJ |
1329 | /// |
1330 | /// # Examples | |
1331 | /// | |
1332 | /// ``` | |
62682a34 | 1333 | /// # #![feature(bitset)] |
85aaf69f | 1334 | /// use std::collections::BitSet; |
1a4d82fc | 1335 | /// |
85aaf69f | 1336 | /// let mut s = BitSet::new(); |
1a4d82fc JJ |
1337 | /// ``` |
1338 | #[inline] | |
85aaf69f SL |
1339 | #[stable(feature = "rust1", since = "1.0.0")] |
1340 | pub fn new() -> BitSet { | |
1341 | BitSet { bit_vec: BitVec::new() } | |
1a4d82fc JJ |
1342 | } |
1343 | ||
85aaf69f | 1344 | /// Creates a new `BitSet` with initially no contents, able to |
1a4d82fc JJ |
1345 | /// hold `nbits` elements without resizing. |
1346 | /// | |
1347 | /// # Examples | |
1348 | /// | |
1349 | /// ``` | |
62682a34 | 1350 | /// # #![feature(bitset)] |
85aaf69f | 1351 | /// use std::collections::BitSet; |
1a4d82fc | 1352 | /// |
85aaf69f | 1353 | /// let mut s = BitSet::with_capacity(100); |
1a4d82fc JJ |
1354 | /// assert!(s.capacity() >= 100); |
1355 | /// ``` | |
1356 | #[inline] | |
85aaf69f SL |
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) | |
1a4d82fc JJ |
1361 | } |
1362 | ||
85aaf69f | 1363 | /// Creates a new `BitSet` from the given bit vector. |
1a4d82fc JJ |
1364 | /// |
1365 | /// # Examples | |
1366 | /// | |
1367 | /// ``` | |
62682a34 | 1368 | /// # #![feature(bitset, bitvec)] |
85aaf69f | 1369 | /// use std::collections::{BitVec, BitSet}; |
1a4d82fc | 1370 | /// |
85aaf69f SL |
1371 | /// let bv = BitVec::from_bytes(&[0b01100000]); |
1372 | /// let s = BitSet::from_bit_vec(bv); | |
1a4d82fc JJ |
1373 | /// |
1374 | /// // Print 1, 2 in arbitrary order | |
62682a34 | 1375 | /// for x in &s { |
1a4d82fc JJ |
1376 | /// println!("{}", x); |
1377 | /// } | |
1378 | /// ``` | |
1379 | #[inline] | |
85aaf69f SL |
1380 | pub fn from_bit_vec(bit_vec: BitVec) -> BitSet { |
1381 | BitSet { bit_vec: bit_vec } | |
1382 | } | |
1383 | ||
1a4d82fc JJ |
1384 | /// Returns the capacity in bits for this bit vector. Inserting any |
1385 | /// element less than this amount will not trigger a resizing. | |
1386 | /// | |
1387 | /// # Examples | |
1388 | /// | |
1389 | /// ``` | |
62682a34 | 1390 | /// # #![feature(bitset)] |
85aaf69f | 1391 | /// use std::collections::BitSet; |
1a4d82fc | 1392 | /// |
85aaf69f | 1393 | /// let mut s = BitSet::with_capacity(100); |
1a4d82fc JJ |
1394 | /// assert!(s.capacity() >= 100); |
1395 | /// ``` | |
1396 | #[inline] | |
85aaf69f SL |
1397 | #[stable(feature = "rust1", since = "1.0.0")] |
1398 | pub fn capacity(&self) -> usize { | |
1399 | self.bit_vec.capacity() | |
1a4d82fc JJ |
1400 | } |
1401 | ||
62682a34 SL |
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`. | |
1a4d82fc JJ |
1405 | /// |
1406 | /// The collection may reserve more space to avoid frequent reallocations. | |
1407 | /// | |
1408 | /// | |
1409 | /// # Examples | |
1410 | /// | |
1411 | /// ``` | |
62682a34 | 1412 | /// # #![feature(bitset)] |
85aaf69f | 1413 | /// use std::collections::BitSet; |
1a4d82fc | 1414 | /// |
85aaf69f | 1415 | /// let mut s = BitSet::new(); |
1a4d82fc JJ |
1416 | /// s.reserve_len(10); |
1417 | /// assert!(s.capacity() >= 10); | |
1418 | /// ``` | |
85aaf69f SL |
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(); | |
1a4d82fc | 1422 | if len >= cur_len { |
85aaf69f | 1423 | self.bit_vec.reserve(len - cur_len); |
1a4d82fc JJ |
1424 | } |
1425 | } | |
1426 | ||
62682a34 SL |
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`. | |
1a4d82fc | 1430 | /// |
62682a34 SL |
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. | |
1a4d82fc JJ |
1434 | /// |
1435 | /// | |
1436 | /// # Examples | |
1437 | /// | |
1438 | /// ``` | |
62682a34 | 1439 | /// # #![feature(bitset)] |
85aaf69f | 1440 | /// use std::collections::BitSet; |
1a4d82fc | 1441 | /// |
85aaf69f | 1442 | /// let mut s = BitSet::new(); |
1a4d82fc JJ |
1443 | /// s.reserve_len_exact(10); |
1444 | /// assert!(s.capacity() >= 10); | |
1445 | /// ``` | |
85aaf69f SL |
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(); | |
1a4d82fc | 1449 | if len >= cur_len { |
85aaf69f | 1450 | self.bit_vec.reserve_exact(len - cur_len); |
1a4d82fc JJ |
1451 | } |
1452 | } | |
1453 | ||
1454 | ||
1455 | /// Consumes this set to return the underlying bit vector. | |
1456 | /// | |
1457 | /// # Examples | |
1458 | /// | |
1459 | /// ``` | |
62682a34 | 1460 | /// # #![feature(bitset)] |
85aaf69f | 1461 | /// use std::collections::BitSet; |
1a4d82fc | 1462 | /// |
85aaf69f | 1463 | /// let mut s = BitSet::new(); |
1a4d82fc JJ |
1464 | /// s.insert(0); |
1465 | /// s.insert(3); | |
1466 | /// | |
85aaf69f | 1467 | /// let bv = s.into_bit_vec(); |
1a4d82fc JJ |
1468 | /// assert!(bv[0]); |
1469 | /// assert!(bv[3]); | |
1470 | /// ``` | |
1471 | #[inline] | |
85aaf69f SL |
1472 | pub fn into_bit_vec(self) -> BitVec { |
1473 | self.bit_vec | |
1a4d82fc JJ |
1474 | } |
1475 | ||
1476 | /// Returns a reference to the underlying bit vector. | |
1477 | /// | |
1478 | /// # Examples | |
1479 | /// | |
1480 | /// ``` | |
62682a34 | 1481 | /// # #![feature(bitset)] |
85aaf69f | 1482 | /// use std::collections::BitSet; |
1a4d82fc | 1483 | /// |
85aaf69f | 1484 | /// let mut s = BitSet::new(); |
1a4d82fc JJ |
1485 | /// s.insert(0); |
1486 | /// | |
1487 | /// let bv = s.get_ref(); | |
1488 | /// assert_eq!(bv[0], true); | |
1489 | /// ``` | |
1490 | #[inline] | |
85aaf69f SL |
1491 | pub fn get_ref(&self) -> &BitVec { |
1492 | &self.bit_vec | |
1a4d82fc JJ |
1493 | } |
1494 | ||
1495 | #[inline] | |
85aaf69f SL |
1496 | fn other_op<F>(&mut self, other: &BitSet, mut f: F) where F: FnMut(u32, u32) -> u32 { |
1497 | // Unwrap BitVecs | |
1498 | let self_bit_vec = &mut self.bit_vec; | |
1499 | let other_bit_vec = &other.bit_vec; | |
1a4d82fc | 1500 | |
85aaf69f SL |
1501 | let self_len = self_bit_vec.len(); |
1502 | let other_len = other_bit_vec.len(); | |
1a4d82fc JJ |
1503 | |
1504 | // Expand the vector if necessary | |
1505 | if self_len < other_len { | |
85aaf69f | 1506 | self_bit_vec.grow(other_len - self_len, false); |
1a4d82fc JJ |
1507 | } |
1508 | ||
1509 | // virtually pad other with 0's for equal lengths | |
85aaf69f SL |
1510 | let other_words = { |
1511 | let (_, result) = match_words(self_bit_vec, other_bit_vec); | |
1a4d82fc JJ |
1512 | result |
1513 | }; | |
1514 | ||
1515 | // Apply values found in other | |
1516 | for (i, w) in other_words { | |
85aaf69f | 1517 | let old = self_bit_vec.storage[i]; |
1a4d82fc | 1518 | let new = f(old, w); |
85aaf69f | 1519 | self_bit_vec.storage[i] = new; |
1a4d82fc JJ |
1520 | } |
1521 | } | |
1522 | ||
1523 | /// Truncates the underlying vector to the least length required. | |
1524 | /// | |
1525 | /// # Examples | |
1526 | /// | |
1527 | /// ``` | |
62682a34 | 1528 | /// # #![feature(bitset)] |
85aaf69f | 1529 | /// use std::collections::BitSet; |
1a4d82fc | 1530 | /// |
85aaf69f | 1531 | /// let mut s = BitSet::new(); |
1a4d82fc JJ |
1532 | /// s.insert(32183231); |
1533 | /// s.remove(&32183231); | |
1534 | /// | |
1535 | /// // Internal storage will probably be bigger than necessary | |
1536 | /// println!("old capacity: {}", s.capacity()); | |
1537 | /// | |
1538 | /// // Now should be smaller | |
1539 | /// s.shrink_to_fit(); | |
1540 | /// println!("new capacity: {}", s.capacity()); | |
1541 | /// ``` | |
1542 | #[inline] | |
85aaf69f | 1543 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1544 | pub fn shrink_to_fit(&mut self) { |
85aaf69f | 1545 | let bit_vec = &mut self.bit_vec; |
1a4d82fc | 1546 | // Obtain original length |
85aaf69f | 1547 | let old_len = bit_vec.storage.len(); |
1a4d82fc | 1548 | // Obtain coarse trailing zero length |
85aaf69f | 1549 | let n = bit_vec.storage.iter().rev().take_while(|&&n| n == 0).count(); |
1a4d82fc JJ |
1550 | // Truncate |
1551 | let trunc_len = cmp::max(old_len - n, 1); | |
85aaf69f | 1552 | bit_vec.storage.truncate(trunc_len); |
9346a6ac | 1553 | bit_vec.nbits = trunc_len * u32::BITS; |
1a4d82fc JJ |
1554 | } |
1555 | ||
bd371182 | 1556 | /// Iterator over each usize stored in the `BitSet`. |
1a4d82fc JJ |
1557 | /// |
1558 | /// # Examples | |
1559 | /// | |
1560 | /// ``` | |
62682a34 | 1561 | /// # #![feature(bitset, bitvec)] |
85aaf69f | 1562 | /// use std::collections::{BitVec, BitSet}; |
1a4d82fc | 1563 | /// |
85aaf69f | 1564 | /// let s = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01001010])); |
1a4d82fc JJ |
1565 | /// |
1566 | /// // Print 1, 4, 6 in arbitrary order | |
1567 | /// for x in s.iter() { | |
1568 | /// println!("{}", x); | |
1569 | /// } | |
1570 | /// ``` | |
1571 | #[inline] | |
85aaf69f SL |
1572 | #[stable(feature = "rust1", since = "1.0.0")] |
1573 | pub fn iter(&self) -> bit_set::Iter { | |
62682a34 | 1574 | SetIter(BlockIter::from_blocks(self.bit_vec.blocks())) |
1a4d82fc JJ |
1575 | } |
1576 | ||
bd371182 | 1577 | /// Iterator over each usize stored in `self` union `other`. |
1a4d82fc JJ |
1578 | /// See [union_with](#method.union_with) for an efficient in-place version. |
1579 | /// | |
1580 | /// # Examples | |
1581 | /// | |
1582 | /// ``` | |
62682a34 | 1583 | /// # #![feature(bitset, bitvec)] |
85aaf69f | 1584 | /// use std::collections::{BitVec, BitSet}; |
1a4d82fc | 1585 | /// |
85aaf69f SL |
1586 | /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000])); |
1587 | /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000])); | |
1a4d82fc JJ |
1588 | /// |
1589 | /// // Print 0, 1, 2, 4 in arbitrary order | |
1590 | /// for x in a.union(&b) { | |
1591 | /// println!("{}", x); | |
1592 | /// } | |
1593 | /// ``` | |
1594 | #[inline] | |
85aaf69f SL |
1595 | #[stable(feature = "rust1", since = "1.0.0")] |
1596 | pub fn union<'a>(&'a self, other: &'a BitSet) -> Union<'a> { | |
1a4d82fc JJ |
1597 | fn or(w1: u32, w2: u32) -> u32 { w1 | w2 } |
1598 | ||
62682a34 SL |
1599 | Union(BlockIter::from_blocks(TwoBitPositions { |
1600 | set: self.bit_vec.blocks(), | |
1601 | other: other.bit_vec.blocks(), | |
1a4d82fc | 1602 | merge: or, |
62682a34 | 1603 | })) |
1a4d82fc JJ |
1604 | } |
1605 | ||
85aaf69f | 1606 | /// Iterator over each usize stored in `self` intersect `other`. |
62682a34 SL |
1607 | /// See [intersect_with](#method.intersect_with) for an efficient in-place |
1608 | /// version. | |
1a4d82fc JJ |
1609 | /// |
1610 | /// # Examples | |
1611 | /// | |
1612 | /// ``` | |
62682a34 | 1613 | /// # #![feature(bitset, bitvec)] |
85aaf69f | 1614 | /// use std::collections::{BitVec, BitSet}; |
1a4d82fc | 1615 | /// |
85aaf69f SL |
1616 | /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000])); |
1617 | /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000])); | |
1a4d82fc JJ |
1618 | /// |
1619 | /// // Print 2 | |
1620 | /// for x in a.intersection(&b) { | |
1621 | /// println!("{}", x); | |
1622 | /// } | |
1623 | /// ``` | |
1624 | #[inline] | |
85aaf69f SL |
1625 | #[stable(feature = "rust1", since = "1.0.0")] |
1626 | pub fn intersection<'a>(&'a self, other: &'a BitSet) -> Intersection<'a> { | |
1a4d82fc | 1627 | fn bitand(w1: u32, w2: u32) -> u32 { w1 & w2 } |
85aaf69f | 1628 | let min = cmp::min(self.bit_vec.len(), other.bit_vec.len()); |
62682a34 SL |
1629 | |
1630 | Intersection(BlockIter::from_blocks(TwoBitPositions { | |
1631 | set: self.bit_vec.blocks(), | |
1632 | other: other.bit_vec.blocks(), | |
1a4d82fc | 1633 | merge: bitand, |
62682a34 | 1634 | }).take(min)) |
1a4d82fc JJ |
1635 | } |
1636 | ||
85aaf69f | 1637 | /// Iterator over each usize stored in the `self` setminus `other`. |
62682a34 SL |
1638 | /// See [difference_with](#method.difference_with) for an efficient in-place |
1639 | /// version. | |
1a4d82fc JJ |
1640 | /// |
1641 | /// # Examples | |
1642 | /// | |
1643 | /// ``` | |
62682a34 | 1644 | /// # #![feature(bitset, bitvec)] |
85aaf69f | 1645 | /// use std::collections::{BitSet, BitVec}; |
1a4d82fc | 1646 | /// |
85aaf69f SL |
1647 | /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000])); |
1648 | /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000])); | |
1a4d82fc JJ |
1649 | /// |
1650 | /// // Print 1, 4 in arbitrary order | |
1651 | /// for x in a.difference(&b) { | |
1652 | /// println!("{}", x); | |
1653 | /// } | |
1654 | /// | |
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); | |
1660 | /// } | |
1661 | /// ``` | |
1662 | #[inline] | |
85aaf69f SL |
1663 | #[stable(feature = "rust1", since = "1.0.0")] |
1664 | pub fn difference<'a>(&'a self, other: &'a BitSet) -> Difference<'a> { | |
1a4d82fc JJ |
1665 | fn diff(w1: u32, w2: u32) -> u32 { w1 & !w2 } |
1666 | ||
62682a34 SL |
1667 | Difference(BlockIter::from_blocks(TwoBitPositions { |
1668 | set: self.bit_vec.blocks(), | |
1669 | other: other.bit_vec.blocks(), | |
1a4d82fc | 1670 | merge: diff, |
62682a34 | 1671 | })) |
1a4d82fc JJ |
1672 | } |
1673 | ||
62682a34 SL |
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. | |
1a4d82fc JJ |
1678 | /// |
1679 | /// # Examples | |
1680 | /// | |
1681 | /// ``` | |
62682a34 | 1682 | /// # #![feature(bitset, bitvec)] |
85aaf69f | 1683 | /// use std::collections::{BitSet, BitVec}; |
1a4d82fc | 1684 | /// |
85aaf69f SL |
1685 | /// let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000])); |
1686 | /// let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000])); | |
1a4d82fc JJ |
1687 | /// |
1688 | /// // Print 0, 1, 4 in arbitrary order | |
1689 | /// for x in a.symmetric_difference(&b) { | |
1690 | /// println!("{}", x); | |
1691 | /// } | |
1692 | /// ``` | |
1693 | #[inline] | |
85aaf69f SL |
1694 | #[stable(feature = "rust1", since = "1.0.0")] |
1695 | pub fn symmetric_difference<'a>(&'a self, other: &'a BitSet) -> SymmetricDifference<'a> { | |
1a4d82fc JJ |
1696 | fn bitxor(w1: u32, w2: u32) -> u32 { w1 ^ w2 } |
1697 | ||
62682a34 SL |
1698 | SymmetricDifference(BlockIter::from_blocks(TwoBitPositions { |
1699 | set: self.bit_vec.blocks(), | |
1700 | other: other.bit_vec.blocks(), | |
1a4d82fc | 1701 | merge: bitxor, |
62682a34 | 1702 | })) |
1a4d82fc JJ |
1703 | } |
1704 | ||
1705 | /// Unions in-place with the specified other bit vector. | |
1706 | /// | |
1707 | /// # Examples | |
1708 | /// | |
1709 | /// ``` | |
62682a34 | 1710 | /// # #![feature(bitset, bitvec)] |
85aaf69f | 1711 | /// use std::collections::{BitSet, BitVec}; |
1a4d82fc JJ |
1712 | /// |
1713 | /// let a = 0b01101000; | |
1714 | /// let b = 0b10100000; | |
1715 | /// let res = 0b11101000; | |
1716 | /// | |
85aaf69f SL |
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])); | |
1a4d82fc JJ |
1720 | /// |
1721 | /// a.union_with(&b); | |
1722 | /// assert_eq!(a, res); | |
1723 | /// ``` | |
1724 | #[inline] | |
85aaf69f | 1725 | pub fn union_with(&mut self, other: &BitSet) { |
1a4d82fc JJ |
1726 | self.other_op(other, |w1, w2| w1 | w2); |
1727 | } | |
1728 | ||
1729 | /// Intersects in-place with the specified other bit vector. | |
1730 | /// | |
1731 | /// # Examples | |
1732 | /// | |
1733 | /// ``` | |
62682a34 | 1734 | /// # #![feature(bitset, bitvec)] |
85aaf69f | 1735 | /// use std::collections::{BitSet, BitVec}; |
1a4d82fc JJ |
1736 | /// |
1737 | /// let a = 0b01101000; | |
1738 | /// let b = 0b10100000; | |
1739 | /// let res = 0b00100000; | |
1740 | /// | |
85aaf69f SL |
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])); | |
1a4d82fc JJ |
1744 | /// |
1745 | /// a.intersect_with(&b); | |
1746 | /// assert_eq!(a, res); | |
1747 | /// ``` | |
1748 | #[inline] | |
85aaf69f | 1749 | pub fn intersect_with(&mut self, other: &BitSet) { |
1a4d82fc JJ |
1750 | self.other_op(other, |w1, w2| w1 & w2); |
1751 | } | |
1752 | ||
1753 | /// Makes this bit vector the difference with the specified other bit vector | |
1754 | /// in-place. | |
1755 | /// | |
1756 | /// # Examples | |
1757 | /// | |
1758 | /// ``` | |
62682a34 | 1759 | /// # #![feature(bitset, bitvec)] |
85aaf69f | 1760 | /// use std::collections::{BitSet, BitVec}; |
1a4d82fc JJ |
1761 | /// |
1762 | /// let a = 0b01101000; | |
1763 | /// let b = 0b10100000; | |
1764 | /// let a_b = 0b01001000; // a - b | |
1765 | /// let b_a = 0b10000000; // b - a | |
1766 | /// | |
85aaf69f SL |
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])); | |
1a4d82fc JJ |
1771 | /// |
1772 | /// bva.difference_with(&bvb); | |
1773 | /// assert_eq!(bva, bva_b); | |
1774 | /// | |
85aaf69f SL |
1775 | /// let bva = BitSet::from_bit_vec(BitVec::from_bytes(&[a])); |
1776 | /// let mut bvb = BitSet::from_bit_vec(BitVec::from_bytes(&[b])); | |
1a4d82fc JJ |
1777 | /// |
1778 | /// bvb.difference_with(&bva); | |
1779 | /// assert_eq!(bvb, bvb_a); | |
1780 | /// ``` | |
1781 | #[inline] | |
85aaf69f | 1782 | pub fn difference_with(&mut self, other: &BitSet) { |
1a4d82fc JJ |
1783 | self.other_op(other, |w1, w2| w1 & !w2); |
1784 | } | |
1785 | ||
1786 | /// Makes this bit vector the symmetric difference with the specified other | |
1787 | /// bit vector in-place. | |
1788 | /// | |
1789 | /// # Examples | |
1790 | /// | |
1791 | /// ``` | |
62682a34 | 1792 | /// # #![feature(bitset, bitvec)] |
85aaf69f | 1793 | /// use std::collections::{BitSet, BitVec}; |
1a4d82fc JJ |
1794 | /// |
1795 | /// let a = 0b01101000; | |
1796 | /// let b = 0b10100000; | |
1797 | /// let res = 0b11001000; | |
1798 | /// | |
85aaf69f SL |
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])); | |
1a4d82fc JJ |
1802 | /// |
1803 | /// a.symmetric_difference_with(&b); | |
1804 | /// assert_eq!(a, res); | |
1805 | /// ``` | |
1806 | #[inline] | |
85aaf69f | 1807 | pub fn symmetric_difference_with(&mut self, other: &BitSet) { |
1a4d82fc JJ |
1808 | self.other_op(other, |w1, w2| w1 ^ w2); |
1809 | } | |
1810 | ||
d9579d0f AL |
1811 | /// Moves all elements from `other` into `Self`, leaving `other` empty. |
1812 | /// | |
1813 | /// # Examples | |
1814 | /// | |
1815 | /// ``` | |
62682a34 | 1816 | /// # #![feature(bitset, bitvec, append)] |
d9579d0f AL |
1817 | /// use std::collections::{BitVec, BitSet}; |
1818 | /// | |
1819 | /// let mut a = BitSet::new(); | |
1820 | /// a.insert(2); | |
1821 | /// a.insert(6); | |
1822 | /// | |
1823 | /// let mut b = BitSet::new(); | |
1824 | /// b.insert(1); | |
1825 | /// b.insert(3); | |
1826 | /// b.insert(6); | |
1827 | /// | |
1828 | /// a.append(&mut b); | |
1829 | /// | |
1830 | /// assert_eq!(a.len(), 4); | |
1831 | /// assert_eq!(b.len(), 0); | |
1832 | /// assert_eq!(a, BitSet::from_bit_vec(BitVec::from_bytes(&[0b01110010]))); | |
1833 | /// ``` | |
62682a34 | 1834 | #[unstable(feature = "append", |
d9579d0f AL |
1835 | reason = "recently added as part of collections reform 2")] |
1836 | pub fn append(&mut self, other: &mut Self) { | |
1837 | self.union_with(other); | |
1838 | other.clear(); | |
1839 | } | |
1840 | ||
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. | |
1843 | /// | |
1844 | /// # Examples | |
1845 | /// | |
1846 | /// ``` | |
62682a34 | 1847 | /// # #![feature(bitset, bitvec, split_off)] |
d9579d0f AL |
1848 | /// use std::collections::{BitSet, BitVec}; |
1849 | /// let mut a = BitSet::new(); | |
1850 | /// a.insert(2); | |
1851 | /// a.insert(6); | |
1852 | /// a.insert(1); | |
1853 | /// a.insert(3); | |
1854 | /// | |
1855 | /// let b = a.split_off(3); | |
1856 | /// | |
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]))); | |
1861 | /// ``` | |
62682a34 | 1862 | #[unstable(feature = "split_off", |
d9579d0f AL |
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(); | |
1866 | ||
1867 | if at == 0 { | |
1868 | swap(self, &mut other); | |
1869 | return other; | |
1870 | } else if at >= self.bit_vec.len() { | |
1871 | return other; | |
1872 | } | |
1873 | ||
1874 | // Calculate block and bit at which to split | |
1875 | let w = at / u32::BITS; | |
1876 | let b = at % u32::BITS; | |
1877 | ||
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; | |
1883 | ||
1884 | if b > 0 { | |
1885 | other.bit_vec.storage[w] &= !0 << b; | |
1886 | } | |
1887 | ||
1888 | // Sets `bit_vec.len()` and fixes the last block as well | |
1889 | self.bit_vec.truncate(at); | |
1890 | ||
1891 | other | |
1892 | } | |
1893 | ||
9346a6ac | 1894 | /// Returns the number of set bits in this set. |
1a4d82fc | 1895 | #[inline] |
85aaf69f SL |
1896 | #[stable(feature = "rust1", since = "1.0.0")] |
1897 | pub fn len(&self) -> usize { | |
c34b1796 | 1898 | self.bit_vec.blocks().fold(0, |acc, n| acc + n.count_ones() as usize) |
1a4d82fc JJ |
1899 | } |
1900 | ||
1901 | /// Returns whether there are no bits set in this set | |
1902 | #[inline] | |
85aaf69f | 1903 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1904 | pub fn is_empty(&self) -> bool { |
85aaf69f | 1905 | self.bit_vec.none() |
1a4d82fc JJ |
1906 | } |
1907 | ||
1908 | /// Clears all bits in this set | |
1909 | #[inline] | |
85aaf69f | 1910 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1911 | pub fn clear(&mut self) { |
85aaf69f | 1912 | self.bit_vec.clear(); |
1a4d82fc JJ |
1913 | } |
1914 | ||
1915 | /// Returns `true` if this set contains the specified integer. | |
1916 | #[inline] | |
85aaf69f SL |
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] | |
1a4d82fc JJ |
1921 | } |
1922 | ||
1923 | /// Returns `true` if the set has no elements in common with `other`. | |
1924 | /// This is equivalent to checking for an empty intersection. | |
1925 | #[inline] | |
85aaf69f SL |
1926 | #[stable(feature = "rust1", since = "1.0.0")] |
1927 | pub fn is_disjoint(&self, other: &BitSet) -> bool { | |
1a4d82fc JJ |
1928 | self.intersection(other).next().is_none() |
1929 | } | |
1930 | ||
1931 | /// Returns `true` if the set is a subset of another. | |
1932 | #[inline] | |
85aaf69f SL |
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()); | |
1a4d82fc JJ |
1938 | |
1939 | // Check that `self` intersect `other` is self | |
85aaf69f | 1940 | self_bit_vec.blocks().zip(other_bit_vec.blocks()).all(|(w1, w2)| w1 & w2 == w1) && |
1a4d82fc | 1941 | // Make sure if `self` has any more blocks than `other`, they're all 0 |
85aaf69f | 1942 | self_bit_vec.blocks().skip(other_blocks).all(|w| w == 0) |
1a4d82fc JJ |
1943 | } |
1944 | ||
1945 | /// Returns `true` if the set is a superset of another. | |
1946 | #[inline] | |
85aaf69f SL |
1947 | #[stable(feature = "rust1", since = "1.0.0")] |
1948 | pub fn is_superset(&self, other: &BitSet) -> bool { | |
1a4d82fc JJ |
1949 | other.is_subset(self) |
1950 | } | |
1951 | ||
1952 | /// Adds a value to the set. Returns `true` if the value was not already | |
1953 | /// present in the set. | |
85aaf69f SL |
1954 | #[stable(feature = "rust1", since = "1.0.0")] |
1955 | pub fn insert(&mut self, value: usize) -> bool { | |
1a4d82fc JJ |
1956 | if self.contains(&value) { |
1957 | return false; | |
1958 | } | |
1959 | ||
1960 | // Ensure we have enough space to hold the new element | |
85aaf69f | 1961 | let len = self.bit_vec.len(); |
1a4d82fc | 1962 | if value >= len { |
85aaf69f | 1963 | self.bit_vec.grow(value - len + 1, false) |
1a4d82fc JJ |
1964 | } |
1965 | ||
85aaf69f | 1966 | self.bit_vec.set(value, true); |
1a4d82fc JJ |
1967 | return true; |
1968 | } | |
1969 | ||
1970 | /// Removes a value from the set. Returns `true` if the value was | |
1971 | /// present in the set. | |
85aaf69f SL |
1972 | #[stable(feature = "rust1", since = "1.0.0")] |
1973 | pub fn remove(&mut self, value: &usize) -> bool { | |
1a4d82fc JJ |
1974 | if !self.contains(value) { |
1975 | return false; | |
1976 | } | |
1977 | ||
85aaf69f | 1978 | self.bit_vec.set(*value, false); |
1a4d82fc JJ |
1979 | |
1980 | return true; | |
1981 | } | |
1982 | } | |
1983 | ||
85aaf69f SL |
1984 | #[stable(feature = "rust1", since = "1.0.0")] |
1985 | impl fmt::Debug for BitSet { | |
1a4d82fc | 1986 | fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { |
c34b1796 | 1987 | try!(write!(fmt, "{{")); |
1a4d82fc | 1988 | let mut first = true; |
85aaf69f | 1989 | for n in self { |
1a4d82fc JJ |
1990 | if !first { |
1991 | try!(write!(fmt, ", ")); | |
1992 | } | |
1993 | try!(write!(fmt, "{:?}", n)); | |
1994 | first = false; | |
1995 | } | |
1996 | write!(fmt, "}}") | |
1997 | } | |
1998 | } | |
1999 | ||
85aaf69f | 2000 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f SL |
2001 | impl hash::Hash for BitSet { |
2002 | fn hash<H: hash::Hasher>(&self, state: &mut H) { | |
2003 | for pos in self { | |
1a4d82fc JJ |
2004 | pos.hash(state); |
2005 | } | |
2006 | } | |
2007 | } | |
2008 | ||
1a4d82fc | 2009 | #[derive(Clone)] |
85aaf69f | 2010 | #[stable(feature = "rust1", since = "1.0.0")] |
62682a34 SL |
2011 | struct BlockIter<T> where T: Iterator<Item=u32> { |
2012 | head: u32, | |
2013 | head_offset: usize, | |
2014 | tail: T, | |
2015 | } | |
2016 | ||
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} | |
2021 | } | |
1a4d82fc JJ |
2022 | } |
2023 | ||
85aaf69f | 2024 | /// An iterator combining two `BitSet` iterators. |
1a4d82fc JJ |
2025 | #[derive(Clone)] |
2026 | struct TwoBitPositions<'a> { | |
62682a34 SL |
2027 | set: Blocks<'a>, |
2028 | other: Blocks<'a>, | |
1a4d82fc | 2029 | merge: fn(u32, u32) -> u32, |
1a4d82fc JJ |
2030 | } |
2031 | ||
62682a34 | 2032 | /// An iterator for `BitSet`. |
c34b1796 | 2033 | #[derive(Clone)] |
85aaf69f | 2034 | #[stable(feature = "rust1", since = "1.0.0")] |
62682a34 | 2035 | pub struct SetIter<'a>(BlockIter<Blocks<'a>>); |
c34b1796 | 2036 | #[derive(Clone)] |
85aaf69f | 2037 | #[stable(feature = "rust1", since = "1.0.0")] |
62682a34 | 2038 | pub struct Union<'a>(BlockIter<TwoBitPositions<'a>>); |
c34b1796 | 2039 | #[derive(Clone)] |
85aaf69f | 2040 | #[stable(feature = "rust1", since = "1.0.0")] |
62682a34 | 2041 | pub struct Intersection<'a>(Take<BlockIter<TwoBitPositions<'a>>>); |
c34b1796 | 2042 | #[derive(Clone)] |
85aaf69f | 2043 | #[stable(feature = "rust1", since = "1.0.0")] |
62682a34 SL |
2044 | pub struct Difference<'a>(BlockIter<TwoBitPositions<'a>>); |
2045 | #[derive(Clone)] | |
2046 | #[stable(feature = "rust1", since = "1.0.0")] | |
2047 | pub struct SymmetricDifference<'a>(BlockIter<TwoBitPositions<'a>>); | |
1a4d82fc | 2048 | |
85aaf69f | 2049 | #[stable(feature = "rust1", since = "1.0.0")] |
62682a34 | 2050 | impl<'a, T> Iterator for BlockIter<T> where T: Iterator<Item=u32> { |
85aaf69f | 2051 | type Item = usize; |
1a4d82fc | 2052 | |
85aaf69f | 2053 | fn next(&mut self) -> Option<usize> { |
62682a34 SL |
2054 | while self.head == 0 { |
2055 | match self.tail.next() { | |
2056 | Some(w) => self.head = w, | |
2057 | None => return None | |
1a4d82fc | 2058 | } |
62682a34 | 2059 | self.head_offset += u32::BITS; |
1a4d82fc JJ |
2060 | } |
2061 | ||
62682a34 SL |
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)) | |
1a4d82fc JJ |
2071 | } |
2072 | ||
2073 | #[inline] | |
85aaf69f | 2074 | fn size_hint(&self) -> (usize, Option<usize>) { |
62682a34 SL |
2075 | match self.tail.size_hint() { |
2076 | (_, Some(h)) => (0, Some(1 + h * (u32::BITS as usize))), | |
2077 | _ => (0, None) | |
2078 | } | |
1a4d82fc JJ |
2079 | } |
2080 | } | |
2081 | ||
85aaf69f | 2082 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 2083 | impl<'a> Iterator for TwoBitPositions<'a> { |
62682a34 SL |
2084 | type Item = u32; |
2085 | ||
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)), | |
2091 | _ => return None | |
1a4d82fc | 2092 | } |
1a4d82fc JJ |
2093 | } |
2094 | ||
2095 | #[inline] | |
85aaf69f | 2096 | fn size_hint(&self) -> (usize, Option<usize>) { |
62682a34 SL |
2097 | let (a, au) = self.set.size_hint(); |
2098 | let (b, bu) = self.other.size_hint(); | |
2099 | ||
2100 | let upper = match (au, bu) { | |
2101 | (Some(au), Some(bu)) => Some(cmp::max(au, bu)), | |
2102 | _ => None | |
2103 | }; | |
2104 | ||
2105 | (cmp::max(a, b), upper) | |
1a4d82fc JJ |
2106 | } |
2107 | } | |
2108 | ||
62682a34 SL |
2109 | #[stable(feature = "rust1", since = "1.0.0")] |
2110 | impl<'a> Iterator for SetIter<'a> { | |
2111 | type Item = usize; | |
2112 | ||
2113 | #[inline] fn next(&mut self) -> Option<usize> { self.0.next() } | |
2114 | #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() } | |
2115 | } | |
2116 | ||
85aaf69f | 2117 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 2118 | impl<'a> Iterator for Union<'a> { |
85aaf69f | 2119 | type Item = usize; |
1a4d82fc | 2120 | |
85aaf69f SL |
2121 | #[inline] fn next(&mut self) -> Option<usize> { self.0.next() } |
2122 | #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() } | |
1a4d82fc JJ |
2123 | } |
2124 | ||
85aaf69f | 2125 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 2126 | impl<'a> Iterator for Intersection<'a> { |
85aaf69f | 2127 | type Item = usize; |
1a4d82fc | 2128 | |
85aaf69f SL |
2129 | #[inline] fn next(&mut self) -> Option<usize> { self.0.next() } |
2130 | #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() } | |
1a4d82fc JJ |
2131 | } |
2132 | ||
85aaf69f | 2133 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 2134 | impl<'a> Iterator for Difference<'a> { |
85aaf69f | 2135 | type Item = usize; |
1a4d82fc | 2136 | |
85aaf69f SL |
2137 | #[inline] fn next(&mut self) -> Option<usize> { self.0.next() } |
2138 | #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() } | |
1a4d82fc JJ |
2139 | } |
2140 | ||
85aaf69f | 2141 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 2142 | impl<'a> Iterator for SymmetricDifference<'a> { |
85aaf69f | 2143 | type Item = usize; |
1a4d82fc | 2144 | |
85aaf69f SL |
2145 | #[inline] fn next(&mut self) -> Option<usize> { self.0.next() } |
2146 | #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() } | |
1a4d82fc JJ |
2147 | } |
2148 | ||
85aaf69f SL |
2149 | #[stable(feature = "rust1", since = "1.0.0")] |
2150 | impl<'a> IntoIterator for &'a BitSet { | |
2151 | type Item = usize; | |
2152 | type IntoIter = SetIter<'a>; | |
2153 | ||
2154 | fn into_iter(self) -> SetIter<'a> { | |
2155 | self.iter() | |
2156 | } | |
2157 | } |