public class HashTableResizing {
   
   private static double resizeLimit = 2.0;        // when load factor is greater, resize
   private static int mult = 3;
   private static int M = 5;
   private static int MNew = 0; 
   private static int N = 0;          // number of keys in the tables
   
   private static int[] primes = {11, 13, 17, 19, 23, 29 
      , 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 
      , 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 
      , 127, 131, 137, 139, 149, 151, 157, 163, 167, 173 
      , 179, 181, 191, 193, 197, 199, 211, 223, 227, 229 
      , 233, 239, 241, 251, 257, 263, 269, 271, 277, 281 
      , 283, 293, 307, 311, 313, 317, 331, 337, 347, 349 
      , 353, 359, 367, 373, 379, 383, 389, 397, 401, 409 
      , 419, 421, 431, 433, 439, 443, 449, 457, 461, 463 
      , 467, 479, 487, 491, 499, 503, 509, 521, 523, 541 
      , 547, 557, 563, 569, 571, 577, 587, 593, 599, 601 
      , 607, 613, 617, 619, 631, 641, 643, 647, 653, 659 
      , 661, 673, 677, 683, 691, 701, 709, 719, 727, 733 
      , 739, 743, 751, 757, 761, 769, 773, 787, 797, 809 
      , 811, 821, 823, 827, 829, 839, 853, 857, 859, 863 
      , 877, 881, 883, 887, 907, 911, 919, 929, 937, 941 
      , 947, 953, 967, 971, 977, 983, 991, 997,1009,1013 
      ,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069 
      ,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151 
      ,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223 
      ,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291 
      ,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373 
      ,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451 
      ,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511 
      ,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583 
      ,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657 
      ,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733 
      ,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811 
      ,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889 
      ,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987 
      ,  1993,1997,1999,2003,2011,2017 }; 
   
   
   private static Node[] T = new Node[M]; 
   
   private static Node[] TNew = null; 
   
   private static class Node {
      
      public int item;
      public Node next;
      
      Node() {                 // this would be the default, put here for reference
         item = 0; 
         next = null;      
      } 
      
      Node(int n) {
         item = n;
         next = null;
      }
      
      Node(int n, Node p) {
         item = n;
         next = p;
      }
   };
   
   public static void printList(Node p) {
      if(p == null)
         System.out.println();
      else {
         System.out.print(" -> " + p.item);
         printList(p.next);
      }
   }
   
   public static void printTable(Node[] T) {
      if(T == null) {
         System.out.println("Table is null");
         return;   
      }  
      for(int i = 0; i < T.length; ++i) {
         System.out.print("[" + i + "]");
         printList(T[i]);    
      }
      System.out.println(); 
   }
   
   public static int hash(int key) {
      return (key * mult) % M;
   }  
   
   public static void delete(int k) {
      T[ hash(k) ] = delete( k, T[ hash(k) ] );
      TNew[ hash(k) ] = delete( k, TNew[ hash(k) ] );
   }
   
   public static Node delete( int k, Node p ) {
      if( p == null )                    
         return p; 
      else if ( p.item == k ) {
         --N;                             // one less key!
         return p.next; 
      }
      else {
         p.next = delete( k, p.next );
         return p; 
      }
   }
   
   public static void insert(int k) {
      System.out.println("Insert( " + k + " ) "); 
      if(rehashing) {
         TNew[ hash(k) ] = insert( k, TNew[ hash(k) ] );
         rehash(); 
      }
      else {
         T[ hash(k) ] = insert( k, T[ hash(k) ] );
         if( (N/(float)M) > resizeLimit )
            resize(); 
      }
   }
   
   public static Node insert( int k, Node p ) {
      if( p == null )  {                      // not in the list, insert at end
         ++N; 
         return new Node( k ); 
      }
      else if( p.item == k ) {               // don't insert duplicates
         return p;
      }
      else {
         p.next = insert( k, p.next ); 
         return p;
      }
   }
   
   public static boolean member(int k) {
      return ( member( k, T[ hash(k) ] )
                 || (rehashing && member( k, TNew[ hash(k) ] )));    
   }
   
   public static boolean member( int k, Node p ) {
      if( p == null )                        // not in the list, insert at end
         return false; 
      else if( p.item == k )                // don't insert duplicates
         return true;
      else 
         return member( k, p.next ); 
   }
   
   
   // returns the prime number just larger than p, or -1 if no larger prime exists
   // in primes array
   
   private static int nextLargerPrime(int p) {
      for(int i = 0; i < primes.length; ++i) {
         if(primes[i] > p) {
            return primes[i];
         }
      }
      return -1; 
   }
   
   private static boolean rehashing = false;      // In the middle of rehashing?
   
   // start the resizing process: allocate new array
   private static void resize() {
  //    System.out.println("resize()"); 
      MNew = nextLargerPrime(M*2); 
      TNew = new Node[MNew];
      System.out.println("                   MNew = " + MNew); 
      M = MNew;
      rehashing = true;    
   }
   
   private static int nextSlot = 0;          // next place to look for key to rehash
   
   // when rehashing, after insert, remove one key from old table and return the key
   // if old table is empty, swap the new one in, and stop "rehashing" mode
   private static void rehash() {
 //     System.out.println("rehash()"); 
      for(int i = nextSlot; i < T.length; ++i) {
         if(T[i] != null) {
            TNew[ hash(T[i].item) ] = insert( T[i].item, TNew[ hash(T[i].item) ] );
            T[i] = T[i].next;           // delete first node in bucket
            --N;                        // decrement key count, will be incremented again on rehash
            return; 
         }
      }
      // table is empty, stop rehashing
      T = TNew;
      TNew = null; 
      M = MNew;
      nextSlot = 0; 
      rehashing = false; 
   }
   
   public static void main(String [] args){
      int[] A = { 4, 2, 6, 8, 1, 5, 23, 43, 25, 73, 24, 14, 87, 33, 42, 27, 53, 13, 24, 111, 128, 84, 29, 122, 26, 11 };
      for(int i = 0; i < A.length; ++i) {
         System.out.println("\n---------------------------"); 
         insert(A[i]); 
         System.out.println("\nM = " + M + "  N = " + N + " Load Factor = " + (N/(float)M));
         System.out.println("\nT:"); 
         printTable(T); 
         System.out.println("TNew:"); 
         printTable(TNew); 
      }
      
      
      
   }
   
}