[Tutor] finding numbers in range of of numbers

[Kent Johnson]

On Tue, Oct 21, 2008 at 10:43 AM, bob gailer <bgailer at gmail.com> wrote:

> I would make a copy of each list; take a pass thru each copy, convert the
> strings to integers and reverse the descending pairs.
>
> a1 = [['xa', 1511255, 1511279],['xb', 7516599, 7516623],['xc', 98356266,
> 98356290]]
>
> b1 = [['G1', 1511200, 1511325],['G2', 7516500, 7516625],['G3', 98356126,
> 98356335]]
>
> Then compare lower and upper limits (no need for range):
>
> for a2 in a1:
>   for b2 in b1:
>     if a2[1] >= b2[1] and a2[2] < b2[2]:
>         print the matched result
>         break
>   else:
>     print the unmatched result.

If you sort  b1 by the second value then you can cut down on the
amount of the list you have to search:
if a2[1] > b2[2]:
  break

Apparently the clever way to do this is to use an interval tree:
http://en.wikipedia.org/wiki/Interval_tree

The bx-python project http://bx-python.trac.bx.psu.edu/ seems to have
an implementation here:
http://bx-python.trac.bx.psu.edu/browser/trunk/lib/bx/intervals/operations/quicksect.py

Also this method that you could use fairly easily:
http://www.bx.psu.edu/projects/bx-python/apidocs/lib/bx.intervals.intersection.Intersecter-class.html

Kent