3 ms·
Here's one I don't know if I've ever seen documented anywhere. If anyone knows a proper name for this one, let me know! Imagine it's for a text editor, and yo
by Dwedit 4y ago
Here's one I don't know if I've ever seen documented anywhere. If anyone knows a proper name for this one, let me know!
Imagine it's for a text editor, and you want to map Line Numbers to Byte Positions. But then you want to insert a byte somewhere, and you need to add 1 to all your Byte Position values.
Instead of actually keeping a big array of Byte Position values, you have a hierarchical array. The convention is that whenever you want to read the value, you add the Parent's value, and that parent's value, etc. Number of parents would be logarithmic.
So if you want to add 1 to everything past a certain point, you just apply it to some leaf nodes, then the next internal nodes, rather than applying it to every single leaf node.
- progval 4y agohttps://en.wikipedia.org/wiki/Rope_(data_structure) https://en.wikipedia.org/wiki/Rope_(data_structure)
- Dwedit 4y agoThat's good for representing the text, but I'm more focused on the part about being able to add X to everything past a particular point very quickly by manipulating parent values.
- progval 4y agoRopes do this too; each node is labeled the size of its subtree. If you want to compute line numbers as well, add them as another label
- kragen 4y agoThat kind of thing is a common extension to ropes, because it makes them indexable containers like arrays, but it is not inherent to the definition of ropes. I don't think it's mentioned in the original Cedar rope paper.
- ant6n 4y agoAn annotated tree?
- ly3xqhl8g9 4y agoSomewhat along these lines, I have formed a concept forcedly called "differentially composable string", or "deposed string", or more precise "poor man's git". The intended use case is to obtain a compact representation of all the historic text entered into an input field (notes, comments, maybe long-form): all the stages of the text, where a stage is a tuple [add/remove, start_index, text/end_index]. Once you get the stages from the deposed string as JSON, you could transform them however you want then load them into a new deposed string. You can read more on GitHub: https://github.com/plurid/plurid-data-structures-typescript#deposedstring https://github.com/plurid/plurid-data-structures-typescript#... or play around on my note-taking app implementing deposed strings and more: https://denote.plurid.com https://denote.plurid.com
- compressedgas 4y agoTed Nelson named them Enfilades. Guy Steele called them Monoid Cached Trees.
- twic 4y agoEnfilade trees were going to be my suggestion for this page? Really nice structures. Such a shame the writing describing them is so hermetic in style - dispative and widdative properties, really, come on now.
- kragen 4y agoActually I think it was Roger Gregory or Mark Miller who came up with the term "enfilade", and I don't think enfilade wids and dsps have to be monoids necessarily. I'm not sure, though.
- deleted 4y ago[deleted]
- jdougan 4y agoRodney Bates called his independent invention of them K-Trees.