ยปCore Development>Code coverage>Lib/test/test_deque.py

Python code coverage for Lib/test/test_deque.py

#countcontent
1n/afrom collections import deque
2n/aimport unittest
3n/afrom test import support, seq_tests
4n/aimport gc
5n/aimport weakref
6n/aimport copy
7n/aimport pickle
8n/afrom io import StringIO
9n/aimport random
10n/aimport struct
11n/a
12n/aBIG = 100000
13n/a
14n/adef fail():
15n/a raise SyntaxError
16n/a yield 1
17n/a
18n/aclass BadCmp:
19n/a def __eq__(self, other):
20n/a raise RuntimeError
21n/a
22n/aclass MutateCmp:
23n/a def __init__(self, deque, result):
24n/a self.deque = deque
25n/a self.result = result
26n/a def __eq__(self, other):
27n/a self.deque.clear()
28n/a return self.result
29n/a
30n/aclass TestBasic(unittest.TestCase):
31n/a
32n/a def test_basics(self):
33n/a d = deque(range(-5125, -5000))
34n/a d.__init__(range(200))
35n/a for i in range(200, 400):
36n/a d.append(i)
37n/a for i in reversed(range(-200, 0)):
38n/a d.appendleft(i)
39n/a self.assertEqual(list(d), list(range(-200, 400)))
40n/a self.assertEqual(len(d), 600)
41n/a
42n/a left = [d.popleft() for i in range(250)]
43n/a self.assertEqual(left, list(range(-200, 50)))
44n/a self.assertEqual(list(d), list(range(50, 400)))
45n/a
46n/a right = [d.pop() for i in range(250)]
47n/a right.reverse()
48n/a self.assertEqual(right, list(range(150, 400)))
49n/a self.assertEqual(list(d), list(range(50, 150)))
50n/a
51n/a def test_maxlen(self):
52n/a self.assertRaises(ValueError, deque, 'abc', -1)
53n/a self.assertRaises(ValueError, deque, 'abc', -2)
54n/a it = iter(range(10))
55n/a d = deque(it, maxlen=3)
56n/a self.assertEqual(list(it), [])
57n/a self.assertEqual(repr(d), 'deque([7, 8, 9], maxlen=3)')
58n/a self.assertEqual(list(d), [7, 8, 9])
59n/a self.assertEqual(d, deque(range(10), 3))
60n/a d.append(10)
61n/a self.assertEqual(list(d), [8, 9, 10])
62n/a d.appendleft(7)
63n/a self.assertEqual(list(d), [7, 8, 9])
64n/a d.extend([10, 11])
65n/a self.assertEqual(list(d), [9, 10, 11])
66n/a d.extendleft([8, 7])
67n/a self.assertEqual(list(d), [7, 8, 9])
68n/a d = deque(range(200), maxlen=10)
69n/a d.append(d)
70n/a support.unlink(support.TESTFN)
71n/a fo = open(support.TESTFN, "w")
72n/a try:
73n/a fo.write(str(d))
74n/a fo.close()
75n/a fo = open(support.TESTFN, "r")
76n/a self.assertEqual(fo.read(), repr(d))
77n/a finally:
78n/a fo.close()
79n/a support.unlink(support.TESTFN)
80n/a
81n/a d = deque(range(10), maxlen=None)
82n/a self.assertEqual(repr(d), 'deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])')
83n/a fo = open(support.TESTFN, "w")
84n/a try:
85n/a fo.write(str(d))
86n/a fo.close()
87n/a fo = open(support.TESTFN, "r")
88n/a self.assertEqual(fo.read(), repr(d))
89n/a finally:
90n/a fo.close()
91n/a support.unlink(support.TESTFN)
92n/a
93n/a def test_maxlen_zero(self):
94n/a it = iter(range(100))
95n/a deque(it, maxlen=0)
96n/a self.assertEqual(list(it), [])
97n/a
98n/a it = iter(range(100))
99n/a d = deque(maxlen=0)
100n/a d.extend(it)
101n/a self.assertEqual(list(it), [])
102n/a
103n/a it = iter(range(100))
104n/a d = deque(maxlen=0)
105n/a d.extendleft(it)
106n/a self.assertEqual(list(it), [])
107n/a
108n/a def test_maxlen_attribute(self):
109n/a self.assertEqual(deque().maxlen, None)
110n/a self.assertEqual(deque('abc').maxlen, None)
111n/a self.assertEqual(deque('abc', maxlen=4).maxlen, 4)
112n/a self.assertEqual(deque('abc', maxlen=2).maxlen, 2)
113n/a self.assertEqual(deque('abc', maxlen=0).maxlen, 0)
114n/a with self.assertRaises(AttributeError):
115n/a d = deque('abc')
116n/a d.maxlen = 10
117n/a
118n/a def test_count(self):
119n/a for s in ('', 'abracadabra', 'simsalabim'*500+'abc'):
120n/a s = list(s)
121n/a d = deque(s)
122n/a for letter in 'abcdefghijklmnopqrstuvwxyz':
123n/a self.assertEqual(s.count(letter), d.count(letter), (s, d, letter))
124n/a self.assertRaises(TypeError, d.count) # too few args
125n/a self.assertRaises(TypeError, d.count, 1, 2) # too many args
126n/a class BadCompare:
127n/a def __eq__(self, other):
128n/a raise ArithmeticError
129n/a d = deque([1, 2, BadCompare(), 3])
130n/a self.assertRaises(ArithmeticError, d.count, 2)
131n/a d = deque([1, 2, 3])
132n/a self.assertRaises(ArithmeticError, d.count, BadCompare())
133n/a class MutatingCompare:
134n/a def __eq__(self, other):
135n/a self.d.pop()
136n/a return True
137n/a m = MutatingCompare()
138n/a d = deque([1, 2, 3, m, 4, 5])
139n/a m.d = d
140n/a self.assertRaises(RuntimeError, d.count, 3)
141n/a
142n/a # test issue11004
143n/a # block advance failed after rotation aligned elements on right side of block
144n/a d = deque([None]*16)
145n/a for i in range(len(d)):
146n/a d.rotate(-1)
147n/a d.rotate(1)
148n/a self.assertEqual(d.count(1), 0)
149n/a self.assertEqual(d.count(None), 16)
150n/a
151n/a def test_comparisons(self):
152n/a d = deque('xabc'); d.popleft()
153n/a for e in [d, deque('abc'), deque('ab'), deque(), list(d)]:
154n/a self.assertEqual(d==e, type(d)==type(e) and list(d)==list(e))
155n/a self.assertEqual(d!=e, not(type(d)==type(e) and list(d)==list(e)))
156n/a
157n/a args = map(deque, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba'))
158n/a for x in args:
159n/a for y in args:
160n/a self.assertEqual(x == y, list(x) == list(y), (x,y))
161n/a self.assertEqual(x != y, list(x) != list(y), (x,y))
162n/a self.assertEqual(x < y, list(x) < list(y), (x,y))
163n/a self.assertEqual(x <= y, list(x) <= list(y), (x,y))
164n/a self.assertEqual(x > y, list(x) > list(y), (x,y))
165n/a self.assertEqual(x >= y, list(x) >= list(y), (x,y))
166n/a
167n/a def test_contains(self):
168n/a n = 200
169n/a
170n/a d = deque(range(n))
171n/a for i in range(n):
172n/a self.assertTrue(i in d)
173n/a self.assertTrue((n+1) not in d)
174n/a
175n/a # Test detection of mutation during iteration
176n/a d = deque(range(n))
177n/a d[n//2] = MutateCmp(d, False)
178n/a with self.assertRaises(RuntimeError):
179n/a n in d
180n/a
181n/a # Test detection of comparison exceptions
182n/a d = deque(range(n))
183n/a d[n//2] = BadCmp()
184n/a with self.assertRaises(RuntimeError):
185n/a n in d
186n/a
187n/a def test_extend(self):
188n/a d = deque('a')
189n/a self.assertRaises(TypeError, d.extend, 1)
190n/a d.extend('bcd')
191n/a self.assertEqual(list(d), list('abcd'))
192n/a d.extend(d)
193n/a self.assertEqual(list(d), list('abcdabcd'))
194n/a
195n/a def test_add(self):
196n/a d = deque()
197n/a e = deque('abc')
198n/a f = deque('def')
199n/a self.assertEqual(d + d, deque())
200n/a self.assertEqual(e + f, deque('abcdef'))
201n/a self.assertEqual(e + e, deque('abcabc'))
202n/a self.assertEqual(e + d, deque('abc'))
203n/a self.assertEqual(d + e, deque('abc'))
204n/a self.assertIsNot(d + d, deque())
205n/a self.assertIsNot(e + d, deque('abc'))
206n/a self.assertIsNot(d + e, deque('abc'))
207n/a
208n/a g = deque('abcdef', maxlen=4)
209n/a h = deque('gh')
210n/a self.assertEqual(g + h, deque('efgh'))
211n/a
212n/a with self.assertRaises(TypeError):
213n/a deque('abc') + 'def'
214n/a
215n/a def test_iadd(self):
216n/a d = deque('a')
217n/a d += 'bcd'
218n/a self.assertEqual(list(d), list('abcd'))
219n/a d += d
220n/a self.assertEqual(list(d), list('abcdabcd'))
221n/a
222n/a def test_extendleft(self):
223n/a d = deque('a')
224n/a self.assertRaises(TypeError, d.extendleft, 1)
225n/a d.extendleft('bcd')
226n/a self.assertEqual(list(d), list(reversed('abcd')))
227n/a d.extendleft(d)
228n/a self.assertEqual(list(d), list('abcddcba'))
229n/a d = deque()
230n/a d.extendleft(range(1000))
231n/a self.assertEqual(list(d), list(reversed(range(1000))))
232n/a self.assertRaises(SyntaxError, d.extendleft, fail())
233n/a
234n/a def test_getitem(self):
235n/a n = 200
236n/a d = deque(range(n))
237n/a l = list(range(n))
238n/a for i in range(n):
239n/a d.popleft()
240n/a l.pop(0)
241n/a if random.random() < 0.5:
242n/a d.append(i)
243n/a l.append(i)
244n/a for j in range(1-len(l), len(l)):
245n/a assert d[j] == l[j]
246n/a
247n/a d = deque('superman')
248n/a self.assertEqual(d[0], 's')
249n/a self.assertEqual(d[-1], 'n')
250n/a d = deque()
251n/a self.assertRaises(IndexError, d.__getitem__, 0)
252n/a self.assertRaises(IndexError, d.__getitem__, -1)
253n/a
254n/a def test_index(self):
255n/a for n in 1, 2, 30, 40, 200:
256n/a
257n/a d = deque(range(n))
258n/a for i in range(n):
259n/a self.assertEqual(d.index(i), i)
260n/a
261n/a with self.assertRaises(ValueError):
262n/a d.index(n+1)
263n/a
264n/a # Test detection of mutation during iteration
265n/a d = deque(range(n))
266n/a d[n//2] = MutateCmp(d, False)
267n/a with self.assertRaises(RuntimeError):
268n/a d.index(n)
269n/a
270n/a # Test detection of comparison exceptions
271n/a d = deque(range(n))
272n/a d[n//2] = BadCmp()
273n/a with self.assertRaises(RuntimeError):
274n/a d.index(n)
275n/a
276n/a # Test start and stop arguments behavior matches list.index()
277n/a elements = 'ABCDEFGHI'
278n/a nonelement = 'Z'
279n/a d = deque(elements * 2)
280n/a s = list(elements * 2)
281n/a for start in range(-5 - len(s)*2, 5 + len(s) * 2):
282n/a for stop in range(-5 - len(s)*2, 5 + len(s) * 2):
283n/a for element in elements + 'Z':
284n/a try:
285n/a target = s.index(element, start, stop)
286n/a except ValueError:
287n/a with self.assertRaises(ValueError):
288n/a d.index(element, start, stop)
289n/a else:
290n/a self.assertEqual(d.index(element, start, stop), target)
291n/a
292n/a def test_index_bug_24913(self):
293n/a d = deque('A' * 3)
294n/a with self.assertRaises(ValueError):
295n/a i = d.index("Hello world", 0, 4)
296n/a
297n/a def test_insert(self):
298n/a # Test to make sure insert behaves like lists
299n/a elements = 'ABCDEFGHI'
300n/a for i in range(-5 - len(elements)*2, 5 + len(elements) * 2):
301n/a d = deque('ABCDEFGHI')
302n/a s = list('ABCDEFGHI')
303n/a d.insert(i, 'Z')
304n/a s.insert(i, 'Z')
305n/a self.assertEqual(list(d), s)
306n/a
307n/a def test_insert_bug_26194(self):
308n/a data = 'ABC'
309n/a d = deque(data, maxlen=len(data))
310n/a with self.assertRaises(IndexError):
311n/a d.insert(2, None)
312n/a
313n/a elements = 'ABCDEFGHI'
314n/a for i in range(-len(elements), len(elements)):
315n/a d = deque(elements, maxlen=len(elements)+1)
316n/a d.insert(i, 'Z')
317n/a if i >= 0:
318n/a self.assertEqual(d[i], 'Z')
319n/a else:
320n/a self.assertEqual(d[i-1], 'Z')
321n/a
322n/a def test_imul(self):
323n/a for n in (-10, -1, 0, 1, 2, 10, 1000):
324n/a d = deque()
325n/a d *= n
326n/a self.assertEqual(d, deque())
327n/a self.assertIsNone(d.maxlen)
328n/a
329n/a for n in (-10, -1, 0, 1, 2, 10, 1000):
330n/a d = deque('a')
331n/a d *= n
332n/a self.assertEqual(d, deque('a' * n))
333n/a self.assertIsNone(d.maxlen)
334n/a
335n/a for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000):
336n/a d = deque('a', 500)
337n/a d *= n
338n/a self.assertEqual(d, deque('a' * min(n, 500)))
339n/a self.assertEqual(d.maxlen, 500)
340n/a
341n/a for n in (-10, -1, 0, 1, 2, 10, 1000):
342n/a d = deque('abcdef')
343n/a d *= n
344n/a self.assertEqual(d, deque('abcdef' * n))
345n/a self.assertIsNone(d.maxlen)
346n/a
347n/a for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000):
348n/a d = deque('abcdef', 500)
349n/a d *= n
350n/a self.assertEqual(d, deque(('abcdef' * n)[-500:]))
351n/a self.assertEqual(d.maxlen, 500)
352n/a
353n/a def test_mul(self):
354n/a d = deque('abc')
355n/a self.assertEqual(d * -5, deque())
356n/a self.assertEqual(d * 0, deque())
357n/a self.assertEqual(d * 1, deque('abc'))
358n/a self.assertEqual(d * 2, deque('abcabc'))
359n/a self.assertEqual(d * 3, deque('abcabcabc'))
360n/a self.assertIsNot(d * 1, d)
361n/a
362n/a self.assertEqual(deque() * 0, deque())
363n/a self.assertEqual(deque() * 1, deque())
364n/a self.assertEqual(deque() * 5, deque())
365n/a
366n/a self.assertEqual(-5 * d, deque())
367n/a self.assertEqual(0 * d, deque())
368n/a self.assertEqual(1 * d, deque('abc'))
369n/a self.assertEqual(2 * d, deque('abcabc'))
370n/a self.assertEqual(3 * d, deque('abcabcabc'))
371n/a
372n/a d = deque('abc', maxlen=5)
373n/a self.assertEqual(d * -5, deque())
374n/a self.assertEqual(d * 0, deque())
375n/a self.assertEqual(d * 1, deque('abc'))
376n/a self.assertEqual(d * 2, deque('bcabc'))
377n/a self.assertEqual(d * 30, deque('bcabc'))
378n/a
379n/a def test_setitem(self):
380n/a n = 200
381n/a d = deque(range(n))
382n/a for i in range(n):
383n/a d[i] = 10 * i
384n/a self.assertEqual(list(d), [10*i for i in range(n)])
385n/a l = list(d)
386n/a for i in range(1-n, 0, -1):
387n/a d[i] = 7*i
388n/a l[i] = 7*i
389n/a self.assertEqual(list(d), l)
390n/a
391n/a def test_delitem(self):
392n/a n = 500 # O(n**2) test, don't make this too big
393n/a d = deque(range(n))
394n/a self.assertRaises(IndexError, d.__delitem__, -n-1)
395n/a self.assertRaises(IndexError, d.__delitem__, n)
396n/a for i in range(n):
397n/a self.assertEqual(len(d), n-i)
398n/a j = random.randrange(-len(d), len(d))
399n/a val = d[j]
400n/a self.assertIn(val, d)
401n/a del d[j]
402n/a self.assertNotIn(val, d)
403n/a self.assertEqual(len(d), 0)
404n/a
405n/a def test_reverse(self):
406n/a n = 500 # O(n**2) test, don't make this too big
407n/a data = [random.random() for i in range(n)]
408n/a for i in range(n):
409n/a d = deque(data[:i])
410n/a r = d.reverse()
411n/a self.assertEqual(list(d), list(reversed(data[:i])))
412n/a self.assertIs(r, None)
413n/a d.reverse()
414n/a self.assertEqual(list(d), data[:i])
415n/a self.assertRaises(TypeError, d.reverse, 1) # Arity is zero
416n/a
417n/a def test_rotate(self):
418n/a s = tuple('abcde')
419n/a n = len(s)
420n/a
421n/a d = deque(s)
422n/a d.rotate(1) # verify rot(1)
423n/a self.assertEqual(''.join(d), 'eabcd')
424n/a
425n/a d = deque(s)
426n/a d.rotate(-1) # verify rot(-1)
427n/a self.assertEqual(''.join(d), 'bcdea')
428n/a d.rotate() # check default to 1
429n/a self.assertEqual(tuple(d), s)
430n/a
431n/a for i in range(n*3):
432n/a d = deque(s)
433n/a e = deque(d)
434n/a d.rotate(i) # check vs. rot(1) n times
435n/a for j in range(i):
436n/a e.rotate(1)
437n/a self.assertEqual(tuple(d), tuple(e))
438n/a d.rotate(-i) # check that it works in reverse
439n/a self.assertEqual(tuple(d), s)
440n/a e.rotate(n-i) # check that it wraps forward
441n/a self.assertEqual(tuple(e), s)
442n/a
443n/a for i in range(n*3):
444n/a d = deque(s)
445n/a e = deque(d)
446n/a d.rotate(-i)
447n/a for j in range(i):
448n/a e.rotate(-1) # check vs. rot(-1) n times
449n/a self.assertEqual(tuple(d), tuple(e))
450n/a d.rotate(i) # check that it works in reverse
451n/a self.assertEqual(tuple(d), s)
452n/a e.rotate(i-n) # check that it wraps backaround
453n/a self.assertEqual(tuple(e), s)
454n/a
455n/a d = deque(s)
456n/a e = deque(s)
457n/a e.rotate(BIG+17) # verify on long series of rotates
458n/a dr = d.rotate
459n/a for i in range(BIG+17):
460n/a dr()
461n/a self.assertEqual(tuple(d), tuple(e))
462n/a
463n/a self.assertRaises(TypeError, d.rotate, 'x') # Wrong arg type
464n/a self.assertRaises(TypeError, d.rotate, 1, 10) # Too many args
465n/a
466n/a d = deque()
467n/a d.rotate() # rotate an empty deque
468n/a self.assertEqual(d, deque())
469n/a
470n/a def test_len(self):
471n/a d = deque('ab')
472n/a self.assertEqual(len(d), 2)
473n/a d.popleft()
474n/a self.assertEqual(len(d), 1)
475n/a d.pop()
476n/a self.assertEqual(len(d), 0)
477n/a self.assertRaises(IndexError, d.pop)
478n/a self.assertEqual(len(d), 0)
479n/a d.append('c')
480n/a self.assertEqual(len(d), 1)
481n/a d.appendleft('d')
482n/a self.assertEqual(len(d), 2)
483n/a d.clear()
484n/a self.assertEqual(len(d), 0)
485n/a
486n/a def test_underflow(self):
487n/a d = deque()
488n/a self.assertRaises(IndexError, d.pop)
489n/a self.assertRaises(IndexError, d.popleft)
490n/a
491n/a def test_clear(self):
492n/a d = deque(range(100))
493n/a self.assertEqual(len(d), 100)
494n/a d.clear()
495n/a self.assertEqual(len(d), 0)
496n/a self.assertEqual(list(d), [])
497n/a d.clear() # clear an empty deque
498n/a self.assertEqual(list(d), [])
499n/a
500n/a def test_remove(self):
501n/a d = deque('abcdefghcij')
502n/a d.remove('c')
503n/a self.assertEqual(d, deque('abdefghcij'))
504n/a d.remove('c')
505n/a self.assertEqual(d, deque('abdefghij'))
506n/a self.assertRaises(ValueError, d.remove, 'c')
507n/a self.assertEqual(d, deque('abdefghij'))
508n/a
509n/a # Handle comparison errors
510n/a d = deque(['a', 'b', BadCmp(), 'c'])
511n/a e = deque(d)
512n/a self.assertRaises(RuntimeError, d.remove, 'c')
513n/a for x, y in zip(d, e):
514n/a # verify that original order and values are retained.
515n/a self.assertTrue(x is y)
516n/a
517n/a # Handle evil mutator
518n/a for match in (True, False):
519n/a d = deque(['ab'])
520n/a d.extend([MutateCmp(d, match), 'c'])
521n/a self.assertRaises(IndexError, d.remove, 'c')
522n/a self.assertEqual(d, deque())
523n/a
524n/a def test_repr(self):
525n/a d = deque(range(200))
526n/a e = eval(repr(d))
527n/a self.assertEqual(list(d), list(e))
528n/a d.append(d)
529n/a self.assertIn('...', repr(d))
530n/a
531n/a def test_print(self):
532n/a d = deque(range(200))
533n/a d.append(d)
534n/a try:
535n/a support.unlink(support.TESTFN)
536n/a fo = open(support.TESTFN, "w")
537n/a print(d, file=fo, end='')
538n/a fo.close()
539n/a fo = open(support.TESTFN, "r")
540n/a self.assertEqual(fo.read(), repr(d))
541n/a finally:
542n/a fo.close()
543n/a support.unlink(support.TESTFN)
544n/a
545n/a def test_init(self):
546n/a self.assertRaises(TypeError, deque, 'abc', 2, 3);
547n/a self.assertRaises(TypeError, deque, 1);
548n/a
549n/a def test_hash(self):
550n/a self.assertRaises(TypeError, hash, deque('abc'))
551n/a
552n/a def test_long_steadystate_queue_popleft(self):
553n/a for size in (0, 1, 2, 100, 1000):
554n/a d = deque(range(size))
555n/a append, pop = d.append, d.popleft
556n/a for i in range(size, BIG):
557n/a append(i)
558n/a x = pop()
559n/a if x != i - size:
560n/a self.assertEqual(x, i-size)
561n/a self.assertEqual(list(d), list(range(BIG-size, BIG)))
562n/a
563n/a def test_long_steadystate_queue_popright(self):
564n/a for size in (0, 1, 2, 100, 1000):
565n/a d = deque(reversed(range(size)))
566n/a append, pop = d.appendleft, d.pop
567n/a for i in range(size, BIG):
568n/a append(i)
569n/a x = pop()
570n/a if x != i - size:
571n/a self.assertEqual(x, i-size)
572n/a self.assertEqual(list(reversed(list(d))),
573n/a list(range(BIG-size, BIG)))
574n/a
575n/a def test_big_queue_popleft(self):
576n/a pass
577n/a d = deque()
578n/a append, pop = d.append, d.popleft
579n/a for i in range(BIG):
580n/a append(i)
581n/a for i in range(BIG):
582n/a x = pop()
583n/a if x != i:
584n/a self.assertEqual(x, i)
585n/a
586n/a def test_big_queue_popright(self):
587n/a d = deque()
588n/a append, pop = d.appendleft, d.pop
589n/a for i in range(BIG):
590n/a append(i)
591n/a for i in range(BIG):
592n/a x = pop()
593n/a if x != i:
594n/a self.assertEqual(x, i)
595n/a
596n/a def test_big_stack_right(self):
597n/a d = deque()
598n/a append, pop = d.append, d.pop
599n/a for i in range(BIG):
600n/a append(i)
601n/a for i in reversed(range(BIG)):
602n/a x = pop()
603n/a if x != i:
604n/a self.assertEqual(x, i)
605n/a self.assertEqual(len(d), 0)
606n/a
607n/a def test_big_stack_left(self):
608n/a d = deque()
609n/a append, pop = d.appendleft, d.popleft
610n/a for i in range(BIG):
611n/a append(i)
612n/a for i in reversed(range(BIG)):
613n/a x = pop()
614n/a if x != i:
615n/a self.assertEqual(x, i)
616n/a self.assertEqual(len(d), 0)
617n/a
618n/a def test_roundtrip_iter_init(self):
619n/a d = deque(range(200))
620n/a e = deque(d)
621n/a self.assertNotEqual(id(d), id(e))
622n/a self.assertEqual(list(d), list(e))
623n/a
624n/a def test_pickle(self):
625n/a for d in deque(range(200)), deque(range(200), 100):
626n/a for i in range(pickle.HIGHEST_PROTOCOL + 1):
627n/a s = pickle.dumps(d, i)
628n/a e = pickle.loads(s)
629n/a self.assertNotEqual(id(e), id(d))
630n/a self.assertEqual(list(e), list(d))
631n/a self.assertEqual(e.maxlen, d.maxlen)
632n/a
633n/a def test_pickle_recursive(self):
634n/a for d in deque('abc'), deque('abc', 3):
635n/a d.append(d)
636n/a for i in range(pickle.HIGHEST_PROTOCOL + 1):
637n/a e = pickle.loads(pickle.dumps(d, i))
638n/a self.assertNotEqual(id(e), id(d))
639n/a self.assertEqual(id(e[-1]), id(e))
640n/a self.assertEqual(e.maxlen, d.maxlen)
641n/a
642n/a def test_iterator_pickle(self):
643n/a orig = deque(range(200))
644n/a data = [i*1.01 for i in orig]
645n/a for proto in range(pickle.HIGHEST_PROTOCOL + 1):
646n/a # initial iterator
647n/a itorg = iter(orig)
648n/a dump = pickle.dumps((itorg, orig), proto)
649n/a it, d = pickle.loads(dump)
650n/a for i, x in enumerate(data):
651n/a d[i] = x
652n/a self.assertEqual(type(it), type(itorg))
653n/a self.assertEqual(list(it), data)
654n/a
655n/a # running iterator
656n/a next(itorg)
657n/a dump = pickle.dumps((itorg, orig), proto)
658n/a it, d = pickle.loads(dump)
659n/a for i, x in enumerate(data):
660n/a d[i] = x
661n/a self.assertEqual(type(it), type(itorg))
662n/a self.assertEqual(list(it), data[1:])
663n/a
664n/a # empty iterator
665n/a for i in range(1, len(data)):
666n/a next(itorg)
667n/a dump = pickle.dumps((itorg, orig), proto)
668n/a it, d = pickle.loads(dump)
669n/a for i, x in enumerate(data):
670n/a d[i] = x
671n/a self.assertEqual(type(it), type(itorg))
672n/a self.assertEqual(list(it), [])
673n/a
674n/a # exhausted iterator
675n/a self.assertRaises(StopIteration, next, itorg)
676n/a dump = pickle.dumps((itorg, orig), proto)
677n/a it, d = pickle.loads(dump)
678n/a for i, x in enumerate(data):
679n/a d[i] = x
680n/a self.assertEqual(type(it), type(itorg))
681n/a self.assertEqual(list(it), [])
682n/a
683n/a def test_deepcopy(self):
684n/a mut = [10]
685n/a d = deque([mut])
686n/a e = copy.deepcopy(d)
687n/a self.assertEqual(list(d), list(e))
688n/a mut[0] = 11
689n/a self.assertNotEqual(id(d), id(e))
690n/a self.assertNotEqual(list(d), list(e))
691n/a
692n/a def test_copy(self):
693n/a mut = [10]
694n/a d = deque([mut])
695n/a e = copy.copy(d)
696n/a self.assertEqual(list(d), list(e))
697n/a mut[0] = 11
698n/a self.assertNotEqual(id(d), id(e))
699n/a self.assertEqual(list(d), list(e))
700n/a
701n/a for i in range(5):
702n/a for maxlen in range(-1, 6):
703n/a s = [random.random() for j in range(i)]
704n/a d = deque(s) if maxlen == -1 else deque(s, maxlen)
705n/a e = d.copy()
706n/a self.assertEqual(d, e)
707n/a self.assertEqual(d.maxlen, e.maxlen)
708n/a self.assertTrue(all(x is y for x, y in zip(d, e)))
709n/a
710n/a def test_copy_method(self):
711n/a mut = [10]
712n/a d = deque([mut])
713n/a e = d.copy()
714n/a self.assertEqual(list(d), list(e))
715n/a mut[0] = 11
716n/a self.assertNotEqual(id(d), id(e))
717n/a self.assertEqual(list(d), list(e))
718n/a
719n/a def test_reversed(self):
720n/a for s in ('abcd', range(2000)):
721n/a self.assertEqual(list(reversed(deque(s))), list(reversed(s)))
722n/a
723n/a def test_reversed_new(self):
724n/a klass = type(reversed(deque()))
725n/a for s in ('abcd', range(2000)):
726n/a self.assertEqual(list(klass(deque(s))), list(reversed(s)))
727n/a
728n/a def test_gc_doesnt_blowup(self):
729n/a import gc
730n/a # This used to assert-fail in deque_traverse() under a debug
731n/a # build, or run wild with a NULL pointer in a release build.
732n/a d = deque()
733n/a for i in range(100):
734n/a d.append(1)
735n/a gc.collect()
736n/a
737n/a def test_container_iterator(self):
738n/a # Bug #3680: tp_traverse was not implemented for deque iterator objects
739n/a class C(object):
740n/a pass
741n/a for i in range(2):
742n/a obj = C()
743n/a ref = weakref.ref(obj)
744n/a if i == 0:
745n/a container = deque([obj, 1])
746n/a else:
747n/a container = reversed(deque([obj, 1]))
748n/a obj.x = iter(container)
749n/a del obj, container
750n/a gc.collect()
751n/a self.assertTrue(ref() is None, "Cycle was not collected")
752n/a
753n/a check_sizeof = support.check_sizeof
754n/a
755n/a @support.cpython_only
756n/a def test_sizeof(self):
757n/a BLOCKLEN = 64
758n/a basesize = support.calcvobjsize('2P4nP')
759n/a blocksize = struct.calcsize('P%dPP' % BLOCKLEN)
760n/a self.assertEqual(object.__sizeof__(deque()), basesize)
761n/a check = self.check_sizeof
762n/a check(deque(), basesize + blocksize)
763n/a check(deque('a'), basesize + blocksize)
764n/a check(deque('a' * (BLOCKLEN - 1)), basesize + blocksize)
765n/a check(deque('a' * BLOCKLEN), basesize + 2 * blocksize)
766n/a check(deque('a' * (42 * BLOCKLEN)), basesize + 43 * blocksize)
767n/a
768n/aclass TestVariousIteratorArgs(unittest.TestCase):
769n/a
770n/a def test_constructor(self):
771n/a for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
772n/a for g in (seq_tests.Sequence, seq_tests.IterFunc,
773n/a seq_tests.IterGen, seq_tests.IterFuncStop,
774n/a seq_tests.itermulti, seq_tests.iterfunc):
775n/a self.assertEqual(list(deque(g(s))), list(g(s)))
776n/a self.assertRaises(TypeError, deque, seq_tests.IterNextOnly(s))
777n/a self.assertRaises(TypeError, deque, seq_tests.IterNoNext(s))
778n/a self.assertRaises(ZeroDivisionError, deque, seq_tests.IterGenExc(s))
779n/a
780n/a def test_iter_with_altered_data(self):
781n/a d = deque('abcdefg')
782n/a it = iter(d)
783n/a d.pop()
784n/a self.assertRaises(RuntimeError, next, it)
785n/a
786n/a def test_runtime_error_on_empty_deque(self):
787n/a d = deque()
788n/a it = iter(d)
789n/a d.append(10)
790n/a self.assertRaises(RuntimeError, next, it)
791n/a
792n/aclass Deque(deque):
793n/a pass
794n/a
795n/aclass DequeWithBadIter(deque):
796n/a def __iter__(self):
797n/a raise TypeError
798n/a
799n/aclass TestSubclass(unittest.TestCase):
800n/a
801n/a def test_basics(self):
802n/a d = Deque(range(25))
803n/a d.__init__(range(200))
804n/a for i in range(200, 400):
805n/a d.append(i)
806n/a for i in reversed(range(-200, 0)):
807n/a d.appendleft(i)
808n/a self.assertEqual(list(d), list(range(-200, 400)))
809n/a self.assertEqual(len(d), 600)
810n/a
811n/a left = [d.popleft() for i in range(250)]
812n/a self.assertEqual(left, list(range(-200, 50)))
813n/a self.assertEqual(list(d), list(range(50, 400)))
814n/a
815n/a right = [d.pop() for i in range(250)]
816n/a right.reverse()
817n/a self.assertEqual(right, list(range(150, 400)))
818n/a self.assertEqual(list(d), list(range(50, 150)))
819n/a
820n/a d.clear()
821n/a self.assertEqual(len(d), 0)
822n/a
823n/a def test_copy_pickle(self):
824n/a
825n/a d = Deque('abc')
826n/a
827n/a e = d.__copy__()
828n/a self.assertEqual(type(d), type(e))
829n/a self.assertEqual(list(d), list(e))
830n/a
831n/a e = Deque(d)
832n/a self.assertEqual(type(d), type(e))
833n/a self.assertEqual(list(d), list(e))
834n/a
835n/a for proto in range(pickle.HIGHEST_PROTOCOL + 1):
836n/a s = pickle.dumps(d, proto)
837n/a e = pickle.loads(s)
838n/a self.assertNotEqual(id(d), id(e))
839n/a self.assertEqual(type(d), type(e))
840n/a self.assertEqual(list(d), list(e))
841n/a
842n/a d = Deque('abcde', maxlen=4)
843n/a
844n/a e = d.__copy__()
845n/a self.assertEqual(type(d), type(e))
846n/a self.assertEqual(list(d), list(e))
847n/a
848n/a e = Deque(d)
849n/a self.assertEqual(type(d), type(e))
850n/a self.assertEqual(list(d), list(e))
851n/a
852n/a for proto in range(pickle.HIGHEST_PROTOCOL + 1):
853n/a s = pickle.dumps(d, proto)
854n/a e = pickle.loads(s)
855n/a self.assertNotEqual(id(d), id(e))
856n/a self.assertEqual(type(d), type(e))
857n/a self.assertEqual(list(d), list(e))
858n/a
859n/a def test_pickle_recursive(self):
860n/a for proto in range(pickle.HIGHEST_PROTOCOL + 1):
861n/a for d in Deque('abc'), Deque('abc', 3):
862n/a d.append(d)
863n/a
864n/a e = pickle.loads(pickle.dumps(d, proto))
865n/a self.assertNotEqual(id(e), id(d))
866n/a self.assertEqual(type(e), type(d))
867n/a self.assertEqual(e.maxlen, d.maxlen)
868n/a dd = d.pop()
869n/a ee = e.pop()
870n/a self.assertEqual(id(ee), id(e))
871n/a self.assertEqual(e, d)
872n/a
873n/a d.x = d
874n/a e = pickle.loads(pickle.dumps(d, proto))
875n/a self.assertEqual(id(e.x), id(e))
876n/a
877n/a for d in DequeWithBadIter('abc'), DequeWithBadIter('abc', 2):
878n/a self.assertRaises(TypeError, pickle.dumps, d, proto)
879n/a
880n/a def test_weakref(self):
881n/a d = deque('gallahad')
882n/a p = weakref.proxy(d)
883n/a self.assertEqual(str(p), str(d))
884n/a d = None
885n/a self.assertRaises(ReferenceError, str, p)
886n/a
887n/a def test_strange_subclass(self):
888n/a class X(deque):
889n/a def __iter__(self):
890n/a return iter([])
891n/a d1 = X([1,2,3])
892n/a d2 = X([4,5,6])
893n/a d1 == d2 # not clear if this is supposed to be True or False,
894n/a # but it used to give a SystemError
895n/a
896n/a
897n/aclass SubclassWithKwargs(deque):
898n/a def __init__(self, newarg=1):
899n/a deque.__init__(self)
900n/a
901n/aclass TestSubclassWithKwargs(unittest.TestCase):
902n/a def test_subclass_with_kwargs(self):
903n/a # SF bug #1486663 -- this used to erroneously raise a TypeError
904n/a SubclassWithKwargs(newarg=1)
905n/a
906n/aclass TestSequence(seq_tests.CommonTest):
907n/a type2test = deque
908n/a
909n/a def test_getitem(self):
910n/a # For now, bypass tests that require slicing
911n/a pass
912n/a
913n/a def test_getslice(self):
914n/a # For now, bypass tests that require slicing
915n/a pass
916n/a
917n/a def test_subscript(self):
918n/a # For now, bypass tests that require slicing
919n/a pass
920n/a
921n/a def test_free_after_iterating(self):
922n/a # For now, bypass tests that require slicing
923n/a self.skipTest("Exhausted deque iterator doesn't free a deque")
924n/a
925n/a#==============================================================================
926n/a
927n/alibreftest = """
928n/aExample from the Library Reference: Doc/lib/libcollections.tex
929n/a
930n/a>>> from collections import deque
931n/a>>> d = deque('ghi') # make a new deque with three items
932n/a>>> for elem in d: # iterate over the deque's elements
933n/a... print(elem.upper())
934n/aG
935n/aH
936n/aI
937n/a>>> d.append('j') # add a new entry to the right side
938n/a>>> d.appendleft('f') # add a new entry to the left side
939n/a>>> d # show the representation of the deque
940n/adeque(['f', 'g', 'h', 'i', 'j'])
941n/a>>> d.pop() # return and remove the rightmost item
942n/a'j'
943n/a>>> d.popleft() # return and remove the leftmost item
944n/a'f'
945n/a>>> list(d) # list the contents of the deque
946n/a['g', 'h', 'i']
947n/a>>> d[0] # peek at leftmost item
948n/a'g'
949n/a>>> d[-1] # peek at rightmost item
950n/a'i'
951n/a>>> list(reversed(d)) # list the contents of a deque in reverse
952n/a['i', 'h', 'g']
953n/a>>> 'h' in d # search the deque
954n/aTrue
955n/a>>> d.extend('jkl') # add multiple elements at once
956n/a>>> d
957n/adeque(['g', 'h', 'i', 'j', 'k', 'l'])
958n/a>>> d.rotate(1) # right rotation
959n/a>>> d
960n/adeque(['l', 'g', 'h', 'i', 'j', 'k'])
961n/a>>> d.rotate(-1) # left rotation
962n/a>>> d
963n/adeque(['g', 'h', 'i', 'j', 'k', 'l'])
964n/a>>> deque(reversed(d)) # make a new deque in reverse order
965n/adeque(['l', 'k', 'j', 'i', 'h', 'g'])
966n/a>>> d.clear() # empty the deque
967n/a>>> d.pop() # cannot pop from an empty deque
968n/aTraceback (most recent call last):
969n/a File "<pyshell#6>", line 1, in -toplevel-
970n/a d.pop()
971n/aIndexError: pop from an empty deque
972n/a
973n/a>>> d.extendleft('abc') # extendleft() reverses the input order
974n/a>>> d
975n/adeque(['c', 'b', 'a'])
976n/a
977n/a
978n/a
979n/a>>> def delete_nth(d, n):
980n/a... d.rotate(-n)
981n/a... d.popleft()
982n/a... d.rotate(n)
983n/a...
984n/a>>> d = deque('abcdef')
985n/a>>> delete_nth(d, 2) # remove the entry at d[2]
986n/a>>> d
987n/adeque(['a', 'b', 'd', 'e', 'f'])
988n/a
989n/a
990n/a
991n/a>>> def roundrobin(*iterables):
992n/a... pending = deque(iter(i) for i in iterables)
993n/a... while pending:
994n/a... task = pending.popleft()
995n/a... try:
996n/a... yield next(task)
997n/a... except StopIteration:
998n/a... continue
999n/a... pending.append(task)
1000n/a...
1001n/a
1002n/a>>> for value in roundrobin('abc', 'd', 'efgh'):
1003n/a... print(value)
1004n/a...
1005n/aa
1006n/ad
1007n/ae
1008n/ab
1009n/af
1010n/ac
1011n/ag
1012n/ah
1013n/a
1014n/a
1015n/a>>> def maketree(iterable):
1016n/a... d = deque(iterable)
1017n/a... while len(d) > 1:
1018n/a... pair = [d.popleft(), d.popleft()]
1019n/a... d.append(pair)
1020n/a... return list(d)
1021n/a...
1022n/a>>> print(maketree('abcdefgh'))
1023n/a[[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]]
1024n/a
1025n/a"""
1026n/a
1027n/a
1028n/a#==============================================================================
1029n/a
1030n/a__test__ = {'libreftest' : libreftest}
1031n/a
1032n/adef test_main(verbose=None):
1033n/a import sys
1034n/a test_classes = (
1035n/a TestBasic,
1036n/a TestVariousIteratorArgs,
1037n/a TestSubclass,
1038n/a TestSubclassWithKwargs,
1039n/a TestSequence,
1040n/a )
1041n/a
1042n/a support.run_unittest(*test_classes)
1043n/a
1044n/a # verify reference counting
1045n/a if verbose and hasattr(sys, "gettotalrefcount"):
1046n/a import gc
1047n/a counts = [None] * 5
1048n/a for i in range(len(counts)):
1049n/a support.run_unittest(*test_classes)
1050n/a gc.collect()
1051n/a counts[i] = sys.gettotalrefcount()
1052n/a print(counts)
1053n/a
1054n/a # doctests
1055n/a from test import test_deque
1056n/a support.run_doctest(test_deque, verbose)
1057n/a
1058n/aif __name__ == "__main__":
1059n/a test_main(verbose=True)