Hacker News new | past | comments | ask | show | jobs | submit login

Could you describe your implementation of this tree in more detail in the repo? I think it's really interesting part of your project.



It is actually not very novel. It is just a Fenwick tree[1]. And a Fenwick tree is basically a rope where the leafs don't store any text.

basically every leaf holds some metrics (say bytes and line endings) for some chunk of text. By just looking at the leaf we don't know which chunk it points to. But since the leafs are all in order, we can calculate their byte position and line ending by adding them up. If we add all the leaf we should get the total number of bytes and lines in the text. In order to avoid O(n) cost of summing every leaf, we store them in a tree, where each parent holds the sums of it's children. So when we want to find the byte position[2] of a particular line ending we can just walk down the tree and see if the line ending we are searching for is greater then the left child or not. If it is, we add the left child's sum to our running total and go to the right. Otherwise we go to the left. By the time we get to the leaf, we have summed all the chunks before it in O(logn) time.

Insertion/deletion are similar, except when we update the leaf, we also go and update each parent on the way back up.

[1] https://www.baeldung.com/cs/fenwick-tree

[2] https://github.com/CeleritasCelery/rune/blob/be243ea2bd385ec...




Consider applying for YC's W25 batch! Applications are open till Nov 12.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: