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