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
030package com.itextpdf.text.pdf;
031
032import java.util.Arrays;
033import java.util.Iterator;
034import java.util.NoSuchElementException;
035
036import com.itextpdf.text.error_messages.MessageLocalization;
037
038/***
039 * <p>A hash map that uses primitive ints for the key rather than objects.</p>
040 *
041 * <p>Note that this class is for internal optimization purposes only, and may
042 * not be supported in future releases of Jakarta Commons Lang.  Utilities of
043 * this sort may be included in future releases of Jakarta Commons Collections.</p>
044 *
045 * @author Justin Couch
046 * @author Alex Chaffee (alex@apache.org)
047 * @author Stephen Colebourne
048 * @author Bruno Lowagie (change Objects as keys into int values)
049 * @author Paulo Soares (added extra methods)
050 */
051public class IntHashtable implements Cloneable {
052
053    /***
054     * The hash table data.
055     */
056    private transient Entry table[];
057
058    /***
059     * The total number of entries in the hash table.
060     */
061    private transient int count;
062
063    /***
064     * The table is rehashed when its size exceeds this threshold.  (The
065     * value of this field is (int)(capacity * loadFactor).)
066     *
067     * @serial
068     */
069    private int threshold;
070
071    /***
072     * The load factor for the hashtable.
073     *
074     * @serial
075     */
076    private float loadFactor;
077
078    /***
079     * <p>Constructs a new, empty hashtable with a default capacity and load
080     * factor, which is <code>20</code> and <code>0.75</code> respectively.</p>
081     */
082    public IntHashtable() {
083        this(150, 0.75f);
084    }
085
086    /***
087     * <p>Constructs a new, empty hashtable with the specified initial capacity
088     * and default load factor, which is <code>0.75</code>.</p>
089     *
090     * @param  initialCapacity the initial capacity of the hashtable.
091     * @throws IllegalArgumentException if the initial capacity is less
092     *   than zero.
093     */
094    public IntHashtable(int initialCapacity) {
095        this(initialCapacity, 0.75f);
096    }
097
098    /***
099     * <p>Constructs a new, empty hashtable with the specified initial
100     * capacity and the specified load factor.</p>
101     *
102     * @param initialCapacity the initial capacity of the hashtable.
103     * @param loadFactor the load factor of the hashtable.
104     * @throws IllegalArgumentException  if the initial capacity is less
105     *             than zero, or if the load factor is nonpositive.
106     */
107    public IntHashtable(int initialCapacity, float loadFactor) {
108        super();
109        if (initialCapacity < 0) {
110            throw new IllegalArgumentException(MessageLocalization.getComposedMessage("illegal.capacity.1", initialCapacity));
111        }
112        if (loadFactor <= 0) {
113            throw new IllegalArgumentException(MessageLocalization.getComposedMessage("illegal.load.1", String.valueOf(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        public int getValue() {
377                return value;
378        }
379        @Override
380        protected Object clone() {
381                Entry entry = new Entry(hash, key, value, next != null ? (Entry)next.clone() : null);
382                return entry;
383        }
384    }
385
386    // extra inner class by Paulo
387    static class IntHashtableIterator implements Iterator<Entry> {
388        int index;
389        Entry table[];
390        Entry entry;
391
392        IntHashtableIterator(Entry table[]) {
393                this.table = table;
394                this.index = table.length;
395        }
396        public boolean hasNext() {
397                if (entry != null) {
398                        return true;
399                }
400                while (index-- > 0) {
401                    if ((entry = table[index]) != null) {
402                        return true;
403                    }
404                }
405                return false;
406        }
407
408        public Entry next() {
409            if (entry == null) {
410                while (index-- > 0 && (entry = table[index]) == null);
411            }
412            if (entry != null) {
413                Entry e = entry;
414                entry = e.next;
415                return e;
416            }
417                throw new NoSuchElementException(MessageLocalization.getComposedMessage("inthashtableiterator"));
418        }
419        public void remove() {
420                throw new UnsupportedOperationException(MessageLocalization.getComposedMessage("remove.not.supported"));
421        }
422    }
423
424// extra methods by Paulo Soares:
425
426    public Iterator<Entry> getEntryIterator() {
427        return new IntHashtableIterator(table);
428    }
429
430    public int[] toOrderedKeys() {
431        int res[] = getKeys();
432        Arrays.sort(res);
433        return res;
434    }
435
436    public int[] getKeys() {
437        int res[] = new int[count];
438        int ptr = 0;
439        int index = table.length;
440        Entry entry = null;
441        while (true) {
442                if (entry == null)
443                        while (index-- > 0 && (entry = table[index]) == null);
444                if (entry == null)
445                        break;
446                Entry e = entry;
447                entry = e.next;
448                res[ptr++] = e.key;
449        }
450        return res;
451    }
452
453    public int getOneKey() {
454        if (count == 0)
455                return 0;
456        int index = table.length;
457        Entry entry = null;
458        while (index-- > 0 && (entry = table[index]) == null);
459        if (entry == null)
460                return 0;
461        return entry.key;
462    }
463
464    @Override
465    public Object clone() {
466        try {
467                IntHashtable t = (IntHashtable)super.clone();
468                t.table = new Entry[table.length];
469                for (int i = table.length ; i-- > 0 ; ) {
470                        t.table[i] = table[i] != null
471                        ? (Entry)table[i].clone() : null;
472                }
473                return t;
474        } catch (CloneNotSupportedException e) {
475                // this shouldn't happen, since we are Cloneable
476                throw new InternalError();
477        }
478    }
479}