tudocomp
– The TU Dortmund Compression Framework
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...
 
Rankoperator= (const Rank &other)
 Copy assignment. More...
 
Rankoperator= (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

tdc::Rank::Rank ( )
inline

Default constructor.

Definition at line 33 of file Rank.hpp.

tdc::Rank::Rank ( const Rank other)
inline

Copy constructor.

Definition at line 39 of file Rank.hpp.

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

Move constructor.

Definition at line 47 of file Rank.hpp.

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
bvthe underlying bit vector

Definition at line 79 of file Rank.hpp.

Member Function Documentation

size_t tdc::Rank::operator() ( size_t  x) const
inline
See also
rank1

Definition at line 153 of file Rank.hpp.

size_t tdc::Rank::operator() ( size_t  x,
size_t  y 
) const
inline
See also
rank1

Definition at line 158 of file Rank.hpp.

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

Copy assignment.

Definition at line 55 of file Rank.hpp.

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

Move assignment.

Definition at line 64 of file Rank.hpp.

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
xthe position up to which to count (inclusively)
Returns
the amount of counted 0-bits

Definition at line 166 of file Rank.hpp.

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
xthe position from which to start counting (inclusively)
ythe position at which to stop counting (inclusively)
Returns
the amount of counted 0-bits

Definition at line 175 of file Rank.hpp.

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
xthe position up to which to count (inclusively)
Returns
the amount of counted 1-bits

Definition at line 126 of file Rank.hpp.

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
xthe position from which to start counting (inclusively)
ythe 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

constexpr size_t tdc::Rank::block_size
static
Initial value:

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: