Debian Codegraph @

Lib/test/test_itertools.py

raw
1 import doctest
2 import unittest
3 import itertools
4 from test import support
5 from test.support import threading_helper, script_helper
6 from itertools import *
7 import weakref
8 from decimal import Decimal
9 from fractions import Fraction
10 import operator
11 import random
12 import copy
13 import pickle
14 from functools import reduce
15 import sys
16 import struct
17 import threading
18 import gc
19
20 maxsize = support.MAX_Py_ssize_t
21 minsize = -maxsize-1
22
23 def lzip(*args):
24 return list(zip(*args))
25
26 def onearg(x):
27 'Test function of one argument'
28 return 2*x
29
30 def errfunc(*args):
31 'Test function that raises an error'
32 raise ValueError
33
34 def gen3():
35 'Non-restartable source sequence'
36 for i in (0, 1, 2):
37 yield i
38
39 def isEven(x):
40 'Test predicate'
41 return x%2==0
42
43 def isOdd(x):
44 'Test predicate'
45 return x%2==1
46
47 def tupleize(*args):
48 return args
49
50 def irange(n):
51 for i in range(n):
52 yield i
53
54 class StopNow:
55 'Class emulating an empty iterable.'
56 def __iter__(self):
57 return self
58 def __next__(self):
59 raise StopIteration
60
61 def take(n, seq):
62 'Convenience function for partially consuming a long of infinite iterable'
63 return list(islice(seq, n))
64
65 def prod(iterable):
66 return reduce(operator.mul, iterable, 1)
67
68 def fact(n):
69 'Factorial'
70 return prod(range(1, n+1))
71
72 # root level methods for pickling ability
73 def testR(r):
74 return r[0]
75
76 def testR2(r):
77 return r[2]
78
79 def underten(x):
80 return x<10
81
82 picklecopiers = [lambda s, proto=proto: pickle.loads(pickle.dumps(s, proto))
83 for proto in range(pickle.HIGHEST_PROTOCOL + 1)]
84
85 class TestBasicOps(unittest.TestCase):
86
87 def pickletest(self, protocol, it, stop=4, take=1, compare=None):
88 """Test that an iterator is the same after pickling, also when part-consumed"""
89 def expand(it, i=0):
90 # Recursively expand iterables, within sensible bounds
91 if i > 10:
92 raise RuntimeError("infinite recursion encountered")
93 if isinstance(it, str):
94 return it
95 try:
96 l = list(islice(it, stop))
97 except TypeError:
98 return it # can't expand it
99 return [expand(e, i+1) for e in l]
100
101 # Test the initial copy against the original
102 dump = pickle.dumps(it, protocol)
103 i2 = pickle.loads(dump)
104 self.assertEqual(type(it), type(i2))
105 a, b = expand(it), expand(i2)
106 self.assertEqual(a, b)
107 if compare:
108 c = expand(compare)
109 self.assertEqual(a, c)
110
111 # Take from the copy, and create another copy and compare them.
112 i3 = pickle.loads(dump)
113 took = 0
114 try:
115 for i in range(take):
116 next(i3)
117 took += 1
118 except StopIteration:
119 pass #in case there is less data than 'take'
120 dump = pickle.dumps(i3, protocol)
121 i4 = pickle.loads(dump)
122 a, b = expand(i3), expand(i4)
123 self.assertEqual(a, b)
124 if compare:
125 c = expand(compare[took:])
126 self.assertEqual(a, c);
127
128 def test_accumulate(self):
129 self.assertEqual(list(accumulate(range(10))), # one positional arg
130 [0, 1, 3, 6, 10, 15, 21, 28, 36, 45])
131 self.assertEqual(list(accumulate(iterable=range(10))), # kw arg
132 [0, 1, 3, 6, 10, 15, 21, 28, 36, 45])
133 for typ in int, complex, Decimal, Fraction: # multiple types
134 self.assertEqual(
135 list(accumulate(map(typ, range(10)))),
136 list(map(typ, [0, 1, 3, 6, 10, 15, 21, 28, 36, 45])))
137 self.assertEqual(list(accumulate('abc')), ['a', 'ab', 'abc']) # works with non-numeric
138 self.assertEqual(list(accumulate([])), []) # empty iterable
139 self.assertEqual(list(accumulate([7])), [7]) # iterable of length one
140 self.assertRaises(TypeError, accumulate, range(10), 5, 6) # too many args
141 self.assertRaises(TypeError, accumulate) # too few args
142 self.assertRaises(TypeError, accumulate, x=range(10)) # unexpected kwd arg
143 self.assertRaises(TypeError, list, accumulate([1, []])) # args that don't add
144
145 s = [2, 8, 9, 5, 7, 0, 3, 4, 1, 6]
146 self.assertEqual(list(accumulate(s, min)),
147 [2, 2, 2, 2, 2, 0, 0, 0, 0, 0])
148 self.assertEqual(list(accumulate(s, max)),
149 [2, 8, 9, 9, 9, 9, 9, 9, 9, 9])
150 self.assertEqual(list(accumulate(s, operator.mul)),
151 [2, 16, 144, 720, 5040, 0, 0, 0, 0, 0])
152 with self.assertRaises(TypeError):
153 list(accumulate(s, chr)) # unary-operation
154 self.assertEqual(list(accumulate([10, 5, 1], initial=None)), [10, 15, 16])
155 self.assertEqual(list(accumulate([10, 5, 1], initial=100)), [100, 110, 115, 116])
156 self.assertEqual(list(accumulate([], initial=100)), [100])
157 with self.assertRaises(TypeError):
158 list(accumulate([10, 20], 100))
159
160 def test_batched(self):
161 self.assertEqual(list(batched('ABCDEFG', 3)),
162 [('A', 'B', 'C'), ('D', 'E', 'F'), ('G',)])
163 self.assertEqual(list(batched('ABCDEFG', 2)),
164 [('A', 'B'), ('C', 'D'), ('E', 'F'), ('G',)])
165 self.assertEqual(list(batched('ABCDEFG', 1)),
166 [('A',), ('B',), ('C',), ('D',), ('E',), ('F',), ('G',)])
167 self.assertEqual(list(batched('ABCDEF', 2, strict=True)),
168 [('A', 'B'), ('C', 'D'), ('E', 'F')])
169
170 with self.assertRaises(ValueError): # Incomplete batch when strict
171 list(batched('ABCDEFG', 3, strict=True))
172 with self.assertRaises(TypeError): # Too few arguments
173 list(batched('ABCDEFG'))
174 with self.assertRaises(TypeError):
175 list(batched('ABCDEFG', 3, None)) # Too many arguments
176 with self.assertRaises(TypeError):
177 list(batched(None, 3)) # Non-iterable input
178 with self.assertRaises(TypeError):
179 list(batched('ABCDEFG', 'hello')) # n is a string
180 with self.assertRaises(ValueError):
181 list(batched('ABCDEFG', 0)) # n is zero
182 with self.assertRaises(ValueError):
183 list(batched('ABCDEFG', -1)) # n is negative
184
185 data = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
186 for n in range(1, 6):
187 for i in range(len(data)):
188 s = data[:i]
189 batches = list(batched(s, n))
190 with self.subTest(s=s, n=n, batches=batches):
191 # Order is preserved and no data is lost
192 self.assertEqual(''.join(chain(*batches)), s)
193 # Each batch is an exact tuple
194 self.assertTrue(all(type(batch) is tuple for batch in batches))
195 # All but the last batch is of size n
196 if batches:
197 last_batch = batches.pop()
198 self.assertTrue(all(len(batch) == n for batch in batches))
199 self.assertTrue(len(last_batch) <= n)
200 batches.append(last_batch)
201
202 def test_chain(self):
203
204 def chain2(*iterables):
205 'Pure python version in the docs'
206 for it in iterables:
207 for element in it:
208 yield element
209
210 for c in (chain, chain2):
211 self.assertEqual(list(c('abc', 'def')), list('abcdef'))
212 self.assertEqual(list(c('abc')), list('abc'))
213 self.assertEqual(list(c('')), [])
214 self.assertEqual(take(4, c('abc', 'def')), list('abcd'))
215 self.assertRaises(TypeError, list,c(2, 3))
216
217 def test_chain_from_iterable(self):
218 self.assertEqual(list(chain.from_iterable(['abc', 'def'])), list('abcdef'))
219 self.assertEqual(list(chain.from_iterable(['abc'])), list('abc'))
220 self.assertEqual(list(chain.from_iterable([''])), [])
221 self.assertEqual(take(4, chain.from_iterable(['abc', 'def'])), list('abcd'))
222 self.assertRaises(TypeError, list, chain.from_iterable([2, 3]))
223 self.assertEqual(list(islice(chain.from_iterable(repeat(range(5))), 2)), [0, 1])
224
225 def test_combinations(self):
226 self.assertRaises(TypeError, combinations, 'abc') # missing r argument
227 self.assertRaises(TypeError, combinations, 'abc', 2, 1) # too many arguments
228 self.assertRaises(TypeError, combinations, None) # pool is not iterable
229 self.assertRaises(ValueError, combinations, 'abc', -2) # r is negative
230
231 def combinations1(iterable, r):
232 'Pure python version shown in the docs'
233 pool = tuple(iterable)
234 n = len(pool)
235 if r > n:
236 return
237 indices = list(range(r))
238 yield tuple(pool[i] for i in indices)
239 while 1:
240 for i in reversed(range(r)):
241 if indices[i] != i + n - r:
242 break
243 else:
244 return
245 indices[i] += 1
246 for j in range(i+1, r):
247 indices[j] = indices[j-1] + 1
248 yield tuple(pool[i] for i in indices)
249
250 def combinations2(iterable, r):
251 'Pure python version shown in the docs'
252 pool = tuple(iterable)
253 n = len(pool)
254 for indices in permutations(range(n), r):
255 if sorted(indices) == list(indices):
256 yield tuple(pool[i] for i in indices)
257
258 def combinations3(iterable, r):
259 'Pure python version from cwr()'
260 pool = tuple(iterable)
261 n = len(pool)
262 for indices in combinations_with_replacement(range(n), r):
263 if len(set(indices)) == r:
264 yield tuple(pool[i] for i in indices)
265
266 for n in range(7):
267 values = [5*x-12 for x in range(n)]
268 for r in range(n+2):
269 result = list(combinations(values, r))
270 self.assertEqual(len(result), 0 if r>n else fact(n) / fact(r) / fact(n-r)) # right number of combs
271 self.assertEqual(len(result), len(set(result))) # no repeats
272 self.assertEqual(result, sorted(result)) # lexicographic order
273 for c in result:
274 self.assertEqual(len(c), r) # r-length combinations
275 self.assertEqual(len(set(c)), r) # no duplicate elements
276 self.assertEqual(list(c), sorted(c)) # keep original ordering
277 self.assertTrue(all(e in values for e in c)) # elements taken from input iterable
278 self.assertEqual(list(c),
279 [e for e in values if e in c]) # comb is a subsequence of the input iterable
280 self.assertEqual(result, list(combinations1(values, r))) # matches first pure python version
281 self.assertEqual(result, list(combinations2(values, r))) # matches second pure python version
282 self.assertEqual(result, list(combinations3(values, r))) # matches second pure python version
283
284 @support.bigaddrspacetest
285 def test_combinations_overflow(self):
286 with self.assertRaises((OverflowError, MemoryError)):
287 combinations("AA", 2**29)
288
289 # Test implementation detail: tuple re-use
290 @support.impl_detail("tuple reuse is specific to CPython")
291 def test_combinations_tuple_reuse(self):
292 self.assertEqual(len(set(map(id, combinations('abcde', 3)))), 1)
293 self.assertNotEqual(len(set(map(id, list(combinations('abcde', 3))))), 1)
294
295 def test_combinations_with_replacement(self):
296 cwr = combinations_with_replacement
297 self.assertRaises(TypeError, cwr, 'abc') # missing r argument
298 self.assertRaises(TypeError, cwr, 'abc', 2, 1) # too many arguments
299 self.assertRaises(TypeError, cwr, None) # pool is not iterable
300 self.assertRaises(ValueError, cwr, 'abc', -2) # r is negative
301
302 def cwr1(iterable, r):
303 'Pure python version shown in the docs'
304 # number items returned: (n+r-1)! / r! / (n-1)! when n>0
305 pool = tuple(iterable)
306 n = len(pool)
307 if not n and r:
308 return
309 indices = [0] * r
310 yield tuple(pool[i] for i in indices)
311 while 1:
312 for i in reversed(range(r)):
313 if indices[i] != n - 1:
314 break
315 else:
316 return
317 indices[i:] = [indices[i] + 1] * (r - i)
318 yield tuple(pool[i] for i in indices)
319
320 def cwr2(iterable, r):
321 'Pure python version shown in the docs'
322 pool = tuple(iterable)
323 n = len(pool)
324 for indices in product(range(n), repeat=r):
325 if sorted(indices) == list(indices):
326 yield tuple(pool[i] for i in indices)
327
328 def numcombs(n, r):
329 if not n:
330 return 0 if r else 1
331 return fact(n+r-1) / fact(r)/ fact(n-1)
332
333 for n in range(7):
334 values = [5*x-12 for x in range(n)]
335 for r in range(n+2):
336 result = list(cwr(values, r))
337
338 self.assertEqual(len(result), numcombs(n, r)) # right number of combs
339 self.assertEqual(len(result), len(set(result))) # no repeats
340 self.assertEqual(result, sorted(result)) # lexicographic order
341
342 regular_combs = list(combinations(values, r)) # compare to combs without replacement
343 if n == 0 or r <= 1:
344 self.assertEqual(result, regular_combs) # cases that should be identical
345 else:
346 self.assertTrue(set(result) >= set(regular_combs)) # rest should be supersets of regular combs
347
348 for c in result:
349 self.assertEqual(len(c), r) # r-length combinations
350 noruns = [k for k,v in groupby(c)] # combo without consecutive repeats
351 self.assertEqual(len(noruns), len(set(noruns))) # no repeats other than consecutive
352 self.assertEqual(list(c), sorted(c)) # keep original ordering
353 self.assertTrue(all(e in values for e in c)) # elements taken from input iterable
354 self.assertEqual(noruns,
355 [e for e in values if e in c]) # comb is a subsequence of the input iterable
356 self.assertEqual(result, list(cwr1(values, r))) # matches first pure python version
357 self.assertEqual(result, list(cwr2(values, r))) # matches second pure python version
358
359 @support.bigaddrspacetest
360 def test_combinations_with_replacement_overflow(self):
361 with self.assertRaises((OverflowError, MemoryError)):
362 combinations_with_replacement("AA", 2**30)
363
364 # Test implementation detail: tuple re-use
365 @support.impl_detail("tuple reuse is specific to CPython")
366 def test_combinations_with_replacement_tuple_reuse(self):
367 cwr = combinations_with_replacement
368 self.assertEqual(len(set(map(id, cwr('abcde', 3)))), 1)
369 self.assertNotEqual(len(set(map(id, list(cwr('abcde', 3))))), 1)
370
371 def test_permutations(self):
372 self.assertRaises(TypeError, permutations) # too few arguments
373 self.assertRaises(TypeError, permutations, 'abc', 2, 1) # too many arguments
374 self.assertRaises(TypeError, permutations, None) # pool is not iterable
375 self.assertRaises(ValueError, permutations, 'abc', -2) # r is negative
376 self.assertEqual(list(permutations('abc', 32)), []) # r > n
377 self.assertRaises(TypeError, permutations, 'abc', 's') # r is not an int or None
378 self.assertEqual(list(permutations(range(3), 2)),
379 [(0,1), (0,2), (1,0), (1,2), (2,0), (2,1)])
380
381 def permutations1(iterable, r=None):
382 'Pure python version shown in the docs'
383 pool = tuple(iterable)
384 n = len(pool)
385 r = n if r is None else r
386 if r > n:
387 return
388 indices = list(range(n))
389 cycles = list(range(n-r+1, n+1))[::-1]
390 yield tuple(pool[i] for i in indices[:r])
391 while n:
392 for i in reversed(range(r)):
393 cycles[i] -= 1
394 if cycles[i] == 0:
395 indices[i:] = indices[i+1:] + indices[i:i+1]
396 cycles[i] = n - i
397 else:
398 j = cycles[i]
399 indices[i], indices[-j] = indices[-j], indices[i]
400 yield tuple(pool[i] for i in indices[:r])
401 break
402 else:
403 return
404
405 def permutations2(iterable, r=None):
406 'Pure python version shown in the docs'
407 pool = tuple(iterable)
408 n = len(pool)
409 r = n if r is None else r
410 for indices in product(range(n), repeat=r):
411 if len(set(indices)) == r:
412 yield tuple(pool[i] for i in indices)
413
414 for n in range(7):
415 values = [5*x-12 for x in range(n)]
416 for r in range(n+2):
417 result = list(permutations(values, r))
418 self.assertEqual(len(result), 0 if r>n else fact(n) / fact(n-r)) # right number of perms
419 self.assertEqual(len(result), len(set(result))) # no repeats
420 self.assertEqual(result, sorted(result)) # lexicographic order
421 for p in result:
422 self.assertEqual(len(p), r) # r-length permutations
423 self.assertEqual(len(set(p)), r) # no duplicate elements
424 self.assertTrue(all(e in values for e in p)) # elements taken from input iterable
425 self.assertEqual(result, list(permutations1(values, r))) # matches first pure python version
426 self.assertEqual(result, list(permutations2(values, r))) # matches second pure python version
427 if r == n:
428 self.assertEqual(result, list(permutations(values, None))) # test r as None
429 self.assertEqual(result, list(permutations(values))) # test default r
430
431 @support.bigaddrspacetest
432 def test_permutations_overflow(self):
433 with self.assertRaises((OverflowError, MemoryError)):
434 permutations("A", 2**30)
435
436 @support.impl_detail("tuple reuse is specific to CPython")
437 def test_permutations_tuple_reuse(self):
438 self.assertEqual(len(set(map(id, permutations('abcde', 3)))), 1)
439 self.assertNotEqual(len(set(map(id, list(permutations('abcde', 3))))), 1)
440
441 def test_combinatorics(self):
442 # Test relationships between product(), permutations(),
443 # combinations() and combinations_with_replacement().
444
445 for n in range(6):
446 s = 'ABCDEFG'[:n]
447 for r in range(8):
448 prod = list(product(s, repeat=r))
449 cwr = list(combinations_with_replacement(s, r))
450 perm = list(permutations(s, r))
451 comb = list(combinations(s, r))
452
453 # Check size
454 self.assertEqual(len(prod), n**r)
455 self.assertEqual(len(cwr), (fact(n+r-1) / fact(r)/ fact(n-1)) if n else (not r))
456 self.assertEqual(len(perm), 0 if r>n else fact(n) / fact(n-r))
457 self.assertEqual(len(comb), 0 if r>n else fact(n) / fact(r) / fact(n-r))
458
459 # Check lexicographic order without repeated tuples
460 self.assertEqual(prod, sorted(set(prod)))
461 self.assertEqual(cwr, sorted(set(cwr)))
462 self.assertEqual(perm, sorted(set(perm)))
463 self.assertEqual(comb, sorted(set(comb)))
464
465 # Check interrelationships
466 self.assertEqual(cwr, [t for t in prod if sorted(t)==list(t)]) # cwr: prods which are sorted
467 self.assertEqual(perm, [t for t in prod if len(set(t))==r]) # perm: prods with no dups
468 self.assertEqual(comb, [t for t in perm if sorted(t)==list(t)]) # comb: perms that are sorted
469 self.assertEqual(comb, [t for t in cwr if len(set(t))==r]) # comb: cwrs without dups
470 self.assertEqual(comb, list(filter(set(cwr).__contains__, perm))) # comb: perm that is a cwr
471 self.assertEqual(comb, list(filter(set(perm).__contains__, cwr))) # comb: cwr that is a perm
472 self.assertEqual(comb, sorted(set(cwr) & set(perm))) # comb: both a cwr and a perm
473
474 def test_compress(self):
475 self.assertEqual(list(compress(data='ABCDEF', selectors=[1,0,1,0,1,1])), list('ACEF'))
476 self.assertEqual(list(compress('ABCDEF', [1,0,1,0,1,1])), list('ACEF'))
477 self.assertEqual(list(compress('ABCDEF', [0,0,0,0,0,0])), list(''))
478 self.assertEqual(list(compress('ABCDEF', [1,1,1,1,1,1])), list('ABCDEF'))
479 self.assertEqual(list(compress('ABCDEF', [1,0,1])), list('AC'))
480 self.assertEqual(list(compress('ABC', [0,1,1,1,1,1])), list('BC'))
481 n = 10000
482 data = chain.from_iterable(repeat(range(6), n))
483 selectors = chain.from_iterable(repeat((0, 1)))
484 self.assertEqual(list(compress(data, selectors)), [1,3,5] * n)
485 self.assertRaises(TypeError, compress, None, range(6)) # 1st arg not iterable
486 self.assertRaises(TypeError, compress, range(6), None) # 2nd arg not iterable
487 self.assertRaises(TypeError, compress, range(6)) # too few args
488 self.assertRaises(TypeError, compress, range(6), None) # too many args
489
490 def test_count(self):
491 self.assertEqual(lzip('abc',count()), [('a', 0), ('b', 1), ('c', 2)])
492 self.assertEqual(lzip('abc',count(3)), [('a', 3), ('b', 4), ('c', 5)])
493 self.assertEqual(take(2, lzip('abc',count(3))), [('a', 3), ('b', 4)])
494 self.assertEqual(take(2, zip('abc',count(-1))), [('a', -1), ('b', 0)])
495 self.assertEqual(take(2, zip('abc',count(-3))), [('a', -3), ('b', -2)])
496 self.assertRaises(TypeError, count, 2, 3, 4)
497 self.assertRaises(TypeError, count, 'a')
498 self.assertEqual(take(3, count(maxsize)),
499 [maxsize, maxsize + 1, maxsize + 2])
500 self.assertEqual(take(10, count(maxsize-5)),
501 list(range(maxsize-5, maxsize+5)))
502 self.assertEqual(take(10, count(-maxsize-5)),
503 list(range(-maxsize-5, -maxsize+5)))
504 self.assertEqual(take(3, count(3.25)), [3.25, 4.25, 5.25])
505 self.assertEqual(take(3, count(3.25-4j)), [3.25-4j, 4.25-4j, 5.25-4j])
506 self.assertEqual(take(3, count(Decimal('1.1'))),
507 [Decimal('1.1'), Decimal('2.1'), Decimal('3.1')])
508 self.assertEqual(take(3, count(Fraction(2, 3))),
509 [Fraction(2, 3), Fraction(5, 3), Fraction(8, 3)])
510 BIGINT = 1<<1000
511 self.assertEqual(take(3, count(BIGINT)), [BIGINT, BIGINT+1, BIGINT+2])
512 c = count(3)
513 self.assertEqual(repr(c), 'count(3)')
514 next(c)
515 self.assertEqual(repr(c), 'count(4)')
516 c = count(-9)
517 self.assertEqual(repr(c), 'count(-9)')
518 next(c)
519 self.assertEqual(next(c), -8)
520 self.assertEqual(repr(count(10.25)), 'count(10.25)')
521 self.assertEqual(repr(count(10.0)), 'count(10.0)')
522
523 self.assertEqual(repr(count(maxsize)), f'count({maxsize})')
524 c = count(maxsize - 1)
525 self.assertEqual(repr(c), f'count({maxsize - 1})')
526 next(c) # c is now at masize
527 self.assertEqual(repr(c), f'count({maxsize})')
528 next(c)
529 self.assertEqual(repr(c), f'count({maxsize + 1})')
530
531 self.assertEqual(type(next(count(10.0))), float)
532 for i in (-sys.maxsize-5, -sys.maxsize+5 ,-10, -1, 0, 10, sys.maxsize-5, sys.maxsize+5):
533 # Test repr
534 r1 = repr(count(i))
535 r2 = 'count(%r)'.__mod__(i)
536 self.assertEqual(r1, r2)
537
538 #check proper internal error handling for large "step' sizes
539 count(1, maxsize+5); sys.exc_info()
540
541 def test_count_with_step(self):
542 self.assertEqual(lzip('abc',count(2,3)), [('a', 2), ('b', 5), ('c', 8)])
543 self.assertEqual(lzip('abc',count(start=2,step=3)),
544 [('a', 2), ('b', 5), ('c', 8)])
545 self.assertEqual(lzip('abc',count(step=-1)),
546 [('a', 0), ('b', -1), ('c', -2)])
547 self.assertRaises(TypeError, count, 'a', 'b')
548 self.assertEqual(lzip('abc',count(2,0)), [('a', 2), ('b', 2), ('c', 2)])
549 self.assertEqual(lzip('abc',count(2,1)), [('a', 2), ('b', 3), ('c', 4)])
550 self.assertEqual(lzip('abc',count(2,3)), [('a', 2), ('b', 5), ('c', 8)])
551 self.assertEqual(take(20, count(maxsize-15, 3)), take(20, range(maxsize-15, maxsize+100, 3)))
552 self.assertEqual(take(20, count(-maxsize-15, 3)), take(20, range(-maxsize-15,-maxsize+100, 3)))
553 self.assertEqual(take(3, count(10, maxsize+5)),
554 list(range(10, 10+3*(maxsize+5), maxsize+5)))
555 self.assertEqual(take(3, count(maxsize, 2)),
556 [maxsize, maxsize + 2, maxsize + 4])
557 self.assertEqual(take(3, count(maxsize, maxsize)),
558 [maxsize, 2 * maxsize, 3 * maxsize])
559 self.assertEqual(take(3, count(-maxsize, maxsize)),
560 [-maxsize, 0, maxsize])
561 self.assertEqual(take(3, count(2, 1.25)), [2, 3.25, 4.5])
562 self.assertEqual(take(3, count(2, 3.25-4j)), [2, 5.25-4j, 8.5-8j])
563 self.assertEqual(take(3, count(Decimal('1.1'), Decimal('.1'))),
564 [Decimal('1.1'), Decimal('1.2'), Decimal('1.3')])
565 self.assertEqual(take(3, count(Fraction(2,3), Fraction(1,7))),
566 [Fraction(2,3), Fraction(17,21), Fraction(20,21)])
567 BIGINT = 1<<1000
568 self.assertEqual(take(3, count(step=BIGINT)), [0, BIGINT, 2*BIGINT])
569 self.assertEqual(repr(take(3, count(10, 2.5))), repr([10, 12.5, 15.0]))
570 c = count(3, 5)
571 self.assertEqual(repr(c), 'count(3, 5)')
572 next(c)
573 self.assertEqual(repr(c), 'count(8, 5)')
574 c = count(-9, 0)
575 self.assertEqual(repr(c), 'count(-9, 0)')
576 next(c)
577 self.assertEqual(repr(c), 'count(-9, 0)')
578 c = count(-9, -3)
579 self.assertEqual(repr(c), 'count(-9, -3)')
580 next(c)
581 self.assertEqual(repr(c), 'count(-12, -3)')
582 self.assertEqual(repr(c), 'count(-12, -3)')
583 self.assertEqual(repr(count(10.5, 1.25)), 'count(10.5, 1.25)')
584 self.assertEqual(repr(count(10.5, 1)), 'count(10.5)') # suppress step=1 when it's an int
585 self.assertEqual(repr(count(10.5, 1.00)), 'count(10.5, 1.0)') # do show float values lilke 1.0
586 self.assertEqual(repr(count(10, 1.00)), 'count(10, 1.0)')
587 c = count(10, 1.0)
588 self.assertEqual(type(next(c)), int)
589 self.assertEqual(type(next(c)), float)
590
591 c = count(maxsize -2, 2)
592 self.assertEqual(repr(c), f'count({maxsize - 2}, 2)')
593 next(c) # c is now at masize
594 self.assertEqual(repr(c), f'count({maxsize}, 2)')
595 next(c)
596 self.assertEqual(repr(c), f'count({maxsize + 2}, 2)')
597
598 c = count(maxsize + 1, -1)
599 self.assertEqual(repr(c), f'count({maxsize + 1}, -1)')
600 next(c) # c is now at masize
601 self.assertEqual(repr(c), f'count({maxsize}, -1)')
602 next(c)
603 self.assertEqual(repr(c), f'count({maxsize - 1}, -1)')
604
605 @threading_helper.requires_working_threading()
606 def test_count_threading(self, step=1):
607 # this test verifies multithreading consistency, which is
608 # mostly for testing builds without GIL, but nice to test anyway
609 count_to = 10_000
610 num_threads = 10
611 c = count(step=step)
612 def counting_thread():
613 for i in range(count_to):
614 next(c)
615 threads = []
616 for i in range(num_threads):
617 thread = threading.Thread(target=counting_thread)
618 thread.start()
619 threads.append(thread)
620 for thread in threads:
621 thread.join()
622 self.assertEqual(next(c), count_to * num_threads * step)
623
624 def test_count_with_step_threading(self):
625 self.test_count_threading(step=5)
626
627 def test_cycle(self):
628 self.assertEqual(take(10, cycle('abc')), list('abcabcabca'))
629 self.assertEqual(list(cycle('')), [])
630 self.assertRaises(TypeError, cycle)
631 self.assertRaises(TypeError, cycle, 5)
632 self.assertEqual(list(islice(cycle(gen3()),10)), [0,1,2,0,1,2,0,1,2,0])
633
634 def test_groupby(self):
635 # Check whether it accepts arguments correctly
636 self.assertEqual([], list(groupby([])))
637 self.assertEqual([], list(groupby([], key=id)))
638 self.assertRaises(TypeError, list, groupby('abc', []))
639 self.assertRaises(TypeError, groupby, None)
640 self.assertRaises(TypeError, groupby, 'abc', lambda x:x, 10)
641
642 # Check normal input
643 s = [(0, 10, 20), (0, 11,21), (0,12,21), (1,13,21), (1,14,22),
644 (2,15,22), (3,16,23), (3,17,23)]
645 dup = []
646 for k, g in groupby(s, lambda r:r[0]):
647 for elem in g:
648 self.assertEqual(k, elem[0])
649 dup.append(elem)
650 self.assertEqual(s, dup)
651
652 # Check nested case
653 dup = []
654 for k, g in groupby(s, testR):
655 for ik, ig in groupby(g, testR2):
656 for elem in ig:
657 self.assertEqual(k, elem[0])
658 self.assertEqual(ik, elem[2])
659 dup.append(elem)
660 self.assertEqual(s, dup)
661
662 # Check case where inner iterator is not used
663 keys = [k for k, g in groupby(s, testR)]
664 expectedkeys = set([r[0] for r in s])
665 self.assertEqual(set(keys), expectedkeys)
666 self.assertEqual(len(keys), len(expectedkeys))
667
668 # Check case where inner iterator is used after advancing the groupby
669 # iterator
670 s = list(zip('AABBBAAAA', range(9)))
671 it = groupby(s, testR)
672 _, g1 = next(it)
673 _, g2 = next(it)
674 _, g3 = next(it)
675 self.assertEqual(list(g1), [])
676 self.assertEqual(list(g2), [])
677 self.assertEqual(next(g3), ('A', 5))
678 list(it) # exhaust the groupby iterator
679 self.assertEqual(list(g3), [])
680
681 # Exercise pipes and filters style
682 s = 'abracadabra'
683 # sort s | uniq
684 r = [k for k, g in groupby(sorted(s))]
685 self.assertEqual(r, ['a', 'b', 'c', 'd', 'r'])
686 # sort s | uniq -d
687 r = [k for k, g in groupby(sorted(s)) if list(islice(g,1,2))]
688 self.assertEqual(r, ['a', 'b', 'r'])
689 # sort s | uniq -c
690 r = [(len(list(g)), k) for k, g in groupby(sorted(s))]
691 self.assertEqual(r, [(5, 'a'), (2, 'b'), (1, 'c'), (1, 'd'), (2, 'r')])
692 # sort s | uniq -c | sort -rn | head -3
693 r = sorted([(len(list(g)) , k) for k, g in groupby(sorted(s))], reverse=True)[:3]
694 self.assertEqual(r, [(5, 'a'), (2, 'r'), (2, 'b')])
695
696 # iter.__next__ failure
697 class ExpectedError(Exception):
698 pass
699 def delayed_raise(n=0):
700 for i in range(n):
701 yield 'yo'
702 raise ExpectedError
703 def gulp(iterable, keyp=None, func=list):
704 return [func(g) for k, g in groupby(iterable, keyp)]
705
706 # iter.__next__ failure on outer object
707 self.assertRaises(ExpectedError, gulp, delayed_raise(0))
708 # iter.__next__ failure on inner object
709 self.assertRaises(ExpectedError, gulp, delayed_raise(1))
710
711 # __eq__ failure
712 class DummyCmp:
713 def __eq__(self, dst):
714 raise ExpectedError
715 s = [DummyCmp(), DummyCmp(), None]
716
717 # __eq__ failure on outer object
718 self.assertRaises(ExpectedError, gulp, s, func=id)
719 # __eq__ failure on inner object
720 self.assertRaises(ExpectedError, gulp, s)
721
722 # keyfunc failure
723 def keyfunc(obj):
724 if keyfunc.skip > 0:
725 keyfunc.skip -= 1
726 return obj
727 else:
728 raise ExpectedError
729
730 # keyfunc failure on outer object
731 keyfunc.skip = 0
732 self.assertRaises(ExpectedError, gulp, [None], keyfunc)
733 keyfunc.skip = 1
734 self.assertRaises(ExpectedError, gulp, [None, None], keyfunc)
735
736 def test_groupby_reentrant_eq_does_not_crash(self):
737 # regression test for gh-143543
738 class Key:
739 def __init__(self, do_advance):
740 self.do_advance = do_advance
741
742 def __eq__(self, other):
743 if self.do_advance:
744 self.do_advance = False
745 next(g)
746 return NotImplemented
747 return False
748
749 def keys():
750 yield Key(True)
751 yield Key(False)
752
753 g = itertools.groupby([None, None], keys().send)
754 next(g)
755 next(g) # must pass with address sanitizer
756
757 def test_grouper_reentrant_eq_does_not_crash(self):
758 # regression test for gh-146613
759 grouper_iter = None
760
761 class Key:
762 __hash__ = None
763
764 def __init__(self, do_advance):
765 self.do_advance = do_advance
766
767 def __eq__(self, other):
768 nonlocal grouper_iter
769 if self.do_advance:
770 self.do_advance = False
771 if grouper_iter is not None:
772 try:
773 next(grouper_iter)
774 except StopIteration:
775 pass
776 return NotImplemented
777 return True
778
779 def keyfunc(element):
780 if element == 0:
781 return Key(do_advance=True)
782 return Key(do_advance=False)
783
784 g = itertools.groupby(range(4), keyfunc)
785 key, grouper_iter = next(g)
786 items = list(grouper_iter)
787 self.assertEqual(len(items), 1)
788
789 def test_filter(self):
790 self.assertEqual(list(filter(isEven, range(6))), [0,2,4])
791 self.assertEqual(list(filter(None, [0,1,0,2,0])), [1,2])
792 self.assertEqual(list(filter(bool, [0,1,0,2,0])), [1,2])
793 self.assertEqual(take(4, filter(isEven, count())), [0,2,4,6])
794 self.assertRaises(TypeError, filter)
795 self.assertRaises(TypeError, filter, lambda x:x)
796 self.assertRaises(TypeError, filter, lambda x:x, range(6), 7)
797 self.assertRaises(TypeError, filter, isEven, 3)
798 self.assertRaises(TypeError, next, filter(range(6), range(6)))
799
800 # check copy, deepcopy, pickle
801 ans = [0,2,4]
802
803 c = filter(isEven, range(6))
804 self.assertEqual(list(copy.copy(c)), ans)
805 c = filter(isEven, range(6))
806 self.assertEqual(list(copy.deepcopy(c)), ans)
807 for proto in range(pickle.HIGHEST_PROTOCOL + 1):
808 c = filter(isEven, range(6))
809 self.assertEqual(list(pickle.loads(pickle.dumps(c, proto))), ans)
810 next(c)
811 self.assertEqual(list(pickle.loads(pickle.dumps(c, proto))), ans[1:])
812 for proto in range(pickle.HIGHEST_PROTOCOL + 1):
813 c = filter(isEven, range(6))
814 self.pickletest(proto, c)
815
816 def test_filterfalse(self):
817 self.assertEqual(list(filterfalse(isEven, range(6))), [1,3,5])
818 self.assertEqual(list(filterfalse(None, [0,1,0,2,0])), [0,0,0])
819 self.assertEqual(list(filterfalse(bool, [0,1,0,2,0])), [0,0,0])
820 self.assertEqual(take(4, filterfalse(isEven, count())), [1,3,5,7])
821 self.assertRaises(TypeError, filterfalse)
822 self.assertRaises(TypeError, filterfalse, lambda x:x)
823 self.assertRaises(TypeError, filterfalse, lambda x:x, range(6), 7)
824 self.assertRaises(TypeError, filterfalse, isEven, 3)
825 self.assertRaises(TypeError, next, filterfalse(range(6), range(6)))
826
827 def test_zip(self):
828 # XXX This is rather silly now that builtin zip() calls zip()...
829 ans = [(x,y) for x, y in zip('abc',count())]
830 self.assertEqual(ans, [('a', 0), ('b', 1), ('c', 2)])
831 self.assertEqual(list(zip('abc', range(6))), lzip('abc', range(6)))
832 self.assertEqual(list(zip('abcdef', range(3))), lzip('abcdef', range(3)))
833 self.assertEqual(take(3,zip('abcdef', count())), lzip('abcdef', range(3)))
834 self.assertEqual(list(zip('abcdef')), lzip('abcdef'))
835 self.assertEqual(list(zip()), lzip())
836 self.assertRaises(TypeError, zip, 3)
837 self.assertRaises(TypeError, zip, range(3), 3)
838 self.assertEqual([tuple(list(pair)) for pair in zip('abc', 'def')],
839 lzip('abc', 'def'))
840 self.assertEqual([pair for pair in zip('abc', 'def')],
841 lzip('abc', 'def'))
842
843 @support.impl_detail("tuple reuse is specific to CPython")
844 def test_zip_tuple_reuse(self):
845 ids = list(map(id, zip('abc', 'def')))
846 self.assertEqual(min(ids), max(ids))
847 ids = list(map(id, list(zip('abc', 'def'))))
848 self.assertEqual(len(dict.fromkeys(ids)), len(ids))
849
850 def test_ziplongest(self):
851 for args in [
852 ['abc', range(6)],
853 [range(6), 'abc'],
854 [range(1000), range(2000,2100), range(3000,3050)],
855 [range(1000), range(0), range(3000,3050), range(1200), range(1500)],
856 [range(1000), range(0), range(3000,3050), range(1200), range(1500), range(0)],
857 ]:
858 target = [tuple([arg[i] if i < len(arg) else None for arg in args])
859 for i in range(max(map(len, args)))]
860 self.assertEqual(list(zip_longest(*args)), target)
861 self.assertEqual(list(zip_longest(*args, **{})), target)
862 target = [tuple((e is None and 'X' or e) for e in t) for t in target] # Replace None fills with 'X'
863 self.assertEqual(list(zip_longest(*args, **dict(fillvalue='X'))), target)
864
865 self.assertEqual(take(3,zip_longest('abcdef', count())), list(zip('abcdef', range(3)))) # take 3 from infinite input
866
867 self.assertEqual(list(zip_longest()), list(zip()))
868 self.assertEqual(list(zip_longest([])), list(zip([])))
869 self.assertEqual(list(zip_longest('abcdef')), list(zip('abcdef')))
870
871 self.assertEqual(list(zip_longest('abc', 'defg', **{})),
872 list(zip(list('abc')+[None], 'defg'))) # empty keyword dict
873 self.assertRaises(TypeError, zip_longest, 3)
874 self.assertRaises(TypeError, zip_longest, range(3), 3)
875
876 for stmt in [
877 "zip_longest('abc', fv=1)",
878 "zip_longest('abc', fillvalue=1, bogus_keyword=None)",
879 ]:
880 try:
881 eval(stmt, globals(), locals())
882 except TypeError:
883 pass
884 else:
885 self.fail('Did not raise Type in: ' + stmt)
886
887 self.assertEqual([tuple(list(pair)) for pair in zip_longest('abc', 'def')],
888 list(zip('abc', 'def')))
889 self.assertEqual([pair for pair in zip_longest('abc', 'def')],
890 list(zip('abc', 'def')))
891
892 @support.impl_detail("tuple reuse is specific to CPython")
893 def test_zip_longest_tuple_reuse(self):
894 ids = list(map(id, zip_longest('abc', 'def')))
895 self.assertEqual(min(ids), max(ids))
896 ids = list(map(id, list(zip_longest('abc', 'def'))))
897 self.assertEqual(len(dict.fromkeys(ids)), len(ids))
898
899 def test_zip_longest_bad_iterable(self):
900 exception = TypeError()
901
902 class BadIterable:
903 def __iter__(self):
904 raise exception
905
906 with self.assertRaises(TypeError) as cm:
907 zip_longest(BadIterable())
908
909 self.assertIs(cm.exception, exception)
910
911 def test_bug_7244(self):
912
913 class Repeater:
914 # this class is similar to itertools.repeat
915 def __init__(self, o, t, e):
916 self.o = o
917 self.t = int(t)
918 self.e = e
919 def __iter__(self): # its iterator is itself
920 return self
921 def __next__(self):
922 if self.t > 0:
923 self.t -= 1
924 return self.o
925 else:
926 raise self.e
927
928 # Formerly this code in would fail in debug mode
929 # with Undetected Error and Stop Iteration
930 r1 = Repeater(1, 3, StopIteration)
931 r2 = Repeater(2, 4, StopIteration)
932 def run(r1, r2):
933 result = []
934 for i, j in zip_longest(r1, r2, fillvalue=0):
935 with support.captured_output('stdout'):
936 print((i, j))
937 result.append((i, j))
938 return result
939 self.assertEqual(run(r1, r2), [(1,2), (1,2), (1,2), (0,2)])
940
941 # Formerly, the RuntimeError would be lost
942 # and StopIteration would stop as expected
943 r1 = Repeater(1, 3, RuntimeError)
944 r2 = Repeater(2, 4, StopIteration)
945 it = zip_longest(r1, r2, fillvalue=0)
946 self.assertEqual(next(it), (1, 2))
947 self.assertEqual(next(it), (1, 2))
948 self.assertEqual(next(it), (1, 2))
949 self.assertRaises(RuntimeError, next, it)
950
951 def test_pairwise(self):
952 self.assertEqual(list(pairwise('')), [])
953 self.assertEqual(list(pairwise('a')), [])
954 self.assertEqual(list(pairwise('ab')),
955 [('a', 'b')]),
956 self.assertEqual(list(pairwise('abcde')),
957 [('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'e')])
958 self.assertEqual(list(pairwise(range(10_000))),
959 list(zip(range(10_000), range(1, 10_000))))
960
961 with self.assertRaises(TypeError):
962 pairwise() # too few arguments
963 with self.assertRaises(TypeError):
964 pairwise('abc', 10) # too many arguments
965 with self.assertRaises(TypeError):
966 pairwise(iterable='abc') # keyword arguments
967 with self.assertRaises(TypeError):
968 pairwise(None) # non-iterable argument
969
970 def test_pairwise_reenter(self):
971 def check(reenter_at, expected):
972 class I:
973 count = 0
974 def __iter__(self):
975 return self
976 def __next__(self):
977 self.count +=1
978 if self.count in reenter_at:
979 return next(it)
980 return [self.count] # new object
981
982 it = pairwise(I())
983 for item in expected:
984 self.assertEqual(next(it), item)
985
986 check({1}, [
987 (([2], [3]), [4]),
988 ([4], [5]),
989 ])
990 check({2}, [
991 ([1], ([1], [3])),
992 (([1], [3]), [4]),
993 ([4], [5]),
994 ])
995 check({3}, [
996 ([1], [2]),
997 ([2], ([2], [4])),
998 (([2], [4]), [5]),
999 ([5], [6]),
1000 ])
1001 check({1, 2}, [
1002 ((([3], [4]), [5]), [6]),
1003 ([6], [7]),
1004 ])
1005 check({1, 3}, [
1006 (([2], ([2], [4])), [5]),
1007 ([5], [6]),
1008 ])
1009 check({1, 4}, [
1010 (([2], [3]), (([2], [3]), [5])),
1011 ((([2], [3]), [5]), [6]),
1012 ([6], [7]),
1013 ])
1014 check({2, 3}, [
1015 ([1], ([1], ([1], [4]))),
1016 (([1], ([1], [4])), [5]),
1017 ([5], [6]),
1018 ])
1019
1020 def test_pairwise_reenter2(self):
1021 def check(maxcount, expected):
1022 class I:
1023 count = 0
1024 def __iter__(self):
1025 return self
1026 def __next__(self):
1027 if self.count >= maxcount:
1028 raise StopIteration
1029 self.count +=1
1030 if self.count == 1:
1031 return next(it, None)
1032 return [self.count] # new object
1033
1034 it = pairwise(I())
1035 self.assertEqual(list(it), expected)
1036
1037 check(1, [])
1038 check(2, [])
1039 check(3, [])
1040 check(4, [(([2], [3]), [4])])
1041
1042 def test_product(self):
1043 for args, result in [
1044 ([], [()]), # zero iterables
1045 (['ab'], [('a',), ('b',)]), # one iterable
1046 ([range(2), range(3)], [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2)]), # two iterables
1047 ([range(0), range(2), range(3)], []), # first iterable with zero length
1048 ([range(2), range(0), range(3)], []), # middle iterable with zero length
1049 ([range(2), range(3), range(0)], []), # last iterable with zero length
1050 ]:
1051 self.assertEqual(list(product(*args)), result)
1052 for r in range(4):
1053 self.assertEqual(list(product(*(args*r))),
1054 list(product(*args, **dict(repeat=r))))
1055 self.assertEqual(len(list(product(*[range(7)]*6))), 7**6)
1056 self.assertRaises(TypeError, product, range(6), None)
1057
1058 def product1(*args, **kwds):
1059 pools = list(map(tuple, args)) * kwds.get('repeat', 1)
1060 n = len(pools)
1061 if n == 0:
1062 yield ()
1063 return
1064 if any(len(pool) == 0 for pool in pools):
1065 return
1066 indices = [0] * n
1067 yield tuple(pool[i] for pool, i in zip(pools, indices))
1068 while 1:
1069 for i in reversed(range(n)): # right to left
1070 if indices[i] == len(pools[i]) - 1:
1071 continue
1072 indices[i] += 1
1073 for j in range(i+1, n):
1074 indices[j] = 0
1075 yield tuple(pool[i] for pool, i in zip(pools, indices))
1076 break
1077 else:
1078 return
1079
1080 def product2(*iterables, repeat=1):
1081 'Pure python version used in docs'
1082 if repeat < 0:
1083 raise ValueError('repeat argument cannot be negative')
1084 pools = [tuple(pool) for pool in iterables] * repeat
1085
1086 result = [[]]
1087 for pool in pools:
1088 result = [x+[y] for x in result for y in pool]
1089
1090 for prod in result:
1091 yield tuple(prod)
1092
1093 argtypes = ['', 'abc', '', range(0), range(4), dict(a=1, b=2, c=3),
1094 set('abcdefg'), range(11), tuple(range(13))]
1095 for i in range(100):
1096 args = [random.choice(argtypes) for j in range(random.randrange(5))]
1097 expected_len = prod(map(len, args))
1098 self.assertEqual(len(list(product(*args))), expected_len)
1099 self.assertEqual(list(product(*args)), list(product1(*args)))
1100 self.assertEqual(list(product(*args)), list(product2(*args)))
1101 args = map(iter, args)
1102 self.assertEqual(len(list(product(*args))), expected_len)
1103
1104 @support.bigaddrspacetest
1105 def test_product_overflow(self):
1106 with self.assertRaises((OverflowError, MemoryError)):
1107 product(*(['ab']*2**5), repeat=2**25)
1108
1109 @support.impl_detail("tuple reuse is specific to CPython")
1110 def test_product_tuple_reuse(self):
1111 self.assertEqual(len(set(map(id, product('abc', 'def')))), 1)
1112 self.assertNotEqual(len(set(map(id, list(product('abc', 'def'))))), 1)
1113
1114 def test_repeat(self):
1115 self.assertEqual(list(repeat(object='a', times=3)), ['a', 'a', 'a'])
1116 self.assertEqual(lzip(range(3),repeat('a')),
1117 [(0, 'a'), (1, 'a'), (2, 'a')])
1118 self.assertEqual(list(repeat('a', 3)), ['a', 'a', 'a'])
1119 self.assertEqual(take(3, repeat('a')), ['a', 'a', 'a'])
1120 self.assertEqual(list(repeat('a', 0)), [])
1121 self.assertEqual(list(repeat('a', -3)), [])
1122 self.assertRaises(TypeError, repeat)
1123 self.assertRaises(TypeError, repeat, None, 3, 4)
1124 self.assertRaises(TypeError, repeat, None, 'a')
1125 r = repeat(1+0j)
1126 self.assertEqual(repr(r), 'repeat((1+0j))')
1127 r = repeat(1+0j, 5)
1128 self.assertEqual(repr(r), 'repeat((1+0j), 5)')
1129 list(r)
1130 self.assertEqual(repr(r), 'repeat((1+0j), 0)')
1131
1132 def test_repeat_with_negative_times(self):
1133 self.assertEqual(repr(repeat('a', -1)), "repeat('a', 0)")
1134 self.assertEqual(repr(repeat('a', -2)), "repeat('a', 0)")
1135 self.assertEqual(repr(repeat('a', times=-1)), "repeat('a', 0)")
1136 self.assertEqual(repr(repeat('a', times=-2)), "repeat('a', 0)")
1137
1138 def test_map(self):
1139 self.assertEqual(list(map(operator.pow, range(3), range(1,7))),
1140 [0**1, 1**2, 2**3])
1141 self.assertEqual(list(map(tupleize, 'abc', range(5))),
1142 [('a',0),('b',1),('c',2)])
1143 self.assertEqual(list(map(tupleize, 'abc', count())),
1144 [('a',0),('b',1),('c',2)])
1145 self.assertEqual(take(2,map(tupleize, 'abc', count())),
1146 [('a',0),('b',1)])
1147 self.assertEqual(list(map(operator.pow, [])), [])
1148 self.assertRaises(TypeError, map)
1149 self.assertRaises(TypeError, list, map(None, range(3), range(3)))
1150 self.assertRaises(TypeError, map, operator.neg)
1151 self.assertRaises(TypeError, next, map(10, range(5)))
1152 self.assertRaises(ValueError, next, map(errfunc, [4], [5]))
1153 self.assertRaises(TypeError, next, map(onearg, [4], [5]))
1154
1155 def test_starmap(self):
1156 self.assertEqual(list(starmap(operator.pow, zip(range(3), range(1,7)))),
1157 [0**1, 1**2, 2**3])
1158 self.assertEqual(take(3, starmap(operator.pow, zip(count(), count(1)))),
1159 [0**1, 1**2, 2**3])
1160 self.assertEqual(list(starmap(operator.pow, [])), [])
1161 self.assertEqual(list(starmap(operator.pow, [iter([4,5])])), [4**5])
1162 self.assertRaises(TypeError, list, starmap(operator.pow, [None]))
1163 self.assertRaises(TypeError, starmap)
1164 self.assertRaises(TypeError, starmap, operator.pow, [(4,5)], 'extra')
1165 self.assertRaises(TypeError, next, starmap(10, [(4,5)]))
1166 self.assertRaises(ValueError, next, starmap(errfunc, [(4,5)]))
1167 self.assertRaises(TypeError, next, starmap(onearg, [(4,5)]))
1168
1169 def test_islice(self):
1170 for args in [ # islice(args) should agree with range(args)
1171 (10, 20, 3),
1172 (10, 3, 20),
1173 (10, 20),
1174 (10, 10),
1175 (10, 3),
1176 (20,)
1177 ]:
1178 self.assertEqual(list(islice(range(100), *args)),
1179 list(range(*args)))
1180
1181 for args, tgtargs in [ # Stop when seqn is exhausted
1182 ((10, 110, 3), ((10, 100, 3))),
1183 ((10, 110), ((10, 100))),
1184 ((110,), (100,))
1185 ]:
1186 self.assertEqual(list(islice(range(100), *args)),
1187 list(range(*tgtargs)))
1188
1189 # Test stop=None
1190 self.assertEqual(list(islice(range(10), None)), list(range(10)))
1191 self.assertEqual(list(islice(range(10), None, None)), list(range(10)))
1192 self.assertEqual(list(islice(range(10), None, None, None)), list(range(10)))
1193 self.assertEqual(list(islice(range(10), 2, None)), list(range(2, 10)))
1194 self.assertEqual(list(islice(range(10), 1, None, 2)), list(range(1, 10, 2)))
1195
1196 # Test number of items consumed SF #1171417
1197 it = iter(range(10))
1198 self.assertEqual(list(islice(it, 3)), list(range(3)))
1199 self.assertEqual(list(it), list(range(3, 10)))
1200
1201 it = iter(range(10))
1202 self.assertEqual(list(islice(it, 3, 3)), [])
1203 self.assertEqual(list(it), list(range(3, 10)))
1204
1205 # Test invalid arguments
1206 ra = range(10)
1207 self.assertRaises(TypeError, islice, ra)
1208 self.assertRaises(TypeError, islice, ra, 1, 2, 3, 4)
1209 self.assertRaises(ValueError, islice, ra, -5, 10, 1)
1210 self.assertRaises(ValueError, islice, ra, 1, -5, -1)
1211 self.assertRaises(ValueError, islice, ra, 1, 10, -1)
1212 self.assertRaises(ValueError, islice, ra, 1, 10, 0)
1213 self.assertRaises(ValueError, islice, ra, 'a')
1214 self.assertRaises(ValueError, islice, ra, 'a', 1)
1215 self.assertRaises(ValueError, islice, ra, 1, 'a')
1216 self.assertRaises(ValueError, islice, ra, 'a', 1, 1)
1217 self.assertRaises(ValueError, islice, ra, 1, 'a', 1)
1218 self.assertEqual(len(list(islice(count(), 1, 10, maxsize))), 1)
1219
1220 # Issue #10323: Less islice in a predictable state
1221 c = count()
1222 self.assertEqual(list(islice(c, 1, 3, 50)), [1])
1223 self.assertEqual(next(c), 3)
1224
1225 # Issue #21321: check source iterator is not referenced
1226 # from islice() after the latter has been exhausted
1227 it = (x for x in (1, 2))
1228 wr = weakref.ref(it)
1229 it = islice(it, 1)
1230 self.assertIsNotNone(wr())
1231 list(it) # exhaust the iterator
1232 support.gc_collect()
1233 self.assertIsNone(wr())
1234
1235 # Issue #30537: islice can accept integer-like objects as
1236 # arguments
1237 class IntLike(object):
1238 def __init__(self, val):
1239 self.val = val
1240 def __index__(self):
1241 return self.val
1242 self.assertEqual(list(islice(range(100), IntLike(10))), list(range(10)))
1243 self.assertEqual(list(islice(range(100), IntLike(10), IntLike(50))),
1244 list(range(10, 50)))
1245 self.assertEqual(list(islice(range(100), IntLike(10), IntLike(50), IntLike(5))),
1246 list(range(10,50,5)))
1247
1248 def test_takewhile(self):
1249 data = [1, 3, 5, 20, 2, 4, 6, 8]
1250 self.assertEqual(list(takewhile(underten, data)), [1, 3, 5])
1251 self.assertEqual(list(takewhile(underten, [])), [])
1252 self.assertRaises(TypeError, takewhile)
1253 self.assertRaises(TypeError, takewhile, operator.pow)
1254 self.assertRaises(TypeError, takewhile, operator.pow, [(4,5)], 'extra')
1255 self.assertRaises(TypeError, next, takewhile(10, [(4,5)]))
1256 self.assertRaises(ValueError, next, takewhile(errfunc, [(4,5)]))
1257 t = takewhile(bool, [1, 1, 1, 0, 0, 0])
1258 self.assertEqual(list(t), [1, 1, 1])
1259 self.assertRaises(StopIteration, next, t)
1260
1261 def test_dropwhile(self):
1262 data = [1, 3, 5, 20, 2, 4, 6, 8]
1263 self.assertEqual(list(dropwhile(underten, data)), [20, 2, 4, 6, 8])
1264 self.assertEqual(list(dropwhile(underten, [])), [])
1265 self.assertRaises(TypeError, dropwhile)
1266 self.assertRaises(TypeError, dropwhile, operator.pow)
1267 self.assertRaises(TypeError, dropwhile, operator.pow, [(4,5)], 'extra')
1268 self.assertRaises(TypeError, next, dropwhile(10, [(4,5)]))
1269 self.assertRaises(ValueError, next, dropwhile(errfunc, [(4,5)]))
1270
1271 def test_tee(self):
1272 n = 200
1273
1274 a, b = tee([]) # test empty iterator
1275 self.assertEqual(list(a), [])
1276 self.assertEqual(list(b), [])
1277
1278 a, b = tee(irange(n)) # test 100% interleaved
1279 self.assertEqual(lzip(a,b), lzip(range(n), range(n)))
1280
1281 a, b = tee(irange(n)) # test 0% interleaved
1282 self.assertEqual(list(a), list(range(n)))
1283 self.assertEqual(list(b), list(range(n)))
1284
1285 a, b = tee(irange(n)) # test dealloc of leading iterator
1286 for i in range(100):
1287 self.assertEqual(next(a), i)
1288 del a
1289 self.assertEqual(list(b), list(range(n)))
1290
1291 a, b = tee(irange(n)) # test dealloc of trailing iterator
1292 for i in range(100):
1293 self.assertEqual(next(a), i)
1294 del b
1295 self.assertEqual(list(a), list(range(100, n)))
1296
1297 for j in range(5): # test randomly interleaved
1298 order = [0]*n + [1]*n
1299 random.shuffle(order)
1300 lists = ([], [])
1301 its = tee(irange(n))
1302 for i in order:
1303 value = next(its[i])
1304 lists[i].append(value)
1305 self.assertEqual(lists[0], list(range(n)))
1306 self.assertEqual(lists[1], list(range(n)))
1307
1308 # test argument format checking
1309 self.assertRaises(TypeError, tee)
1310 self.assertRaises(TypeError, tee, 3)
1311 self.assertRaises(TypeError, tee, [1,2], 'x')
1312 self.assertRaises(TypeError, tee, [1,2], 3, 'x')
1313
1314 # tee object should be instantiable
1315 a, b = tee('abc')
1316 c = type(a)('def')
1317 self.assertEqual(list(c), list('def'))
1318
1319 # test long-lagged and multi-way split
1320 a, b, c = tee(range(2000), 3)
1321 for i in range(100):
1322 self.assertEqual(next(a), i)
1323 self.assertEqual(list(b), list(range(2000)))
1324 self.assertEqual([next(c), next(c)], list(range(2)))
1325 self.assertEqual(list(a), list(range(100,2000)))
1326 self.assertEqual(list(c), list(range(2,2000)))
1327
1328 # test values of n
1329 self.assertRaises(TypeError, tee, 'abc', 'invalid')
1330 self.assertRaises(ValueError, tee, [], -1)
1331 for n in range(5):
1332 result = tee('abc', n)
1333 self.assertEqual(type(result), tuple)
1334 self.assertEqual(len(result), n)
1335 self.assertEqual([list(x) for x in result], [list('abc')]*n)
1336
1337 # tee objects are independent (see bug gh-123884)
1338 a, b = tee('abc')
1339 c, d = tee(a)
1340 e, f = tee(c)
1341 self.assertTrue(len({a, b, c, d, e, f}) == 6)
1342
1343 # test tee_new
1344 t1, t2 = tee('abc')
1345 tnew = type(t1)
1346 self.assertRaises(TypeError, tnew)
1347 self.assertRaises(TypeError, tnew, 10)
1348 t3 = tnew(t1)
1349 self.assertTrue(list(t1) == list(t2) == list(t3) == list('abc'))
1350
1351 # test that tee objects are weak referenceable
1352 a, b = tee(range(10))
1353 p = weakref.proxy(a)
1354 self.assertEqual(getattr(p, '__class__'), type(b))
1355 del a
1356 support.gc_collect() # For PyPy or other GCs.
1357 self.assertRaises(ReferenceError, getattr, p, '__class__')
1358
1359 ans = list('abc')
1360 long_ans = list(range(10000))
1361
1362 # check copy
1363 a, b = tee('abc')
1364 self.assertEqual(list(copy.copy(a)), ans)
1365 self.assertEqual(list(copy.copy(b)), ans)
1366 a, b = tee(list(range(10000)))
1367 self.assertEqual(list(copy.copy(a)), long_ans)
1368 self.assertEqual(list(copy.copy(b)), long_ans)
1369
1370 # check partially consumed copy
1371 a, b = tee('abc')
1372 take(2, a)
1373 take(1, b)
1374 self.assertEqual(list(copy.copy(a)), ans[2:])
1375 self.assertEqual(list(copy.copy(b)), ans[1:])
1376 self.assertEqual(list(a), ans[2:])
1377 self.assertEqual(list(b), ans[1:])
1378 a, b = tee(range(10000))
1379 take(100, a)
1380 take(60, b)
1381 self.assertEqual(list(copy.copy(a)), long_ans[100:])
1382 self.assertEqual(list(copy.copy(b)), long_ans[60:])
1383 self.assertEqual(list(a), long_ans[100:])
1384 self.assertEqual(list(b), long_ans[60:])
1385
1386 def test_tee_dealloc_segfault(self):
1387 # gh-115874: segfaults when accessing module state in tp_dealloc.
1388 script = (
1389 "import typing, copyreg, itertools; "
1390 "copyreg.buggy_tee = itertools.tee(())"
1391 )
1392 script_helper.assert_python_ok("-c", script)
1393
1394 # Issue 13454: Crash when deleting backward iterator from tee()
1395 def test_tee_del_backward(self):
1396 forward, backward = tee(repeat(None, 20000000))
1397 try:
1398 any(forward) # exhaust the iterator
1399 del backward
1400 except:
1401 del forward, backward
1402 raise
1403
1404 def test_tee_reenter(self):
1405 class I:
1406 first = True
1407 def __iter__(self):
1408 return self
1409 def __next__(self):
1410 first = self.first
1411 self.first = False
1412 if first:
1413 return next(b)
1414
1415 a, b = tee(I())
1416 with self.assertRaisesRegex(RuntimeError, "tee"):
1417 next(a)
1418
1419 @threading_helper.requires_working_threading()
1420 def test_tee_concurrent(self):
1421 start = threading.Event()
1422 finish = threading.Event()
1423 class I:
1424 def __iter__(self):
1425 return self
1426 def __next__(self):
1427 start.set()
1428 finish.wait()
1429
1430 a, b = tee(I())
1431 thread = threading.Thread(target=next, args=[a])
1432 thread.start()
1433 try:
1434 start.wait()
1435 with self.assertRaisesRegex(RuntimeError, "tee"):
1436 next(b)
1437 finally:
1438 finish.set()
1439 thread.join()
1440
1441 def test_StopIteration(self):
1442 self.assertRaises(StopIteration, next, zip())
1443
1444 for f in (chain, cycle, zip, groupby):
1445 self.assertRaises(StopIteration, next, f([]))
1446 self.assertRaises(StopIteration, next, f(StopNow()))
1447
1448 self.assertRaises(StopIteration, next, islice([], None))
1449 self.assertRaises(StopIteration, next, islice(StopNow(), None))
1450
1451 p, q = tee([])
1452 self.assertRaises(StopIteration, next, p)
1453 self.assertRaises(StopIteration, next, q)
1454 p, q = tee(StopNow())
1455 self.assertRaises(StopIteration, next, p)
1456 self.assertRaises(StopIteration, next, q)
1457
1458 self.assertRaises(StopIteration, next, repeat(None, 0))
1459
1460 for f in (filter, filterfalse, map, takewhile, dropwhile, starmap):
1461 self.assertRaises(StopIteration, next, f(lambda x:x, []))
1462 self.assertRaises(StopIteration, next, f(lambda x:x, StopNow()))
1463
1464 @support.cpython_only
1465 def test_combinations_result_gc(self):
1466 # bpo-42536: combinations's tuple-reuse speed trick breaks the GC's
1467 # assumptions about what can be untracked. Make sure we re-track result
1468 # tuples whenever we reuse them.
1469 it = combinations([None, []], 1)
1470 next(it)
1471 gc.collect()
1472 # That GC collection probably untracked the recycled internal result
1473 # tuple, which has the value (None,). Make sure it's re-tracked when
1474 # it's mutated and returned from __next__:
1475 self.assertTrue(gc.is_tracked(next(it)))
1476
1477 @support.cpython_only
1478 def test_combinations_with_replacement_result_gc(self):
1479 # Ditto for combinations_with_replacement.
1480 it = combinations_with_replacement([None, []], 1)
1481 next(it)
1482 gc.collect()
1483 self.assertTrue(gc.is_tracked(next(it)))
1484
1485 @support.cpython_only
1486 def test_permutations_result_gc(self):
1487 # Ditto for permutations.
1488 it = permutations([None, []], 1)
1489 next(it)
1490 gc.collect()
1491 self.assertTrue(gc.is_tracked(next(it)))
1492
1493 @support.cpython_only
1494 def test_product_result_gc(self):
1495 # Ditto for product.
1496 it = product([None, []])
1497 next(it)
1498 gc.collect()
1499 self.assertTrue(gc.is_tracked(next(it)))
1500
1501 @support.cpython_only
1502 def test_zip_longest_result_gc(self):
1503 # Ditto for zip_longest.
1504 it = zip_longest([[]])
1505 gc.collect()
1506 self.assertTrue(gc.is_tracked(next(it)))
1507
1508 @support.cpython_only
1509 def test_pairwise_result_gc(self):
1510 # Ditto for pairwise.
1511 it = pairwise([None, None])
1512 gc.collect()
1513 self.assertTrue(gc.is_tracked(next(it)))
1514
1515 @support.cpython_only
1516 def test_immutable_types(self):
1517 from itertools import _grouper, _tee, _tee_dataobject
1518 dataset = (
1519 accumulate,
1520 batched,
1521 chain,
1522 combinations,
1523 combinations_with_replacement,
1524 compress,
1525 count,
1526 cycle,
1527 dropwhile,
1528 filterfalse,
1529 groupby,
1530 _grouper,
1531 islice,
1532 pairwise,
1533 permutations,
1534 product,
1535 repeat,
1536 starmap,
1537 takewhile,
1538 _tee,
1539 _tee_dataobject,
1540 zip_longest,
1541 )
1542 for tp in dataset:
1543 with self.subTest(tp=tp):
1544 with self.assertRaisesRegex(TypeError, "immutable"):
1545 tp.foobar = 1
1546
1547
1548 class TestExamples(unittest.TestCase):
1549
1550 def test_accumulate(self):
1551 self.assertEqual(list(accumulate([1,2,3,4,5])), [1, 3, 6, 10, 15])
1552
1553 def test_chain(self):
1554 self.assertEqual(''.join(chain('ABC', 'DEF')), 'ABCDEF')
1555
1556 def test_chain_from_iterable(self):
1557 self.assertEqual(''.join(chain.from_iterable(['ABC', 'DEF'])), 'ABCDEF')
1558
1559 def test_combinations(self):
1560 self.assertEqual(list(combinations('ABCD', 2)),
1561 [('A','B'), ('A','C'), ('A','D'), ('B','C'), ('B','D'), ('C','D')])
1562 self.assertEqual(list(combinations(range(4), 3)),
1563 [(0,1,2), (0,1,3), (0,2,3), (1,2,3)])
1564
1565 def test_combinations_with_replacement(self):
1566 self.assertEqual(list(combinations_with_replacement('ABC', 2)),
1567 [('A','A'), ('A','B'), ('A','C'), ('B','B'), ('B','C'), ('C','C')])
1568
1569 def test_compress(self):
1570 self.assertEqual(list(compress('ABCDEF', [1,0,1,0,1,1])), list('ACEF'))
1571
1572 def test_count(self):
1573 self.assertEqual(list(islice(count(10), 5)), [10, 11, 12, 13, 14])
1574
1575 def test_cycle(self):
1576 self.assertEqual(list(islice(cycle('ABCD'), 12)), list('ABCDABCDABCD'))
1577
1578 def test_dropwhile(self):
1579 self.assertEqual(list(dropwhile(lambda x: x<5, [1,4,6,4,1])), [6,4,1])
1580
1581 def test_groupby(self):
1582 self.assertEqual([k for k, g in groupby('AAAABBBCCDAABBB')],
1583 list('ABCDAB'))
1584 self.assertEqual([(list(g)) for k, g in groupby('AAAABBBCCD')],
1585 [list('AAAA'), list('BBB'), list('CC'), list('D')])
1586
1587 def test_filter(self):
1588 self.assertEqual(list(filter(lambda x: x%2, range(10))), [1,3,5,7,9])
1589
1590 def test_filterfalse(self):
1591 self.assertEqual(list(filterfalse(lambda x: x%2, range(10))), [0,2,4,6,8])
1592
1593 def test_map(self):
1594 self.assertEqual(list(map(pow, (2,3,10), (5,2,3))), [32, 9, 1000])
1595
1596 def test_islice(self):
1597 self.assertEqual(list(islice('ABCDEFG', 2)), list('AB'))
1598 self.assertEqual(list(islice('ABCDEFG', 2, 4)), list('CD'))
1599 self.assertEqual(list(islice('ABCDEFG', 2, None)), list('CDEFG'))
1600 self.assertEqual(list(islice('ABCDEFG', 0, None, 2)), list('ACEG'))
1601
1602 def test_zip(self):
1603 self.assertEqual(list(zip('ABCD', 'xy')), [('A', 'x'), ('B', 'y')])
1604
1605 def test_zip_longest(self):
1606 self.assertEqual(list(zip_longest('ABCD', 'xy', fillvalue='-')),
1607 [('A', 'x'), ('B', 'y'), ('C', '-'), ('D', '-')])
1608
1609 def test_permutations(self):
1610 self.assertEqual(list(permutations('ABCD', 2)),
1611 list(map(tuple, 'AB AC AD BA BC BD CA CB CD DA DB DC'.split())))
1612 self.assertEqual(list(permutations(range(3))),
1613 [(0,1,2), (0,2,1), (1,0,2), (1,2,0), (2,0,1), (2,1,0)])
1614
1615 def test_product(self):
1616 self.assertEqual(list(product('ABCD', 'xy')),
1617 list(map(tuple, 'Ax Ay Bx By Cx Cy Dx Dy'.split())))
1618 self.assertEqual(list(product(range(2), repeat=3)),
1619 [(0,0,0), (0,0,1), (0,1,0), (0,1,1),
1620 (1,0,0), (1,0,1), (1,1,0), (1,1,1)])
1621
1622 def test_repeat(self):
1623 self.assertEqual(list(repeat(10, 3)), [10, 10, 10])
1624
1625 def test_stapmap(self):
1626 self.assertEqual(list(starmap(pow, [(2,5), (3,2), (10,3)])),
1627 [32, 9, 1000])
1628
1629 def test_takewhile(self):
1630 self.assertEqual(list(takewhile(lambda x: x<5, [1,4,6,4,1])), [1,4])
1631
1632
1633 class TestPurePythonRoughEquivalents(unittest.TestCase):
1634
1635 def test_batched_recipe(self):
1636 def batched_recipe(iterable, n):
1637 "Batch data into tuples of length n. The last batch may be shorter."
1638 # batched('ABCDEFG', 3) --> ABC DEF G
1639 if n < 1:
1640 raise ValueError('n must be at least one')
1641 it = iter(iterable)
1642 while batch := tuple(islice(it, n)):
1643 yield batch
1644
1645 for iterable, n in product(
1646 ['', 'a', 'ab', 'abc', 'abcd', 'abcde', 'abcdef', 'abcdefg', None],
1647 [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, None]):
1648 with self.subTest(iterable=iterable, n=n):
1649 try:
1650 e1, r1 = None, list(batched(iterable, n))
1651 except Exception as e:
1652 e1, r1 = type(e), None
1653 try:
1654 e2, r2 = None, list(batched_recipe(iterable, n))
1655 except Exception as e:
1656 e2, r2 = type(e), None
1657 self.assertEqual(r1, r2)
1658 self.assertEqual(e1, e2)
1659
1660
1661 def test_groupby_recipe(self):
1662
1663 # Begin groupby() recipe #######################################
1664
1665 def groupby(iterable, key=None):
1666 # [k for k, g in groupby('AAAABBBCCDAABBB')] → A B C D A B
1667 # [list(g) for k, g in groupby('AAAABBBCCD')] → AAAA BBB CC D
1668
1669 keyfunc = (lambda x: x) if key is None else key
1670 iterator = iter(iterable)
1671 exhausted = False
1672
1673 def _grouper(target_key):
1674 nonlocal curr_value, curr_key, exhausted
1675 yield curr_value
1676 for curr_value in iterator:
1677 curr_key = keyfunc(curr_value)
1678 if curr_key != target_key:
1679 return
1680 yield curr_value
1681 exhausted = True
1682
1683 try:
1684 curr_value = next(iterator)
1685 except StopIteration:
1686 return
1687 curr_key = keyfunc(curr_value)
1688
1689 while not exhausted:
1690 target_key = curr_key
1691 curr_group = _grouper(target_key)
1692 yield curr_key, curr_group
1693 if curr_key == target_key:
1694 for _ in curr_group:
1695 pass
1696
1697 # End groupby() recipe #########################################
1698
1699 # Check whether it accepts arguments correctly
1700 self.assertEqual([], list(groupby([])))
1701 self.assertEqual([], list(groupby([], key=id)))
1702 self.assertRaises(TypeError, list, groupby('abc', []))
1703 if False:
1704 # Test not applicable to the recipe
1705 self.assertRaises(TypeError, list, groupby('abc', None))
1706 self.assertRaises(TypeError, groupby, 'abc', lambda x:x, 10)
1707
1708 # Check normal input
1709 s = [(0, 10, 20), (0, 11,21), (0,12,21), (1,13,21), (1,14,22),
1710 (2,15,22), (3,16,23), (3,17,23)]
1711 dup = []
1712 for k, g in groupby(s, lambda r:r[0]):
1713 for elem in g:
1714 self.assertEqual(k, elem[0])
1715 dup.append(elem)
1716 self.assertEqual(s, dup)
1717
1718 # Check nested case
1719 dup = []
1720 for k, g in groupby(s, testR):
1721 for ik, ig in groupby(g, testR2):
1722 for elem in ig:
1723 self.assertEqual(k, elem[0])
1724 self.assertEqual(ik, elem[2])
1725 dup.append(elem)
1726 self.assertEqual(s, dup)
1727
1728 # Check case where inner iterator is not used
1729 keys = [k for k, g in groupby(s, testR)]
1730 expectedkeys = set([r[0] for r in s])
1731 self.assertEqual(set(keys), expectedkeys)
1732 self.assertEqual(len(keys), len(expectedkeys))
1733
1734 # Check case where inner iterator is used after advancing the groupby
1735 # iterator
1736 s = list(zip('AABBBAAAA', range(9)))
1737 it = groupby(s, testR)
1738 _, g1 = next(it)
1739 _, g2 = next(it)
1740 _, g3 = next(it)
1741 self.assertEqual(list(g1), [])
1742 self.assertEqual(list(g2), [])
1743 self.assertEqual(next(g3), ('A', 5))
1744 list(it) # exhaust the groupby iterator
1745 self.assertEqual(list(g3), [])
1746
1747 # Exercise pipes and filters style
1748 s = 'abracadabra'
1749 # sort s | uniq
1750 r = [k for k, g in groupby(sorted(s))]
1751 self.assertEqual(r, ['a', 'b', 'c', 'd', 'r'])
1752 # sort s | uniq -d
1753 r = [k for k, g in groupby(sorted(s)) if list(islice(g,1,2))]
1754 self.assertEqual(r, ['a', 'b', 'r'])
1755 # sort s | uniq -c
1756 r = [(len(list(g)), k) for k, g in groupby(sorted(s))]
1757 self.assertEqual(r, [(5, 'a'), (2, 'b'), (1, 'c'), (1, 'd'), (2, 'r')])
1758 # sort s | uniq -c | sort -rn | head -3
1759 r = sorted([(len(list(g)) , k) for k, g in groupby(sorted(s))], reverse=True)[:3]
1760 self.assertEqual(r, [(5, 'a'), (2, 'r'), (2, 'b')])
1761
1762 # iter.__next__ failure
1763 class ExpectedError(Exception):
1764 pass
1765 def delayed_raise(n=0):
1766 for i in range(n):
1767 yield 'yo'
1768 raise ExpectedError
1769 def gulp(iterable, keyp=None, func=list):
1770 return [func(g) for k, g in groupby(iterable, keyp)]
1771
1772 # iter.__next__ failure on outer object
1773 self.assertRaises(ExpectedError, gulp, delayed_raise(0))
1774 # iter.__next__ failure on inner object
1775 self.assertRaises(ExpectedError, gulp, delayed_raise(1))
1776
1777 # __eq__ failure
1778 class DummyCmp:
1779 def __eq__(self, dst):
1780 raise ExpectedError
1781 s = [DummyCmp(), DummyCmp(), None]
1782
1783 # __eq__ failure on outer object
1784 self.assertRaises(ExpectedError, gulp, s, func=id)
1785 # __eq__ failure on inner object
1786 self.assertRaises(ExpectedError, gulp, s)
1787
1788 # keyfunc failure
1789 def keyfunc(obj):
1790 if keyfunc.skip > 0:
1791 keyfunc.skip -= 1
1792 return obj
1793 else:
1794 raise ExpectedError
1795
1796 # keyfunc failure on outer object
1797 keyfunc.skip = 0
1798 self.assertRaises(ExpectedError, gulp, [None], keyfunc)
1799 keyfunc.skip = 1
1800 self.assertRaises(ExpectedError, gulp, [None, None], keyfunc)
1801
1802
1803 @staticmethod
1804 def islice(iterable, *args):
1805 # islice('ABCDEFG', 2) → A B
1806 # islice('ABCDEFG', 2, 4) → C D
1807 # islice('ABCDEFG', 2, None) → C D E F G
1808 # islice('ABCDEFG', 0, None, 2) → A C E G
1809
1810 s = slice(*args)
1811 start = 0 if s.start is None else s.start
1812 stop = s.stop
1813 step = 1 if s.step is None else s.step
1814 if start < 0 or (stop is not None and stop < 0) or step <= 0:
1815 raise ValueError
1816
1817 indices = count() if stop is None else range(max(start, stop))
1818 next_i = start
1819 for i, element in zip(indices, iterable):
1820 if i == next_i:
1821 yield element
1822 next_i += step
1823
1824 def test_islice_recipe(self):
1825 self.assertEqual(list(self.islice('ABCDEFG', 2)), list('AB'))
1826 self.assertEqual(list(self.islice('ABCDEFG', 2, 4)), list('CD'))
1827 self.assertEqual(list(self.islice('ABCDEFG', 2, None)), list('CDEFG'))
1828 self.assertEqual(list(self.islice('ABCDEFG', 0, None, 2)), list('ACEG'))
1829 # Test items consumed.
1830 it = iter(range(10))
1831 self.assertEqual(list(self.islice(it, 3)), list(range(3)))
1832 self.assertEqual(list(it), list(range(3, 10)))
1833 it = iter(range(10))
1834 self.assertEqual(list(self.islice(it, 3, 3)), [])
1835 self.assertEqual(list(it), list(range(3, 10)))
1836 # Test that slice finishes in predictable state.
1837 c = count()
1838 self.assertEqual(list(self.islice(c, 1, 3, 50)), [1])
1839 self.assertEqual(next(c), 3)
1840
1841
1842 def test_tee_recipe(self):
1843
1844 # Begin tee() recipe ###########################################
1845
1846 def tee(iterable, n=2):
1847 if n < 0:
1848 raise ValueError
1849 if n == 0:
1850 return ()
1851 iterator = _tee(iterable)
1852 result = [iterator]
1853 for _ in range(n - 1):
1854 result.append(_tee(iterator))
1855 return tuple(result)
1856
1857 class _tee:
1858
1859 def __init__(self, iterable):
1860 it = iter(iterable)
1861 if isinstance(it, _tee):
1862 self.iterator = it.iterator
1863 self.link = it.link
1864 else:
1865 self.iterator = it
1866 self.link = [None, None]
1867
1868 def __iter__(self):
1869 return self
1870
1871 def __next__(self):
1872 link = self.link
1873 if link[1] is None:
1874 link[0] = next(self.iterator)
1875 link[1] = [None, None]
1876 value, self.link = link
1877 return value
1878
1879 # End tee() recipe #############################################
1880
1881 n = 200
1882
1883 a, b = tee([]) # test empty iterator
1884 self.assertEqual(list(a), [])
1885 self.assertEqual(list(b), [])
1886
1887 a, b = tee(irange(n)) # test 100% interleaved
1888 self.assertEqual(lzip(a,b), lzip(range(n), range(n)))
1889
1890 a, b = tee(irange(n)) # test 0% interleaved
1891 self.assertEqual(list(a), list(range(n)))
1892 self.assertEqual(list(b), list(range(n)))
1893
1894 a, b = tee(irange(n)) # test dealloc of leading iterator
1895 for i in range(100):
1896 self.assertEqual(next(a), i)
1897 del a
1898 self.assertEqual(list(b), list(range(n)))
1899
1900 a, b = tee(irange(n)) # test dealloc of trailing iterator
1901 for i in range(100):
1902 self.assertEqual(next(a), i)
1903 del b
1904 self.assertEqual(list(a), list(range(100, n)))
1905
1906 for j in range(5): # test randomly interleaved
1907 order = [0]*n + [1]*n
1908 random.shuffle(order)
1909 lists = ([], [])
1910 its = tee(irange(n))
1911 for i in order:
1912 value = next(its[i])
1913 lists[i].append(value)
1914 self.assertEqual(lists[0], list(range(n)))
1915 self.assertEqual(lists[1], list(range(n)))
1916
1917 # test argument format checking
1918 self.assertRaises(TypeError, tee)
1919 self.assertRaises(TypeError, tee, 3)
1920 self.assertRaises(TypeError, tee, [1,2], 'x')
1921 self.assertRaises(TypeError, tee, [1,2], 3, 'x')
1922
1923 # tee object should be instantiable
1924 a, b = tee('abc')
1925 c = type(a)('def')
1926 self.assertEqual(list(c), list('def'))
1927
1928 # test long-lagged and multi-way split
1929 a, b, c = tee(range(2000), 3)
1930 for i in range(100):
1931 self.assertEqual(next(a), i)
1932 self.assertEqual(list(b), list(range(2000)))
1933 self.assertEqual([next(c), next(c)], list(range(2)))
1934 self.assertEqual(list(a), list(range(100,2000)))
1935 self.assertEqual(list(c), list(range(2,2000)))
1936
1937 # test invalid values of n
1938 self.assertRaises(TypeError, tee, 'abc', 'invalid')
1939 self.assertRaises(ValueError, tee, [], -1)
1940
1941 for n in range(5):
1942 result = tee('abc', n)
1943 self.assertEqual(type(result), tuple)
1944 self.assertEqual(len(result), n)
1945 self.assertEqual([list(x) for x in result], [list('abc')]*n)
1946
1947 # tee objects are independent (see bug gh-123884)
1948 a, b = tee('abc')
1949 c, d = tee(a)
1950 e, f = tee(c)
1951 self.assertTrue(len({a, b, c, d, e, f}) == 6)
1952
1953 # test tee_new
1954 t1, t2 = tee('abc')
1955 tnew = type(t1)
1956 self.assertRaises(TypeError, tnew)
1957 self.assertRaises(TypeError, tnew, 10)
1958 t3 = tnew(t1)
1959 self.assertTrue(list(t1) == list(t2) == list(t3) == list('abc'))
1960
1961 # test that tee objects are weak referencable
1962 a, b = tee(range(10))
1963 p = weakref.proxy(a)
1964 self.assertEqual(getattr(p, '__class__'), type(b))
1965 del a
1966 gc.collect() # For PyPy or other GCs.
1967 self.assertRaises(ReferenceError, getattr, p, '__class__')
1968
1969 ans = list('abc')
1970 long_ans = list(range(10000))
1971
1972 # Tests not applicable to the tee() recipe
1973 if False:
1974 # check copy
1975 a, b = tee('abc')
1976 self.assertEqual(list(copy.copy(a)), ans)
1977 self.assertEqual(list(copy.copy(b)), ans)
1978 a, b = tee(list(range(10000)))
1979 self.assertEqual(list(copy.copy(a)), long_ans)
1980 self.assertEqual(list(copy.copy(b)), long_ans)
1981
1982 # check partially consumed copy
1983 a, b = tee('abc')
1984 take(2, a)
1985 take(1, b)
1986 self.assertEqual(list(copy.copy(a)), ans[2:])
1987 self.assertEqual(list(copy.copy(b)), ans[1:])
1988 self.assertEqual(list(a), ans[2:])
1989 self.assertEqual(list(b), ans[1:])
1990 a, b = tee(range(10000))
1991 take(100, a)
1992 take(60, b)
1993 self.assertEqual(list(copy.copy(a)), long_ans[100:])
1994 self.assertEqual(list(copy.copy(b)), long_ans[60:])
1995 self.assertEqual(list(a), long_ans[100:])
1996 self.assertEqual(list(b), long_ans[60:])
1997
1998 # Issue 13454: Crash when deleting backward iterator from tee()
1999 forward, backward = tee(repeat(None, 2000)) # 20000000
2000 try:
2001 any(forward) # exhaust the iterator
2002 del backward
2003 except:
2004 del forward, backward
2005 raise
2006
2007
2008 class TestGC(unittest.TestCase):
2009
2010 def makecycle(self, iterator, container):
2011 container.append(iterator)
2012 next(iterator)
2013 del container, iterator
2014
2015 def test_accumulate(self):
2016 a = []
2017 self.makecycle(accumulate([1,2,a,3]), a)
2018
2019 def test_batched(self):
2020 a = []
2021 self.makecycle(batched([1,2,a,3], 2), a)
2022
2023 def test_chain(self):
2024 a = []
2025 self.makecycle(chain(a), a)
2026
2027 def test_chain_from_iterable(self):
2028 a = []
2029 self.makecycle(chain.from_iterable([a]), a)
2030
2031 def test_combinations(self):
2032 a = []
2033 self.makecycle(combinations([1,2,a,3], 3), a)
2034
2035 def test_combinations_with_replacement(self):
2036 a = []
2037 self.makecycle(combinations_with_replacement([1,2,a,3], 3), a)
2038
2039 def test_compress(self):
2040 a = []
2041 self.makecycle(compress('ABCDEF', [1,0,1,0,1,0]), a)
2042
2043 def test_count(self):
2044 a = []
2045 Int = type('Int', (int,), dict(x=a))
2046 self.makecycle(count(Int(0), Int(1)), a)
2047
2048 def test_cycle(self):
2049 a = []
2050 self.makecycle(cycle([a]*2), a)
2051
2052 def test_dropwhile(self):
2053 a = []
2054 self.makecycle(dropwhile(bool, [0, a, a]), a)
2055
2056 def test_groupby(self):
2057 a = []
2058 self.makecycle(groupby([a]*2, lambda x:x), a)
2059
2060 def test_issue2246(self):
2061 # Issue 2246 -- the _grouper iterator was not included in GC
2062 n = 10
2063 keyfunc = lambda x: x
2064 for i, j in groupby(range(n), key=keyfunc):
2065 keyfunc.__dict__.setdefault('x',[]).append(j)
2066
2067 def test_filter(self):
2068 a = []
2069 self.makecycle(filter(lambda x:True, [a]*2), a)
2070
2071 def test_filterfalse(self):
2072 a = []
2073 self.makecycle(filterfalse(lambda x:False, a), a)
2074
2075 def test_zip(self):
2076 a = []
2077 self.makecycle(zip([a]*2, [a]*3), a)
2078
2079 def test_zip_longest(self):
2080 a = []
2081 self.makecycle(zip_longest([a]*2, [a]*3), a)
2082 b = [a, None]
2083 self.makecycle(zip_longest([a]*2, [a]*3, fillvalue=b), a)
2084
2085 def test_map(self):
2086 a = []
2087 self.makecycle(map(lambda x:x, [a]*2), a)
2088
2089 def test_islice(self):
2090 a = []
2091 self.makecycle(islice([a]*2, None), a)
2092
2093 def test_pairwise(self):
2094 a = []
2095 self.makecycle(pairwise([a]*5), a)
2096
2097 def test_permutations(self):
2098 a = []
2099 self.makecycle(permutations([1,2,a,3], 3), a)
2100
2101 def test_product(self):
2102 a = []
2103 self.makecycle(product([1,2,a,3], repeat=3), a)
2104
2105 def test_repeat(self):
2106 a = []
2107 self.makecycle(repeat(a), a)
2108
2109 def test_starmap(self):
2110 a = []
2111 self.makecycle(starmap(lambda *t: t, [(a,a)]*2), a)
2112
2113 def test_takewhile(self):
2114 a = []
2115 self.makecycle(takewhile(bool, [1, 0, a, a]), a)
2116
2117 def R(seqn):
2118 'Regular generator'
2119 for i in seqn:
2120 yield i
2121
2122 class G:
2123 'Sequence using __getitem__'
2124 def __init__(self, seqn):
2125 self.seqn = seqn
2126 def __getitem__(self, i):
2127 return self.seqn[i]
2128
2129 class I:
2130 'Sequence using iterator protocol'
2131 def __init__(self, seqn):
2132 self.seqn = seqn
2133 self.i = 0
2134 def __iter__(self):
2135 return self
2136 def __next__(self):
2137 if self.i >= len(self.seqn): raise StopIteration
2138 v = self.seqn[self.i]
2139 self.i += 1
2140 return v
2141
2142 class Ig:
2143 'Sequence using iterator protocol defined with a generator'
2144 def __init__(self, seqn):
2145 self.seqn = seqn
2146 self.i = 0
2147 def __iter__(self):
2148 for val in self.seqn:
2149 yield val
2150
2151 class X:
2152 'Missing __getitem__ and __iter__'
2153 def __init__(self, seqn):
2154 self.seqn = seqn
2155 self.i = 0
2156 def __next__(self):
2157 if self.i >= len(self.seqn): raise StopIteration
2158 v = self.seqn[self.i]
2159 self.i += 1
2160 return v
2161
2162 class N:
2163 'Iterator missing __next__()'
2164 def __init__(self, seqn):
2165 self.seqn = seqn
2166 self.i = 0
2167 def __iter__(self):
2168 return self
2169
2170 class E:
2171 'Test propagation of exceptions'
2172 def __init__(self, seqn):
2173 self.seqn = seqn
2174 self.i = 0
2175 def __iter__(self):
2176 return self
2177 def __next__(self):
2178 3 // 0
2179
2180 class E2:
2181 'Test propagation of exceptions after two iterations'
2182 def __init__(self, seqn):
2183 self.seqn = seqn
2184 self.i = 0
2185 def __iter__(self):
2186 return self
2187 def __next__(self):
2188 if self.i == 2:
2189 raise ZeroDivisionError
2190 v = self.seqn[self.i]
2191 self.i += 1
2192 return v
2193
2194 class S:
2195 'Test immediate stop'
2196 def __init__(self, seqn):
2197 pass
2198 def __iter__(self):
2199 return self
2200 def __next__(self):
2201 raise StopIteration
2202
2203 def L(seqn):
2204 'Test multiple tiers of iterators'
2205 return chain(map(lambda x:x, R(Ig(G(seqn)))))
2206
2207
2208 class TestVariousIteratorArgs(unittest.TestCase):
2209
2210 def test_accumulate(self):
2211 s = [1,2,3,4,5]
2212 r = [1,3,6,10,15]
2213 n = len(s)
2214 for g in (G, I, Ig, L, R):
2215 self.assertEqual(list(accumulate(g(s))), r)
2216 self.assertEqual(list(accumulate(S(s))), [])
2217 self.assertRaises(TypeError, accumulate, X(s))
2218 self.assertRaises(TypeError, accumulate, N(s))
2219 self.assertRaises(ZeroDivisionError, list, accumulate(E(s)))
2220
2221 def test_batched(self):
2222 s = 'abcde'
2223 r = [('a', 'b'), ('c', 'd'), ('e',)]
2224 n = 2
2225 for g in (G, I, Ig, L, R):
2226 with self.subTest(g=g):
2227 self.assertEqual(list(batched(g(s), n)), r)
2228 self.assertEqual(list(batched(S(s), 2)), [])
2229 self.assertRaises(TypeError, batched, X(s), 2)
2230 self.assertRaises(TypeError, batched, N(s), 2)
2231 self.assertRaises(ZeroDivisionError, list, batched(E(s), 2))
2232 self.assertRaises(ZeroDivisionError, list, batched(E2(s), 4))
2233
2234 def test_chain(self):
2235 for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
2236 for g in (G, I, Ig, S, L, R):
2237 self.assertEqual(list(chain(g(s))), list(g(s)))
2238 self.assertEqual(list(chain(g(s), g(s))), list(g(s))+list(g(s)))
2239 self.assertRaises(TypeError, list, chain(X(s)))
2240 self.assertRaises(TypeError, list, chain(N(s)))
2241 self.assertRaises(ZeroDivisionError, list, chain(E(s)))
2242
2243 def test_compress(self):
2244 for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
2245 n = len(s)
2246 for g in (G, I, Ig, S, L, R):
2247 self.assertEqual(list(compress(g(s), repeat(1))), list(g(s)))
2248 self.assertRaises(TypeError, compress, X(s), repeat(1))
2249 self.assertRaises(TypeError, compress, N(s), repeat(1))
2250 self.assertRaises(ZeroDivisionError, list, compress(E(s), repeat(1)))
2251
2252 def test_product(self):
2253 for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
2254 self.assertRaises(TypeError, product, X(s))
2255 self.assertRaises(TypeError, product, N(s))
2256 self.assertRaises(ZeroDivisionError, product, E(s))
2257
2258 def test_cycle(self):
2259 for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
2260 for g in (G, I, Ig, S, L, R):
2261 tgtlen = len(s) * 3
2262 expected = list(g(s))*3
2263 actual = list(islice(cycle(g(s)), tgtlen))
2264 self.assertEqual(actual, expected)
2265 self.assertRaises(TypeError, cycle, X(s))
2266 self.assertRaises(TypeError, cycle, N(s))
2267 self.assertRaises(ZeroDivisionError, list, cycle(E(s)))
2268
2269 def test_groupby(self):
2270 for s in (range(10), range(0), range(1000), (7,11), range(2000,2200,5)):
2271 for g in (G, I, Ig, S, L, R):
2272 self.assertEqual([k for k, sb in groupby(g(s))], list(g(s)))
2273 self.assertRaises(TypeError, groupby, X(s))
2274 self.assertRaises(TypeError, groupby, N(s))
2275 self.assertRaises(ZeroDivisionError, list, groupby(E(s)))
2276
2277 def test_filter(self):
2278 for s in (range(10), range(0), range(1000), (7,11), range(2000,2200,5)):
2279 for g in (G, I, Ig, S, L, R):
2280 self.assertEqual(list(filter(isEven, g(s))),
2281 [x for x in g(s) if isEven(x)])
2282 self.assertRaises(TypeError, filter, isEven, X(s))
2283 self.assertRaises(TypeError, filter, isEven, N(s))
2284 self.assertRaises(ZeroDivisionError, list, filter(isEven, E(s)))
2285
2286 def test_filterfalse(self):
2287 for s in (range(10), range(0), range(1000), (7,11), range(2000,2200,5)):
2288 for g in (G, I, Ig, S, L, R):
2289 self.assertEqual(list(filterfalse(isEven, g(s))),
2290 [x for x in g(s) if isOdd(x)])
2291 self.assertRaises(TypeError, filterfalse, isEven, X(s))
2292 self.assertRaises(TypeError, filterfalse, isEven, N(s))
2293 self.assertRaises(ZeroDivisionError, list, filterfalse(isEven, E(s)))
2294
2295 def test_zip(self):
2296 for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
2297 for g in (G, I, Ig, S, L, R):
2298 self.assertEqual(list(zip(g(s))), lzip(g(s)))
2299 self.assertEqual(list(zip(g(s), g(s))), lzip(g(s), g(s)))
2300 self.assertRaises(TypeError, zip, X(s))
2301 self.assertRaises(TypeError, zip, N(s))
2302 self.assertRaises(ZeroDivisionError, list, zip(E(s)))
2303
2304 def test_ziplongest(self):
2305 for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
2306 for g in (G, I, Ig, S, L, R):
2307 self.assertEqual(list(zip_longest(g(s))), list(zip(g(s))))
2308 self.assertEqual(list(zip_longest(g(s), g(s))), list(zip(g(s), g(s))))
2309 self.assertRaises(TypeError, zip_longest, X(s))
2310 self.assertRaises(TypeError, zip_longest, N(s))
2311 self.assertRaises(ZeroDivisionError, list, zip_longest(E(s)))
2312
2313 def test_map(self):
2314 for s in (range(10), range(0), range(100), (7,11), range(20,50,5)):
2315 for g in (G, I, Ig, S, L, R):
2316 self.assertEqual(list(map(onearg, g(s))),
2317 [onearg(x) for x in g(s)])
2318 self.assertEqual(list(map(operator.pow, g(s), g(s))),
2319 [x**x for x in g(s)])
2320 self.assertRaises(TypeError, map, onearg, X(s))
2321 self.assertRaises(TypeError, map, onearg, N(s))
2322 self.assertRaises(ZeroDivisionError, list, map(onearg, E(s)))
2323
2324 def test_islice(self):
2325 for s in ("12345", "", range(1000), ('do', 1.2), range(2000,2200,5)):
2326 for g in (G, I, Ig, S, L, R):
2327 self.assertEqual(list(islice(g(s),1,None,2)), list(g(s))[1::2])
2328 self.assertRaises(TypeError, islice, X(s), 10)
2329 self.assertRaises(TypeError, islice, N(s), 10)
2330 self.assertRaises(ZeroDivisionError, list, islice(E(s), 10))
2331
2332 def test_pairwise(self):
2333 for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
2334 for g in (G, I, Ig, S, L, R):
2335 seq = list(g(s))
2336 expected = list(zip(seq, seq[1:]))
2337 actual = list(pairwise(g(s)))
2338 self.assertEqual(actual, expected)
2339 self.assertRaises(TypeError, pairwise, X(s))
2340 self.assertRaises(TypeError, pairwise, N(s))
2341 self.assertRaises(ZeroDivisionError, list, pairwise(E(s)))
2342
2343 def test_starmap(self):
2344 for s in (range(10), range(0), range(100), (7,11), range(20,50,5)):
2345 for g in (G, I, Ig, S, L, R):
2346 ss = lzip(s, s)
2347 self.assertEqual(list(starmap(operator.pow, g(ss))),
2348 [x**x for x in g(s)])
2349 self.assertRaises(TypeError, starmap, operator.pow, X(ss))
2350 self.assertRaises(TypeError, starmap, operator.pow, N(ss))
2351 self.assertRaises(ZeroDivisionError, list, starmap(operator.pow, E(ss)))
2352
2353 def test_takewhile(self):
2354 for s in (range(10), range(0), range(1000), (7,11), range(2000,2200,5)):
2355 for g in (G, I, Ig, S, L, R):
2356 tgt = []
2357 for elem in g(s):
2358 if not isEven(elem): break
2359 tgt.append(elem)
2360 self.assertEqual(list(takewhile(isEven, g(s))), tgt)
2361 self.assertRaises(TypeError, takewhile, isEven, X(s))
2362 self.assertRaises(TypeError, takewhile, isEven, N(s))
2363 self.assertRaises(ZeroDivisionError, list, takewhile(isEven, E(s)))
2364
2365 def test_dropwhile(self):
2366 for s in (range(10), range(0), range(1000), (7,11), range(2000,2200,5)):
2367 for g in (G, I, Ig, S, L, R):
2368 tgt = []
2369 for elem in g(s):
2370 if not tgt and isOdd(elem): continue
2371 tgt.append(elem)
2372 self.assertEqual(list(dropwhile(isOdd, g(s))), tgt)
2373 self.assertRaises(TypeError, dropwhile, isOdd, X(s))
2374 self.assertRaises(TypeError, dropwhile, isOdd, N(s))
2375 self.assertRaises(ZeroDivisionError, list, dropwhile(isOdd, E(s)))
2376
2377 def test_tee(self):
2378 for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
2379 for g in (G, I, Ig, S, L, R):
2380 it1, it2 = tee(g(s))
2381 self.assertEqual(list(it1), list(g(s)))
2382 self.assertEqual(list(it2), list(g(s)))
2383 self.assertRaises(TypeError, tee, X(s))
2384 self.assertRaises(TypeError, tee, N(s))
2385 self.assertRaises(ZeroDivisionError, list, tee(E(s))[0])
2386
2387 class LengthTransparency(unittest.TestCase):
2388
2389 def test_repeat(self):
2390 self.assertEqual(operator.length_hint(repeat(None, 50)), 50)
2391 self.assertEqual(operator.length_hint(repeat(None, 0)), 0)
2392 self.assertEqual(operator.length_hint(repeat(None), 12), 12)
2393
2394 def test_repeat_with_negative_times(self):
2395 self.assertEqual(operator.length_hint(repeat(None, -1)), 0)
2396 self.assertEqual(operator.length_hint(repeat(None, -2)), 0)
2397 self.assertEqual(operator.length_hint(repeat(None, times=-1)), 0)
2398 self.assertEqual(operator.length_hint(repeat(None, times=-2)), 0)
2399
2400 class RegressionTests(unittest.TestCase):
2401
2402 def test_sf_793826(self):
2403 # Fix Armin Rigo's successful efforts to wreak havoc
2404
2405 def mutatingtuple(tuple1, f, tuple2):
2406 # this builds a tuple t which is a copy of tuple1,
2407 # then calls f(t), then mutates t to be equal to tuple2
2408 # (needs len(tuple1) == len(tuple2)).
2409 def g(value, first=[1]):
2410 if first:
2411 del first[:]
2412 f(next(z))
2413 return value
2414 items = list(tuple2)
2415 items[1:1] = list(tuple1)
2416 gen = map(g, items)
2417 z = zip(*[gen]*len(tuple1))
2418 next(z)
2419
2420 def f(t):
2421 global T
2422 T = t
2423 first[:] = list(T)
2424
2425 first = []
2426 mutatingtuple((1,2,3), f, (4,5,6))
2427 second = list(T)
2428 self.assertEqual(first, second)
2429
2430
2431 def test_sf_950057(self):
2432 # Make sure that chain() and cycle() catch exceptions immediately
2433 # rather than when shifting between input sources
2434
2435 def gen1():
2436 hist.append(0)
2437 yield 1
2438 hist.append(1)
2439 raise AssertionError
2440 hist.append(2)
2441
2442 def gen2(x):
2443 hist.append(3)
2444 yield 2
2445 hist.append(4)
2446
2447 hist = []
2448 self.assertRaises(AssertionError, list, chain(gen1(), gen2(False)))
2449 self.assertEqual(hist, [0,1])
2450
2451 hist = []
2452 self.assertRaises(AssertionError, list, chain(gen1(), gen2(True)))
2453 self.assertEqual(hist, [0,1])
2454
2455 hist = []
2456 self.assertRaises(AssertionError, list, cycle(gen1()))
2457 self.assertEqual(hist, [0,1])
2458
2459 @support.skip_if_pgo_task
2460 @support.requires_resource('cpu')
2461 def test_long_chain_of_empty_iterables(self):
2462 # Make sure itertools.chain doesn't run into recursion limits when
2463 # dealing with long chains of empty iterables. Even with a high
2464 # number this would probably only fail in Py_DEBUG mode.
2465 it = chain.from_iterable(() for unused in range(10000000))
2466 with self.assertRaises(StopIteration):
2467 next(it)
2468
2469 def test_issue30347_1(self):
2470 def f(n):
2471 if n == 5:
2472 list(b)
2473 return n != 6
2474 for (k, b) in groupby(range(10), f):
2475 list(b) # shouldn't crash
2476
2477 def test_issue30347_2(self):
2478 class K:
2479 def __init__(self, v):
2480 pass
2481 def __eq__(self, other):
2482 nonlocal i
2483 i += 1
2484 if i == 1:
2485 next(g, None)
2486 return True
2487 i = 0
2488 g = next(groupby(range(10), K))[1]
2489 for j in range(2):
2490 next(g, None) # shouldn't crash
2491
2492
2493 class SubclassWithKwargsTest(unittest.TestCase):
2494 def test_keywords_in_subclass(self):
2495 # count is not subclassable...
2496 testcases = [
2497 (repeat, (1, 2), [1, 1]),
2498 (zip, ([1, 2], 'ab'), [(1, 'a'), (2, 'b')]),
2499 (filter, (None, [0, 1]), [1]),
2500 (filterfalse, (None, [0, 1]), [0]),
2501 (chain, ([1, 2], [3, 4]), [1, 2, 3]),
2502 (map, (str, [1, 2]), ['1', '2']),
2503 (starmap, (operator.pow, ((2, 3), (3, 2))), [8, 9]),
2504 (islice, ([1, 2, 3, 4], 1, 3), [2, 3]),
2505 (takewhile, (isEven, [2, 3, 4]), [2]),
2506 (dropwhile, (isEven, [2, 3, 4]), [3, 4]),
2507 (cycle, ([1, 2],), [1, 2, 1]),
2508 (compress, ('ABC', [1, 0, 1]), ['A', 'C']),
2509 ]
2510 for cls, args, result in testcases:
2511 with self.subTest(cls):
2512 class subclass(cls):
2513 pass
2514 u = subclass(*args)
2515 self.assertIs(type(u), subclass)
2516 self.assertEqual(list(islice(u, 0, 3)), result)
2517 with self.assertRaises(TypeError):
2518 subclass(*args, newarg=3)
2519
2520 for cls, args, result in testcases:
2521 # Constructors of repeat, zip, map, compress accept keyword arguments.
2522 # Their subclasses need overriding __new__ to support new
2523 # keyword arguments.
2524 if cls in [repeat, zip, map, compress]:
2525 continue
2526 with self.subTest(cls):
2527 class subclass_with_init(cls):
2528 def __init__(self, *args, newarg=None):
2529 self.newarg = newarg
2530 u = subclass_with_init(*args, newarg=3)
2531 self.assertIs(type(u), subclass_with_init)
2532 self.assertEqual(list(islice(u, 0, 3)), result)
2533 self.assertEqual(u.newarg, 3)
2534
2535 for cls, args, result in testcases:
2536 with self.subTest(cls):
2537 class subclass_with_new(cls):
2538 def __new__(cls, *args, newarg=None):
2539 self = super().__new__(cls, *args)
2540 self.newarg = newarg
2541 return self
2542 u = subclass_with_new(*args, newarg=3)
2543 self.assertIs(type(u), subclass_with_new)
2544 self.assertEqual(list(islice(u, 0, 3)), result)
2545 self.assertEqual(u.newarg, 3)
2546
2547
2548 @support.cpython_only
2549 class SizeofTest(unittest.TestCase):
2550 def setUp(self):
2551 self.ssize_t = struct.calcsize('n')
2552
2553 check_sizeof = support.check_sizeof
2554
2555 def test_product_sizeof(self):
2556 basesize = support.calcobjsize('3Pi')
2557 check = self.check_sizeof
2558 check(product('ab', '12'), basesize + 2 * self.ssize_t)
2559 check(product(*(('abc',) * 10)), basesize + 10 * self.ssize_t)
2560
2561 def test_combinations_sizeof(self):
2562 basesize = support.calcobjsize('3Pni')
2563 check = self.check_sizeof
2564 check(combinations('abcd', 3), basesize + 3 * self.ssize_t)
2565 check(combinations(range(10), 4), basesize + 4 * self.ssize_t)
2566
2567 def test_combinations_with_replacement_sizeof(self):
2568 cwr = combinations_with_replacement
2569 basesize = support.calcobjsize('3Pni')
2570 check = self.check_sizeof
2571 check(cwr('abcd', 3), basesize + 3 * self.ssize_t)
2572 check(cwr(range(10), 4), basesize + 4 * self.ssize_t)
2573
2574 def test_permutations_sizeof(self):
2575 basesize = support.calcobjsize('4Pni')
2576 check = self.check_sizeof
2577 check(permutations('abcd'),
2578 basesize + 4 * self.ssize_t + 4 * self.ssize_t)
2579 check(permutations('abcd', 3),
2580 basesize + 4 * self.ssize_t + 3 * self.ssize_t)
2581 check(permutations('abcde', 3),
2582 basesize + 5 * self.ssize_t + 3 * self.ssize_t)
2583 check(permutations(range(10), 4),
2584 basesize + 10 * self.ssize_t + 4 * self.ssize_t)
2585
2586
2587 def load_tests(loader, tests, pattern):
2588 tests.addTest(doctest.DocTestSuite(itertools))
2589 return tests
2590
2591
2592 if __name__ == "__main__":
2593 unittest.main()