-
Notifications
You must be signed in to change notification settings - Fork 3
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Optional Rank Augmentation; Cursor-oriented Design #1
Comments
Incidentally, what I mean by cursor-oriented design would look like https://forum.nim-lang.org/t/5697#35810 where a cursor is a tree |
Something I don't think I have ever mentioned yet though also relevant here is that separation of seek & edit (add or del) is also a good way to provide well-defined "sub orders" when duplicate keys exist via a "sided seek". For example, if you clone https://github.com/c-blake/adix and $ cd adix/tests
$ nim c ppss
$ nim c -d:btTall btshell
$ ./ppss|./btshell
+1 5 1
+1 5 2
p
-0 5 The tree will still contain the (key=5,val=2) pair because we +1 was like "append" while "-0" was like "de-prepend" (or maybe pop_front in C++ STL-ese). |
Of course, these (seek,edit) things could be the "expert" interface and considered an "implementation detail" and pairs could be bundled up into the "all-in-one" operators like |
B-Trees can cheaply support seek-by-rank. With internal code factoring along "cursor" =
seq[tuple[ptr,index]]
lines, this can even be done both easily and optionally. See my comments here as well https://forum.nim-lang.org/t/5473The text was updated successfully, but these errors were encountered: