//IndexedSearchTree.java /** * A basic start on an indexed search tree data structure. * * @author Zach Tomaszewski * @version Dec 7, 2006 */ public class IndexedSearchTree { /** whether to print debugging/tracing information from some methods */ protected static boolean TRACE_ON = false; /** * Runs a few tests, and prints results to the screen. * * @param args Not used. */ public static void main(String[] args) { System.out.println("--TESTS FROM ASSIGNMENT SHEET--"); TRACE_ON = true; /* Normally I print expected results or else what I'm testing, * but expected output is already printed on the assignment sheet. * Output should match (except perhaps minor formatting differences). */ System.out.println("Creating data nodes:"); DataNode a, b, c, d, e, f, g; a = dataMerge(2, 1, 4, 2); b = dataMerge(6, 3, 8, 4); c = dataMerge(10, 5, -1, 0); d = dataMerge(12, 6, 14, 7); e = dataMerge(16, 8, -1, 0); System.out.println(); System.out.println("Creating index nodes:"); IndexNode h, i, j, k; i = indexMerge(a, b, c); j = indexMerge(d, e, null); k = indexMerge(i, j, null); System.out.println(); System.out.println("Finding:"); find(k, 14); find(k, 11); System.out.println(); System.out.println("Testing ordering within nodes:"); f = dataMerge(17, 9, 15, 10); g = dataMerge(15, 11, 17, 12); h = indexMerge(e, g, null); System.out.println(); System.out.println("Printing:"); System.out.print("OUTPUT: "); print(k); //print(g); -- defined print in such a way as to avoid this error System.out.println(); TRACE_ON = false; System.out.println("\n"); System.out.println("--EXTRA TESTS WITH DIFFERENT DATA TYPE--"); /* * The advantage of abstraction (writing Nodes to take Comparables) * means I can reuse them with different data types, as below. * This abstraction does not necessitate using generics, though generics * give me a certain about of compile-time checking to guarantee * that I'm not accidently mixing different, incompatible types * in the same data structure. */ String[] names = {"BOB", "WILMA", "BARNEY", "BETTY", "FRED", "THELMA", "SHAGGY", "SCOOBY"}; System.out.println("Making tree with: " + java.util.Arrays.toString(names)); //pre sorting required as not sorting across data nodes at all java.util.Arrays.sort(names); //build a queue of data nodes containing String names java.util.Queue nodes = new java.util.LinkedList(); for (int n = 0; n < names.length; n++) { //fill each data node with 2 items, if possible KeyedValue data1 = new KeyedValue(names[n], 10D + n); KeyedValue data2 = null; if (++n < names.length) { data2 = new KeyedValue(names[n], 10D + n); } nodes.add(new DataNode(data1, data2)); } //now go through and connect all data nodes to index nodes //(reusing the nodes queue for IndexNodes -- lazy?) while (nodes.peek() instanceof DataNode) { DataNode data1, data2, data3; data1 = (DataNode) nodes.poll(); data2 = (nodes.peek() instanceof DataNode) ? //also fails if queue empty (DataNode) nodes.poll() : null; data3 = (nodes.peek() instanceof DataNode) ? (DataNode) nodes.poll() : null; nodes.offer(new IndexNode(data1, data2, data3)); } //sigh... now have all our index nodes. So connect those together while (nodes.size() > 1) { //nodes.poll() will give null if queue is empty nodes.offer(new IndexNode((Node) nodes.poll(), (Node) nodes.poll(), (Node) nodes.poll())); } IndexNode tree = (IndexNode) nodes.poll(); System.out.println("Constructed tree contains: "); print(tree); //"Scooby, dooby, doo, where are you?" System.out.println("\n\nFinding \"SCOOBY\": " + find(tree, "SCOOBY")); TRACE_ON = true; System.out.println("\nFinding \"SCOOBY\" w/ tracing on: "); System.out.println(find(tree, "SCOOBY")); System.out.println("\nFinding \"WILMA\" w/ tracing on: "); System.out.println(find(tree, "WILMA")); TRACE_ON = false; System.out.println("\nTests DONE!"); }//end main /** * Constructs and returns a new data node. * If TRACE_ON set to true, then prints out trace info for tests. */ protected static DataNode dataMerge(int k1, int v1, int k2, int v2){ //create KeyedValues if given valid int keys, otherwise use nulls KeyedValue first, second; first = (k1 > 0) ? new KeyedValue(k1, v1) : null; second = (k2 > 0) ? new KeyedValue(k2, v2) : null; /* my DataNode doesn't throw an exception if data keys are out of order * so, instead of catching an exception here, I'll test for misordered * keys and report it for testing purposes, showing I pass that test. */ if (TRACE_ON && first != null && first.compareTo(second) > 0) { System.out.println("OUTPUT: data keys not in order " + "(but constructor will order them)"); } //now create data node with keyed values DataNode dn = new DataNode(first, second); if (TRACE_ON){ System.out.println("OUTPUT: " + dn); } return dn; } /** * Constructs and returns a new index node, * printing out trace info as it does. */ protected static IndexNode indexMerge(Node d1, Node d2, Node d3) { /* my DataNode doesn't throw an exception if data nodes are out of order * so, instead of catching an exception here, I'll test for misordered * nodes and report it for testing purposes, showing I pass that test. */ if (TRACE_ON && d1 != null && d2 != null && (d1.compareTo(d2) > 0 || d2.compareTo(d3) > 0)) { System.out.println("OUTPUT: data nodes not in order " + "(but constructor will order them)"); } IndexNode in = new IndexNode(d1, d2, d3);; if (TRACE_ON) { //Don't want to put TRACE flag in nodes, so will so trace here manually. //No functionality here--just for printing trace info System.out.print("TRACE: "); //trace to find smallest key at each level for each subtree/child. //(skipping first pointer/subtree in node) for (int i = 1; i < in.pointers.length; i++) { Node child = in.pointers[i]; if (child == null) { System.out.print("null."); continue; //don't process nulls any further } while (child instanceof IndexNode) { //go through all index nodes until reach data node System.out.print("minI=" + ((IndexNode) child).minKeys[0] + ", "); child = ((IndexNode) child).pointers[0]; } //now down to the data node assert (child instanceof DataNode): "Node is neither Index nor Data node"; System.out.print("minD=" + ((DataNode) child).data[0] + ". "); } System.out.println(); System.out.println("OUTPUT: " + in); } return in; } /** * Determines minimum key in subtree rooted at node. */ protected static Comparable min(Node node) { return node.getMinKey(); } /** * Given a valid indexed tree rooted at an index node and a * key to find, returns the data node containing (or that should * contain) that data item. * * @param tree An index node with child nodes to search through. * @param key The key of the data item to find in the tree * @return The DataNode in which the data item is found, or * in which it should be placed if it is not already * in the tree. */ protected static DataNode find(IndexNode tree, Comparable key) { //==CODE REMOVED== return null; } /** * Prints the data in the leaves of the given tree. * As an indexed search tree is only valid if the root * is an index node, this method accepts only an IndexNode * (rather than general Node). * * @param tree The root of the tree * for which to print all the data elements */ protected static void print(IndexNode tree) { //==CODE REMOVED== } }//end IndexedSearchTree