Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I think this data structure is usually called a Counted B-tree https://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtr... instead of range tree


Xi has/had a rope library that allowed one to apply many monoids at each internal node. So one could search for a position in the document as TFA is doing, but also count bytes, Unicode codepoints, Unicode characters/glyphs/widths, etc. with just one tree.

What's common to xi's approach and TFA's is monoids. Monoids are at the heart of CRDT.




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

Search: