Jesse HexTrie Junit Test

You need to add in this method to your HexTrie to get the tests to work:

public Node<K,V> getRootNode(){
	return root.me;
}

• StudentTests.java

package tests;

import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeMap;

import org.w3c.dom.Document;

import cmsc420.hextrie.EndNode;
import cmsc420.hextrie.GuideNode;
import cmsc420.hextrie.HexTrie;
import cmsc420.hextrie.LeafNode;
import cmsc420.hextrie.Node;
import cmsc420.hextrie.StringComparator;
import junit.framework.AssertionFailedError;
import junit.framework.TestCase;
import cmsc420.util.BPTreeValidator;
import cmsc420.util.IllegalStructureException;

public class StudentTests extends TestCase {
	@SuppressWarnings("unchecked")
	private HexTrie<Integer,Integer> setUpSmallHexTrie() throws IllegalStructureException{
		HexTrie<Integer, Integer> ht = new HexTrie<Integer, Integer>(DefaultComparator.instance, 3, true);
		// 0 to 49, inclusive
		int [] keys = {41, 9, 30, 17, 3, 22, 42, 12, 26, 31, 20, 46, 16, 36, 1, 18, 6, 10, 47, 13, 11, 37, 38, 32, 8, 5, 28, 2, 0, 25, 48, 19, 33, 14, 49, 4, 39, 7, 35, 29, 21, 34, 27, 40, 15, 43, 23, 45, 44, 24};
		for (int key : keys){
			ht.put(new Integer(key), new Integer(key));
			Document outputDoc = ht.getXmlDocumentSnapshot();
			assertTrue(BPTreeValidator.validateOutputDocument(outputDoc, DefaultComparator.instance));
		}
		return ht;
	}
	
	private HexTrie<Integer,Integer> setUpBigHexTrie(int leafOrder, boolean isBstar) throws IllegalStructureException{
		@SuppressWarnings("unchecked")
		HexTrie<Integer, Integer> ht = new HexTrie<Integer, Integer>(DefaultComparator.instance, leafOrder, isBstar);
		// 0 to 499, inclusive
		int [] keys = {
				391, 173, 386, 207, 341, 414, 291, 369, 225, 33, 317, 357, 2, 347, 416, 106, 489, 217, 129, 449, 73, 69, 19, 356, 309, 257, 114, 373, 302, 427, 213, 388, 263, 235, 301, 195, 18, 283, 0, 288, 107, 477, 85, 50, 236, 419, 429, 30, 92, 439, 453, 392, 491, 256, 124, 266, 96, 289, 121, 282, 406, 410, 396, 139, 42, 168, 421, 358, 83, 90, 381, 432, 115, 100, 384, 269, 179, 412, 265, 313, 395, 220, 334, 338, 134, 204, 66, 484, 290, 26, 486, 492, 74, 145, 41, 117, 71, 170, 426, 466, 259, 17, 375, 240, 97, 455, 377, 447, 335, 223, 370, 273, 476, 497, 431, 278, 253, 299, 445, 281, 436, 380, 324, 175, 162, 190, 212, 467, 12, 275, 343, 232, 226, 307, 128, 271, 448, 322, 494, 93, 255, 451, 345, 119, 177, 59, 463, 150, 11, 475, 437, 311, 340, 206, 252, 329, 405, 165, 318, 126, 132, 304, 51, 409, 130, 7, 238, 151, 344, 214, 247, 237, 21, 434, 367, 22, 146, 76, 63, 191, 149, 218, 350, 239, 355, 178, 116, 127, 118, 250, 138, 49, 222, 15, 496, 300, 332, 142, 364, 70, 208, 102, 403, 457, 424, 81, 294, 58, 320, 326, 29, 248, 287, 346, 5, 143, 45, 241, 372, 125, 245, 478, 153, 200, 89, 306, 465, 495, 137, 336, 490, 113, 360, 328, 383, 284, 159, 171, 86, 56, 202, 279, 468, 327, 498, 148, 94, 359, 417, 47, 472, 459, 493, 68, 141, 133, 286, 211, 57, 72, 331, 188, 155, 167, 4, 53, 227, 292, 480, 110, 433, 337, 79, 147, 483, 234, 123, 471, 368, 43, 393, 6, 230, 473, 64, 111, 221, 112, 189, 201, 199, 164, 196, 77, 462, 378, 75, 105, 205, 163, 400, 264, 469, 450, 9, 399, 382, 152, 308, 342, 62, 444, 198, 333, 8, 418, 158, 36, 197, 260, 330, 441, 185, 411, 315, 34, 243, 242, 228, 371, 428, 443, 479, 80, 314, 40, 379, 10, 425, 38, 298, 87, 407, 84, 194, 420, 25, 3, 454, 215, 474, 31, 193, 485, 397, 316, 154, 160, 325, 415, 61, 95, 254, 366, 174, 120, 108, 39, 389, 261, 268, 277, 440, 244, 258, 280, 251, 24, 91, 135, 394, 321, 446, 423, 385, 461, 44, 131, 422, 210, 297, 209, 231, 305, 361, 103, 184, 285, 456, 20, 262, 293, 183, 312, 35, 442, 362, 354, 99, 28, 229, 267, 82, 499, 172, 276, 481, 272, 55, 67, 187, 48, 310, 488, 224, 349, 365, 109, 430, 351, 13, 192, 274, 246, 387, 404, 37, 401, 54, 323, 101, 122, 460, 353, 376, 352, 303, 482, 203, 169, 157, 1, 23, 470, 374, 180, 452, 464, 176, 166, 104, 295, 52, 65, 156, 14, 140, 46, 181, 487, 60, 219, 136, 216, 413, 88, 408, 161, 438, 319, 402, 27, 16, 186, 144, 270, 435, 458, 98, 398, 233, 182, 249, 78, 339, 363, 296, 348, 32, 390
		};
		for (int key : keys){
			ht.put(new Integer(key), new Integer(key));
			Document outputDoc = ht.getXmlDocumentSnapshot();
			assertTrue(BPTreeValidator.validateOutputDocument(outputDoc, DefaultComparator.instance));
		}
		return ht;
	}
	
	private int[] getSmallDelete(){
		int [] delete = {25, 14, 29, 3, 20, 44, 45, 36, 11, 16, 21, 42, 19, 37, 8, 2, 28, 5, 46, 4, 27, 43, 31, 9, 17, 39, 41, 35, 24, 6, 34, 49, 23, 48, 22, 33, 30, 32, 38, 7, 1, 10, 26, 18, 15, 0, 12, 47, 13, 40};		
		return delete;
	}
	
	private int[] getBigDelete(){
		int [] delete = {
				452, 450, 15, 286, 117, 185, 499, 35, 373, 343, 445, 323, 56, 415, 394, 347, 363, 336, 479, 87, 131, 120, 316, 126, 197, 302, 384, 469, 16, 124, 470, 395, 54, 229, 487, 294, 465, 376, 235, 91, 447, 155, 30, 295, 205, 417, 174, 291, 65, 154, 118, 337, 317, 226, 463, 189, 297, 497, 409, 218, 367, 289, 125, 344, 424, 319, 90, 10, 39, 266, 58, 89, 128, 413, 387, 330, 228, 200, 160, 0, 358, 328, 456, 488, 249, 62, 303, 111, 141, 298, 383, 92, 191, 357, 389, 423, 426, 369, 310, 436, 378, 267, 184, 144, 105, 101, 333, 104, 122, 63, 163, 171, 476, 309, 274, 448, 382, 261, 301, 70, 52, 190, 85, 33, 374, 388, 8, 490, 193, 66, 242, 314, 280, 375, 296, 222, 162, 461, 158, 264, 135, 273, 26, 390, 212, 282, 57, 203, 214, 401, 195, 353, 159, 483, 285, 474, 248, 123, 60, 209, 166, 327, 342, 180, 322, 133, 253, 400, 372, 407, 446, 179, 71, 425, 360, 277, 227, 364, 457, 107, 5, 72, 187, 318, 9, 269, 169, 152, 49, 29, 250, 272, 245, 14, 258, 45, 438, 4, 354, 443, 396, 192, 17, 243, 113, 419, 356, 300, 208, 142, 13, 315, 311, 377, 404, 403, 201, 284, 468, 411, 94, 410, 338, 137, 48, 432, 157, 153, 182, 220, 172, 345, 233, 276, 213, 238, 444, 11, 146, 385, 100, 53, 399, 371, 224, 308, 288, 324, 149, 127, 22, 255, 77, 491, 67, 312, 32, 36, 331, 435, 150, 281, 84, 453, 427, 20, 428, 114, 161, 379, 59, 496, 334, 449, 198, 2, 51, 138, 43, 12, 178, 472, 406, 240, 431, 88, 80, 232, 21, 6, 429, 256, 455, 83, 305, 116, 254, 412, 339, 139, 393, 265, 263, 459, 170, 183, 397, 25, 181, 78, 355, 366, 326, 466, 121, 362, 234, 252, 73, 64, 143, 408, 38, 292, 244, 103, 477, 129, 196, 156, 279, 110, 498, 380, 321, 37, 439, 140, 481, 293, 493, 398, 145, 434, 74, 216, 221, 241, 467, 50, 136, 23, 405, 199, 489, 365, 287, 239, 42, 148, 473, 346, 335, 260, 307, 231, 68, 421, 485, 440, 112, 31, 19, 69, 351, 268, 402, 61, 175, 454, 359, 97, 76, 96, 95, 492, 422, 165, 437, 332, 186, 290, 28, 99, 168, 18, 177, 151, 352, 416, 109, 132, 442, 236, 306, 204, 475, 147, 41, 299, 230, 3, 82, 349, 478, 47, 433, 130, 451, 386, 207, 24, 270, 340, 482, 304, 391, 361, 271, 206, 251, 81, 55, 464, 106, 93, 341, 134, 188, 40, 262, 329, 495, 458, 237, 392, 313, 217, 381, 86, 494, 211, 462, 257, 44, 215, 418, 368, 246, 115, 460, 79, 98, 350, 7, 320, 259, 275, 484, 34, 278, 247, 420, 441, 75, 325, 167, 202, 283, 210, 414, 164, 119, 194, 223, 176, 486, 219, 102, 471, 370, 225, 173, 1, 46, 27, 430, 480, 348, 108
		};
		return delete;
	}
	
	public void testHashCode(){
		HexTrie<String, Object> ht = new HexTrie<String, Object>(new StringComparator(), 5, false);
		TreeMap<String, Object> tm = new TreeMap<String, Object>(new StringComparator());
		assertTrue(ht.hashCode() == tm.hashCode());
		String str = "test string";
		Integer x = 54;
		ht.put(str, x);
		tm.put(str, x);
		ht.put("hi", x);
		tm.put("hi", x);
		System.out.println(tm.hashCode());
		System.out.println(ht.hashCode());
		assertTrue(ht.hashCode() == tm.hashCode());
		assertTrue(ht.equals(tm));
	}
	
	public void testPutGet(){
		HexTrie<String, Object> ht = new HexTrie<String, Object>(new StringComparator(), 5, false);
		TreeMap<String, Object> tm = new TreeMap<String, Object>();
		assertTrue(ht.hashCode() == tm.hashCode());
		String str = "test string";
		Integer x = 54;
		ht.put(str, x);
		tm.put(str, x);
		ht.put("hi", x);
		tm.put("hi", x);
		assertTrue(ht.get("hi").equals(tm.get("hi")));
	}
	
	public void testHexTrie(){
		HexTrie<String, Object> ht = new HexTrie<String, Object>(new StringComparator(), 3, true);
		ht.put("a", "a");
		ht.put("b", "b");
		ht.put("z", "z");
		ht.put("q", "q");
		ht.put("r", "r");
		ht.put("h", "h");
		ht.put("x", "x");
		ht.put("y", "y");
		ht.put("ra", "ra");
		ht.put("vf", "vf");
		ht.put("qq", "qq");
		ht.put("hsgd", "hsgd");
		ht.put("fz", "fz");
		ht.put("fzfzf", "fzfzf");
		ht.put("ttr", "ttr");
		ht.put("bhbh", "bhbh");
		ht.put("rtrtr", "rtrtr");
		ht.put("popo", "popo");
		ht.put("nhbh", 1);
		ht.put("fdy", 1);
		ht.put("ghjz", 1);
		ht.put("dfsaa", 1);
		ht.put("hiu", 1);
		ht.put("ngi", 1);
		ht.put("vnbxcm", 1);
		ht.put("uip", 1);
		ht.put("nfsudia", 1);
		ht.put("uids", 1);
		ht.put("gisuh", 1);
		ht.put("agfsdaf", 1);
		ht.put("fsaa", 1);
		ht.put("dfsafsda", 1);
		ht.put("fdsa", 1);
		ht.put("ahndhfn", 1);
		int oldsize = ht.size();
		assertNotNull(ht.remove("fdy"));
		assertNotNull(ht.remove("b"));
		assertNotNull(ht.remove("a"));
		assertNotNull(ht.remove("uids"));
		assertNotNull(ht.remove("fz"));
		assertNotNull(ht.remove("fzfzf"));
		assertNotNull(ht.remove("ahndhfn"));
		assertNotNull(ht.remove("bhbh"));
		
		//ht.printHexTrie();

		assertTrue(ht.get("fdy") == null);
		assertTrue(ht.get("b") == null);
		assertTrue(ht.get("a") == null);
		assertTrue(ht.size() == oldsize - 8);
	}
	
	public void testSmallHexTrieDelete() throws IllegalStructureException{
		HexTrie<Integer, Integer> ht = setUpSmallHexTrie();
		int [] delete = getSmallDelete();
		for (int key : delete){
			//System.out.println("deleting: "+Integer.toString(key));
			assertNotNull(ht.remove(new Integer(key)));
			//ht.printHexTrie();
			assertUniqueKeys(ht);
			Document outputDoc = ht.getXmlDocumentSnapshot();
			assertTrue(BPTreeValidator.validateOutputDocument(outputDoc, DefaultComparator.instance));
		}
		assertTrue(ht.size() == 0 && ht.isEmpty());
	}
	
	public void testBigBStarHexTrieDelete() throws Throwable{
		boolean isBstar = true;
		for (int leafOrder = 1; leafOrder <= 100; ++leafOrder){
			System.out.println("hextrie delete attempting: "+Integer.toString(leafOrder));
			HexTrie<Integer, Integer> ht = setUpBigHexTrie(leafOrder, isBstar);
			int currentKey = 0;
			try
			{
				int []delete = getBigDelete();
				for (int key : delete){
					currentKey = key;
					if (leafOrder == -1)
						System.out.println("deleting: "+Integer.toString(key));
					//if (key == -1 && leafOrder == -1)
					//	ht.printHexTrie();
					assertNotNull(ht.remove(new Integer(key)));
					assertUniqueKeys(ht);
					verifyOrder(ht.getRootNode(), leafOrder, isBstar);
				}
				assertTrue(ht.size() == 0 && ht.isEmpty());
			} catch (AssertionFailedError e){
				ht.printHexTrie();
				System.out.println(Integer.toString(leafOrder)+" failed at remove of key: "+Integer.toString(currentKey));
				e.printStackTrace();
				throw e;
			} catch (Throwable e){
				ht.printHexTrie();
				System.out.println(Integer.toString(leafOrder)+" failed at remove of key: "+Integer.toString(currentKey));
				e.printStackTrace();
				throw e;
			}
			//break;//TODO: take this out
		}
	}

public void testBigBplusHexTrieDelete() throws Throwable{
		boolean isBstar = false;
		for (int leafOrder = 1; leafOrder <= 100; ++leafOrder){
			System.out.println("hextrie delete attempting: "+Integer.toString(leafOrder));
			HexTrie<Integer, Integer> ht = setUpBigHexTrie(leafOrder, isBstar);
			int currentKey = 0;
			try
			{
				int []delete = getBigDelete();
				for (int key : delete){
					currentKey = key;
					if (leafOrder == -1)
						System.out.println("deleting: "+Integer.toString(key));
					//if (key == -1 && leafOrder == -1)
					//	ht.printHexTrie();
					assertNotNull(ht.remove(new Integer(key)));
					assertUniqueKeys(ht);
					verifyOrder(ht.getRootNode(), leafOrder, isBstar);
				}
				assertTrue(ht.size() == 0 && ht.isEmpty());
			} catch (AssertionFailedError e){
				ht.printHexTrie();
				System.out.println(Integer.toString(leafOrder)+" failed at remove of key: "+Integer.toString(currentKey));
				e.printStackTrace();
				throw e;
			} catch (Throwable e){
				ht.printHexTrie();
				System.out.println(Integer.toString(leafOrder)+" failed at remove of key: "+Integer.toString(currentKey));
				e.printStackTrace();
				throw e;
			}
			//break;//TODO: take this out
		}
	}
	
	private void assertUniqueKeys(HexTrie<Integer, Integer> map) throws AssertionFailedError {
		Set<Object> uniq = new HashSet<Object>(1000);
		for(Object key: map.keySet()){
			if (uniq.contains(key))
				throw new AssertionFailedError("non-unique keys found in set"+key.toString());
			uniq.add(key);
		}
	}
	
	@SuppressWarnings({ "rawtypes", "unchecked" })
	private boolean verifyOrder(Node root, int leafOrder, boolean isBstar) throws IllegalStructureException{
		if (root instanceof EndNode){
			return true;
		}
		if (root instanceof LeafNode){
			LeafNode node = (LeafNode)root;
			if (isUnderfull(node, leafOrder, isBstar) || isOverfull(node, leafOrder, isBstar)){
				throw new IllegalStructureException("node "+node.getKeys().toString()+" has the wrong amount of keys.");
			}
			return true;
		}
		if (root instanceof GuideNode){
			GuideNode node = (GuideNode)root;
			if (isUnderfull(node, isBstar)){
				throw new IllegalStructureException("node "+node.getGuides().toString()+" has too few guides.");
			}
			if (isOverfull(node, isBstar)){
				throw new IllegalStructureException("node "+node.getGuides().toString()+" has too many guides.");
			}
			if (node.getGuides().size() + 1 != node.getKids().size()){
				throw new IllegalStructureException("node "+node.getGuides().toString()+" has "+
						Integer.toString(node.getGuides().size()) + " but "+
						Integer.toString(node.getKids().size())+" children!");
			}
			boolean result = true;
			for (Node n : (List<Node>)node.getKids()){
				result = result && verifyOrder(n, leafOrder, isBstar);
			}
			return result;
		}
		throw new IllegalStructureException("uninstantiated node in tree: "+root.toString());
	}
	
	@SuppressWarnings("rawtypes")
	private boolean isOverfull(LeafNode node, int leafOrder, boolean isBstar)
	{
		if (isBstar && node.getParent() == null){// the node is the root node
			return node.getKeys().size() > leafOrder + (int)Math.floor(leafOrder / 3);
		} else {
			return node.getKeys().size() > leafOrder;
		}
	}
	
	@SuppressWarnings("rawtypes")
	private boolean isUnderfull(LeafNode node, int leafOrder, boolean isBstar)
	{
		if (node.getParent() == null)// the node is the root node
			return false;
		else
			return node.getKeys().size() < mustContain(leafOrder, isBstar);
	}
	
	@SuppressWarnings("rawtypes")
	private boolean isOverfull(GuideNode node, boolean isBstar){
		int leafOrder = 6;
		if (isBstar && node.getParent() == null){// the node is the root node
			return node.getKids().size() > leafOrder + 1; // seven
		} else {
			return node.getKids().size() > leafOrder;
		}
		
	}
	
	@SuppressWarnings("rawtypes")
	private boolean isUnderfull(GuideNode node, boolean isBstar){
		int leafOrder = 6;
		
		if (node.getParent() == null)// the node is the root node
			return false;
		else
			return node.getKids().size() < mustContain(leafOrder, isBstar);
	}
	
	private int mustContain(int leafOrder, boolean isBstar){
		if (isBstar){
			return (int)Math.floor((2.0 * leafOrder + 1) / 3.0);
		} else {
			return (int)Math.ceil(leafOrder / 2.0);
		}
	}
	
	@SuppressWarnings("rawtypes")
	public static class DefaultComparator implements Comparator{
		public static final DefaultComparator instance = new DefaultComparator();
		@SuppressWarnings("unchecked")
		@Override
		public int compare(Object k1, Object k2) {
			return ((Comparable)k1).compareTo(k2);
		}
		
	}
}

Web Accessibility