tudocomp
– The TU Dortmund Compression Framework
tdc Namespace Reference

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>
create_algo (const std::string &options, Args &&...args)
 Template for easy algorithm instantiation. More...
 
template<class 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 >
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_toperator""_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

Convenience shortcut to io::BitIStream.

Definition at line 23 of file io.hpp.

Convenience shortcut to io::BitOStream.

Definition at line 26 of file io.hpp.

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.

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.

using tdc::ByteView = typedef ConstGenericView<uint8_t>

Definition at line 24 of file View.hpp.

template<class Self >
using tdc::ConstIntegerBase = typedef 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> >

Definition at line 197 of file IntegerBase.hpp.

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.

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.

using tdc::Input = typedef io::Input

Convenience shortcut to io::Input.

Definition at line 17 of file io.hpp.

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.

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.

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.

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.

using tdc::Output = typedef io::Output

Convenience shortcut to io::Output.

Definition at line 20 of file io.hpp.

using tdc::Path = typedef io::Path

Convenience shortcut to io::Path.

Definition at line 14 of file io.hpp.

using tdc::QuotPtr = typedef IntPtr<dynamic_t>

Definition at line 90 of file compact_sparse_hash.hpp.

using tdc::Select0 = typedef Select<0>

Definition at line 275 of file Select.hpp.

using tdc::Select1 = typedef Select<1>

Definition at line 251 of file Select.hpp.

using tdc::string_ref = typedef View

Definition at line 26 of file View.hpp.

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

Definition at line 165 of file uint_t.hpp.

typedef uint8_t tdc::uliteral_t

Type to represent signed single literals.

Definition at line 131 of file def.hpp.

using tdc::View = typedef ByteView

Definition at line 25 of file View.hpp.

Enumeration Type Documentation

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

template<size_t bits>
tdc::uint_impl_t IntegerBase tdc::__attribute__ ( (packed)  )
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
TThe byte array type.
Parameters
sThe byte array.
lengthThe length of the byte array.
Returns
The string representation of the byte array.

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

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

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

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.

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
nThe 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.

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.

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
TThe Algorithm type.
Returns
The algorithm builder instance.

Definition at line 83 of file CreateAlgorithm.hpp.

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
byteThe 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.

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
nThe 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.

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

Definition at line 27 of file CompressMode.hpp.

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

Definition at line 30 of file compact_sparse_hash.hpp.

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

Definition at line 42 of file compact_sparse_hash.hpp.

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.

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
sathe suffix array
Returns
the phi array

Definition at line 19 of file LCPSada.hpp.

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.

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
TThe Algorithm type.
ArgsThe constructor's argument types (typically inferred).
Parameters
optionsAn options string for the created environment.
argsAdditional arguments passed to the algorithm's constructor.
Returns
The created algorithm instance.

Definition at line 118 of file CreateAlgorithm.hpp.

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
TThe Algorithm type.
Returns
The created algorithm instance.

Definition at line 131 of file CreateAlgorithm.hpp.

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
metathe meta information to use to create the environment.
optionsalgorithm options to set in the environment.
Returns
the newly created environment.

Definition at line 144 of file CreateAlgorithm.hpp.

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
Theelement type.
Parameters
vsThe input set.
fThe product function.
Returns
The results of the product function for each pair.

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

void tdc::debug_print_uint64_t ( uint64_t  v)
inline

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

void tdc::get_monotonic_time ( struct timespec *  ts)
inline

Definition at line 24 of file StatPhase.hpp.

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
aThe dividend.
bThe divisor.
Returns
The quotient, rounded up to the next integer value.

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

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
sThe input string.
indentThe amount of spaces to indent each line.
Returns
The indented string.

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

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
Tthe integer type.
Parameters
cthe integer value.
Returns
the corresponding literal.

Definition at line 152 of file def.hpp.

bool tdc::is_pot ( size_t  n)
inline

Definition at line 57 of file compact_sparse_hash.hpp.

template<class int_t >
int_t tdc::isqrt ( int_t  num)

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

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

Definition at line 28 of file OptionValue.hpp.

template<typename T = size_t>
constexpr T tdc::literal2int ( uliteral_t  c)

Converts a literal to an integer value as if unsigned.

Template Parameters
Tthe integer type.
Parameters
cthe literal.
Returns
the corresponding unsigned integer value.

Definition at line 142 of file def.hpp.

uint8_t tdc::log2_upper ( uint64_t  v)
inline

Definition at line 46 of file compact_sparse_hash.hpp.

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

Definition at line 91 of file compact_sparse_hash.hpp.

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
dataThe data vector. Each contained string represents a cell in the table. Every cols entries make up one row.
colsThe amount of columns to display the data in.
draw_gridIf true, draws an ASCII grid for the cells.
Returns
The rendered ASCII table string.

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

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.

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.

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.

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.

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

Definition at line 283 of file GenericConstView.hpp.

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

Definition at line 296 of file GenericConstU8View.hpp.

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

Definition at line 319 of file GenericView.hpp.

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

Definition at line 349 of file GenericView.hpp.

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

Definition at line 379 of file GenericView.hpp.

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.

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

Definition at line 288 of file GenericConstView.hpp.

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

Definition at line 301 of file GenericConstU8View.hpp.

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

Definition at line 324 of file GenericView.hpp.

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

Definition at line 354 of file GenericView.hpp.

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

Definition at line 384 of file GenericView.hpp.

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

Definition at line 198 of file OptionValue.hpp.

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

Definition at line 210 of file OptionValue.hpp.

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.

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

Definition at line 321 of file GenericConstU8View.hpp.

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

Definition at line 293 of file GenericConstView.hpp.

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

Definition at line 306 of file GenericConstU8View.hpp.

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

Definition at line 329 of file GenericView.hpp.

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

Definition at line 359 of file GenericView.hpp.

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

Definition at line 389 of file GenericView.hpp.

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

Definition at line 278 of file GenericConstView.hpp.

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

Definition at line 291 of file GenericConstU8View.hpp.

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

Definition at line 314 of file GenericView.hpp.

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

Definition at line 344 of file GenericView.hpp.

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

Definition at line 374 of file GenericView.hpp.

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

Definition at line 298 of file GenericConstView.hpp.

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

Definition at line 311 of file GenericConstU8View.hpp.

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

Definition at line 334 of file GenericView.hpp.

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

Definition at line 364 of file GenericView.hpp.

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

Definition at line 394 of file GenericView.hpp.

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

Definition at line 303 of file GenericConstView.hpp.

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

Definition at line 316 of file GenericConstU8View.hpp.

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

Definition at line 339 of file GenericView.hpp.

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

Definition at line 369 of file GenericView.hpp.

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

Definition at line 399 of file GenericView.hpp.

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.

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
inpThe input stream.
lastUsed to store the first non-digit character read upon termination.
outUsed 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.

template<typename phi_t , typename text_t >
void tdc::phi_algorithm ( phi_t &  phi,
const text_t &  text 
)
inline

Constructs the PLCP array.

Parameters
phithe phi-array. Will be overwritten with PLCP
textthe input text
Author
Kärkkäinen et. al, "Permuted Longest-Common-Prefix Array", CPM'09

Definition at line 40 of file LCPSada.hpp.

template<typename uint_t >
constexpr uint8_t tdc::rank0 ( uint_t  v)
inline

Definition at line 122 of file rank_64bit.hpp.

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.

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.

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
vthe value in question
Returns
the amount of 1-bits in the value's binary representation

Definition at line 51 of file rank_64bit.hpp.

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
vthe value in question
Returns
the amount of 1-bits in the value's binary representation

Definition at line 59 of file rank_64bit.hpp.

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
vthe value in question
Returns
the amount of 1-bits in the value's binary representation

Definition at line 67 of file rank_64bit.hpp.

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
vthe value in question
Returns
the amount of 1-bits in the value's binary representation

Definition at line 75 of file rank_64bit.hpp.

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_tthe type of the value in question
Parameters
vthe value in question
mthe 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.

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_tthe type of the value in question
Parameters
vthe value in question
lthe least significant bit (from which the counting starts)
mthe 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.

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.

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.

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.

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

Definition at line 97 of file compact_sparse_hash.hpp.

template<class T >
constexpr T tdc::round_up_div ( x,
y 
)

Division with rounding up to the next integer.

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

Parameters
xdividend
ydivisor
Returns
ceiling of the term x/y

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

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_tthe input value type
Parameters
vthe input value
kthe 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.

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_tthe input value type
Parameters
vthe input value
lthe bit (LSBF order) to start searching from
kthe 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.

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_tthe input value type
Parameters
vthe input value
kthe 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.

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_tthe input value type
Parameters
vthe input value
lthe bit (LSBF order) to start searching from
kthe 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.

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

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

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

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

Parameters
sThe input string.
Returns
A vector containing the individual lines.

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

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

Definition at line 254 of file GenericViewBase.hpp.

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

Definition at line 308 of file GenericConstView.hpp.

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

Definition at line 308 of file GenericView.hpp.

template<typename T >
std::string tdc::to_str ( const T &  v)
inline

Represent a value as a string.

Template Parameters
Tthe value type.
Parameters
vthe value to convert.
Returns
the string representation of the given value.

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

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
TThe input vector type.
Parameters
sThe input vector.
startThe indext at which to start processing the vector.
replacementThe 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.

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
TThe byte vector type.
Parameters
sThe byte vector.
indentThe 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.

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.

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

class tdc::uint_impl_t< 1 > tdc::__attribute__
constexpr auto tdc::bit_r = BitRange()

Global predefined range for bits (0 or 1).

Definition at line 108 of file Range.hpp.

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.

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.

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.

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.

constexpr auto tdc::len_r = LengthRange()

Global predefined range for len_t.

Definition at line 115 of file Range.hpp.

constexpr auto tdc::literal_r = LiteralRange()

Global predefined reange for literals.

Definition at line 111 of file Range.hpp.

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.

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.

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

Global predefined range for the size_t.

Definition at line 105 of file Range.hpp.

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.

constexpr auto tdc::uliteral_r = LiteralRange()

Definition at line 112 of file Range.hpp.