Building a 205 MB wavelet matrix using WaveletMatrix::from_ints temporarily consumes 3.9 GB memory, which may be too much for small VMs. Is there a way to reduce memory consumption while constructing a wavelet matrix?

This PR uses CompactVector instead of Vec for buffers in WaveletMatrixBuilder, allowing us to specify the minimum number of bits to store an input integer for working memory efficiency.

I measured the peak resident set size during constructing WaveletMatrix from $2^{26}$ random bytes (code is here).

# v0.5.0
$ /usr/bin/time ../target/release/wmb
[bench/src/wmb.rs:16] wm.len() = 67108864
4.09user 0.41system 0:04.52elapsed 99%CPU (0avgtext+0avgdata 1152920maxresident)k
0inputs+0outputs (0major+35199minor)pagefaults 0swaps

# New version (will be v0.6.0)
$ /usr/bin/time ../target/release/wmb
[bench/src/wmb.rs:17] wm.len() = 67108864
5.83user 0.10system 0:05.93elapsed 99%CPU (0avgtext+0avgdata 244280maxresident)k
0inputs+0outputs (0major+68665minor)pagefaults 0swaps

The working memory was reduced from 1.1 GB to 0.24 GB, although the speed was slower.

In this PR, I removed the function WaveletMatrix::from_ints() because this can lead to a memory inefficient construction way.

Current APIs contain some redundant functions. For example, EliasFano::from_bits and EliasFano::from_bitvec can be generalized.

For maintenance cost, such functions should be unified.

The current version implements input iterators taking references such as EliasFano::from_bits.

But, for primitive types, call-by-value is enough and call-by-reference would not be useful.

In the previous version, the library implements serialization/deserialization with Serde.

This PR removed the dependency and added some alternative functions.

Basically, sucds does not recommend to use unsafe approaches such as get_unchecked because deserialization from any data is supported, making it easy to build data structures that contain invalid values.

However, unsafe approaches can be safely used to some parts by prechecking.

Related to #13

There are several implementations of rank/select bit vector data structure, and some of them have already been / will be implemented in this library.

Since there are data structures, like wavelet matrix, uses rank/select bit vector as a building block, it is better that implementing trait for rank/select bit vector as below and let user be able to choose concrete implementations:

trait RsBitVector {
    fn rank0(&self, pos: usize) -> usize;
    fn rank1(&self, pos: usize) -> usize;
    fn select0(&self, k: usize) -> usize;
    fn select1(&self, k: usize) -> usize;
...
}

@kampersanda How do you think about above? If it is roughly OK, I will create PR to discuss this more concretely.

SSIA

This would be accomplished by porting https://github.com/ot/succinct/blob/master/bp_vector.hpp, although it is necessary to understand the data structure first.