std.container.rbtree as Interval Tree?

Eduard Staniloiu edi33416 at
Tue Feb 5 16:24:03 UTC 2019

On Monday, 4 February 2019 at 22:54:01 UTC, James Blachly wrote:
> 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] ("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. 
> ")

I think you are making a slight confusion. Your `Interval` struct 
and the `Elem` type that `lowerBound` takes, are the same type.

You can define your RBTree and Interval as follows
struct Interval
     int start;
     int end;

alias IntervalTree = RedBlackTree!(Interval, (i1, i2) => i1.start 
< i2.start);

Please see this runable example:

The in-order traversal will be the same as the wikipedia example 

Hope this helps.


More information about the Digitalmars-d-learn mailing list