4 ms·
The piece chain approach does indeed have some cons too, not only advantages. E.g. retrieving a byte at a specific absolute offset requires iterating sequential
by akavel 11y ago
The piece chain approach does indeed have some cons too, not only advantages. E.g. retrieving a byte at a specific absolute offset requires iterating sequentially over all preceding "pieces" of the chain in the basic variant of the structure (i.e. if used without additional helpers/caches/...). But which method doesn't bring its own disadvantages as well as advantages? It would probably be interesting if someone managed to write a comprehensive comparison/analysis of all the various known data structures for editors...
My intention was to highlight the piece-chain method as it seems to me surprisingly often overlooked (not known?), while having quite some noteworthy features. That said, I'm starting to think that maybe its non-trivialness can be seen in itself as one of the disadvantages too (i.e. by maybe making the program more complex than for the other, "dumber" methods)? Not sure on that, though. Adding undo upon the other ("simpler") approaches may possibly make them more complex anyway?