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 BM_VECT_ALIGN bcount [bm::set_total_blocksBM_VECT_ALIGN_ATTR
bm::pair< bm::gap_word_t, bm::gap_word_t > BM_VECT_ALIGN subcount [bm::set_total_blocksBM_VECT_ALIGN_ATTR
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 6186 of file bm.h.

References copy_from().

Member Function Documentation

◆ copy_from()

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

copy rs index

Definition at line 6205 of file bm.h.

References total_blocks.

Referenced by rs_index().

◆ count()

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

return bit-count for specified block

Definition at line 6215 of file bm.h.

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 6224 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 6194 of file bm.h.

References 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 6234 of file bm.h.

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

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

Field Documentation


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

Definition at line 103 of file bm.h.


bm::pair<bm::gap_word_t, bm::gap_word_t> BM_VECT_ALIGN subcount [bm::set_total_blocks] bm::rs_index::BM_VECT_ALIGN_ATTR

Definition at line 104 of file bm.h.

◆ total_blocks

unsigned bm::rs_index::total_blocks

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