def test_node_str(self):
     a = dllist([None, None]).first
     self.assertEqual(str(a), "dllistnode(None)")
     b = dllist([1, None]).first
     self.assertEqual(str(b), "dllistnode(1)")
     c = dllist(["abc", None]).first
     self.assertEqual(str(c), "dllistnode(abc)")

 def test_node_repr(self):
     a = dllist([None]).first
     self.assertEqual(repr(a), '<dllistnode(None)>')
     b = dllist([1, None]).first
     self.assertEqual(repr(b), '<dllistnode(1)>')
     c = dllist(['abc', None]).first
     self.assertEqual(repr(c), '<dllistnode(\'abc\')>')

 def test_node_repr(self):
     a = dllist([None]).first
     self.assertEqual(repr(a), "<dllistnode(None)>")
     b = dllist([1, None]).first
     self.assertEqual(repr(b), "<dllistnode(1)>")
     c = dllist(["abc", None]).first
     self.assertEqual(repr(c), "<dllistnode('abc')>")

 def test_guards_after_concat(self):
     a = dllist([1, 2])
     b = dllist([3, 4])
     c = a + b
     self.assertIsNot(c.first, None)
     self.assertEqual(c.first.value, 1)
     self.assertIsNot(c.last, None)
     self.assertEqual(c.last.value, 4)

 def test_guards_after_concat_inplace(self):
     a = dllist([1, 2])
     b = dllist([3, 4])
     orig_a_first = a.first
     a += b
     self.assertIs(a.first, orig_a_first)
     self.assertEqual(a.first.value, 1)
     self.assertIsNot(a.last, None)
     self.assertEqual(a.last.value, 4)

 def test_concat(self):
     a_ref = range(0, 1024, 4)
     a = dllist(a_ref)
     b_ref = range(8092, 8092 + 1024, 4)
     b = dllist(b_ref)
     ab_ref = dllist(a_ref + b_ref)
     c = a + b
     self.assertEqual(c, ab_ref)
     self.assertEqual(len(c), len(ab_ref))
     c = a + b_ref
     self.assertEqual(c, ab_ref)
     self.assertEqual(len(c), len(ab_ref))

 def test_cmp(self):
     a = dllist(xrange(0, 1100))
     b = dllist(xrange(0, 1101))
     c = [xrange(0, 1100)]
     self.assertEqual(cmp(a, a), 0)
     self.assertEqual(cmp(a, b), -1)
     self.assertEqual(cmp(b, a), 1)
     self.assertEqual(cmp(a, c), 1)
     self.assertEqual(cmp(c, a), -1)
     self.assertEqual(cmp([], []), 0)
     self.assertEqual(cmp([], a), -1)
     self.assertEqual(cmp(a, []), 1)

def heavy_hitters(e):
   k = int(1.0 / e - 1)
   table = {}
   inner = dllist()
   for i in range(k):
       inner.insert([None, 0])
   outer = dllist([inner])
   min_count = 0

   with open("Data.txt") as data:
       for line in data:
           print line
           if not table.has_key(line):
               if outer.first.value.first.value[1] == min_count:
                   victim = outer.first.value.popleft()
                   if table.has_key(victim[0]) :
                       table.pop(victim[0], None)
                   outer.first.value.insert([line, min_count])
                   table[line] = [outer.first, outer.first.value.last]

           if table.has_key(line):
               a = table.get(line)
               a[1].value[1] += 1
               if a[0].next:
                   if a[0].next.value.first.value[1] == a[1].value[1]:
                       tl = a[0].next
                       tn = a[0].value.remove(a[1])
                       tl.value.appendleft(tn)
                       table[line] = [tl, tl.value.first]
                       if a[0].value.size == 0:
                           outer.remove(a[0])

                   else:
                       tn = a[0].value.remove(a[1])
                       new_inner = dllist()
                       new_inner.appendleft(tn)
                       outer.insert(new_inner, after=a[0])
                       table[line] = [a[0].next, a[0].next.value.first]
                       if a[0].value.size == 0:
                           outer.remove(a[0])
               else:
                   tn = a[0].value.remove(a[1])
                   new_inner = dllist()
                   new_inner.appendleft(tn)
                   outer.insert(new_inner, after=a[0])
                   table[line] = [a[0].next, a[0].next.value.first]
                   if a[0].value.size == 0:
                       outer.remove(a[0])
           else:
               min_count += 1

   return table

 def test_concat_empty(self):
     empty = dllist()
     filled_ref = range(0, 1024, 4)
     filled = dllist(filled_ref)
     res = empty + empty
     self.assertEqual(res, dllist([] + []))
     self.assertEqual(len(res), 0)
     res = empty + filled
     self.assertEqual(res, dllist([] + filled_ref))
     self.assertEqual(len(res), len(filled_ref))
     res = filled + empty
     self.assertEqual(res, dllist(filled_ref + []))
     self.assertEqual(len(res), len(filled_ref))

 def test_insert_value_after_last(self):
     ll = dllist(xrange(4))
     ref = dllist([0, 1, 2, 3, 10])
     prev = ll.nodeat(3)
     arg_node = dllistnode(10)
     new_node = ll.insert(arg_node, after=ll.last)
     self.assertNotEqual(new_node, arg_node)
     self.assertEqual(new_node.value, 10)
     self.assertEqual(new_node.prev, prev)
     self.assertEqual(new_node.next, None)
     self.assertEqual(prev.next, new_node)
     self.assertEqual(new_node, ll.last)
     self.assertEqual(ll, ref)

 def test_appendleft(self):
     ll = dllist(xrange(4))
     ref = dllist([10, 0, 1, 2, 3])
     next = ll.nodeat(0)
     arg_node = dllistnode(10)
     new_node = ll.appendleft(arg_node)
     self.assertNotEqual(new_node, arg_node)
     self.assertEqual(new_node.value, 10)
     self.assertEqual(new_node.prev, None)
     self.assertEqual(new_node.next, next)
     self.assertEqual(next.prev, new_node)
     self.assertEqual(ll.first, new_node)
     self.assertEqual(ll, ref)

 def test_appendright(self):
     ll = dllist(xrange(4))
     ref = dllist([0, 1, 2, 3, 10])
     prev = ll.nodeat(-1)
     arg_node = dllistnode(10)
     new_node = ll.appendright(arg_node)
     self.assertNotEqual(new_node, arg_node)
     self.assertEqual(new_node.value, 10)
     self.assertEqual(new_node.prev, prev)
     self.assertEqual(new_node.next, None)
     self.assertEqual(prev.next, new_node)
     self.assertEqual(ll.last, new_node)
     self.assertEqual(ll, ref)

 def test_insert_value_after(self):
     ll = dllist(xrange(4))
     ref = dllist([0, 1, 10, 2, 3])
     prev = ll.nodeat(1)
     next = ll.nodeat(2)
     arg_node = dllistnode(10)
     new_node = ll.insert(arg_node, after=ll.nodeat(1))
     self.assertNotEqual(new_node, arg_node)
     self.assertEqual(new_node.value, 10)
     self.assertEqual(new_node.prev, prev)
     self.assertEqual(new_node.next, next)
     self.assertEqual(prev.next, new_node)
     self.assertEqual(next.prev, new_node)
     self.assertEqual(ll, ref)

 def test_node_after_del(self):
     ll = dllist([1, 2, 3])
     node = ll.nodeat(1)
     del ll[1]
     self.assertIs(node.prev, None)
     self.assertIs(node.next, None)
     self.assertIs(node.list, None)

 def test_guards_after_remove(self):
     ll = dllist([1, 2])
     ll.remove(ll.last)
     self.assertIs(ll.first, ll.last)
     ll.remove(ll.first)
     self.assertIs(ll.first, None)
     self.assertIs(ll.last, None)

 def test_node_after_remove(self):
     ll = dllist([1, 2, 3])
     node = ll.nodeat(1)
     ll.remove(node)
     self.assertIs(node.prev, None)
     self.assertIs(node.next, None)
     self.assertIs(node.list, None)

 def test_init_empty(self):
     ll = dllist()
     self.assertEqual(len(ll), 0)
     self.assertEqual(ll.size, 0)
     self.assertEqual(list(ll), [])
     self.assertIs(ll.first, None)
     self.assertIs(ll.last, None)

 def test_guards_after_appendright(self):
     ll = dllist()
     node1 = ll.appendright(1)
     self.assertIs(ll.first, node1)
     self.assertIs(ll.last, node1)
     node2 = ll.appendright(2)
     self.assertIs(ll.first, node1)
     self.assertIs(ll.last, node2)

 def test_guards_after_insert(self):
     ll = dllist()
     node1 = ll.insert(dllistnode(1))
     self.assertIs(ll.first, node1)
     self.assertIs(ll.last, node1)
     node2 = ll.insert(dllistnode(2))
     self.assertIs(ll.first, node1)
     self.assertIs(ll.last, node2)

 def test_guards_after_repeat_inplace(self):
     ll = dllist([1, 2])
     orig_first = ll.first
     orig_last = ll.last
     ll *= 4
     self.assertIs(ll.first, orig_first)
     self.assertIsNot(ll.last, None)
     self.assertIsNot(ll.last, orig_last)