001: /*
002: * This class is based on org.apache.IntHashMap.commons.lang
003: * http://jakarta.apache.org/commons/lang/xref/org/apache/commons/lang/IntHashMap.html
004: * It was adapted by Bruno Lowagie for use in iText,
005: * reusing methods that were written by Paulo Soares.
006: * Instead of being a hashtable that stores objects with an int as key,
007: * it stores int values with an int as key.
008: *
009: * This is the original license of the original class IntHashMap:
010: *
011: * Licensed to the Apache Software Foundation (ASF) under one or more
012: * contributor license agreements. See the NOTICE file distributed with
013: * this work for additional information regarding copyright ownership.
014: * The ASF licenses this file to You under the Apache License, Version 2.0
015: * (the "License"); you may not use this file except in compliance with
016: * the License. You may obtain a copy of the License at
017: *
018: * http://www.apache.org/licenses/LICENSE-2.0
019: *
020: * Unless required by applicable law or agreed to in writing, software
021: * distributed under the License is distributed on an "AS IS" BASIS,
022: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
023: * See the License for the specific language governing permissions and
024: * limitations under the License.
025: *
026: * Note: originally released under the GNU LGPL v2.1,
027: * but rereleased by the original author under the ASF license (above).
028: */
029:
030: package com.lowagie.text.pdf;
031:
032: import java.util.Arrays;
033: import java.util.Iterator;
034: import java.util.NoSuchElementException;
035:
036: /***
037: * <p>A hash map that uses primitive ints for the key rather than objects.</p>
038: *
039: * <p>Note that this class is for internal optimization purposes only, and may
040: * not be supported in future releases of Jakarta Commons Lang. Utilities of
041: * this sort may be included in future releases of Jakarta Commons Collections.</p>
042: *
043: * @author Justin Couch
044: * @author Alex Chaffee (alex@apache.org)
045: * @author Stephen Colebourne
046: * @author Bruno Lowagie (change Objects as keys into int values)
047: * @author Paulo Soares (added extra methods)
048: */
049: public class IntHashtable implements Cloneable {
050:
051: /***
052: * The hash table data.
053: */
054: private transient Entry table[];
055:
056: /***
057: * The total number of entries in the hash table.
058: */
059: private transient int count;
060:
061: /***
062: * The table is rehashed when its size exceeds this threshold. (The
063: * value of this field is (int)(capacity * loadFactor).)
064: *
065: * @serial
066: */
067: private int threshold;
068:
069: /***
070: * The load factor for the hashtable.
071: *
072: * @serial
073: */
074: private float loadFactor;
075:
076: /***
077: * <p>Constructs a new, empty hashtable with a default capacity and load
078: * factor, which is <code>20</code> and <code>0.75</code> respectively.</p>
079: */
080: public IntHashtable() {
081: this (150, 0.75f);
082: }
083:
084: /***
085: * <p>Constructs a new, empty hashtable with the specified initial capacity
086: * and default load factor, which is <code>0.75</code>.</p>
087: *
088: * @param initialCapacity the initial capacity of the hashtable.
089: * @throws IllegalArgumentException if the initial capacity is less
090: * than zero.
091: */
092: public IntHashtable(int initialCapacity) {
093: this (initialCapacity, 0.75f);
094: }
095:
096: /***
097: * <p>Constructs a new, empty hashtable with the specified initial
098: * capacity and the specified load factor.</p>
099: *
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: "
109: + initialCapacity);
110: }
111: if (loadFactor <= 0) {
112: throw new IllegalArgumentException("Illegal Load: "
113: + loadFactor);
114: }
115: if (initialCapacity == 0) {
116: initialCapacity = 1;
117: }
118: this .loadFactor = loadFactor;
119: table = new Entry[initialCapacity];
120: threshold = (int) (initialCapacity * loadFactor);
121: }
122:
123: /***
124: * <p>Returns the number of keys in this hashtable.</p>
125: *
126: * @return the number of keys in this hashtable.
127: */
128: public int size() {
129: return count;
130: }
131:
132: /***
133: * <p>Tests if this hashtable maps no keys to values.</p>
134: *
135: * @return <code>true</code> if this hashtable maps no keys to values;
136: * <code>false</code> otherwise.
137: */
138: public boolean isEmpty() {
139: return count == 0;
140: }
141:
142: /***
143: * <p>Tests if some key maps into the specified value in this hashtable.
144: * This operation is more expensive than the <code>containsKey</code>
145: * method.</p>
146: *
147: * <p>Note that this method is identical in functionality to containsValue,
148: * (which is part of the Map interface in the collections framework).</p>
149: *
150: * @param value a value to search for.
151: * @return <code>true</code> if and only if some key maps to the
152: * <code>value</code> argument in this hashtable as
153: * determined by the <tt>equals</tt> method;
154: * <code>false</code> otherwise.
155: * @throws NullPointerException if the value is <code>null</code>.
156: * @see #containsKey(int)
157: * @see #containsValue(int)
158: * @see java.util.Map
159: */
160: public boolean contains(int value) {
161:
162: Entry tab[] = table;
163: for (int i = tab.length; i-- > 0;) {
164: for (Entry e = tab[i]; e != null; e = e.next) {
165: if (e.value == value) {
166: return true;
167: }
168: }
169: }
170: return false;
171: }
172:
173: /***
174: * <p>Returns <code>true</code> if this HashMap maps one or more keys
175: * to this value.</p>
176: *
177: * <p>Note that this method is identical in functionality to contains
178: * (which predates the Map interface).</p>
179: *
180: * @param value value whose presence in this HashMap is to be tested.
181: * @return boolean <code>true</code> if the value is contained
182: * @see java.util.Map
183: * @since JDK1.2
184: */
185: public boolean containsValue(int value) {
186: return contains(value);
187: }
188:
189: /***
190: * <p>Tests if the specified int is a key in this hashtable.</p>
191: *
192: * @param key possible key.
193: * @return <code>true</code> if and only if the specified int is a
194: * key in this hashtable, as determined by the <tt>equals</tt>
195: * method; <code>false</code> otherwise.
196: * @see #contains(int)
197: */
198: public boolean containsKey(int key) {
199: Entry tab[] = table;
200: int hash = key;
201: int index = (hash & 0x7FFFFFFF) % tab.length;
202: for (Entry e = tab[index]; e != null; e = e.next) {
203: if (e.hash == hash && e.key == key) {
204: return true;
205: }
206: }
207: return false;
208: }
209:
210: /***
211: * <p>Returns the value to which the specified key is mapped in this map.</p>
212: *
213: * @param key a key in the hashtable.
214: * @return the value to which the key is mapped in this hashtable;
215: * <code>null</code> if the key is not mapped to any value in
216: * this hashtable.
217: * @see #put(int, int)
218: */
219: public int get(int key) {
220: Entry tab[] = table;
221: int hash = key;
222: int index = (hash & 0x7FFFFFFF) % tab.length;
223: for (Entry e = tab[index]; e != null; e = e.next) {
224: if (e.hash == hash && e.key == key) {
225: return e.value;
226: }
227: }
228: return 0;
229: }
230:
231: /***
232: * <p>Increases the capacity of and internally reorganizes this
233: * hashtable, in order to accommodate and access its entries more
234: * efficiently.</p>
235: *
236: * <p>This method is called automatically when the number of keys
237: * in the hashtable exceeds this hashtable's capacity and load
238: * factor.</p>
239: */
240: protected void rehash() {
241: int oldCapacity = table.length;
242: Entry oldMap[] = table;
243:
244: int newCapacity = oldCapacity * 2 + 1;
245: Entry newMap[] = new Entry[newCapacity];
246:
247: threshold = (int) (newCapacity * loadFactor);
248: table = newMap;
249:
250: for (int i = oldCapacity; i-- > 0;) {
251: for (Entry old = oldMap[i]; old != null;) {
252: Entry e = old;
253: old = old.next;
254:
255: int index = (e.hash & 0x7FFFFFFF) % newCapacity;
256: e.next = newMap[index];
257: newMap[index] = e;
258: }
259: }
260: }
261:
262: /***
263: * <p>Maps the specified <code>key</code> to the specified
264: * <code>value</code> in this hashtable. The key cannot be
265: * <code>null</code>. </p>
266: *
267: * <p>The value can be retrieved by calling the <code>get</code> method
268: * with a key that is equal to the original key.</p>
269: *
270: * @param key the hashtable key.
271: * @param value the value.
272: * @return the previous value of the specified key in this hashtable,
273: * or <code>null</code> if it did not have one.
274: * @throws NullPointerException if the key is <code>null</code>.
275: * @see #get(int)
276: */
277: public int put(int key, int value) {
278: // Makes sure the key is not already in the hashtable.
279: Entry tab[] = table;
280: int hash = key;
281: int index = (hash & 0x7FFFFFFF) % tab.length;
282: for (Entry e = tab[index]; e != null; e = e.next) {
283: if (e.hash == hash && e.key == key) {
284: int old = e.value;
285: e.value = value;
286: return old;
287: }
288: }
289:
290: if (count >= threshold) {
291: // Rehash the table if the threshold is exceeded
292: rehash();
293:
294: tab = table;
295: index = (hash & 0x7FFFFFFF) % tab.length;
296: }
297:
298: // Creates the new entry.
299: Entry e = new Entry(hash, key, value, tab[index]);
300: tab[index] = e;
301: count++;
302: return 0;
303: }
304:
305: /***
306: * <p>Removes the key (and its corresponding value) from this
307: * hashtable.</p>
308: *
309: * <p>This method does nothing if the key is not present in the
310: * hashtable.</p>
311: *
312: * @param key the key that needs to be removed.
313: * @return the value to which the key had been mapped in this hashtable,
314: * or <code>null</code> if the key did not have a mapping.
315: */
316: public int remove(int key) {
317: Entry tab[] = table;
318: int hash = key;
319: int index = (hash & 0x7FFFFFFF) % tab.length;
320: for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
321: if (e.hash == hash && e.key == key) {
322: if (prev != null) {
323: prev.next = e.next;
324: } else {
325: tab[index] = e.next;
326: }
327: count--;
328: int oldValue = e.value;
329: e.value = 0;
330: return oldValue;
331: }
332: }
333: return 0;
334: }
335:
336: /***
337: * <p>Clears this hashtable so that it contains no keys.</p>
338: */
339: public void clear() {
340: Entry tab[] = table;
341: for (int index = tab.length; --index >= 0;) {
342: tab[index] = null;
343: }
344: count = 0;
345: }
346:
347: /***
348: * <p>Innerclass that acts as a datastructure to create a new entry in the
349: * table.</p>
350: */
351: static class Entry {
352: int hash;
353: int key;
354: int value;
355: Entry next;
356:
357: /***
358: * <p>Create a new entry with the given values.</p>
359: *
360: * @param hash The code used to hash the int with
361: * @param key The key used to enter this in the table
362: * @param value The value for this key
363: * @param next A reference to the next entry in the table
364: */
365: protected Entry(int hash, int key, int value, Entry next) {
366: this .hash = hash;
367: this .key = key;
368: this .value = value;
369: this .next = next;
370: }
371:
372: // extra methods for inner class Entry by Paulo
373: public int getKey() {
374: return key;
375: }
376:
377: public int getValue() {
378: return value;
379: }
380:
381: protected Object clone() {
382: Entry entry = new Entry(hash, key, value,
383: (next != null) ? (Entry) next.clone() : null);
384: return entry;
385: }
386: }
387:
388: // extra inner class by Paulo
389: static class IntHashtableIterator implements Iterator {
390: int index;
391: Entry table[];
392: Entry entry;
393:
394: IntHashtableIterator(Entry table[]) {
395: this .table = table;
396: this .index = table.length;
397: }
398:
399: public boolean hasNext() {
400: if (entry != null) {
401: return true;
402: }
403: while (index-- > 0) {
404: if ((entry = table[index]) != null) {
405: return true;
406: }
407: }
408: return false;
409: }
410:
411: public Object next() {
412: if (entry == null) {
413: while ((index-- > 0)
414: && ((entry = table[index]) == null))
415: ;
416: }
417: if (entry != null) {
418: Entry e = entry;
419: entry = e.next;
420: return e;
421: }
422: throw new NoSuchElementException("IntHashtableIterator");
423: }
424:
425: public void remove() {
426: throw new UnsupportedOperationException(
427: "remove() not supported.");
428: }
429: }
430:
431: // extra methods by Paulo Soares:
432:
433: public Iterator getEntryIterator() {
434: return new IntHashtableIterator(table);
435: }
436:
437: public int[] toOrderedKeys() {
438: int res[] = getKeys();
439: Arrays.sort(res);
440: return res;
441: }
442:
443: public int[] getKeys() {
444: int res[] = new int[count];
445: int ptr = 0;
446: int index = table.length;
447: Entry entry = null;
448: while (true) {
449: if (entry == null)
450: while ((index-- > 0)
451: && ((entry = table[index]) == null))
452: ;
453: if (entry == null)
454: break;
455: Entry e = entry;
456: entry = e.next;
457: res[ptr++] = e.key;
458: }
459: return res;
460: }
461:
462: public int getOneKey() {
463: if (count == 0)
464: return 0;
465: int index = table.length;
466: Entry entry = null;
467: while ((index-- > 0) && ((entry = table[index]) == null))
468: ;
469: if (entry == null)
470: return 0;
471: return entry.key;
472: }
473:
474: public Object clone() {
475: try {
476: IntHashtable t = (IntHashtable) super .clone();
477: t.table = new Entry[table.length];
478: for (int i = table.length; i-- > 0;) {
479: t.table[i] = (table[i] != null) ? (Entry) table[i]
480: .clone() : null;
481: }
482: return t;
483: } catch (CloneNotSupportedException e) {
484: // this shouldn't happen, since we are Cloneable
485: throw new InternalError();
486: }
487: }
488: }
|