simongog/sdsl-lite — pull request #176 by simongog (2014-03-19 01:46:23+00:00)
Title: Optimize cst sct3 for large alphabet

cst_sct3 can now support fast ops on int alphabets.

Methods `degree()`, `lca(v,w)`, `parent()`, `select_child(v,i)`, `sl(v)`
used a linear scan of at most `degree()` bits. For byte alphabets this
was just a lookup in 4 64-bit words. For integer alphabets in the
multi-millions the scan slows down the operations.
The result of the scan can also be calculated in constant time with
the help of a rank and select structure. I have now added the
possibility to specify the rank and select structure, so that the
operations are still fast on very large alphabets.

The structure is still ABI backward compatible for byte-alphabet
CSTs. Notice: The ABI changed for integer-alphabets.