Brolib-fs Alternatives

brolib-fs reviews and mentions

• Zed Decoded: Rope and SumTree
  4 projects | news.ycombinator.com | 28 Apr 2024

  I have a simple (well, simple by my standards because I've spent a long time with it) implementation of a rope in Standard ML [0], OCaml [1] and F# [2]. (See tiny_rope.sml, brolib.fs or lib/tiny_rope.ml for implementation if you can read any of those languages; the F# implementation is probably easiest to read.)

  [0] https://github.com/hummy123/brolib-sml

  [1] https://github.com/hummy123/brolib

  [2] https://github.com/hummy123/brolib-fs

  The essence of a data structure is a binary tree where the internal nodes (the N2 case) contains a pointer to the left subtree, an integer containing the total length of the strings in the left subtree and a pointer to the right subtree. Then there are leaf nodes (the N0 case) which contain simply strings. (There are some other cases in the type like N1, N3 and L2, but those are solely for balancing because I built my ropes on top of 1-2 Brother Trees as described by Ralf Hinze, and those aren't essential to the rope data structure.)

  When indexing (which is necessary for the insertion and deletion operations), you have a simple recursive algorithm which can be best seen in the recursive "ins" function. In the internal N2 nodes, the algorithm is to compare the index (given as an argument) with the left metadata. If the index argument is less than the left metadata, recurse to the left subtree passing the same index; otherwise, recurse to the right subtree, subtracting the index argument with the left metadata.

  By the end, when you eventually reach the leaf case, the index argument is equal to the position you want to insert into in the current node. (I haven't tried to understand the maths behind this but it's how the data structure works.) At that point, all you do is insert into the leaf node's string (this is the same as inserting at an arbitrary index in any normal string) and unroll the recursion. Unrolling the recursion involves updating the left subtree metadata when you reach the parent, and it also involves balancing. (I'm using 1-2 Brother Trees for balancing but ropes don't really care which balancing you use or if you use one at all.)

  That's pretty much all there is to ropes. The deletion and substring algorithms just require minor modifications (the user might specify a range that includes more than one subtree, so you might need to recurse on both subtrees).