Python Overlap Algorithm

class overlap.OverlapAlgorithm(ranges=[])

Optimized algoritm to find an overlapping range.

Ranges are first added using add(). To find the overlapping range, call find():

>>> from overlap import OverlapAlgorithm
>>> algo = OverlapAlgorithm()
>>> algo.add(1, 5)
>>> algo.add(3, 9)
>>> count, lo, hi = algo.find()
>>> print((count, lo, hi))
(2, 3, 5)

The first value returned by the method, count, is the number of overlaps. The second and third, lo and hi, are the common overlap of all ranges.

It’s possible to iteratively add additional ranges and call find() again:

>>> algo.add(4, 5)
>>> print(algo.find())
(3, 4, 5)

If there are multiple overlapping ranges the one with the highest number of overlaps will be returned:

>>> algo.add(10, 20)
>>> algo.add(12, 18)
>>> print(algo.find())
(3, 4, 5)

If there are multiple overlapping ranges with the same number of overlaps, the boundaries of both ranges will be returned,

>>> algo.add(13, 17)
>>> print(algo.find())
(3, 4, 17)

It’s up to the user to interpret this properly. One userfule requirement is that a majority of the ranges have to overlap.

>>> ranges = [ (1,5), (3,9), (4,5), (10,20), (12,18) ]
>>> algo = OverlapAlgorithm(ranges)
>>> count, lo, hi = algo.find()
>>> print(len(ranges))
5
>>> print((count, lo, hi))
(3, 4, 5)
>>> assert count > len(ranges) // 2

This algorithm is based on the selection & clustering algorithm from RFC5905 Appendix A.5.5.1.

add(lo, hi)

Add a range.

Parameters

• lo – low value for the range

• hi – high value for the range

Raises

ValueError – if lo >= hi

find()

Find overlap between ranges.

Returns

count: number of ranges in returned overlap

lo: low value for overlap

hi: high value for overlap

Return type

A tuple with the following values