SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
 All Classes Namespaces Files Functions Variables Typedefs Friends
File List
Here is a list of all documented files with brief descriptions:
sdsl/include/sdsl/algorithms.hpp [code]Algorithms.hpp contains algorithms for suffixarrays
sdsl/include/sdsl/algorithms_for_balanced_parentheses.hpp [code]Algorithms.hpp contains algorithms for balanced parentheses sequences
sdsl/include/sdsl/algorithms_for_compressed_suffix_arrays.hpp [code]Algorithms_for_compressed_suffix_arrays.hpp contains algorithms for compressed suffix arrays
sdsl/include/sdsl/algorithms_for_compressed_suffix_trees.hpp [code]Algorithms_for_compressed_suffix_trees.hpp contains algorithms for compressed suffix trees
sdsl/include/sdsl/algorithms_for_string_matching.hpp [code]Algorithms_for_string_matching.hpp contains algorithms for string matching like backward_search, ..
sdsl/include/sdsl/bit_vector_interleaved.hpp [code]Bit_vector_interleaved.hpp contains the sdsl::bit_vector_interleaved class, and classes which support rank and select for bit_vector_interleaved
sdsl/include/sdsl/bit_vectors.hpp [code]Bit_vectors.hpp contains classes for uncompressed and compressed bit vector representations
sdsl/include/sdsl/bitmagic.hpp [code]Bitmagic.hpp contains the sdsl::bit_magic class
sdsl/include/sdsl/bp_support.hpp [code]Bp_support.hpp contains several classed which support find_open, find_close, enclose and rr-enclose queries
sdsl/include/sdsl/bp_support_g.hpp [code]Bp_support_g.hpp contains an implementation of a balanced parentheses support data structure
sdsl/include/sdsl/bp_support_gg.hpp [code]Bp_support_gg.hpp contains an implementation of a balanced parentheses support data structure
sdsl/include/sdsl/bp_support_j.hpp [code]Bp_support_j.hpp contains an implementation of a balanced parentheses support data structure
sdsl/include/sdsl/bp_support_sada.hpp [code]Bp_support_sada.hpp contains an implementation of a balanced parentheses support data structure proposed by Kunihiko Sadakane in the paper "The Ultimate Balanced Parentheses"
sdsl/include/sdsl/bwt_construct.hpp [code]Bwt_construct.hpp contains a space and time efficient construction method for the Burrows and Wheeler Transform (BWT)
sdsl/include/sdsl/coder.hpp [code]Coder.hpp contains the coder namespace and includes the header files of sdsl::coder::fibonacci, sdsl::coder::elias_delta, sdsl::coder::ternary, and sdsl::coder::run_length
sdsl/include/sdsl/compatibility.hpp [code]
sdsl/include/sdsl/csa_construct.hpp [code]Csa_construct.hpp contains a space and time efficient construction method for csa_wt, csa_sada, csa_uncompressed
sdsl/include/sdsl/csa_sada.hpp [code]Csa_sada.hpp contains an implementation of the compressed suffix array
sdsl/include/sdsl/csa_sada_theo.hpp [code]Csa_sada_theo.hpp contains an implemenation of the compressed suffix array
sdsl/include/sdsl/csa_uncompressed.hpp [code]Csa_uncompressed.hpp contains an implementation of an uncompressed suffix array providing information of the suffix array, the inverse suffix array and the psi function
sdsl/include/sdsl/csa_wt.hpp [code]Csa_wt.hpp contains an implementation of the compressed suffix array based on a wavelet tree
sdsl/include/sdsl/cst3_sct3p.hpp [code]
sdsl/include/sdsl/cst_construct.hpp [code]Cst_construct.hpp contains a space and time efficient construction method for compressed suffix trees (cst)
sdsl/include/sdsl/cst_iterators.hpp [code]Cst_iterators.hpp contains iterator classes for traversing (compressed) suffix arrays
sdsl/include/sdsl/cst_sada.hpp [code]Cst_sada.hpp contains an implementation of the compressed suffix tree (CST)
sdsl/include/sdsl/cst_sct.hpp [code]Cst_sct.hpp contains an implementation of an compressed suffix tree (CST)
sdsl/include/sdsl/cst_sct2.hpp [code]Cst_sct2.hpp contains an implementation of an compressed suffix tree (CST)
sdsl/include/sdsl/cst_sct3.hpp [code]Cst_sct3.hpp contains an implementation of an compressed suffix tree (CST)
sdsl/include/sdsl/elias_delta_coder.hpp [code]Elias_delta_coder.hpp contains the class sdsl::coder::elias_delta
sdsl/include/sdsl/enc_vector.hpp [code]Enc_vector.hpp contains the sdsl::enc_vector class
sdsl/include/sdsl/enc_vector_dna.hpp [code]Enc_vector_dna.hpp contains the sdsl::enc_vector_dna class
sdsl/include/sdsl/enc_vector_prac2.hpp [code]Enc_vector_prac2.hpp contains the sdsl::enc_vector_prac2 class
sdsl/include/sdsl/enc_vector_theo.hpp [code]Enc_vector_theo.hpp contains the sdsl::enc_vector_theo class and the iterator class for enc_vector_theo
sdsl/include/sdsl/fast_cache.hpp [code]
sdsl/include/sdsl/fibonacci_coder.hpp [code]Fibonacci_coder.hpp contains the class sdsl::coder::fibonacci
sdsl/include/sdsl/gap_vector.hpp [code]Gap_vector.hpp contains the sdsl::gap_vector class, and classes which support rank and select for gap_vector
sdsl/include/sdsl/int_vector.hpp [code]
sdsl/include/sdsl/int_vector_io_wrappers.hpp [code]This file contains classes which could be used to encode and decode integer vectors when they are written to disk
sdsl/include/sdsl/isa_construct.hpp [code]Isa_construct.hpp contains a space and time efficient construction method for the inverse suffix array
sdsl/include/sdsl/iterators.hpp [code]Iterators.hpp contains an generic iterator for random access containers
sdsl/include/sdsl/lcp.hpp [code]Lcp.hpp contains classes for lcp information
sdsl/include/sdsl/lcp_bitcompressed.hpp [code]Lcp_bitcompressed.hpp contains an implementation of an uncompressed lcp array
sdsl/include/sdsl/lcp_construct.hpp [code]Lcp_construct.hpp contains a space and time efficient construction method for lcp arrays
sdsl/include/sdsl/lcp_dac.hpp [code]Lcp_dac.hpp contains an implementation of a (compressed) lcp array proposed by Brisaboa, Ladra and Navarro in the paper "Direct addressable variable-length codes" (SPIRE 2009)
sdsl/include/sdsl/lcp_kurtz.hpp [code]Lcp_kurtz.hpp contains an implementation of a (compressed) lcp array proposed by Stefan Kurtz
sdsl/include/sdsl/lcp_support_sada.hpp [code]Lcp_support_sada.hpp contains an implementation of a compressed lcp array
sdsl/include/sdsl/lcp_support_tree.hpp [code]
sdsl/include/sdsl/lcp_support_tree2.hpp [code]
sdsl/include/sdsl/lcp_vlc.hpp [code]
sdsl/include/sdsl/lcp_wt.hpp [code]Lcp_wt.hpp contains an implementation of a (compressed) lcp array proposed by Simon Gog based on the Wavelet Tree
sdsl/include/sdsl/louds_tree.hpp [code]Louds_tree.hpp contains a classes for the succinct tree representation LOUDS (level order unary degree sequence)
sdsl/include/sdsl/nearest_neighbour_dictionary.hpp [code]Nearest_neighbour_dictionary.hpp contains a class which supports rank/select for sparse populated sdsl::bit_vectors
sdsl/include/sdsl/nn_dict_dynamic.hpp [code]Nn_dict_dynamic.hpp contains a class for a dynamic bit vector which also supports the prev and next operations
sdsl/include/sdsl/rank_support.hpp [code]Rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information
sdsl/include/sdsl/rank_support_jmc.hpp [code]Rank_support_jmc.hpp contains classes that support a sdsl::bit_vector with constant time rank information
sdsl/include/sdsl/rank_support_v.hpp [code]Rank_support_v.hpp contains rank_support_v that support a sdsl::bit_vector with constant time rank information
sdsl/include/sdsl/rank_support_v5.hpp [code]Rank_support_v5.hpp contains rank_support_v5 that support a sdsl::bit_vector with constant time rank information
sdsl/include/sdsl/rmq_succinct_sada.hpp [code]Rmq_succinct_sada.hpp contains the class rmq_succinct_sada which supports range minimum or range maximum queries on a random access container in constant time and $4 n+o(n) bits$ space
sdsl/include/sdsl/rmq_succinct_sct.hpp [code]Rmq_succinct_sct.hpp contains the class rmq_succinct_sct which supports range minimum or range maximum queries on a random access container in constant time and $2 n+o(n) bits$ space
sdsl/include/sdsl/rmq_support.hpp [code]Rmq_support.hpp contains different range minimum support data structures
sdsl/include/sdsl/rmq_support_sparse_table.hpp [code]Rmq_support_sparse_table.hpp contains the class rmq_support_sparse_table which supports range minimum or range maximum queries on a random access container in constant time and $\Order{n\log^2 n} bits$ space. See paper LCP revisted of Bender and Farach
sdsl/include/sdsl/rrr_helper.hpp [code]Rrr_helper.hpp contains the sdsl::binomial class, a class which contains informations about the binomial coefficients
sdsl/include/sdsl/rrr_vector.hpp [code]Rrr_vector.hpp contains the sdsl::rrr_vector class, and classes which support rank and select for rrr_vector
sdsl/include/sdsl/rrr_vector_15.hpp [code]
sdsl/include/sdsl/sd_vector.hpp [code]Sd_vector.hpp contains the sdsl::sd_vector class, and classes which support rank and select for sd_vector
sdsl/include/sdsl/sdsl_concepts.hpp [code]
sdsl/include/sdsl/select_support.hpp [code]Select_support.hpp contains classes that support a sdsl::bit_vector with constant time select information
sdsl/include/sdsl/select_support_bs.hpp [code]Select_support_bs.hpp contains the select_support_bs class that support a sdsl::bit_vector with constant time select information
sdsl/include/sdsl/select_support_dummy.hpp [code]Select_support_dummy.hpp contains classes that support a sdsl::bit_vector with constant time select information
sdsl/include/sdsl/select_support_mcl.hpp [code]Select_support_mcl.hpp contains classes that support a sdsl::bit_vector with constant time select information
sdsl/include/sdsl/sorted_int_stack.hpp [code]Sorted_int_stack.hpp contains a data structure for a stack which can contain numbers in the range from $0$ to $n-1$ and the numbers on the stack are sorted in increasing order
sdsl/include/sdsl/sorted_multi_stack_support.hpp [code]Sorted_multi_stack_support.hpp contains a data structure for a stack which contains elements from [0..n] in sorted order. Duplicates are possible
sdsl/include/sdsl/sorted_stack_support.hpp [code]Sorted_stack_support.hpp contains a data structure for a stack which contains indices of a random access container and the elements of the indices are sorted in the stack order. This data structure was proposed by Johannes Fischer in the paper Wee LCP
sdsl/include/sdsl/structure_tree.hpp [code]Structure_tree.hpp contains a helper class which can represent the memory structure of a class
sdsl/include/sdsl/suffixarray_helper.hpp [code]Suffixarray_helper.hpp contains some helper classes for (compressed suffix arrays)
sdsl/include/sdsl/suffixarrays.hpp [code]Suffixarrays.hpp contains generic classes for different suffix array classes
sdsl/include/sdsl/suffixtrees.hpp [code]Suffixtrees.hpp contains generic classes for different suffix tree classes
sdsl/include/sdsl/temp_write_read_buffer.hpp [code]
sdsl/include/sdsl/template_class.hpp [code]Template_class.hpp contains a template for our own sdsl class
sdsl/include/sdsl/ternary_coder.hpp [code]Ternary_coder.hpp contains the class sdsl::coder::ternary
sdsl/include/sdsl/test_index_performance.hpp [code]Test_index_performance.hpp contains a set of functions which test the speed of operations of compressed suffix arrays and compressed suffix trees
sdsl/include/sdsl/testutils.hpp [code]Testutils.hpp contains a "stopwatch" class for performance meassurement of program pieces
sdsl/include/sdsl/tikz.hpp [code]
sdsl/include/sdsl/typedefs.hpp [code]
sdsl/include/sdsl/uint128_t.hpp [code]Uint128_t.hpp contains contains the definition of a 128-bit unsigned integer type
sdsl/include/sdsl/uint256_t.hpp [code]Uint256_t.hpp contains a class for 256-bit unsigned integers
sdsl/include/sdsl/util.hpp [code]Util.hpp contains some helper methods for int_vector and other stuff like demangle class names
sdsl/include/sdsl/vbyte_coder.hpp [code]
sdsl/include/sdsl/vectors.hpp [code]
sdsl/include/sdsl/vlc_vector.hpp [code]Vlc_vector.hpp contains a vector which stores the values with variable length codes
sdsl/include/sdsl/wavelet_trees.hpp [code]Wavelet_trees.hpp contains wavelet tree implementations
sdsl/include/sdsl/wt.hpp [code]Wt.hpp contains a generic class for the wavelet tree proposed first by Grossi et al. 2003 and applied to the BWT in Foschini et al. 2004
sdsl/include/sdsl/wt_fixed_block.hpp [code]
sdsl/include/sdsl/wt_helper.hpp [code]
sdsl/include/sdsl/wt_huff.hpp [code]Wt_huff.hpp contains a class for the wavelet tree of byte sequences which is in Huffman shape
sdsl/include/sdsl/wt_int.hpp [code]Wt_int.hpp contains a specialized class for a wavelet tree of a permutation of the numbers from 0..n. This wavelet tree class takes less memory than the generic class for wavelet trees
sdsl/include/sdsl/wt_rlg.hpp [code]Wt_rlg.hpp contains a class for the wavelet tree of byte sequences which is in Huffman shape and runs of character are compressed
sdsl/include/sdsl/wt_rlg8.hpp [code]Wt_rlg8.hpp contains a class for the wavelet tree of byte sequences which is in Huffman shape and runs of character are compressed
sdsl/include/sdsl/wt_rlmn.hpp [code]Wt_rlmn.hpp contains a class for a compressed wavelet tree. Compression is achieved by exploiting runs in the input sequence