# Find overlaps in ranges pairwise

I've wrote a function which take in a list of ranges (the ranges being tuples) and then returns a list of dictionaries which are a summary of how these ranges overlap with each other

There's not a lot of context to this to take into consideration, I was just aiming to find the overlaps pairwise from a list of ranges. The comments are mostly there for this post. The average amount of ranges I had in mind when developing this was 10.

I'm hoping to get this reviewed mostly just to get other peoples opinions on the function. Another way to do this would be to compare all the ranges individually against each other but I didn't like the idea of that.

Terms:

• encapsulated: These ranges are within this range.

• higherLinked: These ranges overlap, and are more to the right of this range.

• lowerLinked: These ranges overlap, and are more to the left of this range.

• matches: Ranges match each other.

Code:

import collections

# Return a list of dicts.
# Each dict is is a overlap summary of an individual range within the range list parameter.
def do_ranges_overlap_pairwise(rangeTupleList):
sortedRangeTupleList = sorted(rangeTupleList, key=lambda elem: elem[0])
rangeDict = collections.OrderedDict()
overLapDictList = []

def getPartnerKey(key):
if "A" in key:
return key.replace("A", "B")
elif "B" in key:
return key.replace("B", "A")

# Creating an ordered dict and then sorting it by value.
for iteration, rangeTuple in enumerate(sortedRangeTupleList):
sortedRangeTuple = sorted(rangeTuple)
rangeDict["{}A".format(iteration)] = sortedRangeTuple[0]
rangeDict["{}B".format(iteration)] = sortedRangeTuple[1]

sortedRangeDict = collections.OrderedDict(sorted(rangeDict.items(), key=lambda t: t[1]))
keyList = list(sortedRangeDict.keys())  # Ordered list of the keys

# Loop A keys, find the range inbetween itself and it's B pair.
for key in keyList:
if "A" in key:
keyB = getPartnerKey(key)
lowerOverlapIndex = (keyList.index(key) + 1)
higherOverlapIndex = keyList.index(keyB)
overLapRange = keyList[lowerOverlapIndex:higherOverlapIndex]

overlapDict = {
"range": (sortedRangeDict[key], sortedRangeDict[keyB]),
"hasOverlaps": len(overLapRange) > 0,
"encapsulated": [],
"matches": []
}

# Sort the overlapped key into a list based on it's nature.
for overlapKey in overLapRange:
partnerKey = getPartnerKey(overlapKey)

if sorted((sortedRangeDict[overlapKey], sortedRangeDict[partnerKey])) == sorted((sortedRangeDict[key], sortedRangeDict[keyB])):
overlapDict["matches"].append(sorted((sortedRangeDict[overlapKey], sortedRangeDict[partnerKey])))

elif "A" in overlapKey and partnerKey in overLapRange:
overlapDict["encapsulated"].append((sortedRangeDict[overlapKey], sortedRangeDict[partnerKey]))

elif "A" in overlapKey and partnerKey not in overLapRange:

elif "B" in overlapKey and partnerKey not in overLapRange:

overLapDictList.append(overlapDict)

return overLapDictList


Example function call:

import pprint
pp = pprint.PrettyPrinter(indent=4)
pp.pprint(do_ranges_overlap_pairwise([(2, 4), (3, 8), (5, 6), (1, 10), (9, 10), (9, 10)]))


Example output:

[   {   'encapsulated': [(2, 4), (3, 8), (5, 6)],
'hasOverlaps': True,
'matches': [],
'range': (1, 10)},
{   'encapsulated': [],
'hasOverlaps': True,
'matches': [],
'range': (2, 4)},
{   'encapsulated': [(5, 6)],
'hasOverlaps': True,
'matches': [],
'range': (3, 8)},
{   'encapsulated': [],
'hasOverlaps': False,
'matches': [],
'range': (5, 6)},
{   'encapsulated': [],
'hasOverlaps': True,
'matches': [[9, 10]],
'range': (9, 10)},
{   'encapsulated': [],
'hasOverlaps': True,
'matches': [[9, 10]],
'range': (9, 10)}]


Timing

10 ranges:
real    0m0.045s
user    0m0.032s
sys 0m0.010s

100 ranges:
real    0m0.143s
user    0m0.122s
sys 0m0.015s

250 ranges:
real    0m0.682s
user    0m0.625s
sys 0m0.046s

500 ranges:
real    0m2.812s
user    0m2.636s
sys 0m0.145s

1000 ranges:
real    0m13.607s
user    0m13.033s
sys 0m0.492s