Merged revisions 61209-61214,61217-61222,61224-61226,61233-61237 via svnmerge from
svn+ssh://pythondev@svn.python.org/python/trunk
........
r61209 | georg.brandl | 2008-03-03 21:37:55 +0100 (Mon, 03 Mar 2008) | 2 lines
There are now sixteen isfoo functions.
........
r61210 | georg.brandl | 2008-03-03 21:39:00 +0100 (Mon, 03 Mar 2008) | 2 lines
15 -> 16, the 2nd
........
r61211 | georg.brandl | 2008-03-03 22:22:47 +0100 (Mon, 03 Mar 2008) | 2 lines
Actually import itertools.
........
r61212 | georg.brandl | 2008-03-03 22:31:50 +0100 (Mon, 03 Mar 2008) | 2 lines
Expand a bit on genexp scopes.
........
r61213 | raymond.hettinger | 2008-03-03 23:04:55 +0100 (Mon, 03 Mar 2008) | 1 line
Remove dependency on itertools -- a simple genexp suffices.
........
r61214 | raymond.hettinger | 2008-03-03 23:19:58 +0100 (Mon, 03 Mar 2008) | 1 line
Issue 2226: Callable checked for the wrong abstract method.
........
r61217 | andrew.kuchling | 2008-03-04 01:40:32 +0100 (Tue, 04 Mar 2008) | 1 line
Typo fix
........
r61218 | andrew.kuchling | 2008-03-04 02:30:10 +0100 (Tue, 04 Mar 2008) | 1 line
Grammar fix; markup fix
........
r61219 | andrew.kuchling | 2008-03-04 02:47:38 +0100 (Tue, 04 Mar 2008) | 1 line
Fix sentence fragment
........
r61220 | andrew.kuchling | 2008-03-04 02:48:26 +0100 (Tue, 04 Mar 2008) | 1 line
Typo fix
........
r61221 | andrew.kuchling | 2008-03-04 02:49:37 +0100 (Tue, 04 Mar 2008) | 1 line
Add versionadded tags
........
r61222 | andrew.kuchling | 2008-03-04 02:50:32 +0100 (Tue, 04 Mar 2008) | 1 line
Thesis night results: add various items
........
r61224 | raymond.hettinger | 2008-03-04 05:17:08 +0100 (Tue, 04 Mar 2008) | 1 line
Beef-up docs and tests for itertools. Fix-up end-case for product().
........
r61225 | georg.brandl | 2008-03-04 08:25:54 +0100 (Tue, 04 Mar 2008) | 2 lines
Fix some patch attributions.
........
r61226 | georg.brandl | 2008-03-04 08:33:30 +0100 (Tue, 04 Mar 2008) | 2 lines
#2230: document that PyArg_* leaves addresses alone on error.
........
r61233 | neal.norwitz | 2008-03-04 17:22:46 +0100 (Tue, 04 Mar 2008) | 3 lines
Close the file before trying to remove the directory so it works on Windows.
As reported by Trent Nelson on python-dev.
........
r61234 | thomas.heller | 2008-03-04 21:09:11 +0100 (Tue, 04 Mar 2008) | 9 lines
Merged changes from libffi3-branch.
The bundled libffi copy is now in sync with the recently released
libffi3.0.4 version, apart from some small changes to
Modules/_ctypes/libffi/configure.ac.
I gave up on using libffi3 files on os x.
Instead, static configuration with files from pyobjc is used.
........
r61235 | thomas.heller | 2008-03-04 21:21:42 +0100 (Tue, 04 Mar 2008) | 1 line
Try to fix the build for PY_LINUX.
........
r61236 | fred.drake | 2008-03-04 22:14:04 +0100 (Tue, 04 Mar 2008) | 2 lines
fix typo
........
r61237 | raymond.hettinger | 2008-03-04 23:29:44 +0100 (Tue, 04 Mar 2008) | 1 line
Fix refleak in chain().
........
diff --git a/Lib/test/test_itertools.py b/Lib/test/test_itertools.py
index 44762eb..4e0902b 100644
--- a/Lib/test/test_itertools.py
+++ b/Lib/test/test_itertools.py
@@ -44,9 +44,21 @@
'Convenience function for partially consuming a long of infinite iterable'
return list(islice(seq, n))
+def prod(iterable):
+ return reduce(operator.mul, iterable, 1)
+
def fact(n):
'Factorial'
- return reduce(operator.mul, range(1, n+1), 1)
+ return prod(range(1, n+1))
+
+def permutations(iterable, r=None):
+ # XXX use this until real permutations code is added
+ pool = tuple(iterable)
+ n = len(pool)
+ r = n if r is None else r
+ for indices in product(range(n), repeat=r):
+ if len(set(indices)) == r:
+ yield tuple(pool[i] for i in indices)
class TestBasicOps(unittest.TestCase):
def test_chain(self):
@@ -66,11 +78,38 @@
def test_combinations(self):
self.assertRaises(TypeError, combinations, 'abc') # missing r argument
self.assertRaises(TypeError, combinations, 'abc', 2, 1) # too many arguments
+ self.assertRaises(TypeError, combinations, None) # pool is not iterable
self.assertRaises(ValueError, combinations, 'abc', -2) # r is negative
self.assertRaises(ValueError, combinations, 'abc', 32) # r is too big
self.assertEqual(list(combinations(range(4), 3)),
[(0,1,2), (0,1,3), (0,2,3), (1,2,3)])
- for n in range(8):
+
+ def combinations1(iterable, r):
+ 'Pure python version shown in the docs'
+ pool = tuple(iterable)
+ n = len(pool)
+ indices = list(range(r))
+ yield tuple(pool[i] for i in indices)
+ while 1:
+ for i in reversed(range(r)):
+ if indices[i] != i + n - r:
+ break
+ else:
+ return
+ indices[i] += 1
+ for j in range(i+1, r):
+ indices[j] = indices[j-1] + 1
+ yield tuple(pool[i] for i in indices)
+
+ def combinations2(iterable, r):
+ 'Pure python version shown in the docs'
+ pool = tuple(iterable)
+ n = len(pool)
+ for indices in permutations(range(n), r):
+ if sorted(indices) == list(indices):
+ yield tuple(pool[i] for i in indices)
+
+ for n in range(7):
values = [5*x-12 for x in range(n)]
for r in range(n+1):
result = list(combinations(values, r))
@@ -82,6 +121,73 @@
self.assertEqual(len(set(c)), r) # no duplicate elements
self.assertEqual(list(c), sorted(c)) # keep original ordering
self.assert_(all(e in values for e in c)) # elements taken from input iterable
+ self.assertEqual(result, list(combinations1(values, r))) # matches first pure python version
+ self.assertEqual(result, list(combinations2(values, r))) # matches first pure python version
+
+ # Test implementation detail: tuple re-use
+ self.assertEqual(len(set(map(id, combinations('abcde', 3)))), 1)
+ self.assertNotEqual(len(set(map(id, list(combinations('abcde', 3))))), 1)
+
+ def test_permutations(self):
+ self.assertRaises(TypeError, permutations) # too few arguments
+ self.assertRaises(TypeError, permutations, 'abc', 2, 1) # too many arguments
+## self.assertRaises(TypeError, permutations, None) # pool is not iterable
+## self.assertRaises(ValueError, permutations, 'abc', -2) # r is negative
+## self.assertRaises(ValueError, permutations, 'abc', 32) # r is too big
+ self.assertEqual(list(permutations(range(3), 2)),
+ [(0,1), (0,2), (1,0), (1,2), (2,0), (2,1)])
+
+ def permutations1(iterable, r=None):
+ 'Pure python version shown in the docs'
+ pool = tuple(iterable)
+ n = len(pool)
+ r = n if r is None else r
+ indices = list(range(n))
+ cycles = list(range(n-r+1, n+1))[::-1]
+ yield tuple(pool[i] for i in indices[:r])
+ while n:
+ for i in reversed(range(r)):
+ cycles[i] -= 1
+ if cycles[i] == 0:
+ indices[i:] = indices[i+1:] + indices[i:i+1]
+ cycles[i] = n - i
+ else:
+ j = cycles[i]
+ indices[i], indices[-j] = indices[-j], indices[i]
+ yield tuple(pool[i] for i in indices[:r])
+ break
+ else:
+ return
+
+ def permutations2(iterable, r=None):
+ 'Pure python version shown in the docs'
+ pool = tuple(iterable)
+ n = len(pool)
+ r = n if r is None else r
+ for indices in product(range(n), repeat=r):
+ if len(set(indices)) == r:
+ yield tuple(pool[i] for i in indices)
+
+ for n in range(7):
+ values = [5*x-12 for x in range(n)]
+ for r in range(n+1):
+ result = list(permutations(values, r))
+ self.assertEqual(len(result), fact(n) / fact(n-r)) # right number of perms
+ self.assertEqual(len(result), len(set(result))) # no repeats
+ self.assertEqual(result, sorted(result)) # lexicographic order
+ for p in result:
+ self.assertEqual(len(p), r) # r-length permutations
+ self.assertEqual(len(set(p)), r) # no duplicate elements
+ self.assert_(all(e in values for e in p)) # elements taken from input iterable
+ self.assertEqual(result, list(permutations1(values, r))) # matches first pure python version
+ self.assertEqual(result, list(permutations2(values, r))) # matches first pure python version
+ if r == n:
+ self.assertEqual(result, list(permutations(values, None))) # test r as None
+ self.assertEqual(result, list(permutations(values))) # test default r
+
+ # Test implementation detail: tuple re-use
+## self.assertEqual(len(set(map(id, permutations('abcde', 3)))), 1)
+ self.assertNotEqual(len(set(map(id, list(permutations('abcde', 3))))), 1)
def test_count(self):
self.assertEqual(lzip('abc',count()), [('a', 0), ('b', 1), ('c', 2)])
@@ -297,7 +403,7 @@
def test_product(self):
for args, result in [
- ([], []), # zero iterables ??? is this correct
+ ([], [()]), # zero iterables
(['ab'], [('a',), ('b',)]), # one iterable
([range(2), range(3)], [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2)]), # two iterables
([range(0), range(2), range(3)], []), # first iterable with zero length
@@ -314,10 +420,10 @@
set('abcdefg'), range(11), tuple(range(13))]
for i in range(100):
args = [random.choice(argtypes) for j in range(random.randrange(5))]
- n = reduce(operator.mul, map(len, args), 1) if args else 0
- self.assertEqual(len(list(product(*args))), n)
+ expected_len = prod(map(len, args))
+ self.assertEqual(len(list(product(*args))), expected_len)
args = map(iter, args)
- self.assertEqual(len(list(product(*args))), n)
+ self.assertEqual(len(list(product(*args))), expected_len)
# Test implementation detail: tuple re-use
self.assertEqual(len(set(map(id, product('abc', 'def')))), 1)