Wednesday, 05 January 2011 17:54
"""
Unit test cases for the Balanced Binary Search Tree module
"""
from bbst import *
import unittest
import random
class TestEmptyTreeFunctions(unittest.TestCase):
def setUp(self):
self.emptyTree = bbstree()
# lookup in an empty tree returns None
def test_lookup(self):
self.assertEqual(None, self.emptyTree.lookup(1))
# height of an empty tree is zero
def test_height(self):
self.assertEqual(0,self.emptyTree.height())
# scan over empty tree returns nothing
def test_scan_f(self):
f = []
for t in self.emptyTree.forward():
f.append(t.key)
self.assertEqual(f,[])
def test_scan_b(self):
f = []
for t in self.emptyTree.reverse():
f.append(t.key)
self.assertEqual(f,[])
# inserting into an empty tree returns no value but the lookup
# should then work and height should be 1.
def test_insert(self):
self.emptyTree.insert(1,'waka')
self.assertEqual(self.emptyTree.height(), 1)
self.assertEqual(self.emptyTree.lookup(1).value, 'waka')
class TestTreeFunctions(unittest.TestCase):
# setup: create a 15-item tree from [0..15]
def setUp(self):
self.Tree = bbstree()
self.datalist = [x for x in range(15)]
for x in self.datalist:
self.Tree.insert(x,x*10)
# make sure all the items can be found
def test_lookup(self):
for x in self.datalist:
t = self.Tree.lookup(x)
self.assertTrue(None != t)
self.assertTrue(t.value == x*10)
def test_scan(self):
# make sure forward scan returns all but only the items that went in
f = []
for t in self.Tree.forward():
f.append(t.key)
self.assertEqual(self.datalist,f)
# ditto reverse scan
f = []
for t in self.Tree.reverse():
f.append(t.key)
self.datalist.reverse()
self.assertEqual(self.datalist,f)
# check for proper balance
def test_height(self):
self.assertEqual(self.Tree.height(),4)
self.Tree.insert(15,150)
self.assertEqual(self.Tree.height(),4)
class TestLoadingTree(unittest.TestCase):
# for realistic loading use a shuffled list of 8192 ints
def setUp(self):
self.Tree = bbstree()
self.datalist = [x for x in range(8192)]
random.shuffle(self.datalist)
def test_load(self):
# load the tree, check for reasonable balance
for x in range(len(self.datalist)):
self.Tree.insert(self.datalist[x], x)
self.assertTrue(self.Tree.height()<=11)
# make sure all can still be found
for x in range(len(self.datalist)):
t = self.Tree.lookup(self.datalist[x])
self.assertTrue(t != None)
if __name__ == '__main__':
suite = unittest.TestLoader().loadTestsFromTestCase(TestEmptyTreeFunctions)
unittest.TextTestRunner(verbosity=2).run(suite)
suite = unittest.TestLoader().loadTestsFromTestCase(TestTreeFunctions)
unittest.TextTestRunner(verbosity=2).run(suite)
suite = unittest.TestLoader().loadTestsFromTestCase(TestLoadingTree)
unittest.TextTestRunner(verbosity=2).run(suite)
Read more: http://feeds.dzone.com/~r/dzone/snippets/~3/kiETXilcQeE/12813