search

narimiran / sorta

SortedTables in Nim, based on B-Trees
MIT License
17 stars 3 forks source link

Optional Rank Augmentation; Cursor-oriented Design #1

Open c-blake opened 5 years ago

c-blake commented 5 years ago

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/5473

c-blake commented 4 years ago

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 Path.

c-blake commented 4 years ago

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).

c-blake commented 4 years ago

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 []= and friends which people seem pulled toward. While I see the notational appeal of that, it's also true that in practice it can create issues like https://github.com/nim-lang/RFCs/issues/200 and also that one almost always wants two slightly different branches when (seek,edit) is involved..either update-or-init or update-or-release and so on. Often those slightly different branches are handled with in/contains first and then some secondary operation which is also less than ideal both for the duplicated work and for the in-ordered-sets duplicated interfaces. It could be, ultimately, that the expert interface is actually the end-to-end simpler interface hiding behind less simple notation. Just a note. I'm not sure what the best answer is.