diff options
Diffstat (limited to 'vendor/fixedbitset')
| -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, 0 insertions, 1895 deletions
diff --git a/vendor/fixedbitset/.cargo-checksum.json b/vendor/fixedbitset/.cargo-checksum.json deleted file mode 100644 index c26ef7360..000000000 --- a/vendor/fixedbitset/.cargo-checksum.json +++ /dev/null @@ -1 +0,0 @@ -{"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 deleted file mode 100644 index 9f21fbfee..000000000 --- a/vendor/fixedbitset/Cargo.toml +++ /dev/null @@ -1,29 +0,0 @@ -# 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 deleted file mode 100644 index 16fe87b06..000000000 --- a/vendor/fixedbitset/LICENSE-APACHE +++ /dev/null @@ -1,201 +0,0 @@ - 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 deleted file mode 100644 index 327cc6174..000000000 --- a/vendor/fixedbitset/LICENSE-MIT +++ /dev/null @@ -1,25 +0,0 @@ -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 deleted file mode 100644 index 13727433e..000000000 --- a/vendor/fixedbitset/README.rst +++ /dev/null @@ -1,92 +0,0 @@ - -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 deleted file mode 100644 index ac999b014..000000000 --- a/vendor/fixedbitset/benches/benches.rs +++ /dev/null @@ -1,133 +0,0 @@ -#![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 deleted file mode 100644 index 368eccf4e..000000000 --- a/vendor/fixedbitset/src/lib.rs +++ /dev/null @@ -1,1375 +0,0 @@ -//! `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 deleted file mode 100644 index aaa48961b..000000000 --- a/vendor/fixedbitset/src/range.rs +++ /dev/null @@ -1,39 +0,0 @@ -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) } -} |