#![warn(
// missing_docs,
// rustdoc::missing_doc_code_examples,
future_incompatible,
rust_2018_idioms,
unused,
trivial_casts,
trivial_numeric_casts,
unused_lifetimes,
unused_qualifications,
unused_crate_dependencies,
clippy::cargo,
clippy::multiple_crate_versions,
clippy::empty_line_after_outer_attr,
clippy::fallible_impl_from,
clippy::redundant_pub_crate,
clippy::use_self,
clippy::suspicious_operation_groupings,
clippy::useless_let_if_seq,
// clippy::missing_errors_doc,
// clippy::missing_panics_doc,
clippy::wildcard_imports
)]
#![doc(html_logo_url = "https://raw.githubusercontent.com/HellButcher/pulz/master/docs/logo.png")]
#![doc(html_no_source)]
#![doc = include_str!("../README.md")]
use std::ops::Range;
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct BitSet(Vec<u64>);
impl BitSet {
#[inline]
pub const fn new() -> Self {
Self(Vec::new())
}
pub fn clear(&mut self) {
self.0.clear()
}
pub fn from_range(range: Range<usize>) -> Self {
let words_from = range.start / 64;
let words_to = range.end / 64;
let words_from_rest = range.end % 64;
let words_to_rest = range.end % 64;
let mut result = Vec::with_capacity(words_to + 1);
result.resize(words_from, u64::MAX); if words_from == words_to {
let mut value = !0u64;
if words_from_rest != 0 {
value <<= words_from_rest;
}
if words_to_rest != 0 {
value &= !(!0u64 << words_to_rest);
}
if value != 0 {
result.push(value);
}
} else {
if words_from_rest != 0 {
result.push(!0u64 << words_from_rest);
}
result.resize(words_to, u64::MAX); if words_to_rest != 0 {
result.push(!(!0u64 << words_to_rest));
}
}
Self(result)
}
#[inline]
fn split_value(value: usize) -> (usize, u64) {
let index = value / 64;
let bits = 1u64 << (value % 64);
(index, bits)
}
#[inline]
pub fn contains(&self, value: usize) -> bool {
let (index, bits) = Self::split_value(value);
if let Some(word) = self.0.get(index) {
*word & bits != 0
} else {
false
}
}
pub fn insert(&mut self, value: usize) -> bool {
let (index, bits) = Self::split_value(value);
if index >= self.0.len() {
self.0.resize(index + 1, 0);
}
let word = unsafe { self.0.get_unchecked_mut(index) };
let was_unset = (*word & bits) == 0;
*word |= bits;
was_unset
}
pub fn remove(&mut self, value: usize) -> bool {
let (index, bits) = Self::split_value(value);
let was_set = if let Some(word) = self.0.get_mut(index) {
let was_set = (*word & bits) != 0;
*word &= !bits;
was_set
} else {
false
};
if index + 1 == self.0.len() {
while let Some(0) = self.0.last() {
self.0.pop();
}
}
was_set
}
pub fn first(&self) -> Option<usize> {
for (i, word) in self.0.iter().copied().enumerate() {
if word != 0 {
let mut value = i * 64;
let mut bit = 1;
while bit != 0 {
if word & bit != 0 {
return Some(value);
}
value += 1;
bit <<= 1;
}
}
}
None
}
pub fn find_next(&self, mut value: usize) -> Option<usize> {
value += 1;
let (mut index, mut bits) = Self::split_value(value);
while let Some(word) = self.0.get(index) {
if *word & bits != 0 {
return Some(value);
}
value += 1;
if bits > (!0 >> 1) {
index += 1;
bits = 1;
} else {
bits <<= 1;
}
}
None
}
fn ones_inside_word(start: usize, mut word: u64) -> impl Iterator<Item = usize> {
let mut i = start;
std::iter::from_fn(move || {
while word != 0 {
if word & 1 == 1 {
let result = i;
i += 1;
word >>= 1;
return Some(result);
}
i += 1;
word >>= 1;
}
None
})
}
pub fn iter(&self) -> impl Iterator<Item = usize> + '_ {
self.0
.iter()
.copied()
.enumerate()
.flat_map(|(i, word)| Self::ones_inside_word(i * 64, word))
}
}
impl Default for BitSet {
#[inline]
fn default() -> Self {
Self::new()
}
}
impl Extend<usize> for BitSet {
fn extend<I: IntoIterator<Item = usize>>(&mut self, iter: I) {
for t in iter {
self.insert(t);
}
}
}
impl<T> FromIterator<T> for BitSet
where
Self: Extend<T>,
{
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
let mut bitset = Self::new();
bitset.extend(iter);
bitset
}
}