mapping subintervals

[Nis Jørgensen]

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"