b_treetestcasegdi.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_TreeTestCaseGDI 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_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_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 testInsertFile1_Balanced() {
		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("The Tree is not balanced!", isBalanced(test_tree.get(0)));
	}

	@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_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 testDeleteFile1_Balanced() {
		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("The Tree is not balanced!", isBalanced(test_tree.get(0)));
	}

	@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
		// correct!", 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 boolean isBalanced(TestNode t) {
		return getBalancedHeight(t) > -1;
	}

	/**
	 * @param t
	 *            the root of the checked subtree
	 * @return -1 if the subtree isnt balanced, and the height of the subtree,
	 *         if it is.
	 */
	protected int getBalancedHeight(TestNode t) {
		Vector<TestNode> children = t.getChildren();
		if (children.isEmpty())
			return 0;
		int height = getBalancedHeight(children.get(0));
		for (TestNode child : children) {
			if (height != getBalancedHeight(child))
				return -1;
		}
		return (height == -1) ? -1 : height + 1;
	}

	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;
	}
}