home *** CD-ROM | disk | FTP | other *** search
/ Apple Developer Connection Student Program / ADC Tools Sampler CD Disk 3 1999.iso / Metrowerks CodeWarrior / Java Support / Java_Source / Java2 / src / java / text / IntHashtable.java < prev    next >
Encoding:
Java Source  |  1999-05-28  |  9.7 KB  |  292 lines  |  [TEXT/CWIE]
  1. /*
  2.  * @(#)IntHashtable.java    1.3 98/09/21
  3.  *
  4.  * Copyright 1998-1998 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  * 
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14. /*
  15.  * @(#)IntHashtable.java    1.3 98/09/21
  16.  *
  17.  * (C) Copyright Taligent, Inc. 1996,1997 - All Rights Reserved
  18.  * (C) Copyright IBM Corp. 1996, 1997 - All Rights Reserved
  19.  */
  20.  
  21. package java.text;
  22.  
  23. /** Simple internal class for doing hash mapping. Much, much faster than the
  24.  * standard Hashtable for integer to integer mappings,
  25.  * and doesn't require object creation.<br>
  26.  * If a key is not found, the defaultValue is returned.
  27.  * Note: the keys are limited to values above Integer.MIN_VALUE+1.<br>
  28.  */
  29. final class IntHashtable {
  30.  
  31.     public IntHashtable () {
  32.         initialize(3);
  33.     }
  34.  
  35.     public IntHashtable (int initialSize) {
  36.         initialize(leastGreaterPrimeIndex((int)(initialSize/highWaterFactor)));
  37.     }
  38.  
  39.     public int size() {
  40.         return count;
  41.     }
  42.  
  43.     public boolean isEmpty() {
  44.         return count == 0;
  45.     }
  46.  
  47.     public void put(int key, int value) {
  48.         if (count > highWaterMark) {
  49.             rehash();
  50.         }
  51.         int index = find(key);
  52.         if (keyList[index] <= MAX_UNUSED) {      // deleted or empty
  53.             keyList[index] = key;
  54.             ++count;
  55.         }
  56.         values[index] = value;                                  // reset value
  57.     }
  58.  
  59.     public int get(int key) {
  60.         return values[find(key)];
  61.     }
  62.  
  63.     public void remove(int key) {
  64.         int index = find(key);
  65.         if (keyList[index] > MAX_UNUSED) {       // neither deleted nor empty
  66.             keyList[index] = DELETED;                        // set to deleted
  67.             values[index] = defaultValue;                        // set to deleted
  68.             --count;
  69.             if (count < lowWaterMark) {
  70.                 rehash();
  71.             }
  72.         }
  73.     }
  74.  
  75.     public int getDefaultValue() {
  76.         return defaultValue;
  77.     }
  78.  
  79.     public void setDefaultValue(int newValue) {
  80.         defaultValue = newValue;
  81.         rehash();
  82.     }
  83.  
  84.     public boolean equals (Object that) {
  85.         if (that.getClass() != this.getClass()) return false;
  86.  
  87.         IntHashtable other = (IntHashtable) that;
  88.         if (other.size() != count || other.defaultValue != defaultValue) {
  89.                 return false;
  90.         }
  91.         for (int i = 0; i < keyList.length; ++i) {
  92.             int key = keyList[i];
  93.             if (key > MAX_UNUSED && other.get(key) != values[i])
  94.                 return false;
  95.         }
  96.         return true;
  97.     }
  98.  
  99.     public Object clone ()
  100.                     throws CloneNotSupportedException {
  101.         IntHashtable result = (IntHashtable) super.clone();
  102.         values = (int[]) values.clone();
  103.         keyList = (int[])keyList.clone();
  104.         return result;
  105.     }
  106.  
  107.     // =======================PRIVATES============================
  108.     private int defaultValue = 0;
  109.  
  110.     // the tables have to have prime-number lengths. Rather than compute
  111.     // primes, we just keep a table, with the current index we are using.
  112.     private int primeIndex;
  113.  
  114.     // highWaterFactor determines the maximum number of elements before
  115.     // a rehash. Can be tuned for different performance/storage characteristics.
  116.     private static final float highWaterFactor = 0.4F;
  117.     private int highWaterMark;
  118.  
  119.     // lowWaterFactor determines the minimum number of elements before
  120.     // a rehash. Can be tuned for different performance/storage characteristics.
  121.     private static final float lowWaterFactor = 0.0F;
  122.     private int lowWaterMark;
  123.  
  124.     private int count;
  125.  
  126.     // we use two arrays to minimize allocations
  127.     private int[] values;
  128.     private int[] keyList;
  129.  
  130.     private static final int EMPTY   = Integer.MIN_VALUE;
  131.     private static final int DELETED = EMPTY + 1;
  132.     private static final int MAX_UNUSED = DELETED;
  133.  
  134.     private void initialize (int primeIndex) {
  135.         if (primeIndex < 0) {
  136.             primeIndex = 0;
  137.         } else if (primeIndex >= PRIMES.length) {
  138.             System.out.println("TOO BIG");
  139.             primeIndex = PRIMES.length - 1;
  140.             // throw new java.util.IllegalArgumentError();
  141.         }
  142.         this.primeIndex = primeIndex;
  143.         int initialSize = PRIMES[primeIndex];
  144.         values = new int[initialSize];
  145.         keyList = new int[initialSize];
  146.         for (int i = 0; i < initialSize; ++i) {
  147.             keyList[i] = EMPTY;
  148.             values[i] = defaultValue;
  149.         }
  150.         count = 0;
  151.         lowWaterMark = (int)(initialSize * lowWaterFactor);
  152.         highWaterMark = (int)(initialSize * highWaterFactor);
  153.     }
  154.  
  155.     private void rehash() {
  156.         int[] oldValues = values;
  157.         int[] oldkeyList = keyList;
  158.         int newPrimeIndex = primeIndex;
  159.         if (count > highWaterMark) {
  160.             ++newPrimeIndex;
  161.         } else if (count < lowWaterMark) {
  162.             newPrimeIndex -= 2;
  163.         }
  164.         initialize(newPrimeIndex);
  165.         for (int i = oldValues.length - 1; i >= 0; --i) {
  166.             int key = oldkeyList[i];
  167.             if (key > MAX_UNUSED) {
  168.                     putInternal(key, oldValues[i]);
  169.             }
  170.         }
  171.     }
  172.  
  173.     public void putInternal (int key, int value) {
  174.         int index = find(key);
  175.         if (keyList[index] < MAX_UNUSED) {      // deleted or empty
  176.             keyList[index] = key;
  177.             ++count;
  178.         }
  179.         values[index] = value;                                  // reset value
  180.     }
  181.  
  182.     private int find (int key) {
  183.         if (key <= MAX_UNUSED)
  184.             throw new IllegalArgumentException("key can't be less than 0xFFFFFFFE");
  185.         int firstDeleted = -1;  // assume invalid index
  186.         int index = (key ^ 0x4000000) % keyList.length;
  187.         if (index < 0) index = -index; // positive only
  188.         int jump = 0; // lazy evaluate
  189.         while (true) {
  190.             int tableHash = keyList[index];
  191.             if (tableHash == key) {                    // quick check
  192.                 return index;
  193.             } else if (tableHash > MAX_UNUSED) {    // neither correct nor unused
  194.                 // ignore
  195.             } else if (tableHash == EMPTY) {        // empty, end o' the line
  196.                 if (firstDeleted >= 0) {
  197.                         index = firstDeleted;           // reset if had deleted slot
  198.                 }
  199.                 return index;
  200.             } else if (firstDeleted < 0) {  // remember first deleted
  201.                     firstDeleted = index;
  202.             }
  203.             // System.out.println("Collision at: " + index);
  204.             if (jump == 0) {                                                        // lazy compute jump
  205.                 jump = (key % (keyList.length - 1));
  206.                 if (jump < 0) jump = -jump;
  207.                 ++jump;
  208.             }
  209.             //*/
  210.             index = (index + jump) % keyList.length;
  211.             //System.out.print(" => " + index);
  212.         }
  213.     }
  214.  
  215.     private static int leastGreaterPrimeIndex(int source) {
  216.         int i;
  217.         for (i = 0; i < PRIMES.length; ++i) {
  218.             if (source < PRIMES[i]) {
  219.                 break;
  220.             }
  221.         }
  222.         return (i == 0) ? 0 : (i - 1);
  223.     }
  224.  
  225.     // This list is the result of buildList below. Can be tuned for different
  226.     // performance/storage characteristics.
  227.     private static final int[] PRIMES = {
  228.         17, 37, 67, 131, 257,
  229.         521, 1031, 2053, 4099, 8209, 16411, 32771, 65537,
  230.         131101, 262147, 524309, 1048583, 2097169, 4194319, 8388617, 16777259,
  231.         33554467, 67108879, 134217757, 268435459, 536870923, 1073741827, 2147483647
  232.  
  233.         // finer-grained table
  234.         /*11, 37, 71, 127, 179, 257, 359, 491, 661, 887, 1181, 1553,
  235.         2053, 2683, 3517, 4591, 6007, 7817, 10193, 13291, 17291,
  236.         22481, 29251, 38053, 49499, 64373, 83701, 108863, 141511,
  237.         184003, 239231, 310997, 404321, 525649, 683377, 888397,
  238.         1154947, 1501447, 1951949, 2537501, 3298807, 4288439,
  239.         5575001, 7247533, 9421793, 12248389, 15922903, 20699753,
  240.         26909713, 34982639, 45477503, 59120749, 76856959, 99914123,
  241.         129888349, 168854831, 219511301, 285364721, 370974151,
  242.         482266423, 626946367, 815030309, 1059539417, 1377401287,
  243.         1790621681, 2147483647
  244.         //*/
  245.     };
  246.  
  247.     /*
  248.     public static void buildList() {
  249.         String currentLine = "";
  250.         for (double target = 8; target < 0x7FFFFFFF; target = 2 * target) {
  251.                 int nextPrime = leastPrimeAsLargeAs((int)target);
  252.                 if (nextPrime <= 0) break;
  253.                 String addition = nextPrime + ", ";
  254.                 if (currentLine.length() + addition.length() > 60) {
  255.                         System.out.println(currentLine);
  256.                         currentLine = addition;
  257.                 } else {
  258.                         currentLine += addition;
  259.                 }
  260.         }
  261.         System.out.print(currentLine);
  262.         System.out.println(greatestPrimeAsSmallAs(Integer.MAX_VALUE));
  263.     }
  264.  
  265.     public static boolean isPrime(int candidate) {
  266.         int sqrt = (int) Math.sqrt(candidate) + 1;
  267.         for (int i = 2; i <= sqrt; ++i) {
  268.                 if (candidate % i == 0) {
  269.                         return false;
  270.                 }
  271.         }
  272.         return true;
  273.     }
  274.  
  275.     public static int leastPrimeAsLargeAs(int target) {
  276.             for (int i = target; i < Integer.MAX_VALUE; ++i) {
  277.                     if (isPrime(i))
  278.                             return i;
  279.             }
  280.             return 0;
  281.     }
  282.     public static int greatestPrimeAsSmallAs(int target) {
  283.             for (int i = target; i > 0 ; --i) {
  284.                     if (isPrime(i))
  285.                             return i;
  286.             }
  287.             return 0;
  288.     }
  289.     //*/
  290. }
  291.  
  292.