std.container.rbtree as Interval Tree?

James Blachly james.blachly at
Mon Feb 4 22:54:01 UTC 2019

I tried to implement an interval tree backed by 
std.container.rbtree today and fell flat.

A standard way to make an interval tree is to make an augmented 
tree; I supposed since rbtree was a generic container and because 
I could define opCmp, this should be a cinch. I ran into two 

First (minor problem), RedBlackTree considers a return value of 0 
from opCmp equivalent to "equals", which is discordant with the 
guidance given for opCmp.[1] This is a  minor pedantic point, 
since you cannot store un-orderable elements in the tree anyway.

More importantly, though, I cannot figure out how to implement an 
interval query function on the tree. Typically, the tree would 
have a "key" that is the left position of the interval and the 
augmented part of the tree would be that a second value -- a 
right, or end, position. My Elem == key type is a struct 
encapsulating both of these (start, end; plus some metadata).

For my Interval element type, I overloaded opCmp to take an 
integer, but unfortunately RedBlackTree's upperBound() and 
lowerBound() functions are defined in terms of "Elem" which is 
aliased to the contained element type, rather than a generic type.

Q1: Is there a simple or elegant way to do this without 
re-implementing RedBlackTree? I apologize if it is obvious and I 
am missing it. I suppose it may work if I rewrite Interval's 
opCmp to not consider the upper bound, and by creating a dummy 
interval to pass to upperBound and lowerBound, but that seems 
inelegant compared to passing an integer.

Q2: Would replacing "Elem" with a generic type "T" in the 
function signatures for upperBound, lowerBound, and various 
related fns like _firstGreater / _firstGreaterEqual solve this 


[1] ("For 
example ... x and y are disjoint sets, then neither x < y nor y < 
x holds, but that does not imply that x == y. Thus, it is 
insufficient to determine equality purely based on opCmp alone. ")

More information about the Digitalmars-d-learn mailing list