Implement rank/select bit vector trait

[hirosassa]

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.

[kampersanda]

@hirosassa Thank you for your suggestion! As you said, such traits are essential for scaling up the crate, not only for rank/select on bit vectors but also for compressed integer vectors, selection data structures and so on.

But, this library currently contains only RsBitVector for rank/select queries on bit vectors, so that trait is not needed immediately. I think it is better to introduce the trait after implementing other equivalent rank/select data structures such as RRR, because, if the trait is implemented but no other rank/select queries are implemented, the trait may become a negative legacy.

NOTE: If we were to implement such traits, it would be better to separate rank and select queries as follows, because there are also data structures that support only one of the queries such as DArray.

trait Ranker {
    fn rank0(&self, pos: usize) -> usize;
    fn rank1(&self, pos: usize) -> usize;
}

trait Selector {
    fn select0(&self, k: usize) -> usize;
    fn select1(&self, k: usize) -> usize;
}

[hirosassa]

I think it is better to introduce the trait after implementing other equivalent rank/select data structures

Agreed 👍 So, I'll implement RRR first. Thanks for the rapid response!

[kampersanda]

Many thanks!