List of Implemented Data Structures

• Bitvectors
  • An uncompressed mutual bitvector (bit_vector)
  • An uncompressed immutable bitvector (bit_vector_il)
  • A -compressed immutable bitvector (rrr_vector<>)
  • A bitvector for sparse populated arrays (sd_vector<>)
• Rank Support (RS) and Select Support (SS)
  • Several rank and select implementations with different time-space trade-offs for the uncompressed bitvectors (rank_support_v, rank_support_v5, select_support_mcl, ...)
  • Rank and select for compressed bitvectors (rank_support_rrr, rank_support_sd, ...)
• Variable-length Coders
  • Elias- coder (coder::elias_delta)
  • Elias- coder (coder::elias_gamma)
  • Fibonacci-coder (coder::fibonacci)
• Integer Vectors
  • Mutable vectors for (compile-time) fixed w-bit integers (int_vector)
  • Mutable vector for (run-time) fixed w-bit integers (int_vector<0>, w passed to the constructor)
  • Immutable compressed integer vectors using a variable-length coder coder (enc_vector, vlc_vector)
• Wavelet Trees (WT) (all immutable)
  • Balanced wavelet (wt_blcd)
  • Balanced wavelet tree for integer alphabets (wt_int)
  • Wavelet matrix for integer alphabets (wm_int)
  • Huffman-shaped wavelet tree (wt_huff)
  • Hu-Tucker-shaped wavelet tree (wt_hutu)
  • Run-length compressed wavelet tree (wt_rlmn)
  • Fast select wavelet tree for integer alphabets (wt_gmr)
• Compressed Suffix Arrays (CSA) (all immutable)
  • csa_bitcompressed is based on the bitcompressed SA and inverse SA.
  • csa_wt is based on a WT of the BWT.
  • csa_sada is based on the compressed -function
• Balanced Parentheses Support (BPS) (all immutable)
  • A range-min-max-tree implementation (bp_support_sada) to support operations find_open, find_close, enclose, double_enclose,...
  • Hierarchical solutions with pioneer parentheses (bp_support_g, bp_support_gg)
• Longest Common Prefix (LCP) Arrays (all immutable)
  • lcp_bitcompressed is a bitcompressed version
  • lcp_byte encodes small values with one byte and large values with two words
  • lcp_dac used direct accessible codes
  • lcp_wt stores small values in a WT and large value in on word.
  • lcp_vlc stores the values in a vlc_vector.
  • lcp_support_sada uses a bitvector of 2n bits, a select structure supporting it, and the corresponding CSA.
  • lcp_support_tree uses the topology of the corresponding CST.
  • lcp_support_tree2 uses the corresponding CSA and CST.
• Compressed Suffix Trees (CST) (all immutable)
  • cst_sada provides very fast navigation operations; worst case
    space |CSA|+|LCP|+4n+o(n)
  • cst_sct3 representing nodes as intervals in the suffix array; worst case space |CSA|+|LCP|+3n+o(n)
• Range Minimum/Maximum Query (RMQ) Structures (all immutable)
  • Self-contained RMQ structure using 2n+o(n) bits or 4n+o(n) bits (rmq_succinct_sct, rmq_succinct_sada)
  • Non-succinct support structure for RMQ (rmq_support_sparse_table)