std.container.rbtree as Interval Tree?

[Eduard Staniloiu]

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] 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. 
> ")

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: https://run.dlang.io/is/4cPTik

The in-order traversal will be the same as the wikipedia example 
here: https://en.wikipedia.org/wiki/Interval_tree

Hope this helps.

Cheers,
Edi