9
edits
Changes
From CMSC 420
JUnit Test for HexTrie Bplus and Bstar
<pre>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);
Document outputDoc = ht.getXmlDocumentSnapshot();
assertTrue(BPTreeValidator.validateOutputDocument(outputDoc, DefaultComparator.instance));
}
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);
Document outputDoc = ht.getXmlDocumentSnapshot();
assertTrue(BPTreeValidator.validateOutputDocument(outputDoc, DefaultComparator.instance));
}
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);
}
}
}
</pre>
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);
Document outputDoc = ht.getXmlDocumentSnapshot();
assertTrue(BPTreeValidator.validateOutputDocument(outputDoc, DefaultComparator.instance));
}
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);
Document outputDoc = ht.getXmlDocumentSnapshot();
assertTrue(BPTreeValidator.validateOutputDocument(outputDoc, DefaultComparator.instance));
}
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);
}
}
}
</pre>
