Commit | Line | Data |
---|---|---|
86530b38 AT |
1 | from collections import deque |
2 | import unittest | |
3 | from test import test_support | |
4 | from weakref import proxy | |
5 | import copy | |
6 | import cPickle as pickle | |
7 | from cStringIO import StringIO | |
8 | import random | |
9 | import os | |
10 | ||
11 | BIG = 100000 | |
12 | ||
13 | def fail(): | |
14 | raise SyntaxError | |
15 | yield 1 | |
16 | ||
17 | class TestBasic(unittest.TestCase): | |
18 | ||
19 | def test_basics(self): | |
20 | d = deque(xrange(100)) | |
21 | d.__init__(xrange(100, 200)) | |
22 | for i in xrange(200, 400): | |
23 | d.append(i) | |
24 | for i in reversed(xrange(-200, 0)): | |
25 | d.appendleft(i) | |
26 | self.assertEqual(list(d), range(-200, 400)) | |
27 | self.assertEqual(len(d), 600) | |
28 | ||
29 | left = [d.popleft() for i in xrange(250)] | |
30 | self.assertEqual(left, range(-200, 50)) | |
31 | self.assertEqual(list(d), range(50, 400)) | |
32 | ||
33 | right = [d.pop() for i in xrange(250)] | |
34 | right.reverse() | |
35 | self.assertEqual(right, range(150, 400)) | |
36 | self.assertEqual(list(d), range(50, 150)) | |
37 | ||
38 | def test_comparisons(self): | |
39 | d = deque('xabc'); d.popleft() | |
40 | for e in [d, deque('abc'), deque('ab'), deque(), list(d)]: | |
41 | self.assertEqual(d==e, type(d)==type(e) and list(d)==list(e)) | |
42 | self.assertEqual(d!=e, not(type(d)==type(e) and list(d)==list(e))) | |
43 | ||
44 | args = map(deque, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba')) | |
45 | for x in args: | |
46 | for y in args: | |
47 | self.assertEqual(x == y, list(x) == list(y), (x,y)) | |
48 | self.assertEqual(x != y, list(x) != list(y), (x,y)) | |
49 | self.assertEqual(x < y, list(x) < list(y), (x,y)) | |
50 | self.assertEqual(x <= y, list(x) <= list(y), (x,y)) | |
51 | self.assertEqual(x > y, list(x) > list(y), (x,y)) | |
52 | self.assertEqual(x >= y, list(x) >= list(y), (x,y)) | |
53 | self.assertEqual(cmp(x,y), cmp(list(x),list(y)), (x,y)) | |
54 | ||
55 | def test_extend(self): | |
56 | d = deque('a') | |
57 | self.assertRaises(TypeError, d.extend, 1) | |
58 | d.extend('bcd') | |
59 | self.assertEqual(list(d), list('abcd')) | |
60 | ||
61 | def test_extendleft(self): | |
62 | d = deque('a') | |
63 | self.assertRaises(TypeError, d.extendleft, 1) | |
64 | d.extendleft('bcd') | |
65 | self.assertEqual(list(d), list(reversed('abcd'))) | |
66 | d = deque() | |
67 | d.extendleft(range(1000)) | |
68 | self.assertEqual(list(d), list(reversed(range(1000)))) | |
69 | self.assertRaises(SyntaxError, d.extendleft, fail()) | |
70 | ||
71 | def test_getitem(self): | |
72 | n = 200 | |
73 | d = deque(xrange(n)) | |
74 | l = range(n) | |
75 | for i in xrange(n): | |
76 | d.popleft() | |
77 | l.pop(0) | |
78 | if random.random() < 0.5: | |
79 | d.append(i) | |
80 | l.append(i) | |
81 | for j in xrange(1-len(l), len(l)): | |
82 | assert d[j] == l[j] | |
83 | ||
84 | d = deque('superman') | |
85 | self.assertEqual(d[0], 's') | |
86 | self.assertEqual(d[-1], 'n') | |
87 | d = deque() | |
88 | self.assertRaises(IndexError, d.__getitem__, 0) | |
89 | self.assertRaises(IndexError, d.__getitem__, -1) | |
90 | ||
91 | def test_setitem(self): | |
92 | n = 200 | |
93 | d = deque(xrange(n)) | |
94 | for i in xrange(n): | |
95 | d[i] = 10 * i | |
96 | self.assertEqual(list(d), [10*i for i in xrange(n)]) | |
97 | l = list(d) | |
98 | for i in xrange(1-n, 0, -1): | |
99 | d[i] = 7*i | |
100 | l[i] = 7*i | |
101 | self.assertEqual(list(d), l) | |
102 | ||
103 | def test_delitem(self): | |
104 | n = 500 # O(n**2) test, don't make this too big | |
105 | d = deque(xrange(n)) | |
106 | self.assertRaises(IndexError, d.__delitem__, -n-1) | |
107 | self.assertRaises(IndexError, d.__delitem__, n) | |
108 | for i in xrange(n): | |
109 | self.assertEqual(len(d), n-i) | |
110 | j = random.randrange(-len(d), len(d)) | |
111 | val = d[j] | |
112 | self.assert_(val in d) | |
113 | del d[j] | |
114 | self.assert_(val not in d) | |
115 | self.assertEqual(len(d), 0) | |
116 | ||
117 | def test_rotate(self): | |
118 | s = tuple('abcde') | |
119 | n = len(s) | |
120 | ||
121 | d = deque(s) | |
122 | d.rotate(1) # verify rot(1) | |
123 | self.assertEqual(''.join(d), 'eabcd') | |
124 | ||
125 | d = deque(s) | |
126 | d.rotate(-1) # verify rot(-1) | |
127 | self.assertEqual(''.join(d), 'bcdea') | |
128 | d.rotate() # check default to 1 | |
129 | self.assertEqual(tuple(d), s) | |
130 | ||
131 | for i in xrange(n*3): | |
132 | d = deque(s) | |
133 | e = deque(d) | |
134 | d.rotate(i) # check vs. rot(1) n times | |
135 | for j in xrange(i): | |
136 | e.rotate(1) | |
137 | self.assertEqual(tuple(d), tuple(e)) | |
138 | d.rotate(-i) # check that it works in reverse | |
139 | self.assertEqual(tuple(d), s) | |
140 | e.rotate(n-i) # check that it wraps forward | |
141 | self.assertEqual(tuple(e), s) | |
142 | ||
143 | for i in xrange(n*3): | |
144 | d = deque(s) | |
145 | e = deque(d) | |
146 | d.rotate(-i) | |
147 | for j in xrange(i): | |
148 | e.rotate(-1) # check vs. rot(-1) n times | |
149 | self.assertEqual(tuple(d), tuple(e)) | |
150 | d.rotate(i) # check that it works in reverse | |
151 | self.assertEqual(tuple(d), s) | |
152 | e.rotate(i-n) # check that it wraps backaround | |
153 | self.assertEqual(tuple(e), s) | |
154 | ||
155 | d = deque(s) | |
156 | e = deque(s) | |
157 | e.rotate(BIG+17) # verify on long series of rotates | |
158 | dr = d.rotate | |
159 | for i in xrange(BIG+17): | |
160 | dr() | |
161 | self.assertEqual(tuple(d), tuple(e)) | |
162 | ||
163 | self.assertRaises(TypeError, d.rotate, 'x') # Wrong arg type | |
164 | self.assertRaises(TypeError, d.rotate, 1, 10) # Too many args | |
165 | ||
166 | d = deque() | |
167 | d.rotate() # rotate an empty deque | |
168 | self.assertEqual(d, deque()) | |
169 | ||
170 | def test_len(self): | |
171 | d = deque('ab') | |
172 | self.assertEqual(len(d), 2) | |
173 | d.popleft() | |
174 | self.assertEqual(len(d), 1) | |
175 | d.pop() | |
176 | self.assertEqual(len(d), 0) | |
177 | self.assertRaises(IndexError, d.pop) | |
178 | self.assertEqual(len(d), 0) | |
179 | d.append('c') | |
180 | self.assertEqual(len(d), 1) | |
181 | d.appendleft('d') | |
182 | self.assertEqual(len(d), 2) | |
183 | d.clear() | |
184 | self.assertEqual(len(d), 0) | |
185 | ||
186 | def test_underflow(self): | |
187 | d = deque() | |
188 | self.assertRaises(IndexError, d.pop) | |
189 | self.assertRaises(IndexError, d.popleft) | |
190 | ||
191 | def test_clear(self): | |
192 | d = deque(xrange(100)) | |
193 | self.assertEqual(len(d), 100) | |
194 | d.clear() | |
195 | self.assertEqual(len(d), 0) | |
196 | self.assertEqual(list(d), []) | |
197 | d.clear() # clear an emtpy deque | |
198 | self.assertEqual(list(d), []) | |
199 | ||
200 | def test_repr(self): | |
201 | d = deque(xrange(200)) | |
202 | e = eval(repr(d)) | |
203 | self.assertEqual(list(d), list(e)) | |
204 | d.append(d) | |
205 | self.assert_('...' in repr(d)) | |
206 | ||
207 | def test_print(self): | |
208 | d = deque(xrange(200)) | |
209 | d.append(d) | |
210 | try: | |
211 | fo = open(test_support.TESTFN, "wb") | |
212 | print >> fo, d, | |
213 | fo.close() | |
214 | fo = open(test_support.TESTFN, "rb") | |
215 | self.assertEqual(fo.read(), repr(d)) | |
216 | finally: | |
217 | fo.close() | |
218 | os.remove(test_support.TESTFN) | |
219 | ||
220 | def test_init(self): | |
221 | self.assertRaises(TypeError, deque, 'abc', 2); | |
222 | self.assertRaises(TypeError, deque, 1); | |
223 | ||
224 | def test_hash(self): | |
225 | self.assertRaises(TypeError, hash, deque('abc')) | |
226 | ||
227 | def test_long_steadystate_queue_popleft(self): | |
228 | for size in (0, 1, 2, 100, 1000): | |
229 | d = deque(xrange(size)) | |
230 | append, pop = d.append, d.popleft | |
231 | for i in xrange(size, BIG): | |
232 | append(i) | |
233 | x = pop() | |
234 | if x != i - size: | |
235 | self.assertEqual(x, i-size) | |
236 | self.assertEqual(list(d), range(BIG-size, BIG)) | |
237 | ||
238 | def test_long_steadystate_queue_popright(self): | |
239 | for size in (0, 1, 2, 100, 1000): | |
240 | d = deque(reversed(xrange(size))) | |
241 | append, pop = d.appendleft, d.pop | |
242 | for i in xrange(size, BIG): | |
243 | append(i) | |
244 | x = pop() | |
245 | if x != i - size: | |
246 | self.assertEqual(x, i-size) | |
247 | self.assertEqual(list(reversed(list(d))), range(BIG-size, BIG)) | |
248 | ||
249 | def test_big_queue_popleft(self): | |
250 | pass | |
251 | d = deque() | |
252 | append, pop = d.append, d.popleft | |
253 | for i in xrange(BIG): | |
254 | append(i) | |
255 | for i in xrange(BIG): | |
256 | x = pop() | |
257 | if x != i: | |
258 | self.assertEqual(x, i) | |
259 | ||
260 | def test_big_queue_popright(self): | |
261 | d = deque() | |
262 | append, pop = d.appendleft, d.pop | |
263 | for i in xrange(BIG): | |
264 | append(i) | |
265 | for i in xrange(BIG): | |
266 | x = pop() | |
267 | if x != i: | |
268 | self.assertEqual(x, i) | |
269 | ||
270 | def test_big_stack_right(self): | |
271 | d = deque() | |
272 | append, pop = d.append, d.pop | |
273 | for i in xrange(BIG): | |
274 | append(i) | |
275 | for i in reversed(xrange(BIG)): | |
276 | x = pop() | |
277 | if x != i: | |
278 | self.assertEqual(x, i) | |
279 | self.assertEqual(len(d), 0) | |
280 | ||
281 | def test_big_stack_left(self): | |
282 | d = deque() | |
283 | append, pop = d.appendleft, d.popleft | |
284 | for i in xrange(BIG): | |
285 | append(i) | |
286 | for i in reversed(xrange(BIG)): | |
287 | x = pop() | |
288 | if x != i: | |
289 | self.assertEqual(x, i) | |
290 | self.assertEqual(len(d), 0) | |
291 | ||
292 | def test_roundtrip_iter_init(self): | |
293 | d = deque(xrange(200)) | |
294 | e = deque(d) | |
295 | self.assertNotEqual(id(d), id(e)) | |
296 | self.assertEqual(list(d), list(e)) | |
297 | ||
298 | def test_pickle(self): | |
299 | d = deque(xrange(200)) | |
300 | for i in (0, 1, 2): | |
301 | s = pickle.dumps(d, i) | |
302 | e = pickle.loads(s) | |
303 | self.assertNotEqual(id(d), id(e)) | |
304 | self.assertEqual(list(d), list(e)) | |
305 | ||
306 | def test_pickle_recursive(self): | |
307 | d = deque('abc') | |
308 | d.append(d) | |
309 | for i in (0, 1, 2): | |
310 | e = pickle.loads(pickle.dumps(d, i)) | |
311 | self.assertNotEqual(id(d), id(e)) | |
312 | self.assertEqual(id(e), id(e[-1])) | |
313 | ||
314 | def test_deepcopy(self): | |
315 | mut = [10] | |
316 | d = deque([mut]) | |
317 | e = copy.deepcopy(d) | |
318 | self.assertEqual(list(d), list(e)) | |
319 | mut[0] = 11 | |
320 | self.assertNotEqual(id(d), id(e)) | |
321 | self.assertNotEqual(list(d), list(e)) | |
322 | ||
323 | def test_copy(self): | |
324 | mut = [10] | |
325 | d = deque([mut]) | |
326 | e = copy.copy(d) | |
327 | self.assertEqual(list(d), list(e)) | |
328 | mut[0] = 11 | |
329 | self.assertNotEqual(id(d), id(e)) | |
330 | self.assertEqual(list(d), list(e)) | |
331 | ||
332 | def test_reversed(self): | |
333 | for s in ('abcd', xrange(2000)): | |
334 | self.assertEqual(list(reversed(deque(s))), list(reversed(s))) | |
335 | ||
336 | def test_gc_doesnt_blowup(self): | |
337 | import gc | |
338 | # This used to assert-fail in deque_traverse() under a debug | |
339 | # build, or run wild with a NULL pointer in a release build. | |
340 | d = deque() | |
341 | for i in xrange(100): | |
342 | d.append(1) | |
343 | gc.collect() | |
344 | ||
345 | def R(seqn): | |
346 | 'Regular generator' | |
347 | for i in seqn: | |
348 | yield i | |
349 | ||
350 | class G: | |
351 | 'Sequence using __getitem__' | |
352 | def __init__(self, seqn): | |
353 | self.seqn = seqn | |
354 | def __getitem__(self, i): | |
355 | return self.seqn[i] | |
356 | ||
357 | class I: | |
358 | 'Sequence using iterator protocol' | |
359 | def __init__(self, seqn): | |
360 | self.seqn = seqn | |
361 | self.i = 0 | |
362 | def __iter__(self): | |
363 | return self | |
364 | def next(self): | |
365 | if self.i >= len(self.seqn): raise StopIteration | |
366 | v = self.seqn[self.i] | |
367 | self.i += 1 | |
368 | return v | |
369 | ||
370 | class Ig: | |
371 | 'Sequence using iterator protocol defined with a generator' | |
372 | def __init__(self, seqn): | |
373 | self.seqn = seqn | |
374 | self.i = 0 | |
375 | def __iter__(self): | |
376 | for val in self.seqn: | |
377 | yield val | |
378 | ||
379 | class X: | |
380 | 'Missing __getitem__ and __iter__' | |
381 | def __init__(self, seqn): | |
382 | self.seqn = seqn | |
383 | self.i = 0 | |
384 | def next(self): | |
385 | if self.i >= len(self.seqn): raise StopIteration | |
386 | v = self.seqn[self.i] | |
387 | self.i += 1 | |
388 | return v | |
389 | ||
390 | class N: | |
391 | 'Iterator missing next()' | |
392 | def __init__(self, seqn): | |
393 | self.seqn = seqn | |
394 | self.i = 0 | |
395 | def __iter__(self): | |
396 | return self | |
397 | ||
398 | class E: | |
399 | 'Test propagation of exceptions' | |
400 | def __init__(self, seqn): | |
401 | self.seqn = seqn | |
402 | self.i = 0 | |
403 | def __iter__(self): | |
404 | return self | |
405 | def next(self): | |
406 | 3 // 0 | |
407 | ||
408 | class S: | |
409 | 'Test immediate stop' | |
410 | def __init__(self, seqn): | |
411 | pass | |
412 | def __iter__(self): | |
413 | return self | |
414 | def next(self): | |
415 | raise StopIteration | |
416 | ||
417 | from itertools import chain, imap | |
418 | def L(seqn): | |
419 | 'Test multiple tiers of iterators' | |
420 | return chain(imap(lambda x:x, R(Ig(G(seqn))))) | |
421 | ||
422 | ||
423 | class TestVariousIteratorArgs(unittest.TestCase): | |
424 | ||
425 | def test_constructor(self): | |
426 | for s in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)): | |
427 | for g in (G, I, Ig, S, L, R): | |
428 | self.assertEqual(list(deque(g(s))), list(g(s))) | |
429 | self.assertRaises(TypeError, deque, X(s)) | |
430 | self.assertRaises(TypeError, deque, N(s)) | |
431 | self.assertRaises(ZeroDivisionError, deque, E(s)) | |
432 | ||
433 | def test_iter_with_altered_data(self): | |
434 | d = deque('abcdefg') | |
435 | it = iter(d) | |
436 | d.pop() | |
437 | self.assertRaises(RuntimeError, it.next) | |
438 | ||
439 | class Deque(deque): | |
440 | pass | |
441 | ||
442 | class DequeWithBadIter(deque): | |
443 | def __iter__(self): | |
444 | raise TypeError | |
445 | ||
446 | class TestSubclass(unittest.TestCase): | |
447 | ||
448 | def test_basics(self): | |
449 | d = Deque(xrange(100)) | |
450 | d.__init__(xrange(100, 200)) | |
451 | for i in xrange(200, 400): | |
452 | d.append(i) | |
453 | for i in reversed(xrange(-200, 0)): | |
454 | d.appendleft(i) | |
455 | self.assertEqual(list(d), range(-200, 400)) | |
456 | self.assertEqual(len(d), 600) | |
457 | ||
458 | left = [d.popleft() for i in xrange(250)] | |
459 | self.assertEqual(left, range(-200, 50)) | |
460 | self.assertEqual(list(d), range(50, 400)) | |
461 | ||
462 | right = [d.pop() for i in xrange(250)] | |
463 | right.reverse() | |
464 | self.assertEqual(right, range(150, 400)) | |
465 | self.assertEqual(list(d), range(50, 150)) | |
466 | ||
467 | d.clear() | |
468 | self.assertEqual(len(d), 0) | |
469 | ||
470 | def test_copy_pickle(self): | |
471 | ||
472 | d = Deque('abc') | |
473 | ||
474 | e = d.__copy__() | |
475 | self.assertEqual(type(d), type(e)) | |
476 | self.assertEqual(list(d), list(e)) | |
477 | ||
478 | e = Deque(d) | |
479 | self.assertEqual(type(d), type(e)) | |
480 | self.assertEqual(list(d), list(e)) | |
481 | ||
482 | s = pickle.dumps(d) | |
483 | e = pickle.loads(s) | |
484 | self.assertNotEqual(id(d), id(e)) | |
485 | self.assertEqual(type(d), type(e)) | |
486 | self.assertEqual(list(d), list(e)) | |
487 | ||
488 | def test_pickle(self): | |
489 | d = Deque('abc') | |
490 | d.append(d) | |
491 | ||
492 | e = pickle.loads(pickle.dumps(d)) | |
493 | self.assertNotEqual(id(d), id(e)) | |
494 | self.assertEqual(type(d), type(e)) | |
495 | dd = d.pop() | |
496 | ee = e.pop() | |
497 | self.assertEqual(id(e), id(ee)) | |
498 | self.assertEqual(d, e) | |
499 | ||
500 | d.x = d | |
501 | e = pickle.loads(pickle.dumps(d)) | |
502 | self.assertEqual(id(e), id(e.x)) | |
503 | ||
504 | d = DequeWithBadIter('abc') | |
505 | self.assertRaises(TypeError, pickle.dumps, d) | |
506 | ||
507 | def test_weakref(self): | |
508 | d = deque('gallahad') | |
509 | p = proxy(d) | |
510 | self.assertEqual(str(p), str(d)) | |
511 | d = None | |
512 | self.assertRaises(ReferenceError, str, p) | |
513 | ||
514 | def test_strange_subclass(self): | |
515 | class X(deque): | |
516 | def __iter__(self): | |
517 | return iter([]) | |
518 | d1 = X([1,2,3]) | |
519 | d2 = X([4,5,6]) | |
520 | d1 == d2 # not clear if this is supposed to be True or False, | |
521 | # but it used to give a SystemError | |
522 | ||
523 | #============================================================================== | |
524 | ||
525 | libreftest = """ | |
526 | Example from the Library Reference: Doc/lib/libcollections.tex | |
527 | ||
528 | >>> from collections import deque | |
529 | >>> d = deque('ghi') # make a new deque with three items | |
530 | >>> for elem in d: # iterate over the deque's elements | |
531 | ... print elem.upper() | |
532 | G | |
533 | H | |
534 | I | |
535 | >>> d.append('j') # add a new entry to the right side | |
536 | >>> d.appendleft('f') # add a new entry to the left side | |
537 | >>> d # show the representation of the deque | |
538 | deque(['f', 'g', 'h', 'i', 'j']) | |
539 | >>> d.pop() # return and remove the rightmost item | |
540 | 'j' | |
541 | >>> d.popleft() # return and remove the leftmost item | |
542 | 'f' | |
543 | >>> list(d) # list the contents of the deque | |
544 | ['g', 'h', 'i'] | |
545 | >>> d[0] # peek at leftmost item | |
546 | 'g' | |
547 | >>> d[-1] # peek at rightmost item | |
548 | 'i' | |
549 | >>> list(reversed(d)) # list the contents of a deque in reverse | |
550 | ['i', 'h', 'g'] | |
551 | >>> 'h' in d # search the deque | |
552 | True | |
553 | >>> d.extend('jkl') # add multiple elements at once | |
554 | >>> d | |
555 | deque(['g', 'h', 'i', 'j', 'k', 'l']) | |
556 | >>> d.rotate(1) # right rotation | |
557 | >>> d | |
558 | deque(['l', 'g', 'h', 'i', 'j', 'k']) | |
559 | >>> d.rotate(-1) # left rotation | |
560 | >>> d | |
561 | deque(['g', 'h', 'i', 'j', 'k', 'l']) | |
562 | >>> deque(reversed(d)) # make a new deque in reverse order | |
563 | deque(['l', 'k', 'j', 'i', 'h', 'g']) | |
564 | >>> d.clear() # empty the deque | |
565 | >>> d.pop() # cannot pop from an empty deque | |
566 | Traceback (most recent call last): | |
567 | File "<pyshell#6>", line 1, in -toplevel- | |
568 | d.pop() | |
569 | IndexError: pop from an empty deque | |
570 | ||
571 | >>> d.extendleft('abc') # extendleft() reverses the input order | |
572 | >>> d | |
573 | deque(['c', 'b', 'a']) | |
574 | ||
575 | ||
576 | ||
577 | >>> def delete_nth(d, n): | |
578 | ... d.rotate(-n) | |
579 | ... d.popleft() | |
580 | ... d.rotate(n) | |
581 | ... | |
582 | >>> d = deque('abcdef') | |
583 | >>> delete_nth(d, 2) # remove the entry at d[2] | |
584 | >>> d | |
585 | deque(['a', 'b', 'd', 'e', 'f']) | |
586 | ||
587 | ||
588 | ||
589 | >>> def roundrobin(*iterables): | |
590 | ... pending = deque(iter(i) for i in iterables) | |
591 | ... while pending: | |
592 | ... task = pending.popleft() | |
593 | ... try: | |
594 | ... yield task.next() | |
595 | ... except StopIteration: | |
596 | ... continue | |
597 | ... pending.append(task) | |
598 | ... | |
599 | ||
600 | >>> for value in roundrobin('abc', 'd', 'efgh'): | |
601 | ... print value | |
602 | ... | |
603 | a | |
604 | d | |
605 | e | |
606 | b | |
607 | f | |
608 | c | |
609 | g | |
610 | h | |
611 | ||
612 | ||
613 | >>> def maketree(iterable): | |
614 | ... d = deque(iterable) | |
615 | ... while len(d) > 1: | |
616 | ... pair = [d.popleft(), d.popleft()] | |
617 | ... d.append(pair) | |
618 | ... return list(d) | |
619 | ... | |
620 | >>> print maketree('abcdefgh') | |
621 | [[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]] | |
622 | ||
623 | """ | |
624 | ||
625 | ||
626 | #============================================================================== | |
627 | ||
628 | __test__ = {'libreftest' : libreftest} | |
629 | ||
630 | def test_main(verbose=None): | |
631 | import sys | |
632 | test_classes = ( | |
633 | TestBasic, | |
634 | TestVariousIteratorArgs, | |
635 | TestSubclass, | |
636 | ) | |
637 | ||
638 | test_support.run_unittest(*test_classes) | |
639 | ||
640 | # verify reference counting | |
641 | if verbose and hasattr(sys, "gettotalrefcount"): | |
642 | import gc | |
643 | counts = [None] * 5 | |
644 | for i in xrange(len(counts)): | |
645 | test_support.run_unittest(*test_classes) | |
646 | gc.collect() | |
647 | counts[i] = sys.gettotalrefcount() | |
648 | print counts | |
649 | ||
650 | # doctests | |
651 | from test import test_deque | |
652 | test_support.run_doctest(test_deque, verbose) | |
653 | ||
654 | if __name__ == "__main__": | |
655 | test_main(verbose=True) |