use std::hash::Hash;
use crate::core::util::accountable::Accountable;
use crate::core::util::array_util::ArrayUtil;
use crate::core::util::error::lucene_error::{LuceneError, Result};
#[derive(Debug)]
pub struct LongBitSet {
bits: Vec<i64>, num_bits: usize, num_words: usize,
}
impl LongBitSet {
pub const MAX_NUM_BITS: usize = 64 * ArrayUtil::MAX_ARRAY_LENGTH;
pub fn ensure_capacity(bits: &mut LongBitSet, num_bits: usize) -> Result<()> {
if num_bits < bits.num_bits {
} else {
let num_words = Self::bits2words(num_bits)?;
let length = bits.bits.len();
if num_words >= length {
ArrayUtil::grow_with(&mut bits.bits, num_words + 1, || 0)?;
}
debug_assert!(bits.bits.len() <= i32::MAX as usize);
bits.num_bits = (bits.bits.len()) << 6;
bits.num_words = Self::bits2words(bits.num_bits)?;
}
Ok(())
}
pub fn bits2words(num_bits: usize) -> Result<usize> {
if !(0..=Self::MAX_NUM_BITS).contains(&num_bits) {
return Err(LuceneError::illegal_argument(format!(
"num_bits must be 0..{}; got {}",
Self::MAX_NUM_BITS,
num_bits
)));
}
if num_bits == 0 {
Ok(0)
} else {
Ok(((num_bits - 1) >> 6) + 1)
}
}
pub fn new(num_bits: usize) -> Result<Self> {
let num_words = Self::bits2words(num_bits)?;
let bits = vec![0i64; num_words];
Ok(Self::from_validated_parts(bits, num_bits, num_words))
}
pub fn from_bits<B>(stored_bits: B, num_bits: usize) -> Result<Self>
where
B: Into<Vec<i64>>,
{
let stored_bits = stored_bits.into();
let num_words = Self::bits2words(num_bits)?;
if num_words > stored_bits.len() {
return Err(LuceneError::illegal_argument(format!(
"The given long array is too small to hold {num_bits} bits"
)));
}
Ok(Self::from_validated_parts(stored_bits, num_bits, num_words))
}
fn from_validated_parts(bits: Vec<i64>, num_bits: usize, num_words: usize) -> Self {
debug_assert!(matches!(
Self::bits2words(num_bits),
Ok(expected_num_words) if expected_num_words == num_words
));
debug_assert!(num_words <= bits.len());
let bit_set = Self {
bits,
num_bits,
num_words,
};
debug_assert!(bit_set.verify_ghost_bits_clear());
bit_set
}
fn verify_ghost_bits_clear(&self) -> bool {
for i in self.num_words..self.bits.len() {
if self.bits[i] != 0 {
return false;
}
}
if (self.num_bits & 0x3f) == 0 {
return true;
}
let mask = (!0i64).wrapping_shl(self.num_bits as u32);
(self.bits[self.num_words - 1] & mask) == 0
}
pub fn length(&self) -> usize {
self.num_bits
}
pub fn get_bits(&self) -> &[i64] {
&self.bits
}
pub fn cardinality(&self) -> usize {
let words = &self.bits[..self.num_words];
if words.len() >= 8 {
words.iter().map(|v| v.count_ones() as usize).sum()
} else {
match words.len() {
0 => 0,
1 => words[0].count_ones() as usize,
_ => {
let (pairs, tail) = words.as_chunks::<2>();
pairs
.iter()
.map(|&[a, b]| ((a as u64 as u128) | ((b as u64 as u128) << 64)).count_ones() as usize)
.sum::<usize>()
+ tail.iter().map(|v| v.count_ones() as usize).sum::<usize>()
},
}
}
}
pub fn get(&self, index: usize) -> bool {
debug_assert!(
index < self.num_bits,
"index = {}, num_bits = {}",
index,
self.num_bits
);
let i = index >> 6;
let bitmask = 1i64.wrapping_shl(index as u32);
(self.bits[i] & bitmask) != 0
}
pub fn set(&mut self, index: usize) {
debug_assert!(
index < self.num_bits,
"index = {}, num_bits = {}",
index,
self.num_bits
);
let word_num = index >> 6;
let bitmask = 1i64.wrapping_shl(index as u32);
self.bits[word_num] |= bitmask;
}
pub fn get_and_set(&mut self, index: usize) -> bool {
debug_assert!(
index < self.num_bits,
"index = {}, num_bits = {}",
index,
self.num_bits
);
let word_num = index >> 6;
let bitmask = 1i64.wrapping_shl(index as u32);
let val = (self.bits[word_num] & bitmask) != 0;
self.bits[word_num] |= bitmask;
val
}
pub fn clear(&mut self, index: usize) {
debug_assert!(
index < self.num_bits,
"index = {}, num_bits = {}",
index,
self.num_bits
);
let word_num = index >> 6;
let bitmask = 1i64.wrapping_shl(index as u32);
self.bits[word_num] &= !bitmask;
}
pub fn get_and_clear(&mut self, index: usize) -> bool {
debug_assert!(
index < self.num_bits,
"index = {}, num_bits = {}",
index,
self.num_bits
);
let word_num = index >> 6;
let bitmask = 1i64.wrapping_shl(index as u32);
let val = (self.bits[word_num] & bitmask) != 0;
self.bits[word_num] &= !bitmask;
val
}
pub fn next_set_bit(&self, index: usize) -> Option<usize> {
debug_assert!(
index < self.num_bits,
"index = {}, num_bits = {}",
index,
self.num_bits
);
let mut i = index >> 6;
let sub_index = index & 63;
let mut word = self.bits[i] >> sub_index;
if word != 0 {
return Some(index + word.trailing_zeros() as usize);
}
i += 1;
while i < self.num_words {
word = self.bits[i];
if word != 0 {
return Some(i << 6 | word.trailing_zeros() as usize);
}
i += 1;
}
None
}
pub fn prev_set_bit(&self, index: usize) -> Option<usize> {
debug_assert!(
index < self.num_bits,
"index = {}, num_bits = {}",
index,
self.num_bits
);
let i = index >> 6;
let sub_index = index & 0x3f;
let word = self.bits[i] << (63 - sub_index);
if word != 0 {
return Some((i << 6) + sub_index - word.leading_zeros() as usize);
}
let mut v = i.checked_sub(1);
while let Some(i) = v {
let word = self.bits[i];
if word != 0 {
return Some((i << 6) + 63 - word.leading_zeros() as usize);
}
v = i.checked_sub(1);
}
None
}
pub fn or(&mut self, other: &LongBitSet) {
debug_assert!(
other.num_words <= self.num_words,
"num_words = {}, other.num_words = {}",
self.num_words,
other.num_words
);
let pos = std::cmp::min(self.num_words, other.num_words);
for i in 0..pos {
self.bits[i] |= other.bits[i];
}
}
pub fn xor(&mut self, other: &LongBitSet) {
debug_assert!(
other.num_words <= self.num_words,
"num_words = {}, other.num_words = {}",
self.num_words,
other.num_words
);
let pos = std::cmp::min(self.num_words, other.num_words);
for i in 0..pos {
self.bits[i] ^= other.bits[i];
}
}
pub fn intersects(&self, other: &LongBitSet) -> bool {
let pos = std::cmp::min(self.num_words, other.num_words);
if pos == 0 {
return false;
}
if (self.bits[0] & other.bits[0]) != 0 {
return true;
}
if pos == 1 {
return false;
}
if (self.bits[pos - 1] & other.bits[pos - 1]) != 0 {
return true;
}
for i in 1..pos - 1 {
if (self.bits[i] & other.bits[i]) != 0 {
return true;
}
}
false
}
pub fn and(&mut self, other: &LongBitSet) {
let pos = std::cmp::min(self.num_words, other.num_words);
for i in 0..pos {
self.bits[i] &= other.bits[i];
}
if self.num_words > other.num_words {
for i in other.num_words..self.num_words {
self.bits[i] = 0;
}
}
}
pub fn and_not(&mut self, other: &LongBitSet) {
let pos = std::cmp::min(self.num_words, other.num_words);
for i in 0..pos {
self.bits[i] &= !other.bits[i];
}
}
pub fn scan_is_empty(&self) -> bool {
let mut num_words = self.num_words;
if num_words > self.bits.len() {
num_words = self.bits.len();
}
let mut i = 0;
while i < num_words {
if self.bits[i] != 0 {
return false;
}
i += 1;
if i + 5 <= num_words {
if (self.bits[i]
| self.bits[i + 1]
| self.bits[i + 2]
| self.bits[i + 3]
| self.bits[i + 4])
!= 0
{
return false;
}
i += 5;
}
}
true
}
pub fn flip(&mut self, start_index: usize, end_index: usize) {
debug_assert!(
start_index < self.num_bits,
"start_index = {}, num_bits = {}",
start_index,
self.num_bits
);
debug_assert!(
end_index <= self.num_bits,
"end_index = {}, num_bits = {}",
end_index,
self.num_bits
);
if end_index <= start_index {
return;
}
let start_word = start_index >> 6;
let end_word = (end_index - 1) >> 6;
let start_mask = -1_i64 << (start_index % 64);
let shift = 0usize.wrapping_sub(end_index) & 63;
let end_mask = (u64::MAX >> shift) as i64;
if start_word == end_word {
self.bits[start_word] ^= start_mask & end_mask;
return;
}
self.bits[start_word] ^= start_mask;
for i in (start_word + 1)..end_word {
self.bits[i] = !self.bits[i];
}
self.bits[end_word] ^= end_mask;
}
pub fn flip_one(&mut self, index: usize) {
debug_assert!(
index < self.num_bits,
"index = {}, num_bits = {}",
index,
self.num_bits
);
let word_num = index >> 6;
let bitmask = 1i64.wrapping_shl(index as u32); self.bits[word_num] ^= bitmask;
}
pub fn set_range(&mut self, start_index: usize, end_index: usize) {
debug_assert!(
start_index < self.num_bits,
"start_index = {}, num_bits = {}",
start_index,
self.num_bits
);
debug_assert!(
end_index <= self.num_bits,
"end_index = {}, num_bits = {}",
end_index,
self.num_bits
);
if end_index <= start_index {
return;
}
let start_word = start_index >> 6;
let end_word = (end_index - 1) >> 6;
let start_mask = -1_i64 << (start_index % 64);
let shift = 0usize.wrapping_sub(end_index) & 63;
let end_mask = (u64::MAX >> shift) as i64;
if start_word == end_word {
self.bits[start_word] |= start_mask & end_mask;
return;
}
self.bits[start_word] |= start_mask;
for i in (start_word + 1)..end_word {
self.bits[i] = -1;
}
self.bits[end_word] |= end_mask;
}
pub fn clear_range(&mut self, start_index: usize, end_index: usize) {
debug_assert!(
start_index < self.num_bits,
"start_index = {}, num_bits = {}",
start_index,
self.num_bits
);
debug_assert!(
end_index <= self.num_bits,
"end_index = {}, num_bits = {}",
end_index,
self.num_bits
);
if end_index <= start_index {
return;
}
let start_word = start_index >> 6;
let end_word = (end_index - 1) >> 6;
let mut start_mask = -1_i64 << (start_index % 64);
let shift = 0usize.wrapping_sub(end_index) & 63;
let mut end_mask = (u64::MAX >> shift) as i64;
start_mask = !start_mask;
end_mask = !end_mask;
if start_word == end_word {
self.bits[start_word] &= start_mask | end_mask;
return;
}
self.bits[start_word] &= start_mask;
for i in (start_word + 1)..end_word {
self.bits[i] = 0;
}
self.bits[end_word] &= end_mask;
}
}
impl Accountable for LongBitSet {
fn ram_bytes_used(&self) -> Result<i64> {
Ok(crate::core::util::ram_usage_estimator::size_of_vec(
&self.bits,
))
}
}
impl Clone for LongBitSet {
fn clone(&self) -> Self {
Self::from_validated_parts(self.bits.clone(), self.num_bits, self.num_words)
}
}
impl PartialEq for LongBitSet {
fn eq(&self, other: &Self) -> bool {
if self.num_bits != other.num_bits {
return false;
}
self.bits == other.bits
}
}
impl Eq for LongBitSet {}
impl Hash for LongBitSet {
fn hash<H>(&self, state: &mut H)
where
H: std::hash::Hasher,
{
self.bits.hash(state);
self.num_bits.hash(state);
}
}