Omnifarious Omnifarious - 1 month ago 6
Python Question

Is there a standard Python data structure that keeps thing in sorted order?

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

Answer

It looks like you want something like bisect's 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