← Back to branch summary

~ubuntu-branches/ubuntu/trusty/python3.4/trusty-proposed

« back to all changes in this revision

Viewing changes to Lib/test/test_itertools.py

  • Committer: Package Import Robot
  • Author(s): Matthias Klose
  • Date: 2013-11-25 09:44:27 UTC
  • Revision ID: package-import@ubuntu.com-20131125094427-lzxj8ap5w01lmo7f
Tags: upstream-3.4~b1
Import upstream version 3.4~b1

Show diffs side-by-side

added added

removed removed

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