1 9 package prefuse.util.collections; 10 11 import java.util.ArrayList ; 12 import java.util.Arrays ; 13 14 28 public class IntObjectHashMap extends AbstractHashMap implements Cloneable { 29 30 protected static final int defaultCapacity = 277; 31 protected static final double defaultMinLoadFactor = 0.2; 32 protected static final double defaultMaxLoadFactor = 0.5; 33 34 protected static final byte FREE = 0; 35 protected static final byte FULL = 1; 36 protected static final byte REMOVED = 2; 37 38 41 protected int table[]; 42 43 46 protected Object values[]; 47 48 51 protected byte state[]; 52 53 56 protected int freeEntries; 57 58 61 public IntObjectHashMap() { 62 this(defaultCapacity); 63 } 64 65 74 public IntObjectHashMap(int initialCapacity) { 75 this(initialCapacity, defaultMinLoadFactor, defaultMaxLoadFactor); 76 } 77 78 92 public IntObjectHashMap(int initialCapacity, double minLoadFactor, 93 double maxLoadFactor) { 94 setUp(initialCapacity, minLoadFactor, maxLoadFactor); 95 } 96 97 101 public void clear() { 102 Arrays.fill(state, FREE); 103 Arrays.fill(values, null); 104 105 this.distinct = 0; 106 this.freeEntries = table.length; trimToSize(); 108 } 109 110 114 public Object clone() { 115 try { 116 IntObjectHashMap copy = (IntObjectHashMap) super.clone(); 117 copy.table = (int[]) copy.table.clone(); 118 copy.values = (Object []) copy.values.clone(); 119 copy.state = (byte[]) copy.state.clone(); 120 return copy; 121 } catch (CloneNotSupportedException e) { 122 return null; 124 } 125 } 126 127 131 public boolean containsKey(int key) { 132 return indexOfKey(key) >= 0; 133 } 134 135 139 public boolean containsValue(Object value) { 140 return indexOfValue(value) >= 0; 141 } 142 143 157 public void ensureCapacity(int minCapacity) { 158 if (table.length < minCapacity) { 159 int newCapacity = nextPrime(minCapacity); 160 rehash(newCapacity); 161 } 162 } 163 164 175 public Object get(int key) { 176 int i = indexOfKey(key); 177 if (i < 0) 178 return null; return values[i]; 180 } 181 182 192 protected int indexOfInsertion(int key) { 193 final int tab[] = table; 194 final byte stat[] = state; 195 final int length = tab.length; 196 197 final int hash = key & 0x7FFFFFFF; 198 int i = hash % length; 199 int decrement = hash % (length - 2); 201 if (decrement == 0) 203 decrement = 1; 204 205 while (stat[i] == FULL && tab[i] != key) { 208 i -= decrement; 209 if (i < 0) 211 i += length; 212 } 213 214 if (stat[i] == REMOVED) { 215 int j = i; 219 while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) { 220 i -= decrement; 221 if (i < 0) 223 i += length; 224 } 225 if (stat[i] == FREE) 226 i = j; 227 } 228 229 if (stat[i] == FULL) { 230 return -i - 1; 233 } 234 return i; 237 } 238 239 245 protected int indexOfKey(int key) { 246 final int tab[] = table; 247 final byte stat[] = state; 248 final int length = tab.length; 249 250 final int hash = key & 0x7FFFFFFF; 251 int i = hash % length; 252 int decrement = hash % (length - 2); 254 if (decrement == 0) 256 decrement = 1; 257 258 while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) { 261 i -= decrement; 262 if (i < 0) 264 i += length; 265 } 266 267 if (stat[i] == FREE) 268 return -1; return i; } 271 272 278 protected int indexOfValue(Object value) { 279 final Object val[] = values; 280 final byte stat[] = state; 281 282 for (int i = stat.length; --i >= 0;) { 283 if (stat[i] == FULL && val[i] == value) 284 return i; 285 } 286 287 return -1; } 289 290 299 public int keyOf(Object value) { 300 int i = indexOfValue(value); 303 if (i < 0) 304 return Integer.MIN_VALUE; 305 return table[i]; 306 } 307 308 318 public int keys(int[] list) { 319 int[] tab = table; 320 byte[] stat = state; 321 322 if ( list.length < distinct ) 323 return -1; 324 325 int j = 0; 326 for (int i = tab.length; i-- > 0;) { 327 if (stat[i] == FULL) 328 list[j++] = tab[i]; 329 } 330 return distinct; 331 } 332 333 346 public boolean put(int key, Object value) { 347 int i = indexOfInsertion(key); 348 if (i < 0) { i = -i - 1; 350 this.values[i] = value; 351 return false; 352 } 353 354 if (this.distinct > this.highWaterMark) { 355 int newCapacity = chooseGrowCapacity(this.distinct + 1, 356 this.minLoadFactor, this.maxLoadFactor); 357 rehash(newCapacity); 358 return put(key, value); 359 } 360 361 this.table[i] = key; 362 this.values[i] = value; 363 if (this.state[i] == FREE) 364 this.freeEntries--; 365 this.state[i] = FULL; 366 this.distinct++; 367 368 if (this.freeEntries < 1) { int newCapacity = chooseGrowCapacity(this.distinct + 1, 370 this.minLoadFactor, this.maxLoadFactor); 371 rehash(newCapacity); 372 } 373 374 return true; 375 } 376 377 383 protected void rehash(int newCapacity) { 384 int oldCapacity = table.length; 385 387 int oldTable[] = table; 388 Object oldValues[] = values; 389 byte oldState[] = state; 390 391 int newTable[] = new int[newCapacity]; 392 Object newValues[] = new Object [newCapacity]; 393 byte newState[] = new byte[newCapacity]; 394 395 this.lowWaterMark = chooseLowWaterMark(newCapacity, this.minLoadFactor); 396 this.highWaterMark = chooseHighWaterMark(newCapacity, 397 this.maxLoadFactor); 398 399 this.table = newTable; 400 this.values = newValues; 401 this.state = newState; 402 this.freeEntries = newCapacity - this.distinct; 404 for (int i = oldCapacity; i-- > 0;) { 405 if (oldState[i] == FULL) { 406 int element = oldTable[i]; 407 int index = indexOfInsertion(element); 408 newTable[index] = element; 409 newValues[index] = oldValues[i]; 410 newState[index] = FULL; 411 } 412 } 413 } 414 415 424 public boolean removeKey(int key) { 425 int i = indexOfKey(key); 426 if (i < 0) 427 return false; 429 this.state[i] = REMOVED; 430 this.values[i] = null; this.distinct--; 432 433 if (this.distinct < this.lowWaterMark) { 434 int newCapacity = chooseShrinkCapacity(this.distinct, 435 this.minLoadFactor, this.maxLoadFactor); 436 rehash(newCapacity); 437 } 438 439 return true; 440 } 441 442 455 protected void setUp(int initialCapacity, double minLoadFactor, 456 double maxLoadFactor) { 457 int capacity = initialCapacity; 458 super.setUp(capacity, minLoadFactor, maxLoadFactor); 459 capacity = nextPrime(capacity); 460 if (capacity == 0) 461 capacity = 1; 463 this.table = new int[capacity]; 464 this.values = new Object [capacity]; 465 this.state = new byte[capacity]; 466 467 this.minLoadFactor = minLoadFactor; 469 if (capacity == PrimeFinder.largestPrime) 470 this.maxLoadFactor = 1.0; 471 else 472 this.maxLoadFactor = maxLoadFactor; 473 474 this.distinct = 0; 475 this.freeEntries = capacity; 477 this.lowWaterMark = 0; 482 this.highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor); 483 } 484 485 490 public void trimToSize() { 491 int newCapacity = nextPrime((int) (1 + 1.2 * size())); 494 if (table.length > newCapacity) { 495 rehash(newCapacity); 496 } 497 } 498 499 509 public void values(ArrayList list) { 510 Object [] val = values; 511 byte[] stat = state; 512 513 for (int i = stat.length; i-- > 0;) { 514 if (stat[i] == FULL) 515 list.add(val[i]); 516 } 517 } 518 519 } | Popular Tags |