vigna
NavigableSet?
Is it possible to add this interface to existing fastutil (AVL,RB)TreeSet implementations? The lower and ceiling methods can be mimicked with calls to headSet().last() and tailSet().first() respectively, but they probably wouldn't be as fast, and the higher and floor methods cannot be mimicked easily at all.
@vigna just to help out here a little: To make NavigableSet/Map possible you would have to drop your current TreeSet/Map implementation because with your memory optimization you basically coded yourself into a corner, which I assume you are aware of. And even if you pulled it of with the memory optimization, you would be A LOT slower then Javas implementation which in some cases you already are (iterator remove).
I think that's also the reason why you didn't work on this or anyone else submitted navigable sets/maps in almost 5 years.
Edit: forgot the tip. I would suggest you drop your "No Parent in Nodes" memory optimization and allow it to be a thing. Yes it eats more ram, but compared to the corner you are right now in its A faster, B "useable" and C: You would be at least have a chance against fighting java-collections in speed.
Another approach, a bit ugly and hacky, but easy to implement: introduce a new interface like IntNavigableIterator with one simple function goto(int fromElement) which behaviour like IntSet.iterator(int fromElement) but modified an existed iterator.
Right now it is possible to walk across AVL/RB TreeSet by using this kind of iterator, and each time when a jump is required a user is forced to create a new iterator which creates memory footprint.
Here an improvement that allows to dramatically decrease memory footprint in my case: https://github.com/vigna/fastutil/pull/283