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 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 }