The interface Interval provides a standard implementation for a half-open [u,v) interval. A closed-interval [u,v] can be obtained by implementing a new class ClosedInterval extends Interval, and overriding the length, isAdjacent, and overlaps methods. So far so good. The problems appear when creating a IntervalTree<ClosedInterval>. Each IntervalTree is composed of nodes which are Intervals themselfves: Node implements Interval. Because each node is an interval, they will inherit the default implementations of length, isAdjacent, and overlaps as specified in the Interval class. This causes the problem. When comparing two Nodes, the default implementations are used, as opposed to the overridden implementations in the ClosedInterval. In summary: a Node should not be an interval, but should delegate comparisons to the interval contained inside the node.
Removing implements Interval from the Node class definition, and delegating all length, isAdjacent, and overlaps methods to the interval contained inside the node unfortunately does not suffice. Take for instance two closed intervals [0,10] and [10,15] which overlap in the value 10.
The minimumOverlappingNode(T t) method has the following line: if (!n.isNil() && n.maxEnd > t.start()). n.maxEnd > t.start() only works for open intervals, but not for closed intervals.
It seems significant changes to the underlying implementation are required to support generic intervals. I would recommend removing the from your IntervalTree class since the class does not work well with anything else than the half-open interval.
The interface
Intervalprovides a standard implementation for a half-open [u,v) interval. A closed-interval [u,v] can be obtained by implementing a new class ClosedInterval extends Interval, and overriding thelength,isAdjacent, andoverlapsmethods. So far so good. The problems appear when creating aIntervalTree<ClosedInterval>. Each IntervalTree is composed of nodes which are Intervals themselfves:Node implements Interval. Because each node is an interval, they will inherit the default implementations oflength,isAdjacent, andoverlapsas specified in theIntervalclass. This causes the problem. When comparing two Nodes, the default implementations are used, as opposed to the overridden implementations in the ClosedInterval. In summary: a Node should not be an interval, but should delegate comparisons to the interval contained inside the node.Removing
implements Intervalfrom theNodeclass definition, and delegating alllength,isAdjacent, andoverlapsmethods to the interval contained inside the node unfortunately does not suffice. Take for instance two closed intervals [0,10] and [10,15] which overlap in the value 10.The
minimumOverlappingNode(T t)method has the following line:if (!n.isNil() && n.maxEnd > t.start()).n.maxEnd > t.start()only works for open intervals, but not for closed intervals.It seems significant changes to the underlying implementation are required to support generic intervals. I would recommend removing the from your IntervalTree class since the class does not work well with anything else than the half-open interval.