tdc::Rank Class Reference

Implements a rank data structure for a BitVector. More...

#include <Rank.hpp>

Public Member Functions
	Rank ()
	Default constructor. More...
	Rank (const Rank &other)
	Copy constructor. More...
	Rank (Rank &&other)
	Move constructor. More...
Rank &	operator= (const Rank &other)
	Copy assignment. More...
Rank &	operator= (Rank &&other)
	Move assignment. More...
	Rank (const BitVector &bv)
	Constructs the rank data structure for the given bit vector. More...
size_t	rank1 (size_t x) const
	Counts the amount of 1-bits from the beginning of the bit vector up to (including) the given position. More...
size_t	rank1 (size_t x, size_t y) const
	Counts the amount of 1-bits in the given interval (borders included) of the bit vector. More...
size_t	operator() (size_t x) const
size_t	operator() (size_t x, size_t y) const
size_t	rank0 (size_t x) const
	Counts the amount of 0-bits from the beginning of the bit vector up to (including) the given position. More...
size_t	rank0 (size_t x, size_t y) const
	Counts the amount of 0-bits in the given interval (borders included) of the bit vector. More...

Static Public Attributes
static constexpr size_t	block_size
	The size of a block in bits. More...

Detailed Description

Implements a rank data structure for a BitVector.

The data structure follows a block / superblock principle. Blocks are always of fixed size (e.g. 64 bits), the size of a superblock is the squared block size.

The structure supports both rank1 and rank0 queries.

Definition at line 16 of file Rank.hpp.

Constructor & Destructor Documentation

Rank() [1/4]

tdc::Rank::Rank ( )

inline

Default constructor.

Definition at line 33 of file Rank.hpp.

Rank() [2/4]

tdc::Rank::Rank ( const Rank &  other )

inline

Copy constructor.

Definition at line 39 of file Rank.hpp.

Rank() [3/4]

tdc::Rank::Rank ( Rank &&  other )

inline

Move constructor.

Definition at line 47 of file Rank.hpp.

Rank() [4/4]

tdc::Rank::Rank ( const BitVector &  bv )

inline

Constructs the rank data structure for the given bit vector.

Note that changes to the bit vector after construction of this data structure will cause the rank operations to not work correctly anymore. In other words, this data structure is static.

Parameters

bv	the underlying bit vector

Definition at line 79 of file Rank.hpp.

Member Function Documentation

operator()() [1/2]

size_t tdc::Rank::operator() ( size_t  x ) const

inline

See also

rank1

Definition at line 153 of file Rank.hpp.

operator()() [2/2]

size_t tdc::Rank::operator() ( size_t  x, size_t  y  ) const

inline

See also

rank1

Definition at line 158 of file Rank.hpp.

operator=() [1/2]

Rank& tdc::Rank::operator= ( const Rank &  other )

inline

Copy assignment.

Definition at line 55 of file Rank.hpp.

operator=() [2/2]

Rank& tdc::Rank::operator= ( Rank &&  other )

inline

Move assignment.

Definition at line 64 of file Rank.hpp.

rank0() [1/2]

size_t tdc::Rank::rank0 ( size_t  x ) const

inline

Counts the amount of 0-bits from the beginning of the bit vector up to (including) the given position.

Parameters

x	the position up to which to count (inclusively)

Returns

the amount of counted 0-bits

Definition at line 166 of file Rank.hpp.

rank0() [2/2]

size_t tdc::Rank::rank0 ( size_t  x, size_t  y  ) const

inline

Counts the amount of 0-bits in the given interval (borders included) of the bit vector.

Parameters

x	the position from which to start counting (inclusively)
y	the position at which to stop counting (inclusively)

Returns

the amount of counted 0-bits

Definition at line 175 of file Rank.hpp.

rank1() [1/2]

size_t tdc::Rank::rank1 ( size_t  x ) const

inline

Counts the amount of 1-bits from the beginning of the bit vector up to (including) the given position.

Parameters

x	the position up to which to count (inclusively)

Returns

the amount of counted 1-bits

Definition at line 126 of file Rank.hpp.

rank1() [2/2]

size_t tdc::Rank::rank1 ( size_t  x, size_t  y  ) const

inline

Counts the amount of 1-bits in the given interval (borders included) of the bit vector.

Parameters

x	the position from which to start counting (inclusively)
y	the position at which to stop counting (inclusively)

Returns

the amount of counted 1-bits

Definition at line 145 of file Rank.hpp.

Member Data Documentation

block_size

constexpr size_t tdc::Rank::block_size

static

Initial value:

=
        8 * sizeof(BitVector::internal_data_type)

The size of a block in bits.

Definition at line 19 of file Rank.hpp.

---

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

• Rank.hpp