Last active
January 3, 2016 10:09
-
-
Save barszczmm/8447665 to your computer and use it in GitHub Desktop.
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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