mapping subintervals

[Lee Sander]

Dear Matteo and Nis,
Thankyou very much for your help. I wasn't aware of the bisect
library but it's really useful.
thank you both once again
Lee

On 13 Jun, 23:21, Nis Jørgensen <n... at superlativ.dk> wrote:
> Matteo skrev:
>
> > OK - I'm going to assume your intervals are inclusive (i.e. 34-51
> > contains both 34 and 51).
>
> > If your intervals are all really all non-overlapping, one thing you
> > can try is to put all the endpoints in a single list, and sort it.
> > Then, you can use the bisect module to search for intervals, which
> > will give you a logarithmic time algorithm.
>
> > Here, I'm going to assume you just need the index of the containing
> > interval. If you really need a name (i.e. 'a1' or 'a2'), you can use a
> > list of names, and index into that.
>
> > I hope those assumptions are valid! if so, the following should work:
>
> I have taken the liberty of simplifying your code, using the fact that
> tuples are sorted lexicographically. Note that this requires all
> intervals to be tuples and not lists (since list(a) < tuple(b) is always
> True).
>
> from bisect import bisect
>
> def test_interval(ivl,intervals):
>
>   # Find where ivl would lie in the list
>   # i.e. the index of the first interval sorting as larger than ivl
>   idx=bisect(intervals,ivl)
>   # Left endpoints equal is a special case - a matching interval will be
>   # to the right of the insertion point
>   if idx < len(intervals) and intervals[idx][0] == ivl[0]:
>         if intervals[idx][1] >= ivl[1]:
>                 return idx
>         else:
>                 return None
>   # Otherwise, we need to check to the left of the insertion point
>   if idx > 0 and intervals[idx-1][1] >= ivl[1]:
>         return idx-1
>   else:
>         return None
>
> >>> intervals =[(10, 21), (34, 51), (77, 101)]
> >>> print test_interval((34,35),intervals)
> 1
> >>> print test_interval((34,53),intervals)
> None
> >>> print test_interval((77,53),intervals)
> 2
> >>> print test_interval((77,83),intervals)
> 2
> >>> print test_interval((77,102),intervals)
> None
> >>> print test_interval((77,101),intervals)
>
> 2
>
> u"Nis J\xf8rgensen"