def test_extendleft(self):
     d = deque("a")
     self.assertRaises(TypeError, d.extendleft, 1)
     d.extendleft("bcd")
     self.assertEqual(list(d), list(reversed("abcd")))
     d.extendleft(d)
     self.assertEqual(list(d), list("abcddcba"))
     d = deque()
     d.extendleft(range(1000))
     self.assertEqual(list(d), list(reversed(range(1000))))
     self.assertRaises(SyntaxError, d.extendleft, fail())

    def test_rotate(self):
        s = tuple("abcde")
        n = len(s)

        d = deque(s)
        d.rotate(1)  # verify rot(1)
        self.assertEqual("".join(d), "eabcd")

        d = deque(s)
        d.rotate(-1)  # verify rot(-1)
        self.assertEqual("".join(d), "bcdea")
        d.rotate()  # check default to 1
        self.assertEqual(tuple(d), s)

        for i in xrange(n * 3):
            d = deque(s)
            e = deque(d)
            d.rotate(i)  # check vs. rot(1) n times
            for j in xrange(i):
                e.rotate(1)
            self.assertEqual(tuple(d), tuple(e))
            d.rotate(-i)  # check that it works in reverse
            self.assertEqual(tuple(d), s)
            e.rotate(n - i)  # check that it wraps forward
            self.assertEqual(tuple(e), s)

        for i in xrange(n * 3):
            d = deque(s)
            e = deque(d)
            d.rotate(-i)
            for j in xrange(i):
                e.rotate(-1)  # check vs. rot(-1) n times
            self.assertEqual(tuple(d), tuple(e))
            d.rotate(i)  # check that it works in reverse
            self.assertEqual(tuple(d), s)
            e.rotate(i - n)  # check that it wraps backaround
            self.assertEqual(tuple(e), s)

        d = deque(s)
        e = deque(s)
        e.rotate(BIG + 17)  # verify on long series of rotates
        dr = d.rotate
        for i in xrange(BIG + 17):
            dr()
        self.assertEqual(tuple(d), tuple(e))

        self.assertRaises(TypeError, d.rotate, "x")  # Wrong arg type
        self.assertRaises(TypeError, d.rotate, 1, 10)  # Too many args

        d = deque()
        d.rotate()  # rotate an empty deque
        self.assertEqual(d, deque())

    def test_maxlen_zero(self):
        it = iter(range(100))
        deque(it, maxlen=0)
        self.assertEqual(list(it), [])

        it = iter(range(100))
        d = deque(maxlen=0)
        d.extend(it)
        self.assertEqual(list(it), [])

        it = iter(range(100))
        d = deque(maxlen=0)
        d.extendleft(it)
        self.assertEqual(list(it), [])

 def test_pickle(self):
     d = deque(xrange(200))
     for i in range(pickle.HIGHEST_PROTOCOL + 1):
         s = pickle.dumps(d, i)
         e = pickle.loads(s)
         self.assertNotEqual(id(d), id(e))
         self.assertEqual(list(d), list(e))

    def test_container_iterator(self):
        # Bug #3680: tp_traverse was not implemented for deque iterator objects
        class C(object):
            pass

        for i in range(2):
            obj = C()
            ref = weakref.ref(obj)
            if i == 0:
                container = deque([obj, 1])
            else:
                container = reversed(deque([obj, 1]))
            obj.x = iter(container)
            del obj, container
            gc.collect()
            self.assertTrue(ref() is None, "Cycle was not collected")

    def __init__(self):
        self.game = Game()
        self.found_game = False

        self.variation_stack = collections.deque([self.game])
        self.starting_comment = ""
        self.in_variation = False

 def test_extend(self):
     d = deque("a")
     self.assertRaises(TypeError, d.extend, 1)
     d.extend("bcd")
     self.assertEqual(list(d), list("abcd"))
     d.extend(d)
     self.assertEqual(list(d), list("abcdabcd"))

 def test_copy(self):
     mut = [10]
     d = deque([mut])
     e = copy.copy(d)
     self.assertEqual(list(d), list(e))
     mut[0] = 11
     self.assertNotEqual(id(d), id(e))
     self.assertEqual(list(d), list(e))

 def test_clear(self):
     d = deque(xrange(100))
     self.assertEqual(len(d), 100)
     d.clear()
     self.assertEqual(len(d), 0)
     self.assertEqual(list(d), [])
     d.clear()  # clear an emtpy deque
     self.assertEqual(list(d), [])

    def test_comparisons(self):
        d = deque("xabc")
        d.popleft()
        for e in [d, deque("abc"), deque("ab"), deque(), list(d)]:
            self.assertEqual(d == e, type(d) == type(e) and list(d) == list(e))
            self.assertEqual(d != e, not (type(d) == type(e) and list(d) == list(e)))

        args = map(deque, ("", "a", "b", "ab", "ba", "abc", "xba", "xabc", "cba"))
        for x in args:
            for y in args:
                self.assertEqual(x == y, list(x) == list(y), (x, y))
                self.assertEqual(x != y, list(x) != list(y), (x, y))
                self.assertEqual(x < y, list(x) < list(y), (x, y))
                self.assertEqual(x <= y, list(x) <= list(y), (x, y))
                self.assertEqual(x > y, list(x) > list(y), (x, y))
                self.assertEqual(x >= y, list(x) >= list(y), (x, y))
                self.assertEqual(cmp(x, y), cmp(list(x), list(y)), (x, y))

    def __init__(self):
        self._expectations = collections.deque()
        self._is_dead = threading.Event()
        self._std_streams_closed = False

        self._send_queue = queue.Queue()
        self._send_thread = threading.Thread(target=self._send_thread_target)
        self._send_thread.daemon = True

    def test_gc_doesnt_blowup(self):
        import gc

        # This used to assert-fail in deque_traverse() under a debug
        # build, or run wild with a NULL pointer in a release build.
        d = deque()
        for i in xrange(100):
            d.append(1)
            gc.collect()

 def test_big_queue_popright(self):
     d = deque()
     append, pop = d.appendleft, d.pop
     for i in xrange(BIG):
         append(i)
     for i in xrange(BIG):
         x = pop()
         if x != i:
             self.assertEqual(x, i)

    def test_getitem(self):
        n = 200
        d = deque(xrange(n))
        l = range(n)
        for i in xrange(n):
            d.popleft()
            l.pop(0)
            if random.random() < 0.5:
                d.append(i)
                l.append(i)
            for j in xrange(1 - len(l), len(l)):
                assert d[j] == l[j]

        d = deque("superman")
        self.assertEqual(d[0], "s")
        self.assertEqual(d[-1], "n")
        d = deque()
        self.assertRaises(IndexError, d.__getitem__, 0)
        self.assertRaises(IndexError, d.__getitem__, -1)

 def test_long_steadystate_queue_popright(self):
     for size in (0, 1, 2, 100, 1000):
         d = deque(reversed(xrange(size)))
         append, pop = d.appendleft, d.pop
         for i in xrange(size, BIG):
             append(i)
             x = pop()
             if x != i - size:
                 self.assertEqual(x, i - size)
         self.assertEqual(list(reversed(list(d))), range(BIG - size, BIG))

 def test_big_stack_left(self):
     d = deque()
     append, pop = d.appendleft, d.popleft
     for i in xrange(BIG):
         append(i)
     for i in reversed(xrange(BIG)):
         x = pop()
         if x != i:
             self.assertEqual(x, i)
     self.assertEqual(len(d), 0)

 def test_setitem(self):
     n = 200
     d = deque(xrange(n))
     for i in xrange(n):
         d[i] = 10 * i
     self.assertEqual(list(d), [10 * i for i in xrange(n)])
     l = list(d)
     for i in xrange(1 - n, 0, -1):
         d[i] = 7 * i
         l[i] = 7 * i
     self.assertEqual(list(d), l)

 def test_reverse(self):
     n = 500  # O(n**2) test, don't make this too big
     data = [random.random() for i in range(n)]
     for i in range(n):
         d = deque(data[:i])
         r = d.reverse()
         self.assertEqual(list(d), list(reversed(data[:i])))
         self.assertIs(r, None)
         d.reverse()
         self.assertEqual(list(d), data[:i])
     self.assertRaises(TypeError, d.reverse, 1)  # Arity is zero

    def test_maxlen(self):
        self.assertRaises(ValueError, deque, "abc", -1)
        self.assertRaises(ValueError, deque, "abc", -2)
        it = iter(range(10))
        d = deque(it, maxlen=3)
        self.assertEqual(list(it), [])
        self.assertEqual(repr(d), "deque([7, 8, 9], maxlen=3)")
        self.assertEqual(list(d), range(7, 10))
        self.assertEqual(d, deque(range(10), 3))
        d.append(10)
        self.assertEqual(list(d), range(8, 11))
        d.appendleft(7)
        self.assertEqual(list(d), range(7, 10))
        d.extend([10, 11])
        self.assertEqual(list(d), range(9, 12))
        d.extendleft([8, 7])
        self.assertEqual(list(d), range(7, 10))
        d = deque(xrange(200), maxlen=10)
        d.append(d)
        test_support.unlink(test_support.TESTFN)
        fo = open(test_support.TESTFN, "wb")
        try:
            print >> fo, d,
            fo.close()
            fo = open(test_support.TESTFN, "rb")
            self.assertEqual(fo.read(), repr(d))
        finally:
            fo.close()
            test_support.unlink(test_support.TESTFN)

        d = deque(range(10), maxlen=None)
        self.assertEqual(repr(d), "deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])")
        fo = open(test_support.TESTFN, "wb")
        try:
            print >> fo, d,
            fo.close()
            fo = open(test_support.TESTFN, "rb")
            self.assertEqual(fo.read(), repr(d))
        finally:
            fo.close()
            test_support.unlink(test_support.TESTFN)

 def test_delitem(self):
     n = 500  # O(n**2) test, don't make this too big
     d = deque(xrange(n))
     self.assertRaises(IndexError, d.__delitem__, -n - 1)
     self.assertRaises(IndexError, d.__delitem__, n)
     for i in xrange(n):
         self.assertEqual(len(d), n - i)
         j = random.randrange(-len(d), len(d))
         val = d[j]
         self.assertIn(val, d)
         del d[j]
         self.assertNotIn(val, d)
     self.assertEqual(len(d), 0)