IntSpan?

[Neal Norwitz]

Jeff Bienstadt wrote:
> 
> "Neal Norwitz" <neal at metaslash.com> wrote in message
> news:3C99F049.5A78B149 at metaslash.com...
> > Jeff Bienstadt wrote:
> > >
> > > Does there exist for Python something akin to the Set::IntSpan module
> for
> > > Perl?
> > >
> > > I'm looking for something that inteligently handles and manipulates
> spans
> > > of integers, such as:
> > >    2-356,456,458-500

	[my response deleted]

> Yes, I knew about range, but that's not quite what I'm looking for.
> 
> Using range to create the full list of integers seems prohibitively
> expensive --- spans in the range 1-400000 are not at all out of line.
> 
> I'm envisioning a class that stores (for example) a list of tuples and/or
> integers
> to express each portion of the span, such as
>     [(2,356), 456, (458,500)]
> 
> Then, the class might be asked to insert the value 457 into the
> span, which would then result in a "merging" of the items in the
> internal list, such as:
>     [(2,356), (456, 500)]
> 
> Other operations (removing a value or a sub-span, merging another
> span, etc.) would be useful as well.
> 
> I can see from your reply how range could be useful in the
> implementation, for creating temporary lists of values to work
> with but again, since the spans could be quite long, this
> seems expensive.
> 
> I'm sure that I can implement something like this myself, but
> I was hoping that such a thing already existed, because a) I would
> prefer to not have to re-invent the wheel, and b) existing code
> would almost certainly be better that anything I could write given
> my current (week-old!) knowledge of Python.
> 
> (Also, the fact that the Perl module I mentioned uses Set is not
> really important, it just came up while I was searching --- further
> searching also turned up an Array::IntSpan Perl module.  I'm not
> a Perl guy at all, and attempting to translate code from a language
> that I don't know at all into one that I am just learning strikes me
> as painful :-> )
> 
> If I can't find anything that already does what I'm looking for, I'll go
> ahead and tackle it myself.

Oh, so you wanted something useful??? :-)

Here's a start:

class IntSet:
    def __init__(self, *args):
        self.ints = {}
        self.ranges = []
        for v in args:
            try:
                self.add(*v)
            except TypeError:
                self.add(v)

    def add(self, min, max=None):
        if max is None:
            self.ints[min] = 1
        else:
            self.ranges.append((min, max))

    def __contains__(self, value):
        if self.ints.has_key(value):
            return 1
        for min, max in self.ranges:
            if min <= value <= max:
                return 1
        return 0
    has = __contains__

    def __add__(self, other):
        newset = IntSet()
        newset.ints = self.ints
        newset.ranges = self.ranges
        if type(other) is type(0):
            newset.ints[other] = None
            return newset

        if type(other) is not type(self):
            raise TypeError, "'%s' is not an int or %s" % \
                  (other, self.__class__.__name__)

        newset.ints.update(other.ints)
        newset.ranges = newset.ranges + other.ranges
        return newset

>>> from intset import *
>>> s = IntSet((2, 356), 456, (458, 500))
>>> print s.ranges
[(2, 356), (458, 500)]
>>> n = s + 5
>>> print n.ints
{5: None, 456: 1}
>>> print n.ranges
[(2, 356), (458, 500)]
>>> s + 5.3
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "intset.py", line 37, in __add__
    raise TypeError, "'%s' is not an int or %s" % \
TypeError: '5.3' is not an int or IntSet
>>> j = s + n
>>> 457 in j
0
>>> 456 in j
1
>>> 5 in j
1
>>> 2 in j
1
>>> 1 in j
0
>>> s.has(456)
1
>>> s.has(457)
0
>>> s.add(2, 356)
>>> s.add(456)
>>> s.add(458, 500)

I'll let you learn the how to do intersection, etc.  :-) But union is done.

Neal