Add implementation for covering/enveloped?

[johann-petrak]

Would it be possible to make use of the interval tree to efficiently return all intervals which contain a given interval.

So "tree.covering(from, to)" would return all intervals i in the tree for which:
i.start <= from and i.end >= to

This can be achieved indirectly in various ways, but depending on how intervals are present in the tree, the overhead may perhaps be bigger than if using the interval tree directly?

[chaimleib]

tree.at(from).intersection(tree.at(to)) does a lot of the optimizing work already. Can you think of other easy optimizations?

[chaimleib]

Oh, whoops, not quite. tree.at(to) would inclusively search the end boundary.

[chaimleib]

We would have to search the internal boundary_table for the greatest member less than to:

upper_bound = boundary_table.bisect_left(end)

That would give the actual upper bound. Then the we tweak the algorithm slightly:

tree.at(from).intersection(tree.at(upper_bound))

That would do it.