Public Member Functions | Data Fields
bm::rs_index Struct Reference

Rank-Select acceleration index. More...

#include <bm.h>

Collaboration diagram for bm::rs_index:
Collaboration graph

Public Member Functions

 rs_index ()
 rs_index (const rs_index &rsi) BMNOEXEPT
void init () BMNOEXEPT
 init arrays to zeros More...
void copy_from (const rs_index &rsi) BMNOEXEPT
 copy rs index More...
unsigned count (unsigned nb) const
 return bit-count for specified block More...
unsigned find_sub_range (unsigned block_bit_pos) const
 determine the sub-range within a bit-block More...
bm::gap_word_t select_sub_range (unsigned nb, unsigned &rank) const
 determine block sub-range for rank search More...

Data Fields

unsigned bcount [bm::set_total_blocks]
bm::pair< bm::gap_word_t, bm::gap_word_tsubcount [bm::set_total_blocks]
unsigned total_blocks

Detailed Description

Rank-Select acceleration index.

Index uses two-level acceleration structure: bcount - running total popcount for all (possible) blocks (missing blocks give duplicate counts as POPCNT(N-1) + 0). subcount - sub-count inside blocks

sample11.cpp, and sample17.cpp.

Definition at line 101 of file bm.h.

Constructor & Destructor Documentation

◆ rs_index() [1/2]

bm::rs_index::rs_index ( )

Definition at line 107 of file bm.h.

References BMNOEXEPT, copy_from(), count(), find_sub_range(), init(), and select_sub_range().

◆ rs_index() [2/2]

bm::rs_index::rs_index ( const rs_index rsi)

Definition at line 6195 of file bm.h.

References copy_from().

Member Function Documentation

◆ copy_from()

void bm::rs_index::copy_from ( const rs_index rsi)

◆ count()

unsigned bm::rs_index::count ( unsigned  nb) const

return bit-count for specified block

Definition at line 6224 of file bm.h.

References bcount.

Referenced by bm::bvector<>::count_blocks(), bm::bvector<>::find_rank(), bm::bvector<>::recalc_count(), rs_index(), bm::bvector<>::select(), and bm::bvector<>::size().

◆ find_sub_range()

unsigned bm::rs_index::find_sub_range ( unsigned  block_bit_pos) const

determine the sub-range within a bit-block

Definition at line 6233 of file bm.h.

References bm::rs3_border0, and bm::rs3_border1.

Referenced by bm::bvector<>::count_blocks(), and rs_index().

◆ init()

void bm::rs_index::init ( )

init arrays to zeros

Definition at line 6203 of file bm.h.

References bcount, subcount, and total_blocks.

Referenced by bm::bvector<>::bvector(), rs_index(), bm::bvector<>::running_count_blocks(), and bm::bvector<>::~bvector().

◆ select_sub_range()

bm::gap_word_t bm::rs_index::select_sub_range ( unsigned  nb,
unsigned &  rank 
) const

determine block sub-range for rank search

Definition at line 6243 of file bm.h.

References bm::pair< First, Second >::first, bm::rs3_border0, bm::rs3_border1, bm::pair< First, Second >::second, and subcount.

Referenced by bm::bvector<>::find_rank(), rs_index(), and bm::bvector<>::select().

Field Documentation

◆ bcount

unsigned bm::rs_index::bcount[bm::set_total_blocks]

◆ subcount

◆ total_blocks

unsigned bm::rs_index::total_blocks

The documentation for this struct was generated from the following file: