Homework 5 CS 340

SymbolTable.java

import java.util.*;
public class SymbolTable <T>{

    private int primeIndex, tableSize, numItems;
    private static final double LOAD_FACTOR = .75; // Added const to change as needed.
    private Node<T>[] table;
    private final int[] primes = {7, 23, 59, 131, 271, 563, 1171, 2083, 4441, 8839, 16319, 32467, 65701, 131413};

    public SymbolTable(int s){
        primeIndex = 0;
        tableSize = nextPrime(s);
        table = new Node[tableSize];
        numItems = 0;
    }

    private static class Node<T>{
        private final String key;
        private final T data;
        private Node<T> next;

        private Node(String key, T data, Node<T> next){
            this.key = key;
            this.data = data;
            this.next = next;
        }
    }

    private int nextPrime(int p){
        while(primes[primeIndex] <= p) primeIndex++;
        return primes[primeIndex];
    }

    private int hash(String k){
        // return the hash function value for k
        return Math.abs(k.hashCode()) % tableSize;
    }

    private void resize(){
        tableSize = nextPrime(tableSize*2);
        var oldTable = table;
        table = new Node[tableSize];
        for (Node<T> tNode : oldTable) {
            var node = tNode;
            if (node != null) {
                insert(node.key, node.data);
                while (node.next != null) {
                    node = node.next;
                    insert(node.key, node.data);
                }
            }
        }
    }

    public boolean insert(String k, T d){
        Node<T> node = table[hash(k)]; // Look at the linked list in the loc the key hashes to.

        if(node == null){
            table[hash(k)] = new Node<>(k, d, null);
            return true;
        }

        if(node.key.equals(k)) return false; // If the key is already in there skip it

        while(node.next != null){ // While there is more to look at.
            node = node.next; // Look at the next node.
            if(node.key.equals(k)) return false; // Check to see if it is equivalent.
        }

        node.next = new Node<T>(k, d, null); // Insert the new unique node at the end of the list.
        numItems ++; // Increment the counter.

        if(numItems/(double)tableSize > LOAD_FACTOR) resize(); // If there are too many entries we need to resize.

        return true;
    }

    public T find(String k){
        Node<T> node = table[hash(k)]; // Look at the linked list in the loc the key hashes to.

        if(node == null) return null;
        if(node.key.equals(k)) return node.data; // If the key matches return the node.data

        while(node.next != null){ // While there is more to look at.
            node = node.next; // Look at the next node.
            if(node.key.equals(k)) return node.data; // Check to see if it is equivalent.
        }

        return null;
    }

    public boolean remove(String k){
        int loc = hash(k);
        Node<T> prev, node = table[loc]; // Look at the linked list in the loc the key hashes to.

        if(node.key.equals(k)){
            // If the key matches, remove it and then return true.
            table[loc] = node.next;
            numItems--;
            return true;
        }

        while(node.next != null){ // While there is more to look at.
            prev = node;
            node = node.next; // Look at the next node.
            if(node.key.equals(k)) {
                // If the key matches, remove it and then return true.
                prev.next = node.next;
                numItems--;
                return true;
            }
        }

        return false;
    }

    public class STIterator implements Iterator<String>{
        private int tableIndex = 0;
        private Node<T> node = table[tableIndex];

        @Override
        public boolean hasNext() {
            // Iterate to the next non null node in the array.
            while(node == null && tableIndex < tableSize-1) {
                tableIndex++;
                node = table[tableIndex];
            }
            return node != null;
        }

        @Override
        public String next() {
            // Iterate to the next non null node in the array.
            while(node == null && tableIndex < tableSize) {
                tableIndex++;
                node = table[tableIndex];
            }
            // If the node isn't null set it to the next node in the list and return its key.
            if(node != null){
                var out = node.key;
                node = node.next;
                return out;
            }

            return null;
        }
    }

    public Iterator<String> iterator(){
        return new STIterator();
    }
}