Hacking btree to support the rank API

[romange]

A question to @ezbr :)

Crazy idea before implementing something on my own. I need the Rank API from the btree class (i.e. FindByRank(rank), GetRank(key) etc). Do you think it is possible to somehow hack (externally) absl::btree internal classes by injecting 3rd party params/policies/btree_nodes to expose rank tree functionality? Let's ignore for a second the fact that the internal classes can change between releases etc and the official Google policy is "strongly against" relying on the implementation details :)

[ezbr]

By "rank", I'm assuming you mean the number of keys in the tree that come before that key. Note that we have implemented an optimized btree_iterator::operator-. It's still O(N), but it iterates over nodes instead of over keys. We haven't implemented a corresponding fast btree_iterator::operator+.

Do you think it is possible to somehow hack (externally) absl::btree internal classes by injecting 3rd party params/policies/btree_nodes to expose rank tree functionality?

Yes, I think it's possible, but I don't recommend it of course because it can break when we update our code. Is the btree_iterator::operator- that we provide fast enough for your use case? I.e. you can implement GetRank(key) as return btree.find(key) - btree.begin();. We could potentially provide a similarly fast btree_iterator::operator+(difference_type n) if needed.

[romange]

Unfortunately it won't be enough because we also need FindByRank(rank)

[romange]

And also O(N) (we may have millions of items in the tree)