No late assignments will be accepted.
1 PartB
There is no partA for this homework.
1.1 Symbol Table
For 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 during
compilation (e.g., Java) or interpretation (e.g., Python) to store information associated with variables. The
SymbolTable class will be generic in that it can store any kind of object as values (in the unit test, we will
create two di erent symbol tables, one holding Integers and one holding Strings). The data structure used
to store the variables and values will be a linked list created from the following Node class:
private class Node { // Node class for LLs
String variable;
Value value;
Node next;
public Node(String k, Value v, Node p) { // Constructor
variable = 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 with
each variable name.
You may NOT use loops to process the linked lists, and hence you will have to write recursive algorithms
for those methods that require moving down the linked list. The only loops that will occur in your program
will 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 src
directory):
/*
* File: Dictionary.java
* Author: Wayne Snyder
* Purpose: interface for dictionary in hw08
*/
package hw8;
import java.util.Iterator;
1
public 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 entry
2
* 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 into 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. Your
search ends when you hit null or run out of characters in s before hitting null. If you hit null and at the
same 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_tree
for 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 that
are pre xes of each other; we will simply assume this never happens (one easy way to make sure this never
happens is to have a special terminating character, such as ’n0’ at the end of every string; but in this
homework we won’t bother | we will simply not have test cases where one inserted strings is a pre x of
another).
Your job is to implement insertion, search, and an alphabetical-order iterator. The les to work with are
TernarySearchTree.java, TernaryTreeNode.java, and TernarySearchTreeDriver.java. (Note that we
could make the node an inner class of the tree, like we did in some other examples, but we chose not to for
readability, because you may want to put code in the node class, and it will get hard to see what’s where.)
2 Submission Checklist1
Similar 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 the
following les only.
SymbolTable.java
TernarySearchTree.java
TernaryTreeNode.java
The 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 guidelines
regarding 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.
6
You have removed or changed all comments inherited from my templates which do not relate to your
solution;
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
-ls
You can add as many helper methods (these must all be private), however, YOU CANNOT CHANGE
THE METHOD NAMES OR CHANGE THE SIGNATURE OF THE REQUIRED METHODS IN THIS
ASSIGNMENT. 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