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 valueoriented 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 (also named ki) so that the binary search tree classes provided can import the KeyedItem class.

package ki;

public abstract class KeyedItem { //create single instance variable of type Comparable public KeyedItem(Comparable key) { key= }

public Comparable getKey() { }

//Use Comparable toString() method public String toString() { } }