efficient interval containment lookup

[Steven D'Aprano]

On Mon, 12 Jan 2009 14:49:43 -0800, Per Freem wrote:

> thanks for your replies -- a few clarifications and questions. the
> is_within operation is containment, i.e. (a,b) is within (c,d) iff a
>>= c and b <= d. Note that I am not looking for intervals that
> overlap... this is why interval trees seem to me to not be relevant, as
> the overlapping interval problem is way harder than what I am trying to
> do. Please correct me if I'm wrong on this...


To test for contained intervals:
a >= c and b <= d

To test for overlapping intervals:

not (b < c or a > d)

Not exactly what I would call "way harder".



-- 
Steven