Is there a standard Python data structure that keeps thing in sorted order?
Question: I have a set of ranges that might look something like this:

    
    
    [(0, 100), (150, 220), (500, 1000)]
    

I would then add a range, say `(250, 400)` and the list would look like this:

    
    
    [(0, 100), (150, 220), (250, 400), (500, 1000)]
    

I would then try to add the range `(399, 450)`, and it would error out because
that overlapped `(250, 400)`.

When I add a new range, I need to search to make sure the new range does not
overlap an existing range. And no range will ever be in the list that overlaps
another range in the list.

To this end, I would like a data structure that cheaply maintained its
elements in sorted order, and quickly allowed me to find the element before or
after a given element.

Is there a better way to solve this problem? Is there a data structure like
that available in Python? I know the `bisect` module exists, and that's likely
what I will use. But I was hoping there was something better.

**Edit:** I solved this problem using the `bisect` module. Here is a link to
the code. It's a bit longish, so I won't post it here:

[Implementation of byte range list](http://paste.lisp.org/+2LJE)


Answer: It looks like you want something like
[bisect's](http://docs.python.org/release/2.7.1/library/bisect.html)
insort_right/insort_left. The bisect module works with lists and tuples.

    
    
    import bisect
    
    l = [(0, 100), (150, 300), (500, 1000)]
    bisect.insort_right(l, (250, 400))
    print l # [(0, 100), (150, 300), (250, 400), (500, 1000)]
    bisect.insort_right(l, (399, 450))
    print l # [(0, 100), (150, 300), (250, 400), (399, 450), (500, 1000)]
    

You can write your own `overlaps` function, which you can use to check before
using `insort`.

I assume you made a mistake with your numbers as `(250, 400)` overlaps `(150,
300)`. `overlaps()` can be written like so:

    
    
    def overlaps(inlist, inrange):
        for min, max in inlist:
            if min < inrange[0] < max and max < inrange[1]:
                return True
        return False
    

