PolyRange -- iterator

Hello,

as I was crawling in endless complications with unadequate ranges, I decided to create a "PolyRange" type able to hold arbitrary many "sub-range"; which means finally a big range with wholes in it. This whole stuff again to cope with unicode -- a poly-range would be able to hold a range for a char class (eg 'letter') which spans over several ordinal ranges. (Viva unicode consortium!)

So, it works as needed. It is even able to "stretch" over addictional sub-ranges or to "unite" with a poly-range brother (sister, too). See code below.

Now, I need it to be properly iterable if needed -- the main use beeing indeed the 'in' operator -- but who knows. So, I tried to implement __iter__ and next (by the way, why isin't it called __next__ instead, looks strange for a python builtin?). Seems to work, but the result looks veeery heavy to my eyes. As I had never written an iterator before, would be nice and criticize the code?

Thank you,
Denis
-------
la vita e estrany



==========================================================
class PolyRange(object):
    def __init__(self, *bounds):
        ''' Build list of ranges from bounds.
            * bounds must sequence of (n1,n2) pairs. '''
        self.bounds = list(bounds)
        self.ranges = [xrange(n1,n2) for (n1,n2) in bounds]
        # iteration
    def __contains__(self, item):
        ''' x in self '''
        for range in self.ranges:
            if item in range:
                return True
    def __or__(self, other):
        ''' PolyRange union '''
        bounds = self.bounds + other.bounds
        return PolyRange(*bounds)
    def __add__(self, range):
        ''' PolyRange with new range added '''
        n1 = range[0] ; n2 = n1+len(range)
        bounds = self.bounds + [(n1,n2)]
        return PolyRange(*bounds)
    def __iter__(self):
        self.isEmpty = False
        (self.range_index, self.item_index) = (0,0)
        self.iter = self.ranges[0].__iter__()
        return self
    def next(self):
        # case already emptied
        if self.isEmpty:
            raise StopIteration
        # throw next item
        try:
            item = self.iter.next()
        except StopIteration:
            self.range_index += 1
            self.item_index = 0
        else:
            self.item_index += 1
            return item
        # next range
        if len(self.ranges) > self.range_index:
            self.iter = self.ranges[self.range_index].__iter__()
        else:
            self.empty = True
            raise StopIteration
        # throw item
        try:
            item = self.iter.next()
        except StopIteration:
            self.empty = True
            raise StopIteration
        else:
            self.item_index += 1
            return item
    def __str__(self):
        return "(%s)" %'U'.join("[%s,%s)" %(n1,n2) for (n1,n2) in self.bounds)
    def __repr__(self):
        return "PolyRange(%s)" %', '.join(str(b) for b in self.bounds)
        return False

def testPolyRange():
    print "=== base case -- test in/contains"
    pr = PolyRange((1,3),(5,7),(9,11))
    print "%s\t%s" %(pr,repr(pr))
    print 2 in pr, 4 in pr

    print "=== union"
    pr = PolyRange((1,3),(5,7)) | PolyRange((9,11))
    print pr

    print "=== addition, iteration"
    r = xrange(3,9)
    pr0 = PolyRange((1,3),(5,7))
    pr1 = pr0 + r
    print pr1
    for i in pr1: print i,
testPolyRange()


_______________________________________________
Tutor maillist  -  Tutor@...
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor

[Hugo Arts]

On Wed, Nov 4, 2009 at 5:38 PM, spir <denis.spir@...> wrote:
> Hello,
>
> as I was crawling in endless complications with unadequate ranges, I decided to create a "PolyRange" type able to hold arbitrary many "sub-range"; which means finally a big range with wholes in it. This whole stuff again to cope with unicode -- a poly-range would be able to hold a range for a char class (eg 'letter') which spans over several ordinal ranges. (Viva unicode consortium!)
>
> So, it works as needed. It is even able to "stretch" over addictional sub-ranges or to "unite" with a poly-range brother (sister, too). See code below.
>
> Now, I need it to be properly iterable if needed -- the main use beeing indeed the 'in' operator -- but who knows. So, I tried to implement __iter__ and next (by the way, why isin't it called __next__ instead, looks strange for a python builtin?). Seems to work, but the result looks veeery heavy to my eyes. As I had never written an iterator before, would be nice and criticize the code?
>

You're right, next() should really be called __next__(), and this is
actually fixed in python 3 (don't know why it wasn't originally done
this way).

Now, the code. If you write __iter__ as a generator, you won't have to
write a next method at all. It simplifies The thing a whole lot:

def __iter__(self):
    for range in self.ranges:
        for item in range:
            yield item

That's it. Alternatively, you could turn the whole thing into a
one-liner and just return a generator expression from __iter__:

def __iter__(self):
    return (item for r in self.ranges for item in r)

It's not as clear though, and it doesn't save that much space. I like
the first one slightly better.

python documentation on generators:
http://docs.python.org/tutorial/classes.html#generators

Hugo
_______________________________________________
Tutor maillist  -  Tutor@...
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor

[Stefan Lesicnik-2]

On Wed, Nov 4, 2009 at 7:17 PM, Hugo Arts <hugo.yoshi@...> wrote:

> On Wed, Nov 4, 2009 at 5:38 PM, spir <denis.spir@...> wrote:
>> Hello,
>>
>> as I was crawling in endless complications with unadequate ranges, I decided to create a "PolyRange" type able to hold arbitrary many "sub-range"; which means finally a big range with wholes in it. This whole stuff again to cope with unicode -- a poly-range would be able to hold a range for a char class (eg 'letter') which spans over several ordinal ranges. (Viva unicode consortium!)
>>
>> So, it works as needed. It is even able to "stretch" over addictional sub-ranges or to "unite" with a poly-range brother (sister, too). See code below.
>>
>> Now, I need it to be properly iterable if needed -- the main use beeing indeed the 'in' operator -- but who knows. So, I tried to implement __iter__ and next (by the way, why isin't it called __next__ instead, looks strange for a python builtin?). Seems to work, but the result looks veeery heavy to my eyes. As I had never written an iterator before, would be nice and criticize the code?
>>
>
> You're right, next() should really be called __next__(), and this is
> actually fixed in python 3 (don't know why it wasn't originally done
> this way).
>
> Now, the code. If you write __iter__ as a generator, you won't have to
> write a next method at all. It simplifies The thing a whole lot:
>
> def __iter__(self):
>    for range in self.ranges:
>        for item in range:
>            yield item
>
> That's it. Alternatively, you could turn the whole thing into a
> one-liner and just return a generator expression from __iter__:
>
> def __iter__(self):
>    return (item for r in self.ranges for item in r)
>
> It's not as clear though, and it doesn't save that much space. I like
> the first one slightly better.
>
> python documentation on generators:
> http://docs.python.org/tutorial/classes.html#generators

I dont know much about generators, but this link was posted earlier
this week and i learnt alot from it (actually some basics, like what
happens when you iterate over different objects!)

http://www.dabeaz.com/generators-uk/

(its the PDF presentation)

Stefan
_______________________________________________
Tutor maillist  -  Tutor@...
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor

Le Wed, 4 Nov 2009 18:17:21 +0100,
Hugo Arts <hugo.yoshi@...> s'exprima ainsi:

> Now, the code. If you write __iter__ as a generator, you won't have to
> write a next method at all. It simplifies The thing a whole lot:
>
> def __iter__(self):
>     for range in self.ranges:
>         for item in range:
>             yield item
>
> That's it. Alternatively, you could turn the whole thing into a
> one-liner and just return a generator expression from __iter__:
>
> def __iter__(self):
>     return (item for r in self.ranges for item in r)
>
> It's not as clear though, and it doesn't save that much space. I like
> the first one slightly better.

Thank you very much! That's exactly what I expected. Was sure my code was uselessly heavy. Actually, when reading the doc about iteration, I had wrongly understood that next() is required, too.

Now, I agree with you on your last comment... except that (.. for .. in ..) is precisely the syntax for generator expression (which is much more familiar to me than the use of generator funcs). Still, I will use the first idiom for clarity.

Two additional questions (relative to things manually implemented in my original code):
* What about memorization of "emptyness", meaning the last item is already reached, and following calls will all fail. This is automatic for generators, but...
* Then how do you restart it? With a decoupling of __iter__() and next(), it's possible to have both failure when empty for the same iterator (= call to next()), and
a new iterator returned by __iter__(), typically for a new "for" statement. Below after a bug correction (attributes needing initialisation):
=======================
def testPolyRange():
    .......
    for i in pr1: print i,
    try:
        print pr1.next()
    except StopIteration,e:
        print "StopIteration"
    for i in pr1: print i,
==>
1 2 5 6 3 4 5 6 7 8 StopIteration
1 2 5 6 3 4 5 6 7 8
=======================

PS: Just checked and works as expected with generator.

Thank you again, Denis.
------
la vita e estrany


_______________________________________________
Tutor maillist  -  Tutor@...
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor

[Hugo Arts]

On Thu, Nov 5, 2009 at 10:39 AM, spir <denis.spir@...> wrote:
>
> Thank you very much! That's exactly what I expected. Was sure my code was uselessly heavy. Actually, when reading the doc about iteration, I had wrongly understood that next() is required, too.
>

This is actually correct. An iterator still requires a next method.
The nice thing about generator functions is that calling them creates
a generator object, which supplies the next method for you
automatically. As below:

>>> a = PolyRange((10, 20), (30, 40))
>>> iter(a)
<generator object at 0x7fe8092c38c0>
>>> b = iter(a)
>>> b.next()
10
>>> b.next()
11

etc. A generator expression does essentially the same thing.


> Two additional questions (relative to things manually implemented in my original code):
> * What about memorization of "emptyness", meaning the last item is already reached, and following calls will all fail. This is automatic for generators, but...
> * Then how do you restart it? With a decoupling of __iter__() and next(), it's possible to have both failure when empty for the same iterator (= call to next()), and
> a new iterator returned by __iter__(), typically for a new "for" statement. Below after a bug correction (attributes needing initialisation):
>
> <snip example>
>
> PS: Just checked and works as expected with generator.
>

Yes, every time you call iter(), a new generator object is created,
which works independently of other generators.

As an aside, I just thought of an even shorter implementation that
does not sacrifice clarity, using the itertools module:

#this imported at the top of the file
import itertools

def __iter__(self):
    return itertools.chain(*self.ranges)

HTH,
Hugo
_______________________________________________
Tutor maillist  -  Tutor@...
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor