b_treetestcase.java

自己上学时写的Btree算法

/**
 * B_TreeTestCase
 *
 */

import org.junit.Test;
import junit.framework.TestCase;
import java.util.Vector;
import java.util.Collections;

/**
 * TestCases for the forth lab.
 *
 * @author Kun Fang
 */
public class B_TreeTestCase extends TestCase {
    Vector<TestNode> nodes = new Vector<TestNode>();
    Vector<String> node_names = new Vector<String>();
    Vector<String> pointers = new Vector<String>();
    
    public static void main(String[] args) {
        junit.textui.TestRunner.run(B_TreeTestCase.class);
    }
    
    
    @Test public void testInsertFile1_NumberOfNodes() {
        B_Tree b = new B_Tree(2);
        b.constructB_TreeFromFile("TestFile.txt");
        Vector<String> out = b.getB_Tree();
        Vector<TestNode> test_tree = this.constractB_Tree(out);
        assertEquals("Number of nodes not correct!", 10, test_tree.size());
    }
    
    @Test public void testInsertFile1_HeightOfTree() {
        B_Tree b = new B_Tree(2);
        b.constructB_TreeFromFile("TestFile.txt");
        Vector<String> out = b.getB_Tree();
        Vector<TestNode> test_tree = this.constractB_Tree(out);
        assertEquals("Height of the tree not correct!", 3, b.getB_TreeHeight());
    }
    
    @Test public void testInsertFile1_NumberOfEntries() {
        B_Tree b = new B_Tree(2);
        b.constructB_TreeFromFile("TestFile.txt");
        Vector<String> out = b.getB_Tree();
        Vector<TestNode> test_tree = this.constractB_Tree(out);
        assertEquals("Number of the entries is not correct!", 22, b.getB_TreeSize());
    }
    
    @Test public void testInsertFile1_NodesOfTree() {
        B_Tree b = new B_Tree(2);
        b.constructB_TreeFromFile("TestFile.txt");
        Vector<String> out = b.getB_Tree();
        Vector<TestNode> test_tree = this.constractB_Tree(out);
        testNode("root", nodes.get(0), 1, 2, "GFV8X4TT0");
        testNode("node"+1, nodes.get(1), 2, 3, "4OVZBRS9FDP56R7OTD");
        testNode("node"+2, nodes.get(2), 3, 4, "JZXHZFCB6NXM6F6UWJVM22T8ESM");
        testNode("node"+3, nodes.get(3), 2, 0, "14ST01GLP319BCWVH9");
        testNode("node"+4, nodes.get(4), 2, 0, "8ENSQEGV99BTCH8AHW");
        testNode("node"+5, nodes.get(5), 2, 0, "E465LZPOEFMF1QTZ0Q");
        testNode("node"+6, nodes.get(6), 2, 0, "HRR27B6JYIUS3K395W");
        testNode("node"+7, nodes.get(7), 2, 0, "KC83OJVA8L2Z7499YH");
        testNode("node"+8, nodes.get(8), 4, 0, "OTYAH43JXSSG24YXB1TY4L8P0D3U36TUQ5NO");
        testNode("node"+9, nodes.get(9), 2, 0, "W0KBB1RE7YMUEM9LVC");
    }
    
    @Test public void testInsertFile1_InOrderTraversal() {
        B_Tree b = new B_Tree(2);
        b.constructB_TreeFromFile("TestFile.txt");
        Vector<String> out = b.getB_Tree();
        Vector<TestNode> test_tree = this.constractB_Tree(out);
        assertTrue("getInorderTraversal() doesn't deliver entries in inorder traversal!", testOrderOfEntries(b.getInorderTraversal()));
    }
    
    @Test public void testDeleteFile1_ReturnedEntries() {
        B_Tree b = new B_Tree(2);
        b.constructB_TreeFromFile("TestFile.txt");
        Entry e1 = b.delete("L2Z7499YH");
        Entry e2 = b.delete("FMF1QTZ0Q");
        Entry e3 = b.delete("L2Z74TZ0Q");
        Vector<String> out = b.getB_Tree();
        Vector<TestNode> test_tree = this.constractB_Tree(out);
        assertEquals("delete(L2Z7499YH) output not correct!", "L2Z74;99YH;Error", e1.toString());
        assertEquals("delete(FMF1QTZ0Q) output not correct!", "FMF1Q;TZ0Q;Error", e2.toString());
        assertTrue("delete(L2Z74TZ0Q) output not correct!", null == e3);
    }
    
    @Test public void testDeleteFile1_NumberOfNodes() {
        B_Tree b = new B_Tree(2);
        b.constructB_TreeFromFile("TestFile.txt");
        Entry e1 = b.delete("L2Z7499YH");
        Entry e2 = b.delete("FMF1QTZ0Q");
        Entry e3 = b.delete("L2Z74TZ0Q");
        Vector<String> out = b.getB_Tree();
        Vector<TestNode> test_tree = this.constractB_Tree(out);
        
        assertEquals("Number of nodes not correct!", 9, test_tree.size());
    }
    
    @Test public void testDeleteFile1_HeightOfTree() {
        B_Tree b = new B_Tree(2);
        b.constructB_TreeFromFile("TestFile.txt");
        Entry e1 = b.delete("L2Z7499YH");
        Entry e2 = b.delete("FMF1QTZ0Q");
        Entry e3 = b.delete("L2Z74TZ0Q");
        Vector<String> out = b.getB_Tree();
        Vector<TestNode> test_tree = this.constractB_Tree(out);
        assertEquals("Height of the tree not correct!", 3, b.getB_TreeHeight());
    }
    
    @Test public void testDeleteFile1_NumberOfEntries() {
        B_Tree b = new B_Tree(2);
        b.constructB_TreeFromFile("TestFile.txt");
        Entry e1 = b.delete("L2Z7499YH");
        Entry e2 = b.delete("FMF1QTZ0Q");
        Entry e3 = b.delete("L2Z74TZ0Q");
        Vector<String> out = b.getB_Tree();
        Vector<TestNode> test_tree = this.constractB_Tree(out);
        assertEquals("Number of the entries is not correct!", 20, b.getB_TreeSize());
    }  
    
    @Test public void testDeleteFile1_NodesOfTree() {
        B_Tree b = new B_Tree(2);
        b.constructB_TreeFromFile("TestFile.txt");
        Entry e1 = b.delete("L2Z7499YH");
        Entry e2 = b.delete("FMF1QTZ0Q");
        Entry e3 = b.delete("L2Z74TZ0Q");
        Vector<String> out = b.getB_Tree();
        Vector<TestNode> test_tree = this.constractB_Tree(out);
        testNode("root", nodes.get(0), 1, 2, "JZXHZFCB6");
        testNode("node"+1, nodes.get(1), 2, 3, "4OVZBRS9FGFV8X4TT0");
        testNode("node"+2, nodes.get(2), 2, 3, "SSG24YXB1VM22T8ESM");
        testNode("node"+3, nodes.get(3), 2, 0, "14ST01GLP319BCWVH9");
        testNode("node"+4, nodes.get(4), 4, 0, "8ENSQEGV99BTCH8AHWDP56R7OTDE465LZPOE");
        testNode("node"+5, nodes.get(5), 2, 0, "HRR27B6JYIUS3K395W");
        testNode("node"+6, nodes.get(6), 3, 0, "KC83OJVA8NXM6F6UWJOTYAH43JX");
        testNode("node"+7, nodes.get(7), 2, 0, "TY4L8P0D3U36TUQ5NO");
        testNode("node"+8, nodes.get(8), 2, 0, "W0KBB1RE7YMUEM9LVC");
    }
    
    @Test public void testDeleteFile1_InOrderTraversal() {
        B_Tree b = new B_Tree(2);
        b.constructB_TreeFromFile("TestFile.txt");
        Entry e1 = b.delete("L2Z7499YH");
        Entry e2 = b.delete("FMF1QTZ0Q");
        Entry e3 = b.delete("L2Z74TZ0Q");
        Vector<String> out = b.getB_Tree();
        Vector<TestNode> test_tree = this.constractB_Tree(out);
        
        assertTrue("getInorderTraversal() doesn't deliver entries in inorder traversal!", testOrderOfEntries(b.getInorderTraversal()));
    }
    
    @Test public void testfindFile1_ReturnedEntries() {
        B_Tree b = new B_Tree(2);
        b.constructB_TreeFromFile("TestFile.txt");
        Entry e1 = b.find("SSG24YXB1");
        Entry e2 = b.find("SSG27YXB1");
        assertEquals("find(SSG24YXB1) output not correct!", "SSG24;YXB1;Error", e1.toString());
        assertTrue("find(SSG27YXB1) output not correct!", null == e2);
    }
    
    @Test public void testConstructB_TreeFromFile2() {
        B_Tree b = new B_Tree(3);
        b.constructB_TreeFromFile("TestFile.txt");
        //assertEquals("Number of inserted entries into the B-Tree is not correst!", 51, 51);
    }
    
    protected void testNode(String name, TestNode t, int n_e, int n_ch, String ent) {
        assertEquals("Number of entries of"+name+" not correct!", n_e, t.getEntries().size());
        assertEquals("Number of childen of"+name+" not correct!", n_ch, t.getChildren().size());
        assertEquals("Entries of "+name+" not correct!", ent, t.entriesToString());
    }
    
    protected boolean testOrderOfEntries(Vector<Entry> e) {
        for(int i=0;i<e.size()-1;i++) {
            if(e.elementAt(i).compareTo(e.elementAt(i+1)) >= 0) {
                return false;
            }
        }
        return true;
    }
    
    protected void parseB_Tree(Vector<String> output, int k) {
        int i=0;
        String line;
        while (i<output.size()) {
            line = output.elementAt(i);
            /**only progress if the word "Digraph" and "}" is not contained
             * in the line. "Digraph" is only contained in the first and
             * "}" only in the last line.*/
            if (!line.contains(DotFileConstants.DOT_FILE_DIGRAPH)
            && !line.contains(DotFileConstants.DOT_FILE_CLOSE_BRACKET)
            && !line.contains(DotFileConstants.DOT_FILE_SOURCE)) {
                
                //progress a node
                if(line.contains(DotFileConstants.DOT_FILE_LABEL_START)) {
                    progressNode(line, k);
                }
                //progress a pointer
                else if(line.contains(DotFileConstants.DOT_FILE_EDGE)) {
                    progressPointer(line);
                }
            }
            i++;
        }
    }
    
    protected void progressNode(String line, int k) {
        TestNode result = new TestNode(k);
        String[] names = line.split("\\[");
        String[] entries = (line.split("\""))[1].split("\\|?+<f[0-9]+>\\*?+\\|?+");
        for(int i=0;i<entries.length;i++) {
            if(!entries[i].equals("")) {
                Entry e = new Entry();
                e.setKey(entries[i]);
                result.addEntry(e);
            }
        }
        node_names.add(names[0].trim());
        nodes.add(result);
    }
    
    protected void progressPointer(String line) {
        String pointer = (line.split(";"))[0];
        pointers.add(pointer.trim());
    }
    
    
    protected Vector<TestNode> constractB_Tree(Vector<String> output) {
        Vector<TestNode> r = new Vector<TestNode>();
        parseB_Tree(output, 2);
        Collections.sort(pointers);
        TestNode root = nodes.elementAt(node_names.indexOf("root"));
        Vector<String> pts = new Vector<String>();
        for(int i=0;i<pointers.size();i++) {
            String[] p = pointers.elementAt(i).split("->");
            String parent = (p[0].split(":"))[0];
            pts.add(parent.trim());
            pts.add(p[1].trim());
        }
        for(int i=0;i<pts.size();i=i+2) {
            nodes.elementAt(node_names.indexOf(pts.elementAt(i))).addChild(nodes.elementAt(node_names.indexOf(pts.elementAt(i+1))));
        }
        
        r.add(root);
        int i=0;
        while(i<r.size()) {
            r.addAll(r.elementAt(i).getChildren());
            i++;
        }
        return r;
    }
}