/** * HW2 Version 1.0 * * The LinkedListST class maintains an (unordered) symbol
ID: 3750645 • Letter: #
Question
/**
* 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<Key extends Comparable<Key>, Value extends Comparable<Value>> {
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<Key> keys() {
Queue<Key> theKeys = new Queue<Key>();
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<Value, Key> inverse () {
LinkedListST<Value, Key> answer = new LinkedListST<Value,Key>();
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<String, Integer> st = new 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<String,Integer> aList = new LinkedListST<String,Integer>();
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<String,Integer> aList = new LinkedListST<String,Integer>();
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<String,Integer> aList = new LinkedListST<String,Integer>();
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<String,Integer> aList = new LinkedListST<String,Integer>();
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<String,Integer> aList = new LinkedListST<String,Integer>();
for (int i=0; i < keys.length(); i++) {
aList.put(keys.substring(i, i+1),i);
}
// call the inverse function
LinkedListST<Integer, String> actual = aList.inverse();
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(" --------------- ");
}
}
Explanation / Answer
Code:
public class LinkedListST<Key extends Comparable<Key>, Value extends Comparable<Value>> {
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<Key> keys() {
Queue<Key> theKeys = new Queue<Key>();
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() {
int size = 0;
for (Node x = first; x != null; x = x.next) {
size++;
}
return size;
}
/**
* 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() {
if(first == null || first.next == null) {
return null;
}
Key max = null, secondMax = null;
if(first.key.compareTo(first.next.key) > 0) {
max = first.key;
secondMax = first.next.key;
} else {
max = first.next.key;
secondMax = first.key;
}
for (Node x = first.next.next; x != null; x = x.next) {
if(x.key.compareTo(max) > 0) {
secondMax = max;
max = x.key;
}
}
return secondMax;
}
/**
* 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 getRank(first, key, 0);
}
public int getRank(Node first, Key key, int count) {
if(first == null) {
return count;
}
else if(first.key.compareTo(key) <= 0) {
return getRank(first.next, key, count++);
} else {
return getRank(first.next, key, count);
}
}
/**
* 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) {
if(first == null) {
return null;
}
Key max = first.key;
for (Node x = first; x != null; x = x.next) {
if(x.key.compareTo(key) == 0) {
max = x.key;
} else if(x.key.compareTo(key) < 0 && x.key.compareTo(max) > 0) {
max = x.key;
}
}
return max;
}
/**
* 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<Value, Key> inverse() {
LinkedListST<Value, Key> answer = new LinkedListST<Value, Key>();
for(Node x = first; x != null ; x = x.next) {
if(answer.get(x.val) != null) {
answer.put(x.val, x.key);
}
}
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<String, Integer> st = new 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<String, Integer> aList = new LinkedListST<String, Integer>();
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<String, Integer> aList = new LinkedListST<String, Integer>();
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<String, Integer> aList = new LinkedListST<String, Integer>();
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<String, Integer> aList = new LinkedListST<String, Integer>();
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<String, Integer> aList = new LinkedListST<String, Integer>();
for (int i = 0; i < keys.length(); i++) {
aList.put(keys.substring(i, i + 1), i);
}
// call the inverse function
LinkedListST<Integer, String> actual = aList.inverse();
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(" --------------- ");
}
}
I have implemented rank, floor, size, secondLargest, inverse functions.
In case of any doubts, please comment.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.