if number is 1-2, 4 or 6-8 or 12-28, 30, 32...

[jepler at unpythonic.net]

On Mon, Jun 10, 2002 at 11:16:46PM +0000, Gustaf Liljegren wrote:
> Cliff Wells <logiplexsoftware at earthlink.net> wrote: 
> 
> Thanks both of you. I tried both solutions. Since some intervals are very 
> high (1000000+), it takes too long to add them to a list. Cliff's solution 
> was really fast, but it took a while to understand. :)
> 
> Gustaf

You can do one better by keeping the list sorted.  I'd personally express
the ranges in the half-open way that range() does it, and always store
tuples, so that
    ((1,3), (5,100), (200,201))
means exactly 1, 2, 5, ..., 99, 200.

This means that you can use a Python implementation of a priority queue to
manage the lists (since all items are comparable to each other with the
normal Python comparison operator) and you can test for membership in O(lg
n) where n is the number of intervals.

As an added bonus, something like
    reduce(operator.add, map(range, intervals))
would give you an expanded Python list of all the numbers contained.

The following code does something similar to what you want .. I just wrote
_find, so it's probably wrong.  The rest has been slightly tested, though.
This is not a proper priority queue implementation, because insertions
would appear to be O(n), not O(lg n) as they should be (list.insert to the
middle of the list has to move len()/2 pointers to complete the move).
Similarly, the insertion procedure doesn't coalesce neighboring or
overlapping ranges, you have to call clean() to do that.

def _find(l, n):
    lo = 0
    hi = len(l)
    while lo < hi:
        mid = (lo+hi)/2
	a, b = l[mid]
	if a <= n < b: return 1
        elif n < a: hi = mid
        else: lo = mid+1
    return 0

def _insort(l, i):
    lo = 0
    hi = len(l)
    while lo < hi:
        mid = (lo+hi)/2
        if i < l[mid]: hi = mid
        else: lo = mid+1
    l.insert(lo, i)

class RangeList:
    def __init__(self):
        self.l = []

    def addrange(self, low, hi):
        _insort(self.l, (low, hi))

    def clean(self):
        l = []
        if not self.l: return
        ol, oh = self.l[0]
        for (nl, nh) in self.l[1:]:
            if nl >= oh+1:
                l.append((ol, oh))
                ol, oh = nl, nh
            else:
                oh = nh
        l.append((ol, oh))
        self.l = l

    def get(self):
        return self.l

    def __contains__(self, item):
	return _find(self.l, item)

> -- 
> http://mail.python.org/mailman/listinfo/python-list