IntHashtable


1   /*
2    * This class is based on org.apache.IntHashMap.commons.lang
3    * http://jakarta.apache.org/commons/lang/xref/org/apache/commons/lang/IntHashMap.html
4    * It was adapted by Bruno Lowagie for use in iText,
5    * reusing methods that were written by Paulo Soares.
6    * Instead of being a hashtable that stores objects with an int as key,
7    * it stores int values with an int as key.
8    * 
9    * This is the original license of the original class IntHashMap:
10   * 
11   * Licensed to the Apache Software Foundation (ASF) under one or more
12   * contributor license agreements.  See the NOTICE file distributed with
13   * this work for additional information regarding copyright ownership.
14   * The ASF licenses this file to You under the Apache License, Version 2.0
15   * (the "License"); you may not use this file except in compliance with
16   * the License.  You may obtain a copy of the License at
17   * 
18   *      http://www.apache.org/licenses/LICENSE-2.0
19   * 
20   * Unless required by applicable law or agreed to in writing, software
21   * distributed under the License is distributed on an "AS IS" BASIS,
22   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
23   * See the License for the specific language governing permissions and
24   * limitations under the License.
25   * 
26   * Note: originally released under the GNU LGPL v2.1, 
27   * but rereleased by the original author under the ASF license (above).
28   */
29  
30  package com.lowagie.text.pdf;
31  
32  import java.util.Arrays  ;
33  import java.util.Iterator  ;
34  import java.util.NoSuchElementException  ;
35  
36  /***
37   * <p>A hash map that uses primitive ints for the key rather than objects.</p>
38   *
39   * <p>Note that this class is for internal optimization purposes only, and may
40   * not be supported in future releases of Jakarta Commons Lang.  Utilities of
41   * this sort may be included in future releases of Jakarta Commons Collections.</p>
42   *
43   * @author Justin Couch
44   * @author Alex Chaffee (alex@apache.org)
45   * @author Stephen Colebourne
46   * @author Bruno Lowagie (change Objects as keys into int values)
47   * @author Paulo Soares (added extra methods)
48   */
49  public class IntHashtable implements Cloneable   {
50  
51      /***
52       * The hash table data.
53       */
54      private transient Entry table[];
55  
56      /***
57       * The total number of entries in the hash table.
58       */
59      private transient int count;
60  
61      /***
62       * The table is rehashed when its size exceeds this threshold.  (The
63       * value of this field is (int)(capacity * loadFactor).)
64       *
65       * @serial
66       */
67      private int threshold;
68  
69      /***
70       * The load factor for the hashtable.
71       *
72       * @serial
73       */
74      private float loadFactor;
75  
76      /***
77       * <p>Constructs a new, empty hashtable with a default capacity and load
78       * factor, which is <code>20</code> and <code>0.75</code> respectively.</p>
79       */
80      public IntHashtable() {
81          this(150, 0.75f);
82      }
83  
84      /***
85       * <p>Constructs a new, empty hashtable with the specified initial capacity
86       * and default load factor, which is <code>0.75</code>.</p>
87       *
88       * @param  initialCapacity the initial capacity of the hashtable.
89       * @throws IllegalArgumentException if the initial capacity is less
90       *   than zero.
91       */
92      public IntHashtable(int initialCapacity) {
93          this(initialCapacity, 0.75f);
94      }
95  
96      /***
97       * <p>Constructs a new, empty hashtable with the specified initial
98       * capacity and the specified load factor.</p>
99       *
100      * @param initialCapacity the initial capacity of the hashtable.
101      * @param loadFactor the load factor of the hashtable.
102      * @throws IllegalArgumentException  if the initial capacity is less
103      *             than zero, or if the load factor is nonpositive.
104      */
105     public IntHashtable(int initialCapacity, float loadFactor) {
106         super();
107         if (initialCapacity < 0) {
108             throw new IllegalArgumentException  ("Illegal Capacity: " + initialCapacity);
109         }
110         if (loadFactor <= 0) {
111             throw new IllegalArgumentException  ("Illegal Load: " + loadFactor);
112         }
113         if (initialCapacity == 0) {
114             initialCapacity = 1;
115         }
116         this.loadFactor = loadFactor;
117         table = new Entry[initialCapacity];
118         threshold = (int) (initialCapacity * loadFactor);
119     }
120 
121     /***
122      * <p>Returns the number of keys in this hashtable.</p>
123      *
124      * @return  the number of keys in this hashtable.
125      */
126     public int size() {
127         return count;
128     }
129 
130     /***
131      * <p>Tests if this hashtable maps no keys to values.</p>
132      *
133      * @return  <code>true</code> if this hashtable maps no keys to values;
134      *          <code>false</code> otherwise.
135      */
136     public boolean isEmpty() {
137         return count == 0;
138     }
139 
140     /***
141      * <p>Tests if some key maps into the specified value in this hashtable.
142      * This operation is more expensive than the <code>containsKey</code>
143      * method.</p>
144      *
145      * <p>Note that this method is identical in functionality to containsValue,
146      * (which is part of the Map interface in the collections framework).</p>
147      *
148      * @param      value   a value to search for.
149      * @return     <code>true</code> if and only if some key maps to the
150      *             <code>value</code> argument in this hashtable as
151      *             determined by the <tt>equals</tt> method;
152      *             <code>false</code> otherwise.
153      * @throws  NullPointerException  if the value is <code>null</code>.
154      * @see        #containsKey(int)
155      * @see        #containsValue(int)
156      * @see        java.util.Map
157      */
158     public boolean contains(int value) {
159 
160         Entry tab[] = table;
161         for (int i = tab.length; i-- > 0;) {
162             for (Entry e = tab[i]; e != null; e = e.next) {
163                 if (e.value == value) {
164                     return true;
165                 }
166             }
167         }
168         return false;
169      }
170 
171     /***
172      * <p>Returns <code>true</code> if this HashMap maps one or more keys
173      * to this value.</p>
174      *
175      * <p>Note that this method is identical in functionality to contains
176      * (which predates the Map interface).</p>
177      *
178      * @param value value whose presence in this HashMap is to be tested.
179      * @return boolean <code>true</code> if the value is contained
180      * @see    java.util.Map
181      * @since JDK1.2
182      */
183     public boolean containsValue(int value) {
184         return contains(value);
185     }
186 
187     /***
188      * <p>Tests if the specified int is a key in this hashtable.</p>
189      *
190      * @param  key  possible key.
191      * @return <code>true</code> if and only if the specified int is a
192      *    key in this hashtable, as determined by the <tt>equals</tt>
193      *    method; <code>false</code> otherwise.
194      * @see #contains(int)
195      */
196     public boolean containsKey(int key) {
197         Entry tab[] = table;
198         int hash = key;
199         int index = (hash & 0x7FFFFFFF) % tab.length;
200         for (Entry e = tab[index]; e != null; e = e.next) {
201             if (e.hash == hash && e.key == key) {
202                 return true;
203             }
204         }
205         return false;
206     }
207 
208     /***
209      * <p>Returns the value to which the specified key is mapped in this map.</p>
210      *
211      * @param   key   a key in the hashtable.
212      * @return  the value to which the key is mapped in this hashtable;
213      *          <code>null</code> if the key is not mapped to any value in
214      *          this hashtable.
215      * @see     #put(int, int)
216      */
217     public int get(int key) {
218         Entry tab[] = table;
219         int hash = key;
220         int index = (hash & 0x7FFFFFFF) % tab.length;
221         for (Entry e = tab[index]; e != null; e = e.next) {
222             if (e.hash == hash && e.key == key) {
223                 return e.value;
224             }
225         }
226         return 0;
227     }
228 
229     /***
230      * <p>Increases the capacity of and internally reorganizes this
231      * hashtable, in order to accommodate and access its entries more
232      * efficiently.</p>
233      *
234      * <p>This method is called automatically when the number of keys
235      * in the hashtable exceeds this hashtable's capacity and load
236      * factor.</p>
237      */
238     protected void rehash() {
239         int oldCapacity = table.length;
240         Entry oldMap[] = table;
241 
242         int newCapacity = oldCapacity * 2 + 1;
243         Entry newMap[] = new Entry[newCapacity];
244 
245         threshold = (int) (newCapacity * loadFactor);
246         table = newMap;
247 
248         for (int i = oldCapacity; i-- > 0;) {
249             for (Entry old = oldMap[i]; old != null;) {
250                 Entry e = old;
251                 old = old.next;
252 
253                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
254                 e.next = newMap[index];
255                 newMap[index] = e;
256             }
257         }
258     }
259 
260     /***
261      * <p>Maps the specified <code>key</code> to the specified
262      * <code>value</code> in this hashtable. The key cannot be
263      * <code>null</code>. </p>
264      *
265      * <p>The value can be retrieved by calling the <code>get</code> method
266      * with a key that is equal to the original key.</p>
267      *
268      * @param key     the hashtable key.
269      * @param value   the value.
270      * @return the previous value of the specified key in this hashtable,
271      *         or <code>null</code> if it did not have one.
272      * @throws  NullPointerException  if the key is <code>null</code>.
273      * @see     #get(int)
274      */
275     public int put(int key, int value) {
276         // Makes sure the key is not already in the hashtable.
277         Entry tab[] = table;
278         int hash = key;
279         int index = (hash & 0x7FFFFFFF) % tab.length;
280         for (Entry e = tab[index]; e != null; e = e.next) {
281             if (e.hash == hash && e.key == key) {
282                 int old = e.value;
283                 e.value = value;
284                 return old;
285             }
286         }
287 
288         if (count >= threshold) {
289             // Rehash the table if the threshold is exceeded
290             rehash();
291 
292             tab = table;
293             index = (hash & 0x7FFFFFFF) % tab.length;
294         }
295  
296          // Creates the new entry.
297          Entry e = new Entry(hash, key, value, tab[index]);
298          tab[index] = e;
299          count++;
300          return 0;
301     }
302 
303     /***
304      * <p>Removes the key (and its corresponding value) from this
305      * hashtable.</p>
306      *
307      * <p>This method does nothing if the key is not present in the
308      * hashtable.</p>
309      *
310      * @param   key   the key that needs to be removed.
311      * @return  the value to which the key had been mapped in this hashtable,
312      *          or <code>null</code> if the key did not have a mapping.
313      */
314     public int remove(int key) {
315         Entry tab[] = table;
316         int hash = key;
317         int index = (hash & 0x7FFFFFFF) % tab.length;
318         for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
319             if (e.hash == hash && e.key == key) {
320                 if (prev != null) {
321                     prev.next = e.next;
322                 } else {
323                     tab[index] = e.next;
324                 }
325                 count--;
326                 int oldValue = e.value;
327                 e.value = 0;
328                 return oldValue;
329             }
330         }
331         return 0;
332     }
333 
334     /***
335      * <p>Clears this hashtable so that it contains no keys.</p>
336      */
337     public synchronized void clear() {
338         Entry tab[] = table;
339         for (int index = tab.length; --index >= 0;) {
340             tab[index] = null;
341         }
342         count = 0;
343     }
344     
345     /***
346      * <p>Innerclass that acts as a datastructure to create a new entry in the
347      * table.</p>
348      */
349     static class Entry {
350         int hash;
351         int key;
352         int value;
353         Entry next;
354 
355         /***
356          * <p>Create a new entry with the given values.</p>
357          *
358          * @param hash The code used to hash the int with
359          * @param key The key used to enter this in the table
360          * @param value The value for this key
361          * @param next A reference to the next entry in the table
362          */
363         protected Entry(int hash, int key, int value, Entry next) {
364             this.hash = hash;
365             this.key = key;
366             this.value = value;
367             this.next = next;
368         }
369         
370         // extra methods for inner class Entry by Paulo
371         public int getKey() {
372             return key;
373         }
374         public int getValue() {
375             return value;
376         }
377         protected Object   clone() {
378             Entry entry = new Entry(hash, key, value, (next != null) ? (Entry)next.clone() : null);
379             return entry;
380         }
381     }
382     
383     // extra inner class by Paulo
384     static class IntHashtableIterator implements Iterator   {
385         int index;
386         Entry table[];
387         Entry entry;
388         
389         IntHashtableIterator(Entry table[]) {
390             this.table = table;
391             this.index = table.length;
392         }
393         public boolean hasNext() {
394             if (entry != null) {
395                 return true;
396             }
397             while (index-- > 0) {
398                 if ((entry = table[index]) != null) {
399                     return true;
400                 }
401             }
402             return false;
403         }
404         
405         public Object   next() {
406             if (entry == null) {
407                 while ((index-- > 0) && ((entry = table[index]) == null));
408             }
409             if (entry != null) {
410                 Entry e = entry;
411                 entry = e.next;
412                 return e;
413             }
414             throw new NoSuchElementException  ("IntHashtableIterator");
415         }
416         public void remove() {
417             throw new UnsupportedOperationException  ("remove() not supported.");
418         }
419     }
420     
421 // extra methods by Paulo Soares:
422 
423     public Iterator   getEntryIterator() {
424         return new IntHashtableIterator(table);
425     }
426     
427     public int[] toOrderedKeys() {
428         int res[] = getKeys();
429         Arrays.sort(res);
430         return res;
431     }
432     
433     public int[] getKeys() {
434         int res[] = new int[count];
435         int ptr = 0;
436         int index = table.length;
437         Entry entry = null;
438         while (true) {
439             if (entry == null)
440                 while ((index-- > 0) && ((entry = table[index]) == null));
441             if (entry == null)
442                 break;
443             Entry e = entry;
444             entry = e.next;
445             res[ptr++] = e.key;
446         }
447         return res;
448     }
449     
450     public int getOneKey() {
451         if (count == 0)
452             return 0;
453         int index = table.length;
454         Entry entry = null;
455         while ((index-- > 0) && ((entry = table[index]) == null));
456         if (entry == null)
457             return 0;
458         return entry.key;
459     }
460     
461     public Object   clone() {
462         try {
463             IntHashtable t = (IntHashtable)super.clone();
464             t.table = new Entry[table.length];
465             for (int i = table.length ; i-- > 0 ; ) {
466                 t.table[i] = (table[i] != null)
467                 ? (Entry)table[i].clone() : null;
468             }
469             return t;
470         } catch (CloneNotSupportedException   e) {
471             // this shouldn't happen, since we are Cloneable
472             throw new InternalError  ();
473         }
474     }
475 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags