[Python-checkins] CVS: python/dist/src/Lib/test test_generators.py,1.15,1.16

[Tim Peters]

Update of /cvsroot/python/python/dist/src/Lib/test
In directory usw-pr-cvs1:/tmp/cvs-serv15192/python/dist/src/Lib/test

Modified Files:
	test_generators.py 
Log Message:
A clever union-find implementation from c.l.py, due to David Eppstein.
This is another one that leaks memory without an explict clear!  Time to
bite this bullet.


Index: test_generators.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/test/test_generators.py,v
retrieving revision 1.15
retrieving revision 1.16
diff -C2 -r1.15 -r1.16
*** test_generators.py	2001/06/30 07:29:44	1.15
--- test_generators.py	2001/07/02 01:38:33	1.16
***************
*** 410,413 ****
--- 410,490 ----
  >>> me.gi_running
  0
+ 
+ A clever union-find implementation from c.l.py, due to David Eppstein.
+ Sent: Friday, June 29, 2001 12:16 PM
+ To: python-list@python.org
+ Subject: Re: PEP 255: Simple Generators
+ 
+ >>> class disjointSet:
+ ...     def __init__(self, name):
+ ...         self.name = name
+ ...         self.parent = None
+ ...         self.generator = self.generate()
+ ...
+ ...     def generate(self):
+ ...         while not self.parent:
+ ...             yield self
+ ...         for x in self.parent.generator:
+ ...             yield x
+ ...
+ ...     def find(self):
+ ...         return self.generator.next()
+ ...
+ ...     def union(self, parent):
+ ...         if self.parent:
+ ...             raise ValueError("Sorry, I'm not a root!")
+ ...         self.parent = parent
+ ...
+ ...     def __str__(self):
+ ...         return self.name
+ ...
+ ...     def clear(self):
+ ...         self.__dict__.clear()
+ 
+ >>> names = "ABCDEFGHIJKLM"
+ >>> sets = [disjointSet(name) for name in names]
+ >>> roots = sets[:]
+ 
+ >>> import random
+ >>> random.seed(42)
+ >>> while 1:
+ ...     for s in sets:
+ ...         print "%s->%s" % (s, s.find()),
+ ...     print
+ ...     if len(roots) > 1:
+ ...         s1 = random.choice(roots)
+ ...         roots.remove(s1)
+ ...         s2 = random.choice(roots)
+ ...         s1.union(s2)
+ ...         print "merged", s1, "into", s2
+ ...     else:
+ ...         break
+ 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
+ merged D into G
+ 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
+ merged C into F
+ 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
+ merged L into A
+ 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
+ merged H into E
+ 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
+ merged B into E
+ 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
+ merged J into G
+ 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
+ merged E into G
+ 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
+ merged M into G
+ 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
+ merged I into K
+ 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
+ merged K into A
+ 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
+ merged F into A
+ 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
+ merged A into G
+ 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
+ >>> for s in sets:  # XXX memory leak without this
+ ...    s.clear()
  """