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.

ranges_lists_utils.py

#!/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()