Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Functions for combining/merging lists or tuples representing ranges and for subtracting ranges of one list of ranges from ranges of second list of ranges.
#!/usr/bin/env python
def combine_ranges(ranges, are_touching=lambda x, y: y - x == 1):
"""
Create new list of ranges combining ranges if they overlap
or touch each other.
Examples using integers:
>>> combine_ranges(((1,5), (3,7)))
[(1, 7)]
>>> combine_ranges(((1,8), (3,5)))
[(1, 8)]
>>> combine_ranges(((1,8), (9,12)))
[(1, 12)]
>>> combine_ranges(((1,8), (10,13)))
[(1, 8), (10, 13)]
Arguments:
ranges -- iterable containing elements that can be 0 and 1 indexed
(element[0] and element[1] must raise no exception)
are_touching -- function to detect if items are 'touching'
touch_function(element[1], next_element[0])
must return True or False
Default function for integers:
lambda x, y: y - x == 1
Here's touch_function for dates:
lambda x, y: (y - x).days == 1
"""
sorted_ranges = sorted(ranges)
new_ranges = []
new_range_item_start = None
new_range_item_end = None
length = len(sorted_ranges)
for i, range_item in enumerate(sorted_ranges):
if new_range_item_start is None:
new_range_item_start = range_item[0]
new_range_item_end = range_item[1]
elif new_range_item_end >= range_item[0] \
or are_touching(new_range_item_end, range_item[0]):
new_range_item_end = max(range_item[1], new_range_item_end)
else:
new_ranges.append((new_range_item_start, new_range_item_end))
new_range_item_start = range_item[0]
new_range_item_end = range_item[1]
# save if this is last item
if i + 1 == length:
new_ranges.append((new_range_item_start, new_range_item_end))
return new_ranges
def subtract_ranges(ranges_1, ranges_2, step=1):
"""
Subtract ranges of list_of_ranges_2 from ranges of ranges_1 and create new
list of ranges that contains ranges which fits in ranges of ranges_1 but can
not be included in ranges from ranges_2.
Both list of ranges have to be sorted and they can not have ranges that
'touch' each other (so ranges (3,5) and (6,8) must be represented as one
range: (3,8)). So combine_ranges function should be used on those lists.
Examples:
>>> subtract_ranges(((3,5), (7,10), (12,16), (20,25), (28,29)), ((0,2), (6,8), (13,18), (22,23), (26,30)))
[(3, 5), (9, 10), (12, 12), (20, 21), (24, 25)]
>>> subtract_ranges(((3,5), (7,10)), [])
[(3, 5), (7, 10)]
Arguments:
ranges_1,
ranges_2 -- iterable containing elements that can be 0 and 1 indexed
(element[0] and element[1] must raise no exception)
step -- step in range or minimal distance between two elements
It is 1 for integers and for instance for dates should be
datetime.timedelta(days=1).
"""
# if second list is empty first should be returned without any change
if not ranges_2:
# return copy of input list
return list(ranges_1)
new_ranges = []
length = len(ranges_2)
for range_1 in ranges_1:
new_range_start = range_1[0]
new_range_end = range_1[1]
for i, range_2 in enumerate(ranges_2):
# ignore range_2 if it is before new range item
if range_2[1] < new_range_start:
continue
# ignore range_2 (and all further) if it is after new range item
if range_2[0] > new_range_end:
new_ranges.append((new_range_start, new_range_end))
break
# new range item and range_2 intersects
if range_2[1] >= new_range_start \
and range_2[0] <= new_range_end:
# no new range item if range_2 contains new range item
if range_2[0] <= new_range_start \
and range_2[1] >= new_range_end:
break
# range_2 'cuts' beginning of new range item
if range_2[0] < new_range_start:
new_range_start = range_2[1] + step
# range_2 'cuts' end of new range item
if range_2[1] > new_range_end:
new_range_end = range_2[0] - step
# new range item contains range_2
if range_2[0] >= new_range_start and range_2[1] <= new_range_end:
new_ranges.append((new_range_start, range_2[0] - step))
new_range_start = range_2[1] + step
if new_range_start > new_range_end:
break
if i + 1 == length:
new_ranges.append((new_range_start, new_range_end))
return new_ranges
if __name__ == "__main__":
import doctest
doctest.testmod()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment