built in function for computing overlap in Python

is there a built in function to compute the overlap between two discrete intervals, e.g. the overlap between [10, 15] and [20, 38]? In that case the overlap is 0. If it's [10, 20], [15, 20], the over开发者_如何学运维lap is 5.

You can use max and min:

>>> def getOverlap(a, b):
...     return max(0, min(a[1], b[1]) - max(a[0], b[0]))

>>> getOverlap([10, 25], [20, 38])
5
>>> getOverlap([10, 15], [20, 38])
0

Check out pyinterval http://code.google.com/p/pyinterval/

import interval
x=interval.interval[10, 15]
y=interval.interval[20, 38]
z=interval.interval[12,18]

print(x & y)
# interval()
print(x & z)
# interval([12.0, 15.0])

Here is a good function from Aaron Quinlan's chrom_sweep, modified for your interval representation. It returns the number of bp of overlap if they do overlap, otherwise it returns the distance as a negative int.

def overlaps(a, b):
    """
    Return the amount of overlap, in bp
    between a and b.
    If >0, the number of bp of overlap
    If 0,  they are book-ended.
    If <0, the distance in bp between them
    """

    return min(a[1], b[1]) - max(a[0], b[0])

Just wrote this:

def overlap(interval1, interval2):
    """
    Given [0, 4] and [1, 10] returns [1, 4]
    """
    if interval2[0] <= interval1[0] <= interval2[1]:
        start = interval1[0]
    elif interval1[0] <= interval2[0] <= interval1[1]:
        start = interval2[0]
    else:
        raise Exception("Intervals are not overlapping")

    if interval2[0] <= interval1[1] <= interval2[1]:
        end = interval1[1]
    elif interval1[0] <= interval2[1] <= interval1[1]:
        end = interval2[1]
    else:
        raise Exception("Intervals are not overlapping")

    return (start, end)


def percentage_overlap(interval1, interval2):
    """
    Given [0, 4] and [1, 10] returns 0.75
    """
    try:
        overlap = _overlap(interval1, interval2)
    except Exception:
        return 0.0
    return (overlap[1] - overlap[0]) / (interval1[1] - interval1[0])

I had to process inclusive bounds so the current answers did not work. Here is a solution with inclusive bounds if you only care about a True/False answer:

def overlap(first: int, last: int, another_first: int, another_last: int)->bool:
    """
    Return True if the two intervals overlap.

    >>> not any([
    ...     _overlap(1, 1, 2, 2),
    ...     _overlap(2, 2, 1, 1)
    ... ])
    True

    >>> all([
    ...     _overlap(1, 1, 1, 1),
    ...     _overlap(1, 5, 1, 1),
    ...     _overlap(1, 1, 1, 5),
    ...     _overlap(1, 3, 2, 5),
    ...     _overlap(2, 5, 1, 3),
    ...     _overlap(1, 5, 2, 3),
    ...     _overlap(2, 3, 1, 5),
    ...  ])
    True
    """
    return min(last, another_last) - max(first, another_first) >= 0