Assignment 7

Submission

• Email your assignment to ztomasze@hawaii.edu.
• Attach the source code to your email. Send me only the source code (.java files); do not include the .class or any other files. Do not zip or otherwise bundle the .java files.

Requirements

As stated on the assignment handout, you must:

• Write five methods relevant to an indexed search tree: dataMerge, indexMerge, min, find, and print.

Suggestions

Updated 07 Dec: Added Sorter and some minor changes to the other two classes, including extra tests in main to demonstrate the value of abstraction. Also posted non-generic versions of my classes. Clarified grading requirements that exceptions are acceptable instead of sorting mis-ordered input.

Do this however you want, so long as it meets the requirements of the assignment. (See the assignment handout and the grading criteria, below, for more on this.)

However, I recommend you create a Node class, with DataNode and IndexNode subclasses. A KeyedValue class can hold your key and value together in a single object. Then your five required methods would go in a fifth class.

Here is my partial code for these classes.

• Node.java --Includes Node, DataNode, IndexNode, and KeyedValue
• IndexedSearchTree.java --Includes the 5 methods requested by the assignment, plus the tests from the handout in main. The methods dataMerge, indexMerge, and min are filled in, but they call the appropriate methods and constructors in the node classes that do the real work. These node methods are not complete, and you will need to understand how I implemented the nodes to complete them. The find and print methods are also completely empty.
• Sorter.java --If nulls in your array are causing you trouble, try using this nullSafeSort method.

Here is some sample output produced by the complete code. You can also see the generated JavaDoc pages.

Feel free to use this code however you like--as a framework or just for ideas. If you do adopt it and add to it, please keep the comments up-to-date. (Remove //comments that no longer apply, change the /** javadoc */ documentation if you change how a method works, etc.) Remember to add an @author tag for yourself in the class docs.

As I'm still learning generics myself (new in Java 5.0), my code uses them a lot. You can learn more about generics in this Java tutorial thread. My code does include three warnings associated with trying to construct arrays with generics. After a few hours of research, I've discovered that this is largely unavoidable. (I also discovered that compiling java.util.PriorityQueue produces 25 warnings, and java.util.ArrayList produces 8 warnings. So this seems pretty common with Java 5.0.) This page sums up the basic issues at work here.

If you find generics confusing, here are non-generic version of the above files with all generics removed (even for Comparable). This is what code looked like before Java 5.0. Notice that I maintained the abstraction in KeyedValue class--keys are stored as Comparables and values as Objects. This means the code is still reusable with data types other than Integers. (Note that I didn't bother to write reusable versions of the dataMerge and indexMerge methods though.) To use these files, they need to be renamed, removing the "ng" prefix.

• ngNode.java
• ngIndexedSearchTree.java

My code also includes a few other idioms you may not have seen much, but that you should become familiar with. (You should be able to understand my code, even if you disagree with how I wrote it.) These include the instanceof and ternary operator (? :), an abstract class, assertions, and a debug-print flag (TRACE_ON, in this case). I'd be happy to talk about this more in lab, or I can point you to references in the Java Tutorial, if you're curious about any of these.

Grading:

Out of 100 points:

10 - Compiles

15 - dataMerge and/or a data node constructor

You have a way to construct a data node. Once a data node is constructed, it is guaranteed that items within that node are in sorted order (5 points). (If you prefer, you can throw an exception when input is out of order, instead of sorting it.)

15 - indexMerge and/or an index node constructor

You have a way to construct an index node. The pointers to subtrees within the index node should sorted in term of the subtree's minimum data (key) values (5 points). (Again, an exception instead of sorting is fine.)

15 - min and/or some sort of min function in your nodes

Given a node, you can find the minimum data (key) value in it or its subtrees.

20 - find

Given a tree (rooted at an index node) and a key to find, returns the data node that the key should be found in. (The behavior of such a find method means it could be used by a "get" method to retrieve data from the tree, but also by an "add" method to determine which data node to insert a new key into.)

15 - print

Prints the data (keys, or keys and value) found in the leaves of a given tree. Prints the keys in sorted order.

10 - main/output

Main should include sample tests. (Reproducing the TRACE lines of the output are worth 4 points of this.)