001/* 002 * Copyright (C) 2002-2015 Sebastiano Vigna 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016package squidpony.squidmath; 017 018import squidpony.annotation.GwtIncompatible; 019 020import java.io.Serializable; 021import java.util.*; 022 023/** 024 * A generic unordered hash map; generally prefer {@link HashMap} unless you need array keys. Originally from fastutil 025 * as Object2ObjectOpenCustomHashMap but modified to support SquidLib's {@link squidpony.squidmath.CrossHash.IHasher} 026 * interface for custom hashing instead of fastutil's Strategy interface. 027 * <br> 028 * Instances of this class use a hash table to represent a map. The table is filled up to a specified <em>load factor</em>, and then doubled in size to accommodate new entries. If the table is 029 * emptied below <em>one fourth</em> of the load factor, it is halved in size. However, halving is not performed when deleting entries from an iterator, as it would interfere with the iteration 030 * process. 031 * <br> 032 * Note that {@link #clear()} does not modify the hash table size. Rather, a family of {@linkplain #trim() trimming methods} lets you control the size of the table; this is particularly useful if 033 * you reuse instances of this class. 034 * <br> 035 * You can pass a {@link CrossHash.IHasher} instance such as {@link CrossHash#generalHasher} as an extra parameter to 036 * most of this class' constructors, which allows the OrderedMap to use arrays (usually primitive arrays) as keys. If 037 * you expect only one type of array, you can use an instance like {@link CrossHash#intHasher} to hash int arrays, or 038 * the aforementioned generalHasher to hash most kinds of arrays (it can't handle most multi-dimensional arrays well). 039 * If you aren't using arrays as keys, you don't need to give an IHasher to the constructor and can ignore this feature 040 * most of the time. However, the default IHasher this uses if none is specified performs a small but significant 041 * "mixing" step to make the default generated hashCode() implementation many classes use into a higher-quality 042 * random-like value. This isn't always optimal; if you plan to insert 1000 sequential Integer keys with some small 043 * amount of random Integers after them, then the mixing actually increases the likelihood of a collision and takes time 044 * to calculate. You could use a very simple IHasher in that case, relying on the fact that only Integers will be added: 045 * <pre> 046 * new CrossHash.IHasher() { 047 * public int hash(Object data) { return (int)data; } 048 * public boolean areEqual(Object left, Object right) { return Objects.equals(left, right); } 049 * }; 050 * </pre> 051 * This is just one example of a case where a custom IHasher can be useful for performance reasons; there are also cases 052 * where an IHasher is needed to enforce hashing by identity or by value, which affect program logic. Note that the 053 * given IHasher is likely to be sub-optimal for many situations with Integer keys, and you may want to try a few 054 * different approaches if you know OrderedMap is a bottleneck in your application. If the IHasher is a performance 055 * problem, it will be at its worst if the OrderedMap needs to resize, and thus rehash, many times; this won't happen if 056 * the capacity is set correctly when the OrderedMap is created (with the capacity equal to or greater than the maximum 057 * number of entries that will be added). 058 * <br> 059 * Thank you, Sebastiano Vigna, for making FastUtil available to the public with such high quality. 060 * <br> 061 * See https://github.com/vigna/fastutil for the original library. 062 * @author Sebastiano Vigna (responsible for all the hard parts) 063 * @author Tommy Ettinger (mostly responsible for squashing several layers of parent classes into one monster class) 064 */ 065public class UnorderedMap<K, V> implements Map<K, V>, Serializable, Cloneable { 066 private static final long serialVersionUID = 0L; 067 /** 068 * The array of keys. 069 */ 070 protected K[] key; 071 /** 072 * The array of values. 073 */ 074 protected V[] value; 075 /** 076 * The mask for wrapping a position counter. 077 */ 078 protected int mask; 079 /** 080 * Whether this set contains the key zero. 081 */ 082 protected boolean containsNullKey; 083 /** 084 * The current table size. 085 */ 086 protected int n; 087 /** 088 * Threshold after which we rehash. It must be the table size times {@link #f}. 089 */ 090 protected int maxFill; 091 /** 092 * Number of entries in the set (including the key zero, if present). 093 */ 094 protected int size; 095 /** 096 * The acceptable load factor. 097 */ 098 public final float f; 099 /** 100 * Cached set of entries. 101 */ 102 protected volatile MapEntrySet entries; 103 /** 104 * Cached set of keys. 105 */ 106 protected volatile KeySet keys; 107 /** 108 * Cached collection of values. 109 */ 110 protected volatile Collection<V> values; 111 /** 112 * Default return value. 113 */ 114 protected V defRetValue; 115 116 /** 117 * The initial default size of a hash table. 118 */ 119 public static final int DEFAULT_INITIAL_SIZE = 16; 120 /** 121 * The default load factor of a hash table. 122 */ 123 public static final float DEFAULT_LOAD_FACTOR = .375f; // .1875f; // .75f; 124 /** 125 * The load factor for a (usually small) table that is meant to be particularly fast. 126 */ 127 public static final float FAST_LOAD_FACTOR = .5f; 128 /** 129 * The load factor for a (usually very small) table that is meant to be extremely fast. 130 */ 131 public static final float VERY_FAST_LOAD_FACTOR = .25f; 132 133 protected final CrossHash.IHasher hasher; 134 135 public void defaultReturnValue(final V rv) { 136 defRetValue = rv; 137 } 138 139 public V defaultReturnValue() { 140 return defRetValue; 141 } 142 143 /** 144 * Creates a new OrderedMap. 145 * <p> 146 * <p>The actual table size will be the least power of two greater than <code>expected</code>/<code>f</code>. 147 * 148 * @param expected the expected number of elements in the hash set. 149 * @param f the load factor. 150 */ 151 152 @SuppressWarnings("unchecked") 153 public UnorderedMap(final int expected, final float f) { 154 if (f <= 0 || f > 1) 155 throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than or equal to 1"); 156 if (expected < 0) throw new IllegalArgumentException("The expected number of elements must be nonnegative"); 157 this.f = f; 158 n = arraySize(expected, f); 159 mask = n - 1; 160 maxFill = maxFill(n, f); 161 key = (K[]) new Object[n + 1]; 162 value = (V[]) new Object[n + 1]; 163 hasher = CrossHash.mildHasher; 164 } 165 166 /** 167 * Creates a new OrderedMap with 0.75f as load factor. 168 * 169 * @param expected the expected number of elements in the OrderedMap. 170 */ 171 public UnorderedMap(final int expected) { 172 this(expected, DEFAULT_LOAD_FACTOR); 173 } 174 175 /** 176 * Creates a new OrderedMap with initial expected 16 entries and 0.75f as load factor. 177 */ 178 public UnorderedMap() { 179 this(DEFAULT_INITIAL_SIZE, DEFAULT_LOAD_FACTOR); 180 } 181 182 /** 183 * Creates a new OrderedMap copying a given one. 184 * 185 * @param m a {@link Map} to be copied into the new OrderedMap. 186 * @param f the load factor. 187 */ 188 public UnorderedMap(final Map<? extends K, ? extends V> m, final float f) { 189 this(m.size(), f, (m instanceof UnorderedMap) ? ((UnorderedMap) m).hasher : CrossHash.mildHasher); 190 putAll(m); 191 } 192 193 /** 194 * Creates a new OrderedMap with 0.75f as load factor copying a given one. 195 * 196 * @param m a {@link Map} to be copied into the new OrderedMap. 197 */ 198 public UnorderedMap(final Map<? extends K, ? extends V> m) { 199 this(m, (m instanceof UnorderedMap) ? ((UnorderedMap) m).f : DEFAULT_LOAD_FACTOR, (m instanceof UnorderedMap) ? ((UnorderedMap) m).hasher : CrossHash.mildHasher); 200 } 201 202 /** 203 * Creates a new OrderedMap using the elements of two parallel arrays. 204 * 205 * @param keyArray the array of keys of the new OrderedMap. 206 * @param valueArray the array of corresponding values in the new OrderedMap. 207 * @param f the load factor. 208 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 209 */ 210 public UnorderedMap(final K[] keyArray, final V[] valueArray, final float f) { 211 this(keyArray.length, f); 212 if (keyArray.length != valueArray.length) 213 throw new IllegalArgumentException("The key array and the value array have different lengths (" + keyArray.length + " and " + valueArray.length + ")"); 214 for (int i = 0; i < keyArray.length; i++) 215 put(keyArray[i], valueArray[i]); 216 } 217 /** 218 * Creates a new OrderedMap using the elements of two parallel arrays. 219 * 220 * @param keyColl the collection of keys of the new OrderedMap. 221 * @param valueColl the collection of corresponding values in the new OrderedMap. 222 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 223 */ 224 public UnorderedMap(final Collection<K> keyColl, final Collection<V> valueColl) { 225 this(keyColl, valueColl, DEFAULT_LOAD_FACTOR); 226 } 227 /** 228 * Creates a new OrderedMap using the elements of two parallel arrays. 229 * 230 * @param keyColl the collection of keys of the new OrderedMap. 231 * @param valueColl the collection of corresponding values in the new OrderedMap. 232 * @param f the load factor. 233 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 234 */ 235 public UnorderedMap(final Collection<K> keyColl, final Collection<V> valueColl, final float f) { 236 this(keyColl.size(), f); 237 if (keyColl.size() != valueColl.size()) 238 throw new IllegalArgumentException("The key array and the value array have different lengths (" + keyColl.size() + " and " + valueColl.size() + ")"); 239 Iterator<K> ki = keyColl.iterator(); 240 Iterator<V> vi = valueColl.iterator(); 241 while (ki.hasNext() && vi.hasNext()) 242 { 243 put(ki.next(), vi.next()); 244 } 245 } 246 247 /** 248 * Creates a new OrderedMap with 0.75f as load factor using the elements of two parallel arrays. 249 * 250 * @param keyArray the array of keys of the new OrderedMap. 251 * @param valueArray the array of corresponding values in the new OrderedMap. 252 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 253 */ 254 public UnorderedMap(final K[] keyArray, final V[] valueArray) { 255 this(keyArray, valueArray, DEFAULT_LOAD_FACTOR); 256 } 257 258 /** 259 * Creates a new OrderedMap. 260 * <p> 261 * <p>The actual table size will be the least power of two greater than <code>expected</code>/<code>f</code>. 262 * 263 * @param expected the expected number of elements in the hash set. 264 * @param f the load factor. 265 * @param hasher used to hash items; typically only needed when K is an array, where CrossHash has implementations 266 */ 267 268 @SuppressWarnings("unchecked") 269 public UnorderedMap(final int expected, final float f, CrossHash.IHasher hasher) { 270 if (f <= 0 || f > 1) 271 throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than or equal to 1"); 272 if (expected < 0) throw new IllegalArgumentException("The expected number of elements must be nonnegative"); 273 this.f = f; 274 n = arraySize(expected, f); 275 mask = n - 1; 276 maxFill = maxFill(n, f); 277 key = (K[]) new Object[n + 1]; 278 value = (V[]) new Object[n + 1]; 279 this.hasher = (hasher == null) ? CrossHash.mildHasher : hasher; 280 } 281 /** 282 * Creates a new OrderedMap with 0.75f as load factor. 283 * 284 * @param expected the expected number of elements in the OrderedMap. 285 * @param hasher used to hash items; typically only needed when K is an array, where CrossHash has implementations 286 */ 287 public UnorderedMap(final int expected, CrossHash.IHasher hasher) { 288 this(expected, DEFAULT_LOAD_FACTOR, hasher); 289 } 290 291 /** 292 * Creates a new OrderedMap with initial expected 16 entries and 0.75f as load factor. 293 */ 294 public UnorderedMap(CrossHash.IHasher hasher) { 295 this(DEFAULT_INITIAL_SIZE, DEFAULT_LOAD_FACTOR, hasher); 296 } 297 298 /** 299 * Creates a new OrderedMap copying a given one. 300 * 301 * @param m a {@link Map} to be copied into the new OrderedMap. 302 * @param f the load factor. 303 * @param hasher used to hash items; typically only needed when K is an array, where CrossHash has implementations 304 */ 305 public UnorderedMap(final Map<? extends K, ? extends V> m, final float f, CrossHash.IHasher hasher) { 306 this(m.size(), f, hasher); 307 putAll(m); 308 } 309 310 /** 311 * Creates a new OrderedMap with 0.75f as load factor copying a given one. 312 * @param m a {@link Map} to be copied into the new OrderedMap. 313 * @param hasher used to hash items; typically only needed when K is an array, where CrossHash has implementations 314 */ 315 public UnorderedMap(final Map<? extends K, ? extends V> m, CrossHash.IHasher hasher) { 316 this(m, DEFAULT_LOAD_FACTOR, hasher); 317 } 318 319 /** 320 * Creates a new OrderedMap using the elements of two parallel arrays. 321 * 322 * @param keyArray the array of keys of the new OrderedMap. 323 * @param valueArray the array of corresponding values in the new OrderedMap. 324 * @param f the load factor. 325 * @param hasher used to hash items; typically only needed when K is an array, where CrossHash has implementations 326 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 327 */ 328 public UnorderedMap(final K[] keyArray, final V[] valueArray, final float f, CrossHash.IHasher hasher) { 329 this(keyArray.length, f, hasher); 330 if (keyArray.length != valueArray.length) 331 throw new IllegalArgumentException("The key array and the value array have different lengths (" + keyArray.length + " and " + valueArray.length + ")"); 332 for (int i = 0; i < keyArray.length; i++) 333 put(keyArray[i], valueArray[i]); 334 } 335 /** 336 * Creates a new OrderedMap with 0.75f as load factor using the elements of two parallel arrays. 337 * 338 * @param keyArray the array of keys of the new OrderedMap. 339 * @param valueArray the array of corresponding values in the new OrderedMap. 340 * @param hasher used to hash items; typically only needed when K is an array, where CrossHash has implementations 341 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 342 */ 343 public UnorderedMap(final K[] keyArray, final V[] valueArray, CrossHash.IHasher hasher) { 344 this(keyArray, valueArray, DEFAULT_LOAD_FACTOR, hasher); 345 } 346 347 private int realSize() { 348 return containsNullKey ? size - 1 : size; 349 } 350 private void ensureCapacity(final int capacity) { 351 final int needed = arraySize(capacity, f); 352 if (needed > n) 353 rehash(needed); 354 } 355 private void tryCapacity(final long capacity) { 356 final int needed = (int) Math.min( 357 1 << 30, 358 Math.max(2, HashCommon.nextPowerOfTwo((long) Math.ceil(capacity 359 / f)))); 360 if (needed > n) 361 rehash(needed); 362 } 363 private V removeEntry(final int pos) { 364 final V oldValue = value[pos]; 365 value[pos] = null; 366 size--; 367 shiftKeys(pos); 368 if (size < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) 369 rehash(n / 2); 370 return oldValue; 371 } 372 private V removeNullEntry() { 373 containsNullKey = false; 374 key[n] = null; 375 final V oldValue = value[n]; 376 value[n] = null; 377 size--; 378 if (size < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) 379 rehash(n / 2); 380 return oldValue; 381 } 382 383 /** 384 * Puts the first key in keyArray with the first value in valueArray, then the second in each and so on. 385 * The entries are all appended to the end of the iteration order, unless a key was already present. Then, 386 * its value is changed at the existing position in the iteration order. 387 * If the lengths of the two arrays are not equal, this puts a number of entries equal to the lesser length. 388 * If either array is null, this returns without performing any changes. 389 * @param keyArray an array of K keys that should usually have the same length as valueArray 390 * @param valueArray an array of V values that should usually have the same length as keyArray 391 */ 392 public void putAll(final K[] keyArray, final V[] valueArray) 393 { 394 if(keyArray == null || valueArray == null) 395 return; 396 for (int i = 0; i < keyArray.length && i < valueArray.length; i++) 397 put(keyArray[i], valueArray[i]); 398 399 } 400 401 /** 402 * Puts all key-value pairs in the Map m into this OrderedMap. 403 * The entries are all appended to the end of the iteration order, unless a key was already present. Then, 404 * its value is changed at the existing position in the iteration order. This can take any kind of Map, 405 * including unordered HashMap objects; if the Map does not have stable ordering, the order in which entries 406 * will be appended is not stable either. For this reason, OrderedMap, LinkedHashMap, and TreeMap (or other 407 * SortedMap implementations) will work best when order matters. 408 * @param m a Map that should have the same or compatible K key and V value types; OrderedMap and TreeMap work best 409 */ 410 public void putAll(Map<? extends K, ? extends V> m) { 411 if (f <= .5) 412 ensureCapacity(m.size()); // The resulting map will be sized for 413 // m.size() elements 414 else 415 tryCapacity(size() + m.size()); // The resulting map will be 416 int n = m.size(); 417 final Iterator<? extends Entry<? extends K, ? extends V>> i = m 418 .entrySet().iterator(); 419 Entry<? extends K, ? extends V> e; 420 while (n-- != 0) { 421 e = i.next(); 422 put(e.getKey(), e.getValue()); 423 } 424 } 425 private int insert(final K k, final V v) { 426 int pos; 427 if (k == null) { 428 if (containsNullKey) 429 return n; 430 containsNullKey = true; 431 pos = n; 432 } else { 433 K curr; 434 final K[] key = this.key; 435 // The starting point. 436 if ((curr = key[pos = (hasher.hash(k)) & mask]) != null) { 437 if (hasher.areEqual(curr, k)) 438 return pos; 439 while ((curr = key[pos = (pos + 1) & mask]) != null) 440 if (hasher.areEqual(curr, k)) 441 return pos; 442 } 443 } 444 key[pos] = k; 445 value[pos] = v; 446 if (size++ >= maxFill) 447 rehash(arraySize(size + 1, f)); 448 return -1; 449 } 450 public V put(final K k, final V v) { 451 final int pos = insert(k, v); 452 if (pos < 0) 453 return defRetValue; 454 final V oldValue = value[pos]; 455 value[pos] = v; 456 return oldValue; 457 } 458 /** 459 * Shifts left entries with the specified hash code, starting at the 460 * specified position, and empties the resulting free entry. 461 * 462 * @param pos 463 * a starting position. 464 */ 465 protected final void shiftKeys(int pos) { 466 // Shift entries with the same hash. 467 int last, slot; 468 K curr; 469 final K[] key = this.key; 470 for (;;) { 471 pos = ((last = pos) + 1) & mask; 472 for (;;) { 473 if ((curr = key[pos]) == null) { 474 key[last] = null; 475 value[last] = null; 476 return; 477 } 478 slot = (hasher.hash(curr)) 479 & mask; 480 if (last <= pos ? last >= slot || slot > pos : last >= slot 481 && slot > pos) 482 break; 483 pos = (pos + 1) & mask; 484 } 485 key[last] = curr; 486 value[last] = value[pos]; 487 } 488 } 489 public V remove(final Object k) { 490 if (k == null) { 491 if (containsNullKey) 492 return removeNullEntry(); 493 return defRetValue; 494 } 495 K curr; 496 final K[] key = this.key; 497 int pos; 498 // The starting point. 499 if ((curr = key[pos = (hasher.hash(k)) & mask]) == null) 500 return defRetValue; 501 if (hasher.areEqual(k, curr)) 502 return removeEntry(pos); 503 while (true) { 504 if ((curr = key[pos = (pos + 1) & mask]) == null) 505 return defRetValue; 506 if (hasher.areEqual(k, curr)) 507 return removeEntry(pos); 508 } 509 } 510 private V setValue(final int pos, final V v) { 511 final V oldValue = value[pos]; 512 value[pos] = v; 513 return oldValue; 514 } 515 public V get(final Object k) { 516 if (k == null) 517 return containsNullKey ? value[n] : defRetValue; 518 K curr; 519 final K[] key = this.key; 520 int pos; 521 // The starting point. 522 if ((curr = key[pos = (hasher.hash(k)) & mask]) == null) 523 return defRetValue; 524 if (hasher.areEqual(k, curr)) 525 return value[pos]; 526 // There's always an unused entry. 527 while (true) { 528 if ((curr = key[pos = (pos + 1) & mask]) == null) 529 return defRetValue; 530 if (hasher.areEqual(k, curr)) 531 return value[pos]; 532 } 533 } 534 535 536 public V getOrDefault(final Object k, final V defaultValue) { 537 if (k == null) 538 return containsNullKey ? value[n] : defaultValue; 539 K curr; 540 final K[] key = this.key; 541 int pos; 542 // The starting point. 543 if ((curr = key[pos = (hasher.hash(k)) & mask]) == null) 544 return defaultValue; 545 if (hasher.areEqual(k, curr)) 546 return value[pos]; 547 // There's always an unused entry. 548 while (true) { 549 if ((curr = key[pos = (pos + 1) & mask]) == null) 550 return defaultValue; 551 if (hasher.areEqual(k, curr)) 552 return value[pos]; 553 } 554 } 555 556 protected int positionOf(final Object k) { 557 if (k == null) 558 { 559 if(containsNullKey) 560 return n; 561 else 562 return -1; 563 } 564 K curr; 565 final K[] key = this.key; 566 int pos; 567 // The starting point. 568 if ((curr = key[pos = (hasher.hash(k)) & mask]) == null) 569 return -1; 570 if (hasher.areEqual(k, curr)) 571 return pos; 572 // There's always an unused entry. 573 while (true) { 574 if ((curr = key[pos = pos + 1 & mask]) == null) 575 return -1; 576 if (hasher.areEqual(k, curr)) 577 return pos; 578 } 579 } 580 581 public boolean containsKey(final Object k) { 582 if (k == null) 583 return containsNullKey; 584 K curr; 585 final K[] key = this.key; 586 int pos; 587 // The starting point. 588 if ((curr = key[pos = (hasher.hash(k)) & mask]) == null) 589 return false; 590 if (hasher.areEqual(k, curr)) 591 return true; 592 // There's always an unused entry. 593 while (true) { 594 if ((curr = key[pos = (pos + 1) & mask]) == null) 595 return false; 596 if (hasher.areEqual(k, curr)) 597 return true; 598 } 599 } 600 public boolean containsValue(final Object v) { 601 final V[] value = this.value; 602 final K[] key = this.key; 603 if (containsNullKey 604 && (value[n] == null ? v == null : value[n].equals(v))) 605 return true; 606 for (int i = n; i-- != 0;) 607 if (key[i] != null 608 && (value[i] == null ? v == null : value[i].equals(v))) 609 return true; 610 return false; 611 } 612 /* 613 * Removes all elements from this map. 614 * 615 * <P>To increase object reuse, this method does not change the table size. 616 * If you want to reduce the table size, you must use {@link #trim()}. 617 */ 618 public void clear() { 619 if (size == 0) 620 return; 621 size = 0; 622 containsNullKey = false; 623 Arrays.fill(key, null); 624 Arrays.fill(value, null); 625 } 626 627 public int size() { 628 return size; 629 } 630 631 public boolean isEmpty() { 632 return size == 0; 633 } 634 635 /** 636 * The entry class for a OrderedMap does not record key and value, but rather the position in the hash table of the corresponding entry. This is necessary so that calls to 637 * {@link Entry#setValue(Object)} are reflected in the map 638 */ 639 final class MapEntry implements Entry<K, V> { 640 // The table index this entry refers to, or -1 if this entry has been 641 // deleted. 642 int index; 643 MapEntry(final int index) { 644 this.index = index; 645 } 646 MapEntry() { 647 } 648 public K getKey() { 649 return key[index]; 650 } 651 public V getValue() { 652 return value[index]; 653 } 654 public V setValue(final V v) { 655 final V oldValue = value[index]; 656 value[index] = v; 657 return oldValue; 658 } 659 @SuppressWarnings("unchecked") 660 public boolean equals(final Object o) { 661 if (!(o instanceof Map.Entry)) 662 return false; 663 Entry<K, V> e = (Entry<K, V>) o; 664 return (key[index] == null 665 ? e.getKey() == null 666 : hasher.areEqual(key[index], e.getKey())) 667 && (value[index] == null 668 ? e.getValue() == null 669 : value[index].equals(e.getValue())); 670 } 671 public int hashCode() { 672 return hasher.hash(key[index]) 673 ^ (value[index] == null ? 0 : value[index].hashCode()); 674 } 675 @Override 676 public String toString() { 677 return key[index] + "=>" + value[index]; 678 } 679 } 680 681 /** 682 * An iterator over a hash map. 683 */ 684 private class MapIterator { 685 /** 686 * The index of the last entry returned, if positive or zero; initially, {@link #n}. If negative, the last 687 * <p> 688 * entry returned was that of the key of index {@code - pos - 1} from the {@link #wrapped} list. 689 */ 690 int pos = n; 691 /** 692 * The index of the last entry that has been returned (more precisely, the value of {@link #pos} if {@link #pos} is positive, 693 * <p> 694 * or {@link Integer#MIN_VALUE} if {@link #pos} is negative). It is -1 if either 695 * <p> 696 * we did not return an entry yet, or the last returned entry has been removed. 697 */ 698 int last = -1; 699 /** 700 * A downward counter measuring how many entries must still be returned. 701 */ 702 int c = size; 703 /** 704 * A boolean telling us whether we should return the entry with the null key. 705 */ 706 boolean mustReturnNullKey = UnorderedMap.this.containsNullKey; 707 /** 708 * A lazily allocated list containing keys of entries that have wrapped around the table because of removals. 709 */ 710 ArrayList<K> wrapped; 711 712 public boolean hasNext() { 713 return c != 0; 714 } 715 716 public int nextEntry() { 717 if (!hasNext()) throw new NoSuchElementException(); 718 c--; 719 if (mustReturnNullKey) { 720 mustReturnNullKey = false; 721 return last = n; 722 } 723 final K[] key = UnorderedMap.this.key; 724 for (; ; ) { 725 if (--pos < 0) { 726 // We are just enumerating elements from the wrapped list. 727 last = Integer.MIN_VALUE; 728 final K k = wrapped.get(-pos - 1); 729 int p = hasher.hash(k) & mask; 730 while (!(hasher.areEqual(k, key[p]))) p = (p + 1) & mask; 731 return p; 732 } 733 if (!((key[pos]) == null)) return last = pos; 734 } 735 } 736 737 /** 738 * Shifts left entries with the specified hash code, starting at the specified position, 739 * <p> 740 * and empties the resulting free entry. 741 * 742 * @param pos a starting position. 743 */ 744 private void shiftKeys(int pos) { 745 // Shift entries with the same hash. 746 int last, slot; 747 K curr; 748 final K[] key = UnorderedMap.this.key; 749 for (; ; ) { 750 pos = ((last = pos) + 1) & mask; 751 for (; ; ) { 752 if (((curr = key[pos]) == null)) { 753 key[last] = (null); 754 value[last] = null; 755 return; 756 } 757 slot = (hasher.hash(curr)) & mask; 758 if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) break; 759 pos = (pos + 1) & mask; 760 } 761 if (pos < last) { // Wrapped entry. 762 if (wrapped == null) wrapped = new ArrayList<>(2); 763 wrapped.add(key[pos]); 764 } 765 key[last] = curr; 766 value[last] = value[pos]; 767 } 768 } 769 770 public void remove() { 771 if (last == -1) throw new IllegalStateException(); 772 if (last == n) { 773 containsNullKey = false; 774 key[n] = null; 775 value[n] = null; 776 } else if (pos >= 0) shiftKeys(last); 777 else { 778 // We're removing wrapped entries. 779 UnorderedMap.this.remove(wrapped.set(-pos - 1, null)); 780 last = -1; // Note that we must not decrement size 781 return; 782 } 783 size--; 784 last = -1; // You can no longer remove this entry. 785 } 786 787 public int skip(final int n) { 788 int i = n; 789 while (i-- != 0 && hasNext()) nextEntry(); 790 return n - i - 1; 791 } 792 } 793 794 private class EntryIterator extends MapIterator implements Iterator<Map.Entry<K, V>> { 795 private MapEntry entry; 796 797 public Map.Entry<K, V> next() { 798 return entry = new MapEntry(nextEntry()); 799 } 800 801 @Override 802 public void remove() { 803 super.remove(); 804 entry.index = -1; // You cannot use a deleted entry. 805 } 806 } 807 808 private final class MapEntrySet extends AbstractSet<Map.Entry<K, V>> { 809 public Iterator<Map.Entry<K, V>> iterator() { 810 return new EntryIterator(); 811 } 812 813 @SuppressWarnings("unchecked") 814 public boolean contains(final Object o) { 815 if (!(o instanceof Map.Entry)) return false; 816 final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; 817 final K k = ((K) e.getKey()); 818 final V v = ((V) e.getValue()); 819 if (hasher.areEqual(k, null)) 820 return UnorderedMap.this.containsNullKey && (value[n] == null ? v == null : value[n].equals(v)); 821 K curr; 822 final K[] key = UnorderedMap.this.key; 823 int pos; 824 // The starting point. 825 if (((curr = key[pos = hasher.hash(k) & mask]) == null)) 826 return false; 827 if (hasher.areEqual(k, curr)) return (value[pos] == null ? (v) == null : (value[pos]).equals(v)); 828 // There's always an unused entry. 829 while (true) { 830 if (((curr = key[pos = (pos + 1) & mask]) == null)) return false; 831 if (hasher.areEqual(k, curr)) 832 return (value[pos] == null ? v == null : value[pos].equals(v)); 833 } 834 } 835 836 @SuppressWarnings("unchecked") 837 @Override 838 public boolean remove(final Object o) { 839 if (!(o instanceof Map.Entry)) return false; 840 final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; 841 final K k = ((K) e.getKey()); 842 final V v = ((V) e.getValue()); 843 if ((hasher.areEqual(k, null))) { 844 if (containsNullKey && ((value[n]) == null ? (v) == null : (value[n]).equals(v))) { 845 removeNullEntry(); 846 return true; 847 } 848 return false; 849 } 850 K curr; 851 final K[] key = UnorderedMap.this.key; 852 int pos; 853 // The starting point. 854 if (((curr = key[pos = hasher.hash(k) & mask]) == null)) 855 return false; 856 if (hasher.areEqual(curr, k)) { 857 if (((value[pos]) == null ? (v) == null : (value[pos]).equals(v))) { 858 removeEntry(pos); 859 return true; 860 } 861 return false; 862 } 863 while (true) { 864 if (((curr = key[pos = (pos + 1) & mask]) == null)) return false; 865 if (hasher.areEqual(curr, k)) { 866 if (((value[pos]) == null ? (v) == null : (value[pos]).equals(v))) { 867 removeEntry(pos); 868 return true; 869 } 870 } 871 } 872 } 873 874 public int size() { 875 return size; 876 } 877 878 public void clear() { 879 UnorderedMap.this.clear(); 880 } 881 } 882 883 @Override 884 public Set<Entry<K, V>> entrySet() { 885 if (entries == null) entries = new MapEntrySet(); 886 return entries; 887 } 888 889 890 /** 891 * An iterator on keys. 892 * 893 * 894 * 895 * <P>We simply override the {@link java.util.ListIterator#next()}/{@link java.util.ListIterator#previous()} methods 896 * <p> 897 * (and possibly their type-specific counterparts) so that they return keys 898 * <p> 899 * instead of entries. 900 */ 901 private final class KeyIterator extends MapIterator implements Iterator<K> { 902 public KeyIterator() { 903 super(); 904 } 905 906 public K next() { 907 return key[nextEntry()]; 908 } 909 } 910 911 private final class KeySet extends AbstractSet<K> { 912 public Iterator<K> iterator() { 913 return new KeyIterator(); 914 } 915 916 public int size() { 917 return size; 918 } 919 920 public boolean contains(Object k) { 921 return containsKey(k); 922 } 923 924 public boolean rem(Object k) { 925 final int oldSize = size; 926 UnorderedMap.this.remove(k); 927 return size != oldSize; 928 } 929 930 public void clear() { 931 UnorderedMap.this.clear(); 932 } 933 } 934 935 public Set<K> keySet() { 936 if (keys == null) keys = new KeySet(); 937 return keys; 938 } 939 940 /** 941 * An iterator on values. 942 * <br> 943 * We simply override the {@link java.util.Iterator#next()} method so that it returns values instead of entries. 944 */ 945 private final class ValueIterator extends MapIterator implements Iterator<V> { 946 public ValueIterator() { 947 super(); 948 } 949 950 public V next() { 951 return value[nextEntry()]; 952 } 953 } 954 955 public final class ValueCollection extends AbstractCollection<V> implements Serializable 956 { 957 private static final long serialVersionUID = 0L; 958 public ValueIterator iterator() { 959 return new ValueIterator(); 960 } 961 public int size() { 962 return size; 963 } 964 public boolean contains(Object v) { 965 return containsValue(v); 966 } 967 public void clear() { 968 UnorderedMap.this.clear(); 969 } 970 } 971 public Collection<V> values() { 972 if (values == null) values = new ValueCollection(); 973 return values; 974 } 975 976 public ArrayList<V> valuesAsList() 977 { 978 ArrayList<V> ls = new ArrayList<>(size); 979 ValueIterator vi = new ValueIterator(); 980 while (vi.hasNext()) 981 ls.add(vi.next()); 982 return ls; 983 } 984 985 /** 986 * Rehashes the map, making the table as small as possible. 987 * <p> 988 * <P>This method rehashes the table to the smallest size satisfying the load factor. It can be used when the set will not be changed anymore, so to optimize access speed and size. 989 * <p> 990 * <P>If the table size is already the minimum possible, this method does nothing. 991 * 992 * @return true if there was enough memory to trim the map. 993 * @see #trim(int) 994 */ 995 public boolean trim() { 996 final int l = arraySize(size, f); 997 if (l >= n || size > maxFill(l, f)) return true; 998 try { 999 rehash(l); 1000 } catch (Exception cantDoIt) { 1001 return false; 1002 } 1003 return true; 1004 } 1005 1006 /** 1007 * Rehashes this map if the table is too large. 1008 * <p> 1009 * <P>Let <var>N</var> be the smallest table size that can hold <code>max(n,{@link #size()})</code> entries, still satisfying the load factor. If the current table size is smaller than or equal to 1010 * <var>N</var>, this method does nothing. Otherwise, it rehashes this map in a table of size <var>N</var>. 1011 * <p> 1012 * <P>This method is useful when reusing maps. {@linkplain #clear() Clearing a map} leaves the table size untouched. If you are reusing a map many times, you can call this method with a typical 1013 * size to avoid keeping around a very large table just because of a few large transient maps. 1014 * 1015 * @param n the threshold for the trimming. 1016 * @return true if there was enough memory to trim the map. 1017 * @see #trim() 1018 */ 1019 public boolean trim(final int n) { 1020 final int l = HashCommon.nextPowerOfTwo((int) Math.ceil(n / f)); 1021 if (l >= n || size > maxFill(l, f)) return true; 1022 try { 1023 rehash(l); 1024 } catch (Exception cantDoIt) { 1025 return false; 1026 } 1027 return true; 1028 } 1029 1030 /** 1031 * Rehashes the map. 1032 * 1033 * <P> 1034 * This method implements the basic rehashing strategy, and may be overriden 1035 * by subclasses implementing different rehashing strategies (e.g., 1036 * disk-based rehashing). However, you should not override this method 1037 * unless you understand the internal workings of this class. 1038 * 1039 * @param newN 1040 * the new size 1041 */ 1042 1043 @SuppressWarnings("unchecked") 1044 protected void rehash(final int newN) { 1045 final K[] key = this.key; 1046 final V[] value = this.value; 1047 final int mask = newN - 1; // Note that this is used by the hashing macro 1048 final K[] newKey = (K[]) new Object[newN + 1]; 1049 final V[] newValue = (V[]) new Object[newN + 1]; 1050 1051 int i = n, pos; 1052 for (int j = realSize(); j-- != 0; ) { 1053 while (((key[--i]) == null)) ; 1054 if (!((newKey[pos = hasher.hash(key[i]) & mask]) == null)) 1055 while (!((newKey[pos = (pos + 1) & mask]) == null)) ; 1056 newKey[pos] = key[i]; 1057 newValue[pos] = value[i]; 1058 } 1059 newValue[newN] = value[n]; 1060 n = newN; 1061 this.mask = mask; 1062 maxFill = maxFill(n, f); 1063 this.key = newKey; 1064 this.value = newValue; 1065 } 1066 /* 1067 @SuppressWarnings("unchecked") 1068 protected void rehash(final int newN) { 1069 final K key[] = this.key; 1070 final V value[] = this.value; 1071 final int mask = newN - 1; // Note that this is used by the hashing 1072 // macro 1073 final K newKey[] = (K[]) new Object[newN + 1]; 1074 final V newValue[] = (V[]) new Object[newN + 1]; 1075 int i = first, prev = -1, newPrev = -1, t, pos; 1076 final long link[] = this.link; 1077 final long newLink[] = new long[newN + 1]; 1078 first = -1; 1079 for (int j = size; j-- != 0;) { 1080 if (((key[i]) == null)) 1081 pos = newN; 1082 else { 1083 pos = (((key[i]).hashCode())) & mask; 1084 while (!((newKey[pos]) == null)) 1085 pos = (pos + 1) & mask; 1086 } 1087 newKey[pos] = key[i]; 1088 newValue[pos] = value[i]; 1089 if (prev != -1) { 1090 newLink[newPrev] ^= ((newLink[newPrev] ^ (pos & 0xFFFFFFFFL)) & 0xFFFFFFFFL); 1091 newLink[pos] ^= ((newLink[pos] ^ ((newPrev & 0xFFFFFFFFL) << 32)) & 0xFFFFFFFF00000000L); 1092 newPrev = pos; 1093 } else { 1094 newPrev = first = pos; 1095 // Special case of SET(newLink[ pos ], -1, -1); 1096 newLink[pos] = -1L; 1097 } 1098 t = i; 1099 i = (int) link[i]; 1100 prev = t; 1101 } 1102 this.link = newLink; 1103 this.last = newPrev; 1104 if (newPrev != -1) 1105 // Special case of SET_NEXT( newLink[ newPrev ], -1 ); 1106 newLink[newPrev] |= -1 & 0xFFFFFFFFL; 1107 n = newN; 1108 this.mask = mask; 1109 maxFill = maxFill(n, f); 1110 this.key = newKey; 1111 this.value = newValue; 1112 } 1113 */ 1114 /** 1115 * Returns a deep copy of this map. 1116 * 1117 * <P> 1118 * This method performs a deep copy of this OrderedMap; the data stored in the 1119 * map, however, is not cloned. Note that this makes a difference only for 1120 * object keys. 1121 * 1122 * @return a deep copy of this map. 1123 */ 1124 @SuppressWarnings("unchecked") 1125 @GwtIncompatible 1126 public UnorderedMap<K, V> clone() { 1127 UnorderedMap<K, V> c; 1128 try { 1129 c = new UnorderedMap<>(hasher); 1130 c.key = (K[]) new Object[n + 1]; 1131 System.arraycopy(key, 0, c.key, 0, n + 1); 1132 c.value = (V[]) new Object[n + 1]; 1133 System.arraycopy(value, 0, c.value, 0, n + 1); 1134 return c; 1135 } catch (Exception cantHappen) { 1136 throw new UnsupportedOperationException(cantHappen + (cantHappen.getMessage() != null ? 1137 "; " + cantHappen.getMessage() : "")); 1138 } 1139 } 1140 /** 1141 * Returns a hash code for this map. 1142 * 1143 * This method overrides the generic method provided by the superclass. 1144 * Since <code>equals()</code> is not overriden, it is important that the 1145 * value returned by this method is the same value as the one returned by 1146 * the overriden method. 1147 * 1148 * @return a hash code for this map. 1149 */ 1150 public int hashCode() { 1151 int h = 0; 1152 for (int j = realSize(), i = 0, t = 0; j-- != 0;) { 1153 while (key[i] == null) 1154 i++; 1155 if (this != key[i]) 1156 t = hasher.hash(key[i]); 1157 if (this != value[i]) 1158 t ^= value[i] == null ? 0 : value[i].hashCode(); 1159 h += t; 1160 i++; 1161 } 1162 // Zero / null keys have hash zero. 1163 if (containsNullKey) 1164 h += value[n] == null ? 0 : value[n].hashCode(); 1165 return h; 1166 } 1167 1168 public long hash64() 1169 { 1170 return 31L * (31L * CrossHash.hash64(key) + CrossHash.hash64(value)) + size; 1171 } 1172 /** 1173 * Returns the maximum number of entries that can be filled before rehashing. 1174 * 1175 * @param n the size of the backing array. 1176 * @param f the load factor. 1177 * @return the maximum number of entries before rehashing. 1178 */ 1179 public static int maxFill(final int n, final float f) { 1180 /* We must guarantee that there is always at least 1181 * one free entry (even with pathological load factors). */ 1182 return Math.min((int)(n * f + 0.99999994f), n - 1); 1183 } 1184 1185 /** 1186 * Returns the least power of two smaller than or equal to 2<sup>30</sup> and larger than or equal to <code>Math.ceil( expected / f )</code>. 1187 *re 1188 * @param expected the expected number of elements in a hash table. 1189 * @param f the load factor. 1190 * @return the minimum possible size for a backing array. 1191 * @throws IllegalArgumentException if the necessary size is larger than 2<sup>30</sup>. 1192 */ 1193 public static int arraySize(final int expected, final float f) { 1194 final long s = Math.max(2, HashCommon.nextPowerOfTwo((long) Math.ceil(expected / f))); 1195 if (s > (1 << 30)) 1196 throw new IllegalArgumentException("Too large (" + expected + " expected elements with load factor " + f + ")"); 1197 return (int) s; 1198 } 1199 1200 /** 1201 * Unwraps an iterator into an array starting at a given offset for a given number of elements. 1202 * <p> 1203 * <P>This method iterates over the given type-specific iterator and stores the elements returned, up to a maximum of <code>length</code>, in the given array starting at <code>offset</code>. The 1204 * number of actually unwrapped elements is returned (it may be less than <code>max</code> if the iterator emits less than <code>max</code> elements). 1205 * 1206 * @param i a type-specific iterator. 1207 * @param array an array to contain the output of the iterator. 1208 * @param offset the first element of the array to be returned. 1209 * @param max the maximum number of elements to unwrap. 1210 * @return the number of elements unwrapped. 1211 */ 1212 private int unwrap(final ValueIterator i, final Object[] array, int offset, final int max) { 1213 if (max < 0) throw new IllegalArgumentException("The maximum number of elements (" + max + ") is negative"); 1214 if (offset < 0 || offset + max > array.length) throw new IllegalArgumentException(); 1215 int j = max; 1216 while (j-- != 0 && i.hasNext()) 1217 array[offset++] = i.next(); 1218 return max - j - 1; 1219 } 1220 1221 /** 1222 * Unwraps an iterator into an array. 1223 * <p> 1224 * <P>This method iterates over the given type-specific iterator and stores the elements returned in the given array. The iteration will stop when the iterator has no more elements or when the end 1225 * of the array has been reached. 1226 * 1227 * @param i a type-specific iterator. 1228 * @param array an array to contain the output of the iterator. 1229 * @return the number of elements unwrapped. 1230 */ 1231 private int unwrap(final ValueIterator i, final Object[] array) { 1232 return unwrap(i, array, 0, array.length); 1233 } 1234 1235 1236 /** Unwraps an iterator into an array starting at a given offset for a given number of elements. 1237 * 1238 * <P>This method iterates over the given type-specific iterator and stores the elements returned, up to a maximum of <code>length</code>, in the given array starting at <code>offset</code>. The 1239 * number of actually unwrapped elements is returned (it may be less than <code>max</code> if the iterator emits less than <code>max</code> elements). 1240 * 1241 * @param i a type-specific iterator. 1242 * @param array an array to contain the output of the iterator. 1243 * @param offset the first element of the array to be returned. 1244 * @param max the maximum number of elements to unwrap. 1245 * @return the number of elements unwrapped. */ 1246 private static <K> int objectUnwrap(final Iterator<? extends K> i, final K[] array, int offset, final int max ) { 1247 if ( max < 0 ) throw new IllegalArgumentException( "The maximum number of elements (" + max + ") is negative" ); 1248 if ( offset < 0 || offset + max > array.length ) throw new IllegalArgumentException(); 1249 int j = max; 1250 while ( j-- != 0 && i.hasNext() ) 1251 array[ offset++ ] = i.next(); 1252 return max - j - 1; 1253 } 1254 1255 /** Unwraps an iterator into an array. 1256 * 1257 * <P>This method iterates over the given type-specific iterator and stores the elements returned in the given array. The iteration will stop when the iterator has no more elements or when the end 1258 * of the array has been reached. 1259 * 1260 * @param i a type-specific iterator. 1261 * @param array an array to contain the output of the iterator. 1262 * @return the number of elements unwrapped. */ 1263 private static <K> int objectUnwrap(final Iterator<? extends K> i, final K[] array) { 1264 return objectUnwrap(i, array, 0, array.length ); 1265 } 1266 1267 @Override 1268 public String toString() { 1269 final StringBuilder s = new StringBuilder(); 1270 final Iterator<Map.Entry<K, V>> i = entrySet().iterator(); 1271 int n = size(); 1272 Map.Entry <K,V> e; 1273 boolean first = true; 1274 s.append("UnorderedMap {"); 1275 while(n-- != 0) { 1276 if (first) first = false; 1277 else s.append(", "); 1278 e = i.next(); 1279 if (this == e.getKey()) s.append("(this map)"); else 1280 s.append(String.valueOf(e.getKey())); 1281 s.append("=>"); 1282 if (this == e.getValue()) s.append("(this map)"); else 1283 s.append(String.valueOf(e.getValue())); 1284 } 1285 s.append("}"); 1286 return s.toString(); 1287 } 1288 @Override 1289 public boolean equals(Object o) { 1290 if (o == this) 1291 return true; 1292 if (!(o instanceof Map)) 1293 return false; 1294 Map<?, ?> m = (Map<?, ?>) o; 1295 if (m.size() != size()) 1296 return false; 1297 return entrySet().containsAll(m.entrySet()); 1298 } 1299 1300 @GwtIncompatible 1301 private void writeObject(java.io.ObjectOutputStream s) 1302 throws java.io.IOException { 1303 final K[] key = this.key; 1304 final V[] value = this.value; 1305 final MapIterator i = new MapIterator(); 1306 s.defaultWriteObject(); 1307 for (int j = size, e; j-- != 0;) { 1308 e = i.nextEntry(); 1309 s.writeObject(key[e]); 1310 s.writeObject(value[e]); 1311 } 1312 } 1313 @GwtIncompatible 1314 @SuppressWarnings("unchecked") 1315 private void readObject(java.io.ObjectInputStream s) 1316 throws java.io.IOException, ClassNotFoundException { 1317 s.defaultReadObject(); 1318 n = arraySize(size, f); 1319 maxFill = maxFill(n, f); 1320 mask = n - 1; 1321 final K[] key = this.key = (K[]) new Object[n + 1]; 1322 final V[] value = this.value = (V[]) new Object[n + 1]; 1323 K k; 1324 V v; 1325 for (int i = size, pos; i-- != 0;) { 1326 k = (K) s.readObject(); 1327 v = (V) s.readObject(); 1328 if (k == null) { 1329 pos = n; 1330 containsNullKey = true; 1331 } else { 1332 pos = (hasher.hash(k)) 1333 & mask; 1334 while (key[pos] != null) 1335 pos = (pos + 1) & mask; 1336 } 1337 1338 key[pos] = k; 1339 value[pos] = v; 1340 } 1341 } 1342 1343 public List<V> getMany(Collection<K> keys) 1344 { 1345 if(keys == null) 1346 return new ArrayList<>(1); 1347 ArrayList<V> vals = new ArrayList<>(keys.size()); 1348 for(K k : keys) 1349 { 1350 vals.add(get(k)); 1351 } 1352 return vals; 1353 } 1354 1355 /** 1356 * If the specified key is not already associated with a value (or is mapped 1357 * to {@code null}) associates it with the given value and returns 1358 * {@code null}, else returns the current value. 1359 * 1360 * @param key key with which the specified value is to be associated 1361 * @param value value to be associated with the specified key 1362 * @return the previous value associated with the specified key, or 1363 * {@code null} if there was no mapping for the key. 1364 * (A {@code null} return can also indicate that the map 1365 * previously associated {@code null} with the key.) 1366 */ 1367 public V putIfAbsent(K key, V value) { 1368 V v = get(key); 1369 if(v == null) 1370 v = put(key, value); 1371 return v; 1372 } 1373 1374 /** 1375 * Removes the entry for the specified key only if it is currently 1376 * mapped to the specified value. 1377 * 1378 * @param key key with which the specified value is associated 1379 * @param value value expected to be associated with the specified key 1380 * @return {@code true} if the value was removed 1381 */ 1382 public boolean remove(Object key, Object value) { 1383 if (containsKey(key) && Objects.equals(get(key), value)) { 1384 remove(key); 1385 return true; 1386 } else 1387 return false; 1388 } 1389 1390 /** 1391 * Replaces the entry for the specified key only if currently 1392 * mapped to the specified value. The position in the iteration 1393 * order is retained. 1394 * 1395 * @param key key with which the specified value is associated 1396 * @param oldValue value expected to be associated with the specified key 1397 * @param newValue value to be associated with the specified key 1398 * @return {@code true} if the value was replaced 1399 */ 1400 public boolean replace(K key, V oldValue, V newValue) { 1401 if (containsKey(key) && Objects.equals(get(key), oldValue)) { 1402 put(key, newValue); 1403 return true; 1404 } else 1405 return false; 1406 } 1407 1408 /** 1409 * Replaces the entry for the specified key only if it is 1410 * currently mapped to some value. Preserves the existing key's 1411 * position in the iteration order. 1412 * 1413 * @param key key with which the specified value is associated 1414 * @param value value to be associated with the specified key 1415 * @return the previous value associated with the specified key, or 1416 * {@code null} if there was no mapping for the key. 1417 * (A {@code null} return can also indicate that the map 1418 * previously associated {@code null} with the key.) 1419 */ 1420 public V replace(K key, V value) { 1421 if (containsKey(key)) { 1422 return put(key, value); 1423 } else 1424 return null; 1425 } 1426 /** 1427 * Given alternating key and value arguments in pairs, puts each key-value pair into this OrderedMap as if by 1428 * calling {@link #put(Object, Object)} repeatedly for each pair. This mimics the parameter syntax used for 1429 * {@link #makeMap(Object, Object, Object...)}, and can be used to retain that style of insertion after an 1430 * OrderedMap has been instantiated. 1431 * @param k0 the first key to add 1432 * @param v0 the first value to add 1433 * @param rest an array or vararg of keys and values in pairs; should contain alternating K, V, K, V... elements 1434 * @return this, after adding all viable key-value pairs given 1435 */ 1436 @SuppressWarnings("unchecked") 1437 public UnorderedMap<K, V> putPairs(K k0, V v0, Object... rest) 1438 { 1439 if(rest == null || rest.length == 0) 1440 { 1441 put(k0, v0); 1442 return this; 1443 } 1444 put(k0, v0); 1445 1446 for (int i = 0; i < rest.length - 1; i+=2) { 1447 try { 1448 put((K) rest[i], (V) rest[i + 1]); 1449 }catch (ClassCastException ignored) { 1450 } 1451 } 1452 return this; 1453 } 1454 1455 /** 1456 * Makes an OrderedMap (OM) with the given load factor (which should be between 0.1 and 0.9), key and value types 1457 * inferred from the types of k0 and v0, and considers all remaining parameters key-value pairs, casting the Objects 1458 * at positions 0, 2, 4... etc. to K and the objects at positions 1, 3, 5... etc. to V. If rest has an odd-number 1459 * length, then it discards the last item. If any pair of items in rest cannot be cast to the correct type of K or 1460 * V, then this inserts nothing for that pair. This is similar to the makeOM method in the Maker class, but does not 1461 * allow setting the load factor (since that extra parameter can muddle how javac figures out which generic types 1462 * the map should use), nor does it log debug information if a cast fails. The result should be the same otherwise. 1463 * <br> 1464 * This is named makeMap to indicate that it expects key and value parameters, unlike a Set or List. This convention 1465 * may be extended to other data structures that also have static methods for instantiation. 1466 * @param k0 the first key; used to infer the types of other keys if generic parameters aren't specified. 1467 * @param v0 the first value; used to infer the types of other values if generic parameters aren't specified. 1468 * @param rest an array or vararg of keys and values in pairs; should contain alternating K, V, K, V... elements 1469 * @param <K> the type of keys in the returned OrderedMap; if not specified, will be inferred from k0 1470 * @param <V> the type of values in the returned OrderedMap; if not specified, will be inferred from v0 1471 * @return a freshly-made OrderedMap with K keys and V values, using k0, v0, and the contents of rest to fill it 1472 */ 1473 @SuppressWarnings("unchecked") 1474 public static <K, V> UnorderedMap<K, V> makeMap(K k0, V v0, Object... rest) 1475 { 1476 if(rest == null || rest.length == 0) 1477 { 1478 UnorderedMap<K, V> om = new UnorderedMap<>(2); 1479 om.put(k0, v0); 1480 return om; 1481 } 1482 UnorderedMap<K, V> om = new UnorderedMap<>(1 + (rest.length >> 1)); 1483 om.put(k0, v0); 1484 1485 for (int i = 0; i < rest.length - 1; i+=2) { 1486 try { 1487 om.put((K) rest[i], (V) rest[i + 1]); 1488 }catch (ClassCastException ignored) { 1489 } 1490 } 1491 return om; 1492 } 1493 1494 /** 1495 * Makes an empty OrderedMap (OM); needs key and value types to be specified in order to work. For an empty 1496 * OrderedMap with String keys and Coord values, you could use {@code Maker.<String, Coord>makeOM()}. Using 1497 * the new keyword is probably just as easy in this case; this method is provided for completeness relative to 1498 * makeMap() with 2 or more parameters. 1499 * @param <K> the type of keys in the returned OrderedMap; cannot be inferred and must be specified 1500 * @param <V> the type of values in the returned OrderedMap; cannot be inferred and must be specified 1501 * @return an empty OrderedMap with the given key and value types. 1502 */ 1503 public static <K, V> UnorderedMap<K, V> makeMap() 1504 { 1505 return new UnorderedMap<>(); 1506 } 1507 1508}