SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl Namespace Reference

Namespace for the succinct data structure library. More...

Namespaces

namespace  algorithm
 
namespace  coder
 Namespace for the different coder of the sdsl.
 
namespace  conf
 
namespace  detail
 
namespace  k2_treap_ns
 
namespace  k2_tree_ns
 Namespace for the k2_tree.
 
namespace  qsufsort
 
namespace  ram_fs
 
namespace  util
 A namespace for helper functions.
 

Classes

struct  _balanced_shape
 
class  _bwt_sampling
 
struct  _byte_tree
 
class  _fuzzy_isa_sampling_support
 
class  _fuzzy_sa_sampling
 
struct  _huff_shape
 
struct  _hutu_shape
 
struct  _int_tree
 
struct  _interval_symbols_wt
 
struct  _interval_symbols_wt< t_wt, false >
 
class  _isa_sampling
 
class  _lcp_support_sada
 A class to represent the LCP array in compressed form. More...
 
class  _lcp_support_tree
 This class composes a virtual LCP array from a LCP arrays which is in suffix array order (e.g. More...
 
class  _lcp_support_tree2
 An lcp array class for cst_sct3 and cst_sada. More...
 
struct  _node
 
class  _sa_order_sampling
 
struct  _symbols_calls_wt
 
struct  _symbols_calls_wt< t_wt, false >
 
class  _text_order_isa_sampling_support
 
class  _text_order_sampling
 
struct  _trbudget_t
 
struct  alphabet_tag
 
struct  alphabet_trait
 
struct  alphabet_trait< int_alphabet_tag >
 
struct  balanced_shape
 
struct  bfoot
 
class  binomial15_impl
 
struct  binomial_coefficients
 A struct for the binomial coefficients $ n \choose k $. More...
 
struct  binomial_coefficients_trait
 Trait struct for the binomial coefficient struct to handle different type of integers. More...
 
struct  binomial_coefficients_trait< 7 >
 Specialization of binomial_coefficients_trait for 128-bit integers. More...
 
struct  binomial_coefficients_trait< 8 >
 Specialization of binomial_coefficients_trait for 256-bit integers. More...
 
struct  binomial_table
 
class  bit_vector_il
 A bit vector which interleaves the original bit_vector with rank information. More...
 
struct  bits_impl
 A helper class for bitwise tricks on 64 bit words. More...
 
struct  bp_interval
 
class  bp_support_g
 A class that provides support for bit_vectors that represent a BP sequence. More...
 
class  bp_support_gg
 A class that provides support for bit_vectors that represent a BP sequence. More...
 
class  bp_support_sada
 A class that provides support for bit_vectors that represent a BP sequence. More...
 
class  buffered_char_queue
 
struct  bv_tag
 
class  bwt_of_csa_psi
 A wrapper for the bwt of a compressed suffix array that is based on the $\psi$ function. More...
 
class  bwt_of_csa_wt
 
class  byte_alphabet
 A simple space greedy representation for byte alphabets. More...
 
struct  byte_alphabet_tag
 
struct  byte_tree
 
struct  cache_config
 Helper class for construction process. More...
 
struct  construct_config_data
 
class  csa_bitcompressed
 A class for the uncompressed suffix array (SA). More...
 
struct  csa_member_tag
 
class  csa_sada
 A class for the Compressed Suffix Array (CSA) proposed by Sadakane for practical implementation. More...
 
struct  csa_tag
 
class  csa_wt
 A class for the Compressed Suffix Array (CSA) based on a Wavelet Tree (WT) of the Burrow Wheeler Transform of the original text. More...
 
class  cst_bfs_iterator
 A forward iterator for a breath first traversal of a tree. More...
 
class  cst_bottom_up_const_forward_iterator
 A forward iterator for a bottom up traversal of a suffix tree. More...
 
class  cst_dfs_const_forward_iterator
 An forward iterator for (compressed) suffix trees. More...
 
class  cst_fully
 A class for the Fully-Compressed Suffix Tree (FCST) proposed by Russo et al. More...
 
class  cst_node_child_proxy
 
class  cst_node_child_proxy_iterator
 
class  cst_sada
 A class for the Compressed Suffix Tree (CST) proposed by Sadakane. More...
 
class  cst_sct3
 A class for the Compressed Suffix Tree (CST) proposed by Ohlebusch and Gog. More...
 
struct  cst_tag
 
class  dac_vector
 A generic immutable space-saving vector class for unsigned integers. More...
 
struct  default_sentinel
 
struct  default_sentinel< t_csx, byte_alphabet_tag >
 
struct  default_sentinel< t_csx, int_alphabet_tag >
 
struct  enable_if_type
 
class  enc_vector
 A generic immutable space-saving vector class for unsigned integers. More...
 
struct  enc_vector_trait
 
struct  enc_vector_trait< 32 >
 
struct  enc_vector_trait< 64 >
 
struct  excess
 
struct  fast_cache
 
class  first_row_of_csa
 
struct  fuzzy_isa_sampling_support
 
struct  fuzzy_sa_sampling
 
struct  has_expand
 
struct  has_expand< t_wt, t_ret(t_args...)>
 
struct  has_id
 
struct  has_interval_symbols
 
struct  has_load
 
struct  has_node_type
 
struct  has_node_type< t_wt, typename void_< typename t_wt::node_type >::type >
 
struct  has_range_search_2d
 
struct  has_serialize
 
struct  has_symbols_wt
 
struct  huff_shape
 
class  hugepage_allocator
 
struct  hutu_shape
 
class  hyb_vector
 A hybrid-encoded compressed bitvector representation. More...
 
struct  index_tag
 
struct  index_tag< t_idx, typename enable_if_type< typename t_idx::index_category >::type >
 
class  int_alphabet
 A space-efficient representation for byte alphabets. More...
 
struct  int_alphabet_tag
 
struct  int_tree
 
struct  int_vec_category_trait
 
struct  int_vec_category_trait< 1 >
 
class  int_vector
 A generic vector class for integers of width $w\in [1..64]$. More...
 
class  int_vector_buffer
 
class  int_vector_const_iterator
 
class  int_vector_iterator
 
class  int_vector_iterator_base
 
class  int_vector_load_vbyte_wrapper
 
class  int_vector_load_vlen_wrapper
 
class  int_vector_load_wrapper
 
class  int_vector_mapper
 
class  int_vector_reference
 A proxy class that acts as a reference to an integer of length len bits in a int_vector. More...
 
class  int_vector_reference< bit_vector >
 
class  int_vector_serialize_min_overhead
 
class  int_vector_serialize_vbyte_wrapper
 
class  int_vector_serialize_vlen_wrapper
 
class  int_vector_serialize_wrapper
 
struct  int_vector_trait
 
struct  int_vector_trait< 16 >
 
struct  int_vector_trait< 32 >
 
struct  int_vector_trait< 64 >
 
struct  int_vector_trait< 8 >
 
class  inv_multi_perm_support
 Class inv_multi_perm_support adds access to the inverse of permutations. More...
 
class  inv_perm_support
 Class inv_perm_support adds access to the inverse of a permutation. More...
 
struct  is_alphabet
 
struct  is_alphabet< t_alphabet, typename enable_if_type< typename t_alphabet::alphabet_category >::type >
 
struct  is_enc_vec
 
struct  is_enc_vec< t_enc_vec, typename enable_if_type< typename t_enc_vec::enc_vec_type >::type >
 
class  isa_of_csa_psi
 
class  isa_of_csa_wt
 
struct  isa_sampling
 
struct  isa_sampling_tag
 
class  isfstream
 
struct  iv_tag
 
class  k2_treap
 A k^2-treap. More...
 
class  k2_tree
 A k^2-tree. More...
 
struct  key_bwt_trait_impl
 Helper classes to transform width=0 and width=8 to corresponding bwt key. More...
 
struct  key_bwt_trait_impl< 0, T >
 
struct  key_bwt_trait_impl< 8, T >
 
struct  key_text_trait_impl
 Helper classes to transform width=0 and width=8 to corresponding text key. More...
 
struct  key_text_trait_impl< 0, T >
 
struct  key_text_trait_impl< 8, T >
 
class  lcp_bitcompressed
 
class  lcp_byte
 A class for a simple compressed version of LCP information. More...
 
class  lcp_fully
 
struct  lcp_permuted_tag
 
struct  lcp_plain_tag
 
struct  lcp_support_sada
 Helper class which provides _lcp_support_sada the context of a CSA. More...
 
struct  lcp_support_tree
 Helper class which provides _lcp_support_tree the context of a CST. More...
 
struct  lcp_support_tree2
 Helper class which provides _lcp_support_tree2 the context of a CST. More...
 
struct  lcp_tag
 
struct  lcp_tree_and_lf_compressed_tag
 
struct  lcp_tree_compressed_tag
 
class  lcp_vlc
 
class  lcp_wt
 A class for the compressed version of lcp information of an suffix array. More...
 
struct  lf_tag
 
struct  libdivsufsort_config
 
struct  libdivsufsort_config< int32_t >
 
struct  libdivsufsort_config< int64_t >
 
class  louds_node
 A class for the node representation of louds_tree. More...
 
class  louds_tree
 A tree class based on the level order unary degree sequence (LOUDS) representation. More...
 
class  memory_manager
 
class  memory_monitor
 
struct  mm_alloc
 
struct  mm_block
 
struct  mm_event
 
class  mm_item
 
class  nearest_neighbour_dictionary
 Nearest neighbour dictionary for sparse uniform sets (described in Geary et al., A Simple Optimal Representation for Balanced Parentheses, CPM 2004). More...
 
class  nn_dict_dynamic
 A class for a dynamic bit vector which also supports the prev and next operations. More...
 
class  node_bv_container
 
class  node_seq_container
 
struct  nullstream
 
class  osfstream
 
struct  pc_node
 
class  plain_byte_alphabet
 Provides an alphabet mapping that implements an identity map (i.e. More...
 
class  psi_of_csa_wt
 
struct  psi_tag
 
class  ram_filebuf
 
struct  ramfs_storage
 
class  random_access_const_iterator
 Generic iterator for a random access container. More...
 
struct  random_access_container
 
struct  range_maximum_sct
 
struct  range_maximum_support_sada
 
struct  rank_result
 
struct  rank_result< 0 >
 
class  rank_support
 The base class of classes supporting rank_queries for a sdsl::bit_vector in constant time. More...
 
class  rank_support_hyb
 Rank_support for the hyb_vector class. More...
 
class  rank_support_il
 
class  rank_support_int
 The base class of classes supporting rank_queries for a sdsl::int_vector in constant time. More...
 
class  rank_support_int_scan
 A class supporting rank queries in linear time. More...
 
class  rank_support_int_v
 A rank structure proposed by Christopher Pockrandt. More...
 
class  rank_support_rrr
 
class  rank_support_rrr< t_b, 15, t_rac, t_k >
 rank_support for the specialized rrr_vector class of block size 15. More...
 
struct  rank_support_rrr_trait
 
struct  rank_support_rrr_trait< 0 >
 
class  rank_support_scan
 A class supporting rank queries in linear time. More...
 
class  rank_support_sd
 Rank data structure for sd_vector. More...
 
struct  rank_support_sd_trait
 
struct  rank_support_sd_trait< 0 >
 
struct  rank_support_trait
 
struct  rank_support_trait< 0, 1 >
 
struct  rank_support_trait< 00, 2 >
 
struct  rank_support_trait< 01, 2 >
 
struct  rank_support_trait< 1, 1 >
 
struct  rank_support_trait< 10, 2 >
 
struct  rank_support_trait< 11, 2 >
 
class  rank_support_v
 A rank structure proposed by Sebastiano Vigna. More...
 
class  rank_support_v5
 A class supporting rank queries in constant time. More...
 
class  rmq_succinct_sada
 A class to support range minimum or range maximum queries on a random access container. More...
 
class  rmq_succinct_sct
 A class to support range minimum or range maximum queries on a random access container. More...
 
class  rmq_support_sparse_table
 A class to support range minimum or range maximum queries on a random access container. More...
 
struct  rrr_helper
 Class to encode and decode binomial coefficients on the fly. More...
 
class  rrr_vector
 A. More...
 
class  rrr_vector< 15, t_rac, t_k >
 A specialization of the rrr_vector class for a block_size of 15. More...
 
struct  sa_bwt_sampling
 
struct  sa_order_sa_sampling
 
struct  sa_sampling_tag
 
struct  sampling_tag
 
struct  sampling_tag< t_sampling, typename enable_if_type< typename t_sampling::sampling_category >::type >
 
class  sd_vector
 A bit vector which compresses very sparse populated bit vectors by. More...
 
class  sd_vector_builder
 Class for in-place construction of sd_vector from a strictly increasing sequence. More...
 
class  select_0_support_sd
 Select_0 data structure for sd_vector. More...
 
class  select_support
 The base class of classes supporting select queries for a sdsl::bit_vector in constant time. More...
 
class  select_support_hyb
 Select support for the hyb_vector class. More...
 
class  select_support_il
 
class  select_support_mcl
 A class supporting constant time select queries. More...
 
class  select_support_rrr
 
class  select_support_rrr< t_b, 15, t_rac, t_k >
 Select support for the specialized rrr_vector class of block size 15. More...
 
class  select_support_scan
 A class supporting linear time select queries. More...
 
class  select_support_sd
 Select data structure for sd_vector. More...
 
struct  select_support_sd_trait
 
struct  select_support_sd_trait< 0, t_sd_vec >
 
struct  select_support_trait
 
struct  select_support_trait< 0, 1 >
 
struct  select_support_trait< 00, 2 >
 
struct  select_support_trait< 01, 2 >
 
struct  select_support_trait< 1, 1 >
 
struct  select_support_trait< 10, 2 >
 
struct  select_support_trait< 11, 2 >
 
class  sorted_int_stack
 A stack class which can contain integers in strictly increasing order. More...
 
class  sorted_multi_stack_support
 Stack which contains elements from [0..n] in sorted order. Duplicates are possible. More...
 
class  sorted_stack_support
 A stack which contains strictly increasing numbers in the range from $0$ to $n$. More...
 
class  spin_lock
 
class  structure_tree
 
class  structure_tree_node
 
class  succinct_byte_alphabet
 A space-efficient representation for byte alphabets. More...
 
class  temp_file_buffer
 
class  text_of_csa
 
struct  text_order_isa_sampling_support
 
struct  text_order_sa_sampling
 
struct  track_allocator
 
struct  tracker_storage
 
class  traverse_csa_psi
 
struct  traverse_csa_psi_trait
 
struct  traverse_csa_psi_trait< t_csa, false >
 
class  traverse_csa_saisa
 A helper class for the $\Psi$ function for (compressed) suffix arrays which provide also the inverse suffix array values (like sdsl::csa_bitcompressed). More...
 
struct  traverse_csa_saisa_trait
 
struct  traverse_csa_saisa_trait< t_csa, false >
 
class  traverse_csa_wt
 A wrapper class for the $\Psi$ and LF function for (compressed) suffix arrays that are based on a wavelet tree (like sdsl::csa_wt). More...
 
struct  traverse_csa_wt_traits
 
struct  traverse_csa_wt_traits< t_csa, false >
 
class  uint128_t
 
class  uint256_t
 
class  vlc_vector
 A generic immutable space-saving vector class for unsigned integers. More...
 
struct  vlc_vector_trait
 
struct  vlc_vector_trait< 32 >
 
struct  void_
 
class  wm_int
 A wavelet tree class for integer sequences. More...
 
class  write_out_mapper
 
struct  wt_alphabet_trait
 
struct  wt_alphabet_trait< t_wt, typename enable_if_type< typename t_wt::alphabet_category >::type >
 
class  wt_ap
 A wavelet tree class for integer sequences. More...
 
class  wt_epr
 An EPR-dictionary based wavelet. More...
 
class  wt_gmr
 A wavelet tree class for integer sequences. More...
 
class  wt_gmr_rs
 A wavelet tree class for integer sequences. More...
 
class  wt_int
 A wavelet tree class for integer sequences. More...
 
class  wt_pc
 A prefix code-shaped wavelet. More...
 
class  wt_rlmn
 A Wavelet Tree class for byte sequences. More...
 
struct  wt_rlmn_trait
 
struct  wt_rlmn_trait< byte_alphabet_tag >
 
struct  wt_tag
 

Typedefs

using bits = bits_impl<>
 
typedef uint64_t int_vector_size_type
 
typedef std::map< std::string, std::string > tMSS
 
template<uint8_t width>
using key_text_trait = key_text_trait_impl< width, void >
 
template<uint8_t width>
using key_bwt_trait = key_bwt_trait_impl< width, void >
 
typedef std::list< int_vector<>::size_type > tLI
 
typedef std::vector< int_vector<>::size_type > tVI
 
template<typename saidx_t >
using trbudget_t = _trbudget_t< saidx_t >
 
typedef uint64_t std_size_type_for_int_vector
 
typedef int_vector< 1 > bit_vector
 bit_vector is a specialization of the int_vector. More...
 
template<std::ios_base::openmode t_mode = std::ios_base::out | std::ios_base::in>
using bit_vector_mapper = int_vector_mapper< 1, t_mode >
 
template<uint8_t t_width = 0>
using read_only_mapper = const int_vector_mapper< t_width, std::ios_base::in >
 
template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
using lcp_dac = lcp_vlc< dac_vector< t_b, t_rank > >
 A class for the compressed version of LCP information of an suffix array. More...
 
typedef struct sdsl::mm_block mm_block_t
 
typedef struct sdsl::bfoot mm_block_foot_t
 
template<class t_rac = int_vector<>>
using range_maximum_support_sparse_table = rmq_support_sparse_table< t_rac, false >
 
using binomial15 = binomial15_impl<>
 
template<class t_wt = wt_int<>, uint32_t t_dens = 32, uint32_t t_inv_dens = 64, class t_sa_sample_strat = sa_order_sa_sampling<>, class t_isa_sample_strat = isa_sampling<>>
using csa_wt_int = csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa_sample_strat, int_alphabet<> >
 Typedef for convenient usage of std integer alphabet strategy. More...
 
template<class t_enc_vec = enc_vector<>, uint32_t t_dens = 32, uint32_t t_inv_dens = 64, class t_sa_sample_strat = sa_order_sa_sampling<>, class t_isa_sample_strat = isa_sampling<>>
using csa_sada_int = csa_sada< t_enc_vec, t_dens, t_inv_dens, t_sa_sample_strat, t_isa_sample_strat, int_alphabet<> >
 
template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
using wt_hutu_int = wt_pc< hutu_shape, t_bitvector, t_rank, t_select, t_select_zero, int_tree<> >
 
template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
using wt_huff_int = wt_pc< huff_shape, t_bitvector, t_rank, t_select, t_select_zero, int_tree<> >
 
template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select_one = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
using wt_blcd_int = wt_pc< balanced_shape, t_bitvector, t_rank, t_select_one, t_select_zero, int_tree<> >
 
template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select_one = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
using wt_blcd = wt_pc< balanced_shape, t_bitvector, t_rank, t_select_one, t_select_zero, t_tree_strat >
 A balanced wavelet tree. More...
 
typedef std::array< int_vector<>::size_type, 2 > range_type
 
typedef std::vector< range_typerange_vec_type
 
template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
using wt_huff = wt_pc< huff_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >
 A Huffman-shaped wavelet tree. More...
 
template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
using wt_hutu = wt_pc< hutu_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >
 A Hu-Tucker-shaped wavelet tree. More...
 

Enumerations

enum  format_type { JSON_FORMAT , R_FORMAT , HTML_FORMAT }
 
enum  byte_sa_algo_type { LIBDIVSUFSORT , SE_SAIS }
 

Functions

template<class T >
constexpr bool power_of_two (T x)
 
bit_vector calculate_pioneers_bitmap (const bit_vector &bp, uint64_t block_size)
 Calculate pioneers as defined in the paper of Geary et al. (CPM 2004) More...
 
bit_vector calculate_pioneers_bitmap_succinct (const bit_vector &bp, uint64_t block_size)
 Space-efficient version of calculate_pioneers_bitmap. More...
 
template<class int_vector >
void calculate_matches (const bit_vector &bp, int_vector &matches)
 find_open/find_close for closing/opening parentheses. More...
 
template<class int_vector >
void calculate_enclose (const bit_vector &bp, int_vector &enclose)
 Calculates enclose answers for a balanced parentheses sequence. More...
 
uint64_t near_find_close (const bit_vector &bp, const uint64_t i, const uint64_t block_size)
 
uint64_t near_find_closing (const bit_vector &bp, uint64_t i, uint64_t closings, const uint64_t block_size)
 
uint64_t near_fwd_excess (const bit_vector &bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
 
uint64_t near_rmq (const bit_vector &bp, uint64_t l, uint64_t r, bit_vector::difference_type &min_rel_ex)
 Calculate the position with minimal excess value in the interval [l..r]. More...
 
uint64_t near_bwd_excess (const bit_vector &bp, uint64_t i, bit_vector::difference_type rel, const uint64_t block_size)
 Near backward excess. More...
 
uint64_t near_find_open (const bit_vector &bp, uint64_t i, const uint64_t block_size)
 
uint64_t near_find_opening (const bit_vector &bp, uint64_t i, const uint64_t openings, const uint64_t block_size)
 
uint64_t near_enclose (const bit_vector &bp, uint64_t i, const uint64_t block_size)
 Find the opening parenthesis of the enclosing pair if this parenthesis is near. More...
 
uint64_t near_rmq_open (const bit_vector &bp, const uint64_t begin, const uint64_t end)
 
template<class int_vector >
bool contains_no_zero_symbol (const int_vector &text, const std::string &file)
 
template<class int_vector >
void append_zero_symbol (int_vector &text)
 
template<class t_index >
void construct (t_index &idx, std::string file, uint8_t num_bytes=0, bool move_input=false)
 
template<class t_index , class t_data >
void construct_im (t_index &idx, t_data &&data, uint8_t num_bytes=0)
 
template<class t_index >
void construct (t_index &idx, const std::string &file, cache_config &config, uint8_t num_bytes=0)
 Constructs an index object of type t_index for a text stored on disk. More...
 
template<class t_index >
void construct (t_index &idx, const std::string &file, cache_config &config, uint8_t num_bytes, wt_tag)
 
template<class t_index >
void construct (t_index &idx, const std::string &file, cache_config &config, uint8_t num_bytes, csa_tag)
 
template<class t_index , uint8_t t_width>
void construct (t_index &idx, const std::string &file, cache_config &config, uint8_t num_bytes, lcp_tag)
 
template<class t_index >
void construct (t_index &idx, const std::string &file, cache_config &config, uint8_t num_bytes, lcp_tag tag)
 
template<class t_index >
void construct (t_index &idx, const std::string &file, cache_config &config, uint8_t num_bytes, cst_tag)
 
template<uint8_t t_width>
void construct_bwt (cache_config &config)
 Constructs the Burrows and Wheeler Transform (BWT) from text over byte- or integer-alphabet and suffix array. More...
 
construct_config_dataconstruct_config ()
 
void construct_isa (cache_config &config)
 
template<uint8_t t_width>
void construct_lcp_kasai (cache_config &config)
 Construct the LCP array for text over byte- or integer-alphabet. More...
 
template<uint8_t t_width>
void construct_lcp_PHI (cache_config &config)
 Construct the LCP array for text over byte- or integer-alphabet. More...
 
void construct_lcp_semi_extern_PHI (cache_config &config)
 Construct the LCP array (only for byte strings) More...
 
void construct_lcp_go (cache_config &config)
 Construct the LCP array (only for byte strings) More...
 
void construct_lcp_goPHI (cache_config &config)
 Construct the LCP array (only for byte strings) More...
 
template<typename t_wt = wt_huff<bit_vector, rank_support_v<>, select_support_scan<1>, select_support_scan<0>>>
void construct_lcp_bwt_based (cache_config &config)
 Construct the LCP array out of the BWT (only for byte strings) More...
 
template<typename t_wt = wt_huff<bit_vector, rank_support_v<>, select_support_scan<1>, select_support_scan<0>>>
void construct_lcp_bwt_based2 (cache_config &config)
 Construct the LCP array out of the BWT (only for byte strings) More...
 
void insert_lcp_values (int_vector<> &partial_lcp, bit_vector &index_done, std::string lcp_file, uint64_t max_lcp_value, uint64_t lcp_value_offset)
 Merges a partial LCP array into the LCP array on disk. More...
 
template<class tWT >
void create_C_array (std::vector< uint64_t > &C, const tWT &wt)
 
template<class size_type_class >
void push_front_m_index (size_type_class i, uint8_t c, tLI(&m_list)[256], uint8_t(&m_chars)[256], size_type_class &m_char_count)
 
template<class size_type_class >
void push_back_m_index (size_type_class i, uint8_t c, tLI(&m_list)[256], uint8_t(&m_chars)[256], size_type_class &m_char_count)
 
void construct_sa_se (cache_config &config)
 Constructs the Suffix Array (SA) from text over byte-alphabet. More...
 
template<uint8_t t_width>
void construct_sa (cache_config &config)
 Constructs the Suffix Array (SA) from text over byte- or integer-alphabet. More...
 
template<class int_vector_type >
uint64_t _get_next_lms_position (int_vector_type &text, uint64_t i)
 
void _construct_sa_IS (int_vector<> &text, int_vector<> &sa, std::string &filename_sa, size_t n, size_t text_offset, size_t sigma, uint64_t recursion)
 
template<class int_vector_type >
void _construct_sa_se (int_vector_type &text, std::string filename_sa, uint64_t sigma, uint64_t recursion)
 
template<uint8_t int_width>
constexpr const char * key_text ()
 
template<uint8_t int_width>
constexpr const char * key_bwt ()
 
template<>
constexpr const char * key_text< 8 > ()
 
template<>
constexpr const char * key_bwt< 8 > ()
 
template<typename bit_vector_type , typename size_type >
void init_char_bitvector (bit_vector_type &char_bv, const std::map< size_type, size_type > &D)
 
template<typename t_hi_bit_vector , typename t_select_1 , typename t_select_0 , typename size_type >
void init_char_bitvector (sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > &char_bv, const std::map< size_type, size_type > &D)
 
template<class t_int >
std::ostream & operator<< (std::ostream &os, const bp_interval< t_int > &interval)
 
int32_t ss_ilg (int32_t n)
 
int32_t ss_ilg (int64_t n)
 
template<typename saidx_t >
saidx_t ss_isqrt (saidx_t x)
 
template<typename saidx_t >
int32_t ss_compare (const uint8_t *T, const saidx_t *p1, const saidx_t *p2, saidx_t depth)
 
template<typename saidx_t >
void ss_insertionsort (const uint8_t *T, const saidx_t *PA, saidx_t *first, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void ss_fixdown (const uint8_t *Td, const saidx_t *PA, saidx_t *SA, saidx_t i, saidx_t size)
 
template<typename saidx_t >
void ss_heapsort (const uint8_t *Td, const saidx_t *PA, saidx_t *SA, saidx_t size)
 
template<typename saidx_t >
saidx_t * ss_median3 (const uint8_t *Td, const saidx_t *PA, saidx_t *v1, saidx_t *v2, saidx_t *v3)
 
template<typename saidx_t >
saidx_t * ss_median5 (const uint8_t *Td, const saidx_t *PA, saidx_t *v1, saidx_t *v2, saidx_t *v3, saidx_t *v4, saidx_t *v5)
 
template<typename saidx_t >
saidx_t * ss_pivot (const uint8_t *Td, const saidx_t *PA, saidx_t *first, saidx_t *last)
 
template<typename saidx_t >
saidx_t * ss_partition (const saidx_t *PA, saidx_t *first, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void ss_mintrosort (const uint8_t *T, const saidx_t *PA, saidx_t *first, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void ss_blockswap (saidx_t *a, saidx_t *b, saidx_t n)
 
template<typename saidx_t >
void ss_rotate (saidx_t *first, saidx_t *middle, saidx_t *last)
 
template<typename saidx_t >
void ss_inplacemerge (const uint8_t *T, const saidx_t *PA, saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void ss_mergeforward (const uint8_t *T, const saidx_t *PA, saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t *buf, saidx_t depth)
 
template<typename saidx_t >
void ss_mergebackward (const uint8_t *T, const saidx_t *PA, saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t *buf, saidx_t depth)
 
template<typename saidx_t >
void ss_swapmerge (const uint8_t *T, const saidx_t *PA, saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t *buf, saidx_t bufsize, saidx_t depth)
 
template<typename saidx_t >
void sssort (const uint8_t *T, const saidx_t *PA, saidx_t *first, saidx_t *last, saidx_t *buf, saidx_t bufsize, saidx_t depth, saidx_t n, int32_t lastsuffix)
 
int32_t tr_ilg (int32_t n)
 
int32_t tr_ilg (int64_t n)
 
template<typename saidx_t >
void tr_insertionsort (const saidx_t *ISAd, saidx_t *first, saidx_t *last)
 
template<typename saidx_t >
void tr_fixdown (const saidx_t *ISAd, saidx_t *SA, saidx_t i, saidx_t size)
 
template<typename saidx_t >
void tr_heapsort (const saidx_t *ISAd, saidx_t *SA, saidx_t size)
 
template<typename saidx_t >
saidx_t * tr_median3 (const saidx_t *ISAd, saidx_t *v1, saidx_t *v2, saidx_t *v3)
 
template<typename saidx_t >
saidx_t * tr_median5 (const saidx_t *ISAd, saidx_t *v1, saidx_t *v2, saidx_t *v3, saidx_t *v4, saidx_t *v5)
 
template<typename saidx_t >
saidx_t * tr_pivot (const saidx_t *ISAd, saidx_t *first, saidx_t *last)
 
template<typename saidx_t >
void trbudget_init (trbudget_t< saidx_t > *budget, saidx_t chance, saidx_t incval)
 
template<typename saidx_t >
int32_t trbudget_check (trbudget_t< saidx_t > *budget, saidx_t size)
 
template<typename saidx_t >
void tr_partition (const saidx_t *ISAd, saidx_t *first, saidx_t *middle, saidx_t *last, saidx_t **pa, saidx_t **pb, saidx_t v)
 
template<typename saidx_t >
void tr_copy (saidx_t *ISA, const saidx_t *SA, saidx_t *first, saidx_t *a, saidx_t *b, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void tr_partialcopy (saidx_t *ISA, const saidx_t *SA, saidx_t *first, saidx_t *a, saidx_t *b, saidx_t *last, saidx_t depth)
 
template<typename saidx_t >
void tr_introsort (saidx_t *ISA, const saidx_t *ISAd, saidx_t *SA, saidx_t *first, saidx_t *last, trbudget_t< saidx_t > *budget)
 
template<typename saidx_t >
void trsort (saidx_t *ISA, saidx_t *SA, saidx_t n, saidx_t depth)
 
template<typename saidx_t >
saidx_t sort_typeBstar (const uint8_t *T, saidx_t *SA, saidx_t *bucket_A, saidx_t *bucket_B, saidx_t n)
 
template<typename saidx_t >
void construct_SA (const uint8_t *T, saidx_t *SA, saidx_t *bucket_A, saidx_t *bucket_B, saidx_t n, saidx_t m)
 
template<typename saidx_t >
saidx_t construct_BWT (const uint8_t *T, saidx_t *SA, saidx_t *bucket_A, saidx_t *bucket_B, saidx_t n, saidx_t m)
 
template<typename saidx_t >
int32_t divsufsort (const uint8_t *T, saidx_t *SA, saidx_t n)
 
int32_t divsufsort64 (const uint8_t *T, int64_t *SA, int64_t n)
 
template<typename saidx_t >
int _compare (const uint8_t *T, saidx_t Tsize, const uint8_t *P, saidx_t Psize, saidx_t suf, saidx_t *match)
 
template<class t_int_vector >
void swap (int_vector_reference< t_int_vector > x, int_vector_reference< t_int_vector > y) noexcept
 
template<class t_int_vector >
void swap (typename int_vector_reference< t_int_vector >::value_type &x, int_vector_reference< t_int_vector > y) noexcept
 
template<class t_int_vector >
void swap (int_vector_reference< t_int_vector > x, typename int_vector_reference< t_int_vector >::value_type &y) noexcept
 
template<>
void swap (int_vector_reference< bit_vector > x, int_vector_reference< bit_vector > y) noexcept
 
template<>
void swap (bool &x, int_vector_reference< bit_vector > y) noexcept
 
template<>
void swap (int_vector_reference< bit_vector > x, bool &y) noexcept
 
template<class t_int_vector >
int_vector_iterator< t_int_vector > operator+ (typename int_vector_iterator< t_int_vector >::difference_type n, const int_vector_iterator< t_int_vector > &it)
 
template<class t_int_vector >
int_vector_const_iterator< t_int_vector >::difference_type operator- (const int_vector_const_iterator< t_int_vector > &x, const int_vector_const_iterator< t_int_vector > &y)
 
template<class t_int_vector >
int_vector_const_iterator< t_int_vector > operator+ (typename int_vector_const_iterator< t_int_vector >::difference_type n, const int_vector_const_iterator< t_int_vector > &it)
 
template<class t_bv >
std::enable_if< std::is_same< typenamet_bv::index_category, bv_tag >::value, std::ostream & >::type operator<< (std::ostream &os, const t_bv &bv)
 
template<uint8_t t_width>
void swap (int_vector< t_width > &v1, int_vector< t_width > &v2) noexcept
 
int remove (const std::string &file)
 Remove a file. More...
 
template<typename T >
void load_vector (std::vector< T > &vec, std::istream &in)
 Load all elements of a vector from a input stream. More...
 
template<typename T >
uint64_t serialize_vector (const std::vector< T > &vec, std::ostream &out, sdsl::structure_tree_node *v, std::string name)
 Serialize each element of an std::vector. More...
 
template<typename T >
size_t write_member (const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
 
template<>
size_t write_member< std::string > (const std::string &t, std::ostream &out, sdsl::structure_tree_node *v, std::string name)
 
template<typename T >
void read_member (T &t, std::istream &in)
 
template<>
void read_member< std::string > (std::string &t, std::istream &in)
 
template<typename X >
std::enable_if< has_serialize< X >::value, typenameX::size_type >::type serialize (const X &x, std::ostream &out, structure_tree_node *v=nullptr, std::string name="")
 
template<typename X >
std::enable_if< std::is_standard_layout< X >::value &&std::is_trivial< X >::value, uint64_t >::type serialize (const X &x, std::ostream &out, structure_tree_node *v=nullptr, std::string name="")
 
template<typename X >
uint64_t serialize (const std::vector< X > &x, std::ostream &out, structure_tree_node *v=nullptr, std::string name="")
 
template<typename X >
std::enable_if< has_load< X >::value, void >::type load (X &x, std::istream &in)
 
template<typename X >
std::enable_if< std::is_standard_layout< X >::value &&std::is_trivial< X >::value, void >::type load (X &x, std::istream &in)
 
template<typename X >
void load (std::vector< X > &x, std::istream &in)
 
template<typename T >
bool load_from_file (T &v, const std::string &file)
 Load sdsl-object v from a file. More...
 
template<typename t_int_vec >
bool load_vector_from_file (t_int_vec &v, const std::string &file, uint8_t num_bytes=1, uint8_t max_int_width=64)
 from disk. More...
 
template<typename T >
bool store_to_file (const T &v, const std::string &file)
 Store a data structure to a file. More...
 
bool store_to_file (const char *v, const std::string &file)
 Specialization of store_to_file for a char array. More...
 
template<uint8_t t_width>
bool store_to_file (const int_vector< t_width > &v, const std::string &file)
 Specialization of store_to_file for int_vector. More...
 
template<typename int_type , typename t_int_vec >
bool store_to_plain_array (t_int_vec &v, const std::string &file)
 Store an int_vector as plain int_type array to disk. More...
 
template<typename T >
size_t serialize_empty_object (std::ostream &, structure_tree_node *v=nullptr, std::string name="", const T *t=nullptr)
 
template<typename T >
T::size_type size_in_bytes (const T &t)
 Get the size of a data structure in bytes. More...
 
template<typename T >
double size_in_mega_bytes (const T &t)
 Get the size of a data structure in mega bytes (MiB). More...
 
template<format_type F, typename X >
void write_structure (const X &x, std::ostream &out)
 
template<format_type F, typename X >
void write_structure (const X &x, std::string file)
 
template<format_type F, typename... Xs>
void write_structure (std::ostream &out, Xs... xs)
 
template<typename X , typename... Xs>
void _write_structure (std::unique_ptr< structure_tree_node > &st_node, X x, Xs... xs)
 
void _write_structure (std::unique_ptr< structure_tree_node > &)
 
uint64_t _parse_number (std::string::const_iterator &c, const std::string::const_iterator &end)
 Internal function used by csXprintf. More...
 
template<typename t_csa >
const t_csa & _idx_csa (const t_csa &t, csa_tag)
 Internal function used by csXprintf. More...
 
template<typename t_cst >
const t_cst::csa_type & _idx_csa (const t_cst &t, cst_tag)
 Internal function used by csXprintf. More...
 
template<typename t_csa >
std::string _idx_lcp_val (const t_csa &, uint64_t, uint64_t, csa_tag)
 Internal function used by csXprintf. More...
 
template<typename t_cst >
std::string _idx_lcp_val (const t_cst &t, uint64_t i, uint64_t w, cst_tag)
 Internal function used by csXprintf. More...
 
template<typename t_idx >
void csXprintf (std::ostream &out, const std::string &format, const t_idx &idx, char sentinel=default_sentinel< t_idx >::value)
 Prints members of CSAs and CSTs. More...
 
std::string cache_file_name (const std::string &key, const cache_config &config)
 Returns the file name of the resource. More...
 
template<typename T >
std::string cache_file_name (const std::string &key, const cache_config &config)
 Returns the file name of the resource. More...
 
void register_cache_file (const std::string &key, cache_config &config)
 Register the existing resource specified by the key to the cache. More...
 
bool cache_file_exists (const std::string &key, const cache_config &config)
 Checks if the resource specified by the key exists in the cache. More...
 
template<typename T >
bool cache_file_exists (const std::string &key, const cache_config &config)
 Checks if the resource specified by the key and type exists in the cache. More...
 
std::string tmp_file (const cache_config &config, std::string name_part="")
 Returns a name for a temporary file. I.e. the name was not used before. More...
 
std::string tmp_file (const std::string &filename, std::string name_part="")
 Returns a name for a temporary file. I.e. the name was not used before. More...
 
template<typename T >
bool load_from_cache (T &v, const std::string &key, const cache_config &config, bool add_type_hash=false)
 
template<typename T >
bool store_to_cache (const T &v, const std::string &key, cache_config &config, bool add_type_hash=false)
 Stores the object v as a resource in the cache. More...
 
template<typename T >
bool remove_from_cache (const std::string &key, cache_config &config, bool add_type_hash=false)
 
template<typename T >
void add_hash (const T &t, std::ostream &out)
 
template<typename T >
bool store_to_checked_file (const T &t, const std::string &file)
 
bool store_to_checked_file (const char *v, const std::string &file)
 
bool store_to_file (const std::string &v, const std::string &file)
 
template<uint8_t t_width>
bool store_to_checked_file (const int_vector< t_width > &v, const std::string &file)
 
template<typename T >
bool load_from_checked_file (T &v, const std::string &file)
 
template<typename t_iv >
std::enable_if< std::is_same< typenamet_iv::index_category, iv_tag >::valueorstd::is_same< typenamet_iv::index_category, csa_tag >::valueorstd::is_same< typenamet_iv::index_category, lcp_tag >::value, std::ostream & >::type operator<< (std::ostream &os, const t_iv &v)
 
template<typename t_iv >
std::enable_if< std::is_same< typenamet_iv::index_category, wt_tag >::value, std::ostream & >::type operator<< (std::ostream &os, const t_iv &v)
 
template<typename t_int >
std::enable_if< std::is_integral< t_int >::value, std::ostream & >::type operator<< (std::ostream &os, const std::vector< t_int > &v)
 
template<typename t_iv >
std::enable_if< std::is_same< typenamet_iv::category, csa_member_tag >::value, std::ostream & >::type operator<< (std::ostream &os, const t_iv &v)
 
template<class t_rac >
random_access_const_iterator< t_rac >::difference_type operator- (const random_access_const_iterator< t_rac > &x, const random_access_const_iterator< t_rac > &y)
 
template<class t_rac >
random_access_const_iterator< t_rac > operator+ (typename random_access_const_iterator< t_rac >::difference_type n, const random_access_const_iterator< t_rac > &it)
 
template<typename t_k2_treap >
k2_treap_ns::top_k_iterator< t_k2_treap > top_k (const t_k2_treap &t, k2_treap_ns::point_type p1, k2_treap_ns::point_type p2)
 Get iterator for all heaviest points in rectangle (p1,p2) in decreasing order. More...
 
template<typename t_k2_treap >
k2_treap_ns::range_iterator< t_k2_treap > range_3d (const t_k2_treap &t, k2_treap_ns::point_type p1, k2_treap_ns::point_type p2, k2_treap_ns::range_type range)
 Get iterator for all points in rectangle (p1,p2) with weights in range. More...
 
template<typename t_k2_treap >
uint64_t __count (const t_k2_treap &, typename t_k2_treap::node_type)
 
template<typename t_k2_treap >
uint64_t _count (const t_k2_treap &, k2_treap_ns::point_type, k2_treap_ns::point_type, typename t_k2_treap::node_type)
 
template<typename t_k2_treap >
uint64_t count (const t_k2_treap &treap, k2_treap_ns::point_type p1, k2_treap_ns::point_type p2)
 Count how many points are in the rectangle (p1,p2) More...
 
template<uint8_t t_k, typename t_bv , typename t_rank , typename t_max_vec >
void construct (k2_treap< t_k, t_bv, t_rank, t_max_vec > &idx, std::string file, cache_config &config)
 Specialized version of method ,,construct'' for k2_treaps. More...
 
template<uint8_t t_k, typename t_bv , typename t_rank , typename t_max_vec >
void construct_im (k2_treap< t_k, t_bv, t_rank, t_max_vec > &idx, std::vector< std::array< uint64_t, 3 > > data)
 Specialized version of method ,,construct_im'' for k2_treaps. More...
 
template<class t_lcp , class t_cst >
void construct_lcp (t_lcp &lcp, const t_cst &cst, cache_config &config)
 
template<class t_lcp , class t_cst >
void construct_lcp (t_lcp &lcp, const t_cst &, cache_config &config, lcp_plain_tag)
 
template<class t_lcp , class t_cst >
void construct_lcp (t_lcp &lcp, const t_cst &cst, cache_config &config, lcp_permuted_tag)
 
template<class t_lcp , class t_cst >
void construct_lcp (t_lcp &lcp, const t_cst &cst, cache_config &config, lcp_tree_compressed_tag)
 
template<class t_lcp , class t_cst >
void construct_lcp (t_lcp &lcp, const t_cst &cst, cache_config &config, lcp_tree_and_lf_compressed_tag)
 
template<class t_lcp , class t_cst >
void copy_lcp (t_lcp &lcp, const t_lcp &lcp_c, const t_cst &cst)
 
template<class t_lcp , class t_cst >
void copy_lcp (t_lcp &lcp, const t_lcp &lcp_c, const t_cst &, lcp_plain_tag)
 
template<class t_lcp , class t_cst >
void copy_lcp (t_lcp &lcp, const t_lcp &lcp_c, const t_cst &cst, lcp_permuted_tag)
 
template<class t_lcp , class t_cst >
void copy_lcp (t_lcp &lcp, const t_lcp &lcp_c, const t_cst &cst, lcp_tree_compressed_tag)
 
template<class t_lcp , class t_cst >
void copy_lcp (t_lcp &lcp, const t_lcp &lcp_c, const t_cst &cst, lcp_tree_and_lf_compressed_tag)
 
template<class t_lcp , class t_cst >
void move_lcp (t_lcp &&lcp, t_lcp &&lcp_c, const t_cst &cst)
 
template<class t_lcp , class t_cst >
void move_lcp (t_lcp &&lcp, t_lcp &&lcp_c, const t_cst &, lcp_plain_tag)
 
template<class t_lcp , class t_cst >
void move_lcp (t_lcp &&lcp, t_lcp &&lcp_c, const t_cst &cst, lcp_permuted_tag)
 
template<class t_lcp , class t_cst >
void move_lcp (t_lcp &&lcp, t_lcp &&lcp_c, const t_cst &cst, lcp_tree_compressed_tag)
 
template<class t_lcp , class t_cst >
void move_lcp (t_lcp &&lcp, t_lcp &&lcp_c, const t_cst &cst, lcp_tree_and_lf_compressed_tag)
 
template<class t_lcp , class t_cst >
void load_lcp (t_lcp &lcp, std::istream &in, const t_cst &cst)
 
template<class t_lcp , class t_cst >
void load_lcp (t_lcp &lcp, std::istream &in, const t_cst &, lcp_plain_tag)
 
template<class t_lcp , class t_cst >
void load_lcp (t_lcp &lcp, std::istream &in, const t_cst &cst, lcp_permuted_tag)
 
template<class t_lcp , class t_cst >
void load_lcp (t_lcp &lcp, std::istream &in, const t_cst &cst, lcp_tree_compressed_tag)
 
template<class t_lcp , class t_cst >
void load_lcp (t_lcp &lcp, std::istream &in, const t_cst &cst, lcp_tree_and_lf_compressed_tag)
 
template<class t_lcp , class t_cst >
void set_lcp_pointer (t_lcp &lcp, const t_cst &cst)
 
template<class t_lcp , class t_cst >
void set_lcp_pointer (t_lcp &, const t_cst &, lcp_plain_tag)
 
template<class t_lcp , class t_cst >
void set_lcp_pointer (t_lcp &lcp, const t_cst &cst, lcp_permuted_tag)
 
template<class t_lcp , class t_cst >
void set_lcp_pointer (t_lcp &lcp, const t_cst &cst, lcp_tree_compressed_tag)
 
template<class t_lcp , class t_cst >
void set_lcp_pointer (t_lcp &lcp, const t_cst &cst, lcp_tree_and_lf_compressed_tag)
 
void construct_first_child_lcp (int_vector_buffer<> &lcp_buf, int_vector<> &fc_lcp)
 
template<uint32_t t_dens, uint8_t t_bwt_width>
void construct_first_child_and_lf_lcp (int_vector_buffer<> &, int_vector_buffer< t_bwt_width > &, const std::string &, const std::string &, int_vector<> &)
 
std::ostream & operator<< (std::ostream &os, const louds_node &v)
 
void output_event_json (std::ostream &out, const mm_event &ev, const tracker_storage &m)
 
template<>
void write_mem_log< JSON_FORMAT > (std::ostream &out, const tracker_storage &m)
 
std::string create_mem_html_header ()
 
std::string create_mem_js_body (const std::string &jsonObject)
 
template<>
void write_mem_log< HTML_FORMAT > (std::ostream &out, const tracker_storage &m)
 
mm_block_tblock_cur (void *ptr)
 
mm_block_tblock_prev (mm_block_t *cur_bptr, mm_block_t *first)
 
mm_block_tblock_next (mm_block_t *cur_bptr, uint8_t *top)
 
size_t block_size (void *ptr)
 
bool block_isfree (mm_block_t *ptr)
 
bool block_nextfree (mm_block_t *ptr, uint8_t *top)
 
bool block_prevfree (mm_block_t *ptr, mm_block_t *begin)
 
void foot_update (mm_block_t *ptr, size_t size)
 
void block_update (mm_block_t *ptr, size_t size)
 
void * block_data (mm_block_t *ptr)
 
size_t block_getdatasize (mm_block_t *ptr)
 
void block_markfree (mm_block_t *ptr)
 
void block_markused (mm_block_t *ptr)
 
void memory_monitor_record (int64_t)
 
template<typename T , typename U >
bool operator== (const track_allocator< T > &, const track_allocator< U > &)
 
template<typename T , typename U >
bool operator!= (const track_allocator< T > &a, const track_allocator< U > &b)
 
template<format_type F>
void write_mem_log (std::ostream &out, const tracker_storage &m)
 
bool is_ram_file (const std::string &file)
 Determines if the given file is a RAM-file. More...
 
bool is_ram_file (const int fd)
 Determines if the given file is a RAM-file. More...
 
std::string ram_file_name (const std::string &file)
 Returns the corresponding RAM-file name for file. More...
 
std::string disk_file_name (const std::string &file)
 Returns for a RAM-file the corresponding disk file name. More...
 
int rename (const std::string &old_filename, const std::string &new_filename)
 Rename a file. More...
 
constexpr size_t floor_log2 (size_t const n)
 
constexpr size_t ceil_log2 (size_t const n)
 
void output_tab (std::ostream &out, size_t level)
 
template<format_type F>
void write_structure_tree (const structure_tree_node *v, std::ostream &out, size_t level=0)
 
template<>
void write_structure_tree< JSON_FORMAT > (const structure_tree_node *v, std::ostream &out, size_t level)
 
std::string create_html_header (const char *file_name)
 
std::string create_js_body (const std::string &jsonsize)
 
template<>
void write_structure_tree< HTML_FORMAT > (const structure_tree_node *v, std::ostream &out, SDSL_UNUSED size_t level)
 
template<class t_csa , class t_pat_iter >
t_csa::size_type forward_search (const t_csa &csa, typename t_csa::size_type l, typename t_csa::size_type r, t_pat_iter begin, t_pat_iter end, typename t_csa::size_type &l_res, typename t_csa::size_type &r_res, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
 Forward search for a pattern in an $\omega$-interval $[\ell..r]$ in the CSA. More...
 
template<class t_csa >
t_csa::size_type forward_search (const t_csa &csa, typename t_csa::size_type l, typename t_csa::size_type r, typename t_csa::char_type c, typename t_csa::size_type &l_res, typename t_csa::size_type &r_res, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
 Forward search for a character c in an $\omega$-interval $[\ell..r]$ in the CSA. More...
 
template<class t_csa >
t_csa::size_type backward_search (const t_csa &csa, typename t_csa::size_type l, typename t_csa::size_type r, typename t_csa::char_type c, typename t_csa::size_type &l_res, typename t_csa::size_type &r_res, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
 Backward search for a character c in an $\omega$-interval $[\ell..r]$ in the CSA. More...
 
template<class t_csa , class t_pat_iter >
t_csa::size_type backward_search (const t_csa &csa, typename t_csa::size_type l, typename t_csa::size_type r, t_pat_iter begin, t_pat_iter end, typename t_csa::size_type &l_res, typename t_csa::size_type &r_res, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
 Backward search for a pattern in an $\omega$-interval $[\ell..r]$ in the CSA. More...
 
template<class t_wt , uint32_t t_dens, uint32_t t_inv_dens, class t_sa_sample_strat , class t_isa , class t_alphabet_strat >
csa_wt< t_wt >::size_type bidirectional_search (const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &csa_fwd, typename csa_wt<>::size_type l_fwd, typename csa_wt<>::size_type r_fwd, typename csa_wt<>::size_type l_bwd, typename csa_wt<>::size_type r_bwd, typename csa_wt<>::char_type c, typename csa_wt<>::size_type &l_fwd_res, typename csa_wt<>::size_type &r_fwd_res, typename csa_wt<>::size_type &l_bwd_res, typename csa_wt<>::size_type &r_bwd_res, SDSL_UNUSED typename std::enable_if< t_wt::lex_ordered, csa_tag >::type x=csa_tag())
 Bidirectional search for a character c on an interval $[l_fwd..r_fwd]$ of the suffix array. More...
 
template<class t_pat_iter , class t_wt , uint32_t t_dens, uint32_t t_inv_dens, class t_sa_sample_strat , class t_isa , class t_alphabet_strat >
csa_wt ::size_type bidirectional_search_backward (const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &csa_fwd, SDSL_UNUSED const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &csa_bwd, typename csa_wt<>::size_type l_fwd, typename csa_wt<>::size_type r_fwd, typename csa_wt<>::size_type l_bwd, typename csa_wt<>::size_type r_bwd, t_pat_iter begin, t_pat_iter end, typename csa_wt<>::size_type &l_fwd_res, typename csa_wt<>::size_type &r_fwd_res, typename csa_wt<>::size_type &l_bwd_res, typename csa_wt<>::size_type &r_bwd_res, SDSL_UNUSED typename std::enable_if< t_wt::lex_ordered, csa_tag >::type x=csa_tag())
 Bidirectional search in backward direction. More...
 
template<class t_pat_iter , class t_wt , uint32_t t_dens, uint32_t t_inv_dens, class t_sa_sample_strat , class t_isa , class t_alphabet_strat >
csa_wt< t_wt >::size_type bidirectional_search_forward (SDSL_UNUSED const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &csa_fwd, const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &csa_bwd, typename csa_wt<>::size_type l_fwd, typename csa_wt<>::size_type r_fwd, typename csa_wt<>::size_type l_bwd, typename csa_wt<>::size_type r_bwd, t_pat_iter begin, t_pat_iter end, typename csa_wt<>::size_type &l_fwd_res, typename csa_wt<>::size_type &r_fwd_res, typename csa_wt<>::size_type &l_bwd_res, typename csa_wt<>::size_type &r_bwd_res, SDSL_UNUSED typename std::enable_if< t_wt::lex_ordered, csa_tag >::type x=csa_tag())
 Bidirectional search in forward direction. More...
 
template<class t_csa , class t_pat_iter >
t_csa::size_type count (const t_csa &csa, t_pat_iter begin, t_pat_iter end, csa_tag)
 Counts the number of occurrences of a pattern in a CSA. More...
 
template<class t_csx , class t_pat_iter >
t_csx::size_type count (const t_csx &csx, t_pat_iter begin, t_pat_iter end)
 
template<class t_csx >
t_csx::size_type count (const t_csx &csx, const typename t_csx::string_type &pat)
 Counts the number of occurrences of a pattern in a CSA. More...
 
template<typename t_csx , typename t_pat_iter >
auto lex_interval (const t_csx &csx, t_pat_iter begin, t_pat_iter end) -> std::array< typename t_csx::size_type, 2 >
 Returns the lexicographic interval of a pattern in the SA. More...
 
template<class t_csa , class t_pat_iter , class t_rac = int_vector<64>>
t_rac locate (const t_csa &csa, t_pat_iter begin, t_pat_iter end, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
 Calculates all occurrences of a pattern pat in a CSA. More...
 
template<class t_csx , class t_rac = int_vector<64>>
t_rac locate (const t_csx &csx, const typename t_csx::string_type &pat)
 Calculates all occurrences of a pattern pat in a CSA/CST. More...
 
template<class t_csa , class t_text_iter >
t_csa::size_type extract (const t_csa &csa, typename t_csa::size_type begin, typename t_csa::size_type end, t_text_iter text, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
 Writes the substring T[begin..end] of the original text T to text[0..end-begin+1]. More...
 
template<class t_csa , class t_text_iter >
t_csa::size_type extract (const t_csa &csa, typename t_csa::size_type begin, typename t_csa::size_type end, t_text_iter text, lf_tag)
 Specialization of extract for LF-function based CSAs. More...
 
template<class t_csa , class t_text_iter >
t_csa::size_type extract (const t_csa &csa, typename t_csa::size_type begin, typename t_csa::size_type end, t_text_iter text, psi_tag)
 Specialization of extract for $\Psi$-function based CSAs. More...
 
template<class t_csa >
t_csa::string_type extract (const t_csa &csa, typename t_csa::size_type begin, typename t_csa::size_type end, SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type x=csa_tag())
 Reconstructs the substring T[begin..end] of the original text T to text[0..end-begin+1]. More...
 
template<typename t_csa >
t_csa::char_type first_row_symbol (const typename t_csa::size_type i, const t_csa &csa)
 Get the symbol at position i in the first row of the sorted suffixes of CSA. More...
 
template<class t_cst >
t_cst::size_type forward_search (const t_cst &cst, typename t_cst::node_type &v, const typename t_cst::size_type d, const typename t_cst::char_type c, typename t_cst::size_type &char_pos, SDSL_UNUSED typename std::enable_if< std::is_same< cst_tag, typename t_cst::index_category >::value, cst_tag >::type x=cst_tag())
 Forward search for a character c on the path on depth $d$ to node $v$. More...
 
template<class t_cst , class t_pat_iter >
t_cst::size_type forward_search (const t_cst &cst, typename t_cst::node_type &v, typename t_cst::size_type d, t_pat_iter begin, t_pat_iter end, typename t_cst::size_type &char_pos, SDSL_UNUSED typename std::enable_if< std::is_same< cst_tag, typename t_cst::index_category >::value, cst_tag >::type x=cst_tag())
 Forward search for a pattern pat on the path on depth $d$ to node $v$. More...
 
template<class t_cst , class t_pat_iter >
t_cst::size_type count (const t_cst &cst, t_pat_iter begin, t_pat_iter end, cst_tag)
 Counts the number of occurrences of a pattern in a CST. More...
 
template<class t_cst , class t_pat_iter , class t_rac = int_vector<64>>
t_rac locate (const t_cst &cst, t_pat_iter begin, t_pat_iter end, SDSL_UNUSED typename std::enable_if< std::is_same< cst_tag, typename t_cst::index_category >::value, cst_tag >::type x=cst_tag())
 Calculates all occurrences of a pattern pat in a CST. More...
 
template<class t_cst , class t_text_iter >
t_cst::size_type extract (const t_cst &cst, const typename t_cst::node_type &v, t_text_iter text, SDSL_UNUSED typename std::enable_if< std::is_same< cst_tag, typename t_cst::index_category >::value, cst_tag >::type x=cst_tag())
 Calculate the concatenation of edge labels from the root to the node v of a CST. More...
 
template<class t_cst >
t_cst::csa_type::string_type extract (const t_cst &cst, const typename t_cst::node_type &v, SDSL_UNUSED typename std::enable_if< std::is_same< cst_tag, typename t_cst::index_category >::value, cst_tag >::type x=cst_tag())
 Calculate the concatenation of edge labels from the root to the node v of of c CST. More...
 
template<class t_cst >
double H0 (const typename t_cst::node_type &v, const t_cst &cst)
 Calculate the zeroth order entropy of the text that follows a certain substring s. More...
 
template<class t_cst >
std::pair< double, size_t > Hk (const t_cst &cst, typename t_cst::size_type k)
 Calculate the k-th order entropy of a text. More...
 
template<class t_rac >
void construct_supercartesian_tree_bp (const t_rac &vec, bit_vector &bp, const bool minimum=true)
 Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009). More...
 
template<class t_rac >
bit_vector construct_supercartesian_tree_bp_succinct (const t_rac &vec, const bool minimum=true)
 Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009). More...
 
template<uint8_t t_width>
bit_vector construct_supercartesian_tree_bp_succinct (int_vector_buffer< t_width > &lcp_buf, const bool minimum=true)
 Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009). More...
 
template<uint8_t t_width>
bit_vector::size_type construct_supercartesian_tree_bp_succinct_and_first_child (int_vector_buffer< t_width > &lcp_buf, bit_vector &bp, bit_vector &bp_fc, const bool minimum=true)
 Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009) and the first_child bit_vector. More...
 
template<class t_csa >
t_csa::size_type get_char_pos (typename t_csa::size_type idx, typename t_csa::size_type d, const t_csa &csa)
 
std::ostream & operator<< (std::ostream &os, const uint128_t &x)
 
std::ostream & operator<< (std::ostream &os, const uint256_t &x)
 
template<class t_wt >
std::vector< std::pair< typename t_wt::value_type, typename t_wt::size_type > > intersect (const t_wt &wt, const std::vector< range_type > &ranges, typename t_wt::size_type t=0)
 Intersection of elements in WT[s_0,e_0], WT[s_1,e_1],...,WT[s_k,e_k]. More...
 
template<class t_wt >
std::pair< typename t_wt::value_type, typename t_wt::size_type > quantile_freq (const t_wt &wt, typename t_wt::size_type lb, typename t_wt::size_type rb, typename t_wt::size_type q)
 Returns the q-th smallest element and its frequency in wt[lb..rb]. More...
 
template<class t_wt >
void _interval_symbols_rec (const t_wt &wt, range_type r, typename t_wt::size_type &k, std::vector< typename t_wt::value_type > &cs, std::vector< typename t_wt::size_type > &rank_c_i, std::vector< typename t_wt::size_type > &rank_c_j, const typename t_wt::node_type &v)
 
template<class t_wt >
void _interval_symbols (const t_wt &wt, typename t_wt::size_type i, typename t_wt::size_type j, typename t_wt::size_type &k, std::vector< typename t_wt::value_type > &cs, std::vector< typename t_wt::size_type > &rank_c_i, std::vector< typename t_wt::size_type > &rank_c_j)
 
template<class t_wt >
void interval_symbols (const t_wt &wt, typename t_wt::size_type i, typename t_wt::size_type j, typename t_wt::size_type &k, std::vector< typename t_wt::value_type > &cs, std::vector< typename t_wt::size_type > &rank_c_i, std::vector< typename t_wt::size_type > &rank_c_j)
 For each symbol c in wt[i..j-1] get rank(i,c) and rank(j,c). More...
 
template<class t_wt >
std::pair< bool, typename t_wt::value_type > _symbol_lte (const t_wt &wt, typename t_wt::value_type c)
 Returns for a symbol c the previous smaller or equal symbol in the WT. More...
 
template<class t_wt >
std::pair< bool, typename t_wt::value_type > _symbol_gte (const t_wt &wt, typename t_wt::value_type c)
 Returns for a symbol c the next larger or equal symbol in the WT. More...
 
template<class t_wt >
std::pair< bool, typename t_wt::value_type > symbol_lte (const t_wt &wt, typename t_wt::value_type c)
 Returns for a symbol c the previous smaller or equal symbol in the WT. More...
 
template<class t_wt >
std::pair< bool, typename t_wt::value_type > symbol_gte (const t_wt &wt, typename t_wt::value_type c)
 Returns for a symbol c the next larger or equal symbol in the WT. More...
 
template<class t_wt >
std::vector< typename t_wt::value_type > restricted_unique_range_values (const t_wt &wt, typename t_wt::size_type x_i, typename t_wt::size_type x_j, typename t_wt::value_type y_i, typename t_wt::value_type y_j)
 Returns for a x range [x_i,x_j] and a value range [y_i,y_j] all unique y values occuring in [x_i,x_j] in ascending order. More...
 
template<class t_rac >
void _transform_to_compressed (int_vector<> &iv, typename std::enable_if<!(std::is_same< t_rac, int_vector<> >::value), t_rac >::type &rac, const std::string filename)
 
template<class t_rac >
void _transform_to_compressed (int_vector<> &iv, typename std::enable_if< std::is_same< t_rac, int_vector<> >::value, t_rac >::type &rac, const std::string)
 
bool empty (const range_type &r)
 Empty range check. More...
 
int_vector ::size_type size (const range_type &r)
 Size of a range. More...
 
template<typename t_it , typename t_rac >
void calculate_character_occurences (t_it begin, t_it end, t_rac &C)
 Count for each character the number of occurrences in rac[0..size-1]. More...
 
template<typename t_rac , typename sigma_type >
void calculate_effective_alphabet_size (const t_rac &C, sigma_type &sigma)
 

Variables

constexpr uint8_t sdsl_version_major = SDSL_VERSION_MAJOR
 The major version. More...
 
constexpr uint8_t sdsl_version_minor = SDSL_VERSION_MINOR
 The minor version. More...
 
constexpr uint8_t sdsl_version_patch = SDSL_VERSION_PATCH
 The patch version. More...
 
std::string const sdsl_version
 The full version as std::string. More...
 

Detailed Description

Namespace for the succinct data structure library.

Namespace for the succint data structure library.

Typedef Documentation

◆ binomial15

using sdsl::binomial15 = typedef binomial15_impl<>

Definition at line 97 of file rrr_vector_15.hpp.

◆ bit_vector

bit_vector is a specialization of the int_vector.

Definition at line 53 of file int_vector.hpp.

◆ bit_vector_mapper

template<std::ios_base::openmode t_mode = std::ios_base::out | std::ios_base::in>
using sdsl::bit_vector_mapper = typedef int_vector_mapper<1, t_mode>

Definition at line 421 of file int_vector_mapper.hpp.

◆ bits

using sdsl::bits = typedef bits_impl<>

Definition at line 957 of file bits.hpp.

◆ csa_sada_int

template<class t_enc_vec = enc_vector<>, uint32_t t_dens = 32, uint32_t t_inv_dens = 64, class t_sa_sample_strat = sa_order_sa_sampling<>, class t_isa_sample_strat = isa_sampling<>>
using sdsl::csa_sada_int = typedef csa_sada<t_enc_vec, t_dens, t_inv_dens, t_sa_sample_strat, t_isa_sample_strat, int_alphabet<> >

Definition at line 40 of file suffix_arrays.hpp.

◆ csa_wt_int

template<class t_wt = wt_int<>, uint32_t t_dens = 32, uint32_t t_inv_dens = 64, class t_sa_sample_strat = sa_order_sa_sampling<>, class t_isa_sample_strat = isa_sampling<>>
using sdsl::csa_wt_int = typedef csa_wt<t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa_sample_strat, int_alphabet<> >

Typedef for convenient usage of std integer alphabet strategy.

Definition at line 31 of file suffix_arrays.hpp.

◆ int_vector_size_type

typedef uint64_t sdsl::int_vector_size_type

Definition at line 48 of file config.hpp.

◆ key_bwt_trait

template<uint8_t width>
using sdsl::key_bwt_trait = typedef key_bwt_trait_impl<width, void>

Definition at line 142 of file config.hpp.

◆ key_text_trait

template<uint8_t width>
using sdsl::key_text_trait = typedef key_text_trait_impl<width, void>

Definition at line 139 of file config.hpp.

◆ lcp_dac

template<uint8_t t_b = 4, typename t_rank = rank_support_v5<>>
using sdsl::lcp_dac = typedef lcp_vlc<dac_vector<t_b, t_rank> >

A class for the compressed version of LCP information of an suffix array.

A dac_vector is used to compress represent the values compressed. The template parameter are forwarded to the dac_vector.

Template Parameters
t_bSplit block size.
t_rankRank structure to navigate between the different levels.

Definition at line 26 of file lcp_dac.hpp.

◆ mm_block_foot_t

◆ mm_block_t

◆ range_maximum_support_sparse_table

template<class t_rac = int_vector<>>
using sdsl::range_maximum_support_sparse_table = typedef rmq_support_sparse_table<t_rac, false>

Definition at line 24 of file rmq_support_sparse_table.hpp.

◆ range_type

typedef std::array<int_vector<>::size_type, 2> sdsl::range_type

Definition at line 20 of file wt_helper.hpp.

◆ range_vec_type

typedef std::vector<range_type> sdsl::range_vec_type

Definition at line 21 of file wt_helper.hpp.

◆ read_only_mapper

template<uint8_t t_width = 0>
using sdsl::read_only_mapper = typedef const int_vector_mapper<t_width, std::ios_base::in>

Definition at line 424 of file int_vector_mapper.hpp.

◆ std_size_type_for_int_vector

Definition at line 44 of file int_vector.hpp.

◆ tLI

typedef std::list<int_vector<>::size_type> sdsl::tLI

Definition at line 173 of file construct_lcp_helper.hpp.

◆ tMSS

typedef std::map<std::string, std::string> sdsl::tMSS

Definition at line 50 of file config.hpp.

◆ trbudget_t

template<typename saidx_t >
using sdsl::trbudget_t = typedef _trbudget_t<saidx_t>

Definition at line 1230 of file divsufsort.hpp.

◆ tVI

typedef std::vector<int_vector<>::size_type> sdsl::tVI

Definition at line 174 of file construct_lcp_helper.hpp.

◆ wt_blcd_int

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select_one = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
using sdsl::wt_blcd_int = typedef wt_pc<balanced_shape, t_bitvector, t_rank, t_select_one, t_select_zero, int_tree<> >

Definition at line 51 of file wavelet_trees.hpp.

◆ wt_huff_int

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
using sdsl::wt_huff_int = typedef wt_pc<huff_shape, t_bitvector, t_rank, t_select, t_select_zero, int_tree<> >

Definition at line 45 of file wavelet_trees.hpp.

◆ wt_hutu_int

template<class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type>
using sdsl::wt_hutu_int = typedef wt_pc<hutu_shape, t_bitvector, t_rank, t_select, t_select_zero, int_tree<> >

Definition at line 39 of file wavelet_trees.hpp.

Enumeration Type Documentation

◆ byte_sa_algo_type

Enumerator
LIBDIVSUFSORT 
SE_SAIS 

Definition at line 59 of file config.hpp.

◆ format_type

Enumerator
JSON_FORMAT 
R_FORMAT 
HTML_FORMAT 

Definition at line 52 of file config.hpp.

Function Documentation

◆ __count()

template<typename t_k2_treap >
uint64_t sdsl::__count ( const t_k2_treap &  treap,
typename t_k2_treap::node_type  v 
)

Definition at line 325 of file k2_treap_algorithm.hpp.

◆ _compare()

template<typename saidx_t >
int sdsl::_compare ( const uint8_t *  T,
saidx_t  Tsize,
const uint8_t *  P,
saidx_t  Psize,
saidx_t  suf,
saidx_t *  match 
)
inline

Definition at line 2214 of file divsufsort.hpp.

◆ _construct_sa_IS()

void sdsl::_construct_sa_IS ( int_vector<> &  text,
int_vector<> &  sa,
std::string &  filename_sa,
size_t  n,
size_t  text_offset,
size_t  sigma,
uint64_t  recursion 
)
inline

Definition at line 48 of file construct_sa_se.hpp.

◆ _construct_sa_se()

template<class int_vector_type >
void sdsl::_construct_sa_se ( int_vector_type &  text,
std::string  filename_sa,
uint64_t  sigma,
uint64_t  recursion 
)

Definition at line 271 of file construct_sa_se.hpp.

◆ _count()

template<typename t_k2_treap >
uint64_t sdsl::_count ( const t_k2_treap &  treap,
k2_treap_ns::point_type  p1,
k2_treap_ns::point_type  p2,
typename t_k2_treap::node_type  v 
)

Definition at line 307 of file k2_treap_algorithm.hpp.

◆ _get_next_lms_position()

template<class int_vector_type >
uint64_t sdsl::_get_next_lms_position ( int_vector_type &  text,
uint64_t  i 
)

Definition at line 21 of file construct_sa_se.hpp.

◆ _idx_csa() [1/2]

template<typename t_csa >
const t_csa & sdsl::_idx_csa ( const t_csa &  t,
csa_tag   
)

Internal function used by csXprintf.

Definition at line 461 of file io.hpp.

◆ _idx_csa() [2/2]

template<typename t_cst >
const t_cst::csa_type & sdsl::_idx_csa ( const t_cst &  t,
cst_tag   
)

Internal function used by csXprintf.

Definition at line 468 of file io.hpp.

◆ _idx_lcp_val() [1/2]

template<typename t_csa >
std::string sdsl::_idx_lcp_val ( const t_csa &  ,
uint64_t  ,
uint64_t  ,
csa_tag   
)

Internal function used by csXprintf.

Definition at line 475 of file io.hpp.

◆ _idx_lcp_val() [2/2]

template<typename t_cst >
std::string sdsl::_idx_lcp_val ( const t_cst &  t,
uint64_t  i,
uint64_t  w,
cst_tag   
)

Internal function used by csXprintf.

Definition at line 482 of file io.hpp.

◆ _interval_symbols()

template<class t_wt >
void sdsl::_interval_symbols ( const t_wt &  wt,
typename t_wt::size_type  i,
typename t_wt::size_type  j,
typename t_wt::size_type &  k,
std::vector< typename t_wt::value_type > &  cs,
std::vector< typename t_wt::size_type > &  rank_c_i,
std::vector< typename t_wt::size_type > &  rank_c_j 
)

Definition at line 170 of file wt_algorithm.hpp.

◆ _interval_symbols_rec()

template<class t_wt >
void sdsl::_interval_symbols_rec ( const t_wt &  wt,
range_type  r,
typename t_wt::size_type &  k,
std::vector< typename t_wt::value_type > &  cs,
std::vector< typename t_wt::size_type > &  rank_c_i,
std::vector< typename t_wt::size_type > &  rank_c_j,
const typename t_wt::node_type &  v 
)

Definition at line 139 of file wt_algorithm.hpp.

◆ _parse_number()

uint64_t sdsl::_parse_number ( std::string::const_iterator &  c,
const std::string::const_iterator &  end 
)
inline

Internal function used by csXprintf.

Definition at line 448 of file io.hpp.

◆ _symbol_gte()

template<class t_wt >
std::pair< bool, typename t_wt::value_type > sdsl::_symbol_gte ( const t_wt &  wt,
typename t_wt::value_type  c 
)

Returns for a symbol c the next larger or equal symbol in the WT.

Parameters
cthe symbol
Returns
A pair. The first element of the pair consititues if a valid answer was found (true) or no valid answer (false) could be found. The second element contains the found symbol.

Definition at line 416 of file wt_algorithm.hpp.

◆ _symbol_lte()

template<class t_wt >
std::pair< bool, typename t_wt::value_type > sdsl::_symbol_lte ( const t_wt &  wt,
typename t_wt::value_type  c 
)

Returns for a symbol c the previous smaller or equal symbol in the WT.

Parameters
cthe symbol
Returns
A pair. The first element of the pair consititues if a valid answer was found (true) or no valid answer (false) could be found. The second element contains the found symbol.

Definition at line 358 of file wt_algorithm.hpp.

◆ _transform_to_compressed() [1/2]

template<class t_rac >
void sdsl::_transform_to_compressed ( int_vector<> &  iv,
typename std::enable_if< std::is_same< t_rac, int_vector<> >::value, t_rac >::type &  rac,
const std::string   
)

Definition at line 293 of file wt_gmr.hpp.

◆ _transform_to_compressed() [2/2]

template<class t_rac >
void sdsl::_transform_to_compressed ( int_vector<> &  iv,
typename std::enable_if<!(std::is_same< t_rac, int_vector<> >::value), t_rac >::type &  rac,
const std::string  filename 
)

Definition at line 280 of file wt_gmr.hpp.

◆ _write_structure() [1/2]

void sdsl::_write_structure ( std::unique_ptr< structure_tree_node > &  )
inline

Definition at line 445 of file io.hpp.

◆ _write_structure() [2/2]

template<typename X , typename... Xs>
void sdsl::_write_structure ( std::unique_ptr< structure_tree_node > &  st_node,
x,
Xs...  xs 
)

Definition at line 438 of file io.hpp.

◆ add_hash()

template<typename T >
void sdsl::add_hash ( const T &  t,
std::ostream &  out 
)

Definition at line 791 of file io.hpp.

◆ append_zero_symbol()

template<class int_vector >
void sdsl::append_zero_symbol ( int_vector text)

Definition at line 38 of file construct.hpp.

◆ backward_search() [1/2]

template<class t_csa , class t_pat_iter >
t_csa::size_type sdsl::backward_search ( const t_csa &  csa,
typename t_csa::size_type  l,
typename t_csa::size_type  r,
t_pat_iter  begin,
t_pat_iter  end,
typename t_csa::size_type &  l_res,
typename t_csa::size_type &  r_res,
SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type  x = csa_tag() 
)

Backward search for a pattern in an $\omega$-interval $[\ell..r]$ in the CSA.

Template Parameters
t_csaA CSA type.
t_pat_iterPattern iterator type.
Parameters
csaThe CSA object.
lLeft border of the lcp-interval $ [\ell..r]$.
rRight border of the lcp-interval $ [\ell..r]$.
beginIterator to the begin of the pattern (inclusive).
endIterator to the end of the pattern (exclusive).
l_resNew left border.
r_resNew right border.
Returns
The size of the new interval [\ell_{new}..r_{new}]. Equals zero, if no match is found.
Precondition
$ 0 \leq \ell \leq r < csa.size() $
Time complexity
$ \Order{ len \cdot t_{rank\_bwt} } $
Reference
Paolo Ferragina, Giovanni Manzini: Opportunistic Data Structures with Applications. FOCS 2000: 390-398

Definition at line 219 of file suffix_array_algorithm.hpp.

◆ backward_search() [2/2]

template<class t_csa >
t_csa::size_type sdsl::backward_search ( const t_csa &  csa,
typename t_csa::size_type  l,
typename t_csa::size_type  r,
typename t_csa::char_type  c,
typename t_csa::size_type &  l_res,
typename t_csa::size_type &  r_res,
SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type  x = csa_tag() 
)

Backward search for a character c in an $\omega$-interval $[\ell..r]$ in the CSA.

Template Parameters
t_csaCSA type.
Parameters
csaThe CSA object.
lLeft border of the interval $ [\ell..r]$.
rRight border of the interval $ [\ell..r]$.
cCharacter to be prepended to $\omega$.
l_resNew left border.
r_resRight border.
Returns
The size of the new interval [\ell_{new}..r_{new}]. Equals zero, if no match is found.
Precondition
$ 0 \leq \ell \leq r < csa.size() $
Time complexity
$ \Order{ t_{rank\_bwt} } $
Reference
Paolo Ferragina, Giovanni Manzini: Opportunistic Data Structures with Applications. FOCS 2000: 390-398

Definition at line 157 of file suffix_array_algorithm.hpp.

◆ bidirectional_search()

template<class t_wt , uint32_t t_dens, uint32_t t_inv_dens, class t_sa_sample_strat , class t_isa , class t_alphabet_strat >
csa_wt< t_wt >::size_type sdsl::bidirectional_search ( const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &  csa_fwd,
typename csa_wt<>::size_type  l_fwd,
typename csa_wt<>::size_type  r_fwd,
typename csa_wt<>::size_type  l_bwd,
typename csa_wt<>::size_type  r_bwd,
typename csa_wt<>::char_type  c,
typename csa_wt<>::size_type &  l_fwd_res,
typename csa_wt<>::size_type &  r_fwd_res,
typename csa_wt<>::size_type &  l_bwd_res,
typename csa_wt<>::size_type &  r_bwd_res,
SDSL_UNUSED typename std::enable_if< t_wt::lex_ordered, csa_tag >::type  x = csa_tag() 
)

Bidirectional search for a character c on an interval $[l_fwd..r_fwd]$ of the suffix array.

Parameters
csa_fwdThe CSA object of the forward text in which the backward_search should be done.
l_fwdLeft border of the lcp-interval $ [l_fwd..r_fwd]$ in suffix array of the forward text.
r_fwdRight border of the lcp-interval $ [l_fwd..r_fwd]$ in suffix array of the forward text.
l_bwdLeft border of the lcp-interval $ [l_bwd..r_bwd]$ in suffix array of the backward text.
r_bwdRight border of the lcp-interval $ [l_bwd..r_bwd]$ in suffix array of the backward text.
cThe character c which is the starting character of the suffixes in the resulting interval $
[l_fwd_res..r_fwd_res] $ .
l_fwd_resReference to the resulting left border in suffix array of the forward text.
r_fwd_resReference to the resulting right border in suffix array of the forward text.
l_bwd_resReference to the resulting left border in suffix array of the backward text.
r_bwd_resReference to the resulting right border in suffix array of the backward text.
Returns
The size of the new interval [l_fwd_res..r_fwd_res].
Precondition
$ 0 \leq \ell \leq r_fwd < csa_fwd.size() $
Reference Thomas Schnattinger, Enno
Ohlebusch, Simon Gog: Bidirectional search in a string with wavelet trees and bidirectional matching statistics. Inf. Comput. 213: 13-22

Definition at line 264 of file suffix_array_algorithm.hpp.

◆ bidirectional_search_backward()

template<class t_pat_iter , class t_wt , uint32_t t_dens, uint32_t t_inv_dens, class t_sa_sample_strat , class t_isa , class t_alphabet_strat >
csa_wt ::size_type sdsl::bidirectional_search_backward ( const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &  csa_fwd,
SDSL_UNUSED const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &  csa_bwd,
typename csa_wt<>::size_type  l_fwd,
typename csa_wt<>::size_type  r_fwd,
typename csa_wt<>::size_type  l_bwd,
typename csa_wt<>::size_type  r_bwd,
t_pat_iter  begin,
t_pat_iter  end,
typename csa_wt<>::size_type &  l_fwd_res,
typename csa_wt<>::size_type &  r_fwd_res,
typename csa_wt<>::size_type &  l_bwd_res,
typename csa_wt<>::size_type &  r_bwd_res,
SDSL_UNUSED typename std::enable_if< t_wt::lex_ordered, csa_tag >::type  x = csa_tag() 
)

Bidirectional search in backward direction.

The function requires a pattern $p$, an $\omega$-interval $[l_fwd..r_fwd]$ in the CSA object of the forward text and an $\omega^{rev}$-interval $[l_bwd..r_bwd]$ in the CSA object of the backward text. The function returns the $p\omega$-interval in the CSA object of the forward text and the $\omega^{rev}p^{rev}$-interval in the CSA object of the backward text.

Template Parameters
t_pat_iterPattern iterator type.
Parameters
csa_fwdThe CSA object of the forward text.
csa_bwdThe CSA object of the backward text.
l_fwdLeft border of the lcp-interval $ [l_fwd..r_fwd]$ in suffix array of the forward text.
r_fwdRight border of the lcp-interval $ [l_fwd..r_fwd]$ in suffix array of the forward text.
l_bwdLeft border of the lcp-interval $ [l_bwd..r_bwd]$ in suffix array of the backward text.
r_bwdRight border of the lcp-interval $ [l_bwd..r_bwd]$ in suffix array of the backward text.
beginIterator to the begin of the pattern (inclusive).
endIterator to the end of the pattern (exclusive).
l_fwd_resReference to the resulting left border in suffix array of the forward text.
r_fwd_resReference to the resulting right border in suffix array of the forward text.
l_bwd_resReference to the resulting left border in suffix array of the backward text.
r_bwd_resReference to the resulting right border in suffix array of the backward text.
Returns
The size of the new interval [l_fwd_res..r_fwd_res]. Equals zero, if no match is found.
Precondition
$ 0 \leq \ell \leq r_fwd < csa_fwd.size() $
Reference
Thomas Schnattinger, Enno Ohlebusch, Simon Gog: Bidirectional search in a string with wavelet trees and bidirectional matching statistics. Inf. Comput. 213: 13-22

Definition at line 331 of file suffix_array_algorithm.hpp.

◆ bidirectional_search_forward()

template<class t_pat_iter , class t_wt , uint32_t t_dens, uint32_t t_inv_dens, class t_sa_sample_strat , class t_isa , class t_alphabet_strat >
csa_wt< t_wt >::size_type sdsl::bidirectional_search_forward ( SDSL_UNUSED const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &  csa_fwd,
const csa_wt< t_wt, t_dens, t_inv_dens, t_sa_sample_strat, t_isa, t_alphabet_strat > &  csa_bwd,
typename csa_wt<>::size_type  l_fwd,
typename csa_wt<>::size_type  r_fwd,
typename csa_wt<>::size_type  l_bwd,
typename csa_wt<>::size_type  r_bwd,
t_pat_iter  begin,
t_pat_iter  end,
typename csa_wt<>::size_type &  l_fwd_res,
typename csa_wt<>::size_type &  r_fwd_res,
typename csa_wt<>::size_type &  l_bwd_res,
typename csa_wt<>::size_type &  r_bwd_res,
SDSL_UNUSED typename std::enable_if< t_wt::lex_ordered, csa_tag >::type  x = csa_tag() 
)

Bidirectional search in forward direction.

The function requires a pattern $p$, an $\omega$-interval $[l_fwd..r_fwd]$ in the CSA object of the forward text and an $\omega^{rev}$-interval $[l_bwd..r_bwd]$ in the CSA object of the backward text. The function returns the $\omega p$-interval in the CSA object of the forward text and the $p^{rev}omega^{rev}$-interval in the CSA object of the backward text.

Template Parameters
t_pat_iterPattern iterator type.
Parameters
csa_fwdThe CSA object of the forward text.
csa_bwdThe CSA object of the backward text.
l_fwdLeft border of the lcp-interval $ [l_fwd..r_fwd]$ in suffix array of the forward text.
r_fwdRight border of the lcp-interval $ [l_fwd..r_fwd]$ in suffix array of the forward text.
l_bwdLeft border of the lcp-interval $ [l_bwd..r_bwd]$ in suffix array of the backward text.
r_bwdRight border of the lcp-interval $ [l_bwd..r_bwd]$ in suffix array of the backward text.
beginIterator to the begin of the pattern (inclusive).
endIterator to the end of the pattern (exclusive).
l_fwd_resReference to the resulting left border in suffix array of the forward text.
r_fwd_resReference to the resulting right border in suffix array of the forward text.
l_bwd_resReference to the resulting left border in suffix array of the backward text.
r_bwd_resReference to the resulting right border in suffix array of the backward text.
Returns
The size of the new interval [l_fwd_res..r_fwd_res]. Equals zero, if no match is found.
Precondition
$ 0 \leq \ell \leq r_fwd < csa_fwd.size() $
Reference
Thomas Schnattinger, Enno Ohlebusch, Simon Gog: Bidirectional search in a string with wavelet trees and bidirectional matching statistics. Inf. Comput. 213: 13-22

Definition at line 411 of file suffix_array_algorithm.hpp.

◆ block_cur()

mm_block_t * sdsl::block_cur ( void *  ptr)
inline

Definition at line 251 of file memory_management.hpp.

◆ block_data()

void * sdsl::block_data ( mm_block_t ptr)
inline

Definition at line 320 of file memory_management.hpp.

◆ block_getdatasize()

size_t sdsl::block_getdatasize ( mm_block_t ptr)
inline

Definition at line 326 of file memory_management.hpp.

◆ block_isfree()

bool sdsl::block_isfree ( mm_block_t ptr)
inline

Definition at line 284 of file memory_management.hpp.

◆ block_markfree()

void sdsl::block_markfree ( mm_block_t ptr)
inline

Definition at line 333 of file memory_management.hpp.

◆ block_markused()

void sdsl::block_markused ( mm_block_t ptr)
inline

Definition at line 339 of file memory_management.hpp.

◆ block_next()

mm_block_t * sdsl::block_next ( mm_block_t cur_bptr,
uint8_t *  top 
)
inline

Definition at line 268 of file memory_management.hpp.

◆ block_nextfree()

bool sdsl::block_nextfree ( mm_block_t ptr,
uint8_t *  top 
)
inline

Definition at line 290 of file memory_management.hpp.

◆ block_prev()

mm_block_t * sdsl::block_prev ( mm_block_t cur_bptr,
mm_block_t first 
)
inline

Definition at line 258 of file memory_management.hpp.

◆ block_prevfree()

bool sdsl::block_prevfree ( mm_block_t ptr,
mm_block_t begin 
)
inline

Definition at line 298 of file memory_management.hpp.

◆ block_size()

size_t sdsl::block_size ( void *  ptr)
inline

Definition at line 278 of file memory_management.hpp.

◆ block_update()

void sdsl::block_update ( mm_block_t ptr,
size_t  size 
)
inline

Definition at line 313 of file memory_management.hpp.

◆ cache_file_exists() [1/2]

bool sdsl::cache_file_exists ( const std::string &  key,
const cache_config config 
)
inline

Checks if the resource specified by the key exists in the cache.

Parameters
keyResource key.
configCache configuration.
Returns
True, if the file exists, false otherwise.

Definition at line 672 of file io.hpp.

◆ cache_file_exists() [2/2]

template<typename T >
bool sdsl::cache_file_exists ( const std::string &  key,
const cache_config config 
)

Checks if the resource specified by the key and type exists in the cache.

Template Parameters
TType.
Parameters
keyResource key.
configCache configuration.
Returns
True, if the file exists, false otherwise.

Definition at line 692 of file io.hpp.

◆ cache_file_name() [1/2]

std::string sdsl::cache_file_name ( const std::string &  key,
const cache_config config 
)
inline

Returns the file name of the resource.

Parameters
keyResource key.
configCache configuration.
Returns
The file name of the resource.

Definition at line 630 of file io.hpp.

◆ cache_file_name() [2/2]

template<typename T >
std::string sdsl::cache_file_name ( const std::string &  key,
const cache_config config 
)

Returns the file name of the resource.

Parameters
keyResource key.
configCache configuration.
Returns
The file name of the resource.

Definition at line 643 of file io.hpp.

◆ calculate_character_occurences()

template<typename t_it , typename t_rac >
void sdsl::calculate_character_occurences ( t_it  begin,
t_it  end,
t_rac &  C 
)

Count for each character the number of occurrences in rac[0..size-1].

Parameters
CAn array of size 256, which contains for each character the number of occurrences in rac[0..size-1]

Definition at line 40 of file wt_helper.hpp.

◆ calculate_effective_alphabet_size()

template<typename t_rac , typename sigma_type >
void sdsl::calculate_effective_alphabet_size ( const t_rac &  C,
sigma_type &  sigma 
)

Definition at line 52 of file wt_helper.hpp.

◆ calculate_enclose()

template<class int_vector >
void sdsl::calculate_enclose ( const bit_vector bp,
int_vector enclose 
)

Calculates enclose answers for a balanced parentheses sequence.

Parameters
bpA bit_vector representing a balanced parentheses sequence.
encloseReference to the result.
Precondition
bp represents a balanced parentheses sequence.
Time complexity
$ \Order{n} $, where $ n=$bp.size()
Space complexity
$ \Order{n + 2n\log n } $

Definition at line 314 of file bp_support_algorithm.hpp.

◆ calculate_matches()

template<class int_vector >
void sdsl::calculate_matches ( const bit_vector bp,
int_vector matches 
)

find_open/find_close for closing/opening parentheses.

Parameters
bpThe balanced parentheses sequence.
matchesReference to the result.
Precondition
bp represents a balanced parentheses sequence.
Time complexity
$ \Order{n} $, where $ n=$bp.size()
Space complexity
$ \Order{n + 2n\log n } $

Definition at line 279 of file bp_support_algorithm.hpp.

◆ calculate_pioneers_bitmap()

bit_vector sdsl::calculate_pioneers_bitmap ( const bit_vector bp,
uint64_t  block_size 
)
inline

Calculate pioneers as defined in the paper of Geary et al. (CPM 2004)

Parameters
bpThe balanced parentheses sequence.
block_sizeBlock size.
Returns
Bitvector which marks the pioneers in bp.
Time complexity
$ \Order{n \log n} $, where $ n=$bp.size()
Space complexity
$ \Order{2n + min(block\_size, \frac{n}{block\_size} )\cdot \log n } $

Definition at line 165 of file bp_support_algorithm.hpp.

◆ calculate_pioneers_bitmap_succinct()

bit_vector sdsl::calculate_pioneers_bitmap_succinct ( const bit_vector bp,
uint64_t  block_size 
)
inline

Space-efficient version of calculate_pioneers_bitmap.

Parameters
bpThe balanced parentheses sequence.
block_sizeBlock size.
Returns
Bitvector which marks the pioneers in bp.
Time complexity
$ \Order{n} $, where $ n=$bp.size()
Space complexity
$ \Order{2n + n} $ bits: $n$ bits for input, $n$ bits for output, and $n$ bits for a succinct stack.
Precondition
The parentheses sequence represented by bp has to be balanced.

Definition at line 218 of file bp_support_algorithm.hpp.

◆ ceil_log2()

constexpr size_t sdsl::ceil_log2 ( size_t const  n)
constexpr

Definition at line 31 of file rank_support_int.hpp.

◆ construct() [1/8]

template<uint8_t t_k, typename t_bv , typename t_rank , typename t_max_vec >
void sdsl::construct ( k2_treap< t_k, t_bv, t_rank, t_max_vec > &  idx,
std::string  file,
cache_config config 
)

Specialized version of method ,,construct'' for k2_treaps.

Definition at line 339 of file k2_treap_algorithm.hpp.

◆ construct() [2/8]

template<class t_index >
void sdsl::construct ( t_index &  idx,
const std::string &  file,
cache_config config,
uint8_t  num_bytes,
csa_tag   
)

Definition at line 117 of file construct.hpp.

◆ construct() [3/8]

template<class t_index >
void sdsl::construct ( t_index &  idx,
const std::string &  file,
cache_config config,
uint8_t  num_bytes,
cst_tag   
)

Definition at line 240 of file construct.hpp.

◆ construct() [4/8]

template<class t_index >
void sdsl::construct ( t_index &  idx,
const std::string &  file,
cache_config config,
uint8_t  num_bytes,
lcp_tag  tag 
)

Definition at line 229 of file construct.hpp.

◆ construct() [5/8]

template<class t_index , uint8_t t_width>
void sdsl::construct ( t_index &  idx,
const std::string &  file,
cache_config config,
uint8_t  num_bytes,
lcp_tag   
)

Definition at line 177 of file construct.hpp.

◆ construct() [6/8]

template<class t_index >
void sdsl::construct ( t_index &  idx,
const std::string &  file,
cache_config config,
uint8_t  num_bytes,
wt_tag   
)

Definition at line 86 of file construct.hpp.

◆ construct() [7/8]

template<class t_index >
void sdsl::construct ( t_index &  idx,
const std::string &  file,
cache_config config,
uint8_t  num_bytes = 0 
)

Constructs an index object of type t_index for a text stored on disk.

Parameters
idxt_index object. Any sdsl suffix array of suffix tree.
fileName of the text file. The representation of the file is dependent on the next parameter. \
num_bytesIf num_bytes equals 0, the file format is a serialized int_vector<>. Otherwise the file is interpreted as sequence of num_bytes-byte integer stored in big endian order.

Definition at line 77 of file construct.hpp.

◆ construct() [8/8]

template<class t_index >
void sdsl::construct ( t_index &  idx,
std::string  file,
uint8_t  num_bytes = 0,
bool  move_input = false 
)

Definition at line 45 of file construct.hpp.

◆ construct_bwt()

template<uint8_t t_width>
void sdsl::construct_bwt ( cache_config config)

Constructs the Burrows and Wheeler Transform (BWT) from text over byte- or integer-alphabet and suffix array.

The algorithm constructs the BWT and stores it to disk.

Template Parameters
t_widthWidth of the text. 0==integer alphabet, 8=byte alphabet.
Parameters
configReference to cache configuration
Space complexity
$ n \log \sigma $ bits
Precondition
Text and Suffix array exist in the cache. Keys:
Postcondition
BWT exist in the cache. Key

Definition at line 36 of file construct_bwt.hpp.

◆ construct_BWT()

template<typename saidx_t >
saidx_t sdsl::construct_BWT ( const uint8_t *  T,
saidx_t *  SA,
saidx_t *  bucket_A,
saidx_t *  bucket_B,
saidx_t  n,
saidx_t  m 
)
inline

Definition at line 2041 of file divsufsort.hpp.

◆ construct_config()

construct_config_data & sdsl::construct_config ( )
inline

Definition at line 17 of file construct_config.hpp.

◆ construct_first_child_and_lf_lcp()

template<uint32_t t_dens, uint8_t t_bwt_width>
void sdsl::construct_first_child_and_lf_lcp ( int_vector_buffer<> &  lcp_buf,
int_vector_buffer< t_bwt_width > &  bwt_buf,
const std::string &  small_lcp_file,
const std::string &  big_lcp_file,
int_vector<> &  big_lcp 
)
Template Parameters
t_densSample an LCP value x if x modulo t_dens == 0
t_bwt_widthWidth of the integers of the streamed BWT array.

Definition at line 204 of file lcp_support_tree2.hpp.

◆ construct_first_child_lcp()

void sdsl::construct_first_child_lcp ( int_vector_buffer<> &  lcp_buf,
int_vector<> &  fc_lcp 
)
inline

Definition at line 18 of file lcp_support_tree.hpp.

◆ construct_im() [1/2]

template<uint8_t t_k, typename t_bv , typename t_rank , typename t_max_vec >
void sdsl::construct_im ( k2_treap< t_k, t_bv, t_rank, t_max_vec > &  idx,
std::vector< std::array< uint64_t, 3 > >  data 
)

Specialized version of method ,,construct_im'' for k2_treaps.

Definition at line 349 of file k2_treap_algorithm.hpp.

◆ construct_im() [2/2]

template<class t_index , class t_data >
void sdsl::construct_im ( t_index &  idx,
t_data &&  data,
uint8_t  num_bytes = 0 
)

Definition at line 58 of file construct.hpp.

◆ construct_isa()

void sdsl::construct_isa ( cache_config config)
inline

Definition at line 21 of file construct_isa.hpp.

◆ construct_lcp() [1/5]

template<class t_lcp , class t_cst >
void sdsl::construct_lcp ( t_lcp &  lcp,
const t_cst &  ,
cache_config config,
lcp_plain_tag   
)

Definition at line 32 of file lcp.hpp.

◆ construct_lcp() [2/5]

template<class t_lcp , class t_cst >
void sdsl::construct_lcp ( t_lcp &  lcp,
const t_cst &  cst,
cache_config config 
)

Definition at line 25 of file lcp.hpp.

◆ construct_lcp() [3/5]

template<class t_lcp , class t_cst >
void sdsl::construct_lcp ( t_lcp &  lcp,
const t_cst &  cst,
cache_config config,
lcp_permuted_tag   
)

Definition at line 38 of file lcp.hpp.

◆ construct_lcp() [4/5]

template<class t_lcp , class t_cst >
void sdsl::construct_lcp ( t_lcp &  lcp,
const t_cst &  cst,
cache_config config,
lcp_tree_and_lf_compressed_tag   
)

Definition at line 50 of file lcp.hpp.

◆ construct_lcp() [5/5]

template<class t_lcp , class t_cst >
void sdsl::construct_lcp ( t_lcp &  lcp,
const t_cst &  cst,
cache_config config,
lcp_tree_compressed_tag   
)

Definition at line 44 of file lcp.hpp.

◆ construct_lcp_bwt_based()

template<typename t_wt = wt_huff<bit_vector, rank_support_v<>, select_support_scan<1>, select_support_scan<0>>>
void sdsl::construct_lcp_bwt_based ( cache_config config)
inline

Construct the LCP array out of the BWT (only for byte strings)

The algorithm computes the lcp array and stores it to disk. It needs only the Burrows and Wheeler transform.

Parameters
configReference to cache configuration
Precondition
BWT exist in the cache. Keys:
Postcondition
LCP array exist in the cache. Key
Time complexity
$ \Order{n \log{\sigma}} $
Space complexity
Usually not more than $ 2.5n $ bytes
Reference
Timo Beller, Simon Gog, Enno Ohlebusch, Thomas Schnattinger: Computing the Longest Common Prefix Array Based on the Burrows-Wheeler Transform. SPIRE 2011: 197-208

Definition at line 931 of file construct_lcp.hpp.

◆ construct_lcp_bwt_based2()

template<typename t_wt = wt_huff<bit_vector, rank_support_v<>, select_support_scan<1>, select_support_scan<0>>>
void sdsl::construct_lcp_bwt_based2 ( cache_config config)

Construct the LCP array out of the BWT (only for byte strings)

The algorithm computes the lcp array and stores it to disk. It needs only the Burrows and Wheeler transform.

Parameters
configReference to cache configuration
Precondition
BWT exist in the cache. Keys:
Postcondition
LCP array exist in the cache. Key
Time complexity
$ \Order{n \log{\sigma}} $
Space complexity
Usually not more than $ 1.5n $ bytes
Reference
Timo Beller, Simon Gog, Enno Ohlebusch, Thomas Schnattinger: Computing the longest common prefix array based on the Burrows-Wheeler transform. J. Discrete Algorithms 18: 22-31 (2013)

Definition at line 1215 of file construct_lcp.hpp.

◆ construct_lcp_go()

void sdsl::construct_lcp_go ( cache_config config)
inline

Construct the LCP array (only for byte strings)

The algorithm computes the lcp array and stores it to disk. Our new 2 phases lcp algorithm

Parameters
configReference to cache configuration
Precondition
Text, Suffix array and BWT exist in the cache. Keys:
Postcondition
LCP array exist in the cache. Key
Time complexity
$ \Order{n^2} $, but usually faster than goPHI
Space complexity
Usually $ 2n $ bytes, worst case $5n bytes$
Reference
Simon Gog, Enno Ohlebusch: Fast and Lightweight LCP-Array Construction Algorithms. ALENEX 2011: 25-34

Definition at line 312 of file construct_lcp.hpp.

◆ construct_lcp_goPHI()

void sdsl::construct_lcp_goPHI ( cache_config config)
inline

Construct the LCP array (only for byte strings)

The algorithm computes the lcp array and stores it to disk. Our new 2 phases lcp algorithm

Parameters
configReference to cache configuration
Precondition
Text, Suffix array and BWT exist in the cache. Keys:
Postcondition
LCP array exist in the cache. Key
Time complexity
$ \Order{n} $
Space complexity
Usually $ 2n $ bytes
Reference
Simon Gog, Enno Ohlebusch: Lightweight LCP-Array Construction in Linear Time. CoRR abs/1012.4263 (2010)

Definition at line 692 of file construct_lcp.hpp.

◆ construct_lcp_kasai()

template<uint8_t t_width>
void sdsl::construct_lcp_kasai ( cache_config config)

Construct the LCP array for text over byte- or integer-alphabet.

The algorithm computes the lcp array and stores it to disk.

Template Parameters
t_widthWidth of the text. 0==integer alphabet, 8=byte alphabet.
Parameters
configReference to cache configuration
Precondition
Text and Suffix array exist in the cache. Keys:
Postcondition
LCP array exist in the cache. Key
Time complexity
$ \Order{n} $
Space complexity
$ n (\log \sigma + \log n) $ bits
Reference
Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, Kunsoo Park: Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. CPM 2001: 181-192

Definition at line 55 of file construct_lcp.hpp.

◆ construct_lcp_PHI()

template<uint8_t t_width>
void sdsl::construct_lcp_PHI ( cache_config config)

Construct the LCP array for text over byte- or integer-alphabet.

The algorithm computes the lcp array and stores it to disk.

Precondition
Text and Suffix array exist in the cache. Keys:
Postcondition
LCP array exist in the cache. Key
Time complexity
$ \Order{n} $
Space complexity
$ n( \log \sigma + \log n ) $ bits
Reference
Juha Kärkkäinen, Giovanni Manzini, Simon J. Puglisi: Permuted Longest-Common-Prefix Array. CPM 2009: 181-192

Definition at line 116 of file construct_lcp.hpp.

◆ construct_lcp_semi_extern_PHI()

void sdsl::construct_lcp_semi_extern_PHI ( cache_config config)
inline

Construct the LCP array (only for byte strings)

The algorithm computes the lcp array and stores it to disk.

Parameters
configReference to cache configuration
Precondition
Text and Suffix array exist in the cache. Keys:
Postcondition
LCP array exist in the cache. Key
Time complexity
$ \Order{n*q} $ implmented with $ q=64 $
Space complexity
$ n + \frac{n*\log{n}}{q} $ bytes, implmented with $ q=64 $
Reference
Juha Kärkkäinen, Giovanni Manzini, Simon J. Puglisi: Permuted Longest-Common-Prefix Array. CPM 2009: 181-192

Definition at line 195 of file construct_lcp.hpp.

◆ construct_sa()

template<uint8_t t_width>
void sdsl::construct_sa ( cache_config config)

Constructs the Suffix Array (SA) from text over byte- or integer-alphabet.

The algorithm constructs the SA and stores it to disk.

Template Parameters
t_widthWidth of the text. 0==integer alphabet, 8=byte alphabet.
Parameters
configReference to cache configuration
Space complexity
$ 5n $ byte for t_width=8 and input < 2GB $ 9n $ byte for t_width=8 and input > 2GB $ n \log \sigma $ bits for t_width=0
Precondition
Text exist in the cache. Keys:
Postcondition
SA exist in the cache. Key
Reference
For t_width=8: DivSufSort (http://code.google.com/p/libdivsufsort/) For t_width=0: qsufsort (http://www.larsson.dogma.net/qsufsort.c)

Definition at line 160 of file construct_sa.hpp.

◆ construct_SA()

template<typename saidx_t >
void sdsl::construct_SA ( const uint8_t *  T,
saidx_t *  SA,
saidx_t *  bucket_A,
saidx_t *  bucket_B,
saidx_t  n,
saidx_t  m 
)
inline

Definition at line 1970 of file divsufsort.hpp.

◆ construct_sa_se()

void sdsl::construct_sa_se ( cache_config config)
inline

Constructs the Suffix Array (SA) from text over byte-alphabet.

The algorithm constructs the SA and stores it to disk.

Parameters
configReference to cache configuration
Space complexity
Usually less than $1.5n $ bytes of main memory and $10n $ bytes of secondary memory
Precondition
Text exist in the cache. Keys:
Postcondition
SA exist in the cache. Key

This construction method uses less main memory, since data-structures are only kept in main memory, when random access to them is needed. Otherwise they are stored on disk. The disk-usage peak of this algorithm is about 10 times the input.

References
[1] T. Beller, M. Zwerger, S. Gog and E. Ohlebusch: ,,Space-Efficient Construction of the Burrows-Wheeler Transform'', Proceedings of SPIRE 2013.

Definition at line 44 of file construct_sa.hpp.

◆ construct_supercartesian_tree_bp()

template<class t_rac >
void sdsl::construct_supercartesian_tree_bp ( const t_rac &  vec,
bit_vector bp,
const bool  minimum = true 
)

Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009).

Parameters
vecRandom access container for which the Super-Cartesian tree representation should be calculated. The value_type of vec should be an unsigned integer type.
bpReference to the balanced parentheses sequence which represents the Super-Cartesian tree.
minimumSpecifies if the higher levels contains minima or maxima. Default is maxima.
Time complexity
$ \Order{2n} $, where $ n=$vec.size()
Space complexity
$ \Order{n \cdot \log n } $ bits.

Definition at line 108 of file suffix_tree_helper.hpp.

◆ construct_supercartesian_tree_bp_succinct() [1/2]

template<class t_rac >
bit_vector sdsl::construct_supercartesian_tree_bp_succinct ( const t_rac &  vec,
const bool  minimum = true 
)

Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009).

Parameters
vecRandom access container for which the Super-Cartesian tree representation should be calculated. The value_type of vec should be an unsigned integer type.
minimumSpecifies if the higher levels contains minima or maxima. Default is maxima.
Returns
The balanced parentheses sequence representing the Super-Cartesian tree.
Time complexity
$ \Order{2n} $, where $ n=$vec.size()
Space complexity
$\Order{n}$ bits

Definition at line 159 of file suffix_tree_helper.hpp.

◆ construct_supercartesian_tree_bp_succinct() [2/2]

template<uint8_t t_width>
bit_vector sdsl::construct_supercartesian_tree_bp_succinct ( int_vector_buffer< t_width > &  lcp_buf,
const bool  minimum = true 
)

Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009).

Parameters
lcp_bufint_vector_buffer of the LCP Array for which the Super-Cartesian tree representation should be calculated. The value_type of vec should be an unsigned integer type.
minimumSpecifies if the higher levels contains minima or maxima. Default is maxima.
Returns
The balanced parentheses sequence representing the Super-Cartesian tree.
Time complexity #208, where #10vec.size() \par Space complexity
$\Order{2n}$ bits, by the multi_stack_support
Precondition
The largest value in lcp_buf has to be smaller than lcp_buf.size().

Definition at line 218 of file suffix_tree_helper.hpp.

◆ construct_supercartesian_tree_bp_succinct_and_first_child()

template<uint8_t t_width>
bit_vector::size_type sdsl::construct_supercartesian_tree_bp_succinct_and_first_child ( int_vector_buffer< t_width > &  lcp_buf,
bit_vector bp,
bit_vector bp_fc,
const bool  minimum = true 
)

Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE 2009) and the first_child bit_vector.

Parameters
lcp_bufint_vector_buffer for the lcp array for which the Super-Cartesian tree representation should be calculated. The value_type of vec should be an unsigned integer type.
bpReference to the balanced parentheses sequence which represents the Super-Cartesian tree.
bp_fcReference to the first child bit_vector of bp.
minimumSpecifies if the higher levels contains minima or maxima. Default is maxima.
Time complexity
$ \Order{2n} $, where $ n=$vec.size()
Space complexity
$\Order{2n}$ bits, by the multi_stack_support

Definition at line 282 of file suffix_tree_helper.hpp.

◆ contains_no_zero_symbol()

template<class int_vector >
bool sdsl::contains_no_zero_symbol ( const int_vector text,
const std::string &  file 
)

Definition at line 24 of file construct.hpp.

◆ copy_lcp() [1/5]

template<class t_lcp , class t_cst >
void sdsl::copy_lcp ( t_lcp &  lcp,
const t_lcp &  lcp_c,
const t_cst &  ,
lcp_plain_tag   
)

Definition at line 64 of file lcp.hpp.

◆ copy_lcp() [2/5]

template<class t_lcp , class t_cst >
void sdsl::copy_lcp ( t_lcp &  lcp,
const t_lcp &  lcp_c,
const t_cst &  cst 
)

Definition at line 57 of file lcp.hpp.

◆ copy_lcp() [3/5]

template<class t_lcp , class t_cst >
void sdsl::copy_lcp ( t_lcp &  lcp,
const t_lcp &  lcp_c,
const t_cst &  cst,
lcp_permuted_tag   
)

Definition at line 70 of file lcp.hpp.

◆ copy_lcp() [4/5]

template<class t_lcp , class t_cst >
void sdsl::copy_lcp ( t_lcp &  lcp,
const t_lcp &  lcp_c,
const t_cst &  cst,
lcp_tree_and_lf_compressed_tag   
)

Definition at line 84 of file lcp.hpp.

◆ copy_lcp() [5/5]

template<class t_lcp , class t_cst >
void sdsl::copy_lcp ( t_lcp &  lcp,
const t_lcp &  lcp_c,
const t_cst &  cst,
lcp_tree_compressed_tag   
)

Definition at line 77 of file lcp.hpp.

◆ count() [1/5]

template<class t_csa , class t_pat_iter >
t_csa::size_type sdsl::count ( const t_csa &  csa,
t_pat_iter  begin,
t_pat_iter  end,
csa_tag   
)

Counts the number of occurrences of a pattern in a CSA.

Template Parameters
t_csaCSA type.
t_pat_iterPattern iterator type.
Parameters
csaThe CSA object.
beginIterator to the begin of the pattern (inclusive).
endIterator to the end of the pattern (exclusive).
Returns
The number of occurrences of the pattern in the CSA.
Time complexity
$ \Order{ t_{backward\_search} } $

Definition at line 467 of file suffix_array_algorithm.hpp.

◆ count() [2/5]

template<class t_cst , class t_pat_iter >
t_cst::size_type sdsl::count ( const t_cst &  cst,
t_pat_iter  begin,
t_pat_iter  end,
cst_tag   
)

Counts the number of occurrences of a pattern in a CST.

Template Parameters
t_cstCST type.
t_pat_iterPattern iterator type.
Parameters
cstThe CST object.
beginIterator to the begin of the pattern (inclusive).
endIterator to the end of the pattern (exclusive).
Returns
The number of occurrences of the pattern in the CSA.
Time complexity
$ \Order{ t_{backward\_search} } $

Definition at line 115 of file suffix_tree_algorithm.hpp.

◆ count() [3/5]

template<class t_csx >
t_csx::size_type sdsl::count ( const t_csx &  csx,
const typename t_csx::string_type &  pat 
)

Counts the number of occurrences of a pattern in a CSA.

Template Parameters
t_csaCSA type.
Parameters
csaThe CSA object.
patThe pattern.
Returns
The number of occurrences of the pattern in the CSA.
Time complexity
$ \Order{ t_{backward\_search} } $

Definition at line 495 of file suffix_array_algorithm.hpp.

◆ count() [4/5]

template<class t_csx , class t_pat_iter >
t_csx::size_type sdsl::count ( const t_csx &  csx,
t_pat_iter  begin,
t_pat_iter  end 
)

Definition at line 476 of file suffix_array_algorithm.hpp.

◆ count() [5/5]

template<typename t_k2_treap >
uint64_t sdsl::count ( const t_k2_treap &  treap,
k2_treap_ns::point_type  p1,
k2_treap_ns::point_type  p2 
)

Count how many points are in the rectangle (p1,p2)

Parameters
treapk2-treap
p1Lower left corner of the rectangle.
p2Upper right corner of the rectangle.
Returns
The number of points in rectangle (p1,p2).
Precondition
real(p1) <= real(p2) and imag(p1)<=imag(p2)

Definition at line 300 of file k2_treap_algorithm.hpp.

◆ create_C_array()

template<class tWT >
void sdsl::create_C_array ( std::vector< uint64_t > &  C,
const tWT &  wt 
)

Definition at line 66 of file construct_lcp_helper.hpp.

◆ create_html_header()

std::string sdsl::create_html_header ( const char *  file_name)
inline

Definition at line 124 of file structure_tree.hpp.

◆ create_js_body()

std::string sdsl::create_js_body ( const std::string &  jsonsize)
inline

Definition at line 148 of file structure_tree.hpp.

◆ create_mem_html_header()

std::string sdsl::create_mem_html_header ( )
inline

Definition at line 67 of file memory_management.hpp.

◆ create_mem_js_body()

std::string sdsl::create_mem_js_body ( const std::string &  jsonObject)
inline

Definition at line 87 of file memory_management.hpp.

◆ csXprintf()

template<typename t_idx >
void sdsl::csXprintf ( std::ostream &  out,
const std::string &  format,
const t_idx &  idx,
char  sentinel = default_sentinel<t_idx>::value 
)

Prints members of CSAs and CSTs.

This is a printf like method to write members of CSAs and CSTs into an outstream.

Template Parameters
t_idxType of the index. Class should be of concept csa_tag or cst_tag.
Parameters
outOutput stream.
formatFormat string. See explanation below.
idxCSA or CST object.
sentinelCharacter which should replace the 0-symbol in BWT/ TEXT.
Format string
Each line of the output will be formatted according to the format string. All content, except tokens which start with % will be copied. Tokens which start with % will be replaced as follows (let w be a positive number. setw(w) is used to format single numbers):

Token | Replacement | Comment

%[w]I | Row index i. | %[w]S | SA[i] | %[w]s | ISA[i] | %[w]P | PSI[i] | %[w]p | LF[i] | %[w]L | LCP[i] | only for CSTs %[w]B | BWT[i] | %[w[:W]]T | Print min(idx.size(),w) chars of each | | suffix, each char formatted by setw(W).| %% | % |

Definition at line 533 of file io.hpp.

◆ disk_file_name()

std::string sdsl::disk_file_name ( const std::string &  file)
inline

Returns for a RAM-file the corresponding disk file name.

Definition at line 184 of file ram_fs.hpp.

◆ divsufsort()

template<typename saidx_t >
int32_t sdsl::divsufsort ( const uint8_t *  T,
saidx_t *  SA,
saidx_t  n 
)

Definition at line 2128 of file divsufsort.hpp.

◆ divsufsort64()

int32_t sdsl::divsufsort64 ( const uint8_t *  T,
int64_t *  SA,
int64_t  n 
)
inline

Definition at line 2208 of file divsufsort.hpp.

◆ empty()

bool sdsl::empty ( const range_type r)
inline

Empty range check.

Parameters
rRange to check
Returns
True if the range is empty, false otherwise.

Definition at line 782 of file wt_helper.hpp.

◆ extract() [1/6]

template<class t_csa >
t_csa::string_type sdsl::extract ( const t_csa &  csa,
typename t_csa::size_type  begin,
typename t_csa::size_type  end,
SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type  x = csa_tag() 
)

Reconstructs the substring T[begin..end] of the original text T to text[0..end-begin+1].

Template Parameters
t_racRandom access container which should hold the result.
t_csaCSA type.
Parameters
csaThe CSA object.
beginPosition of the first character which should be extracted (inclusive).
endPosition of the last character which should be extracted (inclusive).
Returns
A t_rac object holding the extracted text.
Precondition
$begin <= end$ and $ end < csa.size() $
Time complexity
$ \Order{ (end-begin+1) \cdot t_{\Psi} + t_{SA^{-1}} } $

Definition at line 657 of file suffix_array_algorithm.hpp.

◆ extract() [2/6]

template<class t_csa , class t_text_iter >
t_csa::size_type sdsl::extract ( const t_csa &  csa,
typename t_csa::size_type  begin,
typename t_csa::size_type  end,
t_text_iter  text,
lf_tag   
)

Specialization of extract for LF-function based CSAs.

Definition at line 598 of file suffix_array_algorithm.hpp.

◆ extract() [3/6]

template<class t_csa , class t_text_iter >
t_csa::size_type sdsl::extract ( const t_csa &  csa,
typename t_csa::size_type  begin,
typename t_csa::size_type  end,
t_text_iter  text,
psi_tag   
)

Specialization of extract for $\Psi$-function based CSAs.

Definition at line 625 of file suffix_array_algorithm.hpp.

◆ extract() [4/6]

template<class t_csa , class t_text_iter >
t_csa::size_type sdsl::extract ( const t_csa &  csa,
typename t_csa::size_type  begin,
typename t_csa::size_type  end,
t_text_iter  text,
SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type  x = csa_tag() 
)

Writes the substring T[begin..end] of the original text T to text[0..end-begin+1].

Template Parameters
t_csaCSA type.
t_text_iterRandom access iterator type.
Parameters
csaThe CSA object.
beginPosition of the first character which should be extracted (inclusive).
endPosition of the last character which should be extracted (inclusive).
textRandom access iterator pointing to the start of an container, which can hold at least (end-begin+1) character.
Returns
The length of the extracted text.
Precondition
$begin <= end$ and $ end < csa.size() $
Time
complexity $ \Order{ (end-begin+1) \cdot t_{\Psi} + t_{SA^{-1}} } $

Definition at line 584 of file suffix_array_algorithm.hpp.

◆ extract() [5/6]

template<class t_cst >
t_cst::csa_type::string_type sdsl::extract ( const t_cst &  cst,
const typename t_cst::node_type &  v,
SDSL_UNUSED typename std::enable_if< std::is_same< cst_tag, typename t_cst::index_category >::value, cst_tag >::type  x = cst_tag() 
)

Calculate the concatenation of edge labels from the root to the node v of of c CST.

Template Parameters
t_racRandom access container which should hold the result.
t_cstCSA type.
Parameters
cstThe CST object.
Returns
A t_rac object holding the extracted edge label.
The string of the concatenated edge labels from the root to the node v.

Definition at line 187 of file suffix_tree_algorithm.hpp.

◆ extract() [6/6]

template<class t_cst , class t_text_iter >
t_cst::size_type sdsl::extract ( const t_cst &  cst,
const typename t_cst::node_type &  v,
t_text_iter  text,
SDSL_UNUSED typename std::enable_if< std::is_same< cst_tag, typename t_cst::index_category >::value, cst_tag >::type  x = cst_tag() 
)

Calculate the concatenation of edge labels from the root to the node v of a CST.

Template Parameters
t_cstCST type.
t_text_iterRandom access iterator type.
Parameters
cstThe CST object.
vThe node where the concatenation of the edge label ends.
textRandom access iterator pointing to the start of an container, which can hold at least (end-begin+1) character.
Returns
The length of the extracted edge label.
Precondition
text has to be initialized with enough memory ( $
cst.depth(v)+1$ bytes) to hold the extracted text.

Definition at line 158 of file suffix_tree_algorithm.hpp.

◆ first_row_symbol()

template<typename t_csa >
t_csa::char_type sdsl::first_row_symbol ( const typename t_csa::size_type  i,
const t_csa &  csa 
)

Get the symbol at position i in the first row of the sorted suffixes of CSA.

Definition at line 29 of file suffix_array_helper.hpp.

◆ floor_log2()

constexpr size_t sdsl::floor_log2 ( size_t const  n)
constexpr

Definition at line 26 of file rank_support_int.hpp.

◆ foot_update()

void sdsl::foot_update ( mm_block_t ptr,
size_t  size 
)
inline

Definition at line 306 of file memory_management.hpp.

◆ forward_search() [1/4]

template<class t_csa , class t_pat_iter >
t_csa::size_type sdsl::forward_search ( const t_csa &  csa,
typename t_csa::size_type  l,
typename t_csa::size_type  r,
t_pat_iter  begin,
t_pat_iter  end,
typename t_csa::size_type &  l_res,
typename t_csa::size_type &  r_res,
SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type  x = csa_tag() 
)

Forward search for a pattern in an $\omega$-interval $[\ell..r]$ in the CSA.

Template Parameters
t_csaA CSA type.
t_pat_iterPattern iterator type.
Parameters
csaThe CSA object.
lLeft border of the lcp-interval $ [\ell..r]$.
rRight border of the lcp-interval $ [\ell..r]$.
beginIterator to the begin of the pattern (inclusive).
endIterator to the end of the pattern (exclusive).
l_resNew left border.
r_resNew right border.
Returns
The size of the new interval [\ell_{new}..r_{new}]. Equals zero, if no match is found.

Definition at line 37 of file suffix_array_algorithm.hpp.

◆ forward_search() [2/4]

template<class t_csa >
t_csa::size_type sdsl::forward_search ( const t_csa &  csa,
typename t_csa::size_type  l,
typename t_csa::size_type  r,
typename t_csa::char_type  c,
typename t_csa::size_type &  l_res,
typename t_csa::size_type &  r_res,
SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type  x = csa_tag() 
)

Forward search for a character c in an $\omega$-interval $[\ell..r]$ in the CSA.

Template Parameters
t_csaCSA type.
Parameters
csaThe CSA object.
lLeft border of the interval $ [\ell..r]$.
rRight border of the interval $ [\ell..r]$.
cCharacter to be prepended to $\omega$.
l_resNew left border.
r_resRight border.
Returns
The size of the new interval [\ell_{new}..r_{new}]. Equals zero, if no match is found.

Definition at line 119 of file suffix_array_algorithm.hpp.

◆ forward_search() [3/4]

template<class t_cst >
t_cst::size_type sdsl::forward_search ( const t_cst &  cst,
typename t_cst::node_type &  v,
const typename t_cst::size_type  d,
const typename t_cst::char_type  c,
typename t_cst::size_type &  char_pos,
SDSL_UNUSED typename std::enable_if< std::is_same< cst_tag, typename t_cst::index_category >::value, cst_tag >::type  x = cst_tag() 
)

Forward search for a character c on the path on depth $d$ to node $v$.

Parameters
cstThe CST object
vThe node at the endpoint of the current edge.
dThe current depth of the path starting with 0.
cThe character c which should be matched with pathlabel_{root()..v}[d]
char_posT[char_pos-d+1..char_pos] matches with the already matched pattern P[0..d-1] or d=0 => char_pos=0.
Returns
The number of the matching substrings in T.
Time complexity
$ \Order{ t_{\Psi} } $ or $ \Order{t_{cst.child}} $

Definition at line 33 of file suffix_tree_algorithm.hpp.

◆ forward_search() [4/4]

template<class t_cst , class t_pat_iter >
t_cst::size_type sdsl::forward_search ( const t_cst &  cst,
typename t_cst::node_type &  v,
typename t_cst::size_type  d,
t_pat_iter  begin,
t_pat_iter  end,
typename t_cst::size_type &  char_pos,
SDSL_UNUSED typename std::enable_if< std::is_same< cst_tag, typename t_cst::index_category >::value, cst_tag >::type  x = cst_tag() 
)

Forward search for a pattern pat on the path on depth $d$ to node $v$.

Parameters
cstThe compressed suffix tree.
vThe node at the endpoint of the current edge.
dThe current depth of the path. 0 = first character on each edge of the root node.
patThe character c which should be matched at the path on depth $d$ to node $v$.
char_posOne position in the text, which corresponds to the text that is already matched. If v=cst.root() and d=0 => char_pos=0.
Time complexity
$ \Order{ t_{\Psi} } $ or $ \Order{t_{cst.child}} $

Definition at line 80 of file suffix_tree_algorithm.hpp.

◆ get_char_pos()

template<class t_csa >
t_csa::size_type sdsl::get_char_pos ( typename t_csa::size_type  idx,
typename t_csa::size_type  d,
const t_csa &  csa 
)

Definition at line 357 of file suffix_tree_helper.hpp.

◆ H0()

template<class t_cst >
double sdsl::H0 ( const typename t_cst::node_type &  v,
const t_cst &  cst 
)

Calculate the zeroth order entropy of the text that follows a certain substring s.

Parameters
vA suffix tree node v. The label of the path from the root to v is s.
cstThe suffix tree of v.
Returns
The zeroth order entropy of the concatenation of all characters that follow s in the original text.

Definition at line 209 of file suffix_tree_algorithm.hpp.

◆ Hk()

template<class t_cst >
std::pair< double, size_t > sdsl::Hk ( const t_cst &  cst,
typename t_cst::size_type  k 
)

Calculate the k-th order entropy of a text.

Parameters
cstThe suffix tree.
kParameter k for which H_k should be calculated.
Returns
H_k and the number of contexts.

Definition at line 232 of file suffix_tree_algorithm.hpp.

◆ init_char_bitvector() [1/2]

template<typename bit_vector_type , typename size_type >
void sdsl::init_char_bitvector ( bit_vector_type &  char_bv,
const std::map< size_type, size_type > &  D 
)

Definition at line 535 of file csa_alphabet_strategy.hpp.

◆ init_char_bitvector() [2/2]

template<typename t_hi_bit_vector , typename t_select_1 , typename t_select_0 , typename size_type >
void sdsl::init_char_bitvector ( sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > &  char_bv,
const std::map< size_type, size_type > &  D 
)

Definition at line 545 of file csa_alphabet_strategy.hpp.

◆ insert_lcp_values()

void sdsl::insert_lcp_values ( int_vector<> &  partial_lcp,
bit_vector index_done,
std::string  lcp_file,
uint64_t  max_lcp_value,
uint64_t  lcp_value_offset 
)
inline

Merges a partial LCP array into the LCP array on disk.

Parameters
partial_lcpVector containing LCP values for all indexes $i$ with index_done[i] == 0. Let x=partail_lcp[rank(index_done, i, 0)]; LCP[i]=x if x!=0 and index_done[i] == 0
lcp_filePath to the LCP array on disk.
index_doneEntry index_done[i] indicates if LCP[i] is already calculated.
max_lcp_valueMaximum known LCP value
lcp_value_offsetLargest LCP value in lcp_file

Definition at line 26 of file construct_lcp_helper.hpp.

◆ intersect()

template<class t_wt >
std::vector< std::pair< typename t_wt::value_type, typename t_wt::size_type > > sdsl::intersect ( const t_wt &  wt,
const std::vector< range_type > &  ranges,
typename t_wt::size_type  t = 0 
)

Intersection of elements in WT[s_0,e_0], WT[s_1,e_1],...,WT[s_k,e_k].

Parameters
wtThe wavelet tree object.
rangesThe ranges.
tThreshold in how many distinct ranges the value has to be present. Default: t=ranges.size()
Returns
A vector containing (value, frequency) - of value which are contained in t different ranges. Frequency = accumulated frequencies in all ranges. The tuples are ordered according to value, if t_wt::lex_ordered=1.

Definition at line 36 of file wt_algorithm.hpp.

◆ interval_symbols()

template<class t_wt >
void sdsl::interval_symbols ( const t_wt &  wt,
typename t_wt::size_type  i,
typename t_wt::size_type  j,
typename t_wt::size_type &  k,
std::vector< typename t_wt::value_type > &  cs,
std::vector< typename t_wt::size_type > &  rank_c_i,
std::vector< typename t_wt::size_type > &  rank_c_j 
)

For each symbol c in wt[i..j-1] get rank(i,c) and rank(j,c).

Parameters
iThe start index (inclusive) of the interval.
jThe end index (exclusive) of the interval.
kReference for number of different symbols in [i..j-1].
csReference to a vector that will contain in cs[0..k-1] all symbols that occur in [i..j-1] in ascending order.
rank_c_iReference to a vector which equals rank_c_i[p] = rank(i,cs[p]), for $ 0 \leq p < k $.
rank_c_jReference to a vector which equals rank_c_j[p] = rank(j,cs[p]), for $ 0 \leq p < k $.
Time complexity
$ \Order{\min{\sigma, k \log \sigma}} $
Precondition
$ i \leq j \leq size() $ $ cs.size() \geq \sigma $ $ rank_{c_i}.size() \geq \sigma $ $ rank_{c_j}.size() \geq \sigma $

Definition at line 218 of file wt_algorithm.hpp.

◆ is_ram_file() [1/2]

bool sdsl::is_ram_file ( const int  fd)
inline

Determines if the given file is a RAM-file.

Definition at line 168 of file ram_fs.hpp.

◆ is_ram_file() [2/2]

bool sdsl::is_ram_file ( const std::string &  file)
inline

Determines if the given file is a RAM-file.

Definition at line 158 of file ram_fs.hpp.

◆ key_bwt()

template<uint8_t int_width>
constexpr const char * sdsl::key_bwt ( )
constexpr

Definition at line 71 of file csa_alphabet_strategy.hpp.

◆ key_bwt< 8 >()

template<>
constexpr const char * sdsl::key_bwt< 8 > ( )
inlineconstexpr

Definition at line 83 of file csa_alphabet_strategy.hpp.

◆ key_text()

template<uint8_t int_width>
constexpr const char * sdsl::key_text ( )
constexpr

Definition at line 65 of file csa_alphabet_strategy.hpp.

◆ key_text< 8 >()

template<>
constexpr const char * sdsl::key_text< 8 > ( )
inlineconstexpr

Definition at line 77 of file csa_alphabet_strategy.hpp.

◆ lex_interval()

template<typename t_csx , typename t_pat_iter >
auto sdsl::lex_interval ( const t_csx &  csx,
t_pat_iter  begin,
t_pat_iter  end 
) -> std::array<typename t_csx::size_type, 2>

Returns the lexicographic interval of a pattern in the SA.

Template Parameters
t_csxType of CSA/CST.
t_pat_iterType of pattern iterator.
Parameters
csxCSA or CST object.
beginIterator to the begin of the pattern.
endIterator to the end (exlusive) of the pattern.
Returns
The interval in the SA in which all suffixes are prefixed by the given pattern.

Definition at line 514 of file suffix_array_algorithm.hpp.

◆ load() [1/3]

template<typename X >
void sdsl::load ( std::vector< X > &  x,
std::istream &  in 
)

Definition at line 168 of file io.hpp.

◆ load() [2/3]

template<typename X >
std::enable_if< has_load< X >::value, void >::type sdsl::load ( X &  x,
std::istream &  in 
)

Definition at line 154 of file io.hpp.

◆ load() [3/3]

template<typename X >
std::enable_if< std::is_standard_layout< X >::value &&std::is_trivial< X >::value, void >::type sdsl::load ( X &  x,
std::istream &  in 
)

Definition at line 160 of file io.hpp.

◆ load_from_cache()

template<typename T >
bool sdsl::load_from_cache ( T &  v,
const std::string &  key,
const cache_config config,
bool  add_type_hash = false 
)

Definition at line 711 of file io.hpp.

◆ load_from_checked_file()

template<typename T >
bool sdsl::load_from_checked_file ( T &  v,
const std::string &  file 
)

Definition at line 916 of file io.hpp.

◆ load_from_file()

template<typename T >
bool sdsl::load_from_file ( T &  v,
const std::string &  file 
)

Load sdsl-object v from a file.

Parameters
vsdsl-
fileName of the serialized file.

Definition at line 901 of file io.hpp.

◆ load_lcp() [1/5]

template<class t_lcp , class t_cst >
void sdsl::load_lcp ( t_lcp &  lcp,
std::istream &  in,
const t_cst &  ,
lcp_plain_tag   
)

Definition at line 134 of file lcp.hpp.

◆ load_lcp() [2/5]

template<class t_lcp , class t_cst >
void sdsl::load_lcp ( t_lcp &  lcp,
std::istream &  in,
const t_cst &  cst 
)

Definition at line 127 of file lcp.hpp.

◆ load_lcp() [3/5]

template<class t_lcp , class t_cst >
void sdsl::load_lcp ( t_lcp &  lcp,
std::istream &  in,
const t_cst &  cst,
lcp_permuted_tag   
)

Definition at line 140 of file lcp.hpp.

◆ load_lcp() [4/5]

template<class t_lcp , class t_cst >
void sdsl::load_lcp ( t_lcp &  lcp,
std::istream &  in,
const t_cst &  cst,
lcp_tree_and_lf_compressed_tag   
)

Definition at line 152 of file lcp.hpp.

◆ load_lcp() [5/5]

template<class t_lcp , class t_cst >
void sdsl::load_lcp ( t_lcp &  lcp,
std::istream &  in,
const t_cst &  cst,
lcp_tree_compressed_tag   
)

Definition at line 146 of file lcp.hpp.

◆ load_vector()

template<typename T >
void sdsl::load_vector ( std::vector< T > &  vec,
std::istream &  in 
)

Load all elements of a vector from a input stream.

Parameters
vecVector whose elements should be loaded.
inInput stream.
Note
The vector has to be resized prior the loading of its elements.

Definition at line 404 of file io.hpp.

◆ load_vector_from_file()

template<typename t_int_vec >
bool sdsl::load_vector_from_file ( t_int_vec &  v,
const std::string &  file,
uint8_t  num_bytes = 1,
uint8_t  max_int_width = 64 
)

from disk.

Definition at line 187 of file io.hpp.

◆ locate() [1/3]

template<class t_csa , class t_pat_iter , class t_rac = int_vector<64>>
t_rac sdsl::locate ( const t_csa &  csa,
t_pat_iter  begin,
t_pat_iter  end,
SDSL_UNUSED typename std::enable_if< std::is_same< csa_tag, typename t_csa::index_category >::value, csa_tag >::type  x = csa_tag() 
)

Calculates all occurrences of a pattern pat in a CSA.

Template Parameters
t_csaCSA type.
t_pat_iterPattern iterator type.
t_racResizeable random access container.
Parameters
csaThe CSA object.
beginIterator to the begin of the pattern (inclusive).
endIterator to the end of the pattern (exclusive).
Returns
A vector containing the occurrences of the pattern in the CSA.
Time complexity
$ \Order{ t_{backward\_search} + z \cdot t_{SA} } $, where $z$ is the number of occurrences of pattern in the CSA.

Definition at line 537 of file suffix_array_algorithm.hpp.

◆ locate() [2/3]

template<class t_cst , class t_pat_iter , class t_rac = int_vector<64>>
t_rac sdsl::locate ( const t_cst &  cst,
t_pat_iter  begin,
t_pat_iter  end,
SDSL_UNUSED typename std::enable_if< std::is_same< cst_tag, typename t_cst::index_category >::value, cst_tag >::type  x = cst_tag() 
)

Calculates all occurrences of a pattern pat in a CST.

Template Parameters
t_cstCST type.
t_pat_iterPattern iterator type.
t_racResizeable random access container.
Parameters
cstThe CST object.
beginIterator to the begin of the pattern (inclusive).
endIterator to the end of the pattern (exclusive).
Returns
A vector containing the occurrences of the pattern in the CST.
Time complexity
$ \Order{ t_{backward\_search} + z \cdot t_{SA} } $, where $z$ is the number of occurrences of pattern in the CST.

Definition at line 136 of file suffix_tree_algorithm.hpp.

◆ locate() [3/3]

template<class t_csx , class t_rac = int_vector<64>>
t_rac sdsl::locate ( const t_csx &  csx,
const typename t_csx::string_type &  pat 
)

Calculates all occurrences of a pattern pat in a CSA/CST.

Template Parameters
t_csaCSA/CST type.
t_racResizeable random access container.
Parameters
csaThe CSA/CST object.
patThe pattern.
Returns
A vector containing the occurrences of the pattern in the CSA.
Time complexity
$ \Order{ t_{backward\_search} + z \cdot t_{SA} } $, where $z$ is the number of occurrences of pattern in the CSA.

Definition at line 565 of file suffix_array_algorithm.hpp.

◆ memory_monitor_record()

void sdsl::memory_monitor_record ( int64_t  delta)
inline

Definition at line 343 of file memory_tracking.hpp.

◆ move_lcp() [1/5]

template<class t_lcp , class t_cst >
void sdsl::move_lcp ( t_lcp &&  lcp,
t_lcp &&  lcp_c,
const t_cst &  ,
lcp_plain_tag   
)

Definition at line 99 of file lcp.hpp.

◆ move_lcp() [2/5]

template<class t_lcp , class t_cst >
void sdsl::move_lcp ( t_lcp &&  lcp,
t_lcp &&  lcp_c,
const t_cst &  cst 
)

Definition at line 92 of file lcp.hpp.

◆ move_lcp() [3/5]

template<class t_lcp , class t_cst >
void sdsl::move_lcp ( t_lcp &&  lcp,
t_lcp &&  lcp_c,
const t_cst &  cst,
lcp_permuted_tag   
)

Definition at line 105 of file lcp.hpp.

◆ move_lcp() [4/5]

template<class t_lcp , class t_cst >
void sdsl::move_lcp ( t_lcp &&  lcp,
t_lcp &&  lcp_c,
const t_cst &  cst,
lcp_tree_and_lf_compressed_tag   
)

Definition at line 119 of file lcp.hpp.

◆ move_lcp() [5/5]

template<class t_lcp , class t_cst >
void sdsl::move_lcp ( t_lcp &&  lcp,
t_lcp &&  lcp_c,
const t_cst &  cst,
lcp_tree_compressed_tag   
)

Definition at line 112 of file lcp.hpp.

◆ near_bwd_excess()

uint64_t sdsl::near_bwd_excess ( const bit_vector bp,
uint64_t  i,
bit_vector::difference_type  rel,
const uint64_t  block_size 
)
inline

Near backward excess.

Definition at line 526 of file bp_support_algorithm.hpp.

◆ near_enclose()

uint64_t sdsl::near_enclose ( const bit_vector bp,
uint64_t  i,
const uint64_t  block_size 
)
inline

Find the opening parenthesis of the enclosing pair if this parenthesis is near.

Parameters
bpbit_vector containing the representation of the balanced parentheses sequence.
iPosition of the opening parenthesis for which we search the position of the opening parenthesis of the enclosing parentheses pair.
block_sizeNumber of entries to search for the corresponding opening parenthesis of the enclosing parentheses pair.
Returns
If no near enclose exists return i, otherwise the position of the opening parenthesis of the enclosing pair.
Precondition
We assert that $ bp[i]=1 $

Definition at line 660 of file bp_support_algorithm.hpp.

◆ near_find_close()

uint64_t sdsl::near_find_close ( const bit_vector bp,
const uint64_t  i,
const uint64_t  block_size 
)
inline

Definition at line 343 of file bp_support_algorithm.hpp.

◆ near_find_closing()

uint64_t sdsl::near_find_closing ( const bit_vector bp,
uint64_t  i,
uint64_t  closings,
const uint64_t  block_size 
)
inline

Definition at line 386 of file bp_support_algorithm.hpp.

◆ near_find_open()

uint64_t sdsl::near_find_open ( const bit_vector bp,
uint64_t  i,
const uint64_t  block_size 
)
inline

Definition at line 569 of file bp_support_algorithm.hpp.

◆ near_find_opening()

uint64_t sdsl::near_find_opening ( const bit_vector bp,
uint64_t  i,
const uint64_t  openings,
const uint64_t  block_size 
)
inline

Definition at line 609 of file bp_support_algorithm.hpp.

◆ near_fwd_excess()

uint64_t sdsl::near_fwd_excess ( const bit_vector bp,
uint64_t  i,
bit_vector::difference_type  rel,
const uint64_t  block_size 
)
inline

Definition at line 429 of file bp_support_algorithm.hpp.

◆ near_rmq()

uint64_t sdsl::near_rmq ( const bit_vector bp,
uint64_t  l,
uint64_t  r,
bit_vector::difference_type min_rel_ex 
)
inline

Calculate the position with minimal excess value in the interval [l..r].

Parameters
bpThe bit_vector which represents the parentheses sequence
lThe left border of the interval.
rThe right border of the interval.
min_rel_exReference to the relative minimal excess value with regards to excess(bp[l])

Definition at line 471 of file bp_support_algorithm.hpp.

◆ near_rmq_open()

uint64_t sdsl::near_rmq_open ( const bit_vector bp,
const uint64_t  begin,
const uint64_t  end 
)
inline

Definition at line 676 of file bp_support_algorithm.hpp.

◆ operator!=()

template<typename T , typename U >
bool sdsl::operator!= ( const track_allocator< T > &  a,
const track_allocator< U > &  b 
)
inline

Definition at line 91 of file memory_tracking.hpp.

◆ operator+() [1/3]

template<class t_int_vector >
int_vector_const_iterator< t_int_vector > sdsl::operator+ ( typename int_vector_const_iterator< t_int_vector >::difference_type  n,
const int_vector_const_iterator< t_int_vector > &  it 
)
inline

Definition at line 1407 of file int_vector.hpp.

◆ operator+() [2/3]

template<class t_int_vector >
int_vector_iterator< t_int_vector > sdsl::operator+ ( typename int_vector_iterator< t_int_vector >::difference_type  n,
const int_vector_iterator< t_int_vector > &  it 
)
inline

Definition at line 1243 of file int_vector.hpp.

◆ operator+() [3/3]

template<class t_rac >
random_access_const_iterator< t_rac > sdsl::operator+ ( typename random_access_const_iterator< t_rac >::difference_type  n,
const random_access_const_iterator< t_rac > &  it 
)
inline

Definition at line 136 of file iterators.hpp.

◆ operator-() [1/2]

template<class t_int_vector >
int_vector_const_iterator< t_int_vector >::difference_type sdsl::operator- ( const int_vector_const_iterator< t_int_vector > &  x,
const int_vector_const_iterator< t_int_vector > &  y 
)
inline

Definition at line 1399 of file int_vector.hpp.

◆ operator-() [2/2]

template<class t_rac >
random_access_const_iterator< t_rac >::difference_type sdsl::operator- ( const random_access_const_iterator< t_rac > &  x,
const random_access_const_iterator< t_rac > &  y 
)
inline

Definition at line 127 of file iterators.hpp.

◆ operator<<() [1/9]

template<class t_int >
std::ostream & sdsl::operator<< ( std::ostream &  os,
const bp_interval< t_int > &  interval 
)
inline

Definition at line 1331 of file cst_sct3.hpp.

◆ operator<<() [2/9]

std::ostream & sdsl::operator<< ( std::ostream &  os,
const louds_node v 
)
inline

Definition at line 45 of file louds_tree.hpp.

◆ operator<<() [3/9]

template<typename t_int >
std::enable_if< std::is_integral< t_int >::value, std::ostream & >::type sdsl::operator<< ( std::ostream &  os,
const std::vector< t_int > &  v 
)
inline

Definition at line 967 of file io.hpp.

◆ operator<<() [4/9]

template<class t_bv >
std::enable_if< std::is_same< typenamet_bv::index_category, bv_tag >::value, std::ostream & >::type sdsl::operator<< ( std::ostream &  os,
const t_bv &  bv 
)
inline

Definition at line 1415 of file int_vector.hpp.

◆ operator<<() [5/9]

template<typename t_iv >
std::enable_if< std::is_same< typenamet_iv::index_category, iv_tag >::valueorstd::is_same< typenamet_iv::index_category, csa_tag >::valueorstd::is_same< typenamet_iv::index_category, lcp_tag >::value, std::ostream & >::type sdsl::operator<< ( std::ostream &  os,
const t_iv &  v 
)
inline

Definition at line 943 of file io.hpp.

◆ operator<<() [6/9]

template<typename t_iv >
std::enable_if< std::is_same< typenamet_iv::index_category, wt_tag >::value, std::ostream & >::type sdsl::operator<< ( std::ostream &  os,
const t_iv &  v 
)
inline

Definition at line 955 of file io.hpp.

◆ operator<<() [7/9]

template<typename t_iv >
std::enable_if< std::is_same< typenamet_iv::category, csa_member_tag >::value, std::ostream & >::type sdsl::operator<< ( std::ostream &  os,
const t_iv &  v 
)
inline

Definition at line 980 of file io.hpp.

◆ operator<<() [8/9]

std::ostream & sdsl::operator<< ( std::ostream &  os,
const uint128_t x 
)
inline

Definition at line 220 of file uint128_t.hpp.

◆ operator<<() [9/9]

std::ostream & sdsl::operator<< ( std::ostream &  os,
const uint256_t x 
)
inline

Definition at line 261 of file uint256_t.hpp.

◆ operator==()

template<typename T , typename U >
bool sdsl::operator== ( const track_allocator< T > &  ,
const track_allocator< U > &   
)
inline

Definition at line 85 of file memory_tracking.hpp.

◆ output_event_json()

void sdsl::output_event_json ( std::ostream &  out,
const mm_event ev,
const tracker_storage m 
)
inline

Definition at line 23 of file memory_management.hpp.

◆ output_tab()

void sdsl::output_tab ( std::ostream &  out,
size_t  level 
)
inline

Definition at line 24 of file structure_tree.hpp.

◆ power_of_two()

template<class T >
constexpr bool sdsl::power_of_two ( x)
constexpr

Definition at line 29 of file bit_vector_il.hpp.

◆ push_back_m_index()

template<class size_type_class >
void sdsl::push_back_m_index ( size_type_class  i,
uint8_t  c,
tLI(&)  m_list[256],
uint8_t(&)  m_chars[256],
size_type_class &  m_char_count 
)

Definition at line 188 of file construct_lcp_helper.hpp.

◆ push_front_m_index()

template<class size_type_class >
void sdsl::push_front_m_index ( size_type_class  i,
uint8_t  c,
tLI(&)  m_list[256],
uint8_t(&)  m_chars[256],
size_type_class &  m_char_count 
)

Definition at line 177 of file construct_lcp_helper.hpp.

◆ quantile_freq()

template<class t_wt >
std::pair< typename t_wt::value_type, typename t_wt::size_type > sdsl::quantile_freq ( const t_wt &  wt,
typename t_wt::size_type  lb,
typename t_wt::size_type  rb,
typename t_wt::size_type  q 
)

Returns the q-th smallest element and its frequency in wt[lb..rb].

Parameters
wtThe wavelet tree.
lbLeft array bound in T
rbRight array bound in T
qq-th largest element ('quantile'), 0-based indexed.

Definition at line 103 of file wt_algorithm.hpp.

◆ ram_file_name()

std::string sdsl::ram_file_name ( const std::string &  file)
inline

Returns the corresponding RAM-file name for file.

Definition at line 174 of file ram_fs.hpp.

◆ range_3d()

template<typename t_k2_treap >
k2_treap_ns::range_iterator< t_k2_treap > sdsl::range_3d ( const t_k2_treap &  t,
k2_treap_ns::point_type  p1,
k2_treap_ns::point_type  p2,
k2_treap_ns::range_type  range 
)

Get iterator for all points in rectangle (p1,p2) with weights in range.

Parameters
treapk2-treap
p1Lower left corner of the rectangle
p2Upper right corner of the rectangle
rangeRange {w1,w2}.
Returns
Iterator to list of all points in the range.
Precondition
real(p1) <= real(p2) and imag(p1)<=imag(p2) real(range) <= imag(range)

Definition at line 276 of file k2_treap_algorithm.hpp.

◆ read_member()

template<typename T >
void sdsl::read_member ( T &  t,
std::istream &  in 
)

Definition at line 111 of file io.hpp.

◆ read_member< std::string >()

template<>
void sdsl::read_member< std::string > ( std::string &  t,
std::istream &  in 
)
inline

Definition at line 118 of file io.hpp.

◆ register_cache_file()

void sdsl::register_cache_file ( const std::string &  key,
cache_config config 
)
inline

Register the existing resource specified by the key to the cache.

Parameters
keyResource key.
configCache configuration.

Note: If the resource does not exist under the given key, it will be not added to the cache configuration.

Definition at line 656 of file io.hpp.

◆ remove()

int sdsl::remove ( const std::string &  file)
inline

Remove a file.

Definition at line 194 of file ram_fs.hpp.

◆ remove_from_cache()

template<typename T >
bool sdsl::remove_from_cache ( const std::string &  key,
cache_config config,
bool  add_type_hash = false 
)

Definition at line 758 of file io.hpp.

◆ rename()

int sdsl::rename ( const std::string &  old_filename,
const std::string &  new_filename 
)
inline

Rename a file.

Definition at line 204 of file ram_fs.hpp.

◆ restricted_unique_range_values()

template<class t_wt >
std::vector< typename t_wt::value_type > sdsl::restricted_unique_range_values ( const t_wt &  wt,
typename t_wt::size_type  x_i,
typename t_wt::size_type  x_j,
typename t_wt::value_type  y_i,
typename t_wt::value_type  y_j 
)

Returns for a x range [x_i,x_j] and a value range [y_i,y_j] all unique y values occuring in [x_i,x_j] in ascending order.

Parameters
x_ilower bound of the x range
x_jupper bound of the x range
y_ilower bound of the y range
y_jupper bound of the y range
Returns
a vector of increasing y values occuring in the range [x_i,x_j]

Definition at line 546 of file wt_algorithm.hpp.

◆ serialize() [1/3]

template<typename X >
uint64_t sdsl::serialize ( const std::vector< X > &  x,
std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
)

Definition at line 144 of file io.hpp.

◆ serialize() [2/3]

template<typename X >
std::enable_if< has_serialize< X >::value, typenameX::size_type >::type sdsl::serialize ( const X &  x,
std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
)

Definition at line 131 of file io.hpp.

◆ serialize() [3/3]

template<typename X >
std::enable_if< std::is_standard_layout< X >::value &&std::is_trivial< X >::value, uint64_t >::type sdsl::serialize ( const X &  x,
std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
)

Definition at line 138 of file io.hpp.

◆ serialize_empty_object()

template<typename T >
size_t sdsl::serialize_empty_object ( std::ostream &  ,
structure_tree_node v = nullptr,
std::string  name = "",
const T *  t = nullptr 
)

Definition at line 325 of file io.hpp.

◆ serialize_vector()

template<typename T >
uint64_t sdsl::serialize_vector ( const std::vector< T > &  vec,
std::ostream &  out,
sdsl::structure_tree_node v,
std::string  name 
)

Serialize each element of an std::vector.

Parameters
vecThe vector which should be serialized.
outOutput stream to which should be written.
vStructure tree node. Note: If all elements have the same structure, then it is tried to combine all elements (i.e. make one node w with size set to the cumulative sum of all sizes of the children)

Definition at line 376 of file io.hpp.

◆ set_lcp_pointer() [1/5]

template<class t_lcp , class t_cst >
void sdsl::set_lcp_pointer ( t_lcp &  ,
const t_cst &  ,
lcp_plain_tag   
)

Definition at line 166 of file lcp.hpp.

◆ set_lcp_pointer() [2/5]

template<class t_lcp , class t_cst >
void sdsl::set_lcp_pointer ( t_lcp &  lcp,
const t_cst &  cst 
)

Definition at line 159 of file lcp.hpp.

◆ set_lcp_pointer() [3/5]

template<class t_lcp , class t_cst >
void sdsl::set_lcp_pointer ( t_lcp &  lcp,
const t_cst &  cst,
lcp_permuted_tag   
)

Definition at line 170 of file lcp.hpp.

◆ set_lcp_pointer() [4/5]

template<class t_lcp , class t_cst >
void sdsl::set_lcp_pointer ( t_lcp &  lcp,
const t_cst &  cst,
lcp_tree_and_lf_compressed_tag   
)

Definition at line 182 of file lcp.hpp.

◆ set_lcp_pointer() [5/5]

template<class t_lcp , class t_cst >
void sdsl::set_lcp_pointer ( t_lcp &  lcp,
const t_cst &  cst,
lcp_tree_compressed_tag   
)

Definition at line 176 of file lcp.hpp.

◆ size()

int_vector::size_type sdsl::size ( const range_type r)
inline

Size of a range.

Parameters
rRange to check
Returns
True if the range is empty, false otherwise.

Definition at line 787 of file wt_helper.hpp.

◆ size_in_bytes()

template<typename T >
T::size_type sdsl::size_in_bytes ( const T &  t)

Get the size of a data structure in bytes.

Parameters
vA reference to the data structure for which the size in bytes should be calculated.

Definition at line 778 of file io.hpp.

◆ size_in_mega_bytes()

template<typename T >
double sdsl::size_in_mega_bytes ( const T &  t)

Get the size of a data structure in mega bytes (MiB).

Parameters
tA reference to the data structure for which the size in bytes should be calculated.

Definition at line 785 of file io.hpp.

◆ sort_typeBstar()

template<typename saidx_t >
saidx_t sdsl::sort_typeBstar ( const uint8_t *  T,
saidx_t *  SA,
saidx_t *  bucket_A,
saidx_t *  bucket_B,
saidx_t  n 
)
inline

Definition at line 1799 of file divsufsort.hpp.

◆ ss_blockswap()

template<typename saidx_t >
void sdsl::ss_blockswap ( saidx_t *  a,
saidx_t *  b,
saidx_t  n 
)
inline

Definition at line 557 of file divsufsort.hpp.

◆ ss_compare()

template<typename saidx_t >
int32_t sdsl::ss_compare ( const uint8_t *  T,
const saidx_t *  p1,
const saidx_t *  p2,
saidx_t  depth 
)
inline

Definition at line 193 of file divsufsort.hpp.

◆ ss_fixdown()

template<typename saidx_t >
void sdsl::ss_fixdown ( const uint8_t *  Td,
const saidx_t *  PA,
saidx_t *  SA,
saidx_t  i,
saidx_t  size 
)
inline

Definition at line 234 of file divsufsort.hpp.

◆ ss_heapsort()

template<typename saidx_t >
void sdsl::ss_heapsort ( const uint8_t *  Td,
const saidx_t *  PA,
saidx_t *  SA,
saidx_t  size 
)
inline

Definition at line 255 of file divsufsort.hpp.

◆ ss_ilg() [1/2]

int32_t sdsl::ss_ilg ( int32_t  n)
inline

Definition at line 115 of file divsufsort.hpp.

◆ ss_ilg() [2/2]

int32_t sdsl::ss_ilg ( int64_t  n)
inline

Definition at line 127 of file divsufsort.hpp.

◆ ss_inplacemerge()

template<typename saidx_t >
void sdsl::ss_inplacemerge ( const uint8_t *  T,
const saidx_t *  PA,
saidx_t *  first,
saidx_t *  middle,
saidx_t *  last,
saidx_t  depth 
)
inline

Definition at line 612 of file divsufsort.hpp.

◆ ss_insertionsort()

template<typename saidx_t >
void sdsl::ss_insertionsort ( const uint8_t *  T,
const saidx_t *  PA,
saidx_t *  first,
saidx_t *  last,
saidx_t  depth 
)
inline

Definition at line 209 of file divsufsort.hpp.

◆ ss_isqrt()

template<typename saidx_t >
saidx_t sdsl::ss_isqrt ( saidx_t  x)
inline

Definition at line 163 of file divsufsort.hpp.

◆ ss_median3()

template<typename saidx_t >
saidx_t * sdsl::ss_median3 ( const uint8_t *  Td,
const saidx_t *  PA,
saidx_t *  v1,
saidx_t *  v2,
saidx_t *  v3 
)
inline

Definition at line 283 of file divsufsort.hpp.

◆ ss_median5()

template<typename saidx_t >
saidx_t * sdsl::ss_median5 ( const uint8_t *  Td,
const saidx_t *  PA,
saidx_t *  v1,
saidx_t *  v2,
saidx_t *  v3,
saidx_t *  v4,
saidx_t *  v5 
)
inline

Definition at line 300 of file divsufsort.hpp.

◆ ss_mergebackward()

template<typename saidx_t >
void sdsl::ss_mergebackward ( const uint8_t *  T,
const saidx_t *  PA,
saidx_t *  first,
saidx_t *  middle,
saidx_t *  last,
saidx_t *  buf,
saidx_t  depth 
)
inline

Definition at line 740 of file divsufsort.hpp.

◆ ss_mergeforward()

template<typename saidx_t >
void sdsl::ss_mergeforward ( const uint8_t *  T,
const saidx_t *  PA,
saidx_t *  first,
saidx_t *  middle,
saidx_t *  last,
saidx_t *  buf,
saidx_t  depth 
)
inline

Definition at line 670 of file divsufsort.hpp.

◆ ss_mintrosort()

template<typename saidx_t >
void sdsl::ss_mintrosort ( const uint8_t *  T,
const saidx_t *  PA,
saidx_t *  first,
saidx_t *  last,
saidx_t  depth 
)
inline

Definition at line 366 of file divsufsort.hpp.

◆ ss_partition()

template<typename saidx_t >
saidx_t * sdsl::ss_partition ( const saidx_t *  PA,
saidx_t *  first,
saidx_t *  last,
saidx_t  depth 
)
inline

Definition at line 347 of file divsufsort.hpp.

◆ ss_pivot()

template<typename saidx_t >
saidx_t * sdsl::ss_pivot ( const uint8_t *  Td,
const saidx_t *  PA,
saidx_t *  first,
saidx_t *  last 
)
inline

Definition at line 321 of file divsufsort.hpp.

◆ ss_rotate()

template<typename saidx_t >
void sdsl::ss_rotate ( saidx_t *  first,
saidx_t *  middle,
saidx_t *  last 
)
inline

Definition at line 564 of file divsufsort.hpp.

◆ ss_swapmerge()

template<typename saidx_t >
void sdsl::ss_swapmerge ( const uint8_t *  T,
const saidx_t *  PA,
saidx_t *  first,
saidx_t *  middle,
saidx_t *  last,
saidx_t *  buf,
saidx_t  bufsize,
saidx_t  depth 
)
inline

Definition at line 885 of file divsufsort.hpp.

◆ sssort()

template<typename saidx_t >
void sdsl::sssort ( const uint8_t *  T,
const saidx_t *  PA,
saidx_t *  first,
saidx_t *  last,
saidx_t *  buf,
saidx_t  bufsize,
saidx_t  depth,
saidx_t  n,
int32_t  lastsuffix 
)

Definition at line 988 of file divsufsort.hpp.

◆ store_to_cache()

template<typename T >
bool sdsl::store_to_cache ( const T &  v,
const std::string &  key,
cache_config config,
bool  add_type_hash = false 
)

Stores the object v as a resource in the cache.

Parameters

Definition at line 737 of file io.hpp.

◆ store_to_checked_file() [1/3]

bool sdsl::store_to_checked_file ( const char *  v,
const std::string &  file 
)
inline

Definition at line 830 of file io.hpp.

◆ store_to_checked_file() [2/3]

template<uint8_t t_width>
bool sdsl::store_to_checked_file ( const int_vector< t_width > &  v,
const std::string &  file 
)

Definition at line 882 of file io.hpp.

◆ store_to_checked_file() [3/3]

template<typename T >
bool sdsl::store_to_checked_file ( const T &  t,
const std::string &  file 
)

Definition at line 813 of file io.hpp.

◆ store_to_file() [1/4]

bool sdsl::store_to_file ( const char *  v,
const std::string &  file 
)
inline

Specialization of store_to_file for a char array.

Definition at line 283 of file io.hpp.

◆ store_to_file() [2/4]

template<uint8_t t_width>
bool sdsl::store_to_file ( const int_vector< t_width > &  v,
const std::string &  file 
)

Specialization of store_to_file for int_vector.

Definition at line 864 of file io.hpp.

◆ store_to_file() [3/4]

bool sdsl::store_to_file ( const std::string &  v,
const std::string &  file 
)
inline

Definition at line 847 of file io.hpp.

◆ store_to_file() [4/4]

template<typename T >
bool sdsl::store_to_file ( const T &  v,
const std::string &  file 
)

Store a data structure to a file.

The data structure has to provide a serialize function.

Parameters
vData structure to store.
fileName of the file where to store the data structure.
Returnif the data structure was stored successfully

Definition at line 798 of file io.hpp.

◆ store_to_plain_array()

template<typename int_type , typename t_int_vec >
bool sdsl::store_to_plain_array ( t_int_vec &  v,
const std::string &  file 
)

Store an int_vector as plain int_type array to disk.

Definition at line 306 of file io.hpp.

◆ swap() [1/7]

template<>
void sdsl::swap ( bool &  x,
int_vector_reference< bit_vector y 
)
inlinenoexcept

Definition at line 1037 of file int_vector.hpp.

◆ swap() [2/7]

template<uint8_t t_width>
void sdsl::swap ( int_vector< t_width > &  v1,
int_vector< t_width > &  v2 
)
noexcept

Definition at line 1502 of file int_vector.hpp.

◆ swap() [3/7]

template<>
void sdsl::swap ( int_vector_reference< bit_vector x,
bool &  y 
)
inlinenoexcept

Definition at line 1047 of file int_vector.hpp.

◆ swap() [4/7]

template<>
void sdsl::swap ( int_vector_reference< bit_vector x,
int_vector_reference< bit_vector y 
)
inlinenoexcept

Definition at line 1027 of file int_vector.hpp.

◆ swap() [5/7]

template<class t_int_vector >
void sdsl::swap ( int_vector_reference< t_int_vector >  x,
int_vector_reference< t_int_vector >  y 
)
inlinenoexcept

Definition at line 946 of file int_vector.hpp.

◆ swap() [6/7]

template<class t_int_vector >
void sdsl::swap ( int_vector_reference< t_int_vector >  x,
typename int_vector_reference< t_int_vector >::value_type &  y 
)
inlinenoexcept

Definition at line 967 of file int_vector.hpp.

◆ swap() [7/7]

template<class t_int_vector >
void sdsl::swap ( typename int_vector_reference< t_int_vector >::value_type &  x,
int_vector_reference< t_int_vector >  y 
)
inlinenoexcept

Definition at line 956 of file int_vector.hpp.

◆ symbol_gte()

template<class t_wt >
std::pair< bool, typename t_wt::value_type > sdsl::symbol_gte ( const t_wt &  wt,
typename t_wt::value_type  c 
)

Returns for a symbol c the next larger or equal symbol in the WT.

Parameters
cthe symbol
Returns
A pair. The first element of the pair consititues if a valid answer was found (true) or no valid answer (false) could be found. The second element contains the found symbol.

Definition at line 529 of file wt_algorithm.hpp.

◆ symbol_lte()

template<class t_wt >
std::pair< bool, typename t_wt::value_type > sdsl::symbol_lte ( const t_wt &  wt,
typename t_wt::value_type  c 
)

Returns for a symbol c the previous smaller or equal symbol in the WT.

Parameters
cthe symbol
Returns
A pair. The first element of the pair consititues if a valid answer was found (true) or no valid answer (false) could be found. The second element contains the found symbol.

Definition at line 514 of file wt_algorithm.hpp.

◆ tmp_file() [1/2]

std::string sdsl::tmp_file ( const cache_config config,
std::string  name_part = "" 
)
inline

Returns a name for a temporary file. I.e. the name was not used before.

Definition at line 698 of file io.hpp.

◆ tmp_file() [2/2]

std::string sdsl::tmp_file ( const std::string &  filename,
std::string  name_part = "" 
)
inline

Returns a name for a temporary file. I.e. the name was not used before.

Definition at line 704 of file io.hpp.

◆ top_k()

template<typename t_k2_treap >
k2_treap_ns::top_k_iterator< t_k2_treap > sdsl::top_k ( const t_k2_treap &  t,
k2_treap_ns::point_type  p1,
k2_treap_ns::point_type  p2 
)

Get iterator for all heaviest points in rectangle (p1,p2) in decreasing order.

Parameters
treapk2-treap
p1Lower left corner of the rectangle
p2Upper right corner of the rectangle
Returns
Iterator to result in decreasing order.
Precondition
real(p1) <= real(p2) and imag(p1)<=imag(p2)

Definition at line 259 of file k2_treap_algorithm.hpp.

◆ tr_copy()

template<typename saidx_t >
void sdsl::tr_copy ( saidx_t *  ISA,
const saidx_t *  SA,
saidx_t *  first,
saidx_t *  a,
saidx_t *  b,
saidx_t *  last,
saidx_t  depth 
)
inline

Definition at line 1330 of file divsufsort.hpp.

◆ tr_fixdown()

template<typename saidx_t >
void sdsl::tr_fixdown ( const saidx_t *  ISAd,
saidx_t *  SA,
saidx_t  i,
saidx_t  size 
)
inline

Definition at line 1110 of file divsufsort.hpp.

◆ tr_heapsort()

template<typename saidx_t >
void sdsl::tr_heapsort ( const saidx_t *  ISAd,
saidx_t *  SA,
saidx_t  size 
)
inline

Definition at line 1131 of file divsufsort.hpp.

◆ tr_ilg() [1/2]

int32_t sdsl::tr_ilg ( int32_t  n)
inline

Definition at line 1072 of file divsufsort.hpp.

◆ tr_ilg() [2/2]

int32_t sdsl::tr_ilg ( int64_t  n)
inline

Definition at line 1078 of file divsufsort.hpp.

◆ tr_insertionsort()

template<typename saidx_t >
void sdsl::tr_insertionsort ( const saidx_t *  ISAd,
saidx_t *  first,
saidx_t *  last 
)
inline

Definition at line 1090 of file divsufsort.hpp.

◆ tr_introsort()

template<typename saidx_t >
void sdsl::tr_introsort ( saidx_t *  ISA,
const saidx_t *  ISAd,
saidx_t *  SA,
saidx_t *  first,
saidx_t *  last,
trbudget_t< saidx_t > *  budget 
)
inline

Definition at line 1416 of file divsufsort.hpp.

◆ tr_median3()

template<typename saidx_t >
saidx_t * sdsl::tr_median3 ( const saidx_t *  ISAd,
saidx_t *  v1,
saidx_t *  v2,
saidx_t *  v3 
)
inline

Definition at line 1159 of file divsufsort.hpp.

◆ tr_median5()

template<typename saidx_t >
saidx_t * sdsl::tr_median5 ( const saidx_t *  ISAd,
saidx_t *  v1,
saidx_t *  v2,
saidx_t *  v3,
saidx_t *  v4,
saidx_t *  v5 
)
inline

Definition at line 1175 of file divsufsort.hpp.

◆ tr_partialcopy()

template<typename saidx_t >
void sdsl::tr_partialcopy ( saidx_t *  ISA,
const saidx_t *  SA,
saidx_t *  first,
saidx_t *  a,
saidx_t *  b,
saidx_t *  last,
saidx_t  depth 
)
inline

Definition at line 1357 of file divsufsort.hpp.

◆ tr_partition()

template<typename saidx_t >
void sdsl::tr_partition ( const saidx_t *  ISAd,
saidx_t *  first,
saidx_t *  middle,
saidx_t *  last,
saidx_t **  pa,
saidx_t **  pb,
saidx_t  v 
)
inline

Definition at line 1259 of file divsufsort.hpp.

◆ tr_pivot()

template<typename saidx_t >
saidx_t * sdsl::tr_pivot ( const saidx_t *  ISAd,
saidx_t *  first,
saidx_t *  last 
)
inline

Definition at line 1196 of file divsufsort.hpp.

◆ trbudget_check()

template<typename saidx_t >
int32_t sdsl::trbudget_check ( trbudget_t< saidx_t > *  budget,
saidx_t  size 
)
inline

Definition at line 1241 of file divsufsort.hpp.

◆ trbudget_init()

template<typename saidx_t >
void sdsl::trbudget_init ( trbudget_t< saidx_t > *  budget,
saidx_t  chance,
saidx_t  incval 
)
inline

Definition at line 1234 of file divsufsort.hpp.

◆ trsort()

template<typename saidx_t >
void sdsl::trsort ( saidx_t *  ISA,
saidx_t *  SA,
saidx_t  n,
saidx_t  depth 
)
inline

Definition at line 1747 of file divsufsort.hpp.

◆ write_mem_log()

template<format_type F>
void sdsl::write_mem_log ( std::ostream &  out,
const tracker_storage m 
)

◆ write_mem_log< HTML_FORMAT >()

template<>
void sdsl::write_mem_log< HTML_FORMAT > ( std::ostream &  out,
const tracker_storage m 
)
inline

Definition at line 218 of file memory_management.hpp.

◆ write_mem_log< JSON_FORMAT >()

template<>
void sdsl::write_mem_log< JSON_FORMAT > ( std::ostream &  out,
const tracker_storage m 
)
inline

Definition at line 47 of file memory_management.hpp.

◆ write_member()

template<typename T >
size_t sdsl::write_member ( const T &  t,
std::ostream &  out,
sdsl::structure_tree_node v = nullptr,
std::string  name = "" 
)

Definition at line 84 of file io.hpp.

◆ write_member< std::string >()

template<>
size_t sdsl::write_member< std::string > ( const std::string &  t,
std::ostream &  out,
sdsl::structure_tree_node v,
std::string  name 
)
inline

Definition at line 95 of file io.hpp.

◆ write_structure() [1/3]

template<format_type F, typename X >
void sdsl::write_structure ( const X &  x,
std::ostream &  out 
)

Definition at line 410 of file io.hpp.

◆ write_structure() [2/3]

template<format_type F, typename X >
void sdsl::write_structure ( const X &  x,
std::string  file 
)

Definition at line 422 of file io.hpp.

◆ write_structure() [3/3]

template<format_type F, typename... Xs>
void sdsl::write_structure ( std::ostream &  out,
Xs...  xs 
)

Definition at line 429 of file io.hpp.

◆ write_structure_tree()

template<format_type F>
void sdsl::write_structure_tree ( const structure_tree_node v,
std::ostream &  out,
size_t  level = 0 
)

◆ write_structure_tree< HTML_FORMAT >()

template<>
void sdsl::write_structure_tree< HTML_FORMAT > ( const structure_tree_node v,
std::ostream &  out,
SDSL_UNUSED size_t  level 
)
inline

Definition at line 350 of file structure_tree.hpp.

◆ write_structure_tree< JSON_FORMAT >()

template<>
void sdsl::write_structure_tree< JSON_FORMAT > ( const structure_tree_node v,
std::ostream &  out,
size_t  level 
)
inline

Definition at line 84 of file structure_tree.hpp.

Variable Documentation

◆ sdsl_version

std::string const sdsl::sdsl_version
Initial value:
= std::to_string(sdsl_version_major) + "." + std::to_string(sdsl_version_minor) + "." +
std::to_string(sdsl_version_patch)

The full version as std::string.

Definition at line 34 of file version.hpp.

◆ sdsl_version_major

constexpr uint8_t sdsl::sdsl_version_major = SDSL_VERSION_MAJOR
constexpr

The major version.

Definition at line 27 of file version.hpp.

◆ sdsl_version_minor

constexpr uint8_t sdsl::sdsl_version_minor = SDSL_VERSION_MINOR
constexpr

The minor version.

Definition at line 29 of file version.hpp.

◆ sdsl_version_patch

constexpr uint8_t sdsl::sdsl_version_patch = SDSL_VERSION_PATCH
constexpr

The patch version.

Definition at line 31 of file version.hpp.