Conversion between data structures and BitVec

[arnsholt]

I'm using vers-vecs for a project, and it's great, but one part of the project is shaping up to really, really want to be implemented in terms of taking a constructed tree and replacing a node with another tree, or replacing the children of a node with some other trees (this is looking down the line, so I'm not sure of the exact needs. Some cases I can work around, but some are looking like they really need to do this kind of stuff). Is this something you'd be open to considering a PR for?

I'm happy to write up a PR with a suggested implementation and such, but before getting into the weeds of that I thought some discussion would be good, since I assume you'll have opinions on the API, or maybe even don't want the functionality at all in the library.

An alternative which would make it possible to for users of the library to implement this kind of stuff on their own would be to make it possible to convert the succinct datatypes "backwards". For example for BpTree if it had a method like:

fn into_rsvec(self) -> RsVec {
    self.vec
}

and probably similar for RsVec -> BitVec, it'd be possible to compute the needed operations on the succinct structures, decay them to simpler datatypes, do the surgery required, and rebuild the succinct structures.

[Cydhra]

More implementations of From to convert the data structures back and forth are no problem to add, and then constructing new RsVecs from modified BitVec can be easily implemented on top.

Unfortunately that is the only way to modify the data structures. The RsVec implementation which is the base of all other data structures (except RMQ) is inherently static. So are the additional structures of BpTree. Dynamic versions of these data structures exist, but they are entirely different data structures, with different runtime guarantees and far more complicated. For example, a dynamic RsVec would be built atop a self-balancing search tree, and all operations are relaxed to O(log n).

Modifying the existing structures is pointless, as every modification requires rebuilding the support structures anyway, adding the same overhead as just rebuilding the data structure entirely, and to insert bits you'd also need to re-allocate the bitvector.

Therefore, adding more From traits is the only feasible way of modification.

[Cydhra]

It'd be great if you could include the merged version in your own project using a github-dependency and verify it all works as required by you, before I publish it :)

[arnsholt]

Yeah, it’s on my list. Unfortunately the last few days and this weekend have been kinda busy, but I think I’ll have some time on Monday to give it a spin.