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...
