Fill This Form To Receive Instant Help

Help in Homework
trustpilot ratings
google ratings


Homework answers / question archive / Can someone help me how to complete this code? I'm really stuck on this code

Can someone help me how to complete this code? I'm really stuck on this code

Computer Science

Can someone help me how to complete this code? I'm really stuck on this code. I'm not exactly sure how to complete this code. Can someone explain it to me? What exactly I need to do?

Part 1: HashTable Class (48 pts + 7 pts for HashTableTest.java)

  • Your job for this lab is to write a Hash Table class given the starter code provided below.

Adding Values to the Hash Table

  • One of the first operations to write for any class is insertion.
  • Since we are using separate chaining for collision resolution, our table consists of an ArrayList where each index stores a List
  • Each time we push (insert) a new Object into the table, we need to complete these steps:
  • Call the hash method to determine at which index or bucket to place the Object inside the table
  • Insert the Object at the correct position in the chain at the appropriate index in the ArrayList
  • Note that you need to call the correct method from the List class to insert this Object onto the end of the chain at that bucket.
  • Each time you insert a new Object, it should be added to the end of the chain. There is no additional sorting required (or needed).

Printing Using printBucket:

  • To verify your Hash Table methods are working properly, you need to be able to print the values contained in the Table.
  • Therefore, your next step - after writing put - should be to write a print method.
  • There are two "print" methods you need to write for this lab - printBucket and toString
  • printBucket is used to display all of the values stored in a single bucket (a "row" in the table).
  • The printBucket method will allow us to dig more deeply into what is contained at a particular bucket.

 

Writing toString:

  • The toString method gathers all elements in the table separated by a blank line.
  • Note that you may make some minor adjustments to your List toString() if needed to get the correct outcome for this method.
  • You can think of toString as providing a vertical cross section of values in the Table (whereas printBucket gives a horizontal cross section.)

Counting items at a bucket using the countBucket method

  • For this method, you will need to count the number of Object at a specific index or bucket.

Searching the Table

  • There are two search methods, which behave similarly. 
  • get will return the desired element from the Table, whereas contains will return a boolean value specifying whether the desired Object is contained in the Table.
  • The first step will be to call the hash method to determine which bucket the Object may be located
  • Next, you will need to search through the values at this bucket to determine if the Object is stored at that bucket - hint: call the appropriate List search method
  • If you find the Object, return it or true (depending on the method).
  • If the Object is not in the table, return null or false (depending on the method).

Clearing the Table

  • To clear the Table, you will need to reset it to an empty state, like right after the constructor is called.
  • Each bucket should contain an empty list and the numElements should be 0.

 

Removing an Object from the Table

  • To remove an Object, you will need to complete these steps:
  • Pass the Object to the hash method to determine at which index this Object is located (if in the table).
  • Search for the Object in the chain at that bucket
  • Once you have located it, call the appropriate List removal method to remove the Object from that bucket .
/**
 * HashTable.java
 * @author 
 * @author
 * CIS 22C, Lab 6
 */
import java.util.ArrayList;

public class HashTable<T> {
    
    private int numElements;
    private ArrayList<List<T> > Table;

    /**
     * Constructor for the Hash.java
     * class. Initializes the Table to
     * be sized according to value passed
     * in as a parameter
     * Inserts size empty Lists into the
     * table. Sets numElements to 0
     * @param size the table size
     */
    public HashTable(int size) {
        
    }
       
    /**Accessors*/
    
    /**
     * returns the hash value in the Table
     * for a given Object 
     * @param t the Object
     * @return the index in the Table
     */
    private int hash(T t) {
        int code = t.hashCode();
        return code % Table.size();
    }
    
    /**
     * counts the number of keys at this index
     * @param index the index in the Table
     * @precondition 0 <=  index < Table.length
     * @return the count of keys at this index
     * @throws IndexOutOfBoundsException
     */
    public int countBucket(int index) throws IndexOutOfBoundsException{
        return -1;
    }
    
    /**
     * returns total number of keys in the Table
     * @return total number of keys
     */
    public int getNumElements() {
        return -1;
    }
    
    /**
     * Accesses a specified key in the Table
     * @param t the key to search for
     * @return  the value to which the specified key is mapped, 
     * or null if this table contains no mapping for the key. 
     * @precondition t != null
     * @throws NullPointerException if the specified key is null
     */
    public T get(T t) throws NullPointerException{
        return null;
    }
    
    /**
     * Determines whether a specified key is in 
     * the Table
     * @param t the key to search for
     * @return  whether the key is in the Table 
     * @precondition t != null
     * @throws NullPointerException if the specified key is null
     */
    public boolean contains(T t) throws NullPointerException{
        return false;
    }
    
     
    /**Mutators*/
    
    /**
     * Inserts a new element in the Table
     * at the end of the chain in the bucket
     * to which the key is mapped
     * @param t the key to insert
     * @precondition t != null
     * @throws NullPointerException for a null key
     */
    public void put(T t) throws NullPointerException{  
        
    }  
     
     
    /**
     * removes the key t from the Table
     * calls the hash method on the key to
     * determine correct placement
     * has no effect if t is not in
     * the Table or for a null argument          
     * @param t the key to remove
     * @throws NullPointerException if the key is null
     */
    public void remove(T t) throws NullPointerException {
        
    }
    
    /**
     * Clears this hash table so that it contains no keys.
     */
    public void clear() {
        
    }

    /**Additional Methods*/

    /**
     * Prints all the keys at a specified
     * bucket in the Table. Tach key displayed
     * on its own line, with a blank line 
     * separating each key
     * Above the keys, prints the message
     * "Printing bucket #<bucket>:"
     * Note that there is no <> in the output
     * @param bucket the index in the Table
     */
    public void printBucket(int bucket) {
        
    }
        
    /**
     * Prints the first key at each bucket
     * along with a count of the total keys
     * with the message "+ <count> -1 more 
     * at this bucket." Each bucket separated
     * with two blank lines. When the bucket is 
     * empty, prints the message "This bucket
     * is empty." followed by two blank lines
     */
    public void printTable(){
         
     }
    
    /**
     * Starting at the first bucket, and continuing
     * in order until the last bucket, concatenates
     * all elements at all buckets into one String
     */
    @Override public String toString() {
        
    }
    
}

This is my List Code:

import java.util.NoSuchElementException;

public class List<T> {

 

private class Node {

private T data;

private Node next;

private Node prev;

 

public Node(T data) {

this.data = data;

this.next = null;

this.prev = null;

}

}

 

private int length;

private Node first;

private Node last;

private Node iterator;

 

/**** CONSTRUCTOR ****/

 

/**

* Instantiates a new List with default values

* @postcondition Constructor is initialized with default values

*/

public List() {

this.first = null;

this.last = null;

this.iterator = null;

this.length = 0;

}

 

/**

* Copy constructor for the List class

* @param original the List to copy

* @postcondition a new List object which is an identical, but distinct, copy of

*        original

*/

public List(List<T> original) {

this.first = original.first;

this.last = original.last;

this.iterator = original.iterator;

this.length = original.length;

 

}

 

/**** ACCESSORS ****/

 

/**

* Returns the value stored in the first node

* @precondition the List is not empty / length != 0

* @return the value stored at node first

* @throws NoSuchElementException when precondition is violated

*/

public T getFirst() throws NoSuchElementException {

if (isEmpty()) {

throw new NoSuchElementException("getFirst(): " + "List is empty.");

}

return first.data;

}

 

/**

* Returns the value stored in the last node

* @precondition the List is not empty / length != 0

* @return the value stored in the node last

* @throws NoSuchElementException when precondition is violated

*/

public T getLast() throws NoSuchElementException {

if (isEmpty()) {

throw new NoSuchElementException("getLast(): " + "List is Empty.");

}

return last.data;

}

 

/**

* Returns the current length of the list

* @return the length of the list from 0 to n

*/

public int getLength() {

return length;

}

 

/**

* Returns whether the list is currently empty

* @return whether the list is empty

*/

public boolean isEmpty() {

if (length == 0) {

return true;

} else

return false;

}

 

/**

* Returns the element current pointed at by the iterator

* @precondition iterator must not be null / !offEnd()

* @return element pointed at by iterator

* @throws NoSuchElementException when precondition is violated

*/

public T getIterator() throws NoSuchElementException {

if (offEnd()) {

throw new NoSuchElementException("getIterator(): " + "Iterator is not pointing to anything.");

}

return iterator.data;

}

 

/**

* returns whether the iterator is off the end of the list, i.e. is NULL

* @returns whether iterator is off the end of the list

*/

public boolean offEnd() {

if (iterator == null) {

return true;

}

return false;

}

 

/**

* overrides the equals method for object to compares this list to another list

* to see if they contain the same data in the same order.

* @param L the List to compare to this List

* @return whether the two Lists are equal

*/

@SuppressWarnings("unchecked")

@Override

public boolean equals(Object o) {

if (o == this) {

return true;

} else if (!(o instanceof List)) {

return false;

} else {

List<T> L = (List<T>) o;

if (this.length != L.length) {

return false;

} else {

Node temp1 = this.first;

Node temp2 = L.first;

 

while (temp1 != null) {

if (!(temp1.data.equals(temp2.data))) {

return false;

}

temp1 = temp1.next;

temp2 = temp2.next;

}

}

return true;

}

}

 

/**** MUTATORS ****/

 

/**

* Creates a new first element

* @param data the data to insert at the front of the list

* @postcondition node is added to beginning of the list

*/

public void addFirst(T data) {

 

Node N = new Node(data);

 

if (isEmpty()) {

first = last = N;

} else {

N.next = first;

first.prev = N;

first = N;

}

length++;

}

 

/**

* Creates a new last element

* @param data the data to insert at the end of the list

* @postcondition node is added end of the list

*/

public void addLast(T data) {

Node N = new Node(data);

 

if (isEmpty()) {

first = last = N;

 

} else {

last.next = N;

N.prev = last;

last = N;

}

length++;

}

 

/**

* removes the element at the front of the list

* @precondition the list must not be empty / length != 0

* @postcondition first element is removed from the list

* @throws NoSuchElementException when precondition is violated

*/

public void removeFirst() throws NoSuchElementException {

if (isEmpty()) { // precondition

throw new NoSuchElementException("removeFirst(): " + "List is empty.");

} else if (length == 1) { // edge case

first = last = null;

} else { // general case

first = first.next;

}

length--;

}

 

/**

* removes the element at the end of the list

* @precondition list is not empty

* @postcondition removes last node

* @throws NoSuchElementException when precondition is violated

*/

public void removeLast() throws NoSuchElementException {

if (length == 0) {

throw new NoSuchElementException("removeLast(): list is empty. Nothing to remove");

} else if (length == 1) { // edge case

first = last = null;

} else { // general case

last = last.prev;

}

length--;

}

 

/**

* moves the iterator the start of the list

* @postcondition moves the iterator to the start of the list

*/

public void placeIterator() {

iterator = first;

}

 

/**

* removes the element current pointed to by the iterator

* @precondition iterator must be on the list / !offEnd()

* @postcondition iterator then points to null

* @throws NoSuchElementException when precondition is violated

*/

public void removeIterator() {

if (offEnd()) {

throw new NoSuchElementException("removeIterator(): " + "Iterator is not on list");

} else if (iterator == first) { // edge case

removeFirst();

} else if (iterator == last) { // edge case

removeLast();

} else { // general case

iterator.prev.next = iterator.next;

iterator = null;

}

length--;

}

 

/**

* inserts an element after the node currently pointed to by the iterator

* @precondition iterator must be on the list / !offEnd()

* @throws NoSuchElementException when precondition is violated

*/

public void addIterator(T data) {

if (offEnd()) {

throw new NoSuchElementException("addIterator(): " + "Iterator is not on list");

}else if (iterator == last) { // edge case

addLast(data);

} else {           // general case

 

Node N = new Node(data);

N.next = iterator.next;

N.prev = iterator;

iterator.next.prev = N;

iterator.next = N;

}

length++;

}

 

/**

* moves the iterator up by one node

* @precondition iterator must be on the list / offEnd()

* @throws NoSuchElementException when precondition is violated

*/

public void advanceIterator() {

if(offEnd()) {

throw new NoSuchElementException("advanceIterator():" + "Iterator is null and cannot advance");

}

iterator = iterator.next;

}

 

/**

* moves the iterator down by one node

* @precondition iterator must be on the list / offEnd()

* @throws NoSuchElementException when precondition is violated

*/

public void reverseIterator() {

if(offEnd()) {

throw new NoSuchElementException("advanceIterator():" + "Iterator is null and cannot reverse");

}

iterator = iterator.prev;

}

 

/**** ADDITIONAL OPERATIONS ****/

 

/**

* prints the contents of the linked list to the screen in the format #: <element> followed by a newline

* @return the List as a String formatted with index and new lines i.e. 1: <element> n2: <element>

*/

public String printNumberedList() {

String result = "";

Node temp = first;

 

for(int i = 0;i < length;i++) {

result += (i+1) + ": " + temp.data + "n";

temp = temp.next;

}

return result + "n";

}

 

/**

* List with each value on its own line At the end of the List a new line

* @return the List as a String for display

*/

@Override

public String toString() {

String result = "";

Node temp = first;

while (temp != null) {

result += temp.data + " ";

temp = temp.next;

}

return result;

}

}

 

Ask a new question

Purchase A New Answer

Custom new solution created by our subject matter experts

GET A QUOTE