Class RankSupportBitString
A bit string supporting rank queries in constant time.

Defined in <seqan/index.h>
Signature template <typename TSpec> class RankSupportBitString;

Template Parameters

TSpec Specialisation tag. Default: void

Interface Function Overview

Detailed Description

The constant rank query time is achieved by evaluating precomputed subsolutions. In order to do so, the bit string is divided into blocks of length l. A super block string stores for each block of l blocks the number of bits set from the beginning. In addition a block string stores the number of bits set in each block from the start of the last super block block. Therefore it is possible to compute the result of a rank query in constant time by adding information from the bit, block and super block string.

Interface Functions Detail

appendValue(bitString, bit)

Appends a bit to a RankSupportBitString.

Parameters

target A container. Types: RankSupportBitString
bit Value that is appended to target.If the value is different from 0 it is interpreted as 1. Types: UnsignedIntegerConcept, bool

clear(bitString)

Resets an rank-support-bit string.

Parameters

bitString The bit string to be cleared.

bool empty(bitString)

Checks whether or not a rank-support-bit string contains any elements.

Parameters

bitString The rank-support-bit string to be checked.

Returns

bool Returns true if the rank-support-bit string is empty and false otherwise.

getFibre(bitString, fibreTag)

Returns a specific fibre of a rank-support-bit string.

Parameters

fibreTag A tag that identifies the Fibre. Types: RankSupportBitString Fibres.
bitString The rank-support-bit string holding the fibre.

Returns

TReturn A reference to the Fibre object.

getRank(bitString, pos)

Returns the rank (the number of bits set from the start of the bit string) of a specified position.

Parameters

bitString The bit string. Types: RankSupportBitString
pos Position of a bit.

Returns

TReturn Value of Fibre of the rank-support-bit string.

isSetBit(bitString, pos)

Returns whether the bit with the given index is set to 1.

Parameters

bitString The bit string.
pos Position of the bit. Types: UnsignedIntegerConcept

Returns

TReturn Returns whether a specified bit is set or not.

length(bitString)

Returns the number of bits in the rank-support-bit string.

Parameters

bitString The rank-support-bit string.

Returns

TReturn Types: Value of Fibre of the rank-support-bit string.

open(bitString, fileName [, openMode])

This functions opens a RankSupportBitString from disk.

Parameters

openMode The combination of flags defining how the file should be opened.To open a file read-only, write-only or to read and write use OPEN_RDONLY, OPEN_WRONLY, or OPEN_RDWR.To create or overwrite a file add OPEN_CREATE.To append a file if existing add OPEN_APPEND.To circumvent problems, files are always opened in binary mode. Default: OPEN_RDWR | OPEN_CREATE | OPEN_APPEND
bitString The bit string to be opened.
fileName C-style character string containing the file name.

Returns

TReturn A bool which is true on success.

TSize resize(bitString, newLenght)

Resets the number of bits in the rank-support-bit string.

Parameters

bitString The rank-support-bit string.
newLength The number of elements which should be stored in the compressed suffix array. Types: UnsignedIntegerConcept.

Returns

TSize The number of elements in the rank-support-bit string. Types: The result of Size of the rank-support-bit string.

Note If the new length is smaller than the actual one then the last x items of the rank-support-bit string are deleted with x = oldLength - newLength.

save(bitString, fileName [, openMode])

This functions saves a RankSupportBitString to disk.

Parameters

openMode The combination of flags defining how the file should be opened.To open a file read-only, write-only or to read and write use OPEN_RDONLY, OPEN_WRONLY, or OPEN_RDWR.To create or overwrite a file add OPEN_CREATE.To append a file if existing add OPEN_APPEND.To circumvent problems, files are always opened in binary mode. Default: OPEN_RDWR | OPEN_CREATE | OPEN_APPEND
bitString The bit string to be saved.
fileName C-style character string containing the file name.

Returns

TReturn A bool which is true on success.

setBitTo(bitString, pos, value)

Set the bit with the given position to the given value.

Parameters

pos Position of the bit. Types: UnsignedIntegerConcept
bitString The bit string.
bit The value of the bit. Note that values different from 0 are interpreted as 1.

Returns

TReturn void

Examples

See Also