If I understand well, you want an efficient rank function on a sequence, you are not particularly interested in B-trees.I have an implementation of balanced trees you might be interested into:It is a binary tree with a smart constructor to ensure only balanced trees are built.Beside that, no other constraints are applied. In particular these are not search trees although those can easily be implemented on top.O(1) access to the size (number of items) is provided, and as such an O(log n) rank function.Performance is also quite competitive: although I did not push the code yet, I implemented Map and Set from the standard library using these trees. On a small set of benchmarks I ran, these were at worst 10% slower than the standard ones.
On Wed, Nov 4, 2015 at 6:39 PM, Francois Berenger <francois.berenger@inria.fr> wrote:
Hello, I am looking for even a simple implementation with at least the following operations: insert/add, remove, mem/contains and at_rank. The at_rank is especially important since it is inefficient to implement it using fold in a set like the ones from the stdlib. Thanks a lot, F.--Caml-list mailing list. Subscription management and archives: https://sympa.inria.fr/sympa/arc/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs