vavr

vavr copied to clipboard

Note: I want to cleanly rewrite it based on the existing Haskell code. We should not try to optimize the if-branches, it is too error prone.

---

We can achieve this by

• make RedBlackTree a final class (currently it is an interface)
• remove Node and Empty (RedBlackTree stores Comparator instead of Empty)
• move all static private methods to an internal class RedBlackTreeOps
• RedBlackTreeOps should not make use of isEmpty(). Instead null represents the empty node. (this is important for left and right subtree)

We expect that this change will boost the performance of SortedSets and SortedMaps.

See also this comment.

This change should be done before pulling #1317!

These changes sound very good, specially replacing the Empty node for null (yeah, null, I know, but sometimes it is ok to embrace "evil" in a controlled manner if "you know what you are doing"!).

The only issue I see with making RedBlackTree a final class instead of an interface is that it might not work if you want to support sub trees efficiently (i.e. as a view of another tree as my implementation in #1317). To support sub views, it would make more sense for RedBlackTree to continue being an interface, and then have two implementing classes: Node and SubTreeView.

Of course, if you are thinking in implementing sub views by just creating a brand new tree, then this design will work. However. creating a sub view will be a very expensive operation, and in my view javaslang will be at a disadvantage versus the java.util implementation.