Implemented succinct data structures

Due to the generic classes in the library it is easy to create instances which corresponds to complex succinct data structures which were described in literature. Here is a list of examples:

• The compressed suffix array (Kunihiko Sadakane: New text indexing functionalities of the compressed suffix arrays. J. Algorithms 48(2): 294-313 (2003)). Corresponding sdsl class: csa_sada

• The run-length encoded succinct suffix array (Veli Mäkinen, Gonzalo Navarro: Succinct Suffix Arrays Based on Run-Length Encoding. CPM 2005: 45-56). Corresponding sdsl class: csa_wt, the choice of sd_vector for the two bit vectors is the best in terms of space.

• A compressed suffix tree (Kunihiko Sadakane: Compressed Suffix Trees with Full Functionality. Theory Comput. Syst. 41(4): 589-607 (2007)). Corresponding sdsl class: cst_sada.

• Another compressed suffix tree (Enno Ohlebusch, Johannes Fischer, Simon Gog: CST++. SPIRE 2010: 322-333). Corresponding sdsl class: cst_sct3

• Another compressed suffix tree (Enno Ohlebusch, Simon Gog: A Compressed Enhanced Suffix Array Supporting Fast String Matching. SPIRE 2009: 51-62). Corresponding sdsl class: cst_sct2

• The FM-index (Paolo Ferragina, Giovanni Manzini: Opportunistic Data Structures with Applications. FOCS 2000: 390-398). Corresponding sdsl class: csa_wt

• Succinct representation of LCP information (Kunihiko Sadakane: Succinct representations of lcp information and improvements in the compressed suffix arrays. SODA 2002: 225-232). Corresponding sdsl class: lcp_support_sada

• Support for operations on a sequence of balanced parentheses (Richard F. Geary, Naila Rahman, Rajeev Raman, Venkatesh Raman: A Simple Optimal Representation for Balanced Parentheses. CPM 2004: 159-172.). Corresponding sdsl class: bp_support_g

• Non-succinct range minimum/maximum data structure (Michael A. Bender and Martin Farach-Colton: The LCA Problem Revisited. LATIN 2000). Corresponding sdsl class: rmq_support_sparse_table (is used in the final recursion level of bp_support_g).

• Support for operations on a sequence of balanced parentheses (Kunihiko Sadakane: The Ultimate Balanced Parentheses".Technical Report 2008). Corresponding sdsl class: bp_support_sada.

• Sparse bitvector representation (Daisuke Okanohara, Kunihiko Sadakane: Practical Entropy-Compressed Rank/Select Dictionary. ALENEX 2007). Corresponding sdsl class sd_vector.

• Sparse bitvector representation (Rasmus Pagh: Low redundancy in dictionaries with O(1) worst case lookup time. TR BRICS-RS-98-28. Rajeev Raman, V. Raman and S. Srinivasa Rao: Succinct Indexable Dictionaries with Applications to representations of k-ary trees and multi-sets. SODA 2002). Corresponding sdsl class rrr_vector.

• ... and many more