Our great sponsors
-
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
-
Rope-Data-Structure-C
Implementation of a data structure that can store a string and efficiently cut a part (a substring) of this string and insert it in a different position
Project site linked from the GitHub[0] is https://xi-editor.io. Linked doc is a mirror of this[1], which was afaik originally written by Raph Linus.
[0]: https://github.com/xi-editor/xi-editor
[1]: https://xi-editor.io/docs/rope_science_01.html
> The worst way to store and manipulate text is to use an array.
Claim made from theoretical considerations, without any actual reference to real-world editors. The popular Micro[1] text editor uses a simple line array[2], and performs fantastically well on real-world editing tasks.
Meanwhile, ropes are so complicated that even high-quality implementations have extremely subtle bugs[3] that can lead to state or content corruption.
Which data structure is "best" is not just a function of its asymptotic performance. Practical considerations are equally important (arguably more so).
[1] https://github.com/zyedidia/micro
[2] https://github.com/zyedidia/micro/blob/master/internal/buffe...
[3] https://github.com/cessen/ropey/pull/67
> The worst way to store and manipulate text is to use an array.
Claim made from theoretical considerations, without any actual reference to real-world editors. The popular Micro[1] text editor uses a simple line array[2], and performs fantastically well on real-world editing tasks.
Meanwhile, ropes are so complicated that even high-quality implementations have extremely subtle bugs[3] that can lead to state or content corruption.
Which data structure is "best" is not just a function of its asymptotic performance. Practical considerations are equally important (arguably more so).
[1] https://github.com/zyedidia/micro
[2] https://github.com/zyedidia/micro/blob/master/internal/buffe...
[3] https://github.com/cessen/ropey/pull/67
if you don't have reflinks you're going to have to load the entire file into an array when you open it anyway, even if that array isn't where you edit it
the complexity of ropes is being oversold here. as i pointed out in a comment in a subthread, you can make ropes quite complex, but https://github.com/ivanbgd/Rope-Data-Structure-C is 339 lines of code. it's probably not a real-world rope, though
probably the most widely used implementation of ropes is the one from the sgi stl, which is in gcc as libstdc++/ext/rope https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USER... and libstdc++/ext/ropeimpl.h https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USER..., which total 1485 lines of code, about five times larger. in a garbage-collected language, like the cedar language where ropes originated, most of that complexity goes away, and production-quality ropes are only a few hundred lines of code. also c++'s verbose syntax isn't doing brevity any favors here
http://www.bitsavers.org/pdf/xerox/parc/cedar/Cedar_7.0/09_C...