std.container.rbtree as Interval Tree?

James Blachly james.blachly at gmail.com
Tue Feb 5 19:12:43 UTC 2019


On Tuesday, 5 February 2019 at 16:24:03 UTC, Eduard Staniloiu 
wrote:
> 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


Edi, thanks for your quick reply!

I do understand that Elem is aliased to my Interval type.

Your suggested rewrite of the less fn is precisely what I was 
groaning about (although not explicitly) in terms of rewriting 
opCmp to be a simple `this.start < other.start`. The reason that 
this is undesirable is that distinct intervals with same starting 
coordinates are then considered equal and not added, unless 
RBTree tepmlate is instantiated with allowDuplicates. However, 
even when allowing (pseudo)duplicates, this means the distinct 
intervals with same start but different end coordinates are not 
deterministically placed/sorted within the tree, because they are 
not sortable with the simple `this.start < other.start` less 
function.

Anyway, in the end, I will assume that in my problem domain there 
are no degenerate intervals with same start coordinate and use 
the simpler less to accomplish goal.

Hopefully the upperBound and lowerBound functions are lazy...


More information about the Digitalmars-d-learn mailing list