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
problems.
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
problem?
James
[1] https://dlang.org/spec/operatoroverloading.html#eqcmp ("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. ")
- std.container.rbtree as Interval ... James Blachly via Digitalmars-d-learn
-
