Contains the text compression and encoding framework. More...

Namespaces
	bwt
	Contains functionality for computing and decoding the Burrows-Wheeler transform (BWT) of a text.

	ds
	Contains general structures and constants concerning the available data structure implementations.

	esp

	int_vector
	Contains the IntVector class and its backing utilities.

	io
	Contains I/O abstractions and utilities.

	json
	Contains a basic JSON builder implementation.

	lcpcomp
	Contains factorization and decoding strategies for the LCPCompressor.

	lfs

	lz78
	Contains compressors and encoders that work with Lempel-Ziv-78-like dictionaries.

	lz78u

	lzss
	Contains compressors and encoders that work with Lempel-Ziv-Storer-Szymansky-like factors.

	lzw
	Contains compressors and encoders that work with Lempel-Ziv-Welch-like dictionaries.

	test
	Contains helpers for the unit tests.

Classes
struct	_DoubleHashingProber

struct	_VignaHasher

class	Algorithm
	Interface for algorithms. More...

class	AlgorithmValue

class	ArithmeticCoder
	Defines data encoding to and decoding from a stream of ASCII characters. More...

class	ArrayDS
	Base for data structures that use an integer array as a storage. More...

class	ArrayMaxHeap
	Represents a binary max heap backed by an external array of keys. More...

class	ASCIICoder
	Defines data encoding to and decoding from a stream of ASCII characters. More...

class	BinarySuffixTree

class	BitCoder
	Defines data encoding to and decoding from a stream of binary integer representations. More...

class	Bucket

class	BucketElem

class	Builder

class	BWTCompressor

class	ChainCompressor

class	compact_hash

class	CompressedLCP
	Constructs the LCP array from the Suffix and PLCP arrays, storing it in a manner as described by Fischer (WeeLCP, 2010). More...

class	Compressor
	Base for data compressors. More...

class	ConstGenericView
	A const view into a slice of memory. More...

class	ConstGenericView< uliteral_t >
	A const view into a slice of memory. More...

class	ConstIntegerBaseCombiner

class	ConstIntegerBaseCombiner< T >

class	ConstIntegerBaseCombiner< T, Ts... >

struct	ConstIntegerBaseTrait

struct	ConstIntegerBaseTrait< bool >

class	ConstIntegerBaseWith32

class	ConstIntegerBaseWith64

class	ConstIntegerBaseWithSelf

class	Counter
	A data structure for counting occurences of values of a given type T. More...

class	Decoder
	Base for data decoders. More...

class	DoubleHashingProber

class	dynamic_t
	This exists to support the `GenericIntVector<dynamic_t>` specialization. More...

class	EliasDeltaCoder
	Defines data encoding to and decoding from a stream of Elias-Delta codes. More...

class	EliasGammaCoder
	Defines data encoding to and decoding from a stream of Elias-Gamma codes. More...

struct	enable_if<(N<=32)>::type >

struct	enable_if<(N<=32)>::type >

class	Encoder
	Base for data encoders. More...

class	Env
	Local environment for a compression/encoding/decompression call. More...

class	EnvRoot

class	EspCompressor

class	FibonacciGenerator
	Generates the n-th Fibonacci word. More...

class	FixedRange
	Represents a compiler-level fixed range. More...

struct	GaussProber

class	Generator
	Base for string generators. More...

class	GenericView
	A view into a slice of memory. More...

class	GenericViewBase

class	HashMap

class	HuffmanCoder

class	IntegerBaseCombiner

class	IntegerBaseCombiner< T >

class	IntegerBaseCombiner< T, Ts... >

struct	IntegerBaseTrait

struct	IntegerBaseTrait< bool >

class	IntegerBaseWith32

class	IntegerBaseWith64

class	IntegerBaseWithSelf

class	ISAFromSA
	Constructs the inverse suffix array using the suffix array. More...

class	KarpRabinHash
	This is a randomized version of the Karp-Rabin hash function. More...

struct	KnuthHasher

class	LCPCompressor
	Factorizes the input by finding redundant phrases in a re-ordered version of the LCP table. More...

class	LCPForwardIterator

class	LCPFromPLCP
	Constructs the LCP array using the Phi algorithm. More...

class	LCPSada

class	LengthRange
	Represents the range of valid tdc::len_t values. More...

struct	LinearProber

struct	Literal
	Contains a literal and its location in the input. More...

class	LiteralEncoder

class	LiteralIterator

class	LiteralRange
	Represents the range of valid tdc::uliteral_t values. More...

class	LZ78Compressor

class	LZ78UCompressor

class	LZSSLCPCompressor
	Computes the LZ77 factorization of the input using its suffix array and LCP table. More...

class	LZSSSlidingWindowCompressor
	Computes the LZ77 factorization of the input by moving a sliding window over it in which redundant phrases will be looked for. More...

class	LZWCompressor

class	Meta
	Provides meta information about an Algorithm. More...

class	MinDistributedRange
	Represents a range of positive integers that tend to be distributed towards the minimum. More...

struct	MixHasher

class	MoveGuard

struct	msbf
	Yields the position of the most significant bit for the template integer type. More...

struct	msbf< uint16_t >
	Specialization of msbf for 16-bit unsigned integers. More...

struct	msbf< uint32_t >
	Specialization of msbf for 32-bit unsigned integers. More...

struct	msbf< uint64_t >
	Specialization of msbf for 64-bit unsigned integers. More...

struct	msbf< uint8_t >
	Specialization of msbf for 8-bit unsigned integers. More...

class	MTFCompressor

class	NaivST

class	NoLiterals
	An empty literal iterator that yields no literals whatsoever. More...

class	NoopCompressor

struct	NoopHasher

class	OptionValue

class	PhiFromSA
	Constructs the Phi array using the suffix array. More...

class	PLCPFromPhi
	Constructs the PLCP array using the phi array. More...

struct	QuadraticProber

class	RandomUniformGenerator
	Generates a random string of uniformly distributed characters. More...

class	Range
	Represents a generic range of positive integers. More...

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

class	Registry
	A registry for algorithms to be made available in the driver application. More...

class	RePairCompressor

class	RunLengthEncoder

class	RunRichGenerator
	Generates strings according to A Series of Run-Rich Strings (Wataru Matsubara et al.) More...

class	SADivSufSort
	Constructs the suffix array using divsufsort. More...

class	Select
	Implements a select data structure for a BitVector. More...

class	SizeManager

struct	SizeManagerDirect

struct	SizeManagerNoob

struct	SizeManagerPow2

struct	SizeManagerPrime

class	SLECoder

class	SparseISA
	Constructs the inverse suffix array using the suffix array. More...

class	StatPhase
	Provides access to runtime and memory measurement in statistics phases. More...

class	SuffixTree

class	TernaryCoder

class	TextDS
	Manages text related data structures. More...

class	ThueMorseGenerator
	Generates the n-th Thue Morse word. More...

class	TypeRange
	Represents a range of valid values for a certain type. More...

struct	uint_dispatch_t

struct	uint_dispatch_t< 1 >

class	uint_impl_t
	Custom integer type for storing values of arbitrary bit size `bits`. More...

class	uint_impl_t< 1 >

struct	UinttDispatch

class	ViewLiterals
	A literal iterator that yields every character from a View. More...

struct	VignaHasher

class	WordpackRollingHash

class	ZBackupRollingHash

Typedefs
template<typename actual_type >
using	fast_t = typename FastIntType< actual_type >::Type
	Type to represent integer values in the size range of `actual_type` that may require more Bits than it, while being faster. More...

using	len_compact_t = uint32_t
	Type to represent an bit-compact length value. More...

using	len_t = fast_t< len_compact_t >
	Type to represent an length value. More...

typedef uint8_t	uliteral_t
	Type to represent signed single literals. More...

template<class T >
using	IntVector = int_vector::IntVector< T >
	A vector over arbitrary unsigned integer types. More...

using	BitVector = IntVector< uint_t< 1 > >
	Represents a bit vector, alias for IntVector with a fixed bit width of 1. More...

using	DynamicIntVector = IntVector< dynamic_t >
	Represents an integer vector with unspecified (dynamic) bit width. More...

using	Select1 = Select< 1 >

using	Select0 = Select< 0 >

template<size_t N>
using	uint_t = typename uint_dispatch_t< N >::type

using	Path = io::Path
	Convenience shortcut to io::Path. More...

using	Input = io::Input
	Convenience shortcut to io::Input. More...

using	Output = io::Output
	Convenience shortcut to io::Output. More...

using	BitIStream = io::BitIStream
	Convenience shortcut to io::BitIStream. More...

using	BitOStream = io::BitOStream
	Convenience shortcut to io::BitOStream. More...

using	BitRange = FixedRange< 0, 1 >
	Represents the range of bit values, ie `0` to `1` More...

using	QuotPtr = IntPtr< dynamic_t >

template<class Self >
using	ConstIntegerBase = ConstIntegerBaseCombiner< ConstIntegerBaseWithSelf< Self >, ConstIntegerBaseWith32< Self, unsigned char >, ConstIntegerBaseWith32< Self, char >, ConstIntegerBaseWith32< Self, signed char >, ConstIntegerBaseWith32< Self, unsigned short int >, ConstIntegerBaseWith32< Self, signed short int >, ConstIntegerBaseWith32< Self, unsigned int >, ConstIntegerBaseWith32< Self, signed int >, ConstIntegerBaseWith64< Self, unsigned long int >, ConstIntegerBaseWith64< Self, signed long int >, ConstIntegerBaseWith64< Self, unsigned long long int >, ConstIntegerBaseWith64< Self, signed long long int > >

template<class Self >
using	IntegerBase = IntegerBaseCombiner< IntegerBaseWithSelf< Self >, IntegerBaseWith32< Self, unsigned char >, IntegerBaseWith32< Self, char >, IntegerBaseWith32< Self, signed char >, IntegerBaseWith32< Self, unsigned short int >, IntegerBaseWith32< Self, signed short int >, IntegerBaseWith32< Self, unsigned int >, IntegerBaseWith32< Self, signed int >, IntegerBaseWith64< Self, unsigned long int >, IntegerBaseWith64< Self, signed long int >, IntegerBaseWith64< Self, unsigned long long int >, IntegerBaseWith64< Self, signed long long int > >

using	ByteView = ConstGenericView< uint8_t >

using	View = ByteView

using	string_ref = View

Enumerations
enum	CompressMode { plain = 0, delayed = 1, compressed = 2, coherent_delayed = 254, select = 255 }
	Defines when data structures are bit-compressed. More...

Functions
template<class value_type = uliteral_t>
value_type	mtf_encode_char (const value_type v, value_type *const table, const size_t table_size)
	Encodes a character 'v' by Move-To-Front Coding Needs and modifies a lookup table storing the last-used characters. More...

template<class value_type = uliteral_t>
value_type	mtf_decode_char (const value_type v, value_type *const table)
	Decodes a character encoded as 'v' by Move-To-Front Coding Needs and modifies a lookup table storing the last-used characters. More...

template<class char_type = uliteral_t>
void	mtf_encode (std::basic_istream< char_type > &is, std::basic_ostream< char_type > &os)

template<class char_type = uliteral_t>
void	mtf_decode (std::basic_istream< char_type > &is, std::basic_ostream< char_type > &os)

template<class char_type >
void	rle_encode (std::basic_istream< char_type > &is, std::basic_ostream< char_type > &os, size_t offset=0)
	Encode a byte-stream with run length encoding each run of the same character is substituted with two occurrences of the same character and the length of the run minus two, encoded in vbyte coding. More...

template<class char_type >
void	rle_decode (std::basic_istream< char_type > &is, std::basic_ostream< char_type > &os, size_t offset=0)
	Decodes a run length encoded stream. More...

template<typename T , typename registry_root_t = T>
Builder< T, registry_root_t >	builder ()
	Builder pattern template for easy algorithm instantiation. More...

template<class T , class... Args>
T	create_algo (const std::string &options, Args &&... args)
	Template for easy algorithm instantiation. More...

template<class T >
T	create_algo ()
	Template for easy algorithm instantiation. More...

Env	create_env (Meta &&meta, const std::string &options="")
	Creates an environment. More...

template<typename T = size_t>
constexpr T	literal2int (uliteral_t c)
	Converts a literal to an integer value as if unsigned. More...

template<typename T = size_t>
constexpr uliteral_t	int2literal (const T &c)
	Converts an integer value to a literal as if unsigned. More...

CompressMode	cm_select (CompressMode in, CompressMode sel)

template<class phi_t , class sa_t >
phi_t	construct_phi_array (const sa_t &sa)
	Constructs the phi array with phi[sa[i]] = sa[i-1]. More...

template<typename phi_t , typename text_t >
void	phi_algorithm (phi_t &phi, const text_t &text)
	Constructs the PLCP array. More...

template<class sa_t , class text_t , class select_t = sdsl::select_support_mcl<1,1>>
sdsl::bit_vector	construct_plcp_bitvector (Env &, const sa_t &sa, const text_t &text)

template<class sa_t , class text_t , class select_t = sdsl::select_support_mcl<1,1>>
LCPSada< sa_t, select_t >	construct_lcp_sada (Env &env, const sa_t &sa, const text_t &text)

constexpr uint8_t	rank1 (uint8_t v)
	Computes the amount of 1-bits in the binary representation of the given 8-bit value. More...

constexpr uint8_t	rank1 (uint16_t v)
	Computes the amount of 1-bits in the binary representation of the given 16-bit value. More...

constexpr uint8_t	rank1 (uint32_t v)
	Computes the amount of 1-bits in the binary representation of the given 32-bit value. More...

constexpr uint8_t	rank1 (uint64_t v)
	Computes the amount of 1-bits in the binary representation of the given 64-bit value. More...

template<typename uint_t >
constexpr uint8_t	rank1 (uint_t v, uint8_t m)
	Computes the amount of 1-bits in an interval of the binary representation of the given value. More...

template<typename uint_t >
constexpr uint8_t	rank1 (uint_t v, uint8_t l, uint8_t m)
	Computes the amount of 1-bits in an interval of the binary representation of the given value. More...

template<typename uint_t >
constexpr uint8_t	rank0 (uint_t v)

template<typename uint_t >
constexpr uint8_t	rank0 (uint_t v, uint8_t m)

template<typename uint_t >
constexpr uint8_t	rank0 (uint_t v, uint8_t l, uint8_t m)

template<typename uint_t >
constexpr uint8_t	select1 (uint_t v, uint8_t k)
	Finds the position of the k-th 1-bit in the binary representation of the given value. More...

template<typename uint_t >
constexpr uint8_t	select1 (uint_t v, uint8_t l, uint8_t k)
	Finds the position of the k-th 1-bit in the binary representation of the given value. More...

template<typename uint_t >
constexpr uint8_t	select0 (uint_t v, uint8_t k)
	Finds the position of the k-th 0-bit in the binary representation of the given value. More...

template<typename uint_t >
constexpr uint8_t	select0 (uint_t v, uint8_t l, uint8_t k)
	Finds the position of the k-th 0-bit in the binary representation of the given value. More...

template<size_t bits>
tdc::uint_impl_t IntegerBase	__attribute__ ((packed))

template<size_t N>
std::ostream &	operator<< (std::ostream &os, const uint_impl_t< N > &v)

template<size_t N>
std::istream &	operator>> (std::istream &is, uint_impl_t< N > &v)

template<typename T >
T	lexical_cast (const std::string &s)

std::ostream &	operator<< (std::ostream &os, const AlgorithmValue &av)

std::ostream &	operator<< (std::ostream &os, const OptionValue &ov)

template<class T , class Q >
void	swap (GenericViewBase< T, Q > &lhs, GenericViewBase< T, Q > &rhs)

uint64_t	compact_hashfn (uint64_t x, uint64_t w)

uint64_t	compact_reverse_hashfn (uint64_t x, uint64_t w)

uint8_t	log2_upper (uint64_t v)

bool	is_pot (size_t n)

QuotPtr	make_quot_ptr (uint64_t *ptr, size_t quot_width)

template<typename V , typename I >
void	rotate_end_to (I base, size_t pos, size_t size)

bool	operator== (const ConstGenericView< uliteral_t > &lhs, const ConstGenericView< uliteral_t > &rhs)

bool	operator!= (const ConstGenericView< uliteral_t > &lhs, const ConstGenericView< uliteral_t > &rhs)

bool	operator< (const ConstGenericView< uliteral_t > &lhs, const ConstGenericView< uliteral_t > &rhs)

bool	operator<= (const ConstGenericView< uliteral_t > &lhs, const ConstGenericView< uliteral_t > &rhs)

bool	operator> (const ConstGenericView< uliteral_t > &lhs, const ConstGenericView< uliteral_t > &rhs)

bool	operator>= (const ConstGenericView< uliteral_t > &lhs, const ConstGenericView< uliteral_t > &rhs)

std::ostream &	operator<< (std::ostream &os, const ConstGenericView< uliteral_t > &v)

ConstGenericView< uliteral_t >	operator"" _v (const char *str, size_t n)
	Custom string literal for constructing a `uliteral` View directly. More...

template<class T >
bool	operator== (const ConstGenericView< T > &lhs, const ConstGenericView< T > &rhs)

template<class T >
bool	operator!= (const ConstGenericView< T > &lhs, const ConstGenericView< T > &rhs)

template<class T >
bool	operator< (const ConstGenericView< T > &lhs, const ConstGenericView< T > &rhs)

template<class T >
bool	operator<= (const ConstGenericView< T > &lhs, const ConstGenericView< T > &rhs)

template<class T >
bool	operator> (const ConstGenericView< T > &lhs, const ConstGenericView< T > &rhs)

template<class T >
bool	operator>= (const ConstGenericView< T > &lhs, const ConstGenericView< T > &rhs)

template<class T >
void	swap (ConstGenericView< T > &lhs, ConstGenericView< T > &rhs)

template<class T >
void	swap (GenericView< T > &lhs, GenericView< T > &rhs)

template<class T >
bool	operator== (const GenericView< T > &lhs, const ConstGenericView< T > &rhs)

template<class T >
bool	operator!= (const GenericView< T > &lhs, const ConstGenericView< T > &rhs)

template<class T >
bool	operator< (const GenericView< T > &lhs, const ConstGenericView< T > &rhs)

template<class T >
bool	operator<= (const GenericView< T > &lhs, const ConstGenericView< T > &rhs)

template<class T >
bool	operator> (const GenericView< T > &lhs, const ConstGenericView< T > &rhs)

template<class T >
bool	operator>= (const GenericView< T > &lhs, const ConstGenericView< T > &rhs)

template<class T >
bool	operator== (const ConstGenericView< T > &lhs, const GenericView< T > &rhs)

template<class T >
bool	operator!= (const ConstGenericView< T > &lhs, const GenericView< T > &rhs)

template<class T >
bool	operator< (const ConstGenericView< T > &lhs, const GenericView< T > &rhs)

template<class T >
bool	operator<= (const ConstGenericView< T > &lhs, const GenericView< T > &rhs)

template<class T >
bool	operator> (const ConstGenericView< T > &lhs, const GenericView< T > &rhs)

template<class T >
bool	operator>= (const ConstGenericView< T > &lhs, const GenericView< T > &rhs)

template<class T >
bool	operator== (const GenericView< T > &lhs, const GenericView< T > &rhs)

template<class T >
bool	operator!= (const GenericView< T > &lhs, const GenericView< T > &rhs)

template<class T >
bool	operator< (const GenericView< T > &lhs, const GenericView< T > &rhs)

template<class T >
bool	operator<= (const GenericView< T > &lhs, const GenericView< T > &rhs)

template<class T >
bool	operator> (const GenericView< T > &lhs, const GenericView< T > &rhs)

template<class T >
bool	operator>= (const GenericView< T > &lhs, const GenericView< T > &rhs)

template<class int_t >
int_t	read_vbyte (std::istream &is)
	Reads an integer stored as a bunch of bytes in the vbyte-encoding. More...

template<class int_t >
void	write_vbyte (std::ostream &os, int_t v)
	Store an integer as a bunch of bytes. More...

template<class T >
std::string	vec_to_debug_string (const T &s, size_t indent=0)
	Builds the string representation of a vector of byte values, sorrounded by square brackets ([ and ]). More...

template<class T >
std::string	arr_to_debug_string (const T *s, size_t length)
	Builds the string representation of an array of printable values, sorrounded by square brackets ([ and ]). More...

std::string	byte_to_nice_ascii_char (uint64_t byte)
	Converts a byte value into its ASCII representation sorrounded by single quotes (`'`) or its string representation. More...

template<class T >
std::string	vec_as_lossy_string (const T &s, size_t start=0, char replacement='?')
	Converts a vector of bytes into a readable ASCII string, substituting non-ASCII symbols. More...

template<typename T >
std::string	to_str (const T &v)
	Represent a value as a string. More...

void	debug_print_uint64_t (uint64_t v)

bool	parse_number_until_other (std::istream &inp, char &last, size_t &out)
	Reads digits from the input stream (`0` to `9`) until a non-digit character is reached and parses them as an integer. More...

constexpr uint_fast8_t	bits_hi (uint64_t x)
	Computes the highest set bit in an integer variable. More...

constexpr uint_fast8_t	bits_for (size_t n)
	Computes the number of bits required to store the given integer value. More...

constexpr size_t	idiv_ceil (size_t a, size_t b)
	Performs an integer division with the result rounded up to the next integer. More...

constexpr uint_fast8_t	bytes_for (size_t n)
	Computes the number of bytes needed to store the given integer value. More...

template<class T >
std::vector< T >	cross (std::vector< std::vector< T >> &&vs, std::function< T(T, T &)> f)
	Creates the cross product of a set of elements given a product function. More...

std::vector< std::string >	split_lines (const std::string &s)
	Splits the input string into lines (separated by `\n`). More...

std::string	indent_lines (const std::string &s, size_t indent)
	Indents each line of a string (separated by `\n`) by the specified amount of spaces. More...

std::string	make_table (const std::vector< std::string > &data, size_t cols, bool draw_grid=true)
	Renders the given dataset into an ASCII table. More...

template<class T >
void	assert_permutation (const T &, size_t)

template<class T >
void	assert_permutation_offset (const T &, size_t, size_t)

template<class T >
constexpr T	round_up_div (T x, T y)
	Division with rounding up to the next integer. More...

template<class int_t >
int_t	isqrt (int_t num)

template<typename T = int>
constexpr T	shift_by (T value, int amount) noexcept

uint64_t	zero_or_next_power_of_two (uint64_t x)

void	get_monotonic_time (struct timespec *ts)

Variables
constexpr size_t	INDEX_MAX = std::numeric_limits<len_compact_t>::max()
	The maximum value of len_compact_t. More...

constexpr size_t	INDEX_BITS = 8 * sizeof(len_compact_t)
	The amount of bits required to store the binary representation of a value of type len_compact_t. More...

constexpr size_t	INDEX_FAST_MAX = std::numeric_limits<len_t>::max()
	The maximum value of len_t. More...

constexpr size_t	INDEX_FAST_BITS = 8 * sizeof(len_t)
	The amount of bits required to store the binary representation of a value of type len_t. More...

constexpr size_t	ULITERAL_MAX = std::numeric_limits<uliteral_t>::max()
	The maximum value of uliteral_t. More...

constexpr uint8_t	rank1_8bit []
	Lookup table for the rank operation on 8-bit values. More...

constexpr uint8_t	SELECT_FAIL = 0xFF
	Returned by select0 and select1 in case the searched bit does not exist in the given input value. More...

class tdc::uint_impl_t< 1 >	__attribute__

constexpr auto	size_r = TypeRange<size_t>()
	Global predefined range for the `size_t`. More...

constexpr auto	bit_r = BitRange()
	Global predefined range for bits (`0` or `1`). More...

constexpr auto	literal_r = LiteralRange()
	Global predefined reange for literals. More...

constexpr auto	uliteral_r = LiteralRange()

constexpr auto	len_r = LengthRange()
	Global predefined range for `len_t`. More...

Detailed Description

Contains the text compression and encoding framework.

This is the framework's central namespace in which text compression and coding algorithms are contained, as well as utilities needed for text compression and coding (e.g. I/O). Families of compressors and encoders or utility groups are contained in the respective sub-namespaces. The namespace tudocomp itself contains types important for all of the framework and its communication.

Typedef Documentation

◆ BitIStream

using tdc::BitIStream = typedef io::BitIStream

Convenience shortcut to io::BitIStream.

Definition at line 23 of file io.hpp.

◆ BitOStream

using tdc::BitOStream = typedef io::BitOStream

Convenience shortcut to io::BitOStream.

Definition at line 26 of file io.hpp.

◆ BitRange

using tdc::BitRange = typedef FixedRange<0, 1>

Represents the range of bit values, ie 0 to 1

Definition at line 102 of file Range.hpp.

◆ BitVector

using tdc::BitVector = typedef IntVector<uint_t<1> >

Represents a bit vector, alias for IntVector with a fixed bit width of 1.

Definition at line 545 of file IntVector.hpp.

◆ ByteView

using tdc::ByteView = typedef ConstGenericView<uint8_t>

Definition at line 24 of file View.hpp.

◆ ConstIntegerBase

template<class Self >

Definition at line 197 of file IntegerBase.hpp.

◆ DynamicIntVector

using tdc::DynamicIntVector = typedef IntVector<dynamic_t>

Represents an integer vector with unspecified (dynamic) bit width.

The bit width defaults to 64 bits, but it can be changed at will via the constructor, or later during runtime using the int_vector::IntVector::width(uint8_t) method.

Definition at line 553 of file IntVector.hpp.

◆ fast_t

template<typename actual_type >

using tdc::fast_t = typedef typename FastIntType<actual_type>::Type

Type to represent integer values in the size range of actual_type that may require more Bits than it, while being faster.

Definition at line 89 of file def.hpp.

◆ Input

using tdc::Input = typedef io::Input

Convenience shortcut to io::Input.

Definition at line 17 of file io.hpp.

◆ IntegerBase

template<class Self >

using tdc::IntegerBase = typedef IntegerBaseCombiner< IntegerBaseWithSelf<Self>, IntegerBaseWith32<Self, unsigned char>, IntegerBaseWith32<Self, char>, IntegerBaseWith32<Self, signed char>, IntegerBaseWith32<Self, unsigned short int>, IntegerBaseWith32<Self, signed short int>, IntegerBaseWith32<Self, unsigned int>, IntegerBaseWith32<Self, signed int>, IntegerBaseWith64<Self, unsigned long int>, IntegerBaseWith64<Self, signed long int>, IntegerBaseWith64<Self, unsigned long long int>, IntegerBaseWith64<Self, signed long long int> >

Definition at line 343 of file IntegerBase.hpp.

◆ IntVector

template<class T >

using tdc::IntVector = typedef int_vector::IntVector<T>

A vector over arbitrary unsigned integer types.

The API behaves mostly identical to std::vector<T>.

Only divergences are the following specializations:

IntVector<uint_t<N>> where N % 8 != 0
IntVector<dynamic_t>

In both cases, the bits of each integer will be packed efficiently next to each other, as opposed to the padding introduced if stored in a std::vector.

In the dynamic_t case, the bit with of an integer can be changed at runtime, in all other cases the corresponding methods will throw.

Definition at line 541 of file IntVector.hpp.

◆ len_compact_t

using tdc::len_compact_t = typedef uint32_t

Type to represent an bit-compact length value.

This type can be defined to take up less bytes than a size_t, but might have worse performance for arithmetic operations. It should only be used for storing many integers in a data structure, to reduce memory usage.

For fast arithmetic operations, prefer a cast to len_t or size_t.

Definition at line 103 of file def.hpp.

◆ len_t

using tdc::len_t = typedef fast_t<len_compact_t>

Type to represent an length value.

This type is defined to take up at least as many bytes as a len_compact_t, but is guaranteed to be a fast integer type with the size of a machine word. It should be used for fast arithmetic operations and local variables.

For a more compact memory footprint in array data structures, prefer a cast to len_compact_t.

Definition at line 114 of file def.hpp.

◆ Output

using tdc::Output = typedef io::Output

Convenience shortcut to io::Output.

Definition at line 20 of file io.hpp.

◆ Path

using tdc::Path = typedef io::Path

Convenience shortcut to io::Path.

Definition at line 14 of file io.hpp.

◆ QuotPtr

using tdc::QuotPtr = typedef IntPtr<dynamic_t>

Definition at line 90 of file compact_sparse_hash.hpp.

◆ Select0

using tdc::Select0 = typedef Select<0>

Definition at line 275 of file Select.hpp.

◆ Select1

using tdc::Select1 = typedef Select<1>

Definition at line 251 of file Select.hpp.

◆ string_ref

using tdc::string_ref = typedef View

Definition at line 26 of file View.hpp.

◆ uint_t

template<size_t N>

using tdc::uint_t = typedef typename uint_dispatch_t<N>::type

Definition at line 165 of file uint_t.hpp.

◆ uliteral_t

typedef uint8_t tdc::uliteral_t

Type to represent signed single literals.

Definition at line 131 of file def.hpp.

◆ View

using tdc::View = typedef ByteView

Definition at line 25 of file View.hpp.

Enumeration Type Documentation

◆ CompressMode

enum tdc::CompressMode

Defines when data structures are bit-compressed.

Enumerator
plain	Data structures are not bit-compressed at all (fastest, but highest memory usage).
delayed	Data structures are bit-compressed after they have been constructed (fast construction, but possibly high memory peak).
compressed	Data structures are constructed directly in bit-compressed space (slower construction, but smaller memory usage).
coherent_delayed	Special mode that will cause no bit-compression at all during construction, internal use in TextDS only.
select	Automatically select compress mode, internal use in TextDS only.

Definition at line 6 of file CompressMode.hpp.

Function Documentation

◆ attribute()

template<size_t bits>

tdc::uint_impl_t IntegerBase tdc::__attribute__ ( (packed) )

◆ arr_to_debug_string()

template<class T >

std::string tdc::arr_to_debug_string	(	const T *	s,
		size_t	length
	)

Builds the string representation of an array of printable values, sorrounded by square brackets ([ and ]).

Example: [1, 2, 3] yields "[1, 2, 3]".

Template Parameters

T	The byte array type.

Parameters

s	The byte array.
length	The length of the byte array.

Returns: The string representation of the byte array.

Definition at line 71 of file include/tudocomp/util.hpp.

◆ assert_permutation()

template<class T >

void tdc::assert_permutation	(	const T &	,
		size_t
	)

inline

Definition at line 472 of file include/tudocomp/util.hpp.

◆ assert_permutation_offset()

template<class T >

void tdc::assert_permutation_offset	(	const T &	,
		size_t	,
		size_t
	)

inline

Definition at line 473 of file include/tudocomp/util.hpp.

◆ bits_for()

constexpr uint_fast8_t tdc::bits_for ( size_t n )

inline

Computes the number of bits required to store the given integer value.

This is equivalent to the binary logarithm rounded up to the next integer.

Examples:

bits_for(0b0) == 1
bits_for(0b1) == 1
bits_for(0b10) == 2
bits_for(0b11) == 2
bits_for(0b100) == 3

Parameters

n	The integer to be stored.

Returns: The amount of bits required to store the value (guaranteed to be greater than zero).

Definition at line 194 of file include/tudocomp/util.hpp.

◆ bits_hi()

constexpr uint_fast8_t tdc::bits_hi ( uint64_t x )

inline

Computes the highest set bit in an integer variable.

Definition at line 175 of file include/tudocomp/util.hpp.

◆ builder()

template<typename T , typename registry_root_t = T>

Builder<T, registry_root_t> tdc::builder ( )

Builder pattern template for easy algorithm instantiation.

Using this function allows the quick instantiation of an Algorithm from its type alone. It will create an environment for the algorithm with the given runtime options and return the created algorithm instance.

Because it has a few optional arguments this function returns a builder for the actual algorithm instance.

Template Parameters

T	The Algorithm type.

Returns: The algorithm builder instance.

Definition at line 83 of file CreateAlgorithm.hpp.

◆ byte_to_nice_ascii_char()

std::string tdc::byte_to_nice_ascii_char ( uint64_t byte )

inline

Converts a byte value into its ASCII representation sorrounded by single quotes (') or its string representation.

Parameters

byte	The byte value.

Returns: 'char(byte)' if the byte represents an ASCII symbol, the string representation of the byte value otherwise.

Definition at line 89 of file include/tudocomp/util.hpp.

◆ bytes_for()

constexpr uint_fast8_t tdc::bytes_for ( size_t n )

inline

Computes the number of bytes needed to store the given integer value.

This is equivalent to binary logarithm divided by 8 and rounded up to the next integer.

Examples:

bytes_for(0) == 1
bytes_for(255) == 1
bytes_for(256) == 2
bytes_for(65535) == 2
bytes_for(65536) == 3
etc.

Parameters

n	The integer to be stored.

Returns: The amount of bits required to store the value (guaranteed to be greater than zero).

Definition at line 225 of file include/tudocomp/util.hpp.

◆ cm_select()

CompressMode tdc::cm_select	(	CompressMode	in,
		CompressMode	sel
	)

inline

Definition at line 27 of file CompressMode.hpp.

◆ compact_hashfn()

uint64_t tdc::compact_hashfn	(	uint64_t	x,
		uint64_t	w
	)

inline

Definition at line 30 of file compact_sparse_hash.hpp.

◆ compact_reverse_hashfn()

uint64_t tdc::compact_reverse_hashfn	(	uint64_t	x,
		uint64_t	w
	)

inline

Definition at line 42 of file compact_sparse_hash.hpp.

◆ construct_lcp_sada()

template<class sa_t , class text_t , class select_t = sdsl::select_support_mcl<1,1>>

LCPSada<sa_t,select_t> tdc::construct_lcp_sada	(	Env &	env,
		const sa_t &	sa,
		const text_t &	text
	)

Definition at line 193 of file LCPSada.hpp.

◆ construct_phi_array()

template<class phi_t , class sa_t >

phi_t tdc::construct_phi_array ( const sa_t & sa )

inline

Constructs the phi array with phi[sa[i]] = sa[i-1].

Parameters

sa	the suffix array

Returns: the phi array

Definition at line 19 of file LCPSada.hpp.

◆ construct_plcp_bitvector()

template<class sa_t , class text_t , class select_t = sdsl::select_support_mcl<1,1>>

sdsl::bit_vector tdc::construct_plcp_bitvector	(	Env &	,
		const sa_t &	sa,
		const text_t &	text
	)

Definition at line 174 of file LCPSada.hpp.

◆ create_algo() [1/2]

template<class T , class... Args>

T tdc::create_algo	(	const std::string &	options,
		Args &&...	args
	)

Template for easy algorithm instantiation.

Using this function allows the quick instantiation of an Algorithm from its type alone. It will create an environment for the algorithm with the given runtime options and return the created algorithm instance.

Template Parameters

T	The Algorithm type.
Args	The constructor's argument types (typically inferred).

Parameters

options	An options string for the created environment.
args	Additional arguments passed to the algorithm's constructor.

Returns: The created algorithm instance.

Definition at line 118 of file CreateAlgorithm.hpp.

◆ create_algo() [2/2]

template<class T >

T tdc::create_algo ( )

Template for easy algorithm instantiation.

Using this function allows the quick instantiation of an Algorithm from its type alone. It will create an environment for the algorithm with no runtime options passed and using the algorithm's constructor.

Template Parameters

T	The Algorithm type.

Returns: The created algorithm instance.

Definition at line 131 of file CreateAlgorithm.hpp.

◆ create_env()

Env tdc::create_env	(	Meta &&	meta,
		const std::string &	options = `""`
	)

inline

Creates an environment.

The environment will be created based on arbitrary tdc::Meta information of an algorithm that may or not really exist. No registry is used to verify.

Parameters

meta	the meta information to use to create the environment.
options	algorithm options to set in the environment.

Returns: the newly created environment.

Definition at line 144 of file CreateAlgorithm.hpp.

◆ cross()

template<class T >

std::vector<T> tdc::cross	(	std::vector< std::vector< T >> &&	vs,
		std::function< T(T, T &)>	f
	)

Creates the cross product of a set of elements given a product function.

The function f is applied to each possible pair of elements in the input set and the results are stored into the result vector.

Template Parameters

The	element type.

Parameters

vs	The input set.
f	The product function.

Returns: The results of the product function for each pair.

Definition at line 283 of file include/tudocomp/util.hpp.

◆ debug_print_uint64_t()

void tdc::debug_print_uint64_t ( uint64_t v )

inline

Definition at line 134 of file include/tudocomp/util.hpp.

◆ get_monotonic_time()

void tdc::get_monotonic_time ( struct timespec * ts )

inline

Definition at line 24 of file StatPhase.hpp.

◆ idiv_ceil()

constexpr size_t tdc::idiv_ceil	(	size_t	a,
		size_t	b
	)

inline

Performs an integer division with the result rounded up to the next integer.

Parameters

a	The dividend.
b	The divisor.

Returns: The quotient, rounded up to the next integer value.

Definition at line 204 of file include/tudocomp/util.hpp.

◆ indent_lines()

std::string tdc::indent_lines	(	const std::string &	s,
		size_t	indent
	)

inline

Indents each line of a string (separated by \n) by the specified amount of spaces.

Parameters

s	The input string.
indent	The amount of spaces to indent each line.

Returns: The indented string.

Definition at line 330 of file include/tudocomp/util.hpp.

◆ int2literal()

template<typename T = size_t>

constexpr uliteral_t tdc::int2literal ( const T & c )

Converts an integer value to a literal as if unsigned.

Template Parameters

T	the integer type.

Parameters

c	the integer value.

Returns: the corresponding literal.

Definition at line 152 of file def.hpp.

◆ is_pot()

bool tdc::is_pot ( size_t n )

inline

Definition at line 57 of file compact_sparse_hash.hpp.

◆ isqrt()

template<class int_t >

int_t tdc::isqrt ( int_t num )

Definition at line 495 of file include/tudocomp/util.hpp.

◆ lexical_cast()

template<typename T >

T tdc::lexical_cast ( const std::string & s )

Definition at line 28 of file OptionValue.hpp.

◆ literal2int()

template<typename T = size_t>

constexpr T tdc::literal2int ( uliteral_t c )

Converts a literal to an integer value as if unsigned.

Template Parameters

T	the integer type.

Parameters

c	the literal.

Returns: the corresponding unsigned integer value.

Definition at line 142 of file def.hpp.

◆ log2_upper()

uint8_t tdc::log2_upper ( uint64_t v )

inline

Definition at line 46 of file compact_sparse_hash.hpp.

◆ make_quot_ptr()

QuotPtr tdc::make_quot_ptr	(	uint64_t *	ptr,
		size_t	quot_width
	)

inline

Definition at line 91 of file compact_sparse_hash.hpp.

◆ make_table()

std::string tdc::make_table	(	const std::vector< std::string > &	data,
		size_t	cols,
		bool	draw_grid = `true`
	)

inline

Renders the given dataset into an ASCII table.

Parameters

data	The data vector. Each contained string represents a cell in the table. Every `cols` entries make up one row.
cols	The amount of columns to display the data in.
draw_grid	If `true`, draws an ASCII grid for the cells.

Returns: The rendered ASCII table string.

Definition at line 354 of file include/tudocomp/util.hpp.

◆ mtf_decode()

template<class char_type = uliteral_t>

void tdc::mtf_decode	(	std::basic_istream< char_type > &	is,
		std::basic_ostream< char_type > &	os
	)

Definition at line 59 of file MTFCompressor.hpp.

◆ mtf_decode_char()

template<class value_type = uliteral_t>

value_type tdc::mtf_decode_char	(	const value_type	v,
		value_type *const	table
	)

Decodes a character encoded as 'v' by Move-To-Front Coding Needs and modifies a lookup table storing the last-used characters.

Definition at line 36 of file MTFCompressor.hpp.

◆ mtf_encode()

template<class char_type = uliteral_t>

void tdc::mtf_encode	(	std::basic_istream< char_type > &	is,
		std::basic_ostream< char_type > &	os
	)

Definition at line 46 of file MTFCompressor.hpp.

◆ mtf_encode_char()

template<class value_type = uliteral_t>

value_type tdc::mtf_encode_char	(	const value_type	v,
		value_type *const	table,
		const size_t	table_size
	)

Encodes a character 'v' by Move-To-Front Coding Needs and modifies a lookup table storing the last-used characters.

Definition at line 17 of file MTFCompressor.hpp.

◆ operator!=() [1/5]

template<class T >

bool tdc::operator!=	(	const ConstGenericView< T > &	lhs,
		const ConstGenericView< T > &	rhs
	)

Definition at line 283 of file GenericConstView.hpp.

◆ operator!=() [2/5]

bool tdc::operator!=	(	const ConstGenericView< uliteral_t > &	lhs,
		const ConstGenericView< uliteral_t > &	rhs
	)

inline

Definition at line 296 of file GenericConstU8View.hpp.

◆ operator!=() [3/5]

template<class T >

bool tdc::operator!=	(	const GenericView< T > &	lhs,
		const ConstGenericView< T > &	rhs
	)

Definition at line 319 of file GenericView.hpp.

◆ operator!=() [4/5]

template<class T >

bool tdc::operator!=	(	const ConstGenericView< T > &	lhs,
		const GenericView< T > &	rhs
	)

Definition at line 349 of file GenericView.hpp.

◆ operator!=() [5/5]

template<class T >

bool tdc::operator!=	(	const GenericView< T > &	lhs,
		const GenericView< T > &	rhs
	)

Definition at line 379 of file GenericView.hpp.

◆ operator"" _v()

ConstGenericView<uliteral_t> tdc::operator"" _v	(	const char *	str,
		size_t	n
	)

inline

Custom string literal for constructing a uliteral View directly.

Example: auto v = "abc"_v;

Definition at line 330 of file GenericConstU8View.hpp.

◆ operator<() [1/5]

template<class T >

bool tdc::operator<	(	const ConstGenericView< T > &	lhs,
		const ConstGenericView< T > &	rhs
	)

Definition at line 288 of file GenericConstView.hpp.

◆ operator<() [2/5]

bool tdc::operator<	(	const ConstGenericView< uliteral_t > &	lhs,
		const ConstGenericView< uliteral_t > &	rhs
	)

inline

Definition at line 301 of file GenericConstU8View.hpp.

◆ operator<() [3/5]

template<class T >

bool tdc::operator<	(	const GenericView< T > &	lhs,
		const ConstGenericView< T > &	rhs
	)

Definition at line 324 of file GenericView.hpp.

◆ operator<() [4/5]

template<class T >

bool tdc::operator<	(	const ConstGenericView< T > &	lhs,
		const GenericView< T > &	rhs
	)

Definition at line 354 of file GenericView.hpp.

◆ operator<() [5/5]

template<class T >

bool tdc::operator<	(	const GenericView< T > &	lhs,
		const GenericView< T > &	rhs
	)

Definition at line 384 of file GenericView.hpp.

◆ operator<<() [1/4]

std::ostream & tdc::operator<<	(	std::ostream &	os,
		const AlgorithmValue &	av
	)

inline

Definition at line 198 of file OptionValue.hpp.

◆ operator<<() [2/4]

std::ostream & tdc::operator<<	(	std::ostream &	os,
		const OptionValue &	ov
	)

inline

Definition at line 210 of file OptionValue.hpp.

◆ operator<<() [3/4]

template<size_t N>

std::ostream& tdc::operator<<	(	std::ostream &	os,
		const uint_impl_t< N > &	v
	)

inline

Definition at line 135 of file uint_t.hpp.

◆ operator<<() [4/4]

std::ostream& tdc::operator<<	(	std::ostream &	os,
		const ConstGenericView< uliteral_t > &	v
	)

inline

Definition at line 321 of file GenericConstU8View.hpp.

◆ operator<=() [1/5]

template<class T >

bool tdc::operator<=	(	const ConstGenericView< T > &	lhs,
		const ConstGenericView< T > &	rhs
	)

Definition at line 293 of file GenericConstView.hpp.

◆ operator<=() [2/5]

bool tdc::operator<=	(	const ConstGenericView< uliteral_t > &	lhs,
		const ConstGenericView< uliteral_t > &	rhs
	)

inline

Definition at line 306 of file GenericConstU8View.hpp.

◆ operator<=() [3/5]

template<class T >

bool tdc::operator<=	(	const GenericView< T > &	lhs,
		const ConstGenericView< T > &	rhs
	)

Definition at line 329 of file GenericView.hpp.

◆ operator<=() [4/5]

template<class T >

bool tdc::operator<=	(	const ConstGenericView< T > &	lhs,
		const GenericView< T > &	rhs
	)

Definition at line 359 of file GenericView.hpp.

◆ operator<=() [5/5]

template<class T >

bool tdc::operator<=	(	const GenericView< T > &	lhs,
		const GenericView< T > &	rhs
	)

Definition at line 389 of file GenericView.hpp.

◆ operator==() [1/5]

template<class T >

bool tdc::operator==	(	const ConstGenericView< T > &	lhs,
		const ConstGenericView< T > &	rhs
	)

Definition at line 278 of file GenericConstView.hpp.

◆ operator==() [2/5]

bool tdc::operator==	(	const ConstGenericView< uliteral_t > &	lhs,
		const ConstGenericView< uliteral_t > &	rhs
	)

inline

Definition at line 291 of file GenericConstU8View.hpp.

◆ operator==() [3/5]

template<class T >

bool tdc::operator==	(	const GenericView< T > &	lhs,
		const ConstGenericView< T > &	rhs
	)

Definition at line 314 of file GenericView.hpp.

◆ operator==() [4/5]

template<class T >

bool tdc::operator==	(	const ConstGenericView< T > &	lhs,
		const GenericView< T > &	rhs
	)

Definition at line 344 of file GenericView.hpp.

◆ operator==() [5/5]

template<class T >

bool tdc::operator==	(	const GenericView< T > &	lhs,
		const GenericView< T > &	rhs
	)

Definition at line 374 of file GenericView.hpp.

◆ operator>() [1/5]

template<class T >

bool tdc::operator>	(	const ConstGenericView< T > &	lhs,
		const ConstGenericView< T > &	rhs
	)

Definition at line 298 of file GenericConstView.hpp.

◆ operator>() [2/5]

bool tdc::operator>	(	const ConstGenericView< uliteral_t > &	lhs,
		const ConstGenericView< uliteral_t > &	rhs
	)

inline

Definition at line 311 of file GenericConstU8View.hpp.

◆ operator>() [3/5]

template<class T >

bool tdc::operator>	(	const GenericView< T > &	lhs,
		const ConstGenericView< T > &	rhs
	)

Definition at line 334 of file GenericView.hpp.

◆ operator>() [4/5]

template<class T >

bool tdc::operator>	(	const ConstGenericView< T > &	lhs,
		const GenericView< T > &	rhs
	)

Definition at line 364 of file GenericView.hpp.

◆ operator>() [5/5]

template<class T >

bool tdc::operator>	(	const GenericView< T > &	lhs,
		const GenericView< T > &	rhs
	)

Definition at line 394 of file GenericView.hpp.

◆ operator>=() [1/5]

template<class T >

bool tdc::operator>=	(	const ConstGenericView< T > &	lhs,
		const ConstGenericView< T > &	rhs
	)

Definition at line 303 of file GenericConstView.hpp.

◆ operator>=() [2/5]

bool tdc::operator>=	(	const ConstGenericView< uliteral_t > &	lhs,
		const ConstGenericView< uliteral_t > &	rhs
	)

inline

Definition at line 316 of file GenericConstU8View.hpp.

◆ operator>=() [3/5]

template<class T >

bool tdc::operator>=	(	const GenericView< T > &	lhs,
		const ConstGenericView< T > &	rhs
	)

Definition at line 339 of file GenericView.hpp.

◆ operator>=() [4/5]

template<class T >

bool tdc::operator>=	(	const ConstGenericView< T > &	lhs,
		const GenericView< T > &	rhs
	)

Definition at line 369 of file GenericView.hpp.

◆ operator>=() [5/5]

template<class T >

bool tdc::operator>=	(	const GenericView< T > &	lhs,
		const GenericView< T > &	rhs
	)

Definition at line 399 of file GenericView.hpp.

◆ operator>>()

template<size_t N>

std::istream& tdc::operator>>	(	std::istream &	is,
		uint_impl_t< N > &	v
	)

inline

Definition at line 140 of file uint_t.hpp.

◆ parse_number_until_other()

bool tdc::parse_number_until_other	(	std::istream &	inp,
		char &	last,
		size_t &	out
	)

inline

Reads digits from the input stream (0 to 9) until a non-digit character is reached and parses them as an integer.

If the initial stream position contains a non-digit, a value of zero is parsed.

Parameters

inp	The input stream.
last	Used to store the first non-digit character read upon termination.
out	Used to store the parsed integer value. This will be zero if no digit character is found.

Returns: true if there are more characters left on the stream after reading to the first non-digit, false if the stream is over.

Definition at line 157 of file include/tudocomp/util.hpp.

◆ phi_algorithm()

template<typename phi_t , typename text_t >

void tdc::phi_algorithm	(	phi_t &	phi,
		const text_t &	text
	)

inline

Constructs the PLCP array.

Parameters

phi	the phi-array. Will be overwritten with PLCP
text	the input text

Author: Kärkkäinen et. al, "Permuted Longest-Common-Prefix Array", CPM'09

Definition at line 40 of file LCPSada.hpp.

◆ rank0() [1/3]

template<typename uint_t >

constexpr uint8_t tdc::rank0 ( uint_t v )

inline

Definition at line 122 of file rank_64bit.hpp.

◆ rank0() [2/3]

template<typename uint_t >

constexpr uint8_t tdc::rank0	(	uint_t	v,
		uint8_t	m
	)

inline

Definition at line 127 of file rank_64bit.hpp.

◆ rank0() [3/3]

template<typename uint_t >

constexpr uint8_t tdc::rank0	(	uint_t	v,
		uint8_t	l,
		uint8_t	m
	)

inline

Definition at line 132 of file rank_64bit.hpp.

◆ rank1() [1/6]

constexpr uint8_t tdc::rank1 ( uint8_t v )

inline

Computes the amount of 1-bits in the binary representation of the given 8-bit value.

Parameters

v	the value in question

Returns: the amount of 1-bits in the value's binary representation

Definition at line 51 of file rank_64bit.hpp.

◆ rank1() [2/6]

constexpr uint8_t tdc::rank1 ( uint16_t v )

inline

Computes the amount of 1-bits in the binary representation of the given 16-bit value.

Parameters

v	the value in question

Returns: the amount of 1-bits in the value's binary representation

Definition at line 59 of file rank_64bit.hpp.

◆ rank1() [3/6]

constexpr uint8_t tdc::rank1 ( uint32_t v )

inline

Computes the amount of 1-bits in the binary representation of the given 32-bit value.

Parameters

v	the value in question

Returns: the amount of 1-bits in the value's binary representation

Definition at line 67 of file rank_64bit.hpp.

◆ rank1() [4/6]

constexpr uint8_t tdc::rank1 ( uint64_t v )

inline

Computes the amount of 1-bits in the binary representation of the given 64-bit value.

Parameters

v	the value in question

Returns: the amount of 1-bits in the value's binary representation

Definition at line 75 of file rank_64bit.hpp.

◆ rank1() [5/6]

template<typename uint_t >

constexpr uint8_t tdc::rank1	(	uint_t	v,
		uint8_t	m
	)

inline

Computes the amount of 1-bits in an interval of the binary representation of the given value.

The rank value computed is that of the bit interval [0,m] in zero-based LSBF order.

Template Parameters

uint_t the type of the value in question

Parameters

v	the value in question
m	the most significant bit (up until which to count)

Returns: the amount of 1-bits in the given interval

Definition at line 90 of file rank_64bit.hpp.

◆ rank1() [6/6]

template<typename uint_t >

constexpr uint8_t tdc::rank1	(	uint_t	v,
		uint8_t	l,
		uint8_t	m
	)

inline

Computes the amount of 1-bits in an interval of the binary representation of the given value.

The rank value computed is that of the bit interval [l,m] in zero-based LSBF order.

Template Parameters

uint_t the type of the value in question

Parameters

v	the value in question
l	the least significant bit (from which the counting starts)
m	the most significant bit (up until which to count)

Returns: the amount of 1-bits in the given interval

Definition at line 109 of file rank_64bit.hpp.

◆ read_vbyte()

template<class int_t >

int_t tdc::read_vbyte ( std::istream & is )

inline

Reads an integer stored as a bunch of bytes in the vbyte-encoding.

Definition at line 11 of file vbyte.hpp.

◆ rle_decode()

template<class char_type >

void tdc::rle_decode	(	std::basic_istream< char_type > &	is,
		std::basic_ostream< char_type > &	os,
		size_t	offset = `0`
	)

Decodes a run length encoded stream.

Definition at line 37 of file RunLengthEncoder.hpp.

◆ rle_encode()

template<class char_type >

void tdc::rle_encode	(	std::basic_istream< char_type > &	is,
		std::basic_ostream< char_type > &	os,
		size_t	offset = `0`
	)

Encode a byte-stream with run length encoding each run of the same character is substituted with two occurrences of the same character and the length of the run minus two, encoded in vbyte coding.

Definition at line 16 of file RunLengthEncoder.hpp.

◆ rotate_end_to()

template<typename V , typename I >

void tdc::rotate_end_to	(	I	base,
		size_t	pos,
		size_t	size
	)

inline

Definition at line 97 of file compact_sparse_hash.hpp.

◆ round_up_div()

template<class T >

constexpr T tdc::round_up_div	(	T	x,
		T	y
	)

Division with rounding up to the next integer.

Call equivalent to (int) std::ceil(((double)x)/y)

Parameters

x	dividend
y	divisor

Returns: ceiling of the term x/y

Definition at line 485 of file include/tudocomp/util.hpp.

◆ select0() [1/2]

template<typename uint_t >

constexpr uint8_t tdc::select0	(	uint_t	v,
		uint8_t	k
	)

inline

Finds the position of the k-th 0-bit in the binary representation of the given value.

The search starts with the least significant bit.

Template Parameters

uint_t the input value type

Parameters

v	the input value
k	the searched 0-bit

Returns: the position of the k-th 0-bit (LSBF and zero-based), or SELECT_FAIL if no such bit exists

Definition at line 65 of file select_64bit.hpp.

◆ select0() [2/2]

template<typename uint_t >

constexpr uint8_t tdc::select0	(	uint_t	v,
		uint8_t	l,
		uint8_t	k
	)

inline

Finds the position of the k-th 0-bit in the binary representation of the given value.

Template Parameters

uint_t the input value type

Parameters

v	the input value
l	the bit (LSBF order) to start searching from
k	the searched 0-bit

Returns: the position of the k-th 0-bit (LSBF and zero-based), or SELECT_FAIL if no such bit exists

Definition at line 89 of file select_64bit.hpp.

◆ select1() [1/2]

template<typename uint_t >

constexpr uint8_t tdc::select1	(	uint_t	v,
		uint8_t	k
	)

inline

Finds the position of the k-th 1-bit in the binary representation of the given value.

The search starts with the least significant bit.

Template Parameters

uint_t the input value type

Parameters

v	the input value
k	the searched 1-bit

Returns: the position of the k-th 1-bit (LSBF and zero-based), or SELECT_FAIL if no such bit exists

Definition at line 26 of file select_64bit.hpp.

◆ select1() [2/2]

template<typename uint_t >

constexpr uint8_t tdc::select1	(	uint_t	v,
		uint8_t	l,
		uint8_t	k
	)

inline

Finds the position of the k-th 1-bit in the binary representation of the given value.

Template Parameters

uint_t the input value type

Parameters

v	the input value
l	the bit (LSBF order) to start searching from
k	the searched 1-bit

Returns: the position of the k-th 1-bit (LSBF and zero-based), or SELECT_FAIL if no such bit exists

Definition at line 49 of file select_64bit.hpp.

◆ shift_by()

template<typename T = int>

constexpr T tdc::shift_by	(	T	value,
		int	amount
	)

noexcept

Definition at line 582 of file include/tudocomp/util.hpp.

◆ split_lines()

std::vector<std::string> tdc::split_lines ( const std::string & s )

inline

Splits the input string into lines (separated by \n).

Parameters

s	The input string.

Returns: A vector containing the individual lines.

Definition at line 312 of file include/tudocomp/util.hpp.

◆ swap() [1/3]

template<class T , class Q >

void tdc::swap	(	GenericViewBase< T, Q > &	lhs,
		GenericViewBase< T, Q > &	rhs
	)

Definition at line 254 of file GenericViewBase.hpp.

◆ swap() [2/3]

template<class T >

void tdc::swap	(	ConstGenericView< T > &	lhs,
		ConstGenericView< T > &	rhs
	)

Definition at line 308 of file GenericConstView.hpp.

◆ swap() [3/3]

template<class T >

void tdc::swap	(	GenericView< T > &	lhs,
		GenericView< T > &	rhs
	)

Definition at line 308 of file GenericView.hpp.

◆ to_str()

template<typename T >

std::string tdc::to_str ( const T & v )

inline

Represent a value as a string.

Template Parameters

T	the value type.

Parameters

v	the value to convert.

Returns: the string representation of the given value.

Definition at line 128 of file include/tudocomp/util.hpp.

◆ vec_as_lossy_string()

template<class T >

std::string tdc::vec_as_lossy_string	(	const T &	s,
		size_t	start = `0`,
		char	replacement = `'?'`
	)

Converts a vector of bytes into a readable ASCII string, substituting non-ASCII symbols.

Example: [97, 32, 97, 0] is converted to "a a?".

Template Parameters

T	The input vector type.

Parameters

s	The input vector.
start	The indext at which to start processing the vector.
replacement	The character to replace non-ASCII symbols with.

Returns: The ASCII string representation of the byte vector.

Definition at line 110 of file include/tudocomp/util.hpp.

◆ vec_to_debug_string()

template<class T >

std::string tdc::vec_to_debug_string	(	const T &	s,
		size_t	indent = `0`
	)

Builds the string representation of a vector of byte values, sorrounded by square brackets ([ and ]).

Example: [1, 2, 3] yields "[1, 2, 3]".

Template Parameters

T	The byte vector type.

Parameters

s	The byte vector.
indent	The amount of spaces to indent the string by.

Returns: The string representation of the byte vector.

Definition at line 46 of file include/tudocomp/util.hpp.

◆ write_vbyte()

template<class int_t >

void tdc::write_vbyte	(	std::ostream &	os,
		int_t	v
	)

inline

Store an integer as a bunch of bytes.

The highest bit determines whether a byte is the last byte representing the integer

Definition at line 29 of file vbyte.hpp.

◆ zero_or_next_power_of_two()

uint64_t tdc::zero_or_next_power_of_two ( uint64_t x )

inline

Definition at line 589 of file include/tudocomp/util.hpp.

Variable Documentation

◆ attribute

class tdc::uint_impl_t< 1 > tdc::__attribute__

◆ bit_r

constexpr auto tdc::bit_r = BitRange()

Global predefined range for bits (0 or 1).

Definition at line 108 of file Range.hpp.

◆ INDEX_BITS

constexpr size_t tdc::INDEX_BITS = 8 * sizeof(len_compact_t)

The amount of bits required to store the binary representation of a value of type len_compact_t.

Definition at line 121 of file def.hpp.

◆ INDEX_FAST_BITS

constexpr size_t tdc::INDEX_FAST_BITS = 8 * sizeof(len_t)

The amount of bits required to store the binary representation of a value of type len_t.

Definition at line 128 of file def.hpp.

◆ INDEX_FAST_MAX

constexpr size_t tdc::INDEX_FAST_MAX = std::numeric_limits<len_t>::max()

The maximum value of len_t.

Definition at line 124 of file def.hpp.

◆ INDEX_MAX

constexpr size_t tdc::INDEX_MAX = std::numeric_limits<len_compact_t>::max()

The maximum value of len_compact_t.

Definition at line 117 of file def.hpp.

◆ len_r

constexpr auto tdc::len_r = LengthRange()

Global predefined range for len_t.

Definition at line 115 of file Range.hpp.

◆ literal_r

constexpr auto tdc::literal_r = LiteralRange()

Global predefined reange for literals.

Definition at line 111 of file Range.hpp.

◆ rank1_8bit

constexpr uint8_t tdc::rank1_8bit[]

Lookup table for the rank operation on 8-bit values.

At index i, this table contains the amount of 1-bits in the binary representation of the value i.

Definition at line 12 of file rank_64bit.hpp.

◆ SELECT_FAIL

constexpr uint8_t tdc::SELECT_FAIL = 0xFF

Returned by select0 and select1 in case the searched bit does not exist in the given input value.

Definition at line 13 of file select_64bit.hpp.

◆ size_r

constexpr auto tdc::size_r = TypeRange<size_t>()

Global predefined range for the size_t.

Definition at line 105 of file Range.hpp.

◆ ULITERAL_MAX

constexpr size_t tdc::ULITERAL_MAX = std::numeric_limits<uliteral_t>::max()

The maximum value of uliteral_t.

Definition at line 134 of file def.hpp.

◆ uliteral_r

constexpr auto tdc::uliteral_r = LiteralRange()

Definition at line 112 of file Range.hpp.

Namespaces

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

Typedef Documentation

◆ BitIStream

◆ BitOStream

◆ BitRange

◆ BitVector

◆ ByteView

◆ ConstIntegerBase

◆ DynamicIntVector

◆ fast_t

◆ Input

◆ IntegerBase

◆ IntVector

◆ len_compact_t

◆ len_t

◆ Output

◆ Path

◆ QuotPtr

◆ Select0

◆ Select1

◆ string_ref

◆ uint_t

◆ uliteral_t

◆ View

Enumeration Type Documentation

◆ CompressMode

Function Documentation

◆ __attribute__()

◆ arr_to_debug_string()

◆ assert_permutation()

◆ assert_permutation_offset()

◆ bits_for()

◆ bits_hi()

◆ builder()

◆ byte_to_nice_ascii_char()

◆ bytes_for()

◆ cm_select()

◆ compact_hashfn()

◆ compact_reverse_hashfn()

◆ construct_lcp_sada()

◆ construct_phi_array()

◆ construct_plcp_bitvector()

◆ create_algo() [1/2]

◆ create_algo() [2/2]

◆ create_env()

◆ cross()

◆ debug_print_uint64_t()

◆ get_monotonic_time()

◆ idiv_ceil()

◆ indent_lines()

◆ int2literal()

◆ is_pot()

◆ isqrt()

◆ lexical_cast()

◆ literal2int()

◆ log2_upper()

◆ make_quot_ptr()

◆ make_table()

◆ mtf_decode()

◆ mtf_decode_char()

◆ mtf_encode()

◆ mtf_encode_char()

◆ operator!=() [1/5]

◆ operator!=() [2/5]

◆ operator!=() [3/5]

◆ operator!=() [4/5]

◆ operator!=() [5/5]

◆ operator"" _v()

◆ operator<() [1/5]

◆ operator<() [2/5]

◆ operator<() [3/5]

◆ operator<() [4/5]

◆ operator<() [5/5]

◆ operator<<() [1/4]

◆ attribute()

◆ attribute