interval_tree.py 文件源码

def intervals_containing(t, p):
    """Query the interval tree

    :param t: root of the interval tree
    :param p: value
    :returns: a list of intervals containing p
    :complexity: O(log n + m), where n is the number of intervals in t,
                and m the length of the returned list
    """
    INF = float('inf')
    if t is None:
        return []
    if p < t.center:
        retval = intervals_containing(t.left, p)
        j = bisect_right(t.by_low, (p, (INF, INF)))
        for i in range(j):
            retval.append(t.by_low[i][1])
    else:
        retval = intervals_containing(t.right, p)
        i = bisect_right(t.by_high, (p, (INF, INF)))
        for j in range(i, len(t.by_high)):
            retval.append(t.by_high[j][1])
    return retval
# snip}