Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I wanted to implemented an algorithm in Python 2.4 (so the odd construction for the conditional assignment) where given a list of ranges, the function returns another list with all ranges that overlap in same entry.

I would appreciate another options (more elegant or efficient) that the one I took.

ranges = [(1,4),(1,9),(3,7),(10,15),(1,2),(8,17),(16,20),(100,200)]


def remove_overlap(rs):
        rs.sort()
        def process (rs,deviation):
                start = len(rs) - deviation - 1
                if start < 1:
                        return rs
                if rs[start][0] > rs[start-1][1]:
                        return process(rs,deviation+1)
                else:
                        rs[start-1] = ((rs[start][0],rs[start-1][0])[rs[start-1][0] < rs[start][0]],(rs[start][1],rs[start-1][1])[rs[start-1][1] > rs[start][1]])
                        del rs[start]
                        return process(rs,0)
        return process(rs,0)

print remove_overlap(ranges)

Many thanks,

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

Firstly, modify of return, don't do both.

Your process method returns lists as well as modify them. Either you should construct a new list and return that, or modify the existing list and return nothing.

Your remove_overlap function does the same thing. It should either modify the incoming list, or return a new list not both.

You index [0] and [1] on the tuples a lot to fetch the start and end. That's best avoided because its not easy to tell whats going on.

rs[start-1] = ((rs[start][0],rs[start-1][0])[rs[start-1][0] < rs[start][0]],(rs[start][1],rs[start-1][1])[rs[start-1][1] > rs[start][1]])

Ouch! That'd be much better off broken into several lines. You shouldn't need to check which of the starts is lower because sorting the array should mean that the earlier one is always lower. I'd also use the max function to select the larger item, (if you don't have it in your version of python, I'd just define it)

Your loop is backwards, working from the end. That complicates the code and makes it harder to follow. I'd suggest reworking it work from the front.

return process(rs,0)

You start the checking process over again whenever you merge two ranges. But that's not so great because you'll end up rechecking all the segments over and over again. Since you've already verified them you shouldn't check them again.

Your recursion process can be easily rewritten as a while loop. All your doing is moving an index forward, and you don't really need recursion.

This is my implementation:

def remove_overlap(ranges):
    result = []
    current_start = -1
    current_stop = -1 

    for start, stop in sorted(ranges):
        if start > current_stop:
            # this segment starts after the last segment stops
            # just add a new segment
            result.append( (start, stop) )
            current_start, current_stop = start, stop
        else:
            # segements overlap, replace
            result[-1] = (current_start, stop)
            # current_start already guaranteed to be lower
            current_stop = max(current_stop, stop)

    return result
share|improve this answer
    
remove_overlap([(-1,1)])IndexError: list assignment index out of range. Maybe start with float('-inf') instead of -1? –  Gareth Rees Feb 5 '13 at 11:18
    
@GarethRees, that'll work if you need negative ranges. I assumed the ranges were positive as typically negatives ranges are non-sensical (not always). –  Winston Ewert Feb 5 '13 at 13:53
add comment

In addition to Winston Ewert's comments, I'd add:

  1. There's no docstring. How are users to know how what this function does and how to call it?

  2. This is an ideal function to give a couple of doctests to show how to use it and to test that it works.

  3. The name remove_overlap could be improved. Remove overlap from what? And remove it how? And anyway, you don't just want to merge overlapping ranges (like 1–3 and 2–4), you want to merge adjacent ranges too (like 1–2 and 2–3). So I'd use merge_ranges.

  4. It's simpler and more flexible to implement the function as a generator, rather than repeatedly appending to a list.

  5. Winston's implementation doesn't work if any of the ranges are negative.

So I would write:

def merge_ranges(ranges):
    """
    Merge overlapping and adjacent ranges and yield the merged ranges
    in order. The argument must be an iterable of pairs (start, stop).

    >>> list(merge_ranges([(5,7), (3,5), (-1,3)]))
    [(-1, 7)]
    >>> list(merge_ranges([(5,6), (3,4), (1,2)]))
    [(1, 2), (3, 4), (5, 6)]
    >>> list(merge_ranges([]))
    []
    """
    ranges = iter(sorted(ranges))
    current_start, current_stop = next(ranges)
    for start, stop in ranges:
        if start > current_stop:
            # Gap between segments: output current segment and start a new one.
            yield current_start, current_stop
            current_start, current_stop = start, stop
        else:
            # Segments adjacent or overlapping: merge.
            current_stop = max(current_stop, stop)
    yield current_start, current_stop

Update

Winston Ewert notes in comments that it's not exactly obvious how this works in the case when ranges is the empty list: in particular, the call next(ranges) looks suspicious.

The explanation is that when ranges is empty, next(ranges) raises the exception StopIteration. And that's exactly what we want, because we are writing a generator function and raising StopIteration is one of the ways that a generator can signal that it is finished.

This is a common pattern when building one iterator from another: the outer iterator keeps reading elements from the inner iterator, relying on the inner iterator to raise StopIteration when it is empty. Several of the recipes in the itertools documentation use this pattern, for example imap and islice.

Supposing that you think this is a bit ugly, and you wanted to make the behaviour explicit, what would you write? Well, you'd end up writing something like this:

try:
    current_start, current_stop = next(ranges)
except StopIteration:     # ranges is empty
    raise StopIteration   # and so are we

I hope you can see now why I didn't write it like that! I prefer to follow the maxim, "program as if you know the language."

share|improve this answer
    
I'm pretty sure it'll fail on ranges = [] due to trying to fetch the next item from an empty list. –  Winston Ewert Feb 5 '13 at 13:56
    
There's already a doctest for that case. (And it passes.) When ranges is empty, the call to next raises the exception StopIteration, which is exactly what we need. –  Gareth Rees Feb 5 '13 at 16:29
    
Oh, subtle. I didn't think of the fact that StopIteration would trigger the end of the generator. Honestly, that feels ugly to me, but that may just be taste. –  Winston Ewert Feb 5 '13 at 16:50
    
It's a natural pattern for building one iterator out of another: the outer iterator reads items from the inner iterator, relying on the inner one to raise StopIteration when it's empty. Many of the recipes in the itertools module use this pattern. See for example imap and islice. –  Gareth Rees Feb 5 '13 at 16:58
    
I reserve my right to still find it ugly. :) Maybe its just a matter of not being used to it, but I don't like the implicit way it handles the case. –  Winston Ewert Feb 5 '13 at 17:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.