use std::cmp;
use std::ops::Deref;
use bv::BitVec;
use bv::Bits;
#[derive(Serialize, Deserialize)]
pub struct RankSelect {
n: usize,
bits: BitVec<u8>,
superblocks_1: Vec<SuperblockRank>,
superblocks_0: Vec<SuperblockRank>,
s: usize,
k: usize,
}
impl RankSelect {
pub fn new(bits: BitVec<u8>, k: usize) -> RankSelect {
let n = bits.len() as usize;
let s = k * 32;
RankSelect {
n,
s,
k,
superblocks_1: superblocks(true, n, s, &bits),
superblocks_0: superblocks(false, n, s, &bits),
bits,
}
}
pub fn k(&self) -> usize {
self.k
}
pub fn bits(&self) -> &BitVec<u8> {
&self.bits
}
pub fn get(&self, i: u64) -> bool {
self.bits.get_bit(i)
}
pub fn rank_1(&self, i: u64) -> Option<u64> {
if i >= self.n as u64 {
None
} else {
let s = i / self.s as u64;
let b = i / 8;
let j = i % 8;
let mut rank = *self.superblocks_1[s as usize];
let mask = ((2u16 << j) - 1) as u8;
rank += (self.bits.get_block(b as usize) & mask).count_ones() as u64;
for block in (s * self.s as u64 / 8)..b {
let b = self.bits.get_block(block as usize);
rank += b.count_ones() as u64;
}
Some(rank)
}
}
pub fn rank_0(&self, i: u64) -> Option<u64> {
self.rank_1(i).map(|r| (i + 1) - r)
}
pub fn rank(&self, i: u64) -> Option<u64> {
self.rank_1(i)
}
pub fn select_1(&self, j: u64) -> Option<u64> {
self.select_x(
j,
&self.superblocks_1,
|bit| bit != 0,
|block| block.count_ones(),
)
}
pub fn select_0(&self, j: u64) -> Option<u64> {
self.select_x(
j,
&self.superblocks_0,
|bit| bit == 0,
|block| block.count_zeros(),
)
}
fn select_x<F: Fn(u8) -> bool, C: Fn(u8) -> u32>(
&self,
j: u64,
superblocks: &[SuperblockRank],
is_match: F,
count_all: C,
) -> Option<u64> {
if j == 0 {
return None;
}
let mut superblock = match superblocks.binary_search(&SuperblockRank::First(j)) {
Ok(i) | Err(i) => i,
};
if superblock > 0 {
superblock -= 1;
}
let mut rank = *superblocks[superblock];
let first_block = superblock * self.s / 8;
for block in first_block..cmp::min(first_block + self.s / 8, self.bits.block_len()) {
let b = self.bits.get_block(block);
let p = count_all(b) as u64;
if rank + p >= j {
let mut bit = 0b1;
let max_bit = cmp::min(8, self.bits.len() - block as u64 * 8);
for i in 0..max_bit {
rank += is_match(b & bit) as u64;
if rank == j {
return Some(block as u64 * 8 + i);
}
bit <<= 1;
}
}
rank += p;
}
None
}
pub fn select(&self, j: u64) -> Option<u64> {
self.select_1(j)
}
}
#[derive(Deserialize, Serialize, Clone, Debug, PartialEq, Eq, PartialOrd)]
pub enum SuperblockRank {
First(u64),
Some(u64),
}
impl Deref for SuperblockRank {
type Target = u64;
fn deref(&self) -> &u64 {
match self {
SuperblockRank::First(rank) => rank,
SuperblockRank::Some(rank) => rank,
}
}
}
impl Ord for SuperblockRank {
fn cmp(&self, other: &Self) -> cmp::Ordering {
let cmp = (**self).cmp(&**other);
if cmp == cmp::Ordering::Equal {
match (self, other) {
(SuperblockRank::First(_), SuperblockRank::Some(_)) => cmp::Ordering::Less,
(SuperblockRank::Some(_), SuperblockRank::First(_)) => cmp::Ordering::Greater,
_ => cmp,
}
} else {
cmp
}
}
}
fn superblocks(t: bool, n: usize, s: usize, bits: &BitVec<u8>) -> Vec<SuperblockRank> {
let mut superblocks = Vec::with_capacity(n / s + 1);
let mut rank: u64 = 0;
let mut last_rank = None;
let mut i = 0;
let nblocks = (bits.len() as f64 / 8.0).ceil() as usize;
for block in 0..nblocks {
let b = bits.get_block(block);
if i % s == 0 {
superblocks.push(if Some(rank) != last_rank {
SuperblockRank::First(rank)
} else {
SuperblockRank::Some(rank)
});
last_rank = Some(rank);
}
rank += if t {
b.count_ones() as u64
} else {
b.count_zeros() as u64
};
i += 8;
}
superblocks
}
#[cfg(test)]
mod tests {
use super::*;
use bv::bit_vec;
use bv::BitVec;
use bv::BitsMut;
#[test]
fn test_select_start() {
let mut bits: BitVec<u8> = BitVec::new_fill(false, 900);
bits.set_bit(64, true);
let rs = RankSelect::new(bits, 1);
assert_eq!(rs.select_1(1), Some(64));
}
#[test]
fn test_select_end() {
let mut bits: BitVec<u8> = BitVec::new_fill(false, 900);
bits.set_bit(50, true);
let rs = RankSelect::new(bits, 1);
assert_eq!(rs.select_1(1).unwrap(), 50);
}
#[test]
fn test_rank_select() {
let mut bits: BitVec<u8> = BitVec::new_fill(false, 64);
bits.set_bit(5, true);
bits.set_bit(32, true);
let rs = RankSelect::new(bits, 1);
assert_eq!(rs.rank_1(1).unwrap(), 0);
assert_eq!(rs.rank_1(5).unwrap(), 1);
assert_eq!(rs.rank_1(6).unwrap(), 1);
assert_eq!(rs.rank_1(7).unwrap(), 1);
assert_eq!(rs.rank_1(32).unwrap(), 2);
assert_eq!(rs.rank_1(33).unwrap(), 2);
assert_eq!(rs.rank_1(64), None);
assert_eq!(rs.select_1(0), None);
assert_eq!(rs.select_1(1).unwrap(), 5);
assert_eq!(rs.select_1(2).unwrap(), 32);
assert_eq!(rs.rank_0(1).unwrap(), 2);
assert_eq!(rs.rank_0(4).unwrap(), 5);
assert_eq!(rs.rank_0(5).unwrap(), 5);
assert_eq!(rs.select_0(0), None);
assert_eq!(rs.select_0(1).unwrap(), 0);
assert_eq!(rs.get(5), true);
assert_eq!(rs.get(1), false);
assert_eq!(rs.get(32), true);
}
#[test]
fn test_rank_select2() {
let mut bits: BitVec<u8> = BitVec::new_fill(false, 64);
bits.set_bit(5, true);
bits.set_bit(32, true);
let rs = RankSelect::new(bits, 1);
assert_eq!(rs.select_1(2).unwrap(), 32);
}
#[test]
fn test_select() {
let bits: BitVec<u8> = bit_vec![true, false];
let rs = RankSelect::new(bits, 1);
assert_eq!(rs.select_0(0), None);
assert_eq!(rs.select_1(0), None);
assert_eq!(rs.select_0(1), Some(1));
assert_eq!(rs.select_1(1), Some(0));
assert_eq!(rs.select_0(2), None);
assert_eq!(rs.select_1(2), None);
}
#[test]
fn test_single_select() {
let bits: BitVec<u8> = bit_vec![true];
let rs = RankSelect::new(bits, 1);
assert_eq!(rs.select_1(0), None);
assert_eq!(rs.select_1(1), Some(0));
assert_eq!(rs.select_0(0), None);
assert_eq!(rs.select_0(1), None);
let bits: BitVec<u8> = bit_vec![false];
let rs = RankSelect::new(bits, 1);
assert_eq!(rs.select_1(1), None);
assert_eq!(rs.select_1(0), None);
assert_eq!(rs.select_0(0), None);
assert_eq!(rs.select_0(1), Some(0));
assert_eq!(rs.rank_0(0), Some(1));
assert_eq!(rs.rank_1(0), Some(0));
}
#[test]
fn test_rank_k() {
let mut bits: BitVec<u8> = BitVec::new_fill(false, 72);
bits.set_bit(63, true);
let rs = RankSelect::new(bits, 2);
assert_eq!(rs.rank_1(63), Some(1));
assert_eq!(rs.rank_1(64), Some(1));
assert_eq!(rs.rank_1(71), Some(1));
}
}