"""Core interval operations on byte ranges."""
from typing import List, Tuple
ByteInterval = Tuple[int, int] # (start, end) inclusive
[docs]
def merge(intervals: List[ByteInterval]) -> List[ByteInterval]:
"""Merge overlapping or adjacent intervals."""
if not intervals:
return []
sorted_intervals = sorted(intervals)
merged = [sorted_intervals[0]]
for current in sorted_intervals[1:]:
last = merged[-1]
if current[0] <= last[1] + 1:
merged[-1] = (last[0], max(last[1], current[1]))
else:
merged.append(current)
return merged
[docs]
def length(intervals: List[ByteInterval]) -> int:
"""Total bytes covered by intervals."""
return sum(end - start + 1 for start, end in merge(intervals))
[docs]
def intersect(a: List[ByteInterval], b: List[ByteInterval]) -> List[ByteInterval]:
"""Intersection of two interval lists."""
a_m, b_m = merge(a), merge(b)
result = []
i, j = 0, 0
while i < len(a_m) and j < len(b_m):
overlap = (max(a_m[i][0], b_m[j][0]), min(a_m[i][1], b_m[j][1]))
if overlap[0] <= overlap[1]:
result.append(overlap)
if a_m[i][1] < b_m[j][1]:
i += 1
elif b_m[j][1] < a_m[i][1]:
j += 1
else:
i += 1
j += 1
return result
[docs]
def intersect_size(a: List[ByteInterval], b: List[ByteInterval]) -> int:
"""Bytes in intersection."""
return length(intersect(a, b))