BitMagic-C++
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
[legend]

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

Examples:
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 ( )
inline

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)
inline

Definition at line 5409 of file bm.h.

References copy_from().

Member Function Documentation

◆ copy_from()

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

copy rs index

Definition at line 5428 of file bm.h.

References total_blocks.

Referenced by rs_index().

◆ count()

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

◆ find_sub_range()

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

determine the sub-range within a bit-block

Definition at line 5447 of file bm.h.

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

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

◆ init()

void bm::rs_index::init ( )
inline

init arrays to zeros

Definition at line 5417 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
inline

determine block sub-range for rank search

Definition at line 5457 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

◆ BM_VECT_ALIGN_ATTR [1/2]

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_VECT_ALIGN_ATTR [2/2]

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: