Question: /** * HW2 Version 1.0 * * The LinkedListST class maintains an (unordered) symbol table of * generic key-value pairs. It supports put, get, and
/**
* HW2 Version 1.0
*
* The LinkedListST class maintains an (unordered) symbol table of
* generic key-value pairs. It supports put, get, and delete methods.
*
* Note you will be implementing methods from the ordered-symbol-table API
* but since the underlying table is not necessarily ordered, your methods
* will likely not be very efficient (and that's fine for this assignment)
*
* You may not add any instance variables to the class.
* You may not change the definition of supplied methods
* You may not use any other Java classes/algorithms without permission
* You may write additional utility/helper instance methods
*
* You are to complete the methods marked toDo
*/
public class LinkedListST
private Node first; // the linked list of key-value pairs
// a helper linked list data type
private class Node {
private Key key;
private Value val;
private Node next;
public Node(Key key, Value val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
/**
* Initializes an empty symbol table.
*/
public LinkedListST() {
first = null;
}
/**
* get
*
* Returns the value associated with the given key in this symbol table.
*/
public Value get(Key key) {
if (key == null) throw new NullPointerException("argument to get() is null");
for (Node x = first; x != null; x = x.next) {
if (key.equals(x.key))
return x.val;
}
return null;
}
/**
* put
*
* Inserts the specified key-value pair into the symbol table, overwriting the old
* value with the new value if the symbol table already contains the specified key.
* Deletes the specified key (and its associated value) from this symbol table
* if the specified value is null.
*/
public void put(Key key, Value val) {
if (key == null) throw new NullPointerException("first argument to put() is null");
if (val == null) {
delete(key);
return;
}
for (Node x = first; x != null; x = x.next) {
if (key.equals(x.key)) {
x.val = val;
return;
}
}
first = new Node(key, val, first);
}
/**
* delete
*
* Removes the specified key and its associated value from this symbol table
* (if the key is in this symbol table).
*/
public void delete(Key key) {
if (key == null) throw new NullPointerException("argument to delete() is null");
first = delete(first, key);
}
/* delete helper function
*
* delete key in linked list beginning at Node x
* warning: function call stack too large if table is large
*
*/
private Node delete(Node x, Key key) {
if (x == null) return null;
if (key.equals(x.key)) {
return x.next;
}
x.next = delete(x.next, key);
return x;
}
public Iterable
Queue
for ( Node temp = first; temp != null; temp=temp.next) {
theKeys.enqueue(temp.key);
}
return theKeys;
}
/* you should not modify anything above this line */
/**
* size
*
* size returns the number of key-value pairs in the symbol table.
* it returns 0 if the symbol table is empty.
*/
public int size () {
return -1; // ToDo 1 fix this
}
/**
* secondLargestKey
*
* secondLargestKey returns the second largest key in the symbol table.
* it returns null if the symbol table is empty or if it has only one key.
* See if you can write it with only one loop
*/
public Key secondLargestKey () {
return null; // TODO 2 fix this
}
/**
* rank
*
* rank returns the number of keys in this symbol table that are less than the given key.
* your implementation should be recursive. You will need to create a helper function
*/
public int rank (Key key) {
return -1; // TODO 3 fix this
}
/**
* floor
*
* floor returns the largest key in the symbol table that is less than or equal to the given key.
* it returns null if there is no such key.
*/
public Key floor (Key key) {
return null; // TODO 4 fix this
}
/**
* inverse
*
* returns the inverse of this symbol table.
* the inverse is a symbol table where the roles of the Keys and Values are switched
* Example:
* Consider the symbol table below, written as a collection of key value pairs
* A, 1
* B, 2
* C, 3
*
* The inverse this would be:
* 1, A
* 2, B
* 3, C
*
* In the original table, keys were Strings, values were Integers
* So in the inverse table, keys would be Integers and values would be Strings
*
* Note that the return type for the function is already correctly specified.
* That is: the invoking instance will be a Symbol table with key type: Key and value type: Value
* the inverse will be a symbol table with key type: Value and value type: Key
*
* Note: if the symbol table contains duplicate values,
* you may use any of the corresponding keys for the inverse
* Example:
* A, 1
* B, 2
* C, 3
* D, 2
*
* 2 will become a Key in the inverse symbol table and its value could be either B or D
*/
public LinkedListST
LinkedListST
return answer; // TODO 5 fix this
}
public static void main(String[] args)
{
// here is the simple testing code from the textbook pg 370
// you may delete/comment this out if you wish
LinkedListST
StdIn.fromFile("data/tinyST.txt");
for (int i = 0; !StdIn.isEmpty(); i++)
{
String key = StdIn.readString();
st.put(key, i);
}
for (String s : st.keys())
StdOut.println(s + " " + st.get(s));
// calls to the testing functions
sizeTest("",0); // test size on an empty ST (symbol table)
sizeTest("abcde",5); // test size on a non-empty ST
StdOut.println();
secondLargestKeyTest("",null);
secondLargestKeyTest("A",null);
secondLargestKeyTest("AB","A");
secondLargestKeyTest("ABC","B");
secondLargestKeyTest("ABABABC","B");
secondLargestKeyTest("ZAYBXC","Y");
StdOut.println();
rankTest("","A",0);
rankTest("A","A",0);
rankTest("ABC","A",0); // A is the smallest key
rankTest("CBA","A",0); // A is the smallest key
rankTest("AYBXC","Y",4); // Y is the largest key
rankTest("AYBXC","X",3); // X is 'in the middle'
// ToDo: 6.1
// replace the println statement below with a new test case here, distinct from the above
// include a comment describing what you are testing for.
StdOut.println(" MY TEST CASE GOES HERE");
StdOut.println();
floorTest("","A",null);
floorTest("A","A","A");
floorTest("ABCDE","A","A"); // A is the smallest key
floorTest("POTSDAM","P","P"); // P is in the middle
floorTest("POTSDAM","T","T"); // T is the largest
// ToDo: 6.2
// replace the println statement below with a new test case here, distinct from the above
// include a comment describing what you are testing for.
StdOut.println(" MY TEST CASE GOES HERE");
StdOut.println();
StdOut.format(" Manually inspect the following output for correctness ");
inverseTest("CAB");
}
/* the testing functions
*
* You are encouraged to look these over, but you should not modify any of this code
*
*/
/* sizeTest
*
* testing function.
* param keys: all substrings of keys of length 1 are added to a ST
* param expected: the correct value of the ST for the input:keys
*
*/
public static void sizeTest( String keys, int expected ) {
// create and populate the table from the input string vals
LinkedListST
for (int i=0; i < keys.length(); i++) {
aList.put(keys.substring(i, i+1),i);
}
// call the size function
int actual = aList.size();
//report result
if ( actual == expected) // test passes
StdOut.format("sizeTest: Correct String %s Actual: %d ", keys,actual);
else
StdOut.format("sizeTest: *Error* String %s Expected %d Actual: %d ", keys,expected,actual);
}
/* secondLargestKeyTest
*
* testing function.
* param keys: all substrings of keys of length 1 are added to a ST
* param expected: the correct value of the ST for the input:keys
*
*/
public static void secondLargestKeyTest( String keys, String expected ) {
// create and populate the table from the input string keys
LinkedListST
for (int i=0; i < keys.length(); i++) {
aList.put(keys.substring(i, i+1),i);
}
// call the secondLargestKey function
String actual = aList.secondLargestKey();
//report result
if ( expected == null) {
if (actual == null)
StdOut.format("secondLargestKeyTest: Correct String %s Answer: null ", keys,actual);
else
StdOut.format("secondLargestKeyTest: *Error* String %s Expected: null Actual: %s ", keys,actual);
return;
}
if (actual == null && expected != null ) { // error
StdOut.format("secondLargestKeyTest: *Error* String %s Expected: %s Actual: null ", keys,expected);
return;
}
if ( actual.equals(expected)) // test passes
StdOut.format("secondLargestKeyTest: Correct String %s Actual: %s ", keys,actual);
else
StdOut.format("secondLargestKeyTest: *Error* String %s Expected %s Actual: %s ", keys,expected,actual);
}
/* rankTest
*
* testing function.
* param keys: all substrings of keys of length 1 are added to a ST
* param key: key to compare against
* param expected: the correct value for the input params
*
*/
public static void rankTest( String keys, String key, int expected ) {
// create and populate the table from the input string keys
LinkedListST
for (int i=0; i < keys.length(); i++) {
aList.put(keys.substring(i, i+1),i);
}
// call the rank function
int actual = aList.rank(key);
//report result
if ( actual == expected) // test passes
StdOut.format("rankTest: Correct String %s Actual: %d ", keys,actual);
else
StdOut.format("rankTest: *Error* String %s Expected %d Actual: %d ", keys,expected,actual);
}
/* floorTest
*
* testing function.
* param keys: all substrings of keys of length 1 are added to a ST
* param key: key to compare against
* param expected: the correct value for the input params
*
*/
public static void floorTest( String keys, String key, String expected ) {
// create and populate the table from the input string keys
LinkedListST
for (int i=0; i < keys.length(); i++) {
aList.put(keys.substring(i, i+1),i);
}
// call the floor function
String actual = aList.floor(key);
//report result
if ( expected == null) {
if (actual == null)
StdOut.format("floorTest: Correct String %s Answer: null ", keys,actual);
else
StdOut.format("floorTest: *Error* String %s Expected: null Actual: %s ", keys,actual);
return;
}
if (actual == null && expected != null ) { // error
StdOut.format("floorTest: *Error* String %s Expected: %s Actual: null ", keys,expected);
return;
}
if ( actual.equals(expected)) // test passes
StdOut.format("floorTest: Correct String %s Actual: %s ", keys,actual);
else
StdOut.format("floorTest: *Error* String %s Expected %s Actual: %s ", keys,expected,actual);
}
/* inverseTest
*
* testing function.
* param keys: all substrings of keys of length 1 are added to a ST
*
* create a symbol table from keys.
* generate it's inverse and then print them both out
*/
public static void inverseTest( String keys ) {
// create and populate the table from the input string vals
LinkedListST
for (int i=0; i < keys.length(); i++) {
aList.put(keys.substring(i, i+1),i);
}
// call the inverse function
LinkedListST
if ( actual == null) {
StdOut.format(" inverseTest *Error* null value returned ");
return;
}
StdOut.format(" Original Symbol Table ");
for ( String s : aList.keys())
StdOut.format(" %s , %d ", s, aList.get(s));
StdOut.format(" --------------- ");
StdOut.format(" Inverse Symbol Table ");
for ( Integer i : actual.keys())
StdOut.format(" %d , %s ", i, actual.get(i));
StdOut.format(" --------------- ");
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help