/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2006-2013. All rights reserved.
 ******************************************************************************************/

/*
 * »ùÓÚÉ¢ÁÐ±íÊµÏÖµÄÓ³Éä½á¹¹
 * ²ÉÓÃ·ÖÀëÁ´²ßÂÔ½â¾ö³åÍ»
 */

package dsa;

public class Map_HashTable implements Map {
   private Map[] A;//Í°Êý×é£¬Ã¿¸öÍ°±¾ÉíÒ²ÊÇÒ»¸ö£¨»ùÓÚÁÐ±íÊµÏÖµÄ£©Ó³Éä½á¹¹
   private  int N;//É¢ÁÐ±í³¤
   private final double maxLemda = 0.75;//×°ÌîÒò×ÓÉÏÏÞ
   private int size;//Ó³Éä½á¹¹µÄ¹æÄ£
   private EqualityTester T;//ÅÐµÈÆ÷

   //Ä¬ÈÏ¹¹Ôì·½·¨
   public Map_HashTable()
   { this(0, new EqualityTesterDefault()); }

   //¹¹Ôì·½·¨
   public Map_HashTable(int n, EqualityTester t) {
      T = t;
      N = p(n);//Í°Êý×éÈÝÁ¿È¡Îª²»Ð¡ÓÚnµÄ×îÐ¡ËØÊý
      A = new Map[N];
      for (int i = 0; i < N; i++) A[i] = new Map_DLNode(T);
      size = 0;
   }

   /***************************** ¸¨Öú·½·¨ *****************************/
   //É¢ÁÐ¶¨Ö·º¯Êý£¨²ÉÓÃÄ£Óà·¨£©
   private int h(Object key)
   { return key.hashCode() % N; }

   //ÅÐ¶ÏnÊÇ·ñÎªËØÊý
   private static boolean prime(int n) {
      for (int i = 3; i < 1 + Math.sqrt(n); i++)
         if (n / i* i == n)   return false;
      return true;
   }

   //È¡²»Ð¡ÓÚnµÄ×îÐ¡ËØÊý
   private static int p(int n) {
      if (3 > n) n = 3;
      n = n | 1;//ÆæÊý»¯
      while (!prime(n)) n += 2;
      return n;
   }

   /***************************** ADT·½·¨ *****************************/
   //²éÑ¯Ó³Éä½á¹¹µ±Ç°µÄ¹æÄ£
   public int getSize()
   { return size; }

   //ÅÐ¶ÏÓ³Éä½á¹¹ÊÇ·ñÎª¿Õ
   public boolean isEmpty()
   { return 0 == size; }

   //ÈôMÖÐ´æÔÚÒÔkeyÎª¹Ø¼üÂëµÄÌõÄ¿£¬Ôò·µ»Ø¸ÃÌõÄ¿µÄÊý¾Ý¶ÔÏó£»·ñÔò£¬·µ»Ønull
   public Object get(Object key)
   { return A[h(key)].get(key); }

   //ÈôMÖÐ²»´æÔÚÒÔkeyÎª¹Ø¼üÂëµÄÌõÄ¿£¬Ôò½«ÌõÄ¿(key, value)¼ÓÈëµ½MÖÐ²¢·µ»Ønull
   //·ñÔò£¬½«ÒÑÓÐÌõÄ¿µÄÊý¾Ý¶ÔÏóÌæ»»Îªvalue£¬²¢·µ»ØÔ­ÏÈµÄÊý¾Ý¶ÔÏó
   public Object put(Object key, Object value) {
      Object oldValue = A[h(key)].put(key, value);
      if (null == oldValue) { //Èô²åÈëµÄÌõÄ¿Î´³öÏÖÓÚÔ­É¢ÁÐ±íÖÐ£¬Ôò
         size++;//¸üÐÂ¹æÄ£¼ÇÂ¼
         if (size > N * maxLemda)   rehash();//Èô×°ÌîÒò×Ó¹ý´ó£¬ÔòÖØÉ¢ÁÐ
      }
      return oldValue;
   }

   //ÈôMÖÐ´æÔÚÒÔkeyÎª¹Ø¼üÂëµÄÌõÄ¿£¬ÔòÉ¾³ýÖ®²¢·µ»ØÆäÊý¾Ý¶ÔÏó£»·ñÔò£¬·µ»Ønull
   public Object remove(Object key) {
      Object oldValue = A[h(key)].remove(key);
      if (null != oldValue)  size--;
      return oldValue;
   }

   //·µ»ØMÖÐËùÓÐÌõÄ¿µÄÒ»¸öµü´úÆ÷
   //½«¸÷Í°¶ÔÓ¦µÄÓ³Éä½á¹¹µÄµü´úÆ÷´®½ÓÆðÀ´£¬¹¹³ÉÕûÌåµÄµü´úÆ÷
   public Iterator entries() {
      List L = new List_DLNode();
      for (int i = 0; i < N; i++) {
         Iterator it = A[i].entries();
         while (it.hasNext()) L.insertLast(it.getNext());
      }
      return new IteratorElement(L);
   }

   //ÖØÉ¢ÁÐ
   private void rehash() {
      Iterator it = this.entries();
      N = p(N << 1);
      A = new Map[N];//Í°Êý×éÈÝÁ¿ÖÁÉÙ¼Ó±¶
      for (int i = 0; i < N; i++) A[i] = new Map_DLNode(T); //ÎªÃ¿¸öÍ°·ÖÅäÒ»¸ö×ÓÓ³Éä
      while (it.hasNext()) {//½«Æä¶ÔÓ¦µÄÓ³Éä½á¹¹ÖÐµÄ
         Entry e = (Entry)it.getNext();//¸÷ÌõÄ¿ÖðÒ»È¡³ö£¬½«Æä
         Object k = e.getKey();//¹Ø¼üÂëºÍ
         Object v = e.getValue();//Êý¾Ý¶ÔÏó
         A[h(k)].put(k, v);//ÕûºÏÎªÐÂµÄÌõÄ¿£¬²åÈë¶ÔÓ¦µÄ×ÓÓ³ÉäÖÐ
      }
   }
}