Write a treeSort method that accepts an array of KeyedItems (see later) and uses a specific traversal of a binary search tree to sort the array. As KeyedItem is an abstract class, objects must extend KeyedItem if they are to be sorted with the treeSort method.

Iterator

The Iterator interface will allow you to visit all of the items in a collection. The interface is very easy to use. The hasNext() method tells you whether there are more items to process, and the next() method will retrieve the next item to process. Use a while loop to continue processing elements in a collection until hasNext() is false.

public boolean hasNext() //are there any more items to process?

public Object next() //get the next item in the collection to process

Lab:

Comparable ("natural ordering")

KeyedItem (immutable)

CD

o Song

Sorting

o TreeSort

Part I: KeyedItem (immutability)

The idea behind the abstract KeyedItem class is that the object extending this class has a field/instance variable (the key) that should not be changed after it has been set in the constructor (immutability). This key is then the field that value-oriented data

structures will use to place or find the corresponding object in the collection. If this key is not protected from change, the value-oriented data structure containing the object can be corrupted.

Write the abstract KeyedItem class. It has a single instance variable of type Comparable so that value-oriented data structures can compare keys and determine where to place or find the object with that key, and this instance variable is set only once by the constructor. There is a getKey method that returns the key, but no setKey method. Note that the getKey method exposes the key and can result in the key being changed unless the key itself is immutable. The String class and the primitive wrapper classes are immutable and Comparable, so these types can be safely used as keys. It is possible to use other classes as keys (as long as they are Comparable), but you must be very careful in writing such classes to maintain immutability of the key.

Put KeyedItem in a package called ki, placing it in the appropriate subdirectory so that the binary search tree classes provided can import the KeyedItem class.

jar cvf ki.jar KeyedItem.java: PLEASE SEE LINK: https://www.dropbox.com/s/f0yq23m9svoiyel/KeyedItem.java?dl=0

Part II: CD

Download the following files:

FileIOException.java PLEASE SEE LINK: https://www.dropbox.com/s/x5k4fu5kizjmo7l/FileIOException.java?dl=0

//has the following public interface:

FileIO.java PLEASE SEE LINK:

https://www.dropbox.com/s/9qoa0wl8m5cxzkw/FileIO.java?dl=0

//has the following public interface:

o FileIO(String fileName, int operation) //either FileIO.FOR_READING or FileIO.FOR_WRITING

o boolean EOF() //has the end of the file been reached?

o String readLine()

o void writeLine(String line)

o void close() //close the file when you are done, especially when writing to a file

Song.java PLEASE SEE LINK:

https://www.dropbox.com/s/ar9ronaghhd5hl3/Song.java?dl=0

//constructor takes the title and the length of the Song as Strings

CD.java PLEASE SEE LINK:

https://www.dropbox.com/s/7tn0c10d2fbsnci/CD.java?dl=0

//the year is the search key

Complete the CD class by extending KeyedItem. Set the year of the CD as the key field (use the primitive wrapper class for integers, the Integer class). Make sure that there is no setYear method in your CD class to ensure that the key is immutable. A getYear method is not necessary as KeyedItem already has a getKey method. Write the following two methods:

public Song getSong(int index)

public void addSong(String title, String length) //create the song and then add it

Part III: Tree Sort

Download the jar file containing the binary search tree classes that you will need to import

bst.jar PLEASE SEE LINK: https://www.dropbox.com/s/b5fsc8lra9iga04/bst.jar?dl=0

Complete the following two methods in a utility class (TreeSort.java) PLEASE SEE LINK: https://www.dropbox.com/s/7p5vmntc0lbykj1/TreeSort.java?dl=0

public static KeyedItem[] treeSort(KeyedItem[] unsorted) //convenience method to sort all of the items in the array (calls the next method)

public static KeyedItem[] treeSort(KeyedItem[] unsorted, int n) //sort the first n items in the array (check n for validity)

As a convenience to the user, the array passed in (unsorted) is not directly sorted. Instead, create a new array with size equal to the number of items to be sorted. Return this new array with the items in sorted order just in case the unsorted array is still needed by the user for some reason.

There is a potential problem with creating a new array and returning it to the user, however. You don't know the actual type of the objects in the array, just their supertype (KeyedItem). You can create and return an array of type KeyedItem[], but if the user needs a particular object in the sorted array, they will have to downcast from KeyedItem to the actual type of the object. If you need to process all of the items in the array, that is a lot of casting.

Instead, you can use the Class class and the Array class to figure out what the actual type of the objects in the array are, and create an array of that type. To get the type of the array, use the getComponentType() method in the Class class. Your driver will still need to downcast the array as a whole from KeyedItem[] to the type of the array, but you won't need to cast each individual object in the array. To accomplish this, refer to the Java API. We also covered this in class. Hint: you are interested in the newInstance method in the Array class.

Refer to the BinarySearchTree documentation to create a BST that will allow duplicate keys and will preserve FIFO ordering for duplicate keys. Place all of the items from the unsorted array into the tree and perform the appropriate traversal to get the items back out in sorted order (look at the documentation for the Iterator and TreeIterator interfaces). Place the sorted items in the array that you instantiated and that will be returned to the user. What is the order notation for this sort? Is it stable?

Part IV: Tree Sort Driver

Download the following files:

TreeSortDriver.java PLEASE SEE LINK:

https://www.dropbox.com/s/8e44ia7k3t0nd76/TreeSortDriver.java?dl=0

Keyboard.java PLEASE SEE LINK:

https://www.dropbox.com/s/hc9eopqvotayo9n/Keyboard.java?dl=0

make.bat PLEASE SEE LINK:

https://www.dropbox.com/s/96647qnv3j6lt4y/make.bat?dl=0

cds.txt PLEASE SEE LINK:

https://www.dropbox.com/s/omlqtiqdjxrnwgk/cds.txt?dl=0

Complete the provided driver to test your work. You may want to write a make.bat file that includes the classpath information that you need for the jar file. You will also need to refer to the FileIO documentation (see the top of the lab). Use try-catch to continue to prompt for a valid file until the end user enters one.