contain-rs / bit-set Goto Github PK

View Code? Open in Web Editor NEW

61.0 7.0 25.0 705 KB

A Set of Bits

License: Apache License 2.0

Rust 100.00%

bit-set's Introduction

bit-set

A compact set of bits.

Usage

Add this to your Cargo.toml:

[dependencies]
bit-set = "0.8"

Since Rust 2018, extern crate is no longer mandatory. If your edition is old (Rust 2015), add this to your crate root:

extern crate bit_set;

If you want to use serde, enable it with the serde feature:

[dependencies]
bit-set = { version = "0.8", features = ["serde"] }

If you want to use bit-set in a program that has #![no_std], just drop default features:

[dependencies]
bit-set = { version = "0.8", default-features = false }

Description

An implementation of a set using a bit vector as an underlying representation for holding unsigned numerical elements.

It should also be noted that the amount of storage necessary for holding a set of objects is proportional to the maximum of the objects when viewed as a usize.

Examples

use bit_set::BitSet;

// It's a regular set
let mut s = BitSet::new();
s.insert(0);
s.insert(3);
s.insert(7);

s.remove(7);

if !s.contains(7) {
    println!("There is no 7");
}

// Can initialize from a `BitVec`
let other = BitSet::from_bytes(&[0b11010000]);

s.union_with(&other);

// Print 0, 1, 3 in some order
for x in s.iter() {
    println!("{}", x);
}

// Can convert back to a `BitVec`
let bv = s.into_bit_vec();
assert!(bv[3]);

License

Dual-licensed for compatibility with the Rust project.

Licensed under the Apache License Version 2.0: http://www.apache.org/licenses/LICENSE-2.0, or the MIT license: http://opensource.org/licenses/MIT, at your option.

bit-set's People

Contributors

Stargazers

Watchers

bit-set's Issues

Grab tests from libcollectionstest

Forgot

remove dependence on feature(core)

Too lazy right now

Faster counts on union/intersection/etc

In my use case, I need to compute:

a.union(b).count()

In the current implementation this is really slow. However, if we override the default count implementation for the iterators they could use bitcount to be much more efficient.

Would a PR of that nature be acceptable? Or is the project too "frozen" for that.

unnecessary use of pointers for remove and contains

the remove and contains methods for bitset take an argument of type &usize, but there seems to be no reason for this instead of just taking a usize directly.

shrink_to_fit method corrupts an empty bitset

Bug in BitSet::shrink_to_fit method

Crate version: 0.5.2

Description: BitSet::shrink_to_fit(...) method being applied to a newly created bitset corrupts the internals state of the bit set. The following test demonstrates the problem:

#[test]
fn shrink_new_bit_set() {
    let mut set = BitSet::new();
    set.shrink_to_fit();
    set.contains(1);
}

The last line panics with message "index out of bounds". The cause is that in lib.rs, line 389 the trunc_len is set to 1 if there are no blocks, after truncation the vector of blocks is still empty but the number of bits is set to the size of the single block.

Make use of `BitVec::insert`

contain-rs/bit-vec#106

No idea how to expose this efficient function.

Add support for serialization/deserialization

It would be useful if bit_set::BitSet supported serialization for serde. Today, if I add a BitSet to my struct, I get the following compiler errors because codegen can't automatically generate serialization for BitSet:

error[E0277]: the trait bound `bit_set::BitSet: serde::Serialize` is not satisfied
  --> src\coverage.rs:20:10
   |
20 | #[derive(Serialize, Deserialize)]
   |          ^^^^^^^^^ the trait `serde::Serialize` is not implemented for `bit_set::BitSet`
   |
   = note: required by `serde::ser::SerializeStruct::serialize_field`

error[E0277]: the trait bound `bit_set::BitSet: serde::Deserialize` is not satisfied
  --> src\coverage.rs:20:21
   |
20 | #[derive(Serialize, Deserialize)]
   |                     ^^^^^^^^^^^ the trait `serde::Deserialize` is not implemented for `bit_set::BitSet`
   |
   = note: required by `serde::de::SeqVisitor::visit`

error[E0277]: the trait bound `bit_set::BitSet: serde::Deserialize` is not satisfied
  --> src\coverage.rs:20:21
   |
20 | #[derive(Serialize, Deserialize)]
   |                     ^^^^^^^^^^^ the trait `serde::Deserialize` is not implemented for `bit_set::BitSet`
   |
   = note: required by `serde::de::MapVisitor::visit_value`

error[E0277]: the trait bound `bit_set::BitSet: serde::Deserialize` is not satisfied
  --> src\coverage.rs:20:21
   |
20 | #[derive(Serialize, Deserialize)]
   |                     ^^^^^^^^^^^ the trait `serde::Deserialize` is not implemented for `bit_set::BitSet`
   |
   = note: required by `serde::de::private::missing_field`

Duplicate license

crates.io indicates MIT/Apache-2.0 for this crate, but the file LICENSE-MIT contains the Apache 2.0 license.

If this is a mistake, I'd be grateful if you could switch the license and republish to crates.io. :)

Size of empty bitset is 32 bytes

let s = BitSet::new();
println!("Size of bitset: {} bytes", std::mem::size_of_val(&s));

The above code gives 32 bytes as the size of empty bitset. Why does an empty bitset need to be 32 bytes?
Also, with a bitset of larger capacity, I still get the size as 32 bits. Shouldn't a bitset of capacity 1024 be 1024/8 = 128 bytes ?

let s = BitSet::with_capacity(1024);
println!("Size of bitset: {} bytes", std::mem::size_of_val(&s));

A "get_mut" method?

Similar to existing get_ref.

Set/unset bits iterator

We could use leading_zeros or trailing_zeros to iterate over the indices of set or unset bits, avoiding lots of arithmetic/shifting.

contain-rs/bit-vec#44

Rename reserve_len, reserve_len_exact

These go against the convention from libstd; they should be reserve and reserve_exact.

IntoIter?

I need an iterator for BitSet that owns all its data to implement an IntoIter for a struct in select.rs, but I couldn't find any IntoIter struct in this crate. Is there a reason it isn't present (other than no one ever asked for it)? Would you accept a PR to add an IntoIter like the bit-vec crate has?

Move BitSet constructors from impl<u32> to impl<B>

The way things are, BitSet<B> for any B except u32 is almost unusable. The only constructor is pretty much hidden (default()).
I propose to move the constructors around from the specialized implementation to the generic one.
It may impact the performances for some use cases. I'm prepared to look into it.
But first, I would love to hear your thought on this.

Best to get a maximum of all elements, then grow once if needed.

impl<B: BitBlock> Extend<usize> for BitSet<B> {
    #[inline]
    fn extend<I: IntoIterator<Item = usize>>(&mut self, iter: I) {
        for i in iter {
            self.insert(i);
        }
    }
}

Broken compilation as a dependency

For some reason I get this error with latest stable [email protected]

Running `rustc --crate-name big_enum_set_derive --edition=2018 /github.com-1ecc6299db9ec823/big_enum_set_derive-0.1.6/src/lib.rs --error-format=json --json=diagnostic-rendered-ansi --crate-type proc-macro --emit=dep-info,link -C prefer-dynamic -C debuginfo=2 --cfg 'feature="serde"' -C metadata=82cd449cce14ad1b -C extra-filename=-82cd449cce14ad1b --out-dir /target/debug/deps -L dependency=/target/debug/deps --extern bit_set=/target/debug/deps/libbit_set-4520cb6de2dc6fe1.rlib --extern bit_vec=/target/debug/deps/libbit_vec-f0539eb5babad206.rlib --extern darling=/target/debug/deps/libdarling-928fe7e4429f8545.rlib --extern proc_macro2=/target/debug/deps/libproc_macro2-c2ad304f8ec9961e.rlib --extern quote=/target/debug/deps/libquote-eb0e517bdf4c6699.rlib --extern syn=/target/debug/deps/libsyn-4bd95eee795b32bf.rlib --extern proc_macro --cap-lints allow -C link-arg=-fuse-ld=lld -C link-arg=-fuse-ld=lld`
       Fresh specs v0.15.1
error[E0599]: no function or associated item named `from_iter` found for struct `bit_set::BitSet<B>` in the current scope
   --> /github.com-1ecc6299db9ec823/big_enum_set_derive-0.1.6/src/lib.rs:203:22
    |
203 |         BitSet::<B>::from_iter(all_variants)
    |                      ^^^^^^^^^ function or associated item not found in `bit_set::BitSet<B>`
    | 
   ::: /github.com-1ecc6299db9ec823/bit-set-0.5.2/src/lib.rs:105:1
    |
105 | pub struct BitSet<B = u32> {
    | -------------------------- doesn't satisfy `bit_set::BitSet<B>: std::iter::FromIterator<usize>`
    |
    = note: the method `from_iter` exists but the following trait bounds were not satisfied:
            `B: bit_vec::BitBlock`
            which is required by `bit_set::BitSet<B>: std::iter::FromIterator<usize>`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0599`.
error: could not compile `big_enum_set_derive`.

This happens while compiling big_enum_set_derive as a dependency, doesn't seem to have anything to do with the project using it.

Broken URLs in documentation

For example, on this page:
https://contain-rs.github.io/bit-set/bit_set/struct.Difference.html

Clicking on [src] near the top right goes to:
https://contain-rs.github.io/bit-set/src/bit_set/src/lib.rs.html.html#833

whereas the correct address ought to be:
https://contain-rs.github.io/bit-set/src/bit_set/src/lib.rs.html#833

Broken compilation for no_std

error[E0432]: unresolved import `alloc::prelude::Vec`
   --> /home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/bit-vec-0.5.1/src/lib.rs:103:5
    |
103 | use alloc::prelude::Vec;
    |     ^^^^^^^^^^^^^^^^^^^ no `Vec` in `prelude`

   Compiling rand_core v0.3.1
error[E0392]: parameter `B` is never used
    --> /home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/bit-vec-0.5.1/src/lib.rs:1262:21
     |
1262 | pub struct IntoIter<B=u32> {
     |                     ^ unused type parameter
     |
     = help: consider removing `B` or using a marker such as `core::marker::PhantomData`

error[E0392]: parameter `B` is never used
    --> /home/user/.cargo/registry/src/github.com-1ecc6299db9ec823/bit-vec-0.5.1/src/lib.rs:1221:21
     |
1221 | pub struct Iter<'a, B: 'a = u32> {
     |                     ^ unused type parameter
     |
     = help: consider removing `B` or using a marker such as `core::marker::PhantomData`

error: aborting due to 3 previous errors

Some errors occurred: E0392, E0432.
For more information about an error, try `rustc --explain E0392`.