For this assignment you are to write a program which stores a set of records in an ordered dictionary implemented using a binary search tree (you do not need to implement an AVL tree). Each internal node of the binary search tree will store a record of the form (word,type,data), where word, type, and data are of type String. The attribute word of a record can be any string, while type and data can only have the following values:

text: this means that the data part of the record is any string,

audio: this means that the data part of the record is the name of an audio file. The only audio files that we will consider are of type .wav and .mid.

image: this means that the data part of the record is the name of an image file. The only image files that we will consider are of type .gif and .jpg.

In each record (word,type,data) the pair of attributes (word,type) will be used as the key. To process the binary tree we need to be able to compare the keys of the records. Comparison between two keys (word1,type1) and (word2,type2) is done in the following manner:

the keys are equal if word1 = word2 and type1 = type2;

the key (word1,type1) is smaller than the key (word2,type2)

if either: word1 lexicographically precedes word2, or word1 = word2 and type1 lexicographically precedes type2.

Consider, for example, an ordered dictionary storing the following records:

r1 =(computer,text,An electronic machine frequently used by Computer Science students.)

r2 =(computer,image,computer.gif)

r3 =(flower,image,flower.jpg)

r4 =(ping,audio,ping.wav)

r5 =(course,text,A series of lessons, for example CS888)

The key (computer,text) of r1 is larger than the key (computer,image) of r2 because image lexicographically precedes text. Also the key of r2 is smaller than the key (flower,image) of r3 because computer lexicographically precedes flower.

CREATE THE FOLLOWING CLASSES

Class Pair

This class represents the key attribute of a record in the ordered dictionary. Each key has two parts: word and type. Attribute word is a string of one or more letters; the letters in word must be converted to lower case. The attribute type can be text, audio, or image, as specified above. For this class you must implement all and only the following public methods: public Pair(String word, String type): A constructor which initializes a new Pair object with the specified word and type. public String getWord(): Returns the word stored in this Pair object. public String getType(): Returns the type stored in this Pair object. public int compareTo(Pair k): Returns 0 if the key stored in this Pair object is equal to k, returns -1 if the key stored in this Pair object is smaller than k, and it returns 1 otherwise.

Class Record

This class represents a record in the ordered dictionary. Each record consists of two parts: a key and the data associated with the key. For this class, you must implement all and only the following public methods: public Record(Pair key, String data): A constructor which initializes a new Record object with the specified key and data. If the type in the key is audio or image, then data stores the name of the corresponding audio or image file. 3 public Pair getKey(): Returns the key stored in this Record object. public String getData(): Returns the data stored in this Record object

Class Ordered Dictionary

This class implements an ordered dictionary using a binary search tree. You must use a Record object to store the data contained in each node of the tree. In your binary search tree only the internal nodes will store information. The leaves will be nodes storing null Record objects. The key for an internal node will be the Pair object from the Record stored in that node. Hint. You might want to implement a class Node to represent the nodes of the binary search tree. Each node will store a reference to a Record object, and references to its left child, right child, and parent. When comparing two node keys you need to use method compareTo from class Pair. In the OrderedDictionary class you must implement all the public methods specified in the OrderedDictionaryADT interface, shown below, and the constructor public OrderedDictionary() You can download OrderedDictionaryADT.java from the courses website. public interface OrderedDictionaryADT { /* Returns the Record object with key k, or it returns null if such a record is not in the dictionary. */ public Record get (Pair k); /* Inserts r into the ordered dictionary. It throws a DictionaryException if a record with the same key as r is already in the dictionary. */ public void put (Record r) throws DictionaryException; /* Removes the record with key k from the dictionary. It throws a DictionaryException if the record is not in the dictionary. */ public void remove (Pair k) throws DictionaryException; /* Returns the successor of k (the record from the ordered dictionary with smallest key larger than k); it returns null if the given key has no successor. The given key DOES NOT need to be in the dictionary. */ public Record successor (Pair k);/* Returns the record with smallest key in the ordered dictionary. Returns null if the dictionary is empty. */ public Record smallest (); /* Returns the record with largest key in the ordered dictionary. Returns null if the dictionary is empty. */ public Record largest (); } 4 To implement this interface, you need to declare your OrderedDictinary class as follows: public class OrderedDictionary implements OrderedDictionaryADT { . . . }

Class Dictionary Exception

This is the class implementing the class of exceptions thrown by the put and remove methods of OrderedDictionary

it will be helpful to create a node class