1import unittest
2from test import support
3from itertools import *
4import weakref
5from decimal import Decimal
6from fractions import Fraction
7import operator
8import random
9import copy
10import pickle
11from functools import reduce
12import sys
13import struct
14maxsize = support.MAX_Py_ssize_t
15minsize = -maxsize-1
16
17def lzip(*args):
18    return list(zip(*args))
19
20def onearg(x):
21    'Test function of one argument'
22    return 2*x
23
24def errfunc(*args):
25    'Test function that raises an error'
26    raise ValueError
27
28def gen3():
29    'Non-restartable source sequence'
30    for i in (0, 1, 2):
31        yield i
32
33def isEven(x):
34    'Test predicate'
35    return x%2==0
36
37def isOdd(x):
38    'Test predicate'
39    return x%2==1
40
41def tupleize(*args):
42    return args
43
44def irange(n):
45    for i in range(n):
46        yield i
47
48class StopNow:
49    'Class emulating an empty iterable.'
50    def __iter__(self):
51        return self
52    def __next__(self):
53        raise StopIteration
54
55def take(n, seq):
56    'Convenience function for partially consuming a long of infinite iterable'
57    return list(islice(seq, n))
58
59def prod(iterable):
60    return reduce(operator.mul, iterable, 1)
61
62def fact(n):
63    'Factorial'
64    return prod(range(1, n+1))
65
66# root level methods for pickling ability
67def testR(r):
68    return r[0]
69
70def testR2(r):
71    return r[2]
72
73def underten(x):
74    return x<10
75
76picklecopiers = [lambda s, proto=proto: pickle.loads(pickle.dumps(s, proto))
77                 for proto in range(pickle.HIGHEST_PROTOCOL + 1)]
78
79class TestBasicOps(unittest.TestCase):
80
81    def pickletest(self, protocol, it, stop=4, take=1, compare=None):
82        """Test that an iterator is the same after pickling, also when part-consumed"""
83        def expand(it, i=0):
84            # Recursively expand iterables, within sensible bounds
85            if i > 10:
86                raise RuntimeError("infinite recursion encountered")
87            if isinstance(it, str):
88                return it
89            try:
90                l = list(islice(it, stop))
91            except TypeError:
92                return it # can't expand it
93            return [expand(e, i+1) for e in l]
94
95        # Test the initial copy against the original
96        dump = pickle.dumps(it, protocol)
97        i2 = pickle.loads(dump)
98        self.assertEqual(type(it), type(i2))
99        a, b = expand(it), expand(i2)
100        self.assertEqual(a, b)
101        if compare:
102            c = expand(compare)
103            self.assertEqual(a, c)
104
105        # Take from the copy, and create another copy and compare them.
106        i3 = pickle.loads(dump)
107        took = 0
108        try:
109            for i in range(take):
110                next(i3)
111                took += 1
112        except StopIteration:
113            pass #in case there is less data than 'take'
114        dump = pickle.dumps(i3, protocol)
115        i4 = pickle.loads(dump)
116        a, b = expand(i3), expand(i4)
117        self.assertEqual(a, b)
118        if compare:
119            c = expand(compare[took:])
120            self.assertEqual(a, c);
121
122    def test_accumulate(self):
123        self.assertEqual(list(accumulate(range(10))),               # one positional arg
124                          [0, 1, 3, 6, 10, 15, 21, 28, 36, 45])
125        self.assertEqual(list(accumulate(iterable=range(10))),      # kw arg
126                          [0, 1, 3, 6, 10, 15, 21, 28, 36, 45])
127        for typ in int, complex, Decimal, Fraction:                 # multiple types
128            self.assertEqual(
129                list(accumulate(map(typ, range(10)))),
130                list(map(typ, [0, 1, 3, 6, 10, 15, 21, 28, 36, 45])))
131        self.assertEqual(list(accumulate('abc')), ['a', 'ab', 'abc'])   # works with non-numeric
132        self.assertEqual(list(accumulate([])), [])                  # empty iterable
133        self.assertEqual(list(accumulate([7])), [7])                # iterable of length one
134        self.assertRaises(TypeError, accumulate, range(10), 5, 6)   # too many args
135        self.assertRaises(TypeError, accumulate)                    # too few args
136        self.assertRaises(TypeError, accumulate, x=range(10))       # unexpected kwd arg
137        self.assertRaises(TypeError, list, accumulate([1, []]))     # args that don't add
138
139        s = [2, 8, 9, 5, 7, 0, 3, 4, 1, 6]
140        self.assertEqual(list(accumulate(s, min)),
141                         [2, 2, 2, 2, 2, 0, 0, 0, 0, 0])
142        self.assertEqual(list(accumulate(s, max)),
143                         [2, 8, 9, 9, 9, 9, 9, 9, 9, 9])
144        self.assertEqual(list(accumulate(s, operator.mul)),
145                         [2, 16, 144, 720, 5040, 0, 0, 0, 0, 0])
146        with self.assertRaises(TypeError):
147            list(accumulate(s, chr))                                # unary-operation
148        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
149            self.pickletest(proto, accumulate(range(10)))           # test pickling
150
151    def test_chain(self):
152
153        def chain2(*iterables):
154            'Pure python version in the docs'
155            for it in iterables:
156                for element in it:
157                    yield element
158
159        for c in (chain, chain2):
160            self.assertEqual(list(c('abc', 'def')), list('abcdef'))
161            self.assertEqual(list(c('abc')), list('abc'))
162            self.assertEqual(list(c('')), [])
163            self.assertEqual(take(4, c('abc', 'def')), list('abcd'))
164            self.assertRaises(TypeError, list,c(2, 3))
165
166    def test_chain_from_iterable(self):
167        self.assertEqual(list(chain.from_iterable(['abc', 'def'])), list('abcdef'))
168        self.assertEqual(list(chain.from_iterable(['abc'])), list('abc'))
169        self.assertEqual(list(chain.from_iterable([''])), [])
170        self.assertEqual(take(4, chain.from_iterable(['abc', 'def'])), list('abcd'))
171        self.assertRaises(TypeError, list, chain.from_iterable([2, 3]))
172
173    def test_chain_reducible(self):
174        for oper in [copy.deepcopy] + picklecopiers:
175            it = chain('abc', 'def')
176            self.assertEqual(list(oper(it)), list('abcdef'))
177            self.assertEqual(next(it), 'a')
178            self.assertEqual(list(oper(it)), list('bcdef'))
179
180            self.assertEqual(list(oper(chain(''))), [])
181            self.assertEqual(take(4, oper(chain('abc', 'def'))), list('abcd'))
182            self.assertRaises(TypeError, list, oper(chain(2, 3)))
183        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
184            self.pickletest(proto, chain('abc', 'def'), compare=list('abcdef'))
185
186    def test_chain_setstate(self):
187        self.assertRaises(TypeError, chain().__setstate__, ())
188        self.assertRaises(TypeError, chain().__setstate__, [])
189        self.assertRaises(TypeError, chain().__setstate__, 0)
190        self.assertRaises(TypeError, chain().__setstate__, ([],))
191        self.assertRaises(TypeError, chain().__setstate__, (iter([]), []))
192        it = chain()
193        it.__setstate__((iter(['abc', 'def']),))
194        self.assertEqual(list(it), ['a', 'b', 'c', 'd', 'e', 'f'])
195        it = chain()
196        it.__setstate__((iter(['abc', 'def']), iter(['ghi'])))
197        self.assertEqual(list(it), ['ghi', 'a', 'b', 'c', 'd', 'e', 'f'])
198
199    def test_combinations(self):
200        self.assertRaises(TypeError, combinations, 'abc')       # missing r argument
201        self.assertRaises(TypeError, combinations, 'abc', 2, 1) # too many arguments
202        self.assertRaises(TypeError, combinations, None)        # pool is not iterable
203        self.assertRaises(ValueError, combinations, 'abc', -2)  # r is negative
204
205        for op in [lambda a:a] + picklecopiers:
206            self.assertEqual(list(op(combinations('abc', 32))), [])     # r > n
207
208            self.assertEqual(list(op(combinations('ABCD', 2))),
209                             [('A','B'), ('A','C'), ('A','D'), ('B','C'), ('B','D'), ('C','D')])
210            testIntermediate = combinations('ABCD', 2)
211            next(testIntermediate)
212            self.assertEqual(list(op(testIntermediate)),
213                             [('A','C'), ('A','D'), ('B','C'), ('B','D'), ('C','D')])
214
215            self.assertEqual(list(op(combinations(range(4), 3))),
216                             [(0,1,2), (0,1,3), (0,2,3), (1,2,3)])
217            testIntermediate = combinations(range(4), 3)
218            next(testIntermediate)
219            self.assertEqual(list(op(testIntermediate)),
220                             [(0,1,3), (0,2,3), (1,2,3)])
221
222
223        def combinations1(iterable, r):
224            'Pure python version shown in the docs'
225            pool = tuple(iterable)
226            n = len(pool)
227            if r > n:
228                return
229            indices = list(range(r))
230            yield tuple(pool[i] for i in indices)
231            while 1:
232                for i in reversed(range(r)):
233                    if indices[i] != i + n - r:
234                        break
235                else:
236                    return
237                indices[i] += 1
238                for j in range(i+1, r):
239                    indices[j] = indices[j-1] + 1
240                yield tuple(pool[i] for i in indices)
241
242        def combinations2(iterable, r):
243            'Pure python version shown in the docs'
244            pool = tuple(iterable)
245            n = len(pool)
246            for indices in permutations(range(n), r):
247                if sorted(indices) == list(indices):
248                    yield tuple(pool[i] for i in indices)
249
250        def combinations3(iterable, r):
251            'Pure python version from cwr()'
252            pool = tuple(iterable)
253            n = len(pool)
254            for indices in combinations_with_replacement(range(n), r):
255                if len(set(indices)) == r:
256                    yield tuple(pool[i] for i in indices)
257
258        for n in range(7):
259            values = [5*x-12 for x in range(n)]
260            for r in range(n+2):
261                result = list(combinations(values, r))
262                self.assertEqual(len(result), 0 if r>n else fact(n) / fact(r) / fact(n-r)) # right number of combs
263                self.assertEqual(len(result), len(set(result)))         # no repeats
264                self.assertEqual(result, sorted(result))                # lexicographic order
265                for c in result:
266                    self.assertEqual(len(c), r)                         # r-length combinations
267                    self.assertEqual(len(set(c)), r)                    # no duplicate elements
268                    self.assertEqual(list(c), sorted(c))                # keep original ordering
269                    self.assertTrue(all(e in values for e in c))           # elements taken from input iterable
270                    self.assertEqual(list(c),
271                                     [e for e in values if e in c])      # comb is a subsequence of the input iterable
272                self.assertEqual(result, list(combinations1(values, r))) # matches first pure python version
273                self.assertEqual(result, list(combinations2(values, r))) # matches second pure python version
274                self.assertEqual(result, list(combinations3(values, r))) # matches second pure python version
275
276                for proto in range(pickle.HIGHEST_PROTOCOL + 1):
277                    self.pickletest(proto, combinations(values, r))      # test pickling
278
279    @support.bigaddrspacetest
280    def test_combinations_overflow(self):
281        with self.assertRaises((OverflowError, MemoryError)):
282            combinations("AA", 2**29)
283
284        # Test implementation detail:  tuple re-use
285    @support.impl_detail("tuple reuse is specific to CPython")
286    def test_combinations_tuple_reuse(self):
287        self.assertEqual(len(set(map(id, combinations('abcde', 3)))), 1)
288        self.assertNotEqual(len(set(map(id, list(combinations('abcde', 3))))), 1)
289
290    def test_combinations_with_replacement(self):
291        cwr = combinations_with_replacement
292        self.assertRaises(TypeError, cwr, 'abc')       # missing r argument
293        self.assertRaises(TypeError, cwr, 'abc', 2, 1) # too many arguments
294        self.assertRaises(TypeError, cwr, None)        # pool is not iterable
295        self.assertRaises(ValueError, cwr, 'abc', -2)  # r is negative
296
297        for op in [lambda a:a] + picklecopiers:
298            self.assertEqual(list(op(cwr('ABC', 2))),
299                             [('A','A'), ('A','B'), ('A','C'), ('B','B'), ('B','C'), ('C','C')])
300            testIntermediate = cwr('ABC', 2)
301            next(testIntermediate)
302            self.assertEqual(list(op(testIntermediate)),
303                             [('A','B'), ('A','C'), ('B','B'), ('B','C'), ('C','C')])
304
305
306        def cwr1(iterable, r):
307            'Pure python version shown in the docs'
308            # number items returned:  (n+r-1)! / r! / (n-1)! when n>0
309            pool = tuple(iterable)
310            n = len(pool)
311            if not n and r:
312                return
313            indices = [0] * r
314            yield tuple(pool[i] for i in indices)
315            while 1:
316                for i in reversed(range(r)):
317                    if indices[i] != n - 1:
318                        break
319                else:
320                    return
321                indices[i:] = [indices[i] + 1] * (r - i)
322                yield tuple(pool[i] for i in indices)
323
324        def cwr2(iterable, r):
325            'Pure python version shown in the docs'
326            pool = tuple(iterable)
327            n = len(pool)
328            for indices in product(range(n), repeat=r):
329                if sorted(indices) == list(indices):
330                    yield tuple(pool[i] for i in indices)
331
332        def numcombs(n, r):
333            if not n:
334                return 0 if r else 1
335            return fact(n+r-1) / fact(r)/ fact(n-1)
336
337        for n in range(7):
338            values = [5*x-12 for x in range(n)]
339            for r in range(n+2):
340                result = list(cwr(values, r))
341
342                self.assertEqual(len(result), numcombs(n, r))           # right number of combs
343                self.assertEqual(len(result), len(set(result)))         # no repeats
344                self.assertEqual(result, sorted(result))                # lexicographic order
345
346                regular_combs = list(combinations(values, r))           # compare to combs without replacement
347                if n == 0 or r <= 1:
348                    self.assertEqual(result, regular_combs)            # cases that should be identical
349                else:
350                    self.assertTrue(set(result) >= set(regular_combs))     # rest should be supersets of regular combs
351
352                for c in result:
353                    self.assertEqual(len(c), r)                         # r-length combinations
354                    noruns = [k for k,v in groupby(c)]                  # combo without consecutive repeats
355                    self.assertEqual(len(noruns), len(set(noruns)))     # no repeats other than consecutive
356                    self.assertEqual(list(c), sorted(c))                # keep original ordering
357                    self.assertTrue(all(e in values for e in c))           # elements taken from input iterable
358                    self.assertEqual(noruns,
359                                     [e for e in values if e in c])     # comb is a subsequence of the input iterable
360                self.assertEqual(result, list(cwr1(values, r)))         # matches first pure python version
361                self.assertEqual(result, list(cwr2(values, r)))         # matches second pure python version
362
363                for proto in range(pickle.HIGHEST_PROTOCOL + 1):
364                    self.pickletest(proto, cwr(values,r))               # test pickling
365
366    @support.bigaddrspacetest
367    def test_combinations_with_replacement_overflow(self):
368        with self.assertRaises((OverflowError, MemoryError)):
369            combinations_with_replacement("AA", 2**30)
370
371        # Test implementation detail:  tuple re-use
372    @support.impl_detail("tuple reuse is specific to CPython")
373    def test_combinations_with_replacement_tuple_reuse(self):
374        cwr = combinations_with_replacement
375        self.assertEqual(len(set(map(id, cwr('abcde', 3)))), 1)
376        self.assertNotEqual(len(set(map(id, list(cwr('abcde', 3))))), 1)
377
378    def test_permutations(self):
379        self.assertRaises(TypeError, permutations)              # too few arguments
380        self.assertRaises(TypeError, permutations, 'abc', 2, 1) # too many arguments
381        self.assertRaises(TypeError, permutations, None)        # pool is not iterable
382        self.assertRaises(ValueError, permutations, 'abc', -2)  # r is negative
383        self.assertEqual(list(permutations('abc', 32)), [])     # r > n
384        self.assertRaises(TypeError, permutations, 'abc', 's')  # r is not an int or None
385        self.assertEqual(list(permutations(range(3), 2)),
386                                           [(0,1), (0,2), (1,0), (1,2), (2,0), (2,1)])
387
388        def permutations1(iterable, r=None):
389            'Pure python version shown in the docs'
390            pool = tuple(iterable)
391            n = len(pool)
392            r = n if r is None else r
393            if r > n:
394                return
395            indices = list(range(n))
396            cycles = list(range(n-r+1, n+1))[::-1]
397            yield tuple(pool[i] for i in indices[:r])
398            while n:
399                for i in reversed(range(r)):
400                    cycles[i] -= 1
401                    if cycles[i] == 0:
402                        indices[i:] = indices[i+1:] + indices[i:i+1]
403                        cycles[i] = n - i
404                    else:
405                        j = cycles[i]
406                        indices[i], indices[-j] = indices[-j], indices[i]
407                        yield tuple(pool[i] for i in indices[:r])
408                        break
409                else:
410                    return
411
412        def permutations2(iterable, r=None):
413            'Pure python version shown in the docs'
414            pool = tuple(iterable)
415            n = len(pool)
416            r = n if r is None else r
417            for indices in product(range(n), repeat=r):
418                if len(set(indices)) == r:
419                    yield tuple(pool[i] for i in indices)
420
421        for n in range(7):
422            values = [5*x-12 for x in range(n)]
423            for r in range(n+2):
424                result = list(permutations(values, r))
425                self.assertEqual(len(result), 0 if r>n else fact(n) / fact(n-r))      # right number of perms
426                self.assertEqual(len(result), len(set(result)))         # no repeats
427                self.assertEqual(result, sorted(result))                # lexicographic order
428                for p in result:
429                    self.assertEqual(len(p), r)                         # r-length permutations
430                    self.assertEqual(len(set(p)), r)                    # no duplicate elements
431                    self.assertTrue(all(e in values for e in p))           # elements taken from input iterable
432                self.assertEqual(result, list(permutations1(values, r))) # matches first pure python version
433                self.assertEqual(result, list(permutations2(values, r))) # matches second pure python version
434                if r == n:
435                    self.assertEqual(result, list(permutations(values, None))) # test r as None
436                    self.assertEqual(result, list(permutations(values)))       # test default r
437
438                for proto in range(pickle.HIGHEST_PROTOCOL + 1):
439                    self.pickletest(proto, permutations(values, r))     # test pickling
440
441    @support.bigaddrspacetest
442    def test_permutations_overflow(self):
443        with self.assertRaises((OverflowError, MemoryError)):
444            permutations("A", 2**30)
445
446    @support.impl_detail("tuple reuse is specific to CPython")
447    def test_permutations_tuple_reuse(self):
448        self.assertEqual(len(set(map(id, permutations('abcde', 3)))), 1)
449        self.assertNotEqual(len(set(map(id, list(permutations('abcde', 3))))), 1)
450
451    def test_combinatorics(self):
452        # Test relationships between product(), permutations(),
453        # combinations() and combinations_with_replacement().
454
455        for n in range(6):
456            s = 'ABCDEFG'[:n]
457            for r in range(8):
458                prod = list(product(s, repeat=r))
459                cwr = list(combinations_with_replacement(s, r))
460                perm = list(permutations(s, r))
461                comb = list(combinations(s, r))
462
463                # Check size
464                self.assertEqual(len(prod), n**r)
465                self.assertEqual(len(cwr), (fact(n+r-1) / fact(r)/ fact(n-1)) if n else (not r))
466                self.assertEqual(len(perm), 0 if r>n else fact(n) / fact(n-r))
467                self.assertEqual(len(comb), 0 if r>n else fact(n) / fact(r) / fact(n-r))
468
469                # Check lexicographic order without repeated tuples
470                self.assertEqual(prod, sorted(set(prod)))
471                self.assertEqual(cwr, sorted(set(cwr)))
472                self.assertEqual(perm, sorted(set(perm)))
473                self.assertEqual(comb, sorted(set(comb)))
474
475                # Check interrelationships
476                self.assertEqual(cwr, [t for t in prod if sorted(t)==list(t)]) # cwr: prods which are sorted
477                self.assertEqual(perm, [t for t in prod if len(set(t))==r])    # perm: prods with no dups
478                self.assertEqual(comb, [t for t in perm if sorted(t)==list(t)]) # comb: perms that are sorted
479                self.assertEqual(comb, [t for t in cwr if len(set(t))==r])      # comb: cwrs without dups
480                self.assertEqual(comb, list(filter(set(cwr).__contains__, perm)))     # comb: perm that is a cwr
481                self.assertEqual(comb, list(filter(set(perm).__contains__, cwr)))     # comb: cwr that is a perm
482                self.assertEqual(comb, sorted(set(cwr) & set(perm)))            # comb: both a cwr and a perm
483
484    def test_compress(self):
485        self.assertEqual(list(compress(data='ABCDEF', selectors=[1,0,1,0,1,1])), list('ACEF'))
486        self.assertEqual(list(compress('ABCDEF', [1,0,1,0,1,1])), list('ACEF'))
487        self.assertEqual(list(compress('ABCDEF', [0,0,0,0,0,0])), list(''))
488        self.assertEqual(list(compress('ABCDEF', [1,1,1,1,1,1])), list('ABCDEF'))
489        self.assertEqual(list(compress('ABCDEF', [1,0,1])), list('AC'))
490        self.assertEqual(list(compress('ABC', [0,1,1,1,1,1])), list('BC'))
491        n = 10000
492        data = chain.from_iterable(repeat(range(6), n))
493        selectors = chain.from_iterable(repeat((0, 1)))
494        self.assertEqual(list(compress(data, selectors)), [1,3,5] * n)
495        self.assertRaises(TypeError, compress, None, range(6))      # 1st arg not iterable
496        self.assertRaises(TypeError, compress, range(6), None)      # 2nd arg not iterable
497        self.assertRaises(TypeError, compress, range(6))            # too few args
498        self.assertRaises(TypeError, compress, range(6), None)      # too many args
499
500        # check copy, deepcopy, pickle
501        for op in [lambda a:copy.copy(a), lambda a:copy.deepcopy(a)] + picklecopiers:
502            for data, selectors, result1, result2 in [
503                ('ABCDEF', [1,0,1,0,1,1], 'ACEF', 'CEF'),
504                ('ABCDEF', [0,0,0,0,0,0], '', ''),
505                ('ABCDEF', [1,1,1,1,1,1], 'ABCDEF', 'BCDEF'),
506                ('ABCDEF', [1,0,1], 'AC', 'C'),
507                ('ABC', [0,1,1,1,1,1], 'BC', 'C'),
508                ]:
509
510                self.assertEqual(list(op(compress(data=data, selectors=selectors))), list(result1))
511                self.assertEqual(list(op(compress(data, selectors))), list(result1))
512                testIntermediate = compress(data, selectors)
513                if result1:
514                    next(testIntermediate)
515                    self.assertEqual(list(op(testIntermediate)), list(result2))
516
517
518    def test_count(self):
519        self.assertEqual(lzip('abc',count()), [('a', 0), ('b', 1), ('c', 2)])
520        self.assertEqual(lzip('abc',count(3)), [('a', 3), ('b', 4), ('c', 5)])
521        self.assertEqual(take(2, lzip('abc',count(3))), [('a', 3), ('b', 4)])
522        self.assertEqual(take(2, zip('abc',count(-1))), [('a', -1), ('b', 0)])
523        self.assertEqual(take(2, zip('abc',count(-3))), [('a', -3), ('b', -2)])
524        self.assertRaises(TypeError, count, 2, 3, 4)
525        self.assertRaises(TypeError, count, 'a')
526        self.assertEqual(take(10, count(maxsize-5)),
527                         list(range(maxsize-5, maxsize+5)))
528        self.assertEqual(take(10, count(-maxsize-5)),
529                         list(range(-maxsize-5, -maxsize+5)))
530        self.assertEqual(take(3, count(3.25)), [3.25, 4.25, 5.25])
531        self.assertEqual(take(3, count(3.25-4j)), [3.25-4j, 4.25-4j, 5.25-4j])
532        self.assertEqual(take(3, count(Decimal('1.1'))),
533                         [Decimal('1.1'), Decimal('2.1'), Decimal('3.1')])
534        self.assertEqual(take(3, count(Fraction(2, 3))),
535                         [Fraction(2, 3), Fraction(5, 3), Fraction(8, 3)])
536        BIGINT = 1<<1000
537        self.assertEqual(take(3, count(BIGINT)), [BIGINT, BIGINT+1, BIGINT+2])
538        c = count(3)
539        self.assertEqual(repr(c), 'count(3)')
540        next(c)
541        self.assertEqual(repr(c), 'count(4)')
542        c = count(-9)
543        self.assertEqual(repr(c), 'count(-9)')
544        next(c)
545        self.assertEqual(next(c), -8)
546        self.assertEqual(repr(count(10.25)), 'count(10.25)')
547        self.assertEqual(repr(count(10.0)), 'count(10.0)')
548        self.assertEqual(type(next(count(10.0))), float)
549        for i in (-sys.maxsize-5, -sys.maxsize+5 ,-10, -1, 0, 10, sys.maxsize-5, sys.maxsize+5):
550            # Test repr
551            r1 = repr(count(i))
552            r2 = 'count(%r)'.__mod__(i)
553            self.assertEqual(r1, r2)
554
555        # check copy, deepcopy, pickle
556        for value in -3, 3, maxsize-5, maxsize+5:
557            c = count(value)
558            self.assertEqual(next(copy.copy(c)), value)
559            self.assertEqual(next(copy.deepcopy(c)), value)
560            for proto in range(pickle.HIGHEST_PROTOCOL + 1):
561                self.pickletest(proto, count(value))
562
563        #check proper internal error handling for large "step' sizes
564        count(1, maxsize+5); sys.exc_info()
565
566    def test_count_with_stride(self):
567        self.assertEqual(lzip('abc',count(2,3)), [('a', 2), ('b', 5), ('c', 8)])
568        self.assertEqual(lzip('abc',count(start=2,step=3)),
569                         [('a', 2), ('b', 5), ('c', 8)])
570        self.assertEqual(lzip('abc',count(step=-1)),
571                         [('a', 0), ('b', -1), ('c', -2)])
572        self.assertRaises(TypeError, count, 'a', 'b')
573        self.assertEqual(lzip('abc',count(2,0)), [('a', 2), ('b', 2), ('c', 2)])
574        self.assertEqual(lzip('abc',count(2,1)), [('a', 2), ('b', 3), ('c', 4)])
575        self.assertEqual(lzip('abc',count(2,3)), [('a', 2), ('b', 5), ('c', 8)])
576        self.assertEqual(take(20, count(maxsize-15, 3)), take(20, range(maxsize-15, maxsize+100, 3)))
577        self.assertEqual(take(20, count(-maxsize-15, 3)), take(20, range(-maxsize-15,-maxsize+100, 3)))
578        self.assertEqual(take(3, count(10, maxsize+5)),
579                         list(range(10, 10+3*(maxsize+5), maxsize+5)))
580        self.assertEqual(take(3, count(2, 1.25)), [2, 3.25, 4.5])
581        self.assertEqual(take(3, count(2, 3.25-4j)), [2, 5.25-4j, 8.5-8j])
582        self.assertEqual(take(3, count(Decimal('1.1'), Decimal('.1'))),
583                         [Decimal('1.1'), Decimal('1.2'), Decimal('1.3')])
584        self.assertEqual(take(3, count(Fraction(2,3), Fraction(1,7))),
585                         [Fraction(2,3), Fraction(17,21), Fraction(20,21)])
586        BIGINT = 1<<1000
587        self.assertEqual(take(3, count(step=BIGINT)), [0, BIGINT, 2*BIGINT])
588        self.assertEqual(repr(take(3, count(10, 2.5))), repr([10, 12.5, 15.0]))
589        c = count(3, 5)
590        self.assertEqual(repr(c), 'count(3, 5)')
591        next(c)
592        self.assertEqual(repr(c), 'count(8, 5)')
593        c = count(-9, 0)
594        self.assertEqual(repr(c), 'count(-9, 0)')
595        next(c)
596        self.assertEqual(repr(c), 'count(-9, 0)')
597        c = count(-9, -3)
598        self.assertEqual(repr(c), 'count(-9, -3)')
599        next(c)
600        self.assertEqual(repr(c), 'count(-12, -3)')
601        self.assertEqual(repr(c), 'count(-12, -3)')
602        self.assertEqual(repr(count(10.5, 1.25)), 'count(10.5, 1.25)')
603        self.assertEqual(repr(count(10.5, 1)), 'count(10.5)')           # suppress step=1 when it's an int
604        self.assertEqual(repr(count(10.5, 1.00)), 'count(10.5, 1.0)')   # do show float values lilke 1.0
605        self.assertEqual(repr(count(10, 1.00)), 'count(10, 1.0)')
606        c = count(10, 1.0)
607        self.assertEqual(type(next(c)), int)
608        self.assertEqual(type(next(c)), float)
609        for i in (-sys.maxsize-5, -sys.maxsize+5 ,-10, -1, 0, 10, sys.maxsize-5, sys.maxsize+5):
610            for j in  (-sys.maxsize-5, -sys.maxsize+5 ,-10, -1, 0, 1, 10, sys.maxsize-5, sys.maxsize+5):
611                # Test repr
612                r1 = repr(count(i, j))
613                if j == 1:
614                    r2 = ('count(%r)' % i)
615                else:
616                    r2 = ('count(%r, %r)' % (i, j))
617                self.assertEqual(r1, r2)
618                for proto in range(pickle.HIGHEST_PROTOCOL + 1):
619                    self.pickletest(proto, count(i, j))
620
621    def test_cycle(self):
622        self.assertEqual(take(10, cycle('abc')), list('abcabcabca'))
623        self.assertEqual(list(cycle('')), [])
624        self.assertRaises(TypeError, cycle)
625        self.assertRaises(TypeError, cycle, 5)
626        self.assertEqual(list(islice(cycle(gen3()),10)), [0,1,2,0,1,2,0,1,2,0])
627
628        # check copy, deepcopy, pickle
629        c = cycle('abc')
630        self.assertEqual(next(c), 'a')
631        #simple copy currently not supported, because __reduce__ returns
632        #an internal iterator
633        #self.assertEqual(take(10, copy.copy(c)), list('bcabcabcab'))
634        self.assertEqual(take(10, copy.deepcopy(c)), list('bcabcabcab'))
635        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
636            self.assertEqual(take(10, pickle.loads(pickle.dumps(c, proto))),
637                             list('bcabcabcab'))
638            next(c)
639            self.assertEqual(take(10, pickle.loads(pickle.dumps(c, proto))),
640                             list('cabcabcabc'))
641            next(c)
642            next(c)
643        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
644            self.pickletest(proto, cycle('abc'))
645
646        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
647            # test with partial consumed input iterable
648            it = iter('abcde')
649            c = cycle(it)
650            _ = [next(c) for i in range(2)]      # consume 2 of 5 inputs
651            p = pickle.dumps(c, proto)
652            d = pickle.loads(p)                  # rebuild the cycle object
653            self.assertEqual(take(20, d), list('cdeabcdeabcdeabcdeab'))
654
655            # test with completely consumed input iterable
656            it = iter('abcde')
657            c = cycle(it)
658            _ = [next(c) for i in range(7)]      # consume 7 of 5 inputs
659            p = pickle.dumps(c, proto)
660            d = pickle.loads(p)                  # rebuild the cycle object
661            self.assertEqual(take(20, d), list('cdeabcdeabcdeabcdeab'))
662
663    def test_cycle_setstate(self):
664        # Verify both modes for restoring state
665
666        # Mode 0 is efficient.  It uses an incompletely consumed input
667        # iterator to build a cycle object and then passes in state with
668        # a list of previously consumed values.  There is no data
669        # overlap between the two.
670        c = cycle('defg')
671        c.__setstate__((list('abc'), 0))
672        self.assertEqual(take(20, c), list('defgabcdefgabcdefgab'))
673
674        # Mode 1 is inefficient.  It starts with a cycle object built
675        # from an iterator over the remaining elements in a partial
676        # cycle and then passes in state with all of the previously
677        # seen values (this overlaps values included in the iterator).
678        c = cycle('defg')
679        c.__setstate__((list('abcdefg'), 1))
680        self.assertEqual(take(20, c), list('defgabcdefgabcdefgab'))
681
682        # The first argument to setstate needs to be a tuple
683        with self.assertRaises(TypeError):
684            cycle('defg').__setstate__([list('abcdefg'), 0])
685
686        # The first argument in the setstate tuple must be a list
687        with self.assertRaises(TypeError):
688            c = cycle('defg')
689            c.__setstate__((tuple('defg'), 0))
690        take(20, c)
691
692        # The second argument in the setstate tuple must be an int
693        with self.assertRaises(TypeError):
694            cycle('defg').__setstate__((list('abcdefg'), 'x'))
695
696        self.assertRaises(TypeError, cycle('').__setstate__, ())
697        self.assertRaises(TypeError, cycle('').__setstate__, ([],))
698
699    def test_groupby(self):
700        # Check whether it accepts arguments correctly
701        self.assertEqual([], list(groupby([])))
702        self.assertEqual([], list(groupby([], key=id)))
703        self.assertRaises(TypeError, list, groupby('abc', []))
704        self.assertRaises(TypeError, groupby, None)
705        self.assertRaises(TypeError, groupby, 'abc', lambda x:x, 10)
706
707        # Check normal input
708        s = [(0, 10, 20), (0, 11,21), (0,12,21), (1,13,21), (1,14,22),
709             (2,15,22), (3,16,23), (3,17,23)]
710        dup = []
711        for k, g in groupby(s, lambda r:r[0]):
712            for elem in g:
713                self.assertEqual(k, elem[0])
714                dup.append(elem)
715        self.assertEqual(s, dup)
716
717        # Check normal pickled
718        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
719            dup = []
720            for k, g in pickle.loads(pickle.dumps(groupby(s, testR), proto)):
721                for elem in g:
722                    self.assertEqual(k, elem[0])
723                    dup.append(elem)
724            self.assertEqual(s, dup)
725
726        # Check nested case
727        dup = []
728        for k, g in groupby(s, testR):
729            for ik, ig in groupby(g, testR2):
730                for elem in ig:
731                    self.assertEqual(k, elem[0])
732                    self.assertEqual(ik, elem[2])
733                    dup.append(elem)
734        self.assertEqual(s, dup)
735
736        # Check nested and pickled
737        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
738            dup = []
739            for k, g in pickle.loads(pickle.dumps(groupby(s, testR), proto)):
740                for ik, ig in pickle.loads(pickle.dumps(groupby(g, testR2), proto)):
741                    for elem in ig:
742                        self.assertEqual(k, elem[0])
743                        self.assertEqual(ik, elem[2])
744                        dup.append(elem)
745            self.assertEqual(s, dup)
746
747
748        # Check case where inner iterator is not used
749        keys = [k for k, g in groupby(s, testR)]
750        expectedkeys = set([r[0] for r in s])
751        self.assertEqual(set(keys), expectedkeys)
752        self.assertEqual(len(keys), len(expectedkeys))
753
754        # Exercise pipes and filters style
755        s = 'abracadabra'
756        # sort s | uniq
757        r = [k for k, g in groupby(sorted(s))]
758        self.assertEqual(r, ['a', 'b', 'c', 'd', 'r'])
759        # sort s | uniq -d
760        r = [k for k, g in groupby(sorted(s)) if list(islice(g,1,2))]
761        self.assertEqual(r, ['a', 'b', 'r'])
762        # sort s | uniq -c
763        r = [(len(list(g)), k) for k, g in groupby(sorted(s))]
764        self.assertEqual(r, [(5, 'a'), (2, 'b'), (1, 'c'), (1, 'd'), (2, 'r')])
765        # sort s | uniq -c | sort -rn | head -3
766        r = sorted([(len(list(g)) , k) for k, g in groupby(sorted(s))], reverse=True)[:3]
767        self.assertEqual(r, [(5, 'a'), (2, 'r'), (2, 'b')])
768
769        # iter.__next__ failure
770        class ExpectedError(Exception):
771            pass
772        def delayed_raise(n=0):
773            for i in range(n):
774                yield 'yo'
775            raise ExpectedError
776        def gulp(iterable, keyp=None, func=list):
777            return [func(g) for k, g in groupby(iterable, keyp)]
778
779        # iter.__next__ failure on outer object
780        self.assertRaises(ExpectedError, gulp, delayed_raise(0))
781        # iter.__next__ failure on inner object
782        self.assertRaises(ExpectedError, gulp, delayed_raise(1))
783
784        # __eq__ failure
785        class DummyCmp:
786            def __eq__(self, dst):
787                raise ExpectedError
788        s = [DummyCmp(), DummyCmp(), None]
789
790        # __eq__ failure on outer object
791        self.assertRaises(ExpectedError, gulp, s, func=id)
792        # __eq__ failure on inner object
793        self.assertRaises(ExpectedError, gulp, s)
794
795        # keyfunc failure
796        def keyfunc(obj):
797            if keyfunc.skip > 0:
798                keyfunc.skip -= 1
799                return obj
800            else:
801                raise ExpectedError
802
803        # keyfunc failure on outer object
804        keyfunc.skip = 0
805        self.assertRaises(ExpectedError, gulp, [None], keyfunc)
806        keyfunc.skip = 1
807        self.assertRaises(ExpectedError, gulp, [None, None], keyfunc)
808
809    def test_filter(self):
810        self.assertEqual(list(filter(isEven, range(6))), [0,2,4])
811        self.assertEqual(list(filter(None, [0,1,0,2,0])), [1,2])
812        self.assertEqual(list(filter(bool, [0,1,0,2,0])), [1,2])
813        self.assertEqual(take(4, filter(isEven, count())), [0,2,4,6])
814        self.assertRaises(TypeError, filter)
815        self.assertRaises(TypeError, filter, lambda x:x)
816        self.assertRaises(TypeError, filter, lambda x:x, range(6), 7)
817        self.assertRaises(TypeError, filter, isEven, 3)
818        self.assertRaises(TypeError, next, filter(range(6), range(6)))
819
820        # check copy, deepcopy, pickle
821        ans = [0,2,4]
822
823        c = filter(isEven, range(6))
824        self.assertEqual(list(copy.copy(c)), ans)
825        c = filter(isEven, range(6))
826        self.assertEqual(list(copy.deepcopy(c)), ans)
827        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
828            c = filter(isEven, range(6))
829            self.assertEqual(list(pickle.loads(pickle.dumps(c, proto))), ans)
830            next(c)
831            self.assertEqual(list(pickle.loads(pickle.dumps(c, proto))), ans[1:])
832        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
833            c = filter(isEven, range(6))
834            self.pickletest(proto, c)
835
836    def test_filterfalse(self):
837        self.assertEqual(list(filterfalse(isEven, range(6))), [1,3,5])
838        self.assertEqual(list(filterfalse(None, [0,1,0,2,0])), [0,0,0])
839        self.assertEqual(list(filterfalse(bool, [0,1,0,2,0])), [0,0,0])
840        self.assertEqual(take(4, filterfalse(isEven, count())), [1,3,5,7])
841        self.assertRaises(TypeError, filterfalse)
842        self.assertRaises(TypeError, filterfalse, lambda x:x)
843        self.assertRaises(TypeError, filterfalse, lambda x:x, range(6), 7)
844        self.assertRaises(TypeError, filterfalse, isEven, 3)
845        self.assertRaises(TypeError, next, filterfalse(range(6), range(6)))
846        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
847            self.pickletest(proto, filterfalse(isEven, range(6)))
848
849    def test_zip(self):
850        # XXX This is rather silly now that builtin zip() calls zip()...
851        ans = [(x,y) for x, y in zip('abc',count())]
852        self.assertEqual(ans, [('a', 0), ('b', 1), ('c', 2)])
853        self.assertEqual(list(zip('abc', range(6))), lzip('abc', range(6)))
854        self.assertEqual(list(zip('abcdef', range(3))), lzip('abcdef', range(3)))
855        self.assertEqual(take(3,zip('abcdef', count())), lzip('abcdef', range(3)))
856        self.assertEqual(list(zip('abcdef')), lzip('abcdef'))
857        self.assertEqual(list(zip()), lzip())
858        self.assertRaises(TypeError, zip, 3)
859        self.assertRaises(TypeError, zip, range(3), 3)
860        self.assertEqual([tuple(list(pair)) for pair in zip('abc', 'def')],
861                         lzip('abc', 'def'))
862        self.assertEqual([pair for pair in zip('abc', 'def')],
863                         lzip('abc', 'def'))
864
865    @support.impl_detail("tuple reuse is specific to CPython")
866    def test_zip_tuple_reuse(self):
867        ids = list(map(id, zip('abc', 'def')))
868        self.assertEqual(min(ids), max(ids))
869        ids = list(map(id, list(zip('abc', 'def'))))
870        self.assertEqual(len(dict.fromkeys(ids)), len(ids))
871
872        # check copy, deepcopy, pickle
873        ans = [(x,y) for x, y in copy.copy(zip('abc',count()))]
874        self.assertEqual(ans, [('a', 0), ('b', 1), ('c', 2)])
875
876        ans = [(x,y) for x, y in copy.deepcopy(zip('abc',count()))]
877        self.assertEqual(ans, [('a', 0), ('b', 1), ('c', 2)])
878
879        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
880            ans = [(x,y) for x, y in pickle.loads(pickle.dumps(zip('abc',count()), proto))]
881            self.assertEqual(ans, [('a', 0), ('b', 1), ('c', 2)])
882
883        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
884            testIntermediate = zip('abc',count())
885            next(testIntermediate)
886            ans = [(x,y) for x, y in pickle.loads(pickle.dumps(testIntermediate, proto))]
887            self.assertEqual(ans, [('b', 1), ('c', 2)])
888
889        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
890            self.pickletest(proto, zip('abc', count()))
891
892    def test_ziplongest(self):
893        for args in [
894                ['abc', range(6)],
895                [range(6), 'abc'],
896                [range(1000), range(2000,2100), range(3000,3050)],
897                [range(1000), range(0), range(3000,3050), range(1200), range(1500)],
898                [range(1000), range(0), range(3000,3050), range(1200), range(1500), range(0)],
899            ]:
900            target = [tuple([arg[i] if i < len(arg) else None for arg in args])
901                      for i in range(max(map(len, args)))]
902            self.assertEqual(list(zip_longest(*args)), target)
903            self.assertEqual(list(zip_longest(*args, **{})), target)
904            target = [tuple((e is None and 'X' or e) for e in t) for t in target]   # Replace None fills with 'X'
905            self.assertEqual(list(zip_longest(*args, **dict(fillvalue='X'))), target)
906
907        self.assertEqual(take(3,zip_longest('abcdef', count())), list(zip('abcdef', range(3)))) # take 3 from infinite input
908
909        self.assertEqual(list(zip_longest()), list(zip()))
910        self.assertEqual(list(zip_longest([])), list(zip([])))
911        self.assertEqual(list(zip_longest('abcdef')), list(zip('abcdef')))
912
913        self.assertEqual(list(zip_longest('abc', 'defg', **{})),
914                         list(zip(list('abc')+[None], 'defg'))) # empty keyword dict
915        self.assertRaises(TypeError, zip_longest, 3)
916        self.assertRaises(TypeError, zip_longest, range(3), 3)
917
918        for stmt in [
919            "zip_longest('abc', fv=1)",
920            "zip_longest('abc', fillvalue=1, bogus_keyword=None)",
921        ]:
922            try:
923                eval(stmt, globals(), locals())
924            except TypeError:
925                pass
926            else:
927                self.fail('Did not raise Type in:  ' + stmt)
928
929        self.assertEqual([tuple(list(pair)) for pair in zip_longest('abc', 'def')],
930                         list(zip('abc', 'def')))
931        self.assertEqual([pair for pair in zip_longest('abc', 'def')],
932                         list(zip('abc', 'def')))
933
934    @support.impl_detail("tuple reuse is specific to CPython")
935    def test_zip_longest_tuple_reuse(self):
936        ids = list(map(id, zip_longest('abc', 'def')))
937        self.assertEqual(min(ids), max(ids))
938        ids = list(map(id, list(zip_longest('abc', 'def'))))
939        self.assertEqual(len(dict.fromkeys(ids)), len(ids))
940
941    def test_zip_longest_pickling(self):
942        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
943            self.pickletest(proto, zip_longest("abc", "def"))
944            self.pickletest(proto, zip_longest("abc", "defgh"))
945            self.pickletest(proto, zip_longest("abc", "defgh", fillvalue=1))
946            self.pickletest(proto, zip_longest("", "defgh"))
947
948    def test_bug_7244(self):
949
950        class Repeater:
951            # this class is similar to itertools.repeat
952            def __init__(self, o, t, e):
953                self.o = o
954                self.t = int(t)
955                self.e = e
956            def __iter__(self): # its iterator is itself
957                return self
958            def __next__(self):
959                if self.t > 0:
960                    self.t -= 1
961                    return self.o
962                else:
963                    raise self.e
964
965        # Formerly this code in would fail in debug mode
966        # with Undetected Error and Stop Iteration
967        r1 = Repeater(1, 3, StopIteration)
968        r2 = Repeater(2, 4, StopIteration)
969        def run(r1, r2):
970            result = []
971            for i, j in zip_longest(r1, r2, fillvalue=0):
972                with support.captured_output('stdout'):
973                    print((i, j))
974                result.append((i, j))
975            return result
976        self.assertEqual(run(r1, r2), [(1,2), (1,2), (1,2), (0,2)])
977
978        # Formerly, the RuntimeError would be lost
979        # and StopIteration would stop as expected
980        r1 = Repeater(1, 3, RuntimeError)
981        r2 = Repeater(2, 4, StopIteration)
982        it = zip_longest(r1, r2, fillvalue=0)
983        self.assertEqual(next(it), (1, 2))
984        self.assertEqual(next(it), (1, 2))
985        self.assertEqual(next(it), (1, 2))
986        self.assertRaises(RuntimeError, next, it)
987
988    def test_product(self):
989        for args, result in [
990            ([], [()]),                     # zero iterables
991            (['ab'], [('a',), ('b',)]),     # one iterable
992            ([range(2), range(3)], [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2)]),     # two iterables
993            ([range(0), range(2), range(3)], []),           # first iterable with zero length
994            ([range(2), range(0), range(3)], []),           # middle iterable with zero length
995            ([range(2), range(3), range(0)], []),           # last iterable with zero length
996            ]:
997            self.assertEqual(list(product(*args)), result)
998            for r in range(4):
999                self.assertEqual(list(product(*(args*r))),
1000                                 list(product(*args, **dict(repeat=r))))
1001        self.assertEqual(len(list(product(*[range(7)]*6))), 7**6)
1002        self.assertRaises(TypeError, product, range(6), None)
1003
1004        def product1(*args, **kwds):
1005            pools = list(map(tuple, args)) * kwds.get('repeat', 1)
1006            n = len(pools)
1007            if n == 0:
1008                yield ()
1009                return
1010            if any(len(pool) == 0 for pool in pools):
1011                return
1012            indices = [0] * n
1013            yield tuple(pool[i] for pool, i in zip(pools, indices))
1014            while 1:
1015                for i in reversed(range(n)):  # right to left
1016                    if indices[i] == len(pools[i]) - 1:
1017                        continue
1018                    indices[i] += 1
1019                    for j in range(i+1, n):
1020                        indices[j] = 0
1021                    yield tuple(pool[i] for pool, i in zip(pools, indices))
1022                    break
1023                else:
1024                    return
1025
1026        def product2(*args, **kwds):
1027            'Pure python version used in docs'
1028            pools = list(map(tuple, args)) * kwds.get('repeat', 1)
1029            result = [[]]
1030            for pool in pools:
1031                result = [x+[y] for x in result for y in pool]
1032            for prod in result:
1033                yield tuple(prod)
1034
1035        argtypes = ['', 'abc', '', range(0), range(4), dict(a=1, b=2, c=3),
1036                    set('abcdefg'), range(11), tuple(range(13))]
1037        for i in range(100):
1038            args = [random.choice(argtypes) for j in range(random.randrange(5))]
1039            expected_len = prod(map(len, args))
1040            self.assertEqual(len(list(product(*args))), expected_len)
1041            self.assertEqual(list(product(*args)), list(product1(*args)))
1042            self.assertEqual(list(product(*args)), list(product2(*args)))
1043            args = map(iter, args)
1044            self.assertEqual(len(list(product(*args))), expected_len)
1045
1046    @support.bigaddrspacetest
1047    def test_product_overflow(self):
1048        with self.assertRaises((OverflowError, MemoryError)):
1049            product(*(['ab']*2**5), repeat=2**25)
1050
1051    @support.impl_detail("tuple reuse is specific to CPython")
1052    def test_product_tuple_reuse(self):
1053        self.assertEqual(len(set(map(id, product('abc', 'def')))), 1)
1054        self.assertNotEqual(len(set(map(id, list(product('abc', 'def'))))), 1)
1055
1056    def test_product_pickling(self):
1057        # check copy, deepcopy, pickle
1058        for args, result in [
1059            ([], [()]),                     # zero iterables
1060            (['ab'], [('a',), ('b',)]),     # one iterable
1061            ([range(2), range(3)], [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2)]),     # two iterables
1062            ([range(0), range(2), range(3)], []),           # first iterable with zero length
1063            ([range(2), range(0), range(3)], []),           # middle iterable with zero length
1064            ([range(2), range(3), range(0)], []),           # last iterable with zero length
1065            ]:
1066            self.assertEqual(list(copy.copy(product(*args))), result)
1067            self.assertEqual(list(copy.deepcopy(product(*args))), result)
1068            for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1069                self.pickletest(proto, product(*args))
1070
1071    def test_product_issue_25021(self):
1072        # test that indices are properly clamped to the length of the tuples
1073        p = product((1, 2),(3,))
1074        p.__setstate__((0, 0x1000))  # will access tuple element 1 if not clamped
1075        self.assertEqual(next(p), (2, 3))
1076        # test that empty tuple in the list will result in an immediate StopIteration
1077        p = product((1, 2), (), (3,))
1078        p.__setstate__((0, 0, 0x1000))  # will access tuple element 1 if not clamped
1079        self.assertRaises(StopIteration, next, p)
1080
1081    def test_repeat(self):
1082        self.assertEqual(list(repeat(object='a', times=3)), ['a', 'a', 'a'])
1083        self.assertEqual(lzip(range(3),repeat('a')),
1084                         [(0, 'a'), (1, 'a'), (2, 'a')])
1085        self.assertEqual(list(repeat('a', 3)), ['a', 'a', 'a'])
1086        self.assertEqual(take(3, repeat('a')), ['a', 'a', 'a'])
1087        self.assertEqual(list(repeat('a', 0)), [])
1088        self.assertEqual(list(repeat('a', -3)), [])
1089        self.assertRaises(TypeError, repeat)
1090        self.assertRaises(TypeError, repeat, None, 3, 4)
1091        self.assertRaises(TypeError, repeat, None, 'a')
1092        r = repeat(1+0j)
1093        self.assertEqual(repr(r), 'repeat((1+0j))')
1094        r = repeat(1+0j, 5)
1095        self.assertEqual(repr(r), 'repeat((1+0j), 5)')
1096        list(r)
1097        self.assertEqual(repr(r), 'repeat((1+0j), 0)')
1098
1099        # check copy, deepcopy, pickle
1100        c = repeat(object='a', times=10)
1101        self.assertEqual(next(c), 'a')
1102        self.assertEqual(take(2, copy.copy(c)), list('a' * 2))
1103        self.assertEqual(take(2, copy.deepcopy(c)), list('a' * 2))
1104        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1105            self.pickletest(proto, repeat(object='a', times=10))
1106
1107    def test_repeat_with_negative_times(self):
1108        self.assertEqual(repr(repeat('a', -1)), "repeat('a', 0)")
1109        self.assertEqual(repr(repeat('a', -2)), "repeat('a', 0)")
1110        self.assertEqual(repr(repeat('a', times=-1)), "repeat('a', 0)")
1111        self.assertEqual(repr(repeat('a', times=-2)), "repeat('a', 0)")
1112
1113    def test_map(self):
1114        self.assertEqual(list(map(operator.pow, range(3), range(1,7))),
1115                         [0**1, 1**2, 2**3])
1116        self.assertEqual(list(map(tupleize, 'abc', range(5))),
1117                         [('a',0),('b',1),('c',2)])
1118        self.assertEqual(list(map(tupleize, 'abc', count())),
1119                         [('a',0),('b',1),('c',2)])
1120        self.assertEqual(take(2,map(tupleize, 'abc', count())),
1121                         [('a',0),('b',1)])
1122        self.assertEqual(list(map(operator.pow, [])), [])
1123        self.assertRaises(TypeError, map)
1124        self.assertRaises(TypeError, list, map(None, range(3), range(3)))
1125        self.assertRaises(TypeError, map, operator.neg)
1126        self.assertRaises(TypeError, next, map(10, range(5)))
1127        self.assertRaises(ValueError, next, map(errfunc, [4], [5]))
1128        self.assertRaises(TypeError, next, map(onearg, [4], [5]))
1129
1130        # check copy, deepcopy, pickle
1131        ans = [('a',0),('b',1),('c',2)]
1132
1133        c = map(tupleize, 'abc', count())
1134        self.assertEqual(list(copy.copy(c)), ans)
1135
1136        c = map(tupleize, 'abc', count())
1137        self.assertEqual(list(copy.deepcopy(c)), ans)
1138
1139        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1140            c = map(tupleize, 'abc', count())
1141            self.pickletest(proto, c)
1142
1143    def test_starmap(self):
1144        self.assertEqual(list(starmap(operator.pow, zip(range(3), range(1,7)))),
1145                         [0**1, 1**2, 2**3])
1146        self.assertEqual(take(3, starmap(operator.pow, zip(count(), count(1)))),
1147                         [0**1, 1**2, 2**3])
1148        self.assertEqual(list(starmap(operator.pow, [])), [])
1149        self.assertEqual(list(starmap(operator.pow, [iter([4,5])])), [4**5])
1150        self.assertRaises(TypeError, list, starmap(operator.pow, [None]))
1151        self.assertRaises(TypeError, starmap)
1152        self.assertRaises(TypeError, starmap, operator.pow, [(4,5)], 'extra')
1153        self.assertRaises(TypeError, next, starmap(10, [(4,5)]))
1154        self.assertRaises(ValueError, next, starmap(errfunc, [(4,5)]))
1155        self.assertRaises(TypeError, next, starmap(onearg, [(4,5)]))
1156
1157        # check copy, deepcopy, pickle
1158        ans = [0**1, 1**2, 2**3]
1159
1160        c = starmap(operator.pow, zip(range(3), range(1,7)))
1161        self.assertEqual(list(copy.copy(c)), ans)
1162
1163        c = starmap(operator.pow, zip(range(3), range(1,7)))
1164        self.assertEqual(list(copy.deepcopy(c)), ans)
1165
1166        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1167            c = starmap(operator.pow, zip(range(3), range(1,7)))
1168            self.pickletest(proto, c)
1169
1170    def test_islice(self):
1171        for args in [          # islice(args) should agree with range(args)
1172                (10, 20, 3),
1173                (10, 3, 20),
1174                (10, 20),
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        # Test invalid arguments
1202        ra = range(10)
1203        self.assertRaises(TypeError, islice, ra)
1204        self.assertRaises(TypeError, islice, ra, 1, 2, 3, 4)
1205        self.assertRaises(ValueError, islice, ra, -5, 10, 1)
1206        self.assertRaises(ValueError, islice, ra, 1, -5, -1)
1207        self.assertRaises(ValueError, islice, ra, 1, 10, -1)
1208        self.assertRaises(ValueError, islice, ra, 1, 10, 0)
1209        self.assertRaises(ValueError, islice, ra, 'a')
1210        self.assertRaises(ValueError, islice, ra, 'a', 1)
1211        self.assertRaises(ValueError, islice, ra, 1, 'a')
1212        self.assertRaises(ValueError, islice, ra, 'a', 1, 1)
1213        self.assertRaises(ValueError, islice, ra, 1, 'a', 1)
1214        self.assertEqual(len(list(islice(count(), 1, 10, maxsize))), 1)
1215
1216        # Issue #10323:  Less islice in a predictable state
1217        c = count()
1218        self.assertEqual(list(islice(c, 1, 3, 50)), [1])
1219        self.assertEqual(next(c), 3)
1220
1221        # check copy, deepcopy, pickle
1222        for args in [          # islice(args) should agree with range(args)
1223                (10, 20, 3),
1224                (10, 3, 20),
1225                (10, 20),
1226                (10, 3),
1227                (20,)
1228                ]:
1229            self.assertEqual(list(copy.copy(islice(range(100), *args))),
1230                             list(range(*args)))
1231            self.assertEqual(list(copy.deepcopy(islice(range(100), *args))),
1232                             list(range(*args)))
1233            for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1234                self.pickletest(proto, islice(range(100), *args))
1235
1236        # Issue #21321: check source iterator is not referenced
1237        # from islice() after the latter has been exhausted
1238        it = (x for x in (1, 2))
1239        wr = weakref.ref(it)
1240        it = islice(it, 1)
1241        self.assertIsNotNone(wr())
1242        list(it) # exhaust the iterator
1243        support.gc_collect()
1244        self.assertIsNone(wr())
1245
1246    def test_takewhile(self):
1247        data = [1, 3, 5, 20, 2, 4, 6, 8]
1248        self.assertEqual(list(takewhile(underten, data)), [1, 3, 5])
1249        self.assertEqual(list(takewhile(underten, [])), [])
1250        self.assertRaises(TypeError, takewhile)
1251        self.assertRaises(TypeError, takewhile, operator.pow)
1252        self.assertRaises(TypeError, takewhile, operator.pow, [(4,5)], 'extra')
1253        self.assertRaises(TypeError, next, takewhile(10, [(4,5)]))
1254        self.assertRaises(ValueError, next, takewhile(errfunc, [(4,5)]))
1255        t = takewhile(bool, [1, 1, 1, 0, 0, 0])
1256        self.assertEqual(list(t), [1, 1, 1])
1257        self.assertRaises(StopIteration, next, t)
1258
1259        # check copy, deepcopy, pickle
1260        self.assertEqual(list(copy.copy(takewhile(underten, data))), [1, 3, 5])
1261        self.assertEqual(list(copy.deepcopy(takewhile(underten, data))),
1262                        [1, 3, 5])
1263        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1264            self.pickletest(proto, takewhile(underten, data))
1265
1266    def test_dropwhile(self):
1267        data = [1, 3, 5, 20, 2, 4, 6, 8]
1268        self.assertEqual(list(dropwhile(underten, data)), [20, 2, 4, 6, 8])
1269        self.assertEqual(list(dropwhile(underten, [])), [])
1270        self.assertRaises(TypeError, dropwhile)
1271        self.assertRaises(TypeError, dropwhile, operator.pow)
1272        self.assertRaises(TypeError, dropwhile, operator.pow, [(4,5)], 'extra')
1273        self.assertRaises(TypeError, next, dropwhile(10, [(4,5)]))
1274        self.assertRaises(ValueError, next, dropwhile(errfunc, [(4,5)]))
1275
1276        # check copy, deepcopy, pickle
1277        self.assertEqual(list(copy.copy(dropwhile(underten, data))), [20, 2, 4, 6, 8])
1278        self.assertEqual(list(copy.deepcopy(dropwhile(underten, data))),
1279                        [20, 2, 4, 6, 8])
1280        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1281            self.pickletest(proto, dropwhile(underten, data))
1282
1283    def test_tee(self):
1284        n = 200
1285
1286        a, b = tee([])        # test empty iterator
1287        self.assertEqual(list(a), [])
1288        self.assertEqual(list(b), [])
1289
1290        a, b = tee(irange(n)) # test 100% interleaved
1291        self.assertEqual(lzip(a,b), lzip(range(n), range(n)))
1292
1293        a, b = tee(irange(n)) # test 0% interleaved
1294        self.assertEqual(list(a), list(range(n)))
1295        self.assertEqual(list(b), list(range(n)))
1296
1297        a, b = tee(irange(n)) # test dealloc of leading iterator
1298        for i in range(100):
1299            self.assertEqual(next(a), i)
1300        del a
1301        self.assertEqual(list(b), list(range(n)))
1302
1303        a, b = tee(irange(n)) # test dealloc of trailing iterator
1304        for i in range(100):
1305            self.assertEqual(next(a), i)
1306        del b
1307        self.assertEqual(list(a), list(range(100, n)))
1308
1309        for j in range(5):   # test randomly interleaved
1310            order = [0]*n + [1]*n
1311            random.shuffle(order)
1312            lists = ([], [])
1313            its = tee(irange(n))
1314            for i in order:
1315                value = next(its[i])
1316                lists[i].append(value)
1317            self.assertEqual(lists[0], list(range(n)))
1318            self.assertEqual(lists[1], list(range(n)))
1319
1320        # test argument format checking
1321        self.assertRaises(TypeError, tee)
1322        self.assertRaises(TypeError, tee, 3)
1323        self.assertRaises(TypeError, tee, [1,2], 'x')
1324        self.assertRaises(TypeError, tee, [1,2], 3, 'x')
1325
1326        # tee object should be instantiable
1327        a, b = tee('abc')
1328        c = type(a)('def')
1329        self.assertEqual(list(c), list('def'))
1330
1331        # test long-lagged and multi-way split
1332        a, b, c = tee(range(2000), 3)
1333        for i in range(100):
1334            self.assertEqual(next(a), i)
1335        self.assertEqual(list(b), list(range(2000)))
1336        self.assertEqual([next(c), next(c)], list(range(2)))
1337        self.assertEqual(list(a), list(range(100,2000)))
1338        self.assertEqual(list(c), list(range(2,2000)))
1339
1340        # test values of n
1341        self.assertRaises(TypeError, tee, 'abc', 'invalid')
1342        self.assertRaises(ValueError, tee, [], -1)
1343        for n in range(5):
1344            result = tee('abc', n)
1345            self.assertEqual(type(result), tuple)
1346            self.assertEqual(len(result), n)
1347            self.assertEqual([list(x) for x in result], [list('abc')]*n)
1348
1349        # tee pass-through to copyable iterator
1350        a, b = tee('abc')
1351        c, d = tee(a)
1352        self.assertTrue(a is c)
1353
1354        # test tee_new
1355        t1, t2 = tee('abc')
1356        tnew = type(t1)
1357        self.assertRaises(TypeError, tnew)
1358        self.assertRaises(TypeError, tnew, 10)
1359        t3 = tnew(t1)
1360        self.assertTrue(list(t1) == list(t2) == list(t3) == list('abc'))
1361
1362        # test that tee objects are weak referencable
1363        a, b = tee(range(10))
1364        p = weakref.proxy(a)
1365        self.assertEqual(getattr(p, '__class__'), type(b))
1366        del a
1367        self.assertRaises(ReferenceError, getattr, p, '__class__')
1368
1369        ans = list('abc')
1370        long_ans = list(range(10000))
1371
1372        # check copy
1373        a, b = tee('abc')
1374        self.assertEqual(list(copy.copy(a)), ans)
1375        self.assertEqual(list(copy.copy(b)), ans)
1376        a, b = tee(list(range(10000)))
1377        self.assertEqual(list(copy.copy(a)), long_ans)
1378        self.assertEqual(list(copy.copy(b)), long_ans)
1379
1380        # check partially consumed copy
1381        a, b = tee('abc')
1382        take(2, a)
1383        take(1, b)
1384        self.assertEqual(list(copy.copy(a)), ans[2:])
1385        self.assertEqual(list(copy.copy(b)), ans[1:])
1386        self.assertEqual(list(a), ans[2:])
1387        self.assertEqual(list(b), ans[1:])
1388        a, b = tee(range(10000))
1389        take(100, a)
1390        take(60, b)
1391        self.assertEqual(list(copy.copy(a)), long_ans[100:])
1392        self.assertEqual(list(copy.copy(b)), long_ans[60:])
1393        self.assertEqual(list(a), long_ans[100:])
1394        self.assertEqual(list(b), long_ans[60:])
1395
1396        # check deepcopy
1397        a, b = tee('abc')
1398        self.assertEqual(list(copy.deepcopy(a)), ans)
1399        self.assertEqual(list(copy.deepcopy(b)), ans)
1400        self.assertEqual(list(a), ans)
1401        self.assertEqual(list(b), ans)
1402        a, b = tee(range(10000))
1403        self.assertEqual(list(copy.deepcopy(a)), long_ans)
1404        self.assertEqual(list(copy.deepcopy(b)), long_ans)
1405        self.assertEqual(list(a), long_ans)
1406        self.assertEqual(list(b), long_ans)
1407
1408        # check partially consumed deepcopy
1409        a, b = tee('abc')
1410        take(2, a)
1411        take(1, b)
1412        self.assertEqual(list(copy.deepcopy(a)), ans[2:])
1413        self.assertEqual(list(copy.deepcopy(b)), ans[1:])
1414        self.assertEqual(list(a), ans[2:])
1415        self.assertEqual(list(b), ans[1:])
1416        a, b = tee(range(10000))
1417        take(100, a)
1418        take(60, b)
1419        self.assertEqual(list(copy.deepcopy(a)), long_ans[100:])
1420        self.assertEqual(list(copy.deepcopy(b)), long_ans[60:])
1421        self.assertEqual(list(a), long_ans[100:])
1422        self.assertEqual(list(b), long_ans[60:])
1423
1424        # check pickle
1425        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1426            self.pickletest(proto, iter(tee('abc')))
1427            a, b = tee('abc')
1428            self.pickletest(proto, a, compare=ans)
1429            self.pickletest(proto, b, compare=ans)
1430
1431    # Issue 13454: Crash when deleting backward iterator from tee()
1432    def test_tee_del_backward(self):
1433        forward, backward = tee(repeat(None, 20000000))
1434        try:
1435            any(forward)  # exhaust the iterator
1436            del backward
1437        except:
1438            del forward, backward
1439            raise
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
1464class TestExamples(unittest.TestCase):
1465
1466    def test_accumulate(self):
1467        self.assertEqual(list(accumulate([1,2,3,4,5])), [1, 3, 6, 10, 15])
1468
1469    def test_accumulate_reducible(self):
1470        # check copy, deepcopy, pickle
1471        data = [1, 2, 3, 4, 5]
1472        accumulated = [1, 3, 6, 10, 15]
1473
1474        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1475            it = accumulate(data)
1476            self.assertEqual(list(pickle.loads(pickle.dumps(it, proto))), accumulated[:])
1477            self.assertEqual(next(it), 1)
1478            self.assertEqual(list(pickle.loads(pickle.dumps(it, proto))), accumulated[1:])
1479        it = accumulate(data)
1480        self.assertEqual(next(it), 1)
1481        self.assertEqual(list(copy.deepcopy(it)), accumulated[1:])
1482        self.assertEqual(list(copy.copy(it)), accumulated[1:])
1483
1484    def test_accumulate_reducible_none(self):
1485        # Issue #25718: total is None
1486        it = accumulate([None, None, None], operator.is_)
1487        self.assertEqual(next(it), None)
1488        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
1489            it_copy = pickle.loads(pickle.dumps(it, proto))
1490            self.assertEqual(list(it_copy), [True, False])
1491        self.assertEqual(list(copy.deepcopy(it)), [True, False])
1492        self.assertEqual(list(copy.copy(it)), [True, False])
1493
1494    def test_chain(self):
1495        self.assertEqual(''.join(chain('ABC', 'DEF')), 'ABCDEF')
1496
1497    def test_chain_from_iterable(self):
1498        self.assertEqual(''.join(chain.from_iterable(['ABC', 'DEF'])), 'ABCDEF')
1499
1500    def test_combinations(self):
1501        self.assertEqual(list(combinations('ABCD', 2)),
1502                         [('A','B'), ('A','C'), ('A','D'), ('B','C'), ('B','D'), ('C','D')])
1503        self.assertEqual(list(combinations(range(4), 3)),
1504                         [(0,1,2), (0,1,3), (0,2,3), (1,2,3)])
1505
1506    def test_combinations_with_replacement(self):
1507        self.assertEqual(list(combinations_with_replacement('ABC', 2)),
1508                         [('A','A'), ('A','B'), ('A','C'), ('B','B'), ('B','C'), ('C','C')])
1509
1510    def test_compress(self):
1511        self.assertEqual(list(compress('ABCDEF', [1,0,1,0,1,1])), list('ACEF'))
1512
1513    def test_count(self):
1514        self.assertEqual(list(islice(count(10), 5)), [10, 11, 12, 13, 14])
1515
1516    def test_cycle(self):
1517        self.assertEqual(list(islice(cycle('ABCD'), 12)), list('ABCDABCDABCD'))
1518
1519    def test_dropwhile(self):
1520        self.assertEqual(list(dropwhile(lambda x: x<5, [1,4,6,4,1])), [6,4,1])
1521
1522    def test_groupby(self):
1523        self.assertEqual([k for k, g in groupby('AAAABBBCCDAABBB')],
1524                         list('ABCDAB'))
1525        self.assertEqual([(list(g)) for k, g in groupby('AAAABBBCCD')],
1526                         [list('AAAA'), list('BBB'), list('CC'), list('D')])
1527
1528    def test_filter(self):
1529        self.assertEqual(list(filter(lambda x: x%2, range(10))), [1,3,5,7,9])
1530
1531    def test_filterfalse(self):
1532        self.assertEqual(list(filterfalse(lambda x: x%2, range(10))), [0,2,4,6,8])
1533
1534    def test_map(self):
1535        self.assertEqual(list(map(pow, (2,3,10), (5,2,3))), [32, 9, 1000])
1536
1537    def test_islice(self):
1538        self.assertEqual(list(islice('ABCDEFG', 2)), list('AB'))
1539        self.assertEqual(list(islice('ABCDEFG', 2, 4)), list('CD'))
1540        self.assertEqual(list(islice('ABCDEFG', 2, None)), list('CDEFG'))
1541        self.assertEqual(list(islice('ABCDEFG', 0, None, 2)), list('ACEG'))
1542
1543    def test_zip(self):
1544        self.assertEqual(list(zip('ABCD', 'xy')), [('A', 'x'), ('B', 'y')])
1545
1546    def test_zip_longest(self):
1547        self.assertEqual(list(zip_longest('ABCD', 'xy', fillvalue='-')),
1548                         [('A', 'x'), ('B', 'y'), ('C', '-'), ('D', '-')])
1549
1550    def test_permutations(self):
1551        self.assertEqual(list(permutations('ABCD', 2)),
1552                         list(map(tuple, 'AB AC AD BA BC BD CA CB CD DA DB DC'.split())))
1553        self.assertEqual(list(permutations(range(3))),
1554                         [(0,1,2), (0,2,1), (1,0,2), (1,2,0), (2,0,1), (2,1,0)])
1555
1556    def test_product(self):
1557        self.assertEqual(list(product('ABCD', 'xy')),
1558                         list(map(tuple, 'Ax Ay Bx By Cx Cy Dx Dy'.split())))
1559        self.assertEqual(list(product(range(2), repeat=3)),
1560                        [(0,0,0), (0,0,1), (0,1,0), (0,1,1),
1561                         (1,0,0), (1,0,1), (1,1,0), (1,1,1)])
1562
1563    def test_repeat(self):
1564        self.assertEqual(list(repeat(10, 3)), [10, 10, 10])
1565
1566    def test_stapmap(self):
1567        self.assertEqual(list(starmap(pow, [(2,5), (3,2), (10,3)])),
1568                         [32, 9, 1000])
1569
1570    def test_takewhile(self):
1571        self.assertEqual(list(takewhile(lambda x: x<5, [1,4,6,4,1])), [1,4])
1572
1573
1574class TestGC(unittest.TestCase):
1575
1576    def makecycle(self, iterator, container):
1577        container.append(iterator)
1578        next(iterator)
1579        del container, iterator
1580
1581    def test_accumulate(self):
1582        a = []
1583        self.makecycle(accumulate([1,2,a,3]), a)
1584
1585    def test_chain(self):
1586        a = []
1587        self.makecycle(chain(a), a)
1588
1589    def test_chain_from_iterable(self):
1590        a = []
1591        self.makecycle(chain.from_iterable([a]), a)
1592
1593    def test_combinations(self):
1594        a = []
1595        self.makecycle(combinations([1,2,a,3], 3), a)
1596
1597    def test_combinations_with_replacement(self):
1598        a = []
1599        self.makecycle(combinations_with_replacement([1,2,a,3], 3), a)
1600
1601    def test_compress(self):
1602        a = []
1603        self.makecycle(compress('ABCDEF', [1,0,1,0,1,0]), a)
1604
1605    def test_count(self):
1606        a = []
1607        Int = type('Int', (int,), dict(x=a))
1608        self.makecycle(count(Int(0), Int(1)), a)
1609
1610    def test_cycle(self):
1611        a = []
1612        self.makecycle(cycle([a]*2), a)
1613
1614    def test_dropwhile(self):
1615        a = []
1616        self.makecycle(dropwhile(bool, [0, a, a]), a)
1617
1618    def test_groupby(self):
1619        a = []
1620        self.makecycle(groupby([a]*2, lambda x:x), a)
1621
1622    def test_issue2246(self):
1623        # Issue 2246 -- the _grouper iterator was not included in GC
1624        n = 10
1625        keyfunc = lambda x: x
1626        for i, j in groupby(range(n), key=keyfunc):
1627            keyfunc.__dict__.setdefault('x',[]).append(j)
1628
1629    def test_filter(self):
1630        a = []
1631        self.makecycle(filter(lambda x:True, [a]*2), a)
1632
1633    def test_filterfalse(self):
1634        a = []
1635        self.makecycle(filterfalse(lambda x:False, a), a)
1636
1637    def test_zip(self):
1638        a = []
1639        self.makecycle(zip([a]*2, [a]*3), a)
1640
1641    def test_zip_longest(self):
1642        a = []
1643        self.makecycle(zip_longest([a]*2, [a]*3), a)
1644        b = [a, None]
1645        self.makecycle(zip_longest([a]*2, [a]*3, fillvalue=b), a)
1646
1647    def test_map(self):
1648        a = []
1649        self.makecycle(map(lambda x:x, [a]*2), a)
1650
1651    def test_islice(self):
1652        a = []
1653        self.makecycle(islice([a]*2, None), a)
1654
1655    def test_permutations(self):
1656        a = []
1657        self.makecycle(permutations([1,2,a,3], 3), a)
1658
1659    def test_product(self):
1660        a = []
1661        self.makecycle(product([1,2,a,3], repeat=3), a)
1662
1663    def test_repeat(self):
1664        a = []
1665        self.makecycle(repeat(a), a)
1666
1667    def test_starmap(self):
1668        a = []
1669        self.makecycle(starmap(lambda *t: t, [(a,a)]*2), a)
1670
1671    def test_takewhile(self):
1672        a = []
1673        self.makecycle(takewhile(bool, [1, 0, a, a]), a)
1674
1675def R(seqn):
1676    'Regular generator'
1677    for i in seqn:
1678        yield i
1679
1680class G:
1681    'Sequence using __getitem__'
1682    def __init__(self, seqn):
1683        self.seqn = seqn
1684    def __getitem__(self, i):
1685        return self.seqn[i]
1686
1687class I:
1688    'Sequence using iterator protocol'
1689    def __init__(self, seqn):
1690        self.seqn = seqn
1691        self.i = 0
1692    def __iter__(self):
1693        return self
1694    def __next__(self):
1695        if self.i >= len(self.seqn): raise StopIteration
1696        v = self.seqn[self.i]
1697        self.i += 1
1698        return v
1699
1700class Ig:
1701    'Sequence using iterator protocol defined with a generator'
1702    def __init__(self, seqn):
1703        self.seqn = seqn
1704        self.i = 0
1705    def __iter__(self):
1706        for val in self.seqn:
1707            yield val
1708
1709class X:
1710    'Missing __getitem__ and __iter__'
1711    def __init__(self, seqn):
1712        self.seqn = seqn
1713        self.i = 0
1714    def __next__(self):
1715        if self.i >= len(self.seqn): raise StopIteration
1716        v = self.seqn[self.i]
1717        self.i += 1
1718        return v
1719
1720class N:
1721    'Iterator missing __next__()'
1722    def __init__(self, seqn):
1723        self.seqn = seqn
1724        self.i = 0
1725    def __iter__(self):
1726        return self
1727
1728class E:
1729    'Test propagation of exceptions'
1730    def __init__(self, seqn):
1731        self.seqn = seqn
1732        self.i = 0
1733    def __iter__(self):
1734        return self
1735    def __next__(self):
1736        3 // 0
1737
1738class S:
1739    'Test immediate stop'
1740    def __init__(self, seqn):
1741        pass
1742    def __iter__(self):
1743        return self
1744    def __next__(self):
1745        raise StopIteration
1746
1747def L(seqn):
1748    'Test multiple tiers of iterators'
1749    return chain(map(lambda x:x, R(Ig(G(seqn)))))
1750
1751
1752class TestVariousIteratorArgs(unittest.TestCase):
1753
1754    def test_accumulate(self):
1755        s = [1,2,3,4,5]
1756        r = [1,3,6,10,15]
1757        n = len(s)
1758        for g in (G, I, Ig, L, R):
1759            self.assertEqual(list(accumulate(g(s))), r)
1760        self.assertEqual(list(accumulate(S(s))), [])
1761        self.assertRaises(TypeError, accumulate, X(s))
1762        self.assertRaises(TypeError, accumulate, N(s))
1763        self.assertRaises(ZeroDivisionError, list, accumulate(E(s)))
1764
1765    def test_chain(self):
1766        for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
1767            for g in (G, I, Ig, S, L, R):
1768                self.assertEqual(list(chain(g(s))), list(g(s)))
1769                self.assertEqual(list(chain(g(s), g(s))), list(g(s))+list(g(s)))
1770            self.assertRaises(TypeError, list, chain(X(s)))
1771            self.assertRaises(TypeError, list, chain(N(s)))
1772            self.assertRaises(ZeroDivisionError, list, chain(E(s)))
1773
1774    def test_compress(self):
1775        for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
1776            n = len(s)
1777            for g in (G, I, Ig, S, L, R):
1778                self.assertEqual(list(compress(g(s), repeat(1))), list(g(s)))
1779            self.assertRaises(TypeError, compress, X(s), repeat(1))
1780            self.assertRaises(TypeError, compress, N(s), repeat(1))
1781            self.assertRaises(ZeroDivisionError, list, compress(E(s), repeat(1)))
1782
1783    def test_product(self):
1784        for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
1785            self.assertRaises(TypeError, product, X(s))
1786            self.assertRaises(TypeError, product, N(s))
1787            self.assertRaises(ZeroDivisionError, product, E(s))
1788
1789    def test_cycle(self):
1790        for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
1791            for g in (G, I, Ig, S, L, R):
1792                tgtlen = len(s) * 3
1793                expected = list(g(s))*3
1794                actual = list(islice(cycle(g(s)), tgtlen))
1795                self.assertEqual(actual, expected)
1796            self.assertRaises(TypeError, cycle, X(s))
1797            self.assertRaises(TypeError, cycle, N(s))
1798            self.assertRaises(ZeroDivisionError, list, cycle(E(s)))
1799
1800    def test_groupby(self):
1801        for s in (range(10), range(0), range(1000), (7,11), range(2000,2200,5)):
1802            for g in (G, I, Ig, S, L, R):
1803                self.assertEqual([k for k, sb in groupby(g(s))], list(g(s)))
1804            self.assertRaises(TypeError, groupby, X(s))
1805            self.assertRaises(TypeError, groupby, N(s))
1806            self.assertRaises(ZeroDivisionError, list, groupby(E(s)))
1807
1808    def test_filter(self):
1809        for s in (range(10), range(0), range(1000), (7,11), range(2000,2200,5)):
1810            for g in (G, I, Ig, S, L, R):
1811                self.assertEqual(list(filter(isEven, g(s))),
1812                                 [x for x in g(s) if isEven(x)])
1813            self.assertRaises(TypeError, filter, isEven, X(s))
1814            self.assertRaises(TypeError, filter, isEven, N(s))
1815            self.assertRaises(ZeroDivisionError, list, filter(isEven, E(s)))
1816
1817    def test_filterfalse(self):
1818        for s in (range(10), range(0), range(1000), (7,11), range(2000,2200,5)):
1819            for g in (G, I, Ig, S, L, R):
1820                self.assertEqual(list(filterfalse(isEven, g(s))),
1821                                 [x for x in g(s) if isOdd(x)])
1822            self.assertRaises(TypeError, filterfalse, isEven, X(s))
1823            self.assertRaises(TypeError, filterfalse, isEven, N(s))
1824            self.assertRaises(ZeroDivisionError, list, filterfalse(isEven, E(s)))
1825
1826    def test_zip(self):
1827        for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
1828            for g in (G, I, Ig, S, L, R):
1829                self.assertEqual(list(zip(g(s))), lzip(g(s)))
1830                self.assertEqual(list(zip(g(s), g(s))), lzip(g(s), g(s)))
1831            self.assertRaises(TypeError, zip, X(s))
1832            self.assertRaises(TypeError, zip, N(s))
1833            self.assertRaises(ZeroDivisionError, list, zip(E(s)))
1834
1835    def test_ziplongest(self):
1836        for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
1837            for g in (G, I, Ig, S, L, R):
1838                self.assertEqual(list(zip_longest(g(s))), list(zip(g(s))))
1839                self.assertEqual(list(zip_longest(g(s), g(s))), list(zip(g(s), g(s))))
1840            self.assertRaises(TypeError, zip_longest, X(s))
1841            self.assertRaises(TypeError, zip_longest, N(s))
1842            self.assertRaises(ZeroDivisionError, list, zip_longest(E(s)))
1843
1844    def test_map(self):
1845        for s in (range(10), range(0), range(100), (7,11), range(20,50,5)):
1846            for g in (G, I, Ig, S, L, R):
1847                self.assertEqual(list(map(onearg, g(s))),
1848                                 [onearg(x) for x in g(s)])
1849                self.assertEqual(list(map(operator.pow, g(s), g(s))),
1850                                 [x**x for x in g(s)])
1851            self.assertRaises(TypeError, map, onearg, X(s))
1852            self.assertRaises(TypeError, map, onearg, N(s))
1853            self.assertRaises(ZeroDivisionError, list, map(onearg, E(s)))
1854
1855    def test_islice(self):
1856        for s in ("12345", "", range(1000), ('do', 1.2), range(2000,2200,5)):
1857            for g in (G, I, Ig, S, L, R):
1858                self.assertEqual(list(islice(g(s),1,None,2)), list(g(s))[1::2])
1859            self.assertRaises(TypeError, islice, X(s), 10)
1860            self.assertRaises(TypeError, islice, N(s), 10)
1861            self.assertRaises(ZeroDivisionError, list, islice(E(s), 10))
1862
1863    def test_starmap(self):
1864        for s in (range(10), range(0), range(100), (7,11), range(20,50,5)):
1865            for g in (G, I, Ig, S, L, R):
1866                ss = lzip(s, s)
1867                self.assertEqual(list(starmap(operator.pow, g(ss))),
1868                                 [x**x for x in g(s)])
1869            self.assertRaises(TypeError, starmap, operator.pow, X(ss))
1870            self.assertRaises(TypeError, starmap, operator.pow, N(ss))
1871            self.assertRaises(ZeroDivisionError, list, starmap(operator.pow, E(ss)))
1872
1873    def test_takewhile(self):
1874        for s in (range(10), range(0), range(1000), (7,11), range(2000,2200,5)):
1875            for g in (G, I, Ig, S, L, R):
1876                tgt = []
1877                for elem in g(s):
1878                    if not isEven(elem): break
1879                    tgt.append(elem)
1880                self.assertEqual(list(takewhile(isEven, g(s))), tgt)
1881            self.assertRaises(TypeError, takewhile, isEven, X(s))
1882            self.assertRaises(TypeError, takewhile, isEven, N(s))
1883            self.assertRaises(ZeroDivisionError, list, takewhile(isEven, E(s)))
1884
1885    def test_dropwhile(self):
1886        for s in (range(10), range(0), range(1000), (7,11), range(2000,2200,5)):
1887            for g in (G, I, Ig, S, L, R):
1888                tgt = []
1889                for elem in g(s):
1890                    if not tgt and isOdd(elem): continue
1891                    tgt.append(elem)
1892                self.assertEqual(list(dropwhile(isOdd, g(s))), tgt)
1893            self.assertRaises(TypeError, dropwhile, isOdd, X(s))
1894            self.assertRaises(TypeError, dropwhile, isOdd, N(s))
1895            self.assertRaises(ZeroDivisionError, list, dropwhile(isOdd, E(s)))
1896
1897    def test_tee(self):
1898        for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
1899            for g in (G, I, Ig, S, L, R):
1900                it1, it2 = tee(g(s))
1901                self.assertEqual(list(it1), list(g(s)))
1902                self.assertEqual(list(it2), list(g(s)))
1903            self.assertRaises(TypeError, tee, X(s))
1904            self.assertRaises(TypeError, tee, N(s))
1905            self.assertRaises(ZeroDivisionError, list, tee(E(s))[0])
1906
1907class LengthTransparency(unittest.TestCase):
1908
1909    def test_repeat(self):
1910        self.assertEqual(operator.length_hint(repeat(None, 50)), 50)
1911        self.assertEqual(operator.length_hint(repeat(None, 0)), 0)
1912        self.assertEqual(operator.length_hint(repeat(None), 12), 12)
1913
1914    def test_repeat_with_negative_times(self):
1915        self.assertEqual(operator.length_hint(repeat(None, -1)), 0)
1916        self.assertEqual(operator.length_hint(repeat(None, -2)), 0)
1917        self.assertEqual(operator.length_hint(repeat(None, times=-1)), 0)
1918        self.assertEqual(operator.length_hint(repeat(None, times=-2)), 0)
1919
1920class RegressionTests(unittest.TestCase):
1921
1922    def test_sf_793826(self):
1923        # Fix Armin Rigo's successful efforts to wreak havoc
1924
1925        def mutatingtuple(tuple1, f, tuple2):
1926            # this builds a tuple t which is a copy of tuple1,
1927            # then calls f(t), then mutates t to be equal to tuple2
1928            # (needs len(tuple1) == len(tuple2)).
1929            def g(value, first=[1]):
1930                if first:
1931                    del first[:]
1932                    f(next(z))
1933                return value
1934            items = list(tuple2)
1935            items[1:1] = list(tuple1)
1936            gen = map(g, items)
1937            z = zip(*[gen]*len(tuple1))
1938            next(z)
1939
1940        def f(t):
1941            global T
1942            T = t
1943            first[:] = list(T)
1944
1945        first = []
1946        mutatingtuple((1,2,3), f, (4,5,6))
1947        second = list(T)
1948        self.assertEqual(first, second)
1949
1950
1951    def test_sf_950057(self):
1952        # Make sure that chain() and cycle() catch exceptions immediately
1953        # rather than when shifting between input sources
1954
1955        def gen1():
1956            hist.append(0)
1957            yield 1
1958            hist.append(1)
1959            raise AssertionError
1960            hist.append(2)
1961
1962        def gen2(x):
1963            hist.append(3)
1964            yield 2
1965            hist.append(4)
1966
1967        hist = []
1968        self.assertRaises(AssertionError, list, chain(gen1(), gen2(False)))
1969        self.assertEqual(hist, [0,1])
1970
1971        hist = []
1972        self.assertRaises(AssertionError, list, chain(gen1(), gen2(True)))
1973        self.assertEqual(hist, [0,1])
1974
1975        hist = []
1976        self.assertRaises(AssertionError, list, cycle(gen1()))
1977        self.assertEqual(hist, [0,1])
1978
1979class SubclassWithKwargsTest(unittest.TestCase):
1980    def test_keywords_in_subclass(self):
1981        # count is not subclassable...
1982        for cls in (repeat, zip, filter, filterfalse, chain, map,
1983                    starmap, islice, takewhile, dropwhile, cycle, compress):
1984            class Subclass(cls):
1985                def __init__(self, newarg=None, *args):
1986                    cls.__init__(self, *args)
1987            try:
1988                Subclass(newarg=1)
1989            except TypeError as err:
1990                # we expect type errors because of wrong argument count
1991                self.assertNotIn("does not take keyword arguments", err.args[0])
1992
1993@support.cpython_only
1994class SizeofTest(unittest.TestCase):
1995    def setUp(self):
1996        self.ssize_t = struct.calcsize('n')
1997
1998    check_sizeof = support.check_sizeof
1999
2000    def test_product_sizeof(self):
2001        basesize = support.calcobjsize('3Pi')
2002        check = self.check_sizeof
2003        check(product('ab', '12'), basesize + 2 * self.ssize_t)
2004        check(product(*(('abc',) * 10)), basesize + 10 * self.ssize_t)
2005
2006    def test_combinations_sizeof(self):
2007        basesize = support.calcobjsize('3Pni')
2008        check = self.check_sizeof
2009        check(combinations('abcd', 3), basesize + 3 * self.ssize_t)
2010        check(combinations(range(10), 4), basesize + 4 * self.ssize_t)
2011
2012    def test_combinations_with_replacement_sizeof(self):
2013        cwr = combinations_with_replacement
2014        basesize = support.calcobjsize('3Pni')
2015        check = self.check_sizeof
2016        check(cwr('abcd', 3), basesize + 3 * self.ssize_t)
2017        check(cwr(range(10), 4), basesize + 4 * self.ssize_t)
2018
2019    def test_permutations_sizeof(self):
2020        basesize = support.calcobjsize('4Pni')
2021        check = self.check_sizeof
2022        check(permutations('abcd'),
2023              basesize + 4 * self.ssize_t + 4 * self.ssize_t)
2024        check(permutations('abcd', 3),
2025              basesize + 4 * self.ssize_t + 3 * self.ssize_t)
2026        check(permutations('abcde', 3),
2027              basesize + 5 * self.ssize_t + 3 * self.ssize_t)
2028        check(permutations(range(10), 4),
2029              basesize + 10 * self.ssize_t + 4 * self.ssize_t)
2030
2031
2032libreftest = """ Doctest for examples in the library reference: libitertools.tex
2033
2034
2035>>> amounts = [120.15, 764.05, 823.14]
2036>>> for checknum, amount in zip(count(1200), amounts):
2037...     print('Check %d is for $%.2f' % (checknum, amount))
2038...
2039Check 1200 is for $120.15
2040Check 1201 is for $764.05
2041Check 1202 is for $823.14
2042
2043>>> import operator
2044>>> for cube in map(operator.pow, range(1,4), repeat(3)):
2045...    print(cube)
2046...
20471
20488
204927
2050
2051>>> reportlines = ['EuroPython', 'Roster', '', 'alex', '', 'laura', '', 'martin', '', 'walter', '', 'samuele']
2052>>> for name in islice(reportlines, 3, None, 2):
2053...    print(name.title())
2054...
2055Alex
2056Laura
2057Martin
2058Walter
2059Samuele
2060
2061>>> from operator import itemgetter
2062>>> d = dict(a=1, b=2, c=1, d=2, e=1, f=2, g=3)
2063>>> di = sorted(sorted(d.items()), key=itemgetter(1))
2064>>> for k, g in groupby(di, itemgetter(1)):
2065...     print(k, list(map(itemgetter(0), g)))
2066...
20671 ['a', 'c', 'e']
20682 ['b', 'd', 'f']
20693 ['g']
2070
2071# Find runs of consecutive numbers using groupby.  The key to the solution
2072# is differencing with a range so that consecutive numbers all appear in
2073# same group.
2074>>> data = [ 1,  4,5,6, 10, 15,16,17,18, 22, 25,26,27,28]
2075>>> for k, g in groupby(enumerate(data), lambda t:t[0]-t[1]):
2076...     print(list(map(operator.itemgetter(1), g)))
2077...
2078[1]
2079[4, 5, 6]
2080[10]
2081[15, 16, 17, 18]
2082[22]
2083[25, 26, 27, 28]
2084
2085>>> def take(n, iterable):
2086...     "Return first n items of the iterable as a list"
2087...     return list(islice(iterable, n))
2088
2089>>> def enumerate(iterable, start=0):
2090...     return zip(count(start), iterable)
2091
2092>>> def tabulate(function, start=0):
2093...     "Return function(0), function(1), ..."
2094...     return map(function, count(start))
2095
2096>>> def nth(iterable, n, default=None):
2097...     "Returns the nth item or a default value"
2098...     return next(islice(iterable, n, None), default)
2099
2100>>> def all_equal(iterable):
2101...     "Returns True if all the elements are equal to each other"
2102...     g = groupby(iterable)
2103...     return next(g, True) and not next(g, False)
2104
2105>>> def quantify(iterable, pred=bool):
2106...     "Count how many times the predicate is true"
2107...     return sum(map(pred, iterable))
2108
2109>>> def padnone(iterable):
2110...     "Returns the sequence elements and then returns None indefinitely"
2111...     return chain(iterable, repeat(None))
2112
2113>>> def ncycles(iterable, n):
2114...     "Returns the sequence elements n times"
2115...     return chain(*repeat(iterable, n))
2116
2117>>> def dotproduct(vec1, vec2):
2118...     return sum(map(operator.mul, vec1, vec2))
2119
2120>>> def flatten(listOfLists):
2121...     return list(chain.from_iterable(listOfLists))
2122
2123>>> def repeatfunc(func, times=None, *args):
2124...     "Repeat calls to func with specified arguments."
2125...     "   Example:  repeatfunc(random.random)"
2126...     if times is None:
2127...         return starmap(func, repeat(args))
2128...     else:
2129...         return starmap(func, repeat(args, times))
2130
2131>>> def pairwise(iterable):
2132...     "s -> (s0,s1), (s1,s2), (s2, s3), ..."
2133...     a, b = tee(iterable)
2134...     try:
2135...         next(b)
2136...     except StopIteration:
2137...         pass
2138...     return zip(a, b)
2139
2140>>> def grouper(n, iterable, fillvalue=None):
2141...     "grouper(3, 'ABCDEFG', 'x') --> ABC DEF Gxx"
2142...     args = [iter(iterable)] * n
2143...     return zip_longest(*args, fillvalue=fillvalue)
2144
2145>>> def roundrobin(*iterables):
2146...     "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
2147...     # Recipe credited to George Sakkis
2148...     pending = len(iterables)
2149...     nexts = cycle(iter(it).__next__ for it in iterables)
2150...     while pending:
2151...         try:
2152...             for next in nexts:
2153...                 yield next()
2154...         except StopIteration:
2155...             pending -= 1
2156...             nexts = cycle(islice(nexts, pending))
2157
2158>>> def powerset(iterable):
2159...     "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
2160...     s = list(iterable)
2161...     return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
2162
2163>>> def unique_everseen(iterable, key=None):
2164...     "List unique elements, preserving order. Remember all elements ever seen."
2165...     # unique_everseen('AAAABBBCCDAABBB') --> A B C D
2166...     # unique_everseen('ABBCcAD', str.lower) --> A B C D
2167...     seen = set()
2168...     seen_add = seen.add
2169...     if key is None:
2170...         for element in iterable:
2171...             if element not in seen:
2172...                 seen_add(element)
2173...                 yield element
2174...     else:
2175...         for element in iterable:
2176...             k = key(element)
2177...             if k not in seen:
2178...                 seen_add(k)
2179...                 yield element
2180
2181>>> def unique_justseen(iterable, key=None):
2182...     "List unique elements, preserving order. Remember only the element just seen."
2183...     # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
2184...     # unique_justseen('ABBCcAD', str.lower) --> A B C A D
2185...     return map(next, map(itemgetter(1), groupby(iterable, key)))
2186
2187>>> def first_true(iterable, default=False, pred=None):
2188...     '''Returns the first true value in the iterable.
2189...
2190...     If no true value is found, returns *default*
2191...
2192...     If *pred* is not None, returns the first item
2193...     for which pred(item) is true.
2194...
2195...     '''
2196...     # first_true([a,b,c], x) --> a or b or c or x
2197...     # first_true([a,b], x, f) --> a if f(a) else b if f(b) else x
2198...     return next(filter(pred, iterable), default)
2199
2200This is not part of the examples but it tests to make sure the definitions
2201perform as purported.
2202
2203>>> take(10, count())
2204[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
2205
2206>>> list(enumerate('abc'))
2207[(0, 'a'), (1, 'b'), (2, 'c')]
2208
2209>>> list(islice(tabulate(lambda x: 2*x), 4))
2210[0, 2, 4, 6]
2211
2212>>> nth('abcde', 3)
2213'd'
2214
2215>>> nth('abcde', 9) is None
2216True
2217
2218>>> [all_equal(s) for s in ('', 'A', 'AAAA', 'AAAB', 'AAABA')]
2219[True, True, True, False, False]
2220
2221>>> quantify(range(99), lambda x: x%2==0)
222250
2223
2224>>> a = [[1, 2, 3], [4, 5, 6]]
2225>>> flatten(a)
2226[1, 2, 3, 4, 5, 6]
2227
2228>>> list(repeatfunc(pow, 5, 2, 3))
2229[8, 8, 8, 8, 8]
2230
2231>>> import random
2232>>> take(5, map(int, repeatfunc(random.random)))
2233[0, 0, 0, 0, 0]
2234
2235>>> list(pairwise('abcd'))
2236[('a', 'b'), ('b', 'c'), ('c', 'd')]
2237
2238>>> list(pairwise([]))
2239[]
2240
2241>>> list(pairwise('a'))
2242[]
2243
2244>>> list(islice(padnone('abc'), 0, 6))
2245['a', 'b', 'c', None, None, None]
2246
2247>>> list(ncycles('abc', 3))
2248['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c']
2249
2250>>> dotproduct([1,2,3], [4,5,6])
225132
2252
2253>>> list(grouper(3, 'abcdefg', 'x'))
2254[('a', 'b', 'c'), ('d', 'e', 'f'), ('g', 'x', 'x')]
2255
2256>>> list(roundrobin('abc', 'd', 'ef'))
2257['a', 'd', 'e', 'b', 'f', 'c']
2258
2259>>> list(powerset([1,2,3]))
2260[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
2261
2262>>> all(len(list(powerset(range(n)))) == 2**n for n in range(18))
2263True
2264
2265>>> list(powerset('abcde')) == sorted(sorted(set(powerset('abcde'))), key=len)
2266True
2267
2268>>> list(unique_everseen('AAAABBBCCDAABBB'))
2269['A', 'B', 'C', 'D']
2270
2271>>> list(unique_everseen('ABBCcAD', str.lower))
2272['A', 'B', 'C', 'D']
2273
2274>>> list(unique_justseen('AAAABBBCCDAABBB'))
2275['A', 'B', 'C', 'D', 'A', 'B']
2276
2277>>> list(unique_justseen('ABBCcAD', str.lower))
2278['A', 'B', 'C', 'A', 'D']
2279
2280>>> first_true('ABC0DEF1', '9', str.isdigit)
2281'0'
2282
2283"""
2284
2285__test__ = {'libreftest' : libreftest}
2286
2287def test_main(verbose=None):
2288    test_classes = (TestBasicOps, TestVariousIteratorArgs, TestGC,
2289                    RegressionTests, LengthTransparency,
2290                    SubclassWithKwargsTest, TestExamples,
2291                    SizeofTest)
2292    support.run_unittest(*test_classes)
2293
2294    # verify reference counting
2295    if verbose and hasattr(sys, "gettotalrefcount"):
2296        import gc
2297        counts = [None] * 5
2298        for i in range(len(counts)):
2299            support.run_unittest(*test_classes)
2300            gc.collect()
2301            counts[i] = sys.gettotalrefcount()
2302        print(counts)
2303
2304    # doctest the examples in the library reference
2305    support.run_doctest(sys.modules[__name__], verbose)
2306
2307if __name__ == "__main__":
2308    test_main(verbose=True)
2309