PyXR

c:\python24\lib \ test \ test_generators.py



0001 tutorial_tests = """
0002 Let's try a simple generator:
0003 
0004     >>> def f():
0005     ...    yield 1
0006     ...    yield 2
0007 
0008     >>> for i in f():
0009     ...     print i
0010     1
0011     2
0012     >>> g = f()
0013     >>> g.next()
0014     1
0015     >>> g.next()
0016     2
0017 
0018 "Falling off the end" stops the generator:
0019 
0020     >>> g.next()
0021     Traceback (most recent call last):
0022       File "<stdin>", line 1, in ?
0023       File "<stdin>", line 2, in g
0024     StopIteration
0025 
0026 "return" also stops the generator:
0027 
0028     >>> def f():
0029     ...     yield 1
0030     ...     return
0031     ...     yield 2 # never reached
0032     ...
0033     >>> g = f()
0034     >>> g.next()
0035     1
0036     >>> g.next()
0037     Traceback (most recent call last):
0038       File "<stdin>", line 1, in ?
0039       File "<stdin>", line 3, in f
0040     StopIteration
0041     >>> g.next() # once stopped, can't be resumed
0042     Traceback (most recent call last):
0043       File "<stdin>", line 1, in ?
0044     StopIteration
0045 
0046 "raise StopIteration" stops the generator too:
0047 
0048     >>> def f():
0049     ...     yield 1
0050     ...     raise StopIteration
0051     ...     yield 2 # never reached
0052     ...
0053     >>> g = f()
0054     >>> g.next()
0055     1
0056     >>> g.next()
0057     Traceback (most recent call last):
0058       File "<stdin>", line 1, in ?
0059     StopIteration
0060     >>> g.next()
0061     Traceback (most recent call last):
0062       File "<stdin>", line 1, in ?
0063     StopIteration
0064 
0065 However, they are not exactly equivalent:
0066 
0067     >>> def g1():
0068     ...     try:
0069     ...         return
0070     ...     except:
0071     ...         yield 1
0072     ...
0073     >>> list(g1())
0074     []
0075 
0076     >>> def g2():
0077     ...     try:
0078     ...         raise StopIteration
0079     ...     except:
0080     ...         yield 42
0081     >>> print list(g2())
0082     [42]
0083 
0084 This may be surprising at first:
0085 
0086     >>> def g3():
0087     ...     try:
0088     ...         return
0089     ...     finally:
0090     ...         yield 1
0091     ...
0092     >>> list(g3())
0093     [1]
0094 
0095 Let's create an alternate range() function implemented as a generator:
0096 
0097     >>> def yrange(n):
0098     ...     for i in range(n):
0099     ...         yield i
0100     ...
0101     >>> list(yrange(5))
0102     [0, 1, 2, 3, 4]
0103 
0104 Generators always return to the most recent caller:
0105 
0106     >>> def creator():
0107     ...     r = yrange(5)
0108     ...     print "creator", r.next()
0109     ...     return r
0110     ...
0111     >>> def caller():
0112     ...     r = creator()
0113     ...     for i in r:
0114     ...             print "caller", i
0115     ...
0116     >>> caller()
0117     creator 0
0118     caller 1
0119     caller 2
0120     caller 3
0121     caller 4
0122 
0123 Generators can call other generators:
0124 
0125     >>> def zrange(n):
0126     ...     for i in yrange(n):
0127     ...         yield i
0128     ...
0129     >>> list(zrange(5))
0130     [0, 1, 2, 3, 4]
0131 
0132 """
0133 
0134 # The examples from PEP 255.
0135 
0136 pep_tests = """
0137 
0138 Specification:  Yield
0139 
0140     Restriction:  A generator cannot be resumed while it is actively
0141     running:
0142 
0143     >>> def g():
0144     ...     i = me.next()
0145     ...     yield i
0146     >>> me = g()
0147     >>> me.next()
0148     Traceback (most recent call last):
0149      ...
0150       File "<string>", line 2, in g
0151     ValueError: generator already executing
0152 
0153 Specification: Return
0154 
0155     Note that return isn't always equivalent to raising StopIteration:  the
0156     difference lies in how enclosing try/except constructs are treated.
0157     For example,
0158 
0159         >>> def f1():
0160         ...     try:
0161         ...         return
0162         ...     except:
0163         ...        yield 1
0164         >>> print list(f1())
0165         []
0166 
0167     because, as in any function, return simply exits, but
0168 
0169         >>> def f2():
0170         ...     try:
0171         ...         raise StopIteration
0172         ...     except:
0173         ...         yield 42
0174         >>> print list(f2())
0175         [42]
0176 
0177     because StopIteration is captured by a bare "except", as is any
0178     exception.
0179 
0180 Specification: Generators and Exception Propagation
0181 
0182     >>> def f():
0183     ...     return 1//0
0184     >>> def g():
0185     ...     yield f()  # the zero division exception propagates
0186     ...     yield 42   # and we'll never get here
0187     >>> k = g()
0188     >>> k.next()
0189     Traceback (most recent call last):
0190       File "<stdin>", line 1, in ?
0191       File "<stdin>", line 2, in g
0192       File "<stdin>", line 2, in f
0193     ZeroDivisionError: integer division or modulo by zero
0194     >>> k.next()  # and the generator cannot be resumed
0195     Traceback (most recent call last):
0196       File "<stdin>", line 1, in ?
0197     StopIteration
0198     >>>
0199 
0200 Specification: Try/Except/Finally
0201 
0202     >>> def f():
0203     ...     try:
0204     ...         yield 1
0205     ...         try:
0206     ...             yield 2
0207     ...             1//0
0208     ...             yield 3  # never get here
0209     ...         except ZeroDivisionError:
0210     ...             yield 4
0211     ...             yield 5
0212     ...             raise
0213     ...         except:
0214     ...             yield 6
0215     ...         yield 7     # the "raise" above stops this
0216     ...     except:
0217     ...         yield 8
0218     ...     yield 9
0219     ...     try:
0220     ...         x = 12
0221     ...     finally:
0222     ...         yield 10
0223     ...     yield 11
0224     >>> print list(f())
0225     [1, 2, 4, 5, 8, 9, 10, 11]
0226     >>>
0227 
0228 Guido's binary tree example.
0229 
0230     >>> # A binary tree class.
0231     >>> class Tree:
0232     ...
0233     ...     def __init__(self, label, left=None, right=None):
0234     ...         self.label = label
0235     ...         self.left = left
0236     ...         self.right = right
0237     ...
0238     ...     def __repr__(self, level=0, indent="    "):
0239     ...         s = level*indent + repr(self.label)
0240     ...         if self.left:
0241     ...             s = s + "\\n" + self.left.__repr__(level+1, indent)
0242     ...         if self.right:
0243     ...             s = s + "\\n" + self.right.__repr__(level+1, indent)
0244     ...         return s
0245     ...
0246     ...     def __iter__(self):
0247     ...         return inorder(self)
0248 
0249     >>> # Create a Tree from a list.
0250     >>> def tree(list):
0251     ...     n = len(list)
0252     ...     if n == 0:
0253     ...         return []
0254     ...     i = n // 2
0255     ...     return Tree(list[i], tree(list[:i]), tree(list[i+1:]))
0256 
0257     >>> # Show it off: create a tree.
0258     >>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
0259 
0260     >>> # A recursive generator that generates Tree labels in in-order.
0261     >>> def inorder(t):
0262     ...     if t:
0263     ...         for x in inorder(t.left):
0264     ...             yield x
0265     ...         yield t.label
0266     ...         for x in inorder(t.right):
0267     ...             yield x
0268 
0269     >>> # Show it off: create a tree.
0270     >>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
0271     >>> # Print the nodes of the tree in in-order.
0272     >>> for x in t:
0273     ...     print x,
0274     A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0275 
0276     >>> # A non-recursive generator.
0277     >>> def inorder(node):
0278     ...     stack = []
0279     ...     while node:
0280     ...         while node.left:
0281     ...             stack.append(node)
0282     ...             node = node.left
0283     ...         yield node.label
0284     ...         while not node.right:
0285     ...             try:
0286     ...                 node = stack.pop()
0287     ...             except IndexError:
0288     ...                 return
0289     ...             yield node.label
0290     ...         node = node.right
0291 
0292     >>> # Exercise the non-recursive generator.
0293     >>> for x in t:
0294     ...     print x,
0295     A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0296 
0297 """
0298 
0299 # Examples from Iterator-List and Python-Dev and c.l.py.
0300 
0301 email_tests = """
0302 
0303 The difference between yielding None and returning it.
0304 
0305 >>> def g():
0306 ...     for i in range(3):
0307 ...         yield None
0308 ...     yield None
0309 ...     return
0310 >>> list(g())
0311 [None, None, None, None]
0312 
0313 Ensure that explicitly raising StopIteration acts like any other exception
0314 in try/except, not like a return.
0315 
0316 >>> def g():
0317 ...     yield 1
0318 ...     try:
0319 ...         raise StopIteration
0320 ...     except:
0321 ...         yield 2
0322 ...     yield 3
0323 >>> list(g())
0324 [1, 2, 3]
0325 
0326 Next one was posted to c.l.py.
0327 
0328 >>> def gcomb(x, k):
0329 ...     "Generate all combinations of k elements from list x."
0330 ...
0331 ...     if k > len(x):
0332 ...         return
0333 ...     if k == 0:
0334 ...         yield []
0335 ...     else:
0336 ...         first, rest = x[0], x[1:]
0337 ...         # A combination does or doesn't contain first.
0338 ...         # If it does, the remainder is a k-1 comb of rest.
0339 ...         for c in gcomb(rest, k-1):
0340 ...             c.insert(0, first)
0341 ...             yield c
0342 ...         # If it doesn't contain first, it's a k comb of rest.
0343 ...         for c in gcomb(rest, k):
0344 ...             yield c
0345 
0346 >>> seq = range(1, 5)
0347 >>> for k in range(len(seq) + 2):
0348 ...     print "%d-combs of %s:" % (k, seq)
0349 ...     for c in gcomb(seq, k):
0350 ...         print "   ", c
0351 0-combs of [1, 2, 3, 4]:
0352     []
0353 1-combs of [1, 2, 3, 4]:
0354     [1]
0355     [2]
0356     [3]
0357     [4]
0358 2-combs of [1, 2, 3, 4]:
0359     [1, 2]
0360     [1, 3]
0361     [1, 4]
0362     [2, 3]
0363     [2, 4]
0364     [3, 4]
0365 3-combs of [1, 2, 3, 4]:
0366     [1, 2, 3]
0367     [1, 2, 4]
0368     [1, 3, 4]
0369     [2, 3, 4]
0370 4-combs of [1, 2, 3, 4]:
0371     [1, 2, 3, 4]
0372 5-combs of [1, 2, 3, 4]:
0373 
0374 From the Iterators list, about the types of these things.
0375 
0376 >>> def g():
0377 ...     yield 1
0378 ...
0379 >>> type(g)
0380 <type 'function'>
0381 >>> i = g()
0382 >>> type(i)
0383 <type 'generator'>
0384 >>> [s for s in dir(i) if not s.startswith('_')]
0385 ['gi_frame', 'gi_running', 'next']
0386 >>> print i.next.__doc__
0387 x.next() -> the next value, or raise StopIteration
0388 >>> iter(i) is i
0389 True
0390 >>> import types
0391 >>> isinstance(i, types.GeneratorType)
0392 True
0393 
0394 And more, added later.
0395 
0396 >>> i.gi_running
0397 0
0398 >>> type(i.gi_frame)
0399 <type 'frame'>
0400 >>> i.gi_running = 42
0401 Traceback (most recent call last):
0402   ...
0403 TypeError: readonly attribute
0404 >>> def g():
0405 ...     yield me.gi_running
0406 >>> me = g()
0407 >>> me.gi_running
0408 0
0409 >>> me.next()
0410 1
0411 >>> me.gi_running
0412 0
0413 
0414 A clever union-find implementation from c.l.py, due to David Eppstein.
0415 Sent: Friday, June 29, 2001 12:16 PM
0416 To: python-list@python.org
0417 Subject: Re: PEP 255: Simple Generators
0418 
0419 >>> class disjointSet:
0420 ...     def __init__(self, name):
0421 ...         self.name = name
0422 ...         self.parent = None
0423 ...         self.generator = self.generate()
0424 ...
0425 ...     def generate(self):
0426 ...         while not self.parent:
0427 ...             yield self
0428 ...         for x in self.parent.generator:
0429 ...             yield x
0430 ...
0431 ...     def find(self):
0432 ...         return self.generator.next()
0433 ...
0434 ...     def union(self, parent):
0435 ...         if self.parent:
0436 ...             raise ValueError("Sorry, I'm not a root!")
0437 ...         self.parent = parent
0438 ...
0439 ...     def __str__(self):
0440 ...         return self.name
0441 
0442 >>> names = "ABCDEFGHIJKLM"
0443 >>> sets = [disjointSet(name) for name in names]
0444 >>> roots = sets[:]
0445 
0446 >>> import random
0447 >>> gen = random.WichmannHill(42)
0448 >>> while 1:
0449 ...     for s in sets:
0450 ...         print "%s->%s" % (s, s.find()),
0451 ...     print
0452 ...     if len(roots) > 1:
0453 ...         s1 = gen.choice(roots)
0454 ...         roots.remove(s1)
0455 ...         s2 = gen.choice(roots)
0456 ...         s1.union(s2)
0457 ...         print "merged", s1, "into", s2
0458 ...     else:
0459 ...         break
0460 A->A B->B C->C D->D E->E F->F G->G H->H I->I J->J K->K L->L M->M
0461 merged D into G
0462 A->A B->B C->C D->G E->E F->F G->G H->H I->I J->J K->K L->L M->M
0463 merged C into F
0464 A->A B->B C->F D->G E->E F->F G->G H->H I->I J->J K->K L->L M->M
0465 merged L into A
0466 A->A B->B C->F D->G E->E F->F G->G H->H I->I J->J K->K L->A M->M
0467 merged H into E
0468 A->A B->B C->F D->G E->E F->F G->G H->E I->I J->J K->K L->A M->M
0469 merged B into E
0470 A->A B->E C->F D->G E->E F->F G->G H->E I->I J->J K->K L->A M->M
0471 merged J into G
0472 A->A B->E C->F D->G E->E F->F G->G H->E I->I J->G K->K L->A M->M
0473 merged E into G
0474 A->A B->G C->F D->G E->G F->F G->G H->G I->I J->G K->K L->A M->M
0475 merged M into G
0476 A->A B->G C->F D->G E->G F->F G->G H->G I->I J->G K->K L->A M->G
0477 merged I into K
0478 A->A B->G C->F D->G E->G F->F G->G H->G I->K J->G K->K L->A M->G
0479 merged K into A
0480 A->A B->G C->F D->G E->G F->F G->G H->G I->A J->G K->A L->A M->G
0481 merged F into A
0482 A->A B->G C->A D->G E->G F->A G->G H->G I->A J->G K->A L->A M->G
0483 merged A into G
0484 A->G B->G C->G D->G E->G F->G G->G H->G I->G J->G K->G L->G M->G
0485 """
0486 # Emacs turd '
0487 
0488 # Fun tests (for sufficiently warped notions of "fun").
0489 
0490 fun_tests = """
0491 
0492 Build up to a recursive Sieve of Eratosthenes generator.
0493 
0494 >>> def firstn(g, n):
0495 ...     return [g.next() for i in range(n)]
0496 
0497 >>> def intsfrom(i):
0498 ...     while 1:
0499 ...         yield i
0500 ...         i += 1
0501 
0502 >>> firstn(intsfrom(5), 7)
0503 [5, 6, 7, 8, 9, 10, 11]
0504 
0505 >>> def exclude_multiples(n, ints):
0506 ...     for i in ints:
0507 ...         if i % n:
0508 ...             yield i
0509 
0510 >>> firstn(exclude_multiples(3, intsfrom(1)), 6)
0511 [1, 2, 4, 5, 7, 8]
0512 
0513 >>> def sieve(ints):
0514 ...     prime = ints.next()
0515 ...     yield prime
0516 ...     not_divisible_by_prime = exclude_multiples(prime, ints)
0517 ...     for p in sieve(not_divisible_by_prime):
0518 ...         yield p
0519 
0520 >>> primes = sieve(intsfrom(2))
0521 >>> firstn(primes, 20)
0522 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
0523 
0524 
0525 Another famous problem:  generate all integers of the form
0526     2**i * 3**j  * 5**k
0527 in increasing order, where i,j,k >= 0.  Trickier than it may look at first!
0528 Try writing it without generators, and correctly, and without generating
0529 3 internal results for each result output.
0530 
0531 >>> def times(n, g):
0532 ...     for i in g:
0533 ...         yield n * i
0534 >>> firstn(times(10, intsfrom(1)), 10)
0535 [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
0536 
0537 >>> def merge(g, h):
0538 ...     ng = g.next()
0539 ...     nh = h.next()
0540 ...     while 1:
0541 ...         if ng < nh:
0542 ...             yield ng
0543 ...             ng = g.next()
0544 ...         elif ng > nh:
0545 ...             yield nh
0546 ...             nh = h.next()
0547 ...         else:
0548 ...             yield ng
0549 ...             ng = g.next()
0550 ...             nh = h.next()
0551 
0552 The following works, but is doing a whale of a lot of redundant work --
0553 it's not clear how to get the internal uses of m235 to share a single
0554 generator.  Note that me_times2 (etc) each need to see every element in the
0555 result sequence.  So this is an example where lazy lists are more natural
0556 (you can look at the head of a lazy list any number of times).
0557 
0558 >>> def m235():
0559 ...     yield 1
0560 ...     me_times2 = times(2, m235())
0561 ...     me_times3 = times(3, m235())
0562 ...     me_times5 = times(5, m235())
0563 ...     for i in merge(merge(me_times2,
0564 ...                          me_times3),
0565 ...                    me_times5):
0566 ...         yield i
0567 
0568 Don't print "too many" of these -- the implementation above is extremely
0569 inefficient:  each call of m235() leads to 3 recursive calls, and in
0570 turn each of those 3 more, and so on, and so on, until we've descended
0571 enough levels to satisfy the print stmts.  Very odd:  when I printed 5
0572 lines of results below, this managed to screw up Win98's malloc in "the
0573 usual" way, i.e. the heap grew over 4Mb so Win98 started fragmenting
0574 address space, and it *looked* like a very slow leak.
0575 
0576 >>> result = m235()
0577 >>> for i in range(3):
0578 ...     print firstn(result, 15)
0579 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
0580 [25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
0581 [81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]
0582 
0583 Heh.  Here's one way to get a shared list, complete with an excruciating
0584 namespace renaming trick.  The *pretty* part is that the times() and merge()
0585 functions can be reused as-is, because they only assume their stream
0586 arguments are iterable -- a LazyList is the same as a generator to times().
0587 
0588 >>> class LazyList:
0589 ...     def __init__(self, g):
0590 ...         self.sofar = []
0591 ...         self.fetch = g.next
0592 ...
0593 ...     def __getitem__(self, i):
0594 ...         sofar, fetch = self.sofar, self.fetch
0595 ...         while i >= len(sofar):
0596 ...             sofar.append(fetch())
0597 ...         return sofar[i]
0598 
0599 >>> def m235():
0600 ...     yield 1
0601 ...     # Gack:  m235 below actually refers to a LazyList.
0602 ...     me_times2 = times(2, m235)
0603 ...     me_times3 = times(3, m235)
0604 ...     me_times5 = times(5, m235)
0605 ...     for i in merge(merge(me_times2,
0606 ...                          me_times3),
0607 ...                    me_times5):
0608 ...         yield i
0609 
0610 Print as many of these as you like -- *this* implementation is memory-
0611 efficient.
0612 
0613 >>> m235 = LazyList(m235())
0614 >>> for i in range(5):
0615 ...     print [m235[j] for j in range(15*i, 15*(i+1))]
0616 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
0617 [25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
0618 [81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]
0619 [200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384]
0620 [400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675]
0621 
0622 
0623 Ye olde Fibonacci generator, LazyList style.
0624 
0625 >>> def fibgen(a, b):
0626 ...
0627 ...     def sum(g, h):
0628 ...         while 1:
0629 ...             yield g.next() + h.next()
0630 ...
0631 ...     def tail(g):
0632 ...         g.next()    # throw first away
0633 ...         for x in g:
0634 ...             yield x
0635 ...
0636 ...     yield a
0637 ...     yield b
0638 ...     for s in sum(iter(fib),
0639 ...                  tail(iter(fib))):
0640 ...         yield s
0641 
0642 >>> fib = LazyList(fibgen(1, 2))
0643 >>> firstn(iter(fib), 17)
0644 [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
0645 """
0646 
0647 # syntax_tests mostly provokes SyntaxErrors.  Also fiddling with #if 0
0648 # hackery.
0649 
0650 syntax_tests = """
0651 
0652 >>> def f():
0653 ...     return 22
0654 ...     yield 1
0655 Traceback (most recent call last):
0656   ..
0657 SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[0]>, line 2)
0658 
0659 >>> def f():
0660 ...     yield 1
0661 ...     return 22
0662 Traceback (most recent call last):
0663   ..
0664 SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[1]>, line 3)
0665 
0666 "return None" is not the same as "return" in a generator:
0667 
0668 >>> def f():
0669 ...     yield 1
0670 ...     return None
0671 Traceback (most recent call last):
0672   ..
0673 SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[2]>, line 3)
0674 
0675 This one is fine:
0676 
0677 >>> def f():
0678 ...     yield 1
0679 ...     return
0680 
0681 >>> def f():
0682 ...     try:
0683 ...         yield 1
0684 ...     finally:
0685 ...         pass
0686 Traceback (most recent call last):
0687   ..
0688 SyntaxError: 'yield' not allowed in a 'try' block with a 'finally' clause (<doctest test.test_generators.__test__.syntax[4]>, line 3)
0689 
0690 >>> def f():
0691 ...     try:
0692 ...         try:
0693 ...             1//0
0694 ...         except ZeroDivisionError:
0695 ...             yield 666  # bad because *outer* try has finally
0696 ...         except:
0697 ...             pass
0698 ...     finally:
0699 ...         pass
0700 Traceback (most recent call last):
0701   ...
0702 SyntaxError: 'yield' not allowed in a 'try' block with a 'finally' clause (<doctest test.test_generators.__test__.syntax[5]>, line 6)
0703 
0704 But this is fine:
0705 
0706 >>> def f():
0707 ...     try:
0708 ...         try:
0709 ...             yield 12
0710 ...             1//0
0711 ...         except ZeroDivisionError:
0712 ...             yield 666
0713 ...         except:
0714 ...             try:
0715 ...                 x = 12
0716 ...             finally:
0717 ...                 yield 12
0718 ...     except:
0719 ...         return
0720 >>> list(f())
0721 [12, 666]
0722 
0723 >>> def f():
0724 ...    yield
0725 Traceback (most recent call last):
0726 SyntaxError: invalid syntax
0727 
0728 >>> def f():
0729 ...    if 0:
0730 ...        yield
0731 Traceback (most recent call last):
0732 SyntaxError: invalid syntax
0733 
0734 >>> def f():
0735 ...     if 0:
0736 ...         yield 1
0737 >>> type(f())
0738 <type 'generator'>
0739 
0740 >>> def f():
0741 ...    if "":
0742 ...        yield None
0743 >>> type(f())
0744 <type 'generator'>
0745 
0746 >>> def f():
0747 ...     return
0748 ...     try:
0749 ...         if x==4:
0750 ...             pass
0751 ...         elif 0:
0752 ...             try:
0753 ...                 1//0
0754 ...             except SyntaxError:
0755 ...                 pass
0756 ...             else:
0757 ...                 if 0:
0758 ...                     while 12:
0759 ...                         x += 1
0760 ...                         yield 2 # don't blink
0761 ...                         f(a, b, c, d, e)
0762 ...         else:
0763 ...             pass
0764 ...     except:
0765 ...         x = 1
0766 ...     return
0767 >>> type(f())
0768 <type 'generator'>
0769 
0770 >>> def f():
0771 ...     if 0:
0772 ...         def g():
0773 ...             yield 1
0774 ...
0775 >>> type(f())
0776 <type 'NoneType'>
0777 
0778 >>> def f():
0779 ...     if 0:
0780 ...         class C:
0781 ...             def __init__(self):
0782 ...                 yield 1
0783 ...             def f(self):
0784 ...                 yield 2
0785 >>> type(f())
0786 <type 'NoneType'>
0787 
0788 >>> def f():
0789 ...     if 0:
0790 ...         return
0791 ...     if 0:
0792 ...         yield 2
0793 >>> type(f())
0794 <type 'generator'>
0795 
0796 
0797 >>> def f():
0798 ...     if 0:
0799 ...         lambda x:  x        # shouldn't trigger here
0800 ...         return              # or here
0801 ...         def f(i):
0802 ...             return 2*i      # or here
0803 ...         if 0:
0804 ...             return 3        # but *this* sucks (line 8)
0805 ...     if 0:
0806 ...         yield 2             # because it's a generator
0807 Traceback (most recent call last):
0808 SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[22]>, line 8)
0809 
0810 This one caused a crash (see SF bug 567538):
0811 
0812 >>> def f():
0813 ...     for i in range(3):
0814 ...         try:
0815 ...             continue
0816 ...         finally:
0817 ...             yield i
0818 ...
0819 >>> g = f()
0820 >>> print g.next()
0821 0
0822 >>> print g.next()
0823 1
0824 >>> print g.next()
0825 2
0826 >>> print g.next()
0827 Traceback (most recent call last):
0828 StopIteration
0829 """
0830 
0831 # conjoin is a simple backtracking generator, named in honor of Icon's
0832 # "conjunction" control structure.  Pass a list of no-argument functions
0833 # that return iterable objects.  Easiest to explain by example:  assume the
0834 # function list [x, y, z] is passed.  Then conjoin acts like:
0835 #
0836 # def g():
0837 #     values = [None] * 3
0838 #     for values[0] in x():
0839 #         for values[1] in y():
0840 #             for values[2] in z():
0841 #                 yield values
0842 #
0843 # So some 3-lists of values *may* be generated, each time we successfully
0844 # get into the innermost loop.  If an iterator fails (is exhausted) before
0845 # then, it "backtracks" to get the next value from the nearest enclosing
0846 # iterator (the one "to the left"), and starts all over again at the next
0847 # slot (pumps a fresh iterator).  Of course this is most useful when the
0848 # iterators have side-effects, so that which values *can* be generated at
0849 # each slot depend on the values iterated at previous slots.
0850 
0851 def conjoin(gs):
0852 
0853     values = [None] * len(gs)
0854 
0855     def gen(i, values=values):
0856         if i >= len(gs):
0857             yield values
0858         else:
0859             for values[i] in gs[i]():
0860                 for x in gen(i+1):
0861                     yield x
0862 
0863     for x in gen(0):
0864         yield x
0865 
0866 # That works fine, but recursing a level and checking i against len(gs) for
0867 # each item produced is inefficient.  By doing manual loop unrolling across
0868 # generator boundaries, it's possible to eliminate most of that overhead.
0869 # This isn't worth the bother *in general* for generators, but conjoin() is
0870 # a core building block for some CPU-intensive generator applications.
0871 
0872 def conjoin(gs):
0873 
0874     n = len(gs)
0875     values = [None] * n
0876 
0877     # Do one loop nest at time recursively, until the # of loop nests
0878     # remaining is divisible by 3.
0879 
0880     def gen(i, values=values):
0881         if i >= n:
0882             yield values
0883 
0884         elif (n-i) % 3:
0885             ip1 = i+1
0886             for values[i] in gs[i]():
0887                 for x in gen(ip1):
0888                     yield x
0889 
0890         else:
0891             for x in _gen3(i):
0892                 yield x
0893 
0894     # Do three loop nests at a time, recursing only if at least three more
0895     # remain.  Don't call directly:  this is an internal optimization for
0896     # gen's use.
0897 
0898     def _gen3(i, values=values):
0899         assert i < n and (n-i) % 3 == 0
0900         ip1, ip2, ip3 = i+1, i+2, i+3
0901         g, g1, g2 = gs[i : ip3]
0902 
0903         if ip3 >= n:
0904             # These are the last three, so we can yield values directly.
0905             for values[i] in g():
0906                 for values[ip1] in g1():
0907                     for values[ip2] in g2():
0908                         yield values
0909 
0910         else:
0911             # At least 6 loop nests remain; peel off 3 and recurse for the
0912             # rest.
0913             for values[i] in g():
0914                 for values[ip1] in g1():
0915                     for values[ip2] in g2():
0916                         for x in _gen3(ip3):
0917                             yield x
0918 
0919     for x in gen(0):
0920         yield x
0921 
0922 # And one more approach:  For backtracking apps like the Knight's Tour
0923 # solver below, the number of backtracking levels can be enormous (one
0924 # level per square, for the Knight's Tour, so that e.g. a 100x100 board
0925 # needs 10,000 levels).  In such cases Python is likely to run out of
0926 # stack space due to recursion.  So here's a recursion-free version of
0927 # conjoin too.
0928 # NOTE WELL:  This allows large problems to be solved with only trivial
0929 # demands on stack space.  Without explicitly resumable generators, this is
0930 # much harder to achieve.  OTOH, this is much slower (up to a factor of 2)
0931 # than the fancy unrolled recursive conjoin.
0932 
0933 def flat_conjoin(gs):  # rename to conjoin to run tests with this instead
0934     n = len(gs)
0935     values = [None] * n
0936     iters  = [None] * n
0937     _StopIteration = StopIteration  # make local because caught a *lot*
0938     i = 0
0939     while 1:
0940         # Descend.
0941         try:
0942             while i < n:
0943                 it = iters[i] = gs[i]().next
0944                 values[i] = it()
0945                 i += 1
0946         except _StopIteration:
0947             pass
0948         else:
0949             assert i == n
0950             yield values
0951 
0952         # Backtrack until an older iterator can be resumed.
0953         i -= 1
0954         while i >= 0:
0955             try:
0956                 values[i] = iters[i]()
0957                 # Success!  Start fresh at next level.
0958                 i += 1
0959                 break
0960             except _StopIteration:
0961                 # Continue backtracking.
0962                 i -= 1
0963         else:
0964             assert i < 0
0965             break
0966 
0967 # A conjoin-based N-Queens solver.
0968 
0969 class Queens:
0970     def __init__(self, n):
0971         self.n = n
0972         rangen = range(n)
0973 
0974         # Assign a unique int to each column and diagonal.
0975         # columns:  n of those, range(n).
0976         # NW-SE diagonals: 2n-1 of these, i-j unique and invariant along
0977         # each, smallest i-j is 0-(n-1) = 1-n, so add n-1 to shift to 0-
0978         # based.
0979         # NE-SW diagonals: 2n-1 of these, i+j unique and invariant along
0980         # each, smallest i+j is 0, largest is 2n-2.
0981 
0982         # For each square, compute a bit vector of the columns and
0983         # diagonals it covers, and for each row compute a function that
0984         # generates the possiblities for the columns in that row.
0985         self.rowgenerators = []
0986         for i in rangen:
0987             rowuses = [(1L << j) |                  # column ordinal
0988                        (1L << (n + i-j + n-1)) |    # NW-SE ordinal
0989                        (1L << (n + 2*n-1 + i+j))    # NE-SW ordinal
0990                             for j in rangen]
0991 
0992             def rowgen(rowuses=rowuses):
0993                 for j in rangen:
0994                     uses = rowuses[j]
0995                     if uses & self.used == 0:
0996                         self.used |= uses
0997                         yield j
0998                         self.used &= ~uses
0999 
1000             self.rowgenerators.append(rowgen)
1001 
1002     # Generate solutions.
1003     def solve(self):
1004         self.used = 0
1005         for row2col in conjoin(self.rowgenerators):
1006             yield row2col
1007 
1008     def printsolution(self, row2col):
1009         n = self.n
1010         assert n == len(row2col)
1011         sep = "+" + "-+" * n
1012         print sep
1013         for i in range(n):
1014             squares = [" " for j in range(n)]
1015             squares[row2col[i]] = "Q"
1016             print "|" + "|".join(squares) + "|"
1017             print sep
1018 
1019 # A conjoin-based Knight's Tour solver.  This is pretty sophisticated
1020 # (e.g., when used with flat_conjoin above, and passing hard=1 to the
1021 # constructor, a 200x200 Knight's Tour was found quickly -- note that we're
1022 # creating 10s of thousands of generators then!), and is lengthy.
1023 
1024 class Knights:
1025     def __init__(self, m, n, hard=0):
1026         self.m, self.n = m, n
1027 
1028         # solve() will set up succs[i] to be a list of square #i's
1029         # successors.
1030         succs = self.succs = []
1031 
1032         # Remove i0 from each of its successor's successor lists, i.e.
1033         # successors can't go back to i0 again.  Return 0 if we can
1034         # detect this makes a solution impossible, else return 1.
1035 
1036         def remove_from_successors(i0, len=len):
1037             # If we remove all exits from a free square, we're dead:
1038             # even if we move to it next, we can't leave it again.
1039             # If we create a square with one exit, we must visit it next;
1040             # else somebody else will have to visit it, and since there's
1041             # only one adjacent, there won't be a way to leave it again.
1042             # Finelly, if we create more than one free square with a
1043             # single exit, we can only move to one of them next, leaving
1044             # the other one a dead end.
1045             ne0 = ne1 = 0
1046             for i in succs[i0]:
1047                 s = succs[i]
1048                 s.remove(i0)
1049                 e = len(s)
1050                 if e == 0:
1051                     ne0 += 1
1052                 elif e == 1:
1053                     ne1 += 1
1054             return ne0 == 0 and ne1 < 2
1055 
1056         # Put i0 back in each of its successor's successor lists.
1057 
1058         def add_to_successors(i0):
1059             for i in succs[i0]:
1060                 succs[i].append(i0)
1061 
1062         # Generate the first move.
1063         def first():
1064             if m < 1 or n < 1:
1065                 return
1066 
1067             # Since we're looking for a cycle, it doesn't matter where we
1068             # start.  Starting in a corner makes the 2nd move easy.
1069             corner = self.coords2index(0, 0)
1070             remove_from_successors(corner)
1071             self.lastij = corner
1072             yield corner
1073             add_to_successors(corner)
1074 
1075         # Generate the second moves.
1076         def second():
1077             corner = self.coords2index(0, 0)
1078             assert self.lastij == corner  # i.e., we started in the corner
1079             if m < 3 or n < 3:
1080                 return
1081             assert len(succs[corner]) == 2
1082             assert self.coords2index(1, 2) in succs[corner]
1083             assert self.coords2index(2, 1) in succs[corner]
1084             # Only two choices.  Whichever we pick, the other must be the
1085             # square picked on move m*n, as it's the only way to get back
1086             # to (0, 0).  Save its index in self.final so that moves before
1087             # the last know it must be kept free.
1088             for i, j in (1, 2), (2, 1):
1089                 this  = self.coords2index(i, j)
1090                 final = self.coords2index(3-i, 3-j)
1091                 self.final = final
1092 
1093                 remove_from_successors(this)
1094                 succs[final].append(corner)
1095                 self.lastij = this
1096                 yield this
1097                 succs[final].remove(corner)
1098                 add_to_successors(this)
1099 
1100         # Generate moves 3 thru m*n-1.
1101         def advance(len=len):
1102             # If some successor has only one exit, must take it.
1103             # Else favor successors with fewer exits.
1104             candidates = []
1105             for i in succs[self.lastij]:
1106                 e = len(succs[i])
1107                 assert e > 0, "else remove_from_successors() pruning flawed"
1108                 if e == 1:
1109                     candidates = [(e, i)]
1110                     break
1111                 candidates.append((e, i))
1112             else:
1113                 candidates.sort()
1114 
1115             for e, i in candidates:
1116                 if i != self.final:
1117                     if remove_from_successors(i):
1118                         self.lastij = i
1119                         yield i
1120                     add_to_successors(i)
1121 
1122         # Generate moves 3 thru m*n-1.  Alternative version using a
1123         # stronger (but more expensive) heuristic to order successors.
1124         # Since the # of backtracking levels is m*n, a poor move early on
1125         # can take eons to undo.  Smallest square board for which this
1126         # matters a lot is 52x52.
1127         def advance_hard(vmid=(m-1)/2.0, hmid=(n-1)/2.0, len=len):
1128             # If some successor has only one exit, must take it.
1129             # Else favor successors with fewer exits.
1130             # Break ties via max distance from board centerpoint (favor
1131             # corners and edges whenever possible).
1132             candidates = []
1133             for i in succs[self.lastij]:
1134                 e = len(succs[i])
1135                 assert e > 0, "else remove_from_successors() pruning flawed"
1136                 if e == 1:
1137                     candidates = [(e, 0, i)]
1138                     break
1139                 i1, j1 = self.index2coords(i)
1140                 d = (i1 - vmid)**2 + (j1 - hmid)**2
1141                 candidates.append((e, -d, i))
1142             else:
1143                 candidates.sort()
1144 
1145             for e, d, i in candidates:
1146                 if i != self.final:
1147                     if remove_from_successors(i):
1148                         self.lastij = i
1149                         yield i
1150                     add_to_successors(i)
1151 
1152         # Generate the last move.
1153         def last():
1154             assert self.final in succs[self.lastij]
1155             yield self.final
1156 
1157         if m*n < 4:
1158             self.squaregenerators = [first]
1159         else:
1160             self.squaregenerators = [first, second] + \
1161                 [hard and advance_hard or advance] * (m*n - 3) + \
1162                 [last]
1163 
1164     def coords2index(self, i, j):
1165         assert 0 <= i < self.m
1166         assert 0 <= j < self.n
1167         return i * self.n + j
1168 
1169     def index2coords(self, index):
1170         assert 0 <= index < self.m * self.n
1171         return divmod(index, self.n)
1172 
1173     def _init_board(self):
1174         succs = self.succs
1175         del succs[:]
1176         m, n = self.m, self.n
1177         c2i = self.coords2index
1178 
1179         offsets = [( 1,  2), ( 2,  1), ( 2, -1), ( 1, -2),
1180                    (-1, -2), (-2, -1), (-2,  1), (-1,  2)]
1181         rangen = range(n)
1182         for i in range(m):
1183             for j in rangen:
1184                 s = [c2i(i+io, j+jo) for io, jo in offsets
1185                                      if 0 <= i+io < m and
1186                                         0 <= j+jo < n]
1187                 succs.append(s)
1188 
1189     # Generate solutions.
1190     def solve(self):
1191         self._init_board()
1192         for x in conjoin(self.squaregenerators):
1193             yield x
1194 
1195     def printsolution(self, x):
1196         m, n = self.m, self.n
1197         assert len(x) == m*n
1198         w = len(str(m*n))
1199         format = "%" + str(w) + "d"
1200 
1201         squares = [[None] * n for i in range(m)]
1202         k = 1
1203         for i in x:
1204             i1, j1 = self.index2coords(i)
1205             squares[i1][j1] = format % k
1206             k += 1
1207 
1208         sep = "+" + ("-" * w + "+") * n
1209         print sep
1210         for i in range(m):
1211             row = squares[i]
1212             print "|" + "|".join(row) + "|"
1213             print sep
1214 
1215 conjoin_tests = """
1216 
1217 Generate the 3-bit binary numbers in order.  This illustrates dumbest-
1218 possible use of conjoin, just to generate the full cross-product.
1219 
1220 >>> for c in conjoin([lambda: iter((0, 1))] * 3):
1221 ...     print c
1222 [0, 0, 0]
1223 [0, 0, 1]
1224 [0, 1, 0]
1225 [0, 1, 1]
1226 [1, 0, 0]
1227 [1, 0, 1]
1228 [1, 1, 0]
1229 [1, 1, 1]
1230 
1231 For efficiency in typical backtracking apps, conjoin() yields the same list
1232 object each time.  So if you want to save away a full account of its
1233 generated sequence, you need to copy its results.
1234 
1235 >>> def gencopy(iterator):
1236 ...     for x in iterator:
1237 ...         yield x[:]
1238 
1239 >>> for n in range(10):
1240 ...     all = list(gencopy(conjoin([lambda: iter((0, 1))] * n)))
1241 ...     print n, len(all), all[0] == [0] * n, all[-1] == [1] * n
1242 0 1 True True
1243 1 2 True True
1244 2 4 True True
1245 3 8 True True
1246 4 16 True True
1247 5 32 True True
1248 6 64 True True
1249 7 128 True True
1250 8 256 True True
1251 9 512 True True
1252 
1253 And run an 8-queens solver.
1254 
1255 >>> q = Queens(8)
1256 >>> LIMIT = 2
1257 >>> count = 0
1258 >>> for row2col in q.solve():
1259 ...     count += 1
1260 ...     if count <= LIMIT:
1261 ...         print "Solution", count
1262 ...         q.printsolution(row2col)
1263 Solution 1
1264 +-+-+-+-+-+-+-+-+
1265 |Q| | | | | | | |
1266 +-+-+-+-+-+-+-+-+
1267 | | | | |Q| | | |
1268 +-+-+-+-+-+-+-+-+
1269 | | | | | | | |Q|
1270 +-+-+-+-+-+-+-+-+
1271 | | | | | |Q| | |
1272 +-+-+-+-+-+-+-+-+
1273 | | |Q| | | | | |
1274 +-+-+-+-+-+-+-+-+
1275 | | | | | | |Q| |
1276 +-+-+-+-+-+-+-+-+
1277 | |Q| | | | | | |
1278 +-+-+-+-+-+-+-+-+
1279 | | | |Q| | | | |
1280 +-+-+-+-+-+-+-+-+
1281 Solution 2
1282 +-+-+-+-+-+-+-+-+
1283 |Q| | | | | | | |
1284 +-+-+-+-+-+-+-+-+
1285 | | | | | |Q| | |
1286 +-+-+-+-+-+-+-+-+
1287 | | | | | | | |Q|
1288 +-+-+-+-+-+-+-+-+
1289 | | |Q| | | | | |
1290 +-+-+-+-+-+-+-+-+
1291 | | | | | | |Q| |
1292 +-+-+-+-+-+-+-+-+
1293 | | | |Q| | | | |
1294 +-+-+-+-+-+-+-+-+
1295 | |Q| | | | | | |
1296 +-+-+-+-+-+-+-+-+
1297 | | | | |Q| | | |
1298 +-+-+-+-+-+-+-+-+
1299 
1300 >>> print count, "solutions in all."
1301 92 solutions in all.
1302 
1303 And run a Knight's Tour on a 10x10 board.  Note that there are about
1304 20,000 solutions even on a 6x6 board, so don't dare run this to exhaustion.
1305 
1306 >>> k = Knights(10, 10)
1307 >>> LIMIT = 2
1308 >>> count = 0
1309 >>> for x in k.solve():
1310 ...     count += 1
1311 ...     if count <= LIMIT:
1312 ...         print "Solution", count
1313 ...         k.printsolution(x)
1314 ...     else:
1315 ...         break
1316 Solution 1
1317 +---+---+---+---+---+---+---+---+---+---+
1318 |  1| 58| 27| 34|  3| 40| 29| 10|  5|  8|
1319 +---+---+---+---+---+---+---+---+---+---+
1320 | 26| 35|  2| 57| 28| 33|  4|  7| 30| 11|
1321 +---+---+---+---+---+---+---+---+---+---+
1322 | 59|100| 73| 36| 41| 56| 39| 32|  9|  6|
1323 +---+---+---+---+---+---+---+---+---+---+
1324 | 74| 25| 60| 55| 72| 37| 42| 49| 12| 31|
1325 +---+---+---+---+---+---+---+---+---+---+
1326 | 61| 86| 99| 76| 63| 52| 47| 38| 43| 50|
1327 +---+---+---+---+---+---+---+---+---+---+
1328 | 24| 75| 62| 85| 54| 71| 64| 51| 48| 13|
1329 +---+---+---+---+---+---+---+---+---+---+
1330 | 87| 98| 91| 80| 77| 84| 53| 46| 65| 44|
1331 +---+---+---+---+---+---+---+---+---+---+
1332 | 90| 23| 88| 95| 70| 79| 68| 83| 14| 17|
1333 +---+---+---+---+---+---+---+---+---+---+
1334 | 97| 92| 21| 78| 81| 94| 19| 16| 45| 66|
1335 +---+---+---+---+---+---+---+---+---+---+
1336 | 22| 89| 96| 93| 20| 69| 82| 67| 18| 15|
1337 +---+---+---+---+---+---+---+---+---+---+
1338 Solution 2
1339 +---+---+---+---+---+---+---+---+---+---+
1340 |  1| 58| 27| 34|  3| 40| 29| 10|  5|  8|
1341 +---+---+---+---+---+---+---+---+---+---+
1342 | 26| 35|  2| 57| 28| 33|  4|  7| 30| 11|
1343 +---+---+---+---+---+---+---+---+---+---+
1344 | 59|100| 73| 36| 41| 56| 39| 32|  9|  6|
1345 +---+---+---+---+---+---+---+---+---+---+
1346 | 74| 25| 60| 55| 72| 37| 42| 49| 12| 31|
1347 +---+---+---+---+---+---+---+---+---+---+
1348 | 61| 86| 99| 76| 63| 52| 47| 38| 43| 50|
1349 +---+---+---+---+---+---+---+---+---+---+
1350 | 24| 75| 62| 85| 54| 71| 64| 51| 48| 13|
1351 +---+---+---+---+---+---+---+---+---+---+
1352 | 87| 98| 89| 80| 77| 84| 53| 46| 65| 44|
1353 +---+---+---+---+---+---+---+---+---+---+
1354 | 90| 23| 92| 95| 70| 79| 68| 83| 14| 17|
1355 +---+---+---+---+---+---+---+---+---+---+
1356 | 97| 88| 21| 78| 81| 94| 19| 16| 45| 66|
1357 +---+---+---+---+---+---+---+---+---+---+
1358 | 22| 91| 96| 93| 20| 69| 82| 67| 18| 15|
1359 +---+---+---+---+---+---+---+---+---+---+
1360 """
1361 
1362 weakref_tests = """\
1363 Generators are weakly referencable:
1364 
1365 >>> import weakref
1366 >>> def gen():
1367 ...     yield 'foo!'
1368 ...
1369 >>> wr = weakref.ref(gen)
1370 >>> wr() is gen
1371 True
1372 >>> p = weakref.proxy(gen)
1373 
1374 Generator-iterators are weakly referencable as well:
1375 
1376 >>> gi = gen()
1377 >>> wr = weakref.ref(gi)
1378 >>> wr() is gi
1379 True
1380 >>> p = weakref.proxy(gi)
1381 >>> list(p)
1382 ['foo!']
1383 
1384 """
1385 
1386 __test__ = {"tut":      tutorial_tests,
1387             "pep":      pep_tests,
1388             "email":    email_tests,
1389             "fun":      fun_tests,
1390             "syntax":   syntax_tests,
1391             "conjoin":  conjoin_tests,
1392             "weakref":  weakref_tests,
1393             }
1394 
1395 # Magic test name that regrtest.py invokes *after* importing this module.
1396 # This worms around a bootstrap problem.
1397 # Note that doctest and regrtest both look in sys.argv for a "-v" argument,
1398 # so this works as expected in both ways of running regrtest.
1399 def test_main(verbose=None):
1400     from test import test_support, test_generators
1401     test_support.run_doctest(test_generators, verbose)
1402 
1403 # This part isn't needed for regrtest, but for running the test directly.
1404 if __name__ == "__main__":
1405     test_main(1)
1406 

Generated by PyXR 0.9.4
SourceForge.net Logo