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