The goal of this project is to implement a Dictionary ADT in Java based on the linked list data structure. The elements of the Dictionary will be pairs of Strings called key and value respectively. Keys will be distinct, whereas values may be repeated. Thus any two (key, value) pairs must have different keys, but may possibly have identical values.

I would like Dictionary.java (do not implement java.util.HashSet or java.util.Set), DictionaryTest.java, DuplicateKeyException.java, and KeyNotFoundException.java coded (DictionaryInterface.java and DictionaryClient.java are left untouched though and served just as reference) and verify in your answer that the DictionaryClient unix output matches what is shown in the beginning of page 3.

Specifically, I'd like DictionaryTest.java to fit within its description:

"Create another file called DictionaryTest.java whose purpose is to serve as a test client for the Dictionary ADT while it is under construction. This file will define the class DictionaryTest, which need not contain any more than a main() method (although you may add other static methods at your discretion.) The design philosophy here is that an ADT should be thoroughly tested in isolation before it is used in any application. Build your Dictionary ADT one method at a time, calling each operation from within DictionaryTest.java to wring out any bugs before going on to the next method. The idea is to add functionality to the Dictionary in small bits, compiling and testing as you go. This way you are never very far from having something that compiles, and errors that arise are likely to be confined to recently written code. You will submit the file DictionaryTest.java with this project. It is expected that it will change significantly during the testing phases of your project. As that happens, comment out the old test code as you insert tests of more recently written operations. The final version of DictionaryTest.java should contain enough test code (possibly all in comments) to convince the grader that you did in fact test your ADT in isolation before proceeding."

I would appreciate the help and hopefully the result prints out that exact output.

CMPS 12B Introduction to Data Structures Programming Assignment 3 The goal of this project is to implement a Dictionary ADT in Java based on the linked list data structure. The elements of the Dictionary will be pairs of Strings called key and value respectively. Keys will be distinct, whereas values may be repeated. Thus any two (key, value) pairs must have different keys, but may possibly have identical values. You can think of a key as being an account number, and a value as say an account balance, both represented by Strings. Recall that an ADT consists of two things: (1) a collection of states, and (2) a collection of operations that act on states. In the Dictionary ADT a state is simply a finite set of (key, value) pairs. There are seven ADT operations to be implemented by the methods below lic boolean isEmpty) Returns true if the Dictionary contains n s, false otherwise. public int size) Returns the number of (key, value) pairs in the Dictionary public String lookup (String key) If the Dictionary contains a pair whose key field matches the argument key, lookup returns the associated value field. If no such pair exists in the Dictionary, a null reference is returned. public void insert (String key, String value) If the Dictionary does not currently contain a pair whose key matches the argument key, then the pair (key value) is added to the Dictionary. If such a pair does exist, a DuplicateKeyException will be thrown with the message: "cannot insert duplicate keys". Thus insert has the precondition that the Dictionary does not currently contain the argument key. This precondition can be tested by the client module by doing lookup (key) -null. public void delete (String key) If the Dictionary currently contains a pair whose key field matches the argument key, then that pair is removed from the Dictionary. If no such pair exists, then a KeyNot FoundException is thrown with the message: "cannot delete non-existent key". Thus delete ) has the precondition that the Dictionary currently contains the argument key. This precondition can be tested by the client module by doing lookup (key)null. public void makeEmpty Resets the Dictionary to the empty state. public String toString ) Returns a String representation of the current state of the Dictionary. Keys will be separated from values by a single space, and consecutive pairs will be separated by newline characters. The return String will be terminated by a newline character. Pairs will occur in the return String in the same order they were inserted into the Dictionary Implementation of the Dictionary ADT An interface file for the Dictionary ADT (DictionaryInterface.java) with prototypes for the above methods will be provided on the class webpage. The implementation file for the Dictionary ADT, which you will write, will be called Dictionary.java. In it you will define the Dictionary class and explicitly implement the interface,.e. the class heading will be: public class Dictionary implements DictionaryInterface You will turn in the interface file with your project, but you are not to alter the contents of that file in any way (don't even put in the customary comment block with your name). In addition to the implementation file you will also write files DuplicateKeyException.java and KeyNotFoundException.java which define the two types of exception classes to be thrown. Make both of these exceptions to be subclasses of RuntimeException, and follow the examples given in lecture and on the webpage. Your implementation of the Dictionary ADT will utilize a linked list data structure. The linked list may be any of the variations discussed in class (c.g. singly linked with head reference, singly linked with both head and tail reference, circular, doubly linked, with or without dummy node(s), or any combination of the preceding types.) It is recommended that you take the linked list representation of the IntegerList ADT as a starting point for this project. Just rename that file and start making changes to it. In particular your Node class must be a private inner class to the Dictionary class. However, your Node class will no longer contain an int field since the data stored at each node will be a pair of Strings. You have two options for storing pairs. The first (simpler and recommended) option is to define your Node class to contain two String fields instead of a single data field. The second option is to let the Dictionary class contain another private inner class called Pair encapsulating the two Strings in fields called key and value respectively. The data field in your Node would then be of type Pair. State which option you are using in your README file. I is recommended that your Dictionary class contain a private method with the following heading private Node findKey (String key) This method should return a reference to the Node containing its argument key, or return null if no such Node exists. Such a method will be helpful in implementing the methods insert , delete) and lookup ) Testing Create another file called DictionaryTest.java whose purpose is to serve as a test client for the Dictionary ADT while it is under construction. This file will define the class DictionaryTest, which need not contain any more than a main method (although you may add other static methods at your discretion.) The design philosophy here is that an ADT should be thoroughly tested in isolation before it is used in any application. Build your Dictionary ADT one method at a time, calling each operation from within DictionaryTest.java to wring out any bugs before going on to the next method. The idea is to add functionality to the Dictionary in small bits, compiling and testing as you go. This way you are never very far from having something that compiles, and errors that arise are likely to be confined to recently written code. You will submit the file DictionaryTest.java with this project. It is expected tha t wll change significantly during the testing phases of your project. As that happens, comment out the old test code as you insert tests of more recently written operations. The final version of DictionaryTest.java should contain enough test code (possibly all in comments) to convince the grader that you did in fact test your ADT in isolation before proceeding. Once you believe a ADT operations are working properly, copy the files DictionaryClient.java and Makefile to your working directory (both provided on the webpage). At this point %make will create an executable jar file in your working directory called DictionaryClient. This program will have the following output. (Recall that s here represents the Unix prompt.) DictionaryClient 2 b 3 c 4 d 5 e key-1 key#3 key=7 key-8 value-a value-c value-g not found 2 b 4 d 5 e false true If your Dictionary ADT behaves according to specs, your output should look exactly as above. You can check this by doing Dictionaryclient > out, copy the file mode1-out from the webpage to your working directory, then do % diff out model-out. If diff gives no output, then the files are exactly the same, which is good. Note the unix operator redirects program output to a file. In other words it associates the data stream stdout with the file on its right hand side, instead of the terminal window Similarly the unix operatorassociates the file on its right hand side with the data stream stdin, instead of the keyboard. See the man pages for a description of the diff command. What to turn in You may alter the provided Makefile to include submit and test utilities, or alter it in any other way you see fit, as long as it creates an executable jar file called DictionaryClient, and includes a clean utility. Do not alter the files DictionaryInterface.java or DictionaryClient.java however. Thus you will submit eight files in all to pa3. README Dictionary.java DictionaryTest.java DuplicateKeyException.java KeyNotFoundException.java DictionaryInterface.java DictionaryClient.java Makefile table of contents, notes to grader created by you created by you created by you created by you unchanged unchanged alter at your discretion As always, start early and ask plenty of questions. // DictionaryClient.java /1 Client module for testing Dictionary ADT public class DictionaryClient public static void main(String[] args)f String v; Dictionary A new Dictionary(); Ainsert("1","a"); A.insert("2", "b"): A.insert("3", "c"): A.insert("4","d"); A.insert("5", "e"): .insert("6", "f"); A.insert("7", "g"); System.out.println(A); vA.lookup("1"); System.out.println("key-1"vnull?"not found":("value-"+v))); vA.lookup("3"); System.out.println("key-3"(vnull?"not found":("value-"+v))); vA.lookup("7"); System.out.println("key-"(vnull?"not found":("value-"+v))); v A. lookup("8"); System.out.println("key-8"vnull?"not found":("value-"+v))); System.out.println(); // .insert ("2","f"); // causes DuplicateKeyException .delete("1"); A.delete("3"; .delete(.. 7" ) ; System.out.println(A); // .delete("8"); // causes KeyNot FoundException System.out.println(A.isEmpty()); System.out.println(A.size()); A.makeEmpty(); System.out.println(A.isEmpty()); System.out.println (A); // DictionaryInterface.java // interface for the Dictionary ADT public interface DictionaryInterfacet // isEmpty() pre: none // returns true if this Dictionary is empty, false otherwise ublic boolean isEmptyO; // size() pre: none // returns the number of entries in this Dictionary public int size(); // lookup() pre: none // returns value associated key, or null reference if no such key exists public String lookup (String key) // insert() // inserts new (key,value) pair into this Dictionary // pre: lookup (key) null public void insert(String key, String value) throws DuplicateKeyException; // delete() // deletes pair with the given key // pre: lookup (key)!null public void delete(String key) throws KeyNotFoundException; // makeEmpty() pre: none public void makeEmpty() // toString() // returns a String representation of this Dictionary overrides Object's toString) method pre: none public String toString()