diff options
| -rw-r--r-- | .cargo_vcs_info.json | 6 | ||||
| -rw-r--r-- | .gitignore | 2 | ||||
| -rw-r--r-- | .travis.yml | 18 | ||||
| -rw-r--r-- | Cargo.toml | 36 | ||||
| -rw-r--r-- | Cargo.toml.orig | 22 | ||||
| -rw-r--r-- | LICENSE-APACHE | 201 | ||||
| -rw-r--r-- | LICENSE-MIT | 25 | ||||
| -rw-r--r-- | README.md | 17 | ||||
| -rw-r--r-- | deploy-docs.sh | 20 | ||||
| -rw-r--r-- | src/lib.rs | 1608 |
10 files changed, 1955 insertions, 0 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json new file mode 100644 index 0000000..eb8df2a --- /dev/null +++ b/.cargo_vcs_info.json @@ -0,0 +1,6 @@ +{ + "git": { + "sha1": "9f1d0b3342f1defdd5ac59566dc6cff698d622a2" + }, + "path_in_vcs": "" +}
\ No newline at end of file diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..a9d37c5 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +target +Cargo.lock diff --git a/.travis.yml b/.travis.yml new file mode 100644 index 0000000..3838a70 --- /dev/null +++ b/.travis.yml @@ -0,0 +1,18 @@ +language: rust +sudo: false +matrix: + include: + - rust: stable + - rust: nightly + env: FEATURES="--features nightly" +script: + - cargo build $FEATURES + - cargo test $FEATURES + - cargo doc --no-deps +after_success: | + [ "$TRAVIS_RUST_VERSION" = nightly ] && + [ "$TRAVIS_BRANCH" = master ] && + [ "$TRAVIS_PULL_REQUEST" = false ] && + bash deploy-docs.sh +notifications: + webhooks: http://huon.me:54857/travis diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..b9539b6 --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,36 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies. +# +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. + +[package] +name = "bit-set" +version = "0.5.3" +authors = ["Alexis Beingessner <a.beingessner@gmail.com>"] +description = "A set of bits" +homepage = "https://github.com/contain-rs/bit-set" +documentation = "https://contain-rs.github.io/bit-set/bit_set" +readme = "README.md" +keywords = [ + "data-structures", + "bitset", +] +license = "MIT/Apache-2.0" +repository = "https://github.com/contain-rs/bit-set" + +[dependencies.bit-vec] +version = "0.6.1" +default-features = false + +[dev-dependencies.rand] +version = "0.3" + +[features] +default = ["std"] +std = ["bit-vec/std"] diff --git a/Cargo.toml.orig b/Cargo.toml.orig new file mode 100644 index 0000000..f200cbe --- /dev/null +++ b/Cargo.toml.orig @@ -0,0 +1,22 @@ +[package] +name = "bit-set" +version = "0.5.3" +authors = ["Alexis Beingessner <a.beingessner@gmail.com>"] +license = "MIT/Apache-2.0" +description = "A set of bits" +repository = "https://github.com/contain-rs/bit-set" +homepage = "https://github.com/contain-rs/bit-set" +documentation = "https://contain-rs.github.io/bit-set/bit_set" +keywords = ["data-structures", "bitset"] +readme = "README.md" + +[dev-dependencies] +rand = "0.3" + +[dependencies.bit-vec] +version = "0.6.1" +default-features = false + +[features] +default = ["std"] +std = ["bit-vec/std"] diff --git a/LICENSE-APACHE b/LICENSE-APACHE new file mode 100644 index 0000000..11069ed --- /dev/null +++ b/LICENSE-APACHE @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + +TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + +1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + +2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + +3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + +4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + +5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + +6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + +7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + +8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + +9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + +END OF TERMS AND CONDITIONS + +APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + +Copyright [yyyy] [name of copyright owner] + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. diff --git a/LICENSE-MIT b/LICENSE-MIT new file mode 100644 index 0000000..40b8817 --- /dev/null +++ b/LICENSE-MIT @@ -0,0 +1,25 @@ +Copyright (c) 2016 The Rust Project Developers + +Permission is hereby granted, free of charge, to any +person obtaining a copy of this software and associated +documentation files (the "Software"), to deal in the +Software without restriction, including without +limitation the rights to use, copy, modify, merge, +publish, distribute, sublicense, and/or sell copies of +the Software, and to permit persons to whom the Software +is furnished to do so, subject to the following +conditions: + +The above copyright notice and this permission notice +shall be included in all copies or substantial portions +of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF +ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED +TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A +PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT +SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION +OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR +IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/README.md b/README.md new file mode 100644 index 0000000..367e425 --- /dev/null +++ b/README.md @@ -0,0 +1,17 @@ +**WARNING: THIS PROJECT IS IN MAINTENANCE MODE, DUE TO INSUFFICIENT MAINTAINER RESOURCES** + +It works fine, but will generally no longer be improved. + +We are currently only accepting changes which: + +* keep this compiling with the latest versions of Rust or its dependencies. +* have minimal review requirements, such as documentation changes (so not totally new APIs). + +------ + +A Set of bits. + +Documentation is available at https://contain-rs.github.io/bit-set/bit_set. + +[](https://travis-ci.org/contain-rs/bit-set) +[](https://crates.io/crates/bit-set) diff --git a/deploy-docs.sh b/deploy-docs.sh new file mode 100644 index 0000000..c8f25ee --- /dev/null +++ b/deploy-docs.sh @@ -0,0 +1,20 @@ +#!/bin/bash + +set -o errexit -o nounset + +rev=$(git rev-parse --short HEAD) + +cd target/doc + +git init +git config user.email 'FlashCat@users.noreply.github.com' +git config user.name 'FlashCat' +git remote add upstream "https://${GH_TOKEN}@github.com/${TRAVIS_REPO_SLUG}.git" +git fetch upstream gh-pages +git reset upstream/gh-pages + +touch . + +git add -A . +git commit -m "rebuild pages at ${rev}" +git push -q upstream HEAD:gh-pages diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..80ee624 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,1608 @@ +// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! An implementation of a set using a bit vector as an underlying +//! representation for holding unsigned numerical elements. +//! +//! It should also be noted that the amount of storage necessary for holding a +//! set of objects is proportional to the maximum of the objects when viewed +//! as a `usize`. +//! +//! # Examples +//! +//! ``` +//! use bit_set::BitSet; +//! +//! // It's a regular set +//! let mut s = BitSet::new(); +//! s.insert(0); +//! s.insert(3); +//! s.insert(7); +//! +//! s.remove(7); +//! +//! if !s.contains(7) { +//! println!("There is no 7"); +//! } +//! +//! // Can initialize from a `BitVec` +//! let other = BitSet::from_bytes(&[0b11010000]); +//! +//! s.union_with(&other); +//! +//! // Print 0, 1, 3 in some order +//! for x in s.iter() { +//! println!("{}", x); +//! } +//! +//! // Can convert back to a `BitVec` +//! let bv = s.into_bit_vec(); +//! assert!(bv[3]); +//! ``` + +#![no_std] +#![cfg_attr(all(test, feature = "nightly"), feature(test))] +extern crate bit_vec; +#[cfg(all(test, feature = "nightly"))] +extern crate rand; +#[cfg(all(test, feature = "nightly"))] +extern crate test; + +#[cfg(test)] +#[macro_use] +extern crate std; + +use bit_vec::{BitBlock, BitVec, Blocks}; +use core::cmp; +use core::cmp::Ordering; +use core::fmt; +use core::hash; +use core::iter::{self, Chain, Enumerate, FromIterator, Repeat, Skip, Take}; + +type MatchWords<'a, B> = Chain<Enumerate<Blocks<'a, B>>, Skip<Take<Enumerate<Repeat<B>>>>>; + +/// Computes how many blocks are needed to store that many bits +fn blocks_for_bits<B: BitBlock>(bits: usize) -> usize { + // If we want 17 bits, dividing by 32 will produce 0. So we add 1 to make sure we + // reserve enough. But if we want exactly a multiple of 32, this will actually allocate + // one too many. So we need to check if that's the case. We can do that by computing if + // bitwise AND by `32 - 1` is 0. But LLVM should be able to optimize the semantically + // superior modulo operator on a power of two to this. + // + // Note that we can technically avoid this branch with the expression + // `(nbits + BITS - 1) / 32::BITS`, but if nbits is almost usize::MAX this will overflow. + if bits % B::bits() == 0 { + bits / B::bits() + } else { + bits / B::bits() + 1 + } +} + +// Take two BitVec's, and return iterators of their words, where the shorter one +// has been padded with 0's +fn match_words<'a, 'b, B: BitBlock>( + a: &'a BitVec<B>, + b: &'b BitVec<B>, +) -> (MatchWords<'a, B>, MatchWords<'b, B>) { + let a_len = a.storage().len(); + let b_len = b.storage().len(); + + // have to uselessly pretend to pad the longer one for type matching + if a_len < b_len { + ( + a.blocks() + .enumerate() + .chain(iter::repeat(B::zero()).enumerate().take(b_len).skip(a_len)), + b.blocks() + .enumerate() + .chain(iter::repeat(B::zero()).enumerate().take(0).skip(0)), + ) + } else { + ( + a.blocks() + .enumerate() + .chain(iter::repeat(B::zero()).enumerate().take(0).skip(0)), + b.blocks() + .enumerate() + .chain(iter::repeat(B::zero()).enumerate().take(a_len).skip(b_len)), + ) + } +} + +pub struct BitSet<B = u32> { + bit_vec: BitVec<B>, +} + +impl<B: BitBlock> Clone for BitSet<B> { + fn clone(&self) -> Self { + BitSet { + bit_vec: self.bit_vec.clone(), + } + } + + fn clone_from(&mut self, other: &Self) { + self.bit_vec.clone_from(&other.bit_vec); + } +} + +impl<B: BitBlock> Default for BitSet<B> { + #[inline] + fn default() -> Self { + BitSet { + bit_vec: Default::default(), + } + } +} + +impl<B: BitBlock> FromIterator<usize> for BitSet<B> { + fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self { + let mut ret = Self::default(); + ret.extend(iter); + ret + } +} + +impl<B: BitBlock> Extend<usize> for BitSet<B> { + #[inline] + fn extend<I: IntoIterator<Item = usize>>(&mut self, iter: I) { + for i in iter { + self.insert(i); + } + } +} + +impl<B: BitBlock> PartialOrd for BitSet<B> { + #[inline] + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + self.iter().partial_cmp(other) + } +} + +impl<B: BitBlock> Ord for BitSet<B> { + #[inline] + fn cmp(&self, other: &Self) -> Ordering { + self.iter().cmp(other) + } +} + +impl<B: BitBlock> PartialEq for BitSet<B> { + #[inline] + fn eq(&self, other: &Self) -> bool { + self.iter().eq(other) + } +} + +impl<B: BitBlock> Eq for BitSet<B> {} + +impl BitSet<u32> { + /// Creates a new empty `BitSet`. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let mut s = BitSet::new(); + /// ``` + #[inline] + pub fn new() -> Self { + Self::default() + } + + /// Creates a new `BitSet` with initially no contents, able to + /// hold `nbits` elements without resizing. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let mut s = BitSet::with_capacity(100); + /// assert!(s.capacity() >= 100); + /// ``` + #[inline] + pub fn with_capacity(nbits: usize) -> Self { + let bit_vec = BitVec::from_elem(nbits, false); + Self::from_bit_vec(bit_vec) + } + + /// Creates a new `BitSet` from the given bit vector. + /// + /// # Examples + /// + /// ``` + /// extern crate bit_vec; + /// extern crate bit_set; + /// + /// fn main() { + /// use bit_vec::BitVec; + /// use bit_set::BitSet; + /// + /// let bv = BitVec::from_bytes(&[0b01100000]); + /// let s = BitSet::from_bit_vec(bv); + /// + /// // Print 1, 2 in arbitrary order + /// for x in s.iter() { + /// println!("{}", x); + /// } + /// } + /// ``` + #[inline] + pub fn from_bit_vec(bit_vec: BitVec) -> Self { + BitSet { bit_vec } + } + + pub fn from_bytes(bytes: &[u8]) -> Self { + BitSet { + bit_vec: BitVec::from_bytes(bytes), + } + } +} + +impl<B: BitBlock> BitSet<B> { + /// Returns the capacity in bits for this bit vector. Inserting any + /// element less than this amount will not trigger a resizing. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let mut s = BitSet::with_capacity(100); + /// assert!(s.capacity() >= 100); + /// ``` + #[inline] + pub fn capacity(&self) -> usize { + self.bit_vec.capacity() + } + + /// Reserves capacity for the given `BitSet` to contain `len` distinct elements. In the case + /// of `BitSet` this means reallocations will not occur as long as all inserted elements + /// are less than `len`. + /// + /// The collection may reserve more space to avoid frequent reallocations. + /// + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let mut s = BitSet::new(); + /// s.reserve_len(10); + /// assert!(s.capacity() >= 10); + /// ``` + pub fn reserve_len(&mut self, len: usize) { + let cur_len = self.bit_vec.len(); + if len >= cur_len { + self.bit_vec.reserve(len - cur_len); + } + } + + /// Reserves the minimum capacity for the given `BitSet` to contain `len` distinct elements. + /// In the case of `BitSet` this means reallocations will not occur as long as all inserted + /// elements are less than `len`. + /// + /// Note that the allocator may give the collection more space than it requests. Therefore + /// capacity can not be relied upon to be precisely minimal. Prefer `reserve_len` if future + /// insertions are expected. + /// + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let mut s = BitSet::new(); + /// s.reserve_len_exact(10); + /// assert!(s.capacity() >= 10); + /// ``` + pub fn reserve_len_exact(&mut self, len: usize) { + let cur_len = self.bit_vec.len(); + if len >= cur_len { + self.bit_vec.reserve_exact(len - cur_len); + } + } + + /// Consumes this set to return the underlying bit vector. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let mut s = BitSet::new(); + /// s.insert(0); + /// s.insert(3); + /// + /// let bv = s.into_bit_vec(); + /// assert!(bv[0]); + /// assert!(bv[3]); + /// ``` + #[inline] + pub fn into_bit_vec(self) -> BitVec<B> { + self.bit_vec + } + + /// Returns a reference to the underlying bit vector. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let mut s = BitSet::new(); + /// s.insert(0); + /// + /// let bv = s.get_ref(); + /// assert_eq!(bv[0], true); + /// ``` + #[inline] + pub fn get_ref(&self) -> &BitVec<B> { + &self.bit_vec + } + + #[inline] + fn other_op<F>(&mut self, other: &Self, mut f: F) + where + F: FnMut(B, B) -> B, + { + // Unwrap BitVecs + let self_bit_vec = &mut self.bit_vec; + let other_bit_vec = &other.bit_vec; + + let self_len = self_bit_vec.len(); + let other_len = other_bit_vec.len(); + + // Expand the vector if necessary + if self_len < other_len { + self_bit_vec.grow(other_len - self_len, false); + } + + // virtually pad other with 0's for equal lengths + let other_words = { + let (_, result) = match_words(self_bit_vec, other_bit_vec); + result + }; + + // Apply values found in other + for (i, w) in other_words { + let old = self_bit_vec.storage()[i]; + let new = f(old, w); + unsafe { + self_bit_vec.storage_mut()[i] = new; + } + } + } + + /// Truncates the underlying vector to the least length required. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let mut s = BitSet::new(); + /// s.insert(32183231); + /// s.remove(32183231); + /// + /// // Internal storage will probably be bigger than necessary + /// println!("old capacity: {}", s.capacity()); + /// + /// // Now should be smaller + /// s.shrink_to_fit(); + /// println!("new capacity: {}", s.capacity()); + /// ``` + #[inline] + pub fn shrink_to_fit(&mut self) { + let bit_vec = &mut self.bit_vec; + // Obtain original length + let old_len = bit_vec.storage().len(); + // Obtain coarse trailing zero length + let n = bit_vec + .storage() + .iter() + .rev() + .take_while(|&&n| n == B::zero()) + .count(); + // Truncate away all empty trailing blocks, then shrink_to_fit + let trunc_len = old_len - n; + unsafe { + bit_vec.storage_mut().truncate(trunc_len); + bit_vec.set_len(trunc_len * B::bits()); + bit_vec.shrink_to_fit(); + } + } + + /// Iterator over each usize stored in the `BitSet`. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let s = BitSet::from_bytes(&[0b01001010]); + /// + /// // Print 1, 4, 6 in arbitrary order + /// for x in s.iter() { + /// println!("{}", x); + /// } + /// ``` + #[inline] + pub fn iter(&self) -> Iter<B> { + Iter(BlockIter::from_blocks(self.bit_vec.blocks())) + } + + /// Iterator over each usize stored in `self` union `other`. + /// See [union_with](#method.union_with) for an efficient in-place version. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let a = BitSet::from_bytes(&[0b01101000]); + /// let b = BitSet::from_bytes(&[0b10100000]); + /// + /// // Print 0, 1, 2, 4 in arbitrary order + /// for x in a.union(&b) { + /// println!("{}", x); + /// } + /// ``` + #[inline] + pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, B> { + fn or<B: BitBlock>(w1: B, w2: B) -> B { + w1 | w2 + } + + Union(BlockIter::from_blocks(TwoBitPositions { + set: self.bit_vec.blocks(), + other: other.bit_vec.blocks(), + merge: or, + })) + } + + /// Iterator over each usize stored in `self` intersect `other`. + /// See [intersect_with](#method.intersect_with) for an efficient in-place version. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let a = BitSet::from_bytes(&[0b01101000]); + /// let b = BitSet::from_bytes(&[0b10100000]); + /// + /// // Print 2 + /// for x in a.intersection(&b) { + /// println!("{}", x); + /// } + /// ``` + #[inline] + pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, B> { + fn bitand<B: BitBlock>(w1: B, w2: B) -> B { + w1 & w2 + } + let min = cmp::min(self.bit_vec.len(), other.bit_vec.len()); + + Intersection( + BlockIter::from_blocks(TwoBitPositions { + set: self.bit_vec.blocks(), + other: other.bit_vec.blocks(), + merge: bitand, + }) + .take(min), + ) + } + + /// Iterator over each usize stored in the `self` setminus `other`. + /// See [difference_with](#method.difference_with) for an efficient in-place version. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let a = BitSet::from_bytes(&[0b01101000]); + /// let b = BitSet::from_bytes(&[0b10100000]); + /// + /// // Print 1, 4 in arbitrary order + /// for x in a.difference(&b) { + /// println!("{}", x); + /// } + /// + /// // Note that difference is not symmetric, + /// // and `b - a` means something else. + /// // This prints 0 + /// for x in b.difference(&a) { + /// println!("{}", x); + /// } + /// ``` + #[inline] + pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, B> { + fn diff<B: BitBlock>(w1: B, w2: B) -> B { + w1 & !w2 + } + + Difference(BlockIter::from_blocks(TwoBitPositions { + set: self.bit_vec.blocks(), + other: other.bit_vec.blocks(), + merge: diff, + })) + } + + /// Iterator over each usize stored in the symmetric difference of `self` and `other`. + /// See [symmetric_difference_with](#method.symmetric_difference_with) for + /// an efficient in-place version. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let a = BitSet::from_bytes(&[0b01101000]); + /// let b = BitSet::from_bytes(&[0b10100000]); + /// + /// // Print 0, 1, 4 in arbitrary order + /// for x in a.symmetric_difference(&b) { + /// println!("{}", x); + /// } + /// ``` + #[inline] + pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, B> { + fn bitxor<B: BitBlock>(w1: B, w2: B) -> B { + w1 ^ w2 + } + + SymmetricDifference(BlockIter::from_blocks(TwoBitPositions { + set: self.bit_vec.blocks(), + other: other.bit_vec.blocks(), + merge: bitxor, + })) + } + + /// Unions in-place with the specified other bit vector. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let a = 0b01101000; + /// let b = 0b10100000; + /// let res = 0b11101000; + /// + /// let mut a = BitSet::from_bytes(&[a]); + /// let b = BitSet::from_bytes(&[b]); + /// let res = BitSet::from_bytes(&[res]); + /// + /// a.union_with(&b); + /// assert_eq!(a, res); + /// ``` + #[inline] + pub fn union_with(&mut self, other: &Self) { + self.other_op(other, |w1, w2| w1 | w2); + } + + /// Intersects in-place with the specified other bit vector. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let a = 0b01101000; + /// let b = 0b10100000; + /// let res = 0b00100000; + /// + /// let mut a = BitSet::from_bytes(&[a]); + /// let b = BitSet::from_bytes(&[b]); + /// let res = BitSet::from_bytes(&[res]); + /// + /// a.intersect_with(&b); + /// assert_eq!(a, res); + /// ``` + #[inline] + pub fn intersect_with(&mut self, other: &Self) { + self.other_op(other, |w1, w2| w1 & w2); + } + + /// Makes this bit vector the difference with the specified other bit vector + /// in-place. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let a = 0b01101000; + /// let b = 0b10100000; + /// let a_b = 0b01001000; // a - b + /// let b_a = 0b10000000; // b - a + /// + /// let mut bva = BitSet::from_bytes(&[a]); + /// let bvb = BitSet::from_bytes(&[b]); + /// let bva_b = BitSet::from_bytes(&[a_b]); + /// let bvb_a = BitSet::from_bytes(&[b_a]); + /// + /// bva.difference_with(&bvb); + /// assert_eq!(bva, bva_b); + /// + /// let bva = BitSet::from_bytes(&[a]); + /// let mut bvb = BitSet::from_bytes(&[b]); + /// + /// bvb.difference_with(&bva); + /// assert_eq!(bvb, bvb_a); + /// ``` + #[inline] + pub fn difference_with(&mut self, other: &Self) { + self.other_op(other, |w1, w2| w1 & !w2); + } + + /// Makes this bit vector the symmetric difference with the specified other + /// bit vector in-place. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let a = 0b01101000; + /// let b = 0b10100000; + /// let res = 0b11001000; + /// + /// let mut a = BitSet::from_bytes(&[a]); + /// let b = BitSet::from_bytes(&[b]); + /// let res = BitSet::from_bytes(&[res]); + /// + /// a.symmetric_difference_with(&b); + /// assert_eq!(a, res); + /// ``` + #[inline] + pub fn symmetric_difference_with(&mut self, other: &Self) { + self.other_op(other, |w1, w2| w1 ^ w2); + } + + /* + /// Moves all elements from `other` into `Self`, leaving `other` empty. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let mut a = BitSet::new(); + /// a.insert(2); + /// a.insert(6); + /// + /// let mut b = BitSet::new(); + /// b.insert(1); + /// b.insert(3); + /// b.insert(6); + /// + /// a.append(&mut b); + /// + /// assert_eq!(a.len(), 4); + /// assert_eq!(b.len(), 0); + /// assert_eq!(a, BitSet::from_bytes(&[0b01110010])); + /// ``` + pub fn append(&mut self, other: &mut Self) { + self.union_with(other); + other.clear(); + } + + /// Splits the `BitSet` into two at the given key including the key. + /// Retains the first part in-place while returning the second part. + /// + /// # Examples + /// + /// ``` + /// use bit_set::BitSet; + /// + /// let mut a = BitSet::new(); + /// a.insert(2); + /// a.insert(6); + /// a.insert(1); + /// a.insert(3); + /// + /// let b = a.split_off(3); + /// + /// assert_eq!(a.len(), 2); + /// assert_eq!(b.len(), 2); + /// assert_eq!(a, BitSet::from_bytes(&[0b01100000])); + /// assert_eq!(b, BitSet::from_bytes(&[0b00010010])); + /// ``` + pub fn split_off(&mut self, at: usize) -> Self { + let mut other = BitSet::new(); + + if at == 0 { + swap(self, &mut other); + return other; + } else if at >= self.bit_vec.len() { + return other; + } + + // Calculate block and bit at which to split + let w = at / BITS; + let b = at % BITS; + + // Pad `other` with `w` zero blocks, + // append `self`'s blocks in the range from `w` to the end to `other` + other.bit_vec.storage_mut().extend(repeat(0u32).take(w) + .chain(self.bit_vec.storage()[w..].iter().cloned())); + other.bit_vec.nbits = self.bit_vec.nbits; + + if b > 0 { + other.bit_vec.storage_mut()[w] &= !0 << b; + } + + // Sets `bit_vec.len()` and fixes the last block as well + self.bit_vec.truncate(at); + + other + } + */ + + /// Returns the number of set bits in this set. + #[inline] + pub fn len(&self) -> usize { + self.bit_vec + .blocks() + .fold(0, |acc, n| acc + n.count_ones() as usize) + } + + /// Returns whether there are no bits set in this set + #[inline] + pub fn is_empty(&self) -> bool { + self.bit_vec.none() + } + + /// Clears all bits in this set + #[inline] + pub fn clear(&mut self) { + self.bit_vec.clear(); + } + + /// Returns `true` if this set contains the specified integer. + #[inline] + pub fn contains(&self, value: usize) -> bool { + let bit_vec = &self.bit_vec; + value < bit_vec.len() && bit_vec[value] + } + + /// Returns `true` if the set has no elements in common with `other`. + /// This is equivalent to checking for an empty intersection. + #[inline] + pub fn is_disjoint(&self, other: &Self) -> bool { + self.intersection(other).next().is_none() + } + + /// Returns `true` if the set is a subset of another. + #[inline] + pub fn is_subset(&self, other: &Self) -> bool { + let self_bit_vec = &self.bit_vec; + let other_bit_vec = &other.bit_vec; + let other_blocks = blocks_for_bits::<B>(other_bit_vec.len()); + + // Check that `self` intersect `other` is self + self_bit_vec.blocks().zip(other_bit_vec.blocks()).all(|(w1, w2)| w1 & w2 == w1) && + // Make sure if `self` has any more blocks than `other`, they're all 0 + self_bit_vec.blocks().skip(other_blocks).all(|w| w == B::zero()) + } + + /// Returns `true` if the set is a superset of another. + #[inline] + pub fn is_superset(&self, other: &Self) -> bool { + other.is_subset(self) + } + + /// Adds a value to the set. Returns `true` if the value was not already + /// present in the set. + pub fn insert(&mut self, value: usize) -> bool { + if self.contains(value) { + return false; + } + + // Ensure we have enough space to hold the new element + let len = self.bit_vec.len(); + if value >= len { + self.bit_vec.grow(value - len + 1, false) + } + + self.bit_vec.set(value, true); + true + } + + /// Removes a value from the set. Returns `true` if the value was + /// present in the set. + pub fn remove(&mut self, value: usize) -> bool { + if !self.contains(value) { + return false; + } + + self.bit_vec.set(value, false); + + true + } +} + +impl<B: BitBlock> fmt::Debug for BitSet<B> { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + fmt.debug_set().entries(self).finish() + } +} + +impl<B: BitBlock> hash::Hash for BitSet<B> { + fn hash<H: hash::Hasher>(&self, state: &mut H) { + for pos in self { + pos.hash(state); + } + } +} + +#[derive(Clone)] +struct BlockIter<T, B> { + head: B, + head_offset: usize, + tail: T, +} + +impl<T, B: BitBlock> BlockIter<T, B> +where + T: Iterator<Item = B>, +{ + fn from_blocks(mut blocks: T) -> BlockIter<T, B> { + let h = blocks.next().unwrap_or_else(B::zero); + BlockIter { + tail: blocks, + head: h, + head_offset: 0, + } + } +} + +/// An iterator combining two `BitSet` iterators. +#[derive(Clone)] +struct TwoBitPositions<'a, B: 'a> { + set: Blocks<'a, B>, + other: Blocks<'a, B>, + merge: fn(B, B) -> B, +} + +/// An iterator for `BitSet`. +#[derive(Clone)] +pub struct Iter<'a, B: 'a>(BlockIter<Blocks<'a, B>, B>); +#[derive(Clone)] +pub struct Union<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>); +#[derive(Clone)] +pub struct Intersection<'a, B: 'a>(Take<BlockIter<TwoBitPositions<'a, B>, B>>); +#[derive(Clone)] +pub struct Difference<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>); +#[derive(Clone)] +pub struct SymmetricDifference<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>); + +impl<'a, T, B: BitBlock> Iterator for BlockIter<T, B> +where + T: Iterator<Item = B>, +{ + type Item = usize; + + fn next(&mut self) -> Option<usize> { + while self.head == B::zero() { + match self.tail.next() { + Some(w) => self.head = w, + None => return None, + } + self.head_offset += B::bits(); + } + + // from the current block, isolate the + // LSB and subtract 1, producing k: + // a block with a number of set bits + // equal to the index of the LSB + let k = (self.head & (!self.head + B::one())) - B::one(); + // update block, removing the LSB + self.head = self.head & (self.head - B::one()); + // return offset + (index of LSB) + Some(self.head_offset + (B::count_ones(k) as usize)) + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + match self.tail.size_hint() { + (_, Some(h)) => (0, Some(1 + h * B::bits())), + _ => (0, None), + } + } +} + +impl<'a, B: BitBlock> Iterator for TwoBitPositions<'a, B> { + type Item = B; + + fn next(&mut self) -> Option<B> { + match (self.set.next(), self.other.next()) { + (Some(a), Some(b)) => Some((self.merge)(a, b)), + (Some(a), None) => Some((self.merge)(a, B::zero())), + (None, Some(b)) => Some((self.merge)(B::zero(), b)), + _ => None, + } + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + let (a, au) = self.set.size_hint(); + let (b, bu) = self.other.size_hint(); + + let upper = match (au, bu) { + (Some(au), Some(bu)) => Some(cmp::max(au, bu)), + _ => None, + }; + + (cmp::max(a, b), upper) + } +} + +impl<'a, B: BitBlock> Iterator for Iter<'a, B> { + type Item = usize; + + #[inline] + fn next(&mut self) -> Option<usize> { + self.0.next() + } + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.0.size_hint() + } +} + +impl<'a, B: BitBlock> Iterator for Union<'a, B> { + type Item = usize; + + #[inline] + fn next(&mut self) -> Option<usize> { + self.0.next() + } + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.0.size_hint() + } +} + +impl<'a, B: BitBlock> Iterator for Intersection<'a, B> { + type Item = usize; + + #[inline] + fn next(&mut self) -> Option<usize> { + self.0.next() + } + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.0.size_hint() + } +} + +impl<'a, B: BitBlock> Iterator for Difference<'a, B> { + type Item = usize; + + #[inline] + fn next(&mut self) -> Option<usize> { + self.0.next() + } + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.0.size_hint() + } +} + +impl<'a, B: BitBlock> Iterator for SymmetricDifference<'a, B> { + type Item = usize; + + #[inline] + fn next(&mut self) -> Option<usize> { + self.0.next() + } + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.0.size_hint() + } +} + +impl<'a, B: BitBlock> IntoIterator for &'a BitSet<B> { + type Item = usize; + type IntoIter = Iter<'a, B>; + + fn into_iter(self) -> Iter<'a, B> { + self.iter() + } +} + +#[cfg(test)] +mod tests { + use super::BitSet; + use bit_vec::BitVec; + use std::cmp::Ordering::{Equal, Greater, Less}; + use std::vec::Vec; + + #[test] + fn test_bit_set_show() { + let mut s = BitSet::new(); + s.insert(1); + s.insert(10); + s.insert(50); + s.insert(2); + assert_eq!("{1, 2, 10, 50}", format!("{:?}", s)); + } + + #[test] + fn test_bit_set_from_usizes() { + let usizes = vec![0, 2, 2, 3]; + let a: BitSet = usizes.into_iter().collect(); + let mut b = BitSet::new(); + b.insert(0); + b.insert(2); + b.insert(3); + assert_eq!(a, b); + } + + #[test] + fn test_bit_set_iterator() { + let usizes = vec![0, 2, 2, 3]; + let bit_vec: BitSet = usizes.into_iter().collect(); + + let idxs: Vec<_> = bit_vec.iter().collect(); + assert_eq!(idxs, [0, 2, 3]); + + let long: BitSet = (0..10000).filter(|&n| n % 2 == 0).collect(); + let real: Vec<_> = (0..10000 / 2).map(|x| x * 2).collect(); + + let idxs: Vec<_> = long.iter().collect(); + assert_eq!(idxs, real); + } + + #[test] + fn test_bit_set_frombit_vec_init() { + let bools = [true, false]; + let lengths = [10, 64, 100]; + for &b in &bools { + for &l in &lengths { + let bitset = BitSet::from_bit_vec(BitVec::from_elem(l, b)); + assert_eq!(bitset.contains(1), b); + assert_eq!(bitset.contains(l - 1), b); + assert!(!bitset.contains(l)); + } + } + } + + #[test] + fn test_bit_vec_masking() { + let b = BitVec::from_elem(140, true); + let mut bs = BitSet::from_bit_vec(b); + assert!(bs.contains(139)); + assert!(!bs.contains(140)); + assert!(bs.insert(150)); + assert!(!bs.contains(140)); + assert!(!bs.contains(149)); + assert!(bs.contains(150)); + assert!(!bs.contains(151)); + } + + #[test] + fn test_bit_set_basic() { + let mut b = BitSet::new(); + assert!(b.insert(3)); + assert!(!b.insert(3)); + assert!(b.contains(3)); + assert!(b.insert(4)); + assert!(!b.insert(4)); + assert!(b.contains(3)); + assert!(b.insert(400)); + assert!(!b.insert(400)); + assert!(b.contains(400)); + assert_eq!(b.len(), 3); + } + + #[test] + fn test_bit_set_intersection() { + let mut a = BitSet::new(); + let mut b = BitSet::new(); + + assert!(a.insert(11)); + assert!(a.insert(1)); + assert!(a.insert(3)); + assert!(a.insert(77)); + assert!(a.insert(103)); + assert!(a.insert(5)); + + assert!(b.insert(2)); + assert!(b.insert(11)); + assert!(b.insert(77)); + assert!(b.insert(5)); + assert!(b.insert(3)); + + let expected = [3, 5, 11, 77]; + let actual: Vec<_> = a.intersection(&b).collect(); + assert_eq!(actual, expected); + } + + #[test] + fn test_bit_set_difference() { + let mut a = BitSet::new(); + let mut b = BitSet::new(); + + assert!(a.insert(1)); + assert!(a.insert(3)); + assert!(a.insert(5)); + assert!(a.insert(200)); + assert!(a.insert(500)); + + assert!(b.insert(3)); + assert!(b.insert(200)); + + let expected = [1, 5, 500]; + let actual: Vec<_> = a.difference(&b).collect(); + assert_eq!(actual, expected); + } + + #[test] + fn test_bit_set_symmetric_difference() { + let mut a = BitSet::new(); + let mut b = BitSet::new(); + + assert!(a.insert(1)); + assert!(a.insert(3)); + assert!(a.insert(5)); + assert!(a.insert(9)); + assert!(a.insert(11)); + + assert!(b.insert(3)); + assert!(b.insert(9)); + assert!(b.insert(14)); + assert!(b.insert(220)); + + let expected = [1, 5, 11, 14, 220]; + let actual: Vec<_> = a.symmetric_difference(&b).collect(); + assert_eq!(actual, expected); + } + + #[test] + fn test_bit_set_union() { + let mut a = BitSet::new(); + let mut b = BitSet::new(); + assert!(a.insert(1)); + assert!(a.insert(3)); + assert!(a.insert(5)); + assert!(a.insert(9)); + assert!(a.insert(11)); + assert!(a.insert(160)); + assert!(a.insert(19)); + assert!(a.insert(24)); + assert!(a.insert(200)); + + assert!(b.insert(1)); + assert!(b.insert(5)); + assert!(b.insert(9)); + assert!(b.insert(13)); + assert!(b.insert(19)); + + let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160, 200]; + let actual: Vec<_> = a.union(&b).collect(); + assert_eq!(actual, expected); + } + + #[test] + fn test_bit_set_subset() { + let mut set1 = BitSet::new(); + let mut set2 = BitSet::new(); + + assert!(set1.is_subset(&set2)); // {} {} + set2.insert(100); + assert!(set1.is_subset(&set2)); // {} { 1 } + set2.insert(200); + assert!(set1.is_subset(&set2)); // {} { 1, 2 } + set1.insert(200); + assert!(set1.is_subset(&set2)); // { 2 } { 1, 2 } + set1.insert(300); + assert!(!set1.is_subset(&set2)); // { 2, 3 } { 1, 2 } + set2.insert(300); + assert!(set1.is_subset(&set2)); // { 2, 3 } { 1, 2, 3 } + set2.insert(400); + assert!(set1.is_subset(&set2)); // { 2, 3 } { 1, 2, 3, 4 } + set2.remove(100); + assert!(set1.is_subset(&set2)); // { 2, 3 } { 2, 3, 4 } + set2.remove(300); + assert!(!set1.is_subset(&set2)); // { 2, 3 } { 2, 4 } + set1.remove(300); + assert!(set1.is_subset(&set2)); // { 2 } { 2, 4 } + } + + #[test] + fn test_bit_set_is_disjoint() { + let a = BitSet::from_bytes(&[0b10100010]); + let b = BitSet::from_bytes(&[0b01000000]); + let c = BitSet::new(); + let d = BitSet::from_bytes(&[0b00110000]); + + assert!(!a.is_disjoint(&d)); + assert!(!d.is_disjoint(&a)); + + assert!(a.is_disjoint(&b)); + assert!(a.is_disjoint(&c)); + assert!(b.is_disjoint(&a)); + assert!(b.is_disjoint(&c)); + assert!(c.is_disjoint(&a)); + assert!(c.is_disjoint(&b)); + } + + #[test] + fn test_bit_set_union_with() { + //a should grow to include larger elements + let mut a = BitSet::new(); + a.insert(0); + let mut b = BitSet::new(); + b.insert(5); + let expected = BitSet::from_bytes(&[0b10000100]); + a.union_with(&b); + assert_eq!(a, expected); + + // Standard + let mut a = BitSet::from_bytes(&[0b10100010]); + let mut b = BitSet::from_bytes(&[0b01100010]); + let c = a.clone(); + a.union_with(&b); + b.union_with(&c); + assert_eq!(a.len(), 4); + assert_eq!(b.len(), 4); + } + + #[test] + fn test_bit_set_intersect_with() { + // Explicitly 0'ed bits + let mut a = BitSet::from_bytes(&[0b10100010]); + let mut b = BitSet::from_bytes(&[0b00000000]); + let c = a.clone(); + a.intersect_with(&b); + b.intersect_with(&c); + assert!(a.is_empty()); + assert!(b.is_empty()); + + // Uninitialized bits should behave like 0's + let mut a = BitSet::from_bytes(&[0b10100010]); + let mut b = BitSet::new(); + let c = a.clone(); + a.intersect_with(&b); + b.intersect_with(&c); + assert!(a.is_empty()); + assert!(b.is_empty()); + + // Standard + let mut a = BitSet::from_bytes(&[0b10100010]); + let mut b = BitSet::from_bytes(&[0b01100010]); + let c = a.clone(); + a.intersect_with(&b); + b.intersect_with(&c); + assert_eq!(a.len(), 2); + assert_eq!(b.len(), 2); + } + + #[test] + fn test_bit_set_difference_with() { + // Explicitly 0'ed bits + let mut a = BitSet::from_bytes(&[0b00000000]); + let b = BitSet::from_bytes(&[0b10100010]); + a.difference_with(&b); + assert!(a.is_empty()); + + // Uninitialized bits should behave like 0's + let mut a = BitSet::new(); + let b = BitSet::from_bytes(&[0b11111111]); + a.difference_with(&b); + assert!(a.is_empty()); + + // Standard + let mut a = BitSet::from_bytes(&[0b10100010]); + let mut b = BitSet::from_bytes(&[0b01100010]); + let c = a.clone(); + a.difference_with(&b); + b.difference_with(&c); + assert_eq!(a.len(), 1); + assert_eq!(b.len(), 1); + } + + #[test] + fn test_bit_set_symmetric_difference_with() { + //a should grow to include larger elements + let mut a = BitSet::new(); + a.insert(0); + a.insert(1); + let mut b = BitSet::new(); + b.insert(1); + b.insert(5); + let expected = BitSet::from_bytes(&[0b10000100]); + a.symmetric_difference_with(&b); + assert_eq!(a, expected); + + let mut a = BitSet::from_bytes(&[0b10100010]); + let b = BitSet::new(); + let c = a.clone(); + a.symmetric_difference_with(&b); + assert_eq!(a, c); + + // Standard + let mut a = BitSet::from_bytes(&[0b11100010]); + let mut b = BitSet::from_bytes(&[0b01101010]); + let c = a.clone(); + a.symmetric_difference_with(&b); + b.symmetric_difference_with(&c); + assert_eq!(a.len(), 2); + assert_eq!(b.len(), 2); + } + + #[test] + fn test_bit_set_eq() { + let a = BitSet::from_bytes(&[0b10100010]); + let b = BitSet::from_bytes(&[0b00000000]); + let c = BitSet::new(); + + assert!(a == a); + assert!(a != b); + assert!(a != c); + assert!(b == b); + assert!(b == c); + assert!(c == c); + } + + #[test] + fn test_bit_set_cmp() { + let a = BitSet::from_bytes(&[0b10100010]); + let b = BitSet::from_bytes(&[0b00000000]); + let c = BitSet::new(); + + assert_eq!(a.cmp(&b), Greater); + assert_eq!(a.cmp(&c), Greater); + assert_eq!(b.cmp(&a), Less); + assert_eq!(b.cmp(&c), Equal); + assert_eq!(c.cmp(&a), Less); + assert_eq!(c.cmp(&b), Equal); + } + + #[test] + fn test_bit_set_shrink_to_fit_new() { + // There was a strange bug where we refused to truncate to 0 + // and this would end up actually growing the array in a way + // that (safely corrupted the state). + let mut a = BitSet::new(); + assert_eq!(a.len(), 0); + assert_eq!(a.capacity(), 0); + a.shrink_to_fit(); + assert_eq!(a.len(), 0); + assert_eq!(a.capacity(), 0); + assert!(!a.contains(1)); + a.insert(3); + assert!(a.contains(3)); + assert_eq!(a.len(), 1); + assert!(a.capacity() > 0); + a.shrink_to_fit(); + assert!(a.contains(3)); + assert_eq!(a.len(), 1); + assert!(a.capacity() > 0); + } + + #[test] + fn test_bit_set_shrink_to_fit() { + let mut a = BitSet::new(); + assert_eq!(a.len(), 0); + assert_eq!(a.capacity(), 0); + a.insert(259); + a.insert(98); + a.insert(3); + assert_eq!(a.len(), 3); + assert!(a.capacity() > 0); + assert!(!a.contains(1)); + assert!(a.contains(259)); + assert!(a.contains(98)); + assert!(a.contains(3)); + + a.shrink_to_fit(); + assert!(!a.contains(1)); + assert!(a.contains(259)); + assert!(a.contains(98)); + assert!(a.contains(3)); + assert_eq!(a.len(), 3); + assert!(a.capacity() > 0); + + let old_cap = a.capacity(); + assert!(a.remove(259)); + a.shrink_to_fit(); + assert!(a.capacity() < old_cap, "{} {}", a.capacity(), old_cap); + assert!(!a.contains(1)); + assert!(!a.contains(259)); + assert!(a.contains(98)); + assert!(a.contains(3)); + assert_eq!(a.len(), 2); + + let old_cap2 = a.capacity(); + a.clear(); + assert_eq!(a.capacity(), old_cap2); + assert_eq!(a.len(), 0); + assert!(!a.contains(1)); + assert!(!a.contains(259)); + assert!(!a.contains(98)); + assert!(!a.contains(3)); + + a.insert(512); + assert!(a.capacity() > 0); + assert_eq!(a.len(), 1); + assert!(a.contains(512)); + assert!(!a.contains(1)); + assert!(!a.contains(259)); + assert!(!a.contains(98)); + assert!(!a.contains(3)); + + a.remove(512); + a.shrink_to_fit(); + assert_eq!(a.capacity(), 0); + assert_eq!(a.len(), 0); + assert!(!a.contains(512)); + assert!(!a.contains(1)); + assert!(!a.contains(259)); + assert!(!a.contains(98)); + assert!(!a.contains(3)); + assert!(!a.contains(0)); + } + + #[test] + fn test_bit_vec_remove() { + let mut a = BitSet::new(); + + assert!(a.insert(1)); + assert!(a.remove(1)); + + assert!(a.insert(100)); + assert!(a.remove(100)); + + assert!(a.insert(1000)); + assert!(a.remove(1000)); + a.shrink_to_fit(); + } + + #[test] + fn test_bit_vec_clone() { + let mut a = BitSet::new(); + + assert!(a.insert(1)); + assert!(a.insert(100)); + assert!(a.insert(1000)); + + let mut b = a.clone(); + + assert!(a == b); + + assert!(b.remove(1)); + assert!(a.contains(1)); + + assert!(a.remove(1000)); + assert!(b.contains(1000)); + } + + /* + #[test] + fn test_bit_set_append() { + let mut a = BitSet::new(); + a.insert(2); + a.insert(6); + + let mut b = BitSet::new(); + b.insert(1); + b.insert(3); + b.insert(6); + + a.append(&mut b); + + assert_eq!(a.len(), 4); + assert_eq!(b.len(), 0); + assert!(b.capacity() >= 6); + + assert_eq!(a, BitSet::from_bytes(&[0b01110010])); + } + + #[test] + fn test_bit_set_split_off() { + // Split at 0 + let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010, + 0b00110011, 0b01101011, 0b10101101]); + + let b = a.split_off(0); + + assert_eq!(a.len(), 0); + assert_eq!(b.len(), 21); + + assert_eq!(b, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010, + 0b00110011, 0b01101011, 0b10101101]); + + // Split behind last element + let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010, + 0b00110011, 0b01101011, 0b10101101]); + + let b = a.split_off(50); + + assert_eq!(a.len(), 21); + assert_eq!(b.len(), 0); + + assert_eq!(a, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010, + 0b00110011, 0b01101011, 0b10101101])); + + // Split at arbitrary element + let mut a = BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010, + 0b00110011, 0b01101011, 0b10101101]); + + let b = a.split_off(34); + + assert_eq!(a.len(), 12); + assert_eq!(b.len(), 9); + + assert_eq!(a, BitSet::from_bytes(&[0b10100000, 0b00010010, 0b10010010, + 0b00110011, 0b01000000])); + assert_eq!(b, BitSet::from_bytes(&[0, 0, 0, 0, + 0b00101011, 0b10101101])); + } + */ +} + +#[cfg(all(test, feature = "nightly"))] +mod bench { + use super::BitSet; + use bit_vec::BitVec; + use rand::{thread_rng, Rng, ThreadRng}; + + use test::{black_box, Bencher}; + + const BENCH_BITS: usize = 1 << 14; + const BITS: usize = 32; + + fn rng() -> ThreadRng { + thread_rng() + } + + #[bench] + fn bench_bit_vecset_small(b: &mut Bencher) { + let mut r = rng(); + let mut bit_vec = BitSet::new(); + b.iter(|| { + for _ in 0..100 { + bit_vec.insert((r.next_u32() as usize) % BITS); + } + black_box(&bit_vec); + }); + } + + #[bench] + fn bench_bit_vecset_big(b: &mut Bencher) { + let mut r = rng(); + let mut bit_vec = BitSet::new(); + b.iter(|| { + for _ in 0..100 { + bit_vec.insert((r.next_u32() as usize) % BENCH_BITS); + } + black_box(&bit_vec); + }); + } + + #[bench] + fn bench_bit_vecset_iter(b: &mut Bencher) { + let bit_vec = BitSet::from_bit_vec(BitVec::from_fn(BENCH_BITS, |idx| idx % 3 == 0)); + b.iter(|| { + let mut sum = 0; + for idx in &bit_vec { + sum += idx as usize; + } + sum + }) + } +} |