Python code coverage for Lib/test/test_deque.py

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