std.container.rbtree as Interval Tree?
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
> 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.
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
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