IntervalTree Java Implementation

Question

I need an IntervalTree or RangeTree implementation in Java, and am having trouble finding one with working deletion support.

There's a built-in one at sun.jvm.hotspot.utilities.IntervalTree, but the deleteNode method in the RBTree superclass states:

/**
 * FIXME: this does not work properly yet for augmented red-black
 * trees since it doesn't update nodes. Need to figure out exactly
 * from which points we need to propagate updates upwards.
 */

Trying to delete nodes from a tree ends up throwing the exception:

Node's max endpoint was not updated properly

How difficult would it be to properly implement delete functionality in a subclass of the sun.jvm.hotspot.utilities.IntervalTree? Or is there another Interval Tree implementation which already implements this correctly?

Currently I'm just wiping out the tree and re-populating it every time there's a deletion, which is far from ideal (note: setting DEBUGGING=false in the RBTree sped things up tremendously).

Answer 1

This project has a RangeTree implementation that might be of more use to you. The sun packages might be ok for quick-and-dirty use, but I would not recommend building anything important relying on them. Sun may not keep them stable.

Answer 2

I don't know your exact requirements but a non-static Segment Tree might work for you. If so, have a look at Layout Management SW, specifically the SegmentTree package. It has the remove feature you need.

If you decide to roll your own, might I suggest open sourcing it? I'm surprised there isn't an open and easy Interval Tree available already.

Answer 3

I ended up modifying the sun.jvm.hotspot.utilities.IntervalTree to maintain a Set of deleted nodes. When doing a search, I exclude any items in this set. Not ideal, but this was a lot easier than getting "real" deletion working. Once the deleted set gets too large, I rebuild the tree.