package hashtables;

import base.MapBase;
import base.Node;

/**
 * Basic implementation of a HashTable.
 * Currently supports:
 * 	- setting size of storage initially
 * 	- Putting and Getting of key, value Strings Pairs
 *  - Blocking Resizing of array when load factor reaches cutoff
 * TODO:
 *  - Deal with collisions - currently just overwrites if a key
 *  	hashes to the same slot
 *  - Dynamic resizing to reduce wait time
 * @author sjc
 */
public class CustomHashTable implements MapBase {
    
    Node[] array;
    double cutoffLoadFactor;
    double currentLoadFactor = 0;
    int count = 0;
    
    public CustomHashTable(int initialSize, double lfactor){
        array = new Node[initialSize];
        cutoffLoadFactor = lfactor;
    }
    
    public CustomHashTable(int initialSize){
        array = new Node[initialSize];
        cutoffLoadFactor = 0.75;
    }
    
    public String get(String key){
        int index = hash(key, array.length);
        Node n = array[index];
        return n.value;
    }
    
    public void put(String key, String val){
        if(count/array.length > cutoffLoadFactor) {
            increaseArraySize();
        }
        int index = hash(key, array.length);
        array[index] = new Node(key, val);
        count++;
    }
    
    public Boolean containsKey(String key) {
        // TODO Auto-generated method stub
        return null;
    }
    
    private void increaseArraySize(){
        int curLen = array.length;
        Node[] newElems = new Node[curLen*2];
        rehashElements(array, newElems);
    }
    
    private void rehashElements(Node[] oldElements, Node[] newElements){
        for(int i=0; i<oldElements.length; i++){
            Node oldNode = oldElements[i];
            if(oldNode != null){
                int newIndex = hash(oldNode.key, newElements.length);
                newElements[newIndex] = new Node(oldNode.key, oldNode.value);
            }
        }
        array = newElements;
    }
    
    private int hash(String key, int length) {  
        return (Math.abs(key.hashCode())) % length;  
    }


}

@@ -52,16 +52,41 @@
 se.Node;
+%0Aimport linkedList.LList;
 %0A%0A/**%0A *
@@ -532,20 +532,24 @@
     
-Node%5B%5D array
+LList%5B%5D elements
 ;%0A  
@@ -698,36 +698,37 @@
 r)%7B%0A    
-    array
+%09elements
  = new 
-Node
+LList
 %5Binitial
@@ -838,24 +838,28 @@
     
-array
+elements
  = new 
-Node
+LList
 %5Bini
@@ -970,37 +970,40 @@
 dex = hash(key, 
-array
+elements
 .length);%0A      
@@ -1008,22 +1008,26 @@
     
-Node n = array
+LList n = elements
 %5Bind
@@ -1048,21 +1048,26 @@
 eturn n.
-value
+fetch(key)
 ;%0A    %7D%0A
@@ -1099,18 +1099,16 @@
 String k
-ey
 , String
@@ -1109,18 +1109,16 @@
 String v
-al
 )%7B%0A     
@@ -1127,45 +1127,25 @@
  if(
-count/array.length %3E cutoffLoadFactor
+tooManyElements()
 ) %7B%0A
@@ -1179,32 +1179,141 @@
 ze();%0A        %7D%0A
+        addNewElement(k, v);%0A        count++;%0A    %7D%0A    %0A    private void addNewElement(String k, String v)%7B%0A
         int inde
@@ -1326,17 +1326,18 @@
 sh(k
-ey, array
+, elements
 .len
@@ -1354,58 +1354,169 @@
     
-array%5Bindex%5D = new Node(key
+LList toAdd = elements%5Bindex%5D;%0A        toAdd.insert(k
 , v
-al
 );%0A    
+%7D%0A
     
-count++
+%0A    private Boolean tooManyElements()%7B%0A    %09return count/elements.length %3E cutoffLoadFactor
 ;%0A  
@@ -1703,21 +1703,24 @@
 urLen = 
-array
+elements
 .length;
@@ -1728,20 +1728,21 @@
         
-Node
+LList
 %5B%5D newEl
@@ -1751,20 +1751,21 @@
 s = new 
-Node
+LList
 %5BcurLen*
@@ -1791,21 +1791,24 @@
 lements(
-array
+elements
 , newEle
@@ -1855,20 +1855,21 @@
 lements(
-Node
+LList
 %5B%5D oldEl
@@ -1876,20 +1876,21 @@
 ements, 
-Node
+LList
 %5B%5D newEl
@@ -1906,137 +1906,98 @@
     
-   
- 
+%09
 for(
-int i=0; i%3ColdElements.length; i++)%7B%0A            Node oldNode = oldElements%5Bi%5D;%0A            if(oldNode != null)%7B
+LList oldList : oldElements)%7B%0A    %09%09Node n;%0A    %09%09do%7B%0A    %09%09%09n = oldList.pop();
 %0A    
-    
+%09
     
@@ -2004,20 +2004,17 @@
     int 
-newI
+i
 ndex = h
@@ -2017,23 +2017,17 @@
  = hash(
-oldNode
+n
 .key, ne
@@ -2049,25 +2049,25 @@
 h);%0A    
- 
+%09
         
    newEl
@@ -2058,18 +2058,29 @@
         
-  
+LList toAdd =
  newElem
@@ -2088,49 +2088,50 @@
 nts%5B
-newI
+i
 ndex%5D
- = new Node(oldNode.key, oldNode
+;%0A    %09        toAdd.insert(n.key, n
 .val
@@ -2139,34 +2139,49 @@
 e);%0A    
-  
-      %7D%0A   
+%09%09%7D%0A    %09%09while(n != null);%0A
     
- 
+%09
 %7D%0A      
@@ -2182,21 +2182,24 @@
         
-array
+elements
  = newEl
@@ -2326,12 +2326,10 @@
  %0A    %7D%0A
-%0A%0A
 %7D%0A

Update custom hash table to use LList instead of Nodes. This means that hashtable should now use chaining to deal with conflicts. Untested