Unit testing for Splay Tree in Python

Question

I am creating a test class for the following code. splay_test.py which is the unit test code for splay tree. I needed help with writing unit tests for python to get %100 coverage. I am very bad at unit testing but have started off ok. just need someone to help me finish it off and maybe find any more bugs. My coverage for some reason isn't connecting the two files together so I can't see what my overall coverage is.

class Node:
 def __init__(self, key):
 self.key = key
 self.left = self.right = None
 def equals(self, node):
 return self.key == node.key
class SplayTree:
 def __init__(self):
 self.root = None
 self.header = Node(None) # For splay()
 def insert(self, key):
 if (self.root == None):
 self.root = Node(key)
 return #test
 self.splay(key)
 if self.root.key == key:
 # If the key is already there in the tree, don't do anything.
 return
 n = Node(key)
 if key < self.root.key:
 n.left = self.root.left
 n.right = self.root
 self.root.left = None
 else:
 n.right = self.root.right
 n.left = self.root
 self.root.right = None
 self.root = n
 def remove(self, key):
 self.splay(key)
 if key != self.root.key:
 raise 'key not found in tree' # do
 # Now delete the root.
 if self.root.left == None:
 self.root = self.root.right
 else:
 x = self.root.right
 self.root = self.root.left
 self.splay(key)
 self.root.right = x
 def findMin(self):
 if self.root == None:
 return None
 x = self.root
 while x.left != None:
 x = x.left
 self.splay(x.key)
 return x.key
 def findMax(self):
 if self.root == None:
 return None
 x = self.root
 while (x.right != None):
 x = x.right
 self.splay(x.key)
 return x.key
 def find(self, key): # test
 if self.root == None:
 return None
 self.splay(key)
 if self.root.key != key:
 return None
 return self.root.key
 def isEmpty(self):
 return self.root == None
 def splay(self, key): # test
 l = r = self.header
 t = self.root
 self.header.left = self.header.right = None
 while True:
 if key < t.key:
 if t.left == None:
 break
 if key < t.left.key:
 y = t.left
 t.left = y.right
 y.right = t
 t = y
 if t.left == None:
 break
 r.left = t
 r = t
 t = t.left
 elif key > t.key:
 if t.right == None:
 break
 if key > t.right.key:
 y = t.right
 t.right = y.left
 y.left = t
 t = y
 if t.right == None:
 break
 l.right = t
 l = t
 t = t.right
 else:
 break
 l.right = t.left
 r.left = t.right
 t.left = self.header.right
 t.right = self.header.left
 self.root = t

What I have so far

import unittest
from splay import SplayTree
class TestCase(unittest.TestCase):
 def setUp(self):
 self.keys = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 self.t = SplayTree()
 for key in self.keys:
 self.t.insert(key)
 def testInsert(self):
 for key in self.keys:
 self.assertEquals(key, self.t.find(key))
 def testRemove(self):
 for key in self.keys:
 self.t.remove(key)
 self.assertEquals(self.t.find(key), None)
 def testLargeInserts(self):
 t = SplayTree()
 nums = 40000
 gap = 307
 i = gap
 while i != 0:
 t.insert(i)
 i = (i + gap) % nums
 def testIsEmpty(self):
 self.assertFalse(self.t.isEmpty())
 t = SplayTree()
 self.assertTrue(t.isEmpty())
 def testMinMax(self):
 self.assertEquals(self.t.findMin(), 0)
 self.assertEquals(self.t.findMax(), 9)

Tests I have done so far

import unittest
from splay import SplayTree
class TestCase(unittest.TestCase):
 def setUp(self):
 self.keys = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 self.t = SplayTree()
 for key in self.keys:
 self.t.insert(key)
 def testInsert(self):
 for key in self.keys:
 self.assertEquals(key, self.t.find(key))
 def testRemove(self):
 for key in self.keys:
 self.t.remove(key)
 self.assertEquals(self.t.find(key), None)
 def testLargeInserts(self):
 t = SplayTree()
 nums = 40000
 gap = 307
 i = gap
 while i != 0:
 t.insert(i)
 i = (i + gap) % nums
 def testIsEmpty(self):
 self.assertFalse(self.t.isEmpty())
 t = SplayTree()
 self.assertTrue(t.isEmpty())
 def testMinMax(self):
 self.assertEquals(self.t.findMin(), 0)
 self.assertEquals(self.t.findMax(), 9)
if __name__ == "__main__":
 unittest.main()

• Reinderien: Rather than writing an equals method, consider using __eq__; do some reading here: docs.python.org/3/reference/datamodel.html#object.__eq__
• SebasSBM: @Reinderien You have a point about that, but as far as i can see, he hasn't make any equals method, he's rather using an assertion.
• Reinderien: @SebasSBM Look harder :) There's an equals under the Node class.
• SebasSBM: @Reinderien in that case, __eq__ usage would fit better, as you said.

Answer 1

You've already done a pretty good job adding these tests and covering a big chunk of the code under test.

The problem is, if we look at the branch coverage, we'll see that quite a few of the branches are not reached as the implementation is relatively "complex" - by code complexity standards:

python -m pytest test_tree.py --cov-branch --cov=tree --cov-report html

Using pytest and pytest-cov plugin, tree here is the module/package name for which to measure coverage.

Other observations:

• self.assertEquals() is deprecated in favor of self.assertEqual()
• even though setUp and tearDown are the legacy camel-case Junit-inspired names, consider following PEP8 and naming your methods in an lower_case_with_underscores style
• look into defining your tree as a pytest fixture
• look into property-based-testing with Hypothesis as a means to generate possible input nodes for your tree
• focus on the more complex parts first as this is where the possibility of having a problem is higher - the splay() method should probably be tested separately and directly checking all the major variations of re-balancing the tree when a new node is added