Please Help complete the TODO's CompletedTwoProbeChainHT.java the other codes are completed

Main.java

public class Main { /** * entry point for testing * * @param args the command line arguments */ public static void main(String[] args) { System.out.println("TwoProbeChainHT: "); //Uncomment as needed. //testIntegers(new CompletedTwoProbeChainHT()); //testStrings(new CompletedTwoProbeChainHT()); System.out.println("GeneralProbingHT: "); //testIntegers(new CompletedLinearProbingHT()); //testStrings(new CompletedLinearProbingHT()); System.out.println("QuadProbingHT: "); //testIntegers(new CompletedQuadProbingHT()); //testStrings(new CompletedQuadProbingHT()); } /** * Test integer operations on symbol table implementation. No JUnit; ugly. * * @param st An object implementing a symbol table. */ public static void testIntegers(SymbolTable st) { System.out.println("*INTEGER TESTING*"); System.out.println(" Testing creation and basic methods... "); //populate initial symbol table. Set keys = new HashSet(Arrays.asList(-42341145, -72, -91, -45, - 43, 0, 34, 2, 71, 48, 38334343)); st.put(-42341145, 58); st.put(-72, 2); st.put(-91, 36); st.put(-45, 90); st.put(-43, 51); st.put(0, 4); st.put(34, 3); st.put(2, 96); st.put(71, 19); st.put(48, 42);

st.put(38334343, 92); assert(!st.isEmpty()) : "symbol table is empty after inserting elemetns"; assert(st.size() == 11) : "does not contain correct number of elements"; assert(st.contains(-42341145)) : "added key -42341145 does not exist"; assert(st.contains(0)) : "added key 0 does not exist" ; assert(st.contains(38334343)) : "added key 38334343 does not exist"; assert(!st.contains(-62341145)) : "contains unknown key -62341145"; assert(!st.contains(-1)) : "contains unknown key -1"; assert(!st.contains(58334343)) : "contains unknown key -58334343"; Set stKeys = new HashSet(); for(Integer i : st.keys()) stKeys.add(i); assert(stKeys.equals(keys)) : "keys do not match expected"; /ote: the following code does not check if keys is maintained properly - it should. System.out.println(" Testing put()... "); //add new key int size = st.size(); st.put(99, 42); assert(st.size() == size + 1) : "size did not update."; assert(st.contains(99)) : "does not contain new key"; assert(st.get(99) == 42) : "does not return correct value"; //update existing key size = st.size(); st.put(-72, 2); assert(st.size() == size) : "size changed"; assert(st.contains(-72)) : "does not contain updated key"; assert(st.get(-72) == 2) : "does not return updated value"; System.out.println(" Testing get... "); //get key not there size = st.size(); Integer ret = st.get(10); assert(ret == null) : "returned non-null for key that doesn't exist"; assert(st.size() == size) : "size changed"; assert(!st.contains(10)) : "a key that doesn't exist appeared after get'ing it"; //get key there (2, 96) size = st.size(); ret = st.get(2); assert(ret == 96) : "returned incorrect value for key"; assert(st.size() == size) : "size changed"; assert(st.contains(2)) : "key vanished after get'ing it"; System.out.println(" Testing delete... ");

//delete key not there size = st.size(); st.delete(49); assert(st.get(49) == null) : "returned non-null for key that was deleted"; assert(st.size() == size) : "size changed"; assert(!st.contains(49)) : "a missing key is contained after it was deleted"; //delete key there (48, 42) size = st.size(); st.delete(48); assert(st.get(48) == null) : "returned non-null for key that was deleted"; assert(st.size() == size - 1) : "size did not update"; assert(!st.contains(48)) : "a deleted key is still contained"; System.out.println(" DONE "); } /** * Test string operations on symbol table implementation. No JUnit; ugly. * * @param st An object implementing a symbol table. */ public static void testStrings(SymbolTable st) { System.out.println("*STRING TESTING*"); System.out.println(" Testing creation and basic methods... "); //populate initial symbol table. Set keys = new HashSet(Arrays.asList("DFKDJSFS", "DAFDW", "XZC", "adsfas", "a", "B", "112323", "

/ote: the following code does not check if keys is maintained properl- it should. System.out.println(" Testing put()... "); //add new key int size = st.size(); st.put("TEST", 42); assert(st.size() == size + 1) : "size did not update."; assert(st.contains("TEST")) : "does not contain new key"; assert(st.get("TEST") == 42) : "does not return correct value"; //update existing key size = st.size(); st.put("AAAA", 2); assert(st.size() == size) : "size changed"; assert(st.contains("AAAA")) : "does not contain updated key"; assert(st.get("AAAA") == 2) : "does not return updated value"; System.out.println(" Testing get... "); //get key not there size = st.size(); Integer ret = st.get("TEST2"); assert(ret == null) : "returned non-null for key that doesn't exist"; assert(st.size() == size) : "size changed"; assert(!st.contains("TEST2")) : "a key that doesn't exist appeared after get'ing it"; //get key there ("DAFDW", 52) size = st.size(); ret = st.get("DAFDW"); assert(ret == 52) : "returned incorrect value for key"; assert(st.size() == size) : "size changed"; assert(st.contains("DAFDW")) : "key vanished after get'ing it"; System.out.println(" Testing delete... "); //delete key not there size = st.size(); st.delete("

System.out.println(" DONE "); } }

ProbingHT.java

public interface ProbingHT extends SymbolTable { /** * Returns the length of the internal array. * * @return The length of the internal array. */ public int getM(); /** * Returns the object being stored at an index in the internal array. If index is not used, it * must return null. * * @param i Array index. * @return Number of entries saved in list at index. */ public Object getTableEntry(int i); /** * Computes the hash (will be used as an index) for a key. * * @param key Object to hash. * @return Hash value. */ public int hash(Key key, int i); }

SymbolTable.java

public interface SymbolTable { // put key-value pair into the table void put(Key key, Value val); //get value paired with key. returns null if key does not exist. Value get(Key key); //remove key (and its value) from table void delete(Key key); //is there a value paired with key? boolean contains(Key key); //is the table empty? boolean isEmpty(); /umber of key-value pairs int size(); //all keys in the table. if st is empty, returns an empty iterable object (not a null). Iterable keys(); }

CompletedLinearProbingHT.java

import java.util.LinkedList; import java.util.Queue;

public class CompletedLinearProbingHT implements ProbingHT {

private static final int DEFAULT_CAPACITY = 997; private int size; private int capacity; private Key[] keys; private Value[] values;

public CompletedLinearProbingHT() { this(DEFAULT_CAPACITY); }

public CompletedLinearProbingHT(int capacity) { this.capacity = capacity; keys = (Key[]) new Object[capacity]; values = (Value[]) new Object[capacity]; }

@Override public int hash(Key key, int i) { // Basic hash function from the slides: hash(k, i) = ((k * hashCode() & 0x7fffffff) + i) % M return (key.hashCode() & 0x7fffffff) % capacity + i; }

@Override public void put(Key key, Value val) { if (key == null) { return; }

int i; for (i = hash(key, 0); keys[i] != null; i = hash(key, ++i)) { if (keys[i].equals(key)) { values[i] = val; return; } }

keys[i] = key; values[i] = val; size++; }

@Override public Value get(Key key) { if (key == null) { return null; }

for (int i = hash(key, 0); keys[i] != null; i = hash(key, ++i)) { if (keys[i].equals(key)) { return values[i]; } }

return null; }

@Override public void delete(Key key) { if (key == null) { return; }

int i = hash(key, 0); while (keys[i] != null) { if (keys[i].equals(key)) { // Shift all keys and values after the deleted element to the left by 1 for (int j = i; j

// Set the last element to null keys[size - 1] = null; values[size - 1] = null; size--; return; } i = hash(key, ++i); } }

@Override public boolean contains(Key key) { return get(key) != null; }

@Override public boolean isEmpty() { return size == 0; }

@Override public int size() { return size; }

@Override public Iterable keys() { Queue queue = new LinkedList(); for (int i = 0; i

@Override public int getM() { return capacity; }

@Override public Object getTableEntry(int i) { return keys[i] + " : " + values[i]; } } CompletedQuadProbingHT.java

public class CompletedQuadProbingHT extends CompletedLinearProbingHT {

public CompletedQuadProbingHT() { super(); }

@Override public int hash(Key key, int i) { return (key.hashCode()); } }

CompletedTwoProbeChainHT.java

import java.util.LinkedList; import java.util.Queue;

public class CompletedTwoProbeChainHT implements TwoProbeChainHT {

//any constructors must be made public

@Override public int hash(Key key) { //TODO return 0; }

@Override public int hash2(Key key) { //TODO return 0; }

@Override public void put(Key key, Value val) { //TODO }

@Override public Value get(Key key) { //TODO return null; }

@Override public void delete(Key key) { //TODO }

@Override public boolean contains(Key key) { //TODO return false; }

@Override public boolean isEmpty() { //TODO return false; }

@Override public int size() { //TODO return 0; }

@Override public Iterable keys() { //TODO return null; }

//////////////////////////////////////////////////////////////////////////////////////////////// // THESE METHODS ARE ONLY FOR GRADING AND COME FROM THE TWOPROBECHAINHT INTERFACE.

@Override public int getM() { //TODO. We suggest something like: //return M;

return 0; }

@Override public int getChainSize(int i) { //TODO. We suggest something like: //return entries[i].size();

return 0; } }

CODE OUTPUT

Debupper Console SER272_HWY (um] INTEGER TESTING- Testing creation and basic methods... Dancing puc () - -- Testing 7:t. . . Togoing delete... DONE *STRING TESTING- Tooking creation and basile methods... Testing put () .. Testing dolots. DONE GeneralProbingHT: INTEGER TESTING- Dancing creation and basic methods... Testing put () . . . Testing get... Tanking doloca... DONE "STRING TESTING Testing creation and basic methods... Tasting put () ... Touting got... Testing delete... DONE OundProbingHI: "INTEGER TESTING* Touting creation and basic methods... Testing put () ... Toncing got... Touting dolots... DONE -STRING TESTING- Testing creation and basic methods... Toncing puc () ... Testing jet. Tooting delete... DONE