Merge remote-tracking branch 'origin/upstream' am: fc3cbf2928 am: ae8ad4ad09
Original change: undetermined
Change-Id: I063c9089aeefd28726e0f89714bd9e9cc541c540
Signed-off-by: Automerger Merge Worker <[email protected]>
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
new file mode 100644
index 0000000..f918122
--- /dev/null
+++ b/.cargo_vcs_info.json
@@ -0,0 +1,6 @@
+{
+ "git": {
+ "sha1": "f1db5d17dabc4b8f3ba68c1228a3ee7601c7f33c"
+ },
+ "path_in_vcs": ""
+}
\ No newline at end of file
diff --git a/.github/Cargo.toml.wasm_ci b/.github/Cargo.toml.wasm_ci
new file mode 100644
index 0000000..6a6e4e0
--- /dev/null
+++ b/.github/Cargo.toml.wasm_ci
@@ -0,0 +1 @@
+wasm-bindgen-test = "0.3"
\ No newline at end of file
diff --git a/.github/workflows/rust.yml b/.github/workflows/rust.yml
new file mode 100644
index 0000000..3430893
--- /dev/null
+++ b/.github/workflows/rust.yml
@@ -0,0 +1,149 @@
+name: Continuous integration
+
+on:
+ push:
+ branches: [ master ]
+ pull_request:
+ branches: [ master ]
+
+env:
+ CARGO_TERM_COLOR: always
+ CARGO_INCREMENTAL: 0
+
+jobs:
+ # Ensure the crate builds on x86
+ build_x86_64:
+ runs-on: ubuntu-latest
+ strategy:
+ matrix:
+ rust: [stable, nightly]
+ features: ["+avx2", "+avx", "+sse2,+sse4.1", "+sse2"]
+ env:
+ RUSTFLAGS: "-C target-feature=${{matrix.features}} -D warnings"
+ steps:
+ - uses: actions/checkout@v4
+ - uses: dtolnay/rust-toolchain@stable
+ with:
+ target: x86_64-unknown-linux-gnu
+ toolchain: ${{ matrix.rust }}
+ components: clippy
+ - name: Tests (x86_64)
+ run: |
+ cargo clippy &&
+ cargo test -v --no-default-features --tests --lib &&
+ cargo build --verbose --features "$FEATURES" &&
+ cargo test --verbose --features "$FEATURES" &&
+ cargo test --verbose --release --features "$FEATURES"
+
+ # Ensure the crate builds on x86
+ build_MSRV:
+ runs-on: ubuntu-latest
+ strategy:
+ matrix:
+ rust: [1.56.0]
+ features: ["+avx2", "+sse2"]
+ env:
+ RUSTFLAGS: "-C target-feature=${{matrix.features}}"
+ steps:
+ - uses: actions/checkout@v4
+ - uses: dtolnay/rust-toolchain@stable
+ with:
+ target: x86_64-unknown-linux-gnu
+ toolchain: ${{ matrix.rust }}
+ components: clippy
+ - name: Tests (x86_64)
+ run: |
+ cargo clippy &&
+ cargo test -v --no-default-features --tests --lib &&
+ cargo build --verbose --features "$FEATURES" &&
+ cargo test --verbose --features "$FEATURES" &&
+ cargo test --verbose --release --features "$FEATURES"
+
+ # Ensure the crate builds on ARM
+ build_aarch64:
+ runs-on: macos-14
+ strategy:
+ matrix:
+ rust: [stable, nightly]
+ features: ["+neon", "-neon"]
+ env:
+ RUSTFLAGS: "-C target-feature=${{matrix.features}} -D warnings"
+ steps:
+ - uses: actions/checkout@v4
+ - uses: dtolnay/rust-toolchain@stable
+ with:
+ target: aarch64-apple-darwin
+ toolchain: ${{ matrix.rust }}
+ components: clippy
+ - name: Tests (aarch64)
+ run: |
+ cargo clippy &&
+ cargo test -v --no-default-features --tests --lib &&
+ cargo build --verbose --features "$FEATURES" &&
+ cargo test --verbose --features "$FEATURES" &&
+ cargo test --verbose --release --features "$FEATURES"
+
+ # Enforce rustfmt formatting
+ formatting:
+ runs-on: ubuntu-latest
+ strategy:
+ matrix:
+ # Run formatting checks only on stable
+ rust: [stable]
+ steps:
+ - uses: actions/checkout@v4
+ - uses: dtolnay/rust-toolchain@stable
+ with:
+ toolchain: ${{ matrix.rust }}
+ components: rustfmt
+ - name: Run Clippy
+ run: |
+ cargo fmt --all --check
+
+ # Ensure the benchmarks compile
+ benchmark_compiles:
+ runs-on: ubuntu-latest
+ strategy:
+ matrix:
+ # Check builds only on stable
+ rust: [stable]
+ steps:
+ - uses: actions/checkout@v4
+ - uses: dtolnay/rust-toolchain@stable
+ with:
+ toolchain: ${{ matrix.rust }}
+ components: clippy
+ - name: Run Clippy
+ run: |
+ cd benches
+ cargo bench --bench benches --no-run
+
+ build-wasm:
+ runs-on: ubuntu-latest
+ strategy:
+ matrix:
+ features: ["+simd128", "-simd128"]
+ env:
+ RUSTFLAGS: "-C target-feature=${{matrix.features}} -D warnings"
+ steps:
+ - uses: actions/checkout@v4
+ - name: Install
+ run: curl https://rustwasm.github.io/wasm-pack/installer/init.sh -sSf | sh
+ - run: cat .github/Cargo.toml.wasm_ci >> Cargo.toml
+ - run: wasm-pack test --headless --chrome
+ - run: wasm-pack test --headless --firefox
+
+ miri:
+ runs-on: ubuntu-latest
+ strategy:
+ matrix:
+ # Check builds only on nightly
+ rust: [nightly]
+ steps:
+ - uses: actions/checkout@v4
+ - uses: dtolnay/rust-toolchain@stable
+ with:
+ toolchain: ${{ matrix.rust }}
+ components: miri
+ - name: Run miri
+ run: cargo miri test
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..7f93f83
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,4 @@
+target/
+.idea/
+Cargo.lock
+.vscode
\ No newline at end of file
diff --git a/Android.bp b/Android.bp
new file mode 100644
index 0000000..8c46a04
--- /dev/null
+++ b/Android.bp
@@ -0,0 +1,56 @@
+// This file is generated by cargo_embargo.
+// Do not modify this file because the changes will be overridden on upgrade.
+
+package {
+ default_applicable_licenses: ["external_rust_crates_fixedbitset_license"],
+}
+
+license {
+ name: "external_rust_crates_fixedbitset_license",
+ visibility: [":__subpackages__"],
+ license_kinds: ["SPDX-license-identifier-Apache-2.0"],
+ license_text: ["LICENSE"],
+}
+
+rust_test {
+ name: "fixedbitset_test_tests_tests",
+ host_supported: true,
+ crate_name: "tests",
+ cargo_env_compat: true,
+ cargo_pkg_version: "0.5.7",
+ crate_root: "tests/tests.rs",
+ test_suites: ["general-tests"],
+ auto_gen_config: true,
+ test_options: {
+ unit_test: true,
+ },
+ edition: "2021",
+ features: [
+ "default",
+ "std",
+ ],
+ rustlibs: [
+ "libfixedbitset",
+ "libserde_json",
+ ],
+}
+
+rust_library {
+ name: "libfixedbitset",
+ host_supported: true,
+ crate_name: "fixedbitset",
+ cargo_env_compat: true,
+ cargo_pkg_version: "0.5.7",
+ crate_root: "src/lib.rs",
+ edition: "2021",
+ features: [
+ "default",
+ "std",
+ ],
+ apex_available: [
+ "//apex_available:platform",
+ "//apex_available:anyapex",
+ ],
+ product_available: true,
+ vendor_available: true,
+}
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..e526880
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,45 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# When uploading crates to the registry Cargo will automatically
+# "normalize" Cargo.toml files for maximal compatibility
+# with all versions of Cargo and also rewrite `path` dependencies
+# to registry (e.g., crates.io) dependencies.
+#
+# If you are reading this file be aware that the original Cargo.toml
+# will likely look very different (and much more reasonable).
+# See Cargo.toml.orig for the original contents.
+
+[package]
+edition = "2021"
+rust-version = "1.56"
+name = "fixedbitset"
+version = "0.5.7"
+authors = ["bluss"]
+description = "FixedBitSet is a simple bitset collection"
+documentation = "https://docs.rs/fixedbitset/"
+readme = "README.md"
+keywords = [
+ "container",
+ "data-structure",
+ "bitvec",
+ "bitset",
+ "no_std",
+]
+categories = ["data-structures"]
+license = "MIT OR Apache-2.0"
+repository = "https://github.com/petgraph/fixedbitset"
+
+[package.metadata.release]
+no-dev-version = true
+tag-name = "{{version}}"
+
+[dependencies.serde]
+version = "1.0"
+optional = true
+
+[dev-dependencies.serde_json]
+version = "1.0"
+
+[features]
+default = ["std"]
+std = []
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
new file mode 100644
index 0000000..5dd44ef
--- /dev/null
+++ b/Cargo.toml.orig
@@ -0,0 +1,29 @@
+[package]
+name = "fixedbitset"
+version = "0.5.7"
+authors = ["bluss"]
+license = "MIT OR Apache-2.0"
+readme = "README.md"
+rust-version = "1.56"
+edition = "2021"
+
+description = "FixedBitSet is a simple bitset collection"
+documentation = "https://docs.rs/fixedbitset/"
+repository = "https://github.com/petgraph/fixedbitset"
+
+keywords = ["container", "data-structure", "bitvec", "bitset", "no_std"]
+categories = ["data-structures"]
+
+[features]
+std = []
+default = ["std"]
+
+[package.metadata.release]
+no-dev-version = true
+tag-name = "{{version}}"
+
+[dependencies]
+serde = { version = "1.0", optional = true }
+
+[dev-dependencies]
+serde_json = "1.0"
diff --git a/LICENSE b/LICENSE
new file mode 120000
index 0000000..6b579aa
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1 @@
+LICENSE-APACHE
\ No newline at end of file
diff --git a/LICENSE-APACHE b/LICENSE-APACHE
new file mode 100644
index 0000000..16fe87b
--- /dev/null
+++ b/LICENSE-APACHE
@@ -0,0 +1,201 @@
+ Apache License
+ Version 2.0, January 2004
+ http://www.apache.org/licenses/
+
+TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+1. Definitions.
+
+ "License" shall mean the terms and conditions for use, reproduction,
+ and distribution as defined by Sections 1 through 9 of this document.
+
+ "Licensor" shall mean the copyright owner or entity authorized by
+ the copyright owner that is granting the License.
+
+ "Legal Entity" shall mean the union of the acting entity and all
+ other entities that control, are controlled by, or are under common
+ control with that entity. For the purposes of this definition,
+ "control" means (i) the power, direct or indirect, to cause the
+ direction or management of such entity, whether by contract or
+ otherwise, or (ii) ownership of fifty percent (50%) or more of the
+ outstanding shares, or (iii) beneficial ownership of such entity.
+
+ "You" (or "Your") shall mean an individual or Legal Entity
+ exercising permissions granted by this License.
+
+ "Source" form shall mean the preferred form for making modifications,
+ including but not limited to software source code, documentation
+ source, and configuration files.
+
+ "Object" form shall mean any form resulting from mechanical
+ transformation or translation of a Source form, including but
+ not limited to compiled object code, generated documentation,
+ and conversions to other media types.
+
+ "Work" shall mean the work of authorship, whether in Source or
+ Object form, made available under the License, as indicated by a
+ copyright notice that is included in or attached to the work
+ (an example is provided in the Appendix below).
+
+ "Derivative Works" shall mean any work, whether in Source or Object
+ form, that is based on (or derived from) the Work and for which the
+ editorial revisions, annotations, elaborations, or other modifications
+ represent, as a whole, an original work of authorship. For the purposes
+ of this License, Derivative Works shall not include works that remain
+ separable from, or merely link (or bind by name) to the interfaces of,
+ the Work and Derivative Works thereof.
+
+ "Contribution" shall mean any work of authorship, including
+ the original version of the Work and any modifications or additions
+ to that Work or Derivative Works thereof, that is intentionally
+ submitted to Licensor for inclusion in the Work by the copyright owner
+ or by an individual or Legal Entity authorized to submit on behalf of
+ the copyright owner. For the purposes of this definition, "submitted"
+ means any form of electronic, verbal, or written communication sent
+ to the Licensor or its representatives, including but not limited to
+ communication on electronic mailing lists, source code control systems,
+ and issue tracking systems that are managed by, or on behalf of, the
+ Licensor for the purpose of discussing and improving the Work, but
+ excluding communication that is conspicuously marked or otherwise
+ designated in writing by the copyright owner as "Not a Contribution."
+
+ "Contributor" shall mean Licensor and any individual or Legal Entity
+ on behalf of whom a Contribution has been received by Licensor and
+ subsequently incorporated within the Work.
+
+2. Grant of Copyright License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ copyright license to reproduce, prepare Derivative Works of,
+ publicly display, publicly perform, sublicense, and distribute the
+ Work and such Derivative Works in Source or Object form.
+
+3. Grant of Patent License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ (except as stated in this section) patent license to make, have made,
+ use, offer to sell, sell, import, and otherwise transfer the Work,
+ where such license applies only to those patent claims licensable
+ by such Contributor that are necessarily infringed by their
+ Contribution(s) alone or by combination of their Contribution(s)
+ with the Work to which such Contribution(s) was submitted. If You
+ institute patent litigation against any entity (including a
+ cross-claim or counterclaim in a lawsuit) alleging that the Work
+ or a Contribution incorporated within the Work constitutes direct
+ or contributory patent infringement, then any patent licenses
+ granted to You under this License for that Work shall terminate
+ as of the date such litigation is filed.
+
+4. Redistribution. You may reproduce and distribute copies of the
+ Work or Derivative Works thereof in any medium, with or without
+ modifications, and in Source or Object form, provided that You
+ meet the following conditions:
+
+ (a) You must give any other recipients of the Work or
+ Derivative Works a copy of this License; and
+
+ (b) You must cause any modified files to carry prominent notices
+ stating that You changed the files; and
+
+ (c) You must retain, in the Source form of any Derivative Works
+ that You distribute, all copyright, patent, trademark, and
+ attribution notices from the Source form of the Work,
+ excluding those notices that do not pertain to any part of
+ the Derivative Works; and
+
+ (d) If the Work includes a "NOTICE" text file as part of its
+ distribution, then any Derivative Works that You distribute must
+ include a readable copy of the attribution notices contained
+ within such NOTICE file, excluding those notices that do not
+ pertain to any part of the Derivative Works, in at least one
+ of the following places: within a NOTICE text file distributed
+ as part of the Derivative Works; within the Source form or
+ documentation, if provided along with the Derivative Works; or,
+ within a display generated by the Derivative Works, if and
+ wherever such third-party notices normally appear. The contents
+ of the NOTICE file are for informational purposes only and
+ do not modify the License. You may add Your own attribution
+ notices within Derivative Works that You distribute, alongside
+ or as an addendum to the NOTICE text from the Work, provided
+ that such additional attribution notices cannot be construed
+ as modifying the License.
+
+ You may add Your own copyright statement to Your modifications and
+ may provide additional or different license terms and conditions
+ for use, reproduction, or distribution of Your modifications, or
+ for any such Derivative Works as a whole, provided Your use,
+ reproduction, and distribution of the Work otherwise complies with
+ the conditions stated in this License.
+
+5. Submission of Contributions. Unless You explicitly state otherwise,
+ any Contribution intentionally submitted for inclusion in the Work
+ by You to the Licensor shall be under the terms and conditions of
+ this License, without any additional terms or conditions.
+ Notwithstanding the above, nothing herein shall supersede or modify
+ the terms of any separate license agreement you may have executed
+ with Licensor regarding such Contributions.
+
+6. Trademarks. This License does not grant permission to use the trade
+ names, trademarks, service marks, or product names of the Licensor,
+ except as required for reasonable and customary use in describing the
+ origin of the Work and reproducing the content of the NOTICE file.
+
+7. Disclaimer of Warranty. Unless required by applicable law or
+ agreed to in writing, Licensor provides the Work (and each
+ Contributor provides its Contributions) on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ implied, including, without limitation, any warranties or conditions
+ of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+ PARTICULAR PURPOSE. You are solely responsible for determining the
+ appropriateness of using or redistributing the Work and assume any
+ risks associated with Your exercise of permissions under this License.
+
+8. Limitation of Liability. In no event and under no legal theory,
+ whether in tort (including negligence), contract, or otherwise,
+ unless required by applicable law (such as deliberate and grossly
+ negligent acts) or agreed to in writing, shall any Contributor be
+ liable to You for damages, including any direct, indirect, special,
+ incidental, or consequential damages of any character arising as a
+ result of this License or out of the use or inability to use the
+ Work (including but not limited to damages for loss of goodwill,
+ work stoppage, computer failure or malfunction, or any and all
+ other commercial damages or losses), even if such Contributor
+ has been advised of the possibility of such damages.
+
+9. Accepting Warranty or Additional Liability. While redistributing
+ the Work or Derivative Works thereof, You may choose to offer,
+ and charge a fee for, acceptance of support, warranty, indemnity,
+ or other liability obligations and/or rights consistent with this
+ License. However, in accepting such obligations, You may act only
+ on Your own behalf and on Your sole responsibility, not on behalf
+ of any other Contributor, and only if You agree to indemnify,
+ defend, and hold each Contributor harmless for any liability
+ incurred by, or claims asserted against, such Contributor by reason
+ of your accepting any such warranty or additional liability.
+
+END OF TERMS AND CONDITIONS
+
+APPENDIX: How to apply the Apache License to your work.
+
+ To apply the Apache License to your work, attach the following
+ boilerplate notice, with the fields enclosed by brackets "[]"
+ replaced with your own identifying information. (Don't include
+ the brackets!) The text should be enclosed in the appropriate
+ comment syntax for the file format. We also recommend that a
+ file or class name and description of purpose be included on the
+ same "printed page" as the copyright notice for easier
+ identification within third-party archives.
+
+Copyright [yyyy] [name of copyright owner]
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
diff --git a/LICENSE-MIT b/LICENSE-MIT
new file mode 100644
index 0000000..327cc61
--- /dev/null
+++ b/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/METADATA b/METADATA
new file mode 100644
index 0000000..6d67be1
--- /dev/null
+++ b/METADATA
@@ -0,0 +1,21 @@
+name: "fixedbitset"
+description: "FixedBitSet is a simple bitset collection"
+third_party {
+ identifier {
+ type: "crates.io"
+ value: "fixedbitset"
+ }
+ identifier {
+ type: "Archive"
+ value: "https://static.crates.io/crates/fixedbitset/fixedbitset-0.5.7.crate"
+ primary_source: true
+ }
+ version: "0.5.7"
+ # Dual-licensed, using the least restrictive per go/thirdpartylicenses#same.
+ license_type: NOTICE
+ last_upgrade_date {
+ year: 2024
+ month: 8
+ day: 9
+ }
+}
diff --git a/MODULE_LICENSE_APACHE2 b/MODULE_LICENSE_APACHE2
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/MODULE_LICENSE_APACHE2
diff --git a/OWNERS b/OWNERS
new file mode 100644
index 0000000..48bea6e
--- /dev/null
+++ b/OWNERS
@@ -0,0 +1,2 @@
+# Bug component: 688011
+include platform/prebuilts/rust:main:/OWNERS
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..929ee32
--- /dev/null
+++ b/README.md
@@ -0,0 +1,125 @@
+fixedbitset
+---
+
+A simple fixed size bitset container for Rust.
+
+Please read the [API documentation here](https://docs.rs/fixedbitset/)
+
+[](https://github.com/petgraph/fixedbitset/actions)
+[](https://crates.io/crates/fixedbitset)
+
+# Recent Changes
+
+- 0.5.7
+ - [#127](https://github.com/petgraph/fixedbitset/pull/127) and [#128](https://github.com/petgraph/fixedbitset/pull/128): Optimize `Clone::clone_from` to avoid
+ extra allocations and copies.
+- 0.5.6
+ - Fixed FixedBitset not implementing Send/Sync due to the stack size shrink.
+- 0.5.5 (yanked)
+ - [#116](https://github.com/petgraph/fixedbitset/pull/116): Add functions for counting the results of a set operation (`union_count`,
+ `intersection_count`, `difference_count`, `symmetric_difference_count`) by @james7132.
+ - [#118](https://github.com/petgraph/fixedbitset/pull/118): Shrink the stack size of FixedBitset. There should be zero stack size overhead
+ compared to a Vec.
+ - [#119](https://github.com/petgraph/fixedbitset/pull/119): Fix builds for wasm32.
+ - [#120](https://github.com/petgraph/fixedbitset/pull/119): Add more utility functions that were previously missing from the public interface:
+ `contains_any_in_range`, `contains_all_in_range`, `minimum`, `maximum`, `is_full`, `count_zeroes`, and `remove_range`.
+ - [#121](https://github.com/petgraph/fixedbitset/pull/121): Add support for SIMD acceleration for AVX builds.
+- 0.5.4
+ - [#112](https://github.com/petgraph/fixedbitset/pull/112): Fix undefined behavior in IntoOnes and setup testing with MIRI by @SkiFire13
+- 0.5.3 (yanked)
+ - [#109](https://github.com/petgraph/fixedbitset/pull/109): Fix non-x86(_64) builds by @james7132
+- 0.5.2 (yanked)
+ - [#86](https://github.com/petgraph/fixedbitset/pull/86): Explicit SIMD vectorization for set operations by @james7132.
+- 0.5.1
+ - [#102](https://github.com/petgraph/fixedbitset/pull/102): Added `contains_unchecked`, `insert_unchecked`, `put_unchecked`,
+ `set_unchecked`, `toggle_unchecked`, `removed_unchecked`, `copy_bit_unchecked` unsafe variants of the safe functions, by @james7132
+ - [#103](https://github.com/petgraph/fixedbitset/pull/103): Added `into_ones` which returns a owned iterator over the one
+ values from a bitset, by @james7132.
+ - [#104](https://github.com/petgraph/fixedbitset/pull/104): Implemented `DoubleEndedIterator` for `Union`, `Intersection`,
+ `Difference`, and `SymmetricDifference` , by @james7132.
+- 0.5.0
+ - [#74](https://github.com/petgraph/fixedbitset/pull/74): Accelerated set operations (union, intersection, difference,
+ symmetric difference) by using larger blocks internally, by @james7132.
+ - [#88](https://github.com/petgraph/fixedbitset/pull/88): Added `FixedBitSet::remove` by @james7132.
+ - [#89](https://github.com/petgraph/fixedbitset/pull/89): Added `FixedBitSet::zeros` and the `Zeros` iterator by @james7132.
+ - [#92](https://github.com/petgraph/fixedbitset/pull/92): Added `FixedBitSet::grow_and_insert` function, a
+ non-panicking version of `insert` that grows the underlying storage as need, by @shuoli84.
+ - [#98](https://github.com/petgraph/fixedbitset/pull/98): `Ones` now implements `DoubleEndedIterator`, by @tikhu.
+ - [#99](https://github.com/petgraph/fixedbitset/pull/99): **Breaking change**: serde now serializes and deserializes from a little-endian encoded
+ raw byte buffer. Existing stored instances of the serialized bitsets will need to be
+ re-encoded.
+ - Bumped MSRV to 1.56.
+- 0.4.2
+ - [#79](https://github.com/petgraph/fixedbitset/pull/79): Add `is_clear`,
+ clarify `is_empty` and `len` documentation by \@nicopap.
+- 0.4.1
+ - Documentation and formatting fixes.
+- 0.4.0
+ - [#61](https://github.com/petgraph/fixedbitset/pull/61): Require
+ Rust 1.39.
+ - [#60](https://github.com/petgraph/fixedbitset/pull/60): Add
+ `const` `FixedBitSet::new` consructor
+ by \@jakobhellermann.
+ - [#59](https://github.com/petgraph/fixedbitset/pull/59): Add
+ optional `serde` support by \@keshavsn.
+- 0.3.2
+ - [#18](https://github.com/petgraph/fixedbitset/pull/18): Optimize
+ `ones` using `trailing_zeroes` by \@vks
+- 0.3.1
+ - Add bit assign operators for references by \@flaghacker
+ - Improve assertion error messages by \@lovasoa
+ - Add documentation examples for `with_capacity_and_blocks`
+- 0.3.0
+ - Add `with_capacity_and_blocks` by \@luizirber
+ - Add `difference_with` by \@sunshowers
+ - Implement `Binary` and `Display` traits by \@Dolphindalt
+ - Add `toggle_range` by \@wirelyre
+- 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](https://www.apache.org/licenses/LICENSE-2.0)
+ or the [MIT license](https://opensource.org/licenses/MIT),
+ at your option. This file may not be copied, modified, or distributed except
+according to those terms.
diff --git a/cargo_embargo.json b/cargo_embargo.json
new file mode 100644
index 0000000..9a0a579
--- /dev/null
+++ b/cargo_embargo.json
@@ -0,0 +1,3 @@
+{
+ "tests": true
+}
diff --git a/src/block/avx.rs b/src/block/avx.rs
new file mode 100644
index 0000000..33ba100
--- /dev/null
+++ b/src/block/avx.rs
@@ -0,0 +1,92 @@
+#[cfg(target_arch = "x86")]
+use core::arch::x86::*;
+#[cfg(target_arch = "x86_64")]
+use core::arch::x86_64::*;
+use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not};
+
+#[derive(Copy, Clone, Debug)]
+#[repr(transparent)]
+pub struct Block(pub(super) __m256d);
+
+impl Block {
+ #[inline]
+ pub fn is_empty(self) -> bool {
+ unsafe {
+ let value = _mm256_castpd_si256(self.0);
+ _mm256_testz_si256(value, value) == 1
+ }
+ }
+
+ #[inline]
+ pub fn andnot(self, other: Self) -> Self {
+ unsafe { Self(_mm256_andnot_pd(other.0, self.0)) }
+ }
+}
+
+impl Not for Block {
+ type Output = Block;
+ #[inline]
+ fn not(self) -> Self::Output {
+ unsafe { Self(_mm256_xor_pd(self.0, Self::ALL.0)) }
+ }
+}
+
+impl BitAnd for Block {
+ type Output = Block;
+ #[inline]
+ fn bitand(self, other: Self) -> Self::Output {
+ unsafe { Self(_mm256_and_pd(self.0, other.0)) }
+ }
+}
+
+impl BitAndAssign for Block {
+ #[inline]
+ fn bitand_assign(&mut self, other: Self) {
+ unsafe {
+ self.0 = _mm256_and_pd(self.0, other.0);
+ }
+ }
+}
+
+impl BitOr for Block {
+ type Output = Block;
+ #[inline]
+ fn bitor(self, other: Self) -> Self::Output {
+ unsafe { Self(_mm256_or_pd(self.0, other.0)) }
+ }
+}
+
+impl BitOrAssign for Block {
+ #[inline]
+ fn bitor_assign(&mut self, other: Self) {
+ unsafe {
+ self.0 = _mm256_or_pd(self.0, other.0);
+ }
+ }
+}
+
+impl BitXor for Block {
+ type Output = Block;
+ #[inline]
+ fn bitxor(self, other: Self) -> Self::Output {
+ unsafe { Self(_mm256_xor_pd(self.0, other.0)) }
+ }
+}
+
+impl BitXorAssign for Block {
+ #[inline]
+ fn bitxor_assign(&mut self, other: Self) {
+ unsafe { self.0 = _mm256_xor_pd(self.0, other.0) }
+ }
+}
+
+impl PartialEq for Block {
+ #[inline]
+ fn eq(&self, other: &Self) -> bool {
+ unsafe {
+ let new = _mm256_xor_pd(self.0, other.0);
+ let neq = _mm256_castpd_si256(new);
+ _mm256_testz_si256(neq, neq) == 1
+ }
+ }
+}
diff --git a/src/block/avx2.rs b/src/block/avx2.rs
new file mode 100644
index 0000000..b359377
--- /dev/null
+++ b/src/block/avx2.rs
@@ -0,0 +1,88 @@
+#[cfg(target_arch = "x86")]
+use core::arch::x86::*;
+#[cfg(target_arch = "x86_64")]
+use core::arch::x86_64::*;
+use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not};
+
+#[derive(Copy, Clone, Debug)]
+#[repr(transparent)]
+pub struct Block(pub(super) __m256i);
+
+impl Block {
+ #[inline]
+ pub fn is_empty(self) -> bool {
+ unsafe { _mm256_testz_si256(self.0, self.0) == 1 }
+ }
+
+ #[inline]
+ pub fn andnot(self, other: Self) -> Self {
+ Self(unsafe { _mm256_andnot_si256(other.0, self.0) })
+ }
+}
+
+impl Not for Block {
+ type Output = Block;
+ #[inline]
+ fn not(self) -> Self::Output {
+ unsafe { Self(_mm256_xor_si256(self.0, Self::ALL.0)) }
+ }
+}
+
+impl BitAnd for Block {
+ type Output = Block;
+ #[inline]
+ fn bitand(self, other: Self) -> Self::Output {
+ unsafe { Self(_mm256_and_si256(self.0, other.0)) }
+ }
+}
+
+impl BitAndAssign for Block {
+ #[inline]
+ fn bitand_assign(&mut self, other: Self) {
+ unsafe {
+ self.0 = _mm256_and_si256(self.0, other.0);
+ }
+ }
+}
+
+impl BitOr for Block {
+ type Output = Block;
+ #[inline]
+ fn bitor(self, other: Self) -> Self::Output {
+ unsafe { Self(_mm256_or_si256(self.0, other.0)) }
+ }
+}
+
+impl BitOrAssign for Block {
+ #[inline]
+ fn bitor_assign(&mut self, other: Self) {
+ unsafe {
+ self.0 = _mm256_or_si256(self.0, other.0);
+ }
+ }
+}
+
+impl BitXor for Block {
+ type Output = Block;
+ #[inline]
+ fn bitxor(self, other: Self) -> Self::Output {
+ unsafe { Self(_mm256_xor_si256(self.0, other.0)) }
+ }
+}
+
+impl BitXorAssign for Block {
+ #[inline]
+ fn bitxor_assign(&mut self, other: Self) {
+ unsafe { self.0 = _mm256_xor_si256(self.0, other.0) }
+ }
+}
+
+impl PartialEq for Block {
+ #[inline]
+ fn eq(&self, other: &Self) -> bool {
+ unsafe {
+ let neq = _mm256_xor_si256(self.0, other.0);
+ _mm256_testz_si256(neq, neq) == 1
+ }
+ }
+}
diff --git a/src/block/default.rs b/src/block/default.rs
new file mode 100644
index 0000000..7fc460f
--- /dev/null
+++ b/src/block/default.rs
@@ -0,0 +1,70 @@
+use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not};
+
+#[derive(Copy, Clone, PartialEq, Debug)]
+#[repr(transparent)]
+pub struct Block(pub(super) usize);
+
+impl Block {
+ #[inline]
+ pub const fn is_empty(self) -> bool {
+ self.0 == Self::NONE.0
+ }
+
+ #[inline]
+ pub fn andnot(self, other: Self) -> Self {
+ Self(!other.0 & self.0)
+ }
+}
+
+impl Not for Block {
+ type Output = Block;
+ #[inline]
+ fn not(self) -> Self::Output {
+ Self(self.0.not())
+ }
+}
+
+impl BitAnd for Block {
+ type Output = Block;
+ #[inline]
+ fn bitand(self, other: Self) -> Self::Output {
+ Self(self.0.bitand(other.0))
+ }
+}
+
+impl BitAndAssign for Block {
+ #[inline]
+ fn bitand_assign(&mut self, other: Self) {
+ self.0.bitand_assign(other.0);
+ }
+}
+
+impl BitOr for Block {
+ type Output = Block;
+ #[inline]
+ fn bitor(self, other: Self) -> Self::Output {
+ Self(self.0.bitor(other.0))
+ }
+}
+
+impl BitOrAssign for Block {
+ #[inline]
+ fn bitor_assign(&mut self, other: Self) {
+ self.0.bitor_assign(other.0)
+ }
+}
+
+impl BitXor for Block {
+ type Output = Block;
+ #[inline]
+ fn bitxor(self, other: Self) -> Self::Output {
+ Self(self.0.bitxor(other.0))
+ }
+}
+
+impl BitXorAssign for Block {
+ #[inline]
+ fn bitxor_assign(&mut self, other: Self) {
+ self.0.bitxor_assign(other.0)
+ }
+}
diff --git a/src/block/mod.rs b/src/block/mod.rs
new file mode 100644
index 0000000..ae7c222
--- /dev/null
+++ b/src/block/mod.rs
@@ -0,0 +1,114 @@
+#![allow(clippy::undocumented_unsafe_blocks)]
+#![allow(dead_code)]
+// TODO: Remove once the transmutes are fixed
+#![allow(unknown_lints)]
+#![allow(clippy::missing_transmute_annotations)]
+
+use core::cmp::Ordering;
+use core::hash::{Hash, Hasher};
+
+#[cfg(all(
+ not(all(target_family = "wasm", target_feature = "simd128")),
+ not(target_feature = "sse2"),
+ not(target_feature = "avx"),
+ not(target_feature = "avx2"),
+))]
+mod default;
+#[cfg(all(
+ not(all(target_family = "wasm", target_feature = "simd128")),
+ not(target_feature = "sse2"),
+ not(target_feature = "avx"),
+ not(target_feature = "avx2"),
+))]
+pub use self::default::*;
+
+#[cfg(all(
+ any(target_arch = "x86", target_arch = "x86_64"),
+ target_feature = "sse2",
+ not(target_feature = "avx"),
+ not(target_feature = "avx2"),
+))]
+mod sse2;
+#[cfg(all(
+ any(target_arch = "x86", target_arch = "x86_64"),
+ target_feature = "sse2",
+ not(target_feature = "avx"),
+ not(target_feature = "avx2"),
+))]
+pub use self::sse2::*;
+
+#[cfg(all(
+ any(target_arch = "x86", target_arch = "x86_64"),
+ target_feature = "avx",
+ not(target_feature = "avx2")
+))]
+mod avx;
+#[cfg(all(
+ any(target_arch = "x86", target_arch = "x86_64"),
+ target_feature = "avx",
+ not(target_feature = "avx2")
+))]
+pub use self::avx::*;
+
+#[cfg(all(
+ any(target_arch = "x86", target_arch = "x86_64"),
+ target_feature = "avx2"
+))]
+mod avx2;
+#[cfg(all(
+ any(target_arch = "x86", target_arch = "x86_64"),
+ target_feature = "avx2"
+))]
+pub use self::avx2::*;
+
+#[cfg(all(target_family = "wasm", target_feature = "simd128"))]
+mod wasm;
+#[cfg(all(target_family = "wasm", target_feature = "simd128"))]
+pub use self::wasm::*;
+
+impl Block {
+ pub const USIZE_COUNT: usize = core::mem::size_of::<Self>() / core::mem::size_of::<usize>();
+ pub const NONE: Self = Self::from_usize_array([0; Self::USIZE_COUNT]);
+ pub const ALL: Self = Self::from_usize_array([usize::MAX; Self::USIZE_COUNT]);
+ pub const BITS: usize = core::mem::size_of::<Self>() * 8;
+
+ #[inline]
+ pub fn into_usize_array(self) -> [usize; Self::USIZE_COUNT] {
+ unsafe { core::mem::transmute(self.0) }
+ }
+
+ #[inline]
+ pub const fn from_usize_array(array: [usize; Self::USIZE_COUNT]) -> Self {
+ Self(unsafe { core::mem::transmute(array) })
+ }
+}
+
+impl Eq for Block {}
+
+impl PartialOrd for Block {
+ #[inline]
+ fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+ Some(self.cmp(other))
+ }
+}
+
+impl Ord for Block {
+ #[inline]
+ fn cmp(&self, other: &Self) -> Ordering {
+ self.into_usize_array().cmp(&other.into_usize_array())
+ }
+}
+
+impl Default for Block {
+ #[inline]
+ fn default() -> Self {
+ Self::NONE
+ }
+}
+
+impl Hash for Block {
+ #[inline]
+ fn hash<H: Hasher>(&self, hasher: &mut H) {
+ Hash::hash_slice(&self.into_usize_array(), hasher);
+ }
+}
diff --git a/src/block/sse2.rs b/src/block/sse2.rs
new file mode 100644
index 0000000..6db08f7
--- /dev/null
+++ b/src/block/sse2.rs
@@ -0,0 +1,104 @@
+#![allow(clippy::undocumented_unsafe_blocks)]
+
+#[cfg(target_arch = "x86")]
+use core::arch::x86::*;
+#[cfg(target_arch = "x86_64")]
+use core::arch::x86_64::*;
+use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not};
+
+#[derive(Copy, Clone, Debug)]
+#[repr(transparent)]
+pub struct Block(pub(super) __m128i);
+
+impl Block {
+ #[inline]
+ pub fn is_empty(self) -> bool {
+ #[cfg(not(target_feature = "sse4.1"))]
+ {
+ self == Self::NONE
+ }
+ #[cfg(target_feature = "sse4.1")]
+ {
+ unsafe { _mm_test_all_zeros(self.0, self.0) == 1 }
+ }
+ }
+
+ #[inline]
+ pub fn andnot(self, other: Self) -> Self {
+ Self(unsafe { _mm_andnot_si128(other.0, self.0) })
+ }
+}
+
+impl Not for Block {
+ type Output = Block;
+ #[inline]
+ fn not(self) -> Self::Output {
+ unsafe { Self(_mm_xor_si128(self.0, Self::ALL.0)) }
+ }
+}
+
+impl BitAnd for Block {
+ type Output = Block;
+ #[inline]
+ fn bitand(self, other: Self) -> Self::Output {
+ unsafe { Self(_mm_and_si128(self.0, other.0)) }
+ }
+}
+
+impl BitAndAssign for Block {
+ #[inline]
+ fn bitand_assign(&mut self, other: Self) {
+ unsafe {
+ self.0 = _mm_and_si128(self.0, other.0);
+ }
+ }
+}
+
+impl BitOr for Block {
+ type Output = Block;
+ #[inline]
+ fn bitor(self, other: Self) -> Self::Output {
+ unsafe { Self(_mm_or_si128(self.0, other.0)) }
+ }
+}
+
+impl BitOrAssign for Block {
+ #[inline]
+ fn bitor_assign(&mut self, other: Self) {
+ unsafe {
+ self.0 = _mm_or_si128(self.0, other.0);
+ }
+ }
+}
+
+impl BitXor for Block {
+ type Output = Block;
+ #[inline]
+ fn bitxor(self, other: Self) -> Self::Output {
+ unsafe { Self(_mm_xor_si128(self.0, other.0)) }
+ }
+}
+
+impl BitXorAssign for Block {
+ #[inline]
+ fn bitxor_assign(&mut self, other: Self) {
+ unsafe { self.0 = _mm_xor_si128(self.0, other.0) }
+ }
+}
+
+impl PartialEq for Block {
+ #[inline]
+ fn eq(&self, other: &Self) -> bool {
+ unsafe {
+ #[cfg(not(target_feature = "sse4.1"))]
+ {
+ _mm_movemask_epi8(_mm_cmpeq_epi8(self.0, other.0)) == 0xffff
+ }
+ #[cfg(target_feature = "sse4.1")]
+ {
+ let neq = _mm_xor_si128(self.0, other.0);
+ _mm_test_all_zeros(neq, neq) == 1
+ }
+ }
+ }
+}
diff --git a/src/block/wasm.rs b/src/block/wasm.rs
new file mode 100644
index 0000000..f823d86
--- /dev/null
+++ b/src/block/wasm.rs
@@ -0,0 +1,80 @@
+use core::{
+ arch::wasm32::*,
+ ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not},
+};
+
+#[derive(Copy, Clone, Debug)]
+#[repr(transparent)]
+pub struct Block(pub(super) v128);
+
+impl Block {
+ #[inline]
+ pub fn is_empty(self) -> bool {
+ !v128_any_true(self.0)
+ }
+
+ #[inline]
+ pub fn andnot(self, other: Self) -> Self {
+ Self(v128_andnot(self.0, other.0))
+ }
+}
+
+impl Not for Block {
+ type Output = Block;
+ #[inline]
+ fn not(self) -> Self::Output {
+ Self(v128_xor(self.0, Self::ALL.0))
+ }
+}
+
+impl BitAnd for Block {
+ type Output = Block;
+ #[inline]
+ fn bitand(self, other: Self) -> Self::Output {
+ Self(v128_and(self.0, other.0))
+ }
+}
+
+impl BitAndAssign for Block {
+ #[inline]
+ fn bitand_assign(&mut self, other: Self) {
+ self.0 = v128_and(self.0, other.0);
+ }
+}
+
+impl BitOr for Block {
+ type Output = Block;
+ #[inline]
+ fn bitor(self, other: Self) -> Self::Output {
+ Self(v128_or(self.0, other.0))
+ }
+}
+
+impl BitOrAssign for Block {
+ #[inline]
+ fn bitor_assign(&mut self, other: Self) {
+ self.0 = v128_or(self.0, other.0);
+ }
+}
+
+impl BitXor for Block {
+ type Output = Block;
+ #[inline]
+ fn bitxor(self, other: Self) -> Self::Output {
+ Self(v128_xor(self.0, other.0))
+ }
+}
+
+impl BitXorAssign for Block {
+ #[inline]
+ fn bitxor_assign(&mut self, other: Self) {
+ self.0 = v128_xor(self.0, other.0)
+ }
+}
+
+impl PartialEq for Block {
+ #[inline]
+ fn eq(&self, other: &Self) -> bool {
+ !v128_any_true(v128_xor(self.0, other.0))
+ }
+}
diff --git a/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..6bf3d1b
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1,1715 @@
+//! `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.
+//!
+//! ### SIMD Acceleration
+//! `fixedbitset` is written with SIMD in mind. The backing store and set operations will use aligned SIMD data types and instructions when compiling
+//! for compatible target platforms. The use of SIMD generally enables better performance in many set and batch operations (i.e. intersection/union/inserting a range).
+//!
+//! When SIMD is not available on the target, the crate will gracefully fallback to a default implementation. It is intended to add support for other SIMD architectures
+//! once they appear in stable Rust.
+//!
+//! Currently only SSE2/AVX/AVX2 on x86/x86_64 and wasm32 SIMD are supported as this is what stable Rust supports.
+#![no_std]
+#![deny(clippy::undocumented_unsafe_blocks)]
+
+/// Local Android change: Use std to allow building as a dylib.
+#[cfg(android_dylib)]
+extern crate std;
+
+extern crate alloc;
+use alloc::{vec, vec::Vec};
+
+mod block;
+mod range;
+
+#[cfg(feature = "serde")]
+extern crate serde;
+#[cfg(feature = "serde")]
+mod serde_impl;
+
+use core::fmt::Write;
+use core::fmt::{Binary, Display, Error, Formatter};
+
+use core::cmp::Ordering;
+use core::hash::Hash;
+use core::iter::{Chain, FusedIterator};
+use core::mem::ManuallyDrop;
+use core::mem::MaybeUninit;
+use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Index};
+use core::ptr::NonNull;
+pub use range::IndexRange;
+
+pub(crate) const BITS: usize = core::mem::size_of::<Block>() * 8;
+#[cfg(feature = "serde")]
+pub(crate) const BYTES: usize = core::mem::size_of::<Block>();
+
+use block::Block as SimdBlock;
+pub type Block = usize;
+
+#[inline]
+fn div_rem(x: usize, denominator: usize) -> (usize, usize) {
+ (x / denominator, x % denominator)
+}
+
+fn vec_into_parts<T>(vec: Vec<T>) -> (NonNull<T>, usize, usize) {
+ let mut vec = ManuallyDrop::new(vec);
+ (
+ // SAFETY: A Vec's internal pointer is always non-null.
+ unsafe { NonNull::new_unchecked(vec.as_mut_ptr()) },
+ vec.capacity(),
+ vec.len(),
+ )
+}
+
+/// `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).
+///
+/// Derived traits depend on both the zeros and ones, so [0,1] is not equal to
+/// [0,1,0].
+#[derive(Debug, Eq)]
+pub struct FixedBitSet {
+ pub(crate) data: NonNull<MaybeUninit<SimdBlock>>,
+ capacity: usize,
+ /// length in bits
+ pub(crate) length: usize,
+}
+
+// SAFETY: FixedBitset contains no thread-local state and can be safely sent between threads
+unsafe impl Send for FixedBitSet {}
+// SAFETY: FixedBitset does not provide simultaneous unsynchronized mutable access to the
+// underlying buffer.
+unsafe impl Sync for FixedBitSet {}
+
+impl FixedBitSet {
+ /// Create a new empty **FixedBitSet**.
+ pub const fn new() -> Self {
+ FixedBitSet {
+ data: NonNull::dangling(),
+ capacity: 0,
+ length: 0,
+ }
+ }
+
+ /// 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, SimdBlock::BITS);
+ blocks += (rem > 0) as usize;
+ Self::from_blocks_and_len(vec![SimdBlock::NONE; blocks], bits)
+ }
+
+ #[inline]
+ fn from_blocks_and_len(data: Vec<SimdBlock>, length: usize) -> Self {
+ let (data, capacity, _) = vec_into_parts(data);
+ FixedBitSet {
+ data: data.cast(),
+ capacity,
+ length,
+ }
+ }
+
+ /// Create a new **FixedBitSet** with a specific number of bits,
+ /// initialized from provided blocks.
+ ///
+ /// If the blocks are not the exact size needed for the capacity
+ /// they will be padded with zeros (if shorter) or truncated to
+ /// the capacity (if longer).
+ ///
+ /// For example:
+ /// ```
+ /// let data = vec![4];
+ /// let bs = fixedbitset::FixedBitSet::with_capacity_and_blocks(4, data);
+ /// assert_eq!(format!("{:b}", bs), "0010");
+ /// ```
+ pub fn with_capacity_and_blocks<I: IntoIterator<Item = Block>>(bits: usize, blocks: I) -> Self {
+ let mut bitset = Self::with_capacity(bits);
+ for (subblock, value) in bitset.as_mut_slice().iter_mut().zip(blocks.into_iter()) {
+ *subblock = value;
+ }
+ bitset
+ }
+
+ /// Grow capacity to **bits**, all new bits initialized to zero
+ #[inline]
+ pub fn grow(&mut self, bits: usize) {
+ #[cold]
+ #[track_caller]
+ #[inline(never)]
+ fn do_grow(slf: &mut FixedBitSet, bits: usize) {
+ // SAFETY: The provided fill is initialized to NONE.
+ unsafe { slf.grow_inner(bits, MaybeUninit::new(SimdBlock::NONE)) };
+ }
+
+ if bits > self.length {
+ do_grow(self, bits);
+ }
+ }
+
+ /// # Safety
+ /// If `fill` is uninitialized, the memory must not be accessed and must be immediately
+ /// written over
+ #[inline(always)]
+ unsafe fn grow_inner(&mut self, bits: usize, fill: MaybeUninit<SimdBlock>) {
+ // SAFETY: The data pointer and capacity were created from a Vec initially. The block
+ // len is identical to that of the original.
+ let mut data = unsafe {
+ Vec::from_raw_parts(self.data.as_ptr(), self.simd_block_len(), self.capacity)
+ };
+ let (mut blocks, rem) = div_rem(bits, SimdBlock::BITS);
+ blocks += (rem > 0) as usize;
+ data.resize(blocks, fill);
+ let (data, capacity, _) = vec_into_parts(data);
+ self.data = data;
+ self.capacity = capacity;
+ self.length = bits;
+ }
+
+ #[inline]
+ unsafe fn get_unchecked(&self, subblock: usize) -> &Block {
+ &*self.data.as_ptr().cast::<Block>().add(subblock)
+ }
+
+ #[inline]
+ unsafe fn get_unchecked_mut(&mut self, subblock: usize) -> &mut Block {
+ &mut *self.data.as_ptr().cast::<Block>().add(subblock)
+ }
+
+ #[inline]
+ fn usize_len(&self) -> usize {
+ let (mut blocks, rem) = div_rem(self.length, BITS);
+ blocks += (rem > 0) as usize;
+ blocks
+ }
+
+ #[inline]
+ fn simd_block_len(&self) -> usize {
+ let (mut blocks, rem) = div_rem(self.length, SimdBlock::BITS);
+ blocks += (rem > 0) as usize;
+ blocks
+ }
+
+ #[inline]
+ fn batch_count_ones(blocks: impl IntoIterator<Item = Block>) -> usize {
+ blocks.into_iter().map(|x| x.count_ones() as usize).sum()
+ }
+
+ #[inline]
+ fn as_simd_slice(&self) -> &[SimdBlock] {
+ // SAFETY: The slice constructed is within bounds of the underlying allocation. This function
+ // is called with a read-only borrow so no other write can happen as long as the returned borrow lives.
+ unsafe { core::slice::from_raw_parts(self.data.as_ptr().cast(), self.simd_block_len()) }
+ }
+
+ #[inline]
+ fn as_mut_simd_slice(&mut self) -> &mut [SimdBlock] {
+ // SAFETY: The slice constructed is within bounds of the underlying allocation. This function
+ // is called with a mutable borrow so no other read or write can happen as long as the returned borrow lives.
+ unsafe { core::slice::from_raw_parts_mut(self.data.as_ptr().cast(), self.simd_block_len()) }
+ }
+
+ #[inline]
+ fn as_simd_slice_uninit(&self) -> &[MaybeUninit<SimdBlock>] {
+ // SAFETY: The slice constructed is within bounds of the underlying allocation. This function
+ // is called with a read-only borrow so no other write can happen as long as the returned borrow lives.
+ unsafe { core::slice::from_raw_parts(self.data.as_ptr(), self.simd_block_len()) }
+ }
+
+ #[inline]
+ fn as_mut_simd_slice_uninit(&mut self) -> &mut [MaybeUninit<SimdBlock>] {
+ // SAFETY: The slice constructed is within bounds of the underlying allocation. This function
+ // is called with a mutable borrow so no other read or write can happen as long as the returned borrow lives.
+ unsafe { core::slice::from_raw_parts_mut(self.data.as_ptr(), self.simd_block_len()) }
+ }
+
+ /// Grows the internal size of the bitset before inserting a bit
+ ///
+ /// Unlike `insert`, this cannot panic, but may allocate if the bit is outside of the existing buffer's range.
+ ///
+ /// This is faster than calling `grow` then `insert` in succession.
+ #[inline]
+ pub fn grow_and_insert(&mut self, bits: usize) {
+ self.grow(bits + 1);
+
+ let (blocks, rem) = div_rem(bits, BITS);
+ // SAFETY: The above grow ensures that the block is inside the Vec's allocation.
+ unsafe {
+ *self.get_unchecked_mut(blocks) |= 1 << rem;
+ }
+ }
+
+ /// The length of the [`FixedBitSet`] in bits.
+ ///
+ /// Note: `len` includes both set and unset bits.
+ /// ```
+ /// # use fixedbitset::FixedBitSet;
+ /// let bitset = FixedBitSet::with_capacity(10);
+ /// // there are 0 set bits, but 10 unset bits
+ /// assert_eq!(bitset.len(), 10);
+ /// ```
+ /// `len` does not return the count of set bits. For that, use
+ /// [`bitset.count_ones(..)`](FixedBitSet::count_ones) instead.
+ #[inline]
+ pub fn len(&self) -> usize {
+ self.length
+ }
+
+ /// `true` if the [`FixedBitSet`] is empty.
+ ///
+ /// Note that an "empty" `FixedBitSet` is a `FixedBitSet` with
+ /// no bits (meaning: it's length is zero). If you want to check
+ /// if all bits are unset, use [`FixedBitSet::is_clear`].
+ ///
+ /// ```
+ /// # use fixedbitset::FixedBitSet;
+ /// let bitset = FixedBitSet::with_capacity(10);
+ /// assert!(!bitset.is_empty());
+ ///
+ /// let bitset = FixedBitSet::with_capacity(0);
+ /// assert!(bitset.is_empty());
+ /// ```
+ #[inline]
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+
+ /// `true` if all bits in the [`FixedBitSet`] are unset.
+ ///
+ /// As opposed to [`FixedBitSet::is_empty`], which is `true` only for
+ /// sets without any bits, set or unset.
+ ///
+ /// ```
+ /// # use fixedbitset::FixedBitSet;
+ /// let mut bitset = FixedBitSet::with_capacity(10);
+ /// assert!(bitset.is_clear());
+ ///
+ /// bitset.insert(2);
+ /// assert!(!bitset.is_clear());
+ /// ```
+ ///
+ /// This is equivalent to [`bitset.count_ones(..) == 0`](FixedBitSet::count_ones).
+ #[inline]
+ pub fn is_clear(&self) -> bool {
+ self.as_simd_slice().iter().all(|block| block.is_empty())
+ }
+
+ /// Finds the lowest set bit in the bitset.
+ ///
+ /// Returns `None` if there aren't any set bits.
+ ///
+ /// ```
+ /// # use fixedbitset::FixedBitSet;
+ /// let mut bitset = FixedBitSet::with_capacity(10);
+ /// assert_eq!(bitset.minimum(), None);
+ ///
+ /// bitset.insert(2);
+ /// assert_eq!(bitset.minimum(), Some(2));
+ /// bitset.insert(8);
+ /// assert_eq!(bitset.minimum(), Some(2));
+ /// ```
+ #[inline]
+ pub fn minimum(&self) -> Option<usize> {
+ let (block_idx, block) = self
+ .as_simd_slice()
+ .iter()
+ .enumerate()
+ .find(|&(_, block)| !block.is_empty())?;
+ let mut inner = 0;
+ let mut trailing = 0;
+ for subblock in block.into_usize_array() {
+ if subblock != 0 {
+ trailing = subblock.trailing_zeros() as usize;
+ break;
+ } else {
+ inner += BITS;
+ }
+ }
+ Some(block_idx * SimdBlock::BITS + inner + trailing)
+ }
+
+ /// Finds the highest set bit in the bitset.
+ ///
+ /// Returns `None` if there aren't any set bits.
+ ///
+ /// ```
+ /// # use fixedbitset::FixedBitSet;
+ /// let mut bitset = FixedBitSet::with_capacity(10);
+ /// assert_eq!(bitset.maximum(), None);
+ ///
+ /// bitset.insert(8);
+ /// assert_eq!(bitset.maximum(), Some(8));
+ /// bitset.insert(2);
+ /// assert_eq!(bitset.maximum(), Some(8));
+ /// ```
+ #[inline]
+ pub fn maximum(&self) -> Option<usize> {
+ let (block_idx, block) = self
+ .as_simd_slice()
+ .iter()
+ .rev()
+ .enumerate()
+ .find(|&(_, block)| !block.is_empty())?;
+ let mut inner = 0;
+ let mut leading = 0;
+ for subblock in block.into_usize_array().iter().rev() {
+ if *subblock != 0 {
+ leading = subblock.leading_zeros() as usize;
+ break;
+ } else {
+ inner += BITS;
+ }
+ }
+ let max = self.simd_block_len() * SimdBlock::BITS;
+ Some(max - block_idx * SimdBlock::BITS - inner - leading - 1)
+ }
+
+ /// `true` if all bits in the [`FixedBitSet`] are set.
+ ///
+ /// ```
+ /// # use fixedbitset::FixedBitSet;
+ /// let mut bitset = FixedBitSet::with_capacity(10);
+ /// assert!(!bitset.is_full());
+ ///
+ /// bitset.insert_range(..);
+ /// assert!(bitset.is_full());
+ /// ```
+ ///
+ /// This is equivalent to [`bitset.count_ones(..) == bitset.len()`](FixedBitSet::count_ones).
+ #[inline]
+ pub fn is_full(&self) -> bool {
+ self.contains_all_in_range(..)
+ }
+
+ /// 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 {
+ (bit < self.length)
+ // SAFETY: The above check ensures that the block and bit are within bounds.
+ .then(|| unsafe { self.contains_unchecked(bit) })
+ .unwrap_or(false)
+ }
+
+ /// Return **true** if the bit is enabled in the **FixedBitSet**,
+ /// **false** otherwise.
+ ///
+ /// Note: unlike `contains`, calling this with an invalid `bit`
+ /// is undefined behavior.
+ ///
+ /// # Safety
+ /// `bit` must be less than `self.len()`
+ #[inline]
+ pub unsafe fn contains_unchecked(&self, bit: usize) -> bool {
+ let (block, i) = div_rem(bit, BITS);
+ (self.get_unchecked(block) & (1 << i)) != 0
+ }
+
+ /// Clear all bits.
+ #[inline]
+ pub fn clear(&mut self) {
+ for elt in self.as_mut_simd_slice().iter_mut() {
+ *elt = SimdBlock::NONE
+ }
+ }
+
+ /// Enable `bit`.
+ ///
+ /// **Panics** if **bit** is out of bounds.
+ #[inline]
+ pub fn insert(&mut self, bit: usize) {
+ assert!(
+ bit < self.length,
+ "insert at index {} exceeds fixedbitset size {}",
+ bit,
+ self.length
+ );
+ // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
+ unsafe {
+ self.insert_unchecked(bit);
+ }
+ }
+
+ /// Enable `bit` without any length checks.
+ ///
+ /// # Safety
+ /// `bit` must be less than `self.len()`
+ #[inline]
+ pub unsafe fn insert_unchecked(&mut self, bit: usize) {
+ let (block, i) = div_rem(bit, BITS);
+ // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
+ unsafe {
+ *self.get_unchecked_mut(block) |= 1 << i;
+ }
+ }
+
+ /// Disable `bit`.
+ ///
+ /// **Panics** if **bit** is out of bounds.
+ #[inline]
+ pub fn remove(&mut self, bit: usize) {
+ assert!(
+ bit < self.length,
+ "remove at index {} exceeds fixedbitset size {}",
+ bit,
+ self.length
+ );
+ // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
+ unsafe {
+ self.remove_unchecked(bit);
+ }
+ }
+
+ /// Disable `bit` without any bounds checking.
+ ///
+ /// # Safety
+ /// `bit` must be less than `self.len()`
+ #[inline]
+ pub unsafe fn remove_unchecked(&mut self, bit: usize) {
+ let (block, i) = div_rem(bit, BITS);
+ // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
+ unsafe {
+ *self.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,
+ "put at index {} exceeds fixedbitset size {}",
+ bit,
+ self.length
+ );
+ // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
+ unsafe { self.put_unchecked(bit) }
+ }
+
+ /// Enable `bit`, and return its previous value without doing any bounds checking.
+ ///
+ /// # Safety
+ /// `bit` must be less than `self.len()`
+ #[inline]
+ pub unsafe fn put_unchecked(&mut self, bit: usize) -> bool {
+ let (block, i) = div_rem(bit, BITS);
+ // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
+ unsafe {
+ let word = self.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,
+ "toggle at index {} exceeds fixedbitset size {}",
+ bit,
+ self.length
+ );
+ // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
+ unsafe {
+ self.toggle_unchecked(bit);
+ }
+ }
+
+ /// Toggle `bit` (inverting its state) without any bounds checking.
+ ///
+ /// # Safety
+ /// `bit` must be less than `self.len()`
+ #[inline]
+ pub unsafe fn toggle_unchecked(&mut self, bit: usize) {
+ let (block, i) = div_rem(bit, BITS);
+ // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
+ unsafe {
+ *self.get_unchecked_mut(block) ^= 1 << i;
+ }
+ }
+
+ /// Sets a bit to the provided `enabled` value.
+ ///
+ /// **Panics** if **bit** is out of bounds.
+ #[inline]
+ pub fn set(&mut self, bit: usize, enabled: bool) {
+ assert!(
+ bit < self.length,
+ "set at index {} exceeds fixedbitset size {}",
+ bit,
+ self.length
+ );
+ // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
+ unsafe {
+ self.set_unchecked(bit, enabled);
+ }
+ }
+
+ /// Sets a bit to the provided `enabled` value without doing any bounds checking.
+ ///
+ /// # Safety
+ /// `bit` must be less than `self.len()`
+ #[inline]
+ pub unsafe fn set_unchecked(&mut self, bit: usize, enabled: bool) {
+ let (block, i) = div_rem(bit, BITS);
+ // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
+ let elt = unsafe { self.get_unchecked_mut(block) };
+ if enabled {
+ *elt |= 1 << i;
+ } else {
+ *elt &= !(1 << i);
+ }
+ }
+
+ /// Copies boolean value from specified bit to the specified bit.
+ ///
+ /// If `from` is out-of-bounds, `to` will be unset.
+ ///
+ /// **Panics** if **to** is out of bounds.
+ #[inline]
+ pub fn copy_bit(&mut self, from: usize, to: usize) {
+ assert!(
+ to < self.length,
+ "copy to index {} exceeds fixedbitset size {}",
+ to,
+ self.length
+ );
+ let enabled = self.contains(from);
+ // SAFETY: The above assertion ensures that the block is inside the Vec's allocation.
+ unsafe { self.set_unchecked(to, enabled) };
+ }
+
+ /// Copies boolean value from specified bit to the specified bit.
+ ///
+ /// Note: unlike `copy_bit`, calling this with an invalid `from`
+ /// is undefined behavior.
+ ///
+ /// # Safety
+ /// `to` must both be less than `self.len()`
+ #[inline]
+ pub unsafe fn copy_bit_unchecked(&mut self, from: usize, to: usize) {
+ // SAFETY: Caller must ensure that `from` is within bounds.
+ let enabled = self.contains_unchecked(from);
+ // SAFETY: Caller must ensure that `to` is within bounds.
+ self.set_unchecked(to, enabled);
+ }
+
+ /// Count the number of set bits in the given bit range.
+ ///
+ /// This function is potentially much faster than using `ones(other).count()`.
+ /// 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 {
+ Self::batch_count_ones(Masks::new(range, self.length).map(|(block, mask)| {
+ // SAFETY: Masks cannot return a block index that is out of range.
+ unsafe { *self.get_unchecked(block) & mask }
+ }))
+ }
+
+ /// Count the number of unset bits in the given bit range.
+ ///
+ /// This function is potentially much faster than using `zeroes(other).count()`.
+ /// Use `..` to count the whole content of the bitset.
+ ///
+ /// **Panics** if the range extends past the end of the bitset.
+ #[inline]
+ pub fn count_zeroes<T: IndexRange>(&self, range: T) -> usize {
+ Self::batch_count_ones(Masks::new(range, self.length).map(|(block, mask)| {
+ // SAFETY: Masks cannot return a block index that is out of range.
+ unsafe { !*self.get_unchecked(block) & mask }
+ }))
+ }
+
+ /// Sets every bit in the given range to the given state (`enabled`)
+ ///
+ /// Use `..` to set 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) {
+ if enabled {
+ self.insert_range(range);
+ } else {
+ self.remove_range(range);
+ }
+ }
+
+ /// 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) {
+ for (block, mask) in Masks::new(range, self.length) {
+ // SAFETY: Masks cannot return a block index that is out of range.
+ let block = unsafe { self.get_unchecked_mut(block) };
+ *block |= mask;
+ }
+ }
+
+ /// Disables 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 remove_range<T: IndexRange>(&mut self, range: T) {
+ for (block, mask) in Masks::new(range, self.length) {
+ // SAFETY: Masks cannot return a block index that is out of range.
+ let block = unsafe { self.get_unchecked_mut(block) };
+ *block &= !mask;
+ }
+ }
+
+ /// Toggles (inverts) every bit in the given range.
+ ///
+ /// Use `..` to toggle the whole bitset.
+ ///
+ /// **Panics** if the range extends past the end of the bitset.
+ #[inline]
+ pub fn toggle_range<T: IndexRange>(&mut self, range: T) {
+ for (block, mask) in Masks::new(range, self.length) {
+ // SAFETY: Masks cannot return a block index that is out of range.
+ let block = unsafe { self.get_unchecked_mut(block) };
+ *block ^= mask;
+ }
+ }
+
+ /// Checks if the bitset contains every bit in the given range.
+ ///
+ /// **Panics** if the range extends past the end of the bitset.
+ #[inline]
+ pub fn contains_all_in_range<T: IndexRange>(&self, range: T) -> bool {
+ for (block, mask) in Masks::new(range, self.length) {
+ // SAFETY: Masks cannot return a block index that is out of range.
+ let block = unsafe { self.get_unchecked(block) };
+ if block & mask != mask {
+ return false;
+ }
+ }
+ true
+ }
+
+ /// Checks if the bitset contains at least one set bit in the given range.
+ ///
+ /// **Panics** if the range extends past the end of the bitset.
+ #[inline]
+ pub fn contains_any_in_range<T: IndexRange>(&self, range: T) -> bool {
+ for (block, mask) in Masks::new(range, self.length) {
+ // SAFETY: Masks cannot return a block index that is out of range.
+ let block = unsafe { self.get_unchecked(block) };
+ if block & mask != 0 {
+ return true;
+ }
+ }
+ false
+ }
+
+ /// View the bitset as a slice of `Block` blocks
+ #[inline]
+ pub fn as_slice(&self) -> &[Block] {
+ // SAFETY: The bits from both usize and Block are required to be reinterprettable, and
+ // neither have any padding or alignment issues. The slice constructed is within bounds
+ // of the underlying allocation. This function is called with a read-only borrow so
+ // no other write can happen as long as the returned borrow lives.
+ unsafe {
+ let ptr = self.data.as_ptr().cast::<Block>();
+ core::slice::from_raw_parts(ptr, self.usize_len())
+ }
+ }
+
+ /// View the bitset as a mutable slice of `Block` 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 [Block] {
+ // SAFETY: The bits from both usize and Block are required to be reinterprettable, and
+ // neither have any padding or alignment issues. The slice constructed is within bounds
+ // of the underlying allocation. This function is called with a mutable borrow so
+ // no other read or write can happen as long as the returned borrow lives.
+ unsafe {
+ let ptr = self.data.as_ptr().cast::<Block>();
+ core::slice::from_raw_parts_mut(ptr, self.usize_len())
+ }
+ }
+
+ /// 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((&first_block, rem)) => {
+ let (&last_block, rem) = rem.split_last().unwrap_or((&0, rem));
+ Ones {
+ bitset_front: first_block,
+ bitset_back: last_block,
+ block_idx_front: 0,
+ block_idx_back: (1 + rem.len()) * BITS,
+ remaining_blocks: rem.iter(),
+ }
+ }
+ None => Ones {
+ bitset_front: 0,
+ bitset_back: 0,
+ block_idx_front: 0,
+ block_idx_back: 0,
+ remaining_blocks: [].iter(),
+ },
+ }
+ }
+
+ /// Iterates over all enabled bits.
+ ///
+ /// Iterator element is the index of the `1` bit, type `usize`.
+ /// Unlike `ones`, this function consumes the `FixedBitset`.
+ pub fn into_ones(self) -> IntoOnes {
+ let ptr = self.data.as_ptr().cast();
+ let len = self.simd_block_len() * SimdBlock::USIZE_COUNT;
+ // SAFETY:
+ // - ptr comes from self.data, so it is valid;
+ // - self.data is valid for self.data.len() SimdBlocks,
+ // which is exactly self.data.len() * SimdBlock::USIZE_COUNT usizes;
+ // - we will keep this slice around only as long as self.data is,
+ // so it won't become dangling.
+ let slice = unsafe { core::slice::from_raw_parts(ptr, len) };
+ // SAFETY: The data pointer and capacity were created from a Vec initially. The block
+ // len is identical to that of the original.
+ let data: Vec<SimdBlock> = unsafe {
+ Vec::from_raw_parts(
+ self.data.as_ptr().cast(),
+ self.simd_block_len(),
+ self.capacity,
+ )
+ };
+ let mut iter = slice.iter().copied();
+
+ core::mem::forget(self);
+
+ IntoOnes {
+ bitset_front: iter.next().unwrap_or(0),
+ bitset_back: iter.next_back().unwrap_or(0),
+ block_idx_front: 0,
+ block_idx_back: len.saturating_sub(1) * BITS,
+ remaining_blocks: iter,
+ _buf: data,
+ }
+ }
+
+ /// Iterates over all disabled bits.
+ ///
+ /// Iterator element is the index of the `0` bit, type `usize`.
+ #[inline]
+ pub fn zeroes(&self) -> Zeroes {
+ match self.as_slice().split_first() {
+ Some((&block, rem)) => Zeroes {
+ bitset: !block,
+ block_idx: 0,
+ len: self.len(),
+ remaining_blocks: rem.iter(),
+ },
+ None => Zeroes {
+ bitset: !0,
+ block_idx: 0,
+ len: self.len(),
+ remaining_blocks: [].iter(),
+ },
+ }
+ }
+
+ /// 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,
+ }
+ }
+
+ /// 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,
+ }
+ }
+
+ /// 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.
+ ///
+ /// On calling this method, `self`'s capacity may be increased to match `other`'s.
+ pub fn union_with(&mut self, other: &FixedBitSet) {
+ if other.len() >= self.len() {
+ self.grow(other.len());
+ }
+ self.as_mut_simd_slice()
+ .iter_mut()
+ .zip(other.as_simd_slice().iter())
+ .for_each(|(x, y)| *x |= *y);
+ }
+
+ /// In-place intersection of two `FixedBitSet`s.
+ ///
+ /// On calling this method, `self`'s capacity will remain the same as before.
+ pub fn intersect_with(&mut self, other: &FixedBitSet) {
+ let me = self.as_mut_simd_slice();
+ let other = other.as_simd_slice();
+ me.iter_mut().zip(other.iter()).for_each(|(x, y)| {
+ *x &= *y;
+ });
+ let mn = core::cmp::min(me.len(), other.len());
+ for wd in &mut me[mn..] {
+ *wd = SimdBlock::NONE;
+ }
+ }
+
+ /// In-place difference of two `FixedBitSet`s.
+ ///
+ /// On calling this method, `self`'s capacity will remain the same as before.
+ pub fn difference_with(&mut self, other: &FixedBitSet) {
+ self.as_mut_simd_slice()
+ .iter_mut()
+ .zip(other.as_simd_slice().iter())
+ .for_each(|(x, y)| {
+ *x &= !*y;
+ });
+
+ // There's no need to grow self or do any other adjustments.
+ //
+ // * If self is longer than other, the bits at the end of self won't be affected since other
+ // has them implicitly set to 0.
+ // * If other is longer than self, the bits at the end of other are irrelevant since self
+ // has them set to 0 anyway.
+ }
+
+ /// In-place symmetric difference of two `FixedBitSet`s.
+ ///
+ /// On calling this method, `self`'s capacity may be increased to match `other`'s.
+ pub fn symmetric_difference_with(&mut self, other: &FixedBitSet) {
+ if other.len() >= self.len() {
+ self.grow(other.len());
+ }
+ self.as_mut_simd_slice()
+ .iter_mut()
+ .zip(other.as_simd_slice().iter())
+ .for_each(|(x, y)| {
+ *x ^= *y;
+ });
+ }
+
+ /// Computes how many bits would be set in the union between two bitsets.
+ ///
+ /// This is potentially much faster than using `union(other).count()`. Unlike
+ /// other methods like using [`union_with`] followed by [`count_ones`], this
+ /// does not mutate in place or require separate allocations.
+ #[inline]
+ pub fn union_count(&self, other: &FixedBitSet) -> usize {
+ let me = self.as_slice();
+ let other = other.as_slice();
+ let count = Self::batch_count_ones(me.iter().zip(other.iter()).map(|(x, y)| (*x | *y)));
+ match other.len().cmp(&me.len()) {
+ Ordering::Greater => count + Self::batch_count_ones(other[me.len()..].iter().copied()),
+ Ordering::Less => count + Self::batch_count_ones(me[other.len()..].iter().copied()),
+ Ordering::Equal => count,
+ }
+ }
+
+ /// Computes how many bits would be set in the intersection between two bitsets.
+ ///
+ /// This is potentially much faster than using `intersection(other).count()`. Unlike
+ /// other methods like using [`intersect_with`] followed by [`count_ones`], this
+ /// does not mutate in place or require separate allocations.
+ #[inline]
+ pub fn intersection_count(&self, other: &FixedBitSet) -> usize {
+ Self::batch_count_ones(
+ self.as_slice()
+ .iter()
+ .zip(other.as_slice())
+ .map(|(x, y)| (*x & *y)),
+ )
+ }
+
+ /// Computes how many bits would be set in the difference between two bitsets.
+ ///
+ /// This is potentially much faster than using `difference(other).count()`. Unlike
+ /// other methods like using [`difference_with`] followed by [`count_ones`], this
+ /// does not mutate in place or require separate allocations.
+ #[inline]
+ pub fn difference_count(&self, other: &FixedBitSet) -> usize {
+ Self::batch_count_ones(
+ self.as_slice()
+ .iter()
+ .zip(other.as_slice().iter())
+ .map(|(x, y)| (*x & !*y)),
+ )
+ }
+
+ /// Computes how many bits would be set in the symmetric difference between two bitsets.
+ ///
+ /// This is potentially much faster than using `symmetric_difference(other).count()`. Unlike
+ /// other methods like using [`symmetric_difference_with`] followed by [`count_ones`], this
+ /// does not mutate in place or require separate allocations.
+ #[inline]
+ pub fn symmetric_difference_count(&self, other: &FixedBitSet) -> usize {
+ let me = self.as_slice();
+ let other = other.as_slice();
+ let count = Self::batch_count_ones(me.iter().zip(other.iter()).map(|(x, y)| (*x ^ *y)));
+ match other.len().cmp(&me.len()) {
+ Ordering::Greater => count + Self::batch_count_ones(other[me.len()..].iter().copied()),
+ Ordering::Less => count + Self::batch_count_ones(me[other.len()..].iter().copied()),
+ Ordering::Equal => count,
+ }
+ }
+
+ /// 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.as_simd_slice()
+ .iter()
+ .zip(other.as_simd_slice())
+ .all(|(x, y)| (*x & *y).is_empty())
+ }
+
+ /// 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 {
+ let me = self.as_simd_slice();
+ let other = other.as_simd_slice();
+ me.iter()
+ .zip(other.iter())
+ .all(|(x, y)| x.andnot(*y).is_empty())
+ && me.iter().skip(other.len()).all(|x| x.is_empty())
+ }
+
+ /// 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)
+ }
+}
+
+impl Hash for FixedBitSet {
+ fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
+ self.length.hash(state);
+ self.as_simd_slice().hash(state);
+ }
+}
+
+impl PartialEq for FixedBitSet {
+ fn eq(&self, other: &Self) -> bool {
+ self.length == other.length && self.as_simd_slice().eq(other.as_simd_slice())
+ }
+}
+
+impl PartialOrd for FixedBitSet {
+ fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+ Some(self.cmp(other))
+ }
+}
+
+impl Ord for FixedBitSet {
+ fn cmp(&self, other: &Self) -> Ordering {
+ self.length
+ .cmp(&other.length)
+ .then_with(|| self.as_simd_slice().cmp(other.as_simd_slice()))
+ }
+}
+
+impl Default for FixedBitSet {
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+impl Drop for FixedBitSet {
+ fn drop(&mut self) {
+ // SAFETY: The data pointer and capacity were created from a Vec initially. The block
+ // len is identical to that of the original.
+ drop(unsafe {
+ Vec::from_raw_parts(self.data.as_ptr(), self.simd_block_len(), self.capacity)
+ });
+ }
+}
+
+impl Binary for FixedBitSet {
+ fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
+ if f.alternate() {
+ f.write_str("0b")?;
+ }
+
+ for i in 0..self.length {
+ if self[i] {
+ f.write_char('1')?;
+ } else {
+ f.write_char('0')?;
+ }
+ }
+
+ Ok(())
+ }
+}
+
+impl Display for FixedBitSet {
+ fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
+ Binary::fmt(&self, f)
+ }
+}
+
+/// 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> {
+ self.iter.by_ref().find(|&nxt| !self.other.contains(nxt))
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.iter.size_hint()
+ }
+}
+
+impl<'a> DoubleEndedIterator for Difference<'a> {
+ fn next_back(&mut self) -> Option<Self::Item> {
+ self.iter
+ .by_ref()
+ .rev()
+ .find(|&nxt| !self.other.contains(nxt))
+ }
+}
+
+// Difference will continue to return None once it first returns None.
+impl<'a> FusedIterator for Difference<'a> {}
+
+/// 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()
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.iter.size_hint()
+ }
+}
+
+impl<'a> DoubleEndedIterator for SymmetricDifference<'a> {
+ fn next_back(&mut self) -> Option<Self::Item> {
+ self.iter.next_back()
+ }
+}
+
+// SymmetricDifference will continue to return None once it first returns None.
+impl<'a> FusedIterator for SymmetricDifference<'a> {}
+
+/// 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> {
+ self.iter.by_ref().find(|&nxt| self.other.contains(nxt))
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.iter.size_hint()
+ }
+}
+
+impl<'a> DoubleEndedIterator for Intersection<'a> {
+ fn next_back(&mut self) -> Option<Self::Item> {
+ self.iter
+ .by_ref()
+ .rev()
+ .find(|&nxt| self.other.contains(nxt))
+ }
+}
+
+// Intersection will continue to return None once it first returns None.
+impl<'a> FusedIterator for Intersection<'a> {}
+
+/// 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()
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.iter.size_hint()
+ }
+}
+
+impl<'a> DoubleEndedIterator for Union<'a> {
+ fn next_back(&mut self) -> Option<Self::Item> {
+ self.iter.next_back()
+ }
+}
+
+// Union will continue to return None once it first returns None.
+impl<'a> FusedIterator for Union<'a> {}
+
+struct Masks {
+ first_block: usize,
+ first_mask: usize,
+ last_block: usize,
+ last_mask: usize,
+}
+
+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,
+ "invalid range {}..{} for a fixedbitset of size {}",
+ start,
+ end,
+ length
+ );
+
+ let (first_block, first_rem) = div_rem(start, BITS);
+ let (last_block, last_rem) = div_rem(end, BITS);
+
+ Masks {
+ first_block,
+ first_mask: usize::MAX << first_rem,
+ last_block,
+ last_mask: (usize::MAX >> 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, usize);
+
+ #[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,
+ }
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (self.first_block..=self.last_block).size_hint()
+ }
+}
+
+// Masks will continue to return None once it first returns None.
+impl FusedIterator for Masks {}
+
+// Masks's size_hint implementation is exact. It never returns an
+// unbounded value and always returns an exact number of values.
+impl ExactSizeIterator for Masks {}
+
+/// 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> {
+ bitset_front: usize,
+ bitset_back: usize,
+ block_idx_front: usize,
+ block_idx_back: usize,
+ remaining_blocks: core::slice::Iter<'a, usize>,
+}
+
+impl<'a> Ones<'a> {
+ #[inline]
+ pub fn last_positive_bit_and_unset(n: &mut usize) -> usize {
+ // Find the last set bit using x & -x
+ let last_bit = *n & n.wrapping_neg();
+
+ // Find the position of the last set bit
+ let position = last_bit.trailing_zeros();
+
+ // Unset the last set bit
+ *n &= *n - 1;
+
+ position as usize
+ }
+
+ #[inline]
+ fn first_positive_bit_and_unset(n: &mut usize) -> usize {
+ /* Identify the first non zero bit */
+ let bit_idx = n.leading_zeros();
+
+ /* set that bit to zero */
+ let mask = !((1_usize) << (BITS as u32 - bit_idx - 1));
+ n.bitand_assign(mask);
+
+ bit_idx as usize
+ }
+}
+
+impl<'a> DoubleEndedIterator for Ones<'a> {
+ fn next_back(&mut self) -> Option<Self::Item> {
+ while self.bitset_back == 0 {
+ match self.remaining_blocks.next_back() {
+ None => {
+ if self.bitset_front != 0 {
+ self.bitset_back = 0;
+ self.block_idx_back = self.block_idx_front;
+ return Some(
+ self.block_idx_front + BITS
+ - Self::first_positive_bit_and_unset(&mut self.bitset_front)
+ - 1,
+ );
+ } else {
+ return None;
+ }
+ }
+ Some(next_block) => {
+ self.bitset_back = *next_block;
+ self.block_idx_back -= BITS;
+ }
+ };
+ }
+
+ Some(
+ self.block_idx_back - Self::first_positive_bit_and_unset(&mut self.bitset_back) + BITS
+ - 1,
+ )
+ }
+}
+
+impl<'a> Iterator for Ones<'a> {
+ type Item = usize; // the bit position of the '1'
+
+ #[inline]
+ fn next(&mut self) -> Option<Self::Item> {
+ while self.bitset_front == 0 {
+ match self.remaining_blocks.next() {
+ Some(next_block) => {
+ self.bitset_front = *next_block;
+ self.block_idx_front += BITS;
+ }
+ None => {
+ if self.bitset_back != 0 {
+ // not needed for iteration, but for size_hint
+ self.block_idx_front = self.block_idx_back;
+ self.bitset_front = 0;
+
+ return Some(
+ self.block_idx_back
+ + Self::last_positive_bit_and_unset(&mut self.bitset_back),
+ );
+ } else {
+ return None;
+ }
+ }
+ };
+ }
+
+ Some(self.block_idx_front + Self::last_positive_bit_and_unset(&mut self.bitset_front))
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (
+ 0,
+ (Some(self.block_idx_back - self.block_idx_front + 2 * BITS)),
+ )
+ }
+}
+
+// Ones will continue to return None once it first returns None.
+impl<'a> FusedIterator for Ones<'a> {}
+
+/// An iterator producing the indices of the set bit in a set.
+///
+/// This struct is created by the [`FixedBitSet::ones`] method.
+pub struct Zeroes<'a> {
+ bitset: usize,
+ block_idx: usize,
+ len: usize,
+ remaining_blocks: core::slice::Iter<'a, usize>,
+}
+
+impl<'a> Iterator for Zeroes<'a> {
+ type Item = usize; // the bit position of the '1'
+
+ #[inline]
+ fn next(&mut self) -> Option<Self::Item> {
+ while self.bitset == 0 {
+ self.bitset = !*self.remaining_blocks.next()?;
+ self.block_idx += BITS;
+ }
+ let t = self.bitset & (0_usize).wrapping_sub(self.bitset);
+ let r = self.bitset.trailing_zeros() as usize;
+ self.bitset ^= t;
+ let bit = self.block_idx + r;
+ // The remaining zeroes beyond the length of the bitset must be excluded.
+ if bit < self.len {
+ Some(bit)
+ } else {
+ None
+ }
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (0, Some(self.len))
+ }
+}
+
+// Zeroes will stop returning Some when exhausted.
+impl<'a> FusedIterator for Zeroes<'a> {}
+
+impl Clone for FixedBitSet {
+ #[inline]
+ fn clone(&self) -> Self {
+ Self::from_blocks_and_len(Vec::from(self.as_simd_slice()), self.length)
+ }
+
+ #[inline]
+ fn clone_from(&mut self, source: &Self) {
+ if self.length < source.length {
+ // SAFETY: `fill` is uninitialized, but is immediately initialized from `source`.
+ unsafe { self.grow_inner(source.length, MaybeUninit::uninit()) };
+ }
+ let me = self.as_mut_simd_slice_uninit();
+ let them = source.as_simd_slice_uninit();
+ match me.len().cmp(&them.len()) {
+ Ordering::Greater => {
+ let (head, tail) = me.split_at_mut(them.len());
+ head.copy_from_slice(them);
+ tail.fill(MaybeUninit::new(SimdBlock::NONE));
+ }
+ Ordering::Equal => me.copy_from_slice(them),
+ // The grow_inner above ensures that self is at least as large as source.
+ // so this branch is unreachable.
+ Ordering::Less => {}
+ }
+ self.length = source.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
+ }
+}
+
+pub struct IntoOnes {
+ bitset_front: Block,
+ bitset_back: Block,
+ block_idx_front: usize,
+ block_idx_back: usize,
+ remaining_blocks: core::iter::Copied<core::slice::Iter<'static, usize>>,
+ // Keep buf along so that `remaining_blocks` remains valid.
+ _buf: Vec<SimdBlock>,
+}
+
+impl IntoOnes {
+ #[inline]
+ pub fn last_positive_bit_and_unset(n: &mut Block) -> usize {
+ // Find the last set bit using x & -x
+ let last_bit = *n & n.wrapping_neg();
+
+ // Find the position of the last set bit
+ let position = last_bit.trailing_zeros();
+
+ // Unset the last set bit
+ *n &= *n - 1;
+
+ position as usize
+ }
+
+ #[inline]
+ fn first_positive_bit_and_unset(n: &mut Block) -> usize {
+ /* Identify the first non zero bit */
+ let bit_idx = n.leading_zeros();
+
+ /* set that bit to zero */
+ let mask = !((1_usize) << (BITS as u32 - bit_idx - 1));
+ n.bitand_assign(mask);
+
+ bit_idx as usize
+ }
+}
+
+impl DoubleEndedIterator for IntoOnes {
+ fn next_back(&mut self) -> Option<Self::Item> {
+ while self.bitset_back == 0 {
+ match self.remaining_blocks.next_back() {
+ None => {
+ if self.bitset_front != 0 {
+ self.bitset_back = 0;
+ self.block_idx_back = self.block_idx_front;
+ return Some(
+ self.block_idx_front + BITS
+ - Self::first_positive_bit_and_unset(&mut self.bitset_front)
+ - 1,
+ );
+ } else {
+ return None;
+ }
+ }
+ Some(next_block) => {
+ self.bitset_back = next_block;
+ self.block_idx_back -= BITS;
+ }
+ };
+ }
+
+ Some(
+ self.block_idx_back - Self::first_positive_bit_and_unset(&mut self.bitset_back) + BITS
+ - 1,
+ )
+ }
+}
+
+impl Iterator for IntoOnes {
+ type Item = usize; // the bit position of the '1'
+
+ #[inline]
+ fn next(&mut self) -> Option<Self::Item> {
+ while self.bitset_front == 0 {
+ match self.remaining_blocks.next() {
+ Some(next_block) => {
+ self.bitset_front = next_block;
+ self.block_idx_front += BITS;
+ }
+ None => {
+ if self.bitset_back != 0 {
+ // not needed for iteration, but for size_hint
+ self.block_idx_front = self.block_idx_back;
+ self.bitset_front = 0;
+
+ return Some(
+ self.block_idx_back
+ + Self::last_positive_bit_and_unset(&mut self.bitset_back),
+ );
+ } else {
+ return None;
+ }
+ }
+ };
+ }
+
+ Some(self.block_idx_front + Self::last_positive_bit_and_unset(&mut self.bitset_front))
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (
+ 0,
+ (Some(self.block_idx_back - self.block_idx_front + 2 * BITS)),
+ )
+ }
+}
+
+// Ones will continue to return None once it first returns None.
+impl FusedIterator for IntoOnes {}
+
+impl<'a> BitAnd for &'a FixedBitSet {
+ type Output = FixedBitSet;
+ fn bitand(self, other: &FixedBitSet) -> FixedBitSet {
+ let (short, long) = {
+ if self.len() <= other.len() {
+ (self.as_simd_slice(), other.as_simd_slice())
+ } else {
+ (other.as_simd_slice(), self.as_simd_slice())
+ }
+ };
+ let mut data = Vec::from(short);
+ for (data, block) in data.iter_mut().zip(long.iter()) {
+ *data &= *block;
+ }
+ let len = core::cmp::min(self.len(), other.len());
+ FixedBitSet::from_blocks_and_len(data, len)
+ }
+}
+
+impl BitAndAssign for FixedBitSet {
+ fn bitand_assign(&mut self, other: Self) {
+ self.intersect_with(&other);
+ }
+}
+
+impl BitAndAssign<&Self> 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.as_simd_slice(), other.as_simd_slice())
+ } else {
+ (other.as_simd_slice(), self.as_simd_slice())
+ }
+ };
+ let mut data = Vec::from(long);
+ for (data, block) in data.iter_mut().zip(short.iter()) {
+ *data |= *block;
+ }
+ let len = core::cmp::max(self.len(), other.len());
+ FixedBitSet::from_blocks_and_len(data, len)
+ }
+}
+
+impl BitOrAssign for FixedBitSet {
+ fn bitor_assign(&mut self, other: Self) {
+ self.union_with(&other);
+ }
+}
+
+impl BitOrAssign<&Self> 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.as_simd_slice(), other.as_simd_slice())
+ } else {
+ (other.as_simd_slice(), self.as_simd_slice())
+ }
+ };
+ let mut data = Vec::from(long);
+ for (data, block) in data.iter_mut().zip(short.iter()) {
+ *data ^= *block;
+ }
+ let len = core::cmp::max(self.len(), other.len());
+ FixedBitSet::from_blocks_and_len(data, len)
+ }
+}
+
+impl BitXorAssign for FixedBitSet {
+ fn bitxor_assign(&mut self, other: Self) {
+ self.symmetric_difference_with(&other);
+ }
+}
+
+impl BitXorAssign<&Self> for FixedBitSet {
+ fn bitxor_assign(&mut self, other: &Self) {
+ self.symmetric_difference_with(other);
+ }
+}
diff --git a/src/range.rs b/src/range.rs
new file mode 100644
index 0000000..9b385c4
--- /dev/null
+++ b/src/range.rs
@@ -0,0 +1,45 @@
+use core::ops::{Range, RangeFrom, RangeFull, RangeTo};
+
+// 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)
+ }
+}
diff --git a/src/serde_impl.rs b/src/serde_impl.rs
new file mode 100644
index 0000000..9823159
--- /dev/null
+++ b/src/serde_impl.rs
@@ -0,0 +1,150 @@
+#[cfg(not(feature = "std"))]
+use core as std;
+
+use crate::{Block, FixedBitSet, BYTES};
+use alloc::vec::Vec;
+use core::{convert::TryFrom, fmt};
+use serde::de::{self, Deserialize, Deserializer, MapAccess, SeqAccess, Visitor};
+use serde::ser::{Serialize, SerializeStruct, Serializer};
+
+struct BitSetByteSerializer<'a>(&'a FixedBitSet);
+
+impl Serialize for FixedBitSet {
+ fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+ where
+ S: Serializer,
+ {
+ let mut struct_serializer = serializer.serialize_struct("FixedBitset", 2)?;
+ struct_serializer.serialize_field("length", &(self.length as u64))?;
+ struct_serializer.serialize_field("data", &BitSetByteSerializer(self))?;
+ struct_serializer.end()
+ }
+}
+
+impl<'a> Serialize for BitSetByteSerializer<'a> {
+ fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+ where
+ S: Serializer,
+ {
+ let len = self.0.as_slice().len() * BYTES;
+ // PERF: Figure out a way to do this without allocating.
+ let mut temp = Vec::with_capacity(len);
+ for block in self.0.as_slice() {
+ temp.extend(&block.to_le_bytes());
+ }
+ serializer.serialize_bytes(&temp)
+ }
+}
+
+impl<'de> Deserialize<'de> for FixedBitSet {
+ fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+ where
+ D: Deserializer<'de>,
+ {
+ enum Field {
+ Length,
+ Data,
+ }
+
+ fn bytes_to_data(length: usize, input: &[u8]) -> Vec<Block> {
+ let block_len = length / BYTES + 1;
+ let mut data = Vec::with_capacity(block_len);
+ for chunk in input.chunks(BYTES) {
+ match <&[u8; BYTES]>::try_from(chunk) {
+ Ok(bytes) => data.push(usize::from_le_bytes(*bytes)),
+ Err(_) => {
+ let mut bytes = [0u8; BYTES];
+ bytes[0..BYTES].copy_from_slice(chunk);
+ data.push(usize::from_le_bytes(bytes));
+ }
+ }
+ }
+ data
+ }
+
+ impl<'de> Deserialize<'de> for Field {
+ fn deserialize<D>(deserializer: D) -> Result<Field, D::Error>
+ where
+ D: Deserializer<'de>,
+ {
+ struct FieldVisitor;
+
+ impl<'de> Visitor<'de> for FieldVisitor {
+ type Value = Field;
+
+ fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+ formatter.write_str("`length` or `data`")
+ }
+
+ fn visit_str<E>(self, value: &str) -> Result<Field, E>
+ where
+ E: de::Error,
+ {
+ match value {
+ "length" => Ok(Field::Length),
+ "data" => Ok(Field::Data),
+ _ => Err(de::Error::unknown_field(value, FIELDS)),
+ }
+ }
+ }
+
+ deserializer.deserialize_identifier(FieldVisitor)
+ }
+ }
+
+ struct FixedBitSetVisitor;
+
+ impl<'de> Visitor<'de> for FixedBitSetVisitor {
+ type Value = FixedBitSet;
+
+ fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+ formatter.write_str("struct Duration")
+ }
+
+ fn visit_seq<V>(self, mut seq: V) -> Result<FixedBitSet, V::Error>
+ where
+ V: SeqAccess<'de>,
+ {
+ let length = seq
+ .next_element()?
+ .ok_or_else(|| de::Error::invalid_length(0, &self))?;
+ let data: &[u8] = seq
+ .next_element()?
+ .ok_or_else(|| de::Error::invalid_length(1, &self))?;
+ let data = bytes_to_data(length, data);
+ Ok(FixedBitSet::with_capacity_and_blocks(length, data))
+ }
+
+ fn visit_map<V>(self, mut map: V) -> Result<FixedBitSet, V::Error>
+ where
+ V: MapAccess<'de>,
+ {
+ let mut length = None;
+ let mut temp: Option<&[u8]> = None;
+ while let Some(key) = map.next_key()? {
+ match key {
+ Field::Length => {
+ if length.is_some() {
+ return Err(de::Error::duplicate_field("length"));
+ }
+ length = Some(map.next_value()?);
+ }
+ Field::Data => {
+ if temp.is_some() {
+ return Err(de::Error::duplicate_field("data"));
+ }
+ temp = Some(map.next_value()?);
+ }
+ }
+ }
+ let length = length.ok_or_else(|| de::Error::missing_field("length"))?;
+ let data = temp.ok_or_else(|| de::Error::missing_field("data"))?;
+ let data = bytes_to_data(length, data);
+ Ok(FixedBitSet::with_capacity_and_blocks(length, data))
+ }
+ }
+
+ const FIELDS: &'static [&'static str] = &["length", "data"];
+ deserializer.deserialize_struct("Duration", FIELDS, FixedBitSetVisitor)
+ }
+}
diff --git a/tests/tests.rs b/tests/tests.rs
new file mode 100644
index 0000000..fcc334d
--- /dev/null
+++ b/tests/tests.rs
@@ -0,0 +1,1313 @@
+use fixedbitset::*;
+
+#[cfg(target_family = "wasm")]
+use wasm_bindgen_test::*;
+#[cfg(target_family = "wasm")]
+wasm_bindgen_test::wasm_bindgen_test_configure!(run_in_browser);
+
+extern crate alloc;
+
+const BITS: usize = core::mem::size_of::<Block>() * 8;
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn with_blocks() {
+ let fb = FixedBitSet::with_capacity_and_blocks(50, vec![8, 0]);
+ assert!(fb.contains(3));
+
+ let ones: Vec<_> = fb.ones().collect();
+ assert_eq!(ones.len(), 1);
+
+ let ones: Vec<_> = fb.ones().rev().collect();
+ assert_eq!(ones.len(), 1);
+
+ let ones: Vec<_> = fb.ones().rev().alternate().collect();
+ assert_eq!(ones.len(), 1);
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn with_blocks_too_small() {
+ let mut fb = FixedBitSet::with_capacity_and_blocks(500, vec![8, 0]);
+ fb.insert(400);
+ assert!(fb.contains(400));
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn with_blocks_too_big() {
+ let fb = FixedBitSet::with_capacity_and_blocks(1, vec![8]);
+
+ // since capacity is 1, 3 shouldn't be set here
+ assert!(!fb.contains(3));
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn with_blocks_too_big_range_check() {
+ let fb = FixedBitSet::with_capacity_and_blocks(1, vec![0xff]);
+
+ // since capacity is 1, only 0 should be set
+ assert!(fb.contains(0));
+ for i in 1..0xff {
+ assert!(!fb.contains(i));
+ }
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn grow_and_insert() {
+ let mut fb = FixedBitSet::default();
+ for i in 0..100 {
+ if i % 3 == 0 {
+ fb.grow_and_insert(i);
+ }
+ }
+
+ assert_eq!(fb.count_ones(..), 34);
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn count_zeroes() {
+ 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_zeroes(..7), 7);
+ assert_eq!(fb.count_zeroes(..8), 7);
+ assert_eq!(fb.count_zeroes(..11), 10);
+ assert_eq!(fb.count_zeroes(..12), 10);
+ assert_eq!(fb.count_zeroes(..13), 10);
+ assert_eq!(fb.count_zeroes(..35), 32);
+ assert_eq!(fb.count_zeroes(..36), 32);
+ assert_eq!(fb.count_zeroes(..40), 36);
+ assert_eq!(fb.count_zeroes(..41), 36);
+ assert_eq!(fb.count_zeroes(50..), 46);
+ assert_eq!(fb.count_zeroes(70..95), 24);
+ assert_eq!(fb.count_zeroes(70..96), 24);
+ assert_eq!(fb.count_zeroes(70..99), 27);
+ assert_eq!(fb.count_zeroes(..), 91);
+ assert_eq!(fb.count_zeroes(0..100), 91);
+ assert_eq!(fb.count_zeroes(0..0), 0);
+ assert_eq!(fb.count_zeroes(100..100), 0);
+ assert_eq!(fb.count_zeroes(7..), 84);
+ assert_eq!(fb.count_zeroes(8..), 84);
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn minimum() {
+ let mut fb = FixedBitSet::with_capacity(100);
+ assert_eq!(fb.minimum(), None);
+ fb.set(95, true);
+ assert_eq!(fb.minimum(), Some(95));
+ fb.set(77, true);
+ assert_eq!(fb.minimum(), Some(77));
+ fb.set(12, true);
+ assert_eq!(fb.minimum(), Some(12));
+ fb.set(40, true);
+ assert_eq!(fb.minimum(), Some(12));
+ fb.set(35, true);
+ assert_eq!(fb.minimum(), Some(12));
+ fb.set(11, true);
+ assert_eq!(fb.minimum(), Some(11));
+ fb.set(7, true);
+ assert_eq!(fb.minimum(), Some(7));
+ fb.set(50, true);
+ assert_eq!(fb.minimum(), Some(7));
+ fb.set(99, true);
+ assert_eq!(fb.minimum(), Some(7));
+ fb.clear();
+ assert_eq!(fb.minimum(), None);
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn maximum() {
+ let mut fb = FixedBitSet::with_capacity(100);
+ assert_eq!(fb.maximum(), None);
+ fb.set(11, true);
+ assert_eq!(fb.maximum(), Some(11));
+ fb.set(12, true);
+ assert_eq!(fb.maximum(), Some(12));
+ fb.set(7, true);
+ assert_eq!(fb.maximum(), Some(12));
+ fb.set(40, true);
+ assert_eq!(fb.maximum(), Some(40));
+ fb.set(35, true);
+ assert_eq!(fb.maximum(), Some(40));
+ fb.set(95, true);
+ assert_eq!(fb.maximum(), Some(95));
+ fb.set(50, true);
+ assert_eq!(fb.maximum(), Some(95));
+ fb.set(77, true);
+ assert_eq!(fb.maximum(), Some(95));
+ fb.set(99, true);
+ assert_eq!(fb.maximum(), Some(99));
+ fb.clear();
+ assert_eq!(fb.maximum(), None);
+}
+
+/* Helper for testing double ended iterator */
+#[cfg(test)]
+struct Alternating<I> {
+ iter: I,
+ front: bool,
+}
+
+#[cfg(test)]
+impl<I: Iterator + DoubleEndedIterator> Iterator for Alternating<I> {
+ type Item = I::Item;
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.iter.size_hint()
+ }
+ fn next(&mut self) -> Option<Self::Item> {
+ if self.front {
+ self.front = false;
+ self.iter.next()
+ } else {
+ self.front = true;
+ self.iter.next_back()
+ }
+ }
+}
+#[cfg(test)]
+trait AlternatingExt: Iterator + DoubleEndedIterator + Sized {
+ fn alternate(self) -> Alternating<Self> {
+ Alternating {
+ iter: self,
+ front: true,
+ }
+ }
+}
+
+#[cfg(test)]
+impl<I: Iterator + DoubleEndedIterator> AlternatingExt for I {}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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();
+ let ones_rev: Vec<_> = fb.ones().rev().collect();
+ let ones_alternating: Vec<_> = fb.ones().alternate().collect();
+
+ let mut known_result = vec![7, 11, 12, 35, 40, 50, 77, 95, 99];
+
+ assert_eq!(known_result, ones);
+ known_result.reverse();
+ assert_eq!(known_result, ones_rev);
+ let known_result: Vec<_> = known_result.into_iter().rev().alternate().collect();
+ assert_eq!(known_result, ones_alternating);
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn into_ones() {
+ fn create() -> FixedBitSet {
+ 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);
+ fb
+ }
+
+ let ones: Vec<_> = create().into_ones().collect();
+ let ones_rev: Vec<_> = create().into_ones().rev().collect();
+ let ones_alternating: Vec<_> = create().into_ones().alternate().collect();
+
+ let mut known_result = vec![7, 11, 12, 35, 40, 50, 77, 95, 99];
+
+ assert_eq!(known_result, ones);
+ known_result.reverse();
+ assert_eq!(known_result, ones_rev);
+ let known_result: Vec<_> = known_result.into_iter().rev().alternate().collect();
+ assert_eq!(known_result, ones_alternating);
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn size_hint() {
+ let iters = if cfg!(miri) { 250 } else { 1000 };
+ for s in 0..iters {
+ let mut bitset = FixedBitSet::with_capacity(s);
+ bitset.insert_range(..);
+ let mut t = s;
+ let mut iter = bitset.ones().rev();
+ loop {
+ match iter.next() {
+ None => break,
+ Some(_) => {
+ t -= 1;
+ assert!(iter.size_hint().1.unwrap() >= t);
+ // factor two, because we have first block and last block
+ assert!(iter.size_hint().1.unwrap() <= t + 2 * BITS);
+ }
+ }
+ }
+ assert_eq!(t, 0);
+ }
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn size_hint_alternate() {
+ let iters = if cfg!(miri) { 250 } else { 1000 };
+ for s in 0..iters {
+ let mut bitset = FixedBitSet::with_capacity(s);
+ bitset.insert_range(..);
+ let mut t = s;
+ extern crate std;
+ let mut iter = bitset.ones().alternate();
+ loop {
+ match iter.next() {
+ None => break,
+ Some(_) => {
+ t -= 1;
+ assert!(iter.size_hint().1.unwrap() >= t);
+ assert!(iter.size_hint().1.unwrap() <= t + 3 * BITS);
+ }
+ }
+ }
+ assert_eq!(t, 0);
+ }
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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();
+ let ones_rev: Vec<_> = fb.ones().rev().collect();
+ let expected_rev: Vec<_> = (from..to).rev().collect();
+ let ones_rev_alt: Vec<_> = fb.ones().rev().alternate().collect();
+ let expected_rev_alt: Vec<_> = (from..to).rev().alternate().collect();
+ assert_eq!(expected, ones);
+ assert_eq!(expected_rev, ones_rev);
+ assert_eq!(expected_rev_alt, ones_rev_alt);
+ }
+
+ for i in 0..100 {
+ test_range(i, 100, 100);
+ test_range(0, i, 100);
+ }
+}
+
+#[should_panic]
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn count_ones_oob() {
+ let fb = FixedBitSet::with_capacity(100);
+ fb.count_ones(90..101);
+}
+
+#[should_panic]
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn count_ones_negative_range() {
+ let fb = FixedBitSet::with_capacity(100);
+ fb.count_ones(90..80);
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn count_ones_panic() {
+ let iters = if cfg!(miri) { 48 } else { 128 };
+ for i in 1..iters {
+ 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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn default() {
+ let fb = FixedBitSet::default();
+ assert_eq!(fb.len(), 0);
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn contains_all_in_range() {
+ let mut fb = FixedBitSet::with_capacity(48);
+ fb.insert_range(..);
+
+ fb.remove_range(..32);
+ fb.remove_range(37..);
+
+ assert!(fb.contains_all_in_range(32..37));
+ assert!(fb.contains_all_in_range(32..35));
+ assert!(!fb.contains_all_in_range(32..));
+ assert!(!fb.contains_all_in_range(..37));
+ assert!(!fb.contains_all_in_range(..));
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn contains_any_in_range() {
+ let mut fb = FixedBitSet::with_capacity(48);
+ fb.insert_range(..);
+
+ fb.remove_range(..32);
+ fb.remove_range(37..);
+
+ assert!(!fb.contains_any_in_range(..32));
+ assert!(fb.contains_any_in_range(32..37));
+ assert!(fb.contains_any_in_range(32..35));
+ assert!(fb.contains_any_in_range(32..));
+ assert!(fb.contains_any_in_range(..37));
+ assert!(!fb.contains_any_in_range(37..));
+ assert!(fb.contains_any_in_range(..));
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn remove_range() {
+ let mut fb = FixedBitSet::with_capacity(48);
+ fb.insert_range(..);
+
+ fb.remove_range(..32);
+ fb.remove_range(37..);
+
+ for i in 0..48 {
+ assert_eq!(fb.contains(i), 32 <= i && i < 37);
+ }
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn toggle_range() {
+ let mut fb = FixedBitSet::with_capacity(40);
+ fb.insert_range(..10);
+ fb.insert_range(34..38);
+
+ fb.toggle_range(5..12);
+ fb.toggle_range(30..);
+
+ for i in 0..40 {
+ assert_eq!(
+ fb.contains(i),
+ i < 5 || 10 <= i && i < 12 || 30 <= i && i < 34 || 38 <= i
+ );
+ }
+ assert!(!fb.contains(40));
+ assert!(!fb.contains(64));
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn bitand_first_smaller() {
+ let a_len = 113;
+ let b_len = 137;
+ let len = core::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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn bitand_first_larger() {
+ let a_len = 173;
+ let b_len = 137;
+ let len = core::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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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 count = a.intersection_count(&b);
+ let iterator_count = a.intersection(&b).count();
+ let mut 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));
+ }
+
+ a.intersect_with(&b);
+ // intersection + collect produces the same results but with a shorter length.
+ ab.grow(a.len());
+ assert_eq!(
+ ab, a,
+ "intersection and intersect_with produce the same results"
+ );
+ assert_eq!(
+ ab.count_ones(..),
+ count,
+ "intersection and intersection_count produce the same results"
+ );
+ assert_eq!(
+ count, iterator_count,
+ "intersection and intersection_count produce the same results"
+ );
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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 count = a.union_count(&b);
+ let iterator_count = a.union(&b).count();
+ 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));
+ }
+
+ a.union_with(&b);
+ assert_eq!(ab, a, "union and union_with produce the same results");
+ assert_eq!(
+ count,
+ ab.count_ones(..),
+ "union and union_count produce the same results"
+ );
+ assert_eq!(
+ count, iterator_count,
+ "union and union_count produce the same results"
+ );
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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 count = a.difference_count(&b);
+ let iterator_count = a.difference(&b).count();
+ let mut 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));
+ }
+
+ a.difference_with(&b);
+ // difference + collect produces the same results but with a shorter length.
+ a_diff_b.grow(a.len());
+ assert_eq!(
+ a_diff_b, a,
+ "difference and difference_with produce the same results"
+ );
+ assert_eq!(
+ a_diff_b.count_ones(..),
+ count,
+ "difference and difference_count produce the same results"
+ );
+ assert_eq!(
+ count, iterator_count,
+ "intersection and intersection_count produce the same results"
+ );
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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 count = a.symmetric_difference_count(&b);
+ let iterator_count = a.symmetric_difference(&b).count();
+ 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));
+ }
+
+ a.symmetric_difference_with(&b);
+ assert_eq!(
+ a_sym_diff_b, a,
+ "symmetric_difference and _with produce the same results"
+ );
+ assert_eq!(
+ a_sym_diff_b.count_ones(..),
+ count,
+ "symmetric_difference and _count produce the same results"
+ );
+ assert_eq!(
+ count, iterator_count,
+ "symmetric_difference and _count produce the same results"
+ );
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn bitxor_first_smaller() {
+ let a_len = 113;
+ let b_len = 137;
+ let len = core::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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn bitxor_first_larger() {
+ let a_len = 173;
+ let b_len = 137;
+ let len = core::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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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_eq!(res, a_or_b);
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn op_assign_ref() {
+ let mut a = FixedBitSet::with_capacity(8);
+ let b = FixedBitSet::with_capacity(8);
+
+ //check that all assign type operators work on references
+ a &= &b;
+ a |= &b;
+ a ^= &b;
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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_eq!(ones, expected);
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_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>>()
+ );
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn zeroes() {
+ let len = 232;
+ let mut fb = FixedBitSet::with_capacity(len);
+ for i in (0..len).filter(|i| i % 7 == 0) {
+ fb.insert(i);
+ }
+ let zeroes = fb.zeroes().collect::<Vec<usize>>();
+
+ assert_eq!(
+ zeroes,
+ vec![
+ 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27,
+ 29, 30, 31, 32, 33, 34, 36, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 48, 50, 51, 52, 53,
+ 54, 55, 57, 58, 59, 60, 61, 62, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 75, 76, 78, 79,
+ 80, 81, 82, 83, 85, 86, 87, 88, 89, 90, 92, 93, 94, 95, 96, 97, 99, 100, 101, 102, 103,
+ 104, 106, 107, 108, 109, 110, 111, 113, 114, 115, 116, 117, 118, 120, 121, 122, 123,
+ 124, 125, 127, 128, 129, 130, 131, 132, 134, 135, 136, 137, 138, 139, 141, 142, 143,
+ 144, 145, 146, 148, 149, 150, 151, 152, 153, 155, 156, 157, 158, 159, 160, 162, 163,
+ 164, 165, 166, 167, 169, 170, 171, 172, 173, 174, 176, 177, 178, 179, 180, 181, 183,
+ 184, 185, 186, 187, 188, 190, 191, 192, 193, 194, 195, 197, 198, 199, 200, 201, 202,
+ 204, 205, 206, 207, 208, 209, 211, 212, 213, 214, 215, 216, 218, 219, 220, 221, 222,
+ 223, 225, 226, 227, 228, 229, 230
+ ]
+ );
+}
+
+#[cfg(feature = "std")]
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn binary_trait() {
+ let items: Vec<usize> = vec![1, 5, 7, 10, 14, 15];
+ let fb = items.iter().cloned().collect::<FixedBitSet>();
+
+ assert_eq!(alloc::format!("{:b}", fb), "0100010100100011");
+ assert_eq!(alloc::format!("{:#b}", fb), "0b0100010100100011");
+}
+
+#[cfg(feature = "std")]
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn display_trait() {
+ let len = 8;
+ let mut fb = FixedBitSet::with_capacity(len);
+
+ fb.put(4);
+ fb.put(2);
+
+ assert_eq!(alloc::format!("{}", fb), "00101000");
+ assert_eq!(alloc::format!("{:#}", fb), "0b00101000");
+}
+
+// TODO: Rewite this test to be platform agnostic.
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+#[cfg(all(feature = "serde", target_pointer_width = "64"))]
+fn test_serialize() {
+ let mut fb = FixedBitSet::with_capacity(10);
+ fb.put(2);
+ fb.put(3);
+ fb.put(6);
+ fb.put(8);
+ let serialized = serde_json::to_string(&fb).unwrap();
+ assert_eq!(r#"{"length":10,"data":[76,1,0,0,0,0,0,0]}"#, serialized);
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn test_is_clear() {
+ let mut fb = FixedBitSet::with_capacity(0);
+ assert!(fb.is_clear());
+
+ fb.grow(1);
+ assert!(fb.is_clear());
+
+ fb.put(0);
+ assert!(!fb.is_clear());
+
+ fb.grow(42);
+ fb.clear();
+ assert!(fb.is_clear());
+
+ fb.put(17);
+ fb.put(19);
+ assert!(!fb.is_clear());
+}
+
+#[test]
+#[cfg_attr(target_family = "wasm", wasm_bindgen_test)]
+fn test_is_full() {
+ let mut fb = FixedBitSet::with_capacity(0);
+ assert!(fb.is_full());
+
+ fb.grow(1);
+ assert!(!fb.is_full());
+
+ fb.put(0);
+ assert!(fb.is_full());
+
+ fb.grow(42);
+ fb.clear();
+ assert!(!fb.is_full());
+
+ fb.put(17);
+ fb.put(19);
+ assert!(!fb.is_full());
+
+ fb.insert_range(..);
+ assert!(fb.is_full());
+}
+
+#[test]
+fn clone() {
+ let mut fb = FixedBitSet::with_capacity(10000);
+ 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 fb_clone = fb.clone();
+ let mut fb_clone_from_smaller = FixedBitSet::with_capacity(1000000);
+ let mut fb_clone_from_same = FixedBitSet::with_capacity(10000);
+ let mut fb_clone_from_bigger = FixedBitSet::with_capacity(100);
+ fb_clone_from_smaller.clone_from(&fb);
+ fb_clone_from_same.clone_from(&fb);
+ fb_clone_from_bigger.clone_from(&fb);
+
+ assert_eq!(&fb, &fb_clone);
+ assert_eq!(&fb, &fb_clone_from_smaller);
+ assert_eq!(&fb, &fb_clone_from_same);
+ assert_eq!(&fb, &fb_clone_from_bigger);
+}
