diff options
Diffstat (limited to '')
| -rw-r--r-- | vendor/fixedbitset/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | vendor/fixedbitset/Cargo.toml | 29 | ||||
| -rw-r--r-- | vendor/fixedbitset/LICENSE-APACHE | 201 | ||||
| -rw-r--r-- | vendor/fixedbitset/LICENSE-MIT | 25 | ||||
| -rw-r--r-- | vendor/fixedbitset/README.rst | 92 | ||||
| -rw-r--r-- | vendor/fixedbitset/benches/benches.rs | 133 | ||||
| -rw-r--r-- | vendor/fixedbitset/src/lib.rs | 1375 | ||||
| -rw-r--r-- | vendor/fixedbitset/src/range.rs | 39 |
8 files changed, 1895 insertions, 0 deletions
diff --git a/vendor/fixedbitset/.cargo-checksum.json b/vendor/fixedbitset/.cargo-checksum.json new file mode 100644 index 000000000..c26ef7360 --- /dev/null +++ b/vendor/fixedbitset/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"eb36c9d8a9578911040f35e1a5246631071e416a0f62b62ab794c01c114bd7a7","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"ce592787ff2321feab698a4c612237f4378cc658ebb1d472913e5802cc47afb4","README.rst":"cf4612100ed6a0d47466565a1557cf3a82dc7ef864af6430fbd3b4b2f9108fa4","benches/benches.rs":"745803c7962409ba8a63635336ca5f6b971ef1dc8f46e2cdee2a8a0c6b86e9a9","src/lib.rs":"1e878c4af42b12557dc2c38f9848ff1cf3d72910171b9b2e121fbe95468a7eed","src/range.rs":"6c9fd2462e353221dcf63393a78783428995a9460de3e4c799bd00a273dda9d8"},"package":"37ab347416e802de484e4d03c7316c48f1ecb56574dfd4a46a80f173ce1de04d"}
\ No newline at end of file diff --git a/vendor/fixedbitset/Cargo.toml b/vendor/fixedbitset/Cargo.toml new file mode 100644 index 000000000..9f21fbfee --- /dev/null +++ b/vendor/fixedbitset/Cargo.toml @@ -0,0 +1,29 @@ +# 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 believe there's an error in this file please file an +# issue against the rust-lang/cargo repository. If you're +# editing this file be aware that the upstream Cargo.toml +# will likely look very different (and much more reasonable) + +[package] +name = "fixedbitset" +version = "0.2.0" +authors = ["bluss"] +description = "FixedBitSet is a simple bitset collection" +documentation = "https://docs.rs/fixedbitset/" +keywords = ["container", "data-structure", "bitvec", "bitset", "no_std"] +categories = ["data-structures"] +license = "MIT/Apache-2.0" +repository = "https://github.com/bluss/fixedbitset" +[package.metadata.release] +no-dev-version = true +tag-name = "{{version}}" + +[features] +default = ["std"] +std = [] diff --git a/vendor/fixedbitset/LICENSE-APACHE b/vendor/fixedbitset/LICENSE-APACHE new file mode 100644 index 000000000..16fe87b06 --- /dev/null +++ b/vendor/fixedbitset/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/vendor/fixedbitset/LICENSE-MIT b/vendor/fixedbitset/LICENSE-MIT new file mode 100644 index 000000000..327cc6174 --- /dev/null +++ b/vendor/fixedbitset/LICENSE-MIT @@ -0,0 +1,25 @@ +Copyright (c) 2015-2017 + +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/vendor/fixedbitset/README.rst b/vendor/fixedbitset/README.rst new file mode 100644 index 000000000..13727433e --- /dev/null +++ b/vendor/fixedbitset/README.rst @@ -0,0 +1,92 @@ + +fixedbitset +=========== + +A simple bitset container for Rust + +Please read the `API documentation here`__ + +__ https://docs.rs/fixedbitset/ + +|build_status|_ |crates|_ + +.. |build_status| image:: https://travis-ci.org/petgraph/fixedbitset.svg?branch=master +.. _build_status: https://travis-ci.org/petgraph/fixedbitset + +.. |crates| image:: http://meritbadge.herokuapp.com/fixedbitset +.. _crates: https://crates.io/crates/fixedbitset + +Recent Changes +-------------- + +- 0.2.0 + + + Add assign operators for the bit operations by @jrraymond + + Add ``symmetric_difference``, ``union_with``, ``intersection_with`` by @jrraymond + + Add ``is_subset``, ``is_superset``, ``is_disjoint`` by @nwn + + Add ``.toggle(i)`` method by @ShiroUsagi-san + + Add default feature "std" which can be disabled to make the crate not + link the std library. By @jonimake and @bluss + + Require Rust 1.31. + +- 0.1.9 + + + Add intersection, union, difference iterators by @jrraymond + + Add intersection: ``&`` and union: ``|`` operator implementations by @jrraymond + + Add Extend and FromIterator implementations (from sequences of bit indices) + by @jrraymond + +- 0.1.8 + + + Add missing ``#[inline]`` on the ones iterator + + Fix docs for ``insert_range, set_range`` + +- 0.1.7 + + + Add fast methods ``.insert_range``, ``.set_range`` by @kennytm + +- 0.1.6 + + + Add iterator ``.ones()`` by @mneumann + + Fix bug with ``.count_ones()`` where it would erronously have an + out-of-bounds panic for even block endpoints + +- 0.1.5 + + + Add method ``.count_ones(range)``. + +- 0.1.4 + + + Remove an assertion in ``.copy_bit(from, to)`` so that it is in line + with the documentation. The ``from`` bit does not need to be in bounds. + + Improve ``.grow()`` to use ``Vec::resize`` internally. + +- 0.1.3 + + + Add method ``.put()`` to enable a bit and return previous value + +- 0.1.2 + + + Add method ``.copy_bit()`` (by fuine) + + impl Default + +- 0.1.1 + + + Update documentation URL + +- 0.1.0 + + + Add method ``.grow()`` + +License +------- + +Dual-licensed to be compatible with the Rust project. + +Licensed under the Apache License, Version 2.0 +http://www.apache.org/licenses/LICENSE-2.0 or the MIT license +http://opensource.org/licenses/MIT, at your +option. This file may not be copied, modified, or distributed +except according to those terms. + + diff --git a/vendor/fixedbitset/benches/benches.rs b/vendor/fixedbitset/benches/benches.rs new file mode 100644 index 000000000..ac999b014 --- /dev/null +++ b/vendor/fixedbitset/benches/benches.rs @@ -0,0 +1,133 @@ +#![feature(test)] + +extern crate test; +extern crate fixedbitset; +use test::Bencher; +use fixedbitset::{FixedBitSet}; +use std::mem::size_of; + +#[inline] +fn iter_ones_using_contains<F: FnMut(usize)>(fb: &FixedBitSet, f: &mut F) { + for bit in 0 .. fb.len() { + if fb.contains(bit) { + f(bit); + } + } +} + +#[inline] +fn iter_ones_using_slice_directly<F: FnMut(usize)>(fb: &FixedBitSet, f: &mut F) { + for (block_idx, &block) in fb.as_slice().iter().enumerate() { + let mut bit_pos = block_idx * size_of::<u32>() * 8; + let mut block: u32 = block; + + while block != 0 { + if (block & 1) == 1 { + f(bit_pos); + } + block = block >> 1; + bit_pos += 1; + } + } +} + +#[bench] +fn bench_iter_ones_using_contains_all_zeros(b: &mut Bencher) { + const N: usize = 1_000_000; + let fb = FixedBitSet::with_capacity(N); + + b.iter(|| { + let mut count = 0; + iter_ones_using_contains(&fb, &mut |_bit| count += 1); + count + }); +} + +#[bench] +fn bench_iter_ones_using_contains_all_ones(b: &mut Bencher) { + const N: usize = 1_000_000; + let mut fb = FixedBitSet::with_capacity(N); + fb.insert_range(..); + + b.iter(|| { + let mut count = 0; + iter_ones_using_contains(&fb, &mut |_bit| count += 1); + count + }); +} + +#[bench] +fn bench_iter_ones_using_slice_directly_all_zero(b: &mut Bencher) { + const N: usize = 1_000_000; + let fb = FixedBitSet::with_capacity(N); + + b.iter(|| { + let mut count = 0; + iter_ones_using_slice_directly(&fb, &mut |_bit| count += 1); + count + }); +} + +#[bench] +fn bench_iter_ones_using_slice_directly_all_ones(b: &mut Bencher) { + const N: usize = 1_000_000; + let mut fb = FixedBitSet::with_capacity(N); + fb.insert_range(..); + + b.iter(|| { + let mut count = 0; + iter_ones_using_slice_directly(&fb, &mut |_bit| count += 1); + count + }); +} + +#[bench] +fn bench_iter_ones_all_zeros(b: &mut Bencher) { + const N: usize = 1_000_000; + let fb = FixedBitSet::with_capacity(N); + + b.iter(|| { + let mut count = 0; + for _ in fb.ones() { + count += 1; + } + count + }); +} + +#[bench] +fn bench_iter_ones_all_ones(b: &mut Bencher) { + const N: usize = 1_000_000; + let mut fb = FixedBitSet::with_capacity(N); + fb.insert_range(..); + + b.iter(|| { + let mut count = 0; + for _ in fb.ones() { + count += 1; + } + count + }); +} + +#[bench] +fn bench_insert_range(b: &mut Bencher) { + const N: usize = 1_000_000; + let mut fb = FixedBitSet::with_capacity(N); + + b.iter(|| { + fb.insert_range(..) + }); +} + +#[bench] +fn bench_insert_range_using_loop(b: &mut Bencher) { + const N: usize = 1_000_000; + let mut fb = FixedBitSet::with_capacity(N); + + b.iter(|| { + for i in 0..N { + fb.insert(i); + } + }); +} diff --git a/vendor/fixedbitset/src/lib.rs b/vendor/fixedbitset/src/lib.rs new file mode 100644 index 000000000..368eccf4e --- /dev/null +++ b/vendor/fixedbitset/src/lib.rs @@ -0,0 +1,1375 @@ +//! `FixedBitSet` is a simple fixed size set of bits. +//! +//! +//! ### Crate features +//! +//! - `std` (default feature) +//! Disabling this feature disables using std and instead uses crate alloc. +//! Requires Rust 1.36 to disable. +//! +//! ### Rust Version +//! +//! This version of fixedbitset requires Rust 1.31 or later. +//! +#![doc(html_root_url="https://docs.rs/fixedbitset/0.2/")] + +#![cfg_attr(not(feature = "std"), no_std)] + +#[cfg(not(feature = "std"))] +extern crate alloc; +#[cfg(not(feature = "std"))] +use alloc::{ + vec, + vec::Vec, +}; + +#[cfg(not(feature = "std"))] +use core as std; + +mod range; + +use std::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Index}; +use std::cmp::{Ord, Ordering}; +use std::iter::{Chain, FromIterator}; +pub use range::IndexRange; + +const BITS: usize = 32; +type Block = u32; + +#[inline] +fn div_rem(x: usize, d: usize) -> (usize, usize) +{ + (x / d, x % d) +} + +/// `FixedBitSet` is a simple fixed size set of bits that each can +/// be enabled (1 / **true**) or disabled (0 / **false**). +/// +/// The bit set has a fixed capacity in terms of enabling bits (and the +/// capacity can grow using the `grow` method). +#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Default)] +pub struct FixedBitSet { + data: Vec<Block>, + /// length in bits + length: usize, +} + +impl FixedBitSet +{ + /// Create a new **FixedBitSet** with a specific number of bits, + /// all initially clear. + pub fn with_capacity(bits: usize) -> Self + { + let (mut blocks, rem) = div_rem(bits, BITS); + blocks += (rem > 0) as usize; + FixedBitSet { + data: vec![0; blocks], + length: bits, + } + } + /// Grow capacity to **bits**, all new bits initialized to zero + pub fn grow(&mut self, bits: usize) { + let (mut blocks, rem) = div_rem(bits, BITS); + blocks += (rem > 0) as usize; + if bits > self.length { + self.length = bits; + self.data.resize(blocks, 0); + } + } + + /// Return the length of the `FixedBitSet` in bits. + #[inline] + pub fn len(&self) -> usize { self.length } + + /// Return **true** if the bit is enabled in the **FixedBitSet**, + /// **false** otherwise. + /// + /// Note: bits outside the capacity are always disabled. + /// + /// Note: Also available with index syntax: `bitset[bit]`. + #[inline] + pub fn contains(&self, bit: usize) -> bool + { + let (block, i) = div_rem(bit, BITS); + match self.data.get(block) { + None => false, + Some(b) => (b & (1 << i)) != 0, + } + } + + /// Clear all bits. + #[inline] + pub fn clear(&mut self) + { + for elt in &mut self.data[..] { + *elt = 0 + } + } + + /// Enable `bit`. + /// + /// **Panics** if **bit** is out of bounds. + #[inline] + pub fn insert(&mut self, bit: usize) + { + assert!(bit < self.length); + let (block, i) = div_rem(bit, BITS); + unsafe { + *self.data.get_unchecked_mut(block) |= 1 << i; + } + } + + /// Enable `bit`, and return its previous value. + /// + /// **Panics** if **bit** is out of bounds. + #[inline] + pub fn put(&mut self, bit: usize) -> bool + { + assert!(bit < self.length); + let (block, i) = div_rem(bit, BITS); + unsafe { + let word = self.data.get_unchecked_mut(block); + let prev = *word & (1 << i) != 0; + *word |= 1 << i; + prev + } + } + /// Toggle `bit` (inverting its state). + /// + /// ***Panics*** if **bit** is out of bounds + #[inline] + pub fn toggle(&mut self, bit: usize) { + assert!(bit < self.length); + let (block, i) = div_rem(bit, BITS); + unsafe { + *self.data.get_unchecked_mut(block) ^= 1 << i; + } + } + /// **Panics** if **bit** is out of bounds. + #[inline] + pub fn set(&mut self, bit: usize, enabled: bool) + { + assert!(bit < self.length); + let (block, i) = div_rem(bit, BITS); + unsafe { + let elt = self.data.get_unchecked_mut(block); + if enabled { + *elt |= 1 << i; + } else { + *elt &= !(1 << i); + } + } + } + + /// Copies boolean value from specified bit to the specified bit. + /// + /// **Panics** if **to** is out of bounds. + #[inline] + pub fn copy_bit(&mut self, from: usize, to: usize) + { + assert!(to < self.length); + let (to_block, t) = div_rem(to, BITS); + let enabled = self.contains(from); + unsafe { + let to_elt = self.data.get_unchecked_mut(to_block); + if enabled { + *to_elt |= 1 << t; + } else { + *to_elt &= !(1 << t); + } + } + } + + /// Count the number of set bits in the given bit range. + /// + /// Use `..` to count the whole content of the bitset. + /// + /// **Panics** if the range extends past the end of the bitset. + #[inline] + pub fn count_ones<T: IndexRange>(&self, range: T) -> usize + { + Masks::new(range, self.length) + .map(|(block, mask)| unsafe { + let value = *self.data.get_unchecked(block); + (value & mask).count_ones() as usize + }) + .sum() + } + + /// Sets every bit in the given range to the given state (`enabled`) + /// + /// Use `..` to toggle the whole bitset. + /// + /// **Panics** if the range extends past the end of the bitset. + #[inline] + pub fn set_range<T: IndexRange>(&mut self, range: T, enabled: bool) + { + for (block, mask) in Masks::new(range, self.length) { + unsafe { + if enabled { + *self.data.get_unchecked_mut(block) |= mask; + } else { + *self.data.get_unchecked_mut(block) &= !mask; + } + } + } + } + + /// Enables every bit in the given range. + /// + /// Use `..` to make the whole bitset ones. + /// + /// **Panics** if the range extends past the end of the bitset. + #[inline] + pub fn insert_range<T: IndexRange>(&mut self, range: T) + { + self.set_range(range, true); + } + + /// View the bitset as a slice of `u32` blocks + #[inline] + pub fn as_slice(&self) -> &[u32] + { + &self.data + } + + /// View the bitset as a mutable slice of `u32` blocks. Writing past the bitlength in the last + /// will cause `contains` to return potentially incorrect results for bits past the bitlength. + #[inline] + pub fn as_mut_slice(&mut self) -> &mut [u32] + { + &mut self.data + } + + /// Iterates over all enabled bits. + /// + /// Iterator element is the index of the `1` bit, type `usize`. + #[inline] + pub fn ones(&self) -> Ones { + match self.as_slice().split_first() { + Some((&block, rem)) => { + Ones { + current_bit_idx: 0, + current_block_idx: 0, + current_block: block, + remaining_blocks: rem + } + } + None => { + Ones { + current_bit_idx: 0, + current_block_idx: 0, + current_block: 0, + remaining_blocks: &[] + } + } + } + } + + /// Returns a lazy iterator over the intersection of two `FixedBitSet`s + pub fn intersection<'a>(&'a self, other: &'a FixedBitSet) -> Intersection<'a> + { + Intersection { + iter: self.ones(), + other: other, + } + } + + /// Returns a lazy iterator over the union of two `FixedBitSet`s. + pub fn union<'a>(&'a self, other: &'a FixedBitSet) -> Union<'a> + { + Union { + iter: self.ones().chain(other.difference(self)), + } + } + + /// Returns a lazy iterator over the difference of two `FixedBitSet`s. The difference of `a` + /// and `b` is the elements of `a` which are not in `b`. + pub fn difference<'a>(&'a self, other: &'a FixedBitSet) -> Difference<'a> + { + Difference { + iter: self.ones(), + other: other, + } + } + + /// Returns a lazy iterator over the symmetric difference of two `FixedBitSet`s. + /// The symmetric difference of `a` and `b` is the elements of one, but not both, sets. + pub fn symmetric_difference<'a>(&'a self, other: &'a FixedBitSet) -> SymmetricDifference<'a> + { + SymmetricDifference { + iter: self.difference(other).chain(other.difference(self)), + } + } + + /// In-place union of two `FixedBitSet`s. + pub fn union_with(&mut self, other: &FixedBitSet) + { + if other.len() >= self.len() { + self.grow(other.len()); + } + for (x, y) in self.data.iter_mut().zip(other.data.iter()) { + *x |= *y; + } + } + + /// In-place intersection of two `FixedBitSet`s. + pub fn intersect_with(&mut self, other: &FixedBitSet) + { + for (x, y) in self.data.iter_mut().zip(other.data.iter()) { + *x &= *y; + } + let mn = std::cmp::min(self.data.len(), other.data.len()); + for wd in &mut self.data[mn..] { + *wd = 0; + } + } + + /// In-place symmetric difference of two `FixedBitSet`s. + pub fn symmetric_difference_with(&mut self, other: &FixedBitSet) + { + if other.len() >= self.len() { + self.grow(other.len()); + } + for (x, y) in self.data.iter_mut().zip(other.data.iter()) { + *x ^= *y; + } + } + + /// Returns `true` if `self` has no elements in common with `other`. This + /// is equivalent to checking for an empty intersection. + pub fn is_disjoint(&self, other: &FixedBitSet) -> bool { + self.data.iter().zip(other.data.iter()).all(|(x, y)| x & y == 0) + } + + /// Returns `true` if the set is a subset of another, i.e. `other` contains + /// at least all the values in `self`. + pub fn is_subset(&self, other: &FixedBitSet) -> bool { + self.data.iter().zip(other.data.iter()).all(|(x, y)| x & !y == 0) && + self.data.iter().skip(other.data.len()).all(|x| *x == 0) + } + + /// Returns `true` if the set is a superset of another, i.e. `self` contains + /// at least all the values in `other`. + pub fn is_superset(&self, other: &FixedBitSet) -> bool { + other.is_subset(self) + } +} + +/// An iterator producing elements in the difference of two sets. +/// +/// This struct is created by the [`FixedBitSet::difference`] method. +pub struct Difference<'a> { + iter: Ones<'a>, + other: &'a FixedBitSet, +} + +impl<'a> Iterator for Difference<'a> { + type Item = usize; + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + while let Some(nxt) = self.iter.next() { + if !self.other.contains(nxt) { + return Some(nxt); + } + } + None + } +} + +/// An iterator producing elements in the symmetric difference of two sets. +/// +/// This struct is created by the [`FixedBitSet::symmetric_difference`] method. +pub struct SymmetricDifference<'a> { + iter: Chain<Difference<'a>, Difference<'a>>, +} + +impl<'a> Iterator for SymmetricDifference<'a> { + type Item = usize; + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + self.iter.next() + } +} + + +/// An iterator producing elements in the intersection of two sets. +/// +/// This struct is created by the [`FixedBitSet::intersection`] method. +pub struct Intersection<'a> { + iter: Ones<'a>, + other: &'a FixedBitSet, +} + +impl<'a> Iterator for Intersection<'a> { + type Item = usize; // the bit position of the '1' + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + while let Some(nxt) = self.iter.next() { + if self.other.contains(nxt) { + return Some(nxt); + } + } + None + } +} + +/// An iterator producing elements in the union of two sets. +/// +/// This struct is created by the [`FixedBitSet::union`] method. +pub struct Union<'a> { + iter: Chain<Ones<'a>, Difference<'a>>, +} + +impl<'a> Iterator for Union<'a> { + type Item = usize; + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + self.iter.next() + } +} + + +struct Masks { + first_block: usize, + first_mask: Block, + last_block: usize, + last_mask: Block, +} + +impl Masks { + #[inline] + fn new<T: IndexRange>(range: T, length: usize) -> Masks { + let start = range.start().unwrap_or(0); + let end = range.end().unwrap_or(length); + assert!(start <= end && end <= length); + + let (first_block, first_rem) = div_rem(start, BITS); + let (last_block, last_rem) = div_rem(end, BITS); + + Masks { + first_block: first_block as usize, + first_mask: Block::max_value() << first_rem, + last_block: last_block as usize, + last_mask: (Block::max_value() >> 1) >> (BITS - last_rem - 1), + // this is equivalent to `MAX >> (BITS - x)` with correct semantics when x == 0. + } + } +} + +impl Iterator for Masks { + type Item = (usize, Block); + #[inline] + fn next(&mut self) -> Option<Self::Item> { + match self.first_block.cmp(&self.last_block) { + Ordering::Less => { + let res = (self.first_block, self.first_mask); + self.first_block += 1; + self.first_mask = !0; + Some(res) + } + Ordering::Equal => { + let mask = self.first_mask & self.last_mask; + let res = if mask == 0 { + None + } else { + Some((self.first_block, mask)) + }; + self.first_block += 1; + res + } + Ordering::Greater => None, + } + } +} + + +/// An iterator producing the indices of the set bit in a set. +/// +/// This struct is created by the [`FixedBitSet::ones`] method. +pub struct Ones<'a> { + current_bit_idx: usize, + current_block_idx: usize, + remaining_blocks: &'a [Block], + current_block: Block +} + +impl<'a> Iterator for Ones<'a> { + type Item = usize; // the bit position of the '1' + + #[inline] + fn next(&mut self) -> Option<Self::Item> { + let mut block = self.current_block; + let mut idx = self.current_bit_idx; + + loop { + loop { + if (block & 1) == 1 { + self.current_block = block >> 1; + self.current_bit_idx = idx + 1; + return Some(idx); + } + // reordering the two lines below makes a huge (2x) difference in performance! + block = block >> 1; + idx += 1; + if block == 0 { + break; + } + } + + // go to next block + match self.remaining_blocks.split_first() { + Some((&next_block, rest)) => { + self.remaining_blocks = rest; + self.current_block_idx += 1; + idx = self.current_block_idx * BITS; + block = next_block; + } + None => { + // last block => done + return None; + } + } + } + } +} + +impl Clone for FixedBitSet +{ + #[inline] + fn clone(&self) -> Self + { + FixedBitSet { + data: self.data.clone(), + length: self.length, + } + } +} + +/// Return **true** if the bit is enabled in the bitset, +/// or **false** otherwise. +/// +/// Note: bits outside the capacity are always disabled, and thus +/// indexing a FixedBitSet will not panic. +impl Index<usize> for FixedBitSet +{ + type Output = bool; + + #[inline] + fn index(&self, bit: usize) -> &bool + { + if self.contains(bit) { + &true + } else { + &false + } + } +} + +/// Sets the bit at index **i** to **true** for each item **i** in the input **src**. +impl Extend<usize> for FixedBitSet +{ + fn extend<I: IntoIterator<Item=usize>>(&mut self, src: I) { + let iter = src.into_iter(); + for i in iter { + if i >= self.len() { + self.grow(i + 1); + } + self.put(i); + } + } +} + +/// Return a FixedBitSet containing bits set to **true** for every bit index in +/// the iterator, other bits are set to **false**. +impl FromIterator<usize> for FixedBitSet +{ + fn from_iter<I: IntoIterator<Item=usize>>(src: I) -> Self { + let mut fbs = FixedBitSet::with_capacity(0); + fbs.extend(src); + fbs + } +} + +impl <'a> BitAnd for &'a FixedBitSet +{ + type Output = FixedBitSet; + fn bitand(self, other: &FixedBitSet) -> FixedBitSet { + let (short, long) = { + if self.len() <= other.len() { + (&self.data, &other.data) + } else { + (&other.data, &self.data) + } + }; + let mut data = short.clone(); + for (data, block) in data.iter_mut().zip(long.iter()) { + *data &= *block; + } + let len = std::cmp::min(self.len(), other.len()); + FixedBitSet{data: data, length: len} + } +} + + +impl <'a> BitAndAssign for FixedBitSet +{ + fn bitand_assign(&mut self, other: Self) { + self.intersect_with(&other); + } +} + +impl <'a> BitOr for &'a FixedBitSet +{ + type Output = FixedBitSet; + fn bitor(self, other: &FixedBitSet) -> FixedBitSet { + let (short, long) = { + if self.len() <= other.len() { + (&self.data, &other.data) + } else { + (&other.data, &self.data) + } + }; + let mut data = long.clone(); + for (data, block) in data.iter_mut().zip(short.iter()) { + *data |= *block; + } + let len = std::cmp::max(self.len(), other.len()); + FixedBitSet{data: data, length: len} + } +} + +impl <'a> BitOrAssign for FixedBitSet +{ + fn bitor_assign(&mut self, other: Self) { + self.union_with(&other); + } +} + +impl <'a> BitXor for &'a FixedBitSet +{ + type Output = FixedBitSet; + fn bitxor(self, other: &FixedBitSet) -> FixedBitSet { + let (short, long) = { + if self.len() <= other.len() { + (&self.data, &other.data) + } else { + (&other.data, &self.data) + } + }; + let mut data = long.clone(); + for (data, block) in data.iter_mut().zip(short.iter()) { + *data ^= *block; + } + let len = std::cmp::max(self.len(), other.len()); + FixedBitSet{data: data, length: len} + } +} + +impl <'a> BitXorAssign for FixedBitSet +{ + fn bitxor_assign(&mut self, other: Self) { + self.symmetric_difference_with(&other); + } +} + +#[test] +fn it_works() { + const N: usize = 50; + let mut fb = FixedBitSet::with_capacity(N); + + + for i in 0..(N + 10) { + assert_eq!(fb.contains(i), false); + } + + fb.insert(10); + fb.set(11, false); + fb.set(12, false); + fb.set(12, true); + fb.set(N-1, true); + + assert!(fb.contains(10)); + assert!(!fb.contains(11)); + assert!(fb.contains(12)); + assert!(fb.contains(N-1)); + for i in 0..N { + let contain = i == 10 || i == 12 || i == N - 1; + assert_eq!(contain, fb[i]); + } + + fb.clear(); +} + +#[test] +fn grow() { + let mut fb = FixedBitSet::with_capacity(48); + for i in 0..fb.len() { + fb.set(i, true); + } + + let old_len = fb.len(); + fb.grow(72); + for j in 0..fb.len() { + assert_eq!(fb.contains(j), j < old_len); + } + fb.set(64, true); + assert!(fb.contains(64)); +} + +#[test] +fn test_toggle() { + let mut fb = FixedBitSet::with_capacity(16); + fb.toggle(1); + fb.put(2); + fb.toggle(2); + fb.put(3); + assert!(fb.contains(1)); + assert!(!fb.contains(2)); + assert!(fb.contains(3)); +} + +#[test] +fn copy_bit() { + let mut fb = FixedBitSet::with_capacity(48); + for i in 0..fb.len() { + fb.set(i, true); + } + fb.set(42, false); + fb.copy_bit(42, 2); + assert!(!fb.contains(42)); + assert!(!fb.contains(2)); + assert!(fb.contains(1)); + fb.copy_bit(1, 42); + assert!(fb.contains(42)); + fb.copy_bit(1024, 42); + assert!(!fb[42]); +} + +#[test] +fn count_ones() { + let mut fb = FixedBitSet::with_capacity(100); + fb.set(11, true); + fb.set(12, true); + fb.set(7, true); + fb.set(35, true); + fb.set(40, true); + fb.set(77, true); + fb.set(95, true); + fb.set(50, true); + fb.set(99, true); + assert_eq!(fb.count_ones(..7), 0); + assert_eq!(fb.count_ones(..8), 1); + assert_eq!(fb.count_ones(..11), 1); + assert_eq!(fb.count_ones(..12), 2); + assert_eq!(fb.count_ones(..13), 3); + assert_eq!(fb.count_ones(..35), 3); + assert_eq!(fb.count_ones(..36), 4); + assert_eq!(fb.count_ones(..40), 4); + assert_eq!(fb.count_ones(..41), 5); + assert_eq!(fb.count_ones(50..), 4); + assert_eq!(fb.count_ones(70..95), 1); + assert_eq!(fb.count_ones(70..96), 2); + assert_eq!(fb.count_ones(70..99), 2); + assert_eq!(fb.count_ones(..), 9); + assert_eq!(fb.count_ones(0..100), 9); + assert_eq!(fb.count_ones(0..0), 0); + assert_eq!(fb.count_ones(100..100), 0); + assert_eq!(fb.count_ones(7..), 9); + assert_eq!(fb.count_ones(8..), 8); +} + +#[test] +fn ones() { + let mut fb = FixedBitSet::with_capacity(100); + fb.set(11, true); + fb.set(12, true); + fb.set(7, true); + fb.set(35, true); + fb.set(40, true); + fb.set(77, true); + fb.set(95, true); + fb.set(50, true); + fb.set(99, true); + + let ones: Vec<_> = fb.ones().collect(); + + assert_eq!(vec![7, 11, 12, 35, 40, 50, 77, 95, 99], ones); +} + +#[test] +fn iter_ones_range() { + fn test_range(from: usize, to: usize, capa: usize) { + assert!(to <= capa); + let mut fb = FixedBitSet::with_capacity(capa); + for i in from..to { + fb.insert(i); + } + let ones: Vec<_> = fb.ones().collect(); + let expected: Vec<_> = (from..to).collect(); + assert_eq!(expected, ones); + } + + for i in 0..100 { + test_range(i, 100, 100); + test_range(0, i, 100); + } +} + +#[should_panic] +#[test] +fn count_ones_oob() { + let fb = FixedBitSet::with_capacity(100); + fb.count_ones(90..101); +} + +#[should_panic] +#[test] +fn count_ones_negative_range() { + let fb = FixedBitSet::with_capacity(100); + fb.count_ones(90..80); +} + +#[test] +fn count_ones_panic() { + for i in 1..128 { + let fb = FixedBitSet::with_capacity(i); + for j in 0..fb.len() + 1 { + for k in j..fb.len() + 1 { + assert_eq!(fb.count_ones(j..k), 0); + } + } + } +} + + +#[test] +fn default() { + let fb = FixedBitSet::default(); + assert_eq!(fb.len(), 0); +} + +#[test] +fn insert_range() { + let mut fb = FixedBitSet::with_capacity(97); + fb.insert_range(..3); + fb.insert_range(9..32); + fb.insert_range(37..81); + fb.insert_range(90..); + for i in 0..97 { + assert_eq!(fb.contains(i), i<3 || 9<=i&&i<32 || 37<=i&&i<81 || 90<=i); + } + assert!(!fb.contains(97)); + assert!(!fb.contains(127)); + assert!(!fb.contains(128)); +} + +#[test] +fn set_range() { + let mut fb = FixedBitSet::with_capacity(48); + fb.insert_range(..); + + fb.set_range(..32, false); + fb.set_range(37.., false); + fb.set_range(5..9, true); + fb.set_range(40..40, true); + + for i in 0..48 { + assert_eq!(fb.contains(i), 5<=i&&i<9 || 32<=i&&i<37); + } + assert!(!fb.contains(48)); + assert!(!fb.contains(64)); +} + +#[test] +fn bitand_equal_lengths() { + let len = 109; + let a_end = 59; + let b_start = 23; + let mut a = FixedBitSet::with_capacity(len); + let mut b = FixedBitSet::with_capacity(len); + a.set_range(..a_end, true); + b.set_range(b_start.., true); + let ab = &a & &b; + for i in 0..b_start { + assert!(!ab.contains(i)); + } + for i in b_start..a_end { + assert!(ab.contains(i)); + } + for i in a_end..len { + assert!(!ab.contains(i)); + } + assert_eq!(a.len(), ab.len()); +} + +#[test] +fn bitand_first_smaller() { + let a_len = 113; + let b_len = 137; + let len = std::cmp::min(a_len, b_len); + let a_end = 97; + let b_start = 89; + let mut a = FixedBitSet::with_capacity(a_len); + let mut b = FixedBitSet::with_capacity(b_len); + a.set_range(..a_end, true); + b.set_range(b_start.., true); + let ab = &a & &b; + for i in 0..b_start { + assert!(!ab.contains(i)); + } + for i in b_start..a_end { + assert!(ab.contains(i)); + } + for i in a_end..len { + assert!(!ab.contains(i)); + } + assert_eq!(a.len(), ab.len()); +} + +#[test] +fn bitand_first_larger() { + let a_len = 173; + let b_len = 137; + let len = std::cmp::min(a_len, b_len); + let a_end = 107; + let b_start = 43; + let mut a = FixedBitSet::with_capacity(a_len); + let mut b = FixedBitSet::with_capacity(b_len); + a.set_range(..a_end, true); + b.set_range(b_start.., true); + let ab = &a & &b; + for i in 0..b_start { + assert!(!ab.contains(i)); + } + for i in b_start..a_end { + assert!(ab.contains(i)); + } + for i in a_end..len { + assert!(!ab.contains(i)); + } + assert_eq!(b.len(), ab.len()); +} + +#[test] +fn intersection() { + let len = 109; + let a_end = 59; + let b_start = 23; + let mut a = FixedBitSet::with_capacity(len); + let mut b = FixedBitSet::with_capacity(len); + a.set_range(..a_end, true); + b.set_range(b_start.., true); + + let ab = a.intersection(&b).collect::<FixedBitSet>(); + + for i in 0..b_start { + assert!(!ab.contains(i)); + } + for i in b_start..a_end { + assert!(ab.contains(i)); + } + for i in a_end..len { + assert!(!ab.contains(i)); + } +} + +#[test] +fn union() { + let a_len = 173; + let b_len = 137; + let a_start = 139; + let b_end = 107; + let mut a = FixedBitSet::with_capacity(a_len); + let mut b = FixedBitSet::with_capacity(b_len); + a.set_range(a_start.., true); + b.set_range(..b_end, true); + let ab = a.union(&b).collect::<FixedBitSet>(); + for i in a_start..a_len { + assert!(ab.contains(i)); + } + for i in 0..b_end { + assert!(ab.contains(i)); + } + for i in b_end..a_start { + assert!(!ab.contains(i)); + } +} + +#[test] +fn difference() { + let a_len = 83; + let b_len = 151; + let a_start = 0; + let a_end = 79; + let b_start = 53; + let mut a = FixedBitSet::with_capacity(a_len); + let mut b = FixedBitSet::with_capacity(b_len); + a.set_range(a_start..a_end, true); + b.set_range(b_start..b_len, true); + let a_diff_b = a.difference(&b).collect::<FixedBitSet>(); + for i in a_start..b_start { + assert!(a_diff_b.contains(i)); + } + for i in b_start..b_len { + assert!(!a_diff_b.contains(i)); + } +} + +#[test] +fn symmetric_difference() { + let a_len = 83; + let b_len = 151; + let a_start = 47; + let a_end = 79; + let b_start = 53; + let mut a = FixedBitSet::with_capacity(a_len); + let mut b = FixedBitSet::with_capacity(b_len); + a.set_range(a_start..a_end, true); + b.set_range(b_start..b_len, true); + let a_sym_diff_b = a.symmetric_difference(&b).collect::<FixedBitSet>(); + for i in 0..a_start { + assert!(!a_sym_diff_b.contains(i)); + } + for i in a_start..b_start { + assert!(a_sym_diff_b.contains(i)); + } + for i in b_start..a_end { + assert!(!a_sym_diff_b.contains(i)); + } + for i in a_end..b_len { + assert!(a_sym_diff_b.contains(i)); + } +} + +#[test] +fn bitor_equal_lengths() { + let len = 109; + let a_start = 17; + let a_end = 23; + let b_start = 19; + let b_end = 59; + let mut a = FixedBitSet::with_capacity(len); + let mut b = FixedBitSet::with_capacity(len); + a.set_range(a_start..a_end, true); + b.set_range(b_start..b_end, true); + let ab = &a | &b; + for i in 0..a_start { + assert!(!ab.contains(i)); + } + for i in a_start..b_end { + assert!(ab.contains(i)); + } + for i in b_end..len { + assert!(!ab.contains(i)); + } + assert_eq!(ab.len(), len); +} + +#[test] +fn bitor_first_smaller() { + let a_len = 113; + let b_len = 137; + let a_end = 89; + let b_start = 97; + let mut a = FixedBitSet::with_capacity(a_len); + let mut b = FixedBitSet::with_capacity(b_len); + a.set_range(..a_end, true); + b.set_range(b_start.., true); + let ab = &a | &b; + for i in 0..a_end { + assert!(ab.contains(i)); + } + for i in a_end..b_start { + assert!(!ab.contains(i)); + } + for i in b_start..b_len { + assert!(ab.contains(i)); + } + assert_eq!(b_len, ab.len()); +} + +#[test] +fn bitor_first_larger() { + let a_len = 173; + let b_len = 137; + let a_start = 139; + let b_end = 107; + let mut a = FixedBitSet::with_capacity(a_len); + let mut b = FixedBitSet::with_capacity(b_len); + a.set_range(a_start.., true); + b.set_range(..b_end, true); + let ab = &a | &b; + for i in a_start..a_len { + assert!(ab.contains(i)); + } + for i in 0..b_end { + assert!(ab.contains(i)); + } + for i in b_end..a_start { + assert!(!ab.contains(i)); + } + assert_eq!(a_len, ab.len()); +} + +#[test] +fn bitxor_equal_lengths() { + let len = 109; + let a_end = 59; + let b_start = 23; + let mut a = FixedBitSet::with_capacity(len); + let mut b = FixedBitSet::with_capacity(len); + a.set_range(..a_end, true); + b.set_range(b_start.., true); + let ab = &a ^ &b; + for i in 0..b_start { + assert!(ab.contains(i)); + } + for i in b_start..a_end { + assert!(!ab.contains(i)); + } + for i in a_end..len { + assert!(ab.contains(i)); + } + assert_eq!(a.len(), ab.len()); +} + +#[test] +fn bitxor_first_smaller() { + let a_len = 113; + let b_len = 137; + let len = std::cmp::max(a_len, b_len); + let a_end = 97; + let b_start = 89; + let mut a = FixedBitSet::with_capacity(a_len); + let mut b = FixedBitSet::with_capacity(b_len); + a.set_range(..a_end, true); + b.set_range(b_start.., true); + let ab = &a ^ &b; + for i in 0..b_start { + assert!(ab.contains(i)); + } + for i in b_start..a_end { + assert!(!ab.contains(i)); + } + for i in a_end..len { + assert!(ab.contains(i)); + } + assert_eq!(b.len(), ab.len()); +} + +#[test] +fn bitxor_first_larger() { + let a_len = 173; + let b_len = 137; + let len = std::cmp::max(a_len, b_len); + let a_end = 107; + let b_start = 43; + let mut a = FixedBitSet::with_capacity(a_len); + let mut b = FixedBitSet::with_capacity(b_len); + a.set_range(..a_end, true); + b.set_range(b_start.., true); + let ab = &a ^ &b; + for i in 0..b_start { + assert!(ab.contains(i)); + } + for i in b_start..a_end { + assert!(!ab.contains(i)); + } + for i in a_end..b_len { + assert!(ab.contains(i)); + } + for i in b_len..len { + assert!(!ab.contains(i)); + } + assert_eq!(a.len(), ab.len()); +} + +#[test] +fn bitand_assign_shorter() { + let a_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101]; + let b_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32]; + let a_and_b: Vec<usize> = vec![2, 7, 31, 32]; + let mut a = a_ones.iter().cloned().collect::<FixedBitSet>(); + let b = b_ones.iter().cloned().collect::<FixedBitSet>(); + a &= b; + let res = a.ones().collect::<Vec<usize>>(); + + assert!(res == a_and_b); +} + +#[test] +fn bitand_assign_longer() { + let a_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32]; + let b_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101]; + let a_and_b: Vec<usize> = vec![2, 7, 31, 32]; + let mut a = a_ones.iter().cloned().collect::<FixedBitSet>(); + let b = b_ones.iter().cloned().collect::<FixedBitSet>(); + a &= b; + let res = a.ones().collect::<Vec<usize>>(); + assert!(res == a_and_b); +} + +#[test] +fn bitor_assign_shorter() { + let a_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101]; + let b_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32]; + let a_or_b: Vec<usize> = vec![2, 3, 7, 8, 11, 19, 23, 31, 32, 37, 41, 43, 47, 71, 73, 101]; + let mut a = a_ones.iter().cloned().collect::<FixedBitSet>(); + let b = b_ones.iter().cloned().collect::<FixedBitSet>(); + a |= b; + let res = a.ones().collect::<Vec<usize>>(); + assert!(res == a_or_b); +} + +#[test] +fn bitor_assign_longer() { + let a_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32]; + let b_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101]; + let a_or_b: Vec<usize> = vec![2, 3, 7, 8, 11, 19, 23, 31, 32, 37, 41, 43, 47, 71, 73, 101]; + let mut a = a_ones.iter().cloned().collect::<FixedBitSet>(); + let b = b_ones.iter().cloned().collect::<FixedBitSet>(); + a |= b; + let res = a.ones().collect::<Vec<usize>>(); + assert!(res == a_or_b); +} + +#[test] +fn bitxor_assign_shorter() { + let a_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101]; + let b_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32]; + let a_xor_b: Vec<usize> = vec![3, 8, 11, 19, 23, 37, 41, 43, 47, 71, 73, 101]; + let mut a = a_ones.iter().cloned().collect::<FixedBitSet>(); + let b = b_ones.iter().cloned().collect::<FixedBitSet>(); + a ^= b; + let res = a.ones().collect::<Vec<usize>>(); + assert!(res == a_xor_b); +} + +#[test] +fn bitxor_assign_longer() { + let a_ones: Vec<usize> = vec![2, 7, 8, 11, 23, 31, 32]; + let b_ones: Vec<usize> = vec![2, 3, 7, 19, 31, 32, 37, 41, 43, 47, 71, 73, 101]; + let a_xor_b: Vec<usize> = vec![3, 8, 11, 19, 23, 37, 41, 43, 47, 71, 73, 101]; + let mut a = a_ones.iter().cloned().collect::<FixedBitSet>(); + let b = b_ones.iter().cloned().collect::<FixedBitSet>(); + a ^= b; + let res = a.ones().collect::<Vec<usize>>(); + assert!(res == a_xor_b); +} + +#[test] +fn subset_superset_shorter() { + let a_ones: Vec<usize> = vec![7, 31, 32, 63]; + let b_ones: Vec<usize> = vec![2, 7, 19, 31, 32, 37, 41, 43, 47, 63, 73, 101]; + let mut a = a_ones.iter().cloned().collect::<FixedBitSet>(); + let b = b_ones.iter().cloned().collect::<FixedBitSet>(); + assert!(a.is_subset(&b) && b.is_superset(&a)); + a.insert(14); + assert!(!a.is_subset(&b) && !b.is_superset(&a)); +} + +#[test] +fn subset_superset_longer() { + let a_len = 153; + let b_len = 75; + let a_ones: Vec<usize> = vec![7, 31, 32, 63]; + let b_ones: Vec<usize> = vec![2, 7, 19, 31, 32, 37, 41, 43, 47, 63, 73]; + let mut a = FixedBitSet::with_capacity(a_len); + let mut b = FixedBitSet::with_capacity(b_len); + a.extend(a_ones.iter().cloned()); + b.extend(b_ones.iter().cloned()); + assert!(a.is_subset(&b) && b.is_superset(&a)); + a.insert(100); + assert!(!a.is_subset(&b) && !b.is_superset(&a)); +} + +#[test] +fn is_disjoint_first_shorter() { + let a_len = 75; + let b_len = 153; + let a_ones: Vec<usize> = vec![2, 19, 32, 37, 41, 43, 47, 73]; + let b_ones: Vec<usize> = vec![7, 23, 31, 63, 124]; + let mut a = FixedBitSet::with_capacity(a_len); + let mut b = FixedBitSet::with_capacity(b_len); + a.extend(a_ones.iter().cloned()); + b.extend(b_ones.iter().cloned()); + assert!(a.is_disjoint(&b)); + a.insert(63); + assert!(!a.is_disjoint(&b)); +} + +#[test] +fn is_disjoint_first_longer() { + let a_ones: Vec<usize> = vec![2, 19, 32, 37, 41, 43, 47, 73, 101]; + let b_ones: Vec<usize> = vec![7, 23, 31, 63]; + let a = a_ones.iter().cloned().collect::<FixedBitSet>(); + let mut b = b_ones.iter().cloned().collect::<FixedBitSet>(); + assert!(a.is_disjoint(&b)); + b.insert(2); + assert!(!a.is_disjoint(&b)); +} + +#[test] +fn extend_on_empty() { + let items: Vec<usize> = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 167]; + let mut fbs = FixedBitSet::with_capacity(0); + fbs.extend(items.iter().cloned()); + let ones = fbs.ones().collect::<Vec<usize>>(); + assert!(ones == items); +} + +#[test] +fn extend() { + let items: Vec<usize> = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 167]; + let mut fbs = FixedBitSet::with_capacity(168); + let new: Vec<usize> = vec![7, 37, 67, 137]; + for i in &new { + fbs.put(*i); + } + + fbs.extend(items.iter().cloned()); + + let ones = fbs.ones().collect::<Vec<usize>>(); + let expected = { + let mut tmp = items.clone(); + tmp.extend(new); + tmp.sort(); + tmp.dedup(); + tmp + }; + + assert!(ones == expected); +} + +#[test] +fn from_iterator() { + let items: Vec<usize> = vec![0, 2, 4, 6, 8]; + let fb = items.iter().cloned().collect::<FixedBitSet>(); + for i in items { + assert!(fb.contains(i)); + } + for i in vec![1, 3, 5, 7] { + assert!(!fb.contains(i)); + } + assert_eq!(fb.len(), 9); +} + +#[test] +fn from_iterator_ones() { + let len = 257; + let mut fb = FixedBitSet::with_capacity(len); + for i in (0..len).filter(|i| i % 7 == 0) { + fb.put(i); + } + fb.put(len - 1); + let dup = fb.ones().collect::<FixedBitSet>(); + + + assert_eq!(fb.len(), dup.len()); + assert_eq!(fb.ones().collect::<Vec<usize>>(), dup.ones().collect::<Vec<usize>>()); +} diff --git a/vendor/fixedbitset/src/range.rs b/vendor/fixedbitset/src/range.rs new file mode 100644 index 000000000..aaa48961b --- /dev/null +++ b/vendor/fixedbitset/src/range.rs @@ -0,0 +1,39 @@ +use std::ops::{ + RangeFull, + RangeFrom, + RangeTo, + Range, +}; + +// Taken from https://github.com/bluss/odds/blob/master/src/range.rs. + +/// **IndexRange** is implemented by Rust's built-in range types, produced +/// by range syntax like `..`, `a..`, `..b` or `c..d`. +pub trait IndexRange<T=usize> { + #[inline] + /// Start index (inclusive) + fn start(&self) -> Option<T> { None } + #[inline] + /// End index (exclusive) + fn end(&self) -> Option<T> { None } +} + + +impl<T> IndexRange<T> for RangeFull {} + +impl<T: Copy> IndexRange<T> for RangeFrom<T> { + #[inline] + fn start(&self) -> Option<T> { Some(self.start) } +} + +impl<T: Copy> IndexRange<T> for RangeTo<T> { + #[inline] + fn end(&self) -> Option<T> { Some(self.end) } +} + +impl<T: Copy> IndexRange<T> for Range<T> { + #[inline] + fn start(&self) -> Option<T> { Some(self.start) } + #[inline] + fn end(&self) -> Option<T> { Some(self.end) } +} |