bm::rs_index Struct Reference

Rank-Select acceleration index. More...

#include <bm.h>

Collaboration diagram for bm::rs_index:

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_t >	subcount [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

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 6195 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 6214 of file bm.h.

References bcount, subcount, and total_blocks.

Referenced by bm::bvps_addr_resolver< bvector_type >::operator=(), rs_index(), and bm::rsc_sparse_vector< Val, SV >::rsc_sparse_vector().

count()

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

inline

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

inline

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

inline

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

inline

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]

Definition at line 103 of file bm.h.

Referenced by copy_from(), count(), bm::bvector<>::count_blocks(), bm::bvector<>::count_to(), bm::bvector<>::count_to_test(), bm::bvector<>::find_rank(), init(), bm::bvector<>::running_count_blocks(), and bm::bvector<>::select().

subcount

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

Definition at line 104 of file bm.h.

Referenced by copy_from(), bm::bvector<>::count_blocks(), init(), bm::bvector<>::running_count_blocks(), and select_sub_range().

total_blocks

unsigned bm::rs_index::total_blocks

Definition at line 105 of file bm.h.

Referenced by copy_from(), bm::bvector<>::find_rank(), init(), bm::bvector<>::running_count_blocks(), and bm::bvector<>::select().

---

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

• bm.h