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}