No late assignments will be accepted.1 PartBThere is no partA for this homework.1.1 Symbol TableFor this problem, you are going to write a program SymbolTable.java which stores variables (just Strings)and associated values (of a generic type); such a data structure is used in all programming languages duringcompilation (e.g., Java) or interpretation (e.g., Python) to store information associated with variables. TheSymbolTable class will be generic in that it can store any kind of object as values (in the unit test, we willcreate two di erent symbol tables, one holding Integers and one holding Strings). The data structure usedto store the variables and values will be a linked list created from the following Node class:private class Node { // Node class for LLsString variable;Value value;Node next;public Node(String k, Value v, Node p) { // Constructorvariable = k; value = v; next = p;}}Node head = null;This class will be an \inner class&" of the SymbolTable class, that is, a class de ned inside another class,and all the information about the linked list will be private. Here is a template to get you started:SymbolTable.java. The linked list will be kept in ascending lexicographic order, (you will use compareTo(...)to compare the Strings when doing insertion). Note that the ordering used is the same as in a dictionary,and in fact, a symbol table IS a dictionary, where the \meaning&" of a symbol is the value associated witheach variable name.You may NOT use loops to process the linked lists, and hence you will have to write recursive algorithmsfor those methods that require moving down the linked list. The only loops that will occur in your programwill be those that I wrote in the Unit Tests.The interface for the symbol table is as follows (cut and paste into a new interface in your hw8 srcdirectory):/** File: Dictionary.java* Author: Wayne Snyder* Purpose: interface for dictionary in hw08*/package hw8;import java.util.Iterator;1public interface Dictionary {// NOTE: comments precede the method stub they specify//-- You do not need to make any changes to this file/** If the variable var is not in the symbol table, insert a new node containing var and val into* the linked list in ascending order (do NOT sort the list, but insert in order of the variable* field); if var is already in the table, then simply replace the existing value with the new* value val. The type Value is a generic type.*/public void put(String var, Value val);/** Return the value associated with the variable var, or throw the exception* if var is not in the table.*/public Value get(String var) throws KeyNotFoundException ;/** Return true or false, depending on whether var is in the table or not.*/public boolean contains(String var);/** Remove the node containing var from the table; if var is not in the table, do nothing.*/void delete(String var);/** Return the smallest variable in the lexicographic ordering (this will be in the first node in* the list); if the table is empty, throw the exception.*/public String min() throws KeyNotFoundException ;/** Similar to the previous, but return the largest entry, which will be in the last node in the* linked list.*/public String max() throws KeyNotFoundException ;/** If the table is empty or if var is smaller than the smallest entry, throw the exception; if var*is in* the table, return var; otherwise, return the largest variable which is less than var (the entry2* just before where var would be inserted into the table). If var is larger than the maximum key* in the table, return that maximum key. Do NOT insert var into the table if it is not there.* This is comparable to the mathematical function floor(...). [Hint: During the recursion, if* your current key equals var, then return it; else you should &"look ahead&" to see what* the next key is (checking first whether it is null!), and if the next key is larger than var,* or if there is no next key, your current key should be returned.]*/public String floor(String var) throws KeyNotFoundException ;/** If the table is empty or if var is larger than the largest entry, throw the exception; if var* is in the* table, return var; otherwise, return the smallest variable which is larger than var (the entry* just after where var would be inserted in代做Java程序、Java课程设计代写留学生、代写Dictionary编程、Java作业代做留学生to the table). (Do NOT insert var into the table!)* This is comparable to the mathematical function ceiling(...).*/public String ceiling(String var) throws KeyNotFoundException ;/** Return the &"rank&" of var, i.e., the number of entries in the table which are smaller* than var; the rank of variables which are in the table is calculated by counting 0, 1, 2,* starting at the first node (as if it were an array); if var is not in the table, then it is the* rank where var would be if it were inserted (do NOT insert var into the table).*/public int rank(String var);/** Return the variable which is at rank n in the linked list (starting the count at 0 with the* first node, as in an array). If the table is empty, or if n is not the rank of any element, i.e., it is negative or is* equal to or larger than the length of the linked list, throw the exception. You are essentially* just* returning the variable at location n in the list, but starting the count with 0 at the first* node.*/public String select(int n) throws KeyNotFoundException ;/* Remove the smallest (i.e., first) entry in the table; if the table is empty, do nothing. */public void deleteMin();/** Remove the largest (i.e., last) entry in the table; if the table is empty do nothing. Hint: you* can directly use a method from the Notes.....*/public void deleteMax();3/** Return the number of entries in the table (the length of the linked list); you should keep* track of this with a private variable size, which is updated when you remove* or add an entry.*/public int size();/** Return the number of entries in the table whose variables are in the range [lo .. hi], that is,* that are >= lo and ) as before, and third case(== of the rst character) in which you take one step forward in s for and one step down in the tree. Yoursearch ends when you hit null or run out of characters in s before hitting null. If you hit null and at thesame exact step as you run out of characters in s, you have found s in the tree; else, s is not in the tree.Our description above is not enough | see https://en.wikipedia.org/wiki/Ternary_search_treefor a nice example and details of insertion and search.In order for ternary search tree to make sense, we cannot allow insertion of two strings s1 and s2 thatare pre xes of each other; we will simply assume this never happens (one easy way to make sure this neverhappens is to have a special terminating character, such as ’n0’ at the end of every string; but in thishomework we won’t bother | we will simply not have test cases where one inserted strings is a pre x ofanother).Your job is to implement insertion, search, and an alphabetical-order iterator. The les to work with areTernarySearchTree.java, TernaryTreeNode.java, and TernarySearchTreeDriver.java. (Note that wecould make the node an inner class of the tree, like we did in some other examples, but we chose not to forreadability, because you may want to put code in the node class, and it will get hard to see what’s where.)2 Submission Checklist1Similar to your previous assignments, you will create a new package hw8 in Eclipse. Inside this package,all your Java les will reside. You will only submit the package hw8 to us. This package must contain thefollowing les only.SymbolTable.javaTernarySearchTree.javaTernaryTreeNode.javaThe rst line in every Java le must be package hw8;Be sure to do the following:You have read the Java Style. Guide for CS112 (linked on BlackBoard), and followed all guidelinesregarding format, layout, spaces, blank lines, and comments;1If you deviate from these instructions, we will penalize you 30% on the entire assignment. No late work will be accepted.If you are still not familiar with gSubmit, please stop by our o ce hours and we can help you with this.6You have removed or changed all comments inherited from my templates which do not relate to yoursolution;You have veri ed that your program satisfy all the performance tests in the templates.You can con rm that your assignment has been correctly2 submitted by typing this out: gsubmit cs112-lsYou can add as many helper methods (these must all be private), however, YOU CANNOT CHANGETHE METHOD NAMES OR CHANGE THE SIGNATURE OF THE REQUIRED METHODS IN THISASSIGNMENT. THIS WILL BREAK OUR TESTS AND YOU WILL RECEIVE ZERO.2You can read more about the gsubmit command by typing man gsubmit on the linux machines at BU转自：http://ass.3daixie.com/2018052158549078.html