Python Range Collection

On several occassions in the past year I needed to describe a set of (time) ranges, and find the gaps in between them.
I used it for finding pauses during animations, to trigger different events, fill up the animation or simply hide non-animated props.
Instead of having to do something slow & memory heavy like:

class Range(object):
    '''
    Describes a range of integer values with an interval of +1,
    describing a set similar to python's range(int start, int end).

    Start is inclusive, end is exclusive, like with for loops.
    '''
    def __init__(self, start, end):
        self.start = min(int(start), int(end))
        self.end = max(int(start), int(end))
        if self.start == self.end:
            raise ValueError('Range() can not express a range of size 0; did you mean TimeRange()?')
    def intersects(self, other):
        return other.start <= self.end and other.end >= self.start
    def combine(self, other):
        self.start = min(self.start, other.start)
        self.end = max(self.end, other.end)
    def __repr__(self):
        return 'range[%s,%s)'%(self.start, self.end)
    def __iter__(self):
        for i in xrange(self.start, self.end):
            yield i


class TimeRange(object):
    '''
    A Range() with inclusive end-value; allows for start == end.
    See Range() and RangeCollection() for more information.
    '''
    def __init__(self, start, end):
        self.start = min(int(start), int(end))
        self.end = max(int(start), int(end))
    def intersects(self, other):
        return other.start <= self.end + 1 and other.end + 1 >= self.start
    def combine(self, other):
        self.start = min(self.start, other.start)
        self.end = max(self.end, other.end)
    def __repr__(self):
        return 'range[%s,%s]'%(self.start, self.end)
    def __iter__(self):
        for i in xrange(self.start, self.end + 1):
            yield i


class RangeCollection(object):
    '''
    A list of Range() or TimeRange() objects that is consolidated so not a single instance
    overlaps another one. Allows for consolidated range iteration using segments() and
    remaining gap iteration using gaps().
    '''
    def __init__(self):
        self.segments = []

    def addSegment(self, inRange):
        state = None
        for i in xrange(len(self.segments)):
            segment = self.segments[i]
            if segment.intersects(inRange):
                if state is not None:
                    # If we found two consecutive intersections we close the gap.
                    state.combine(segment)
                    self.segments.pop(i)
                    return
                # If we found the first intersection we check the next node as well.
                state = segment
                continue
            if state is not None:
                # If we only found the first intersection we extend the node.
                break
        if state is not None:
            # If we only found the first intersection we extend the node.
            state.combine(inRange)
            return
        # if we found no intersections we append the new data.
        self.segments.append(inRange)

    def gaps(self, inStart=None, inEnd=None, wantsInclusiveRange=False):
        self.segments.sort(key=lambda x:  x.start)
        offset = 0
        if inStart is None:
            start = self.segments[0].start
        else:
            start = inStart
            while self.segments[offset].start < inStart:
                offset += 1
        end = None
        for i in xrange(offset, len(self.segments)):
            end = self.segments[i].start
            if end - start == 0:
                start = self.segments[i].end + isinstance(self.segments[i], TimeRange)
                continue
            if wantsInclusiveRange:
                yield TimeRange(start, end-1)
            else:
                yield Range(start, end)
            start = self.segments[i].end + isinstance(self.segments[i], TimeRange)
        if inEnd is not None:
            if wantsInclusiveRange:
                yield TimeRange(end, inEnd)
            else:
                yield Range(end, inEnd)

    def iterGapFrames(self, inStart=None, inEnd=None, wantsInclusiveRange=False):
        for gap in self.gaps(inStart, inEnd, wantsInclusiveRange):
            for i in gap:
                yield i

    def iterRangeFrames(self, inStart=None, inEnd=None):
        self.segments.sort(key=lambda x:  x.start)
        for segment in self.segments:
            for i in segment:
                if inStart is not None and i < inStart:
                    continue
                if inEnd is not None and i > inEnd:
                    continue
                yield i


if __name__ == '__main__':
    timeline = RangeCollection()
    testData = [(2, 5), (4, 8), (2, 3), (44, 60), (10, 43), (80, 90), (100, 110), (200, 210), (220, 230), (210, 220), (300, 310), (320, 330), (311, 319)]
    for timeRange in testData:
        timeline.addSegment(TimeRange(*timeRange))
    print timeline.segments
    print list(timeline.gaps(inStart=20, inEnd=400, wantsInclusiveRange=True))

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>