from BPTree import BPTree, BPTreeNode, BPTreeLeaf import random, unittest # see http://docs.python.org/3.3/library/unittest.html class TestBPTreeLeaf(unittest.TestCase): def setUp(self): pass def test_init(self): # CATEGORY: Testing BPTreeLeaf.init for BPTreeLeaf with capacity 5 # SUB-CATEGORY: init an empty BPTreeLeaf with no keys, no next # YOUR CODE GOES HERE # SUB-CATEGORY: init an empty BPTreeLeaf with no next keys=[4,5,6] next_leaf=None bpt_leaf=BPTreeLeaf(keys, next_leaf, 5) self.assertEquals(bpt_leaf._keys,keys, "init failed on keys (first leaf)") self.assertEquals(bpt_leaf._next,next_leaf, "init failed on next (first leaf)") # SUB-CATEGORY: init a BPTreeLeaf pointing to another BPTreeLeaf keys=[1,2,3] next_leaf=bpt_leaf bpt_leaf1=BPTreeLeaf(keys, next_leaf, 5) self.assertEquals(bpt_leaf1._keys,keys, "init failed on keys (second leaf)") self.assertEquals(bpt_leaf1._next,next_leaf, "init failed on next (second leaf)") def test_insert(self): # CATEGORY: Testing BPTreeLeaf.insert for BPTreeLeaf with capacity 3 bpt_leaf=BPTreeLeaf([], None, 3) # SUB-CATEGORY: insert key into empty leaf # insert 5 mesg="insert failed on empty leaf " (pkey, ppointer)=bpt_leaf.insert(5) self.assertEquals((pkey,ppointer),(None, None), mesg+ "(return)") self.assertEquals(bpt_leaf._keys,[5], mesg + "(keys)") self.assertEquals(bpt_leaf._next,None, mesg +"(next)") # SUB-CATEGORY: insert new largest key into a leaf # insert 6 mesg="insert failed on new largest key in leaf " (pkey, ppointer)=bpt_leaf.insert(6) self.assertEquals((pkey,ppointer),(None, None), mesg+ "(return)") self.assertEquals(bpt_leaf._keys,[5,6], mesg+"(keys)") self.assertEquals(bpt_leaf._next,None, mesg+"(next)") # SEE HOW I CATEGORIZED THE TESTS ABOVE, CONTINUE BELOW, FIXING THE CODE AND COMMENTS # SUB-CATEGORY: insert new smallest key into a leaf # insert 2 mesg="insert failed on new smallest key in leaf " (pkey, ppointer)=bpt_leaf.insert(2) self.assertEquals((pkey,ppointer),(None, None), "insert failed on insert (return)") self.assertEquals(bpt_leaf._keys,[2,5,6], "insert failed on insert (keys)") self.assertEquals(bpt_leaf._next,None, "insert failed on insert (next)") # check re-adds of existing keys # insert 5 (pkey, ppointer)=bpt_leaf.insert(5) self.assertEquals((pkey,ppointer),(None, None), "insert failed on insert (return)") self.assertEquals(bpt_leaf._keys,[2,5,6], "insert failed on insert (keys)") self.assertEquals(bpt_leaf._next,None, "insert failed on insert (next)") # insert 6 (pkey, ppointer)=bpt_leaf.insert(6) self.assertEquals((pkey,ppointer),(None, None), "insert failed on insert (return)") self.assertEquals(bpt_leaf._keys,[2,5,6], "insert failed on insert (keys)") self.assertEquals(bpt_leaf._next,None, "insert failed on insert (next)") # insert 2 (pkey, ppointer)=bpt_leaf.insert(2) self.assertEquals((pkey,ppointer),(None, None), "insert failed on insert (return)") self.assertEquals(bpt_leaf._keys,[2,5,6], "insert failed on insert (keys)") self.assertEquals(bpt_leaf._next,None, "insert failed on insert (next)") # check split (pkey, ppointer)=bpt_leaf.insert(4) self.assertEquals((pkey,ppointer),(5, bpt_leaf._next), "insert failed on insert (return)") self.assertEquals(bpt_leaf._keys,[2,4], "insert failed on insert (keys)") self.assertEquals(bpt_leaf._next,ppointer, "insert failed on insert (next)") self.assertEquals(ppointer._keys,[5,6], "insert failed on insert (keys)") self.assertEquals(ppointer._next,None, "insert failed on insert (next)") # CATEGORY: Testing BPTreeLeaf.insert for BPTreeLeaf with capacity ??? class TestBPTreeNode(unittest.TestCase): def setUp(self): pass def test_init(self): pass def test_insert(self): pass def test_insert_here(self): # NOTE: The goal here is to make sure that this particular method works, independently # of whether the BPTreeLeaf works. To do this, you can manufacture a # BPTreeNode with pointers=['A', 'B', 'C', 'D'], now you can check if insert_here # works for pass class TestBPTree(unittest.TestCase): # FIX THE TESTS BELOW SO THAT THEY USE pyunit, ADD CATEGORIES AND SUB-CATEGORIES AS ABOVE. # ADD ANY OTHER INTERESTING TESTS YOU CAN THINK OF def test_integrity(self): # Generally check the integrity of complete BPTree by building, searching and listing all keys for capacity in [2,5,10,20]: for order in ['increasing', 'decreasing', 'random']: self.integrity_helper(capacity, 10000, order) def integrity_helper(self, capacity, num, order): bpt=BPTree(capacity) r=num print("testing capacity="+str(capacity)+" num="+str(num)+" order="+order) print("Creating list") if order=='decreasing': l=range(num,0,-1) elif order=='increasing': l=range(num) elif order=='random': r=num*10 l=[random.randrange(r) for i in range(num)] print("Building tree") for i in l: bpt.insert(i) print("Searching all") for i in l: self.assertTrue(bpt.find(i), "Search all: missing "+str(i)) if not bpt.find(i): print("Can't find "+i) print("Searching lower") for i in range(-200,200): should_find=(i in l) self.assertEqual((i in l), bpt.find(i), "Search lower: "+str(i)+ " expected find to return "+str(should_find)) if (i in l)!=bpt.find(i): print("error") print("Searching middle") for i in range(r//2-200,r//2+200): if (i in l)!=bpt.find(i): print("error") print("Searching upper") for i in range(r-200,r+200): if (i in l)!=bpt.find(i): print("error") print("Checking All Keys") all_keys=bpt.keys() l1=list(set(l)) l1.sort() print(all_keys==l1) print("Done") def BPTreeLeaf_suite(): return unittest.TestLoader().loadTestsFromTestCase(TestBPTreeLeaf) def BPTreeNode_suite(): return unittest.TestLoader().loadTestsFromTestCase(TestBPTreeNode) def BPTree_suite(): return unittest.TestLoader().loadTestsFromTestCase(TestBPTree) if __name__=='__main__': runner = unittest.TextTestRunner() # Uncomment below to test appropriate classes. # runner.run(BPTreeLeaf_suite()) # runner.run(BPTreeNode_suite()) # runner.run(BPTree_suite())