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 * An int-key and int-value insertion-ordered hash map with with a fast implementation, originally from fastutil as 025 * Object2ObjectLinkedOpenHashMap but modified (in {@link OrderedMap}) to support constant-time indexed access of keys, 026 * values, and entries, and reordering. Deletion is slower with this algorithm (O(n) because the array used to keep 027 * track of ordering and indexing only allows linear-time deletion, instead of a linked-list approach allowing 028 * constant-time deletion but not helping at all with indexed access), and insertion sometimes takes longer than an 029 * ordered map using a linked-list for order because rehashing is more expensive. The benefits from constant-time access 030 * by index are numerous, especially for games, since fetching a random element becomes O(1) instead of O(n), and the 031 * index can be used to store extra info for no cost. 032 * <br> 033 * 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 034 * 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 035 * process. 036 * <br> 037 * 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 038 * you reuse instances of this class. 039 * <br> 040 * Iterators generated by this map will enumerate pairs in the same order in which they have been added to the map (addition of pairs whose key is already present in the set does not change the 041 * iteration order). Note that this order has nothing in common with the natural order of the keys. The order is kept by means of a int-specialized list, {@link IntVLA}, and is modifiable with this 042 * class' {@link #reorder(int...)} and {@link #shuffle(IRNG)} methods, among other tools. It may be preferable to avoid instantiating an Iterator object and instead 043 * use a normal int-based for loop with {@link #getAt(int)} called in each iteration. Though this doesn't allow easy deletion of items during iteration, it may be the 044 * fastest way to iterate through an OrderedMap. 045 * <br> 046 * This class allows approximately constant-time lookup of keys or values by their index in the ordering, which can 047 * allow some novel usage of the data structure. {@link OrderedSet} can be used like a list of unique elements, keeping 048 * order like a list does but also allowing rapid checks for whether an item exists in the OrderedSet, and OrderedMap 049 * can be used like that but with values associated as well (where OrderedSet uses contains(), OrderedMap uses 050 * containsKey()). You can also set the key and value at a position with {@link #putAt(int, int, int)}, or alter 051 * the key while keeping its value and index the same with {@link #alter(int, int)}. Reordering works here too, 052 * both with completely random orders from {@link #shuffle(IRNG)} or with a previously-generated ordering from 053 * {@link #reorder(int...)} (you can produce such an ordering for a given size and reuse it across multiple Ordered data 054 * structures with {@link IRNG#randomOrdering(int)}). Note that putAt() and {@link #removeAt(int)} do not run in constant 055 * time, and depending on the point of insertion/removal, they are likely to run in linear time (but also note that most 056 * insertion-ordered Maps and Sets don't allow insertion or removal at anywhere but the beginning or end of the order). 057 * <br> 058 * This doesn't allow custom IHashers because IHasher expects an Object to hash, and that would box the keys every time. 059 * <br> 060 * Thank you, Sebastiano Vigna, for making FastUtil available to the public with such high quality. 061 * <br> 062 * See https://github.com/vigna/fastutil for the original library. 063 * @author Sebastiano Vigna (responsible for all the hard parts) 064 * @author Tommy Ettinger (mostly responsible for squashing several layers of parent classes into one monster class) 065 */ 066public class IntIntOrderedMap implements Serializable, Cloneable { 067 private static final long serialVersionUID = 0L; 068 /** 069 * The array of keys. 070 */ 071 protected int[] key; 072 /** 073 * The array of values. 074 */ 075 protected int[] value; 076 /** 077 * The mask for wrapping a position counter. 078 */ 079 protected int mask; 080 /** 081 * Whether this set contains the key zero. 082 */ 083 protected boolean containsNullKey; 084 /** 085 * An IntVLA (variable-length int sequence) that stores the positions in the key array of specific keys, with the 086 * positions in insertion order. The order can be changed with {@link #reorder(int...)} and other methods. 087 */ 088 protected IntVLA order; 089 /** 090 * The current table size. 091 */ 092 protected int n; 093 /** 094 * Threshold after which we rehash. It must be the table size times {@link #f}. 095 */ 096 protected int maxFill; 097 /** 098 * Number of entries in the set (including the key zero, if present). 099 */ 100 protected int size; 101 /** 102 * The acceptable load factor. 103 */ 104 public final float f; 105 /** 106 * Cached set of entries. 107 */ 108 protected volatile MapEntrySet entries; 109 /** 110 * Cached set of keys. 111 */ 112 protected volatile KeySet keys; 113 /** 114 * Cached collection of values. 115 */ 116 protected volatile ValueCollection values; 117 /** 118 * Default return value. 119 */ 120 protected int defRetValue = -1; 121 122 /** 123 * The initial default size of a hash table. 124 */ 125 public static final int DEFAULT_INITIAL_SIZE = 16; 126 /** 127 * The default load factor of a hash table. 128 */ 129 public static final float DEFAULT_LOAD_FACTOR = .25f; // .1875f; // .75f; 130 /** 131 * The load factor for a (usually small) table that is meant to be particularly fast. 132 */ 133 public static final float FAST_LOAD_FACTOR = .5f; 134 /** 135 * The load factor for a (usually very small) table that is meant to be extremely fast. 136 */ 137 public static final float VERY_FAST_LOAD_FACTOR = .25f; 138 139 public void defaultReturnValue(final int rv) { 140 defRetValue = rv; 141 } 142 143 public int defaultReturnValue() { 144 return defRetValue; 145 } 146 147 /** 148 * Creates a new OrderedMap. 149 * <p> 150 * <p>The actual table size will be the least power of two greater than <code>expected</code>/<code>f</code>. 151 * 152 * @param expected the expected number of elements in the hash set. 153 * @param f the load factor. 154 */ 155 156 public IntIntOrderedMap(final int expected, final float f) { 157 if (f <= 0 || f > 1) 158 throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than or equal to 1"); 159 if (expected < 0) throw new IllegalArgumentException("The expected number of elements must be nonnegative"); 160 this.f = f; 161 n = arraySize(expected, f); 162 mask = n - 1; 163 maxFill = maxFill(n, f); 164 key = new int[n + 1]; 165 value = new int[n + 1]; 166 //link = new long[n + 1]; 167 order = new IntVLA(expected); 168 } 169 170 /** 171 * Creates a new OrderedMap with 0.75f as load factor. 172 * 173 * @param expected the expected number of elements in the OrderedMap. 174 */ 175 public IntIntOrderedMap(final int expected) { 176 this(expected, DEFAULT_LOAD_FACTOR); 177 } 178 179 /** 180 * Creates a new OrderedMap with initial expected 16 entries and 0.75f as load factor. 181 */ 182 public IntIntOrderedMap() { 183 this(DEFAULT_INITIAL_SIZE, DEFAULT_LOAD_FACTOR); 184 } 185 186 /** 187 * Creates a new OrderedMap copying a given one. 188 * 189 * @param m a {@link Map} to be copied into the new OrderedMap. 190 * @param f the load factor. 191 */ 192 public IntIntOrderedMap(final IntIntOrderedMap m, final float f) { 193 this(m.size(), f); 194 putAll(m); 195 } 196 197 /** 198 * Creates a new OrderedMap with 0.75f as load factor copying a given one. 199 * 200 * @param m a {@link Map} to be copied into the new OrderedMap. 201 */ 202 public IntIntOrderedMap(final IntIntOrderedMap m) { 203 this(m, m.f); 204 } 205 206 /** 207 * Creates a new OrderedMap using the elements of two parallel arrays. 208 * 209 * @param keyArray the array of keys of the new OrderedMap. 210 * @param valueArray the array of corresponding values in the new OrderedMap. 211 * @param f the load factor. 212 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 213 */ 214 public IntIntOrderedMap(final int[] keyArray, final int[] valueArray, final float f) { 215 this(keyArray.length, f); 216 if (keyArray.length != valueArray.length) 217 throw new IllegalArgumentException("The key array and the value array have different lengths (" + keyArray.length + " and " + valueArray.length + ")"); 218 for (int i = 0; i < keyArray.length; i++) 219 put(keyArray[i], valueArray[i]); 220 } 221 /** 222 * Creates a new OrderedMap using the elements of two parallel arrays. 223 * 224 * @param keyColl the collection of keys of the new OrderedMap. 225 * @param valueColl the collection of corresponding values in the new OrderedMap. 226 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 227 */ 228 public IntIntOrderedMap(final IntVLA keyColl, final IntVLA valueColl) { 229 this(keyColl, valueColl, DEFAULT_LOAD_FACTOR); 230 } 231 /** 232 * Creates a new OrderedMap using the elements of two parallel arrays. 233 * 234 * @param keyColl the collection of keys of the new OrderedMap. 235 * @param valueColl the collection of corresponding values in the new OrderedMap. 236 * @param f the load factor. 237 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 238 */ 239 public IntIntOrderedMap(final IntVLA keyColl, final IntVLA valueColl, final float f) { 240 this(keyColl.size, f); 241 if (keyColl.size != valueColl.size) 242 throw new IllegalArgumentException("The key array and the value array have different lengths (" + keyColl.size + " and " + valueColl.size + ")"); 243 final int len = keyColl.size; 244 for (int i = 0; i < len; i++) { 245 put(keyColl.get(i), valueColl.get(i)); 246 } 247 } 248 249 /** 250 * Creates a new OrderedMap with 0.75f as load factor using the elements of two parallel arrays. 251 * 252 * @param keyArray the array of keys of the new OrderedMap. 253 * @param valueArray the array of corresponding values in the new OrderedMap. 254 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 255 */ 256 public IntIntOrderedMap(final int[] keyArray, final int[] valueArray) { 257 this(keyArray, valueArray, DEFAULT_LOAD_FACTOR); 258 } 259 private int realSize() { 260 return containsNullKey ? size - 1 : size; 261 } 262 private void ensureCapacity(final int capacity) { 263 final int needed = arraySize(capacity, f); 264 if (needed > n) 265 rehash(needed); 266 } 267 private void tryCapacity(final long capacity) { 268 final int needed = (int) Math.min( 269 1 << 30, 270 Math.max(2, HashCommon.nextPowerOfTwo((long) Math.ceil(capacity 271 / f)))); 272 if (needed > n) 273 rehash(needed); 274 } 275 private int removeEntry(final int pos) { 276 final int oldValue = value[pos]; 277 size--; 278 fixOrder(pos); 279 shiftKeys(pos); 280 if (size < (maxFill >> 2) && n > DEFAULT_INITIAL_SIZE) 281 rehash(n >> 1); 282 return oldValue; 283 } 284 private int removeNullEntry() { 285 containsNullKey = false; 286 final int oldValue = value[n]; 287 size--; 288 fixOrder(n); 289 if (size < (maxFill >> 2) && n > DEFAULT_INITIAL_SIZE) 290 rehash(n >> 1); 291 return oldValue; 292 } 293 294 /** 295 * Puts the first key in keyArray with the first value in valueArray, then the second in each and so on. 296 * The entries are all appended to the end of the iteration order, unless a key was already present. Then, 297 * its value is changed at the existing position in the iteration order. 298 * If the lengths of the two arrays are not equal, this puts a number of entries equal to the lesser length. 299 * If either array is null, this returns without performing any changes. 300 * @param keyArray an array of int keys that should usually have the same length as valueArray 301 * @param valueArray an array of int values that should usually have the same length as keyArray 302 */ 303 public void putAll(final int[] keyArray, final int[] valueArray) 304 { 305 if(keyArray == null || valueArray == null) 306 return; 307 for (int i = 0; i < keyArray.length && i < valueArray.length; i++) 308 put(keyArray[i], valueArray[i]); 309 310 } 311 312 /** 313 * Puts all key-value pairs in the Map m into this OrderedMap. 314 * The entries are all appended to the end of the iteration order, unless a key was already present. Then, 315 * its value is changed at the existing position in the iteration order. This can take any kind of Map, 316 * including unordered HashMap objects; if the Map does not have stable ordering, the order in which entries 317 * will be appended is not stable either. For this reason, OrderedMap, LinkedHashMap, and TreeMap (or other 318 * SortedMap implementations) will work best when order matters. 319 * @param m an IntIntOrderedMap to add into this 320 */ 321 public void putAll(IntIntOrderedMap m) { 322 if (f <= .5) 323 ensureCapacity(m.size()); // The resulting map will be sized for m.size() elements 324 else 325 tryCapacity(size() + m.size()); // The resulting map will be size() + m.size() elements 326 int n = m.size(); 327 for (int i = 0; i < n; i++) { 328 put(m.keyAt(i), m.getAt(i)); 329 } 330 } 331 private int insert(final int k, final int v) { 332 int pos; 333 if (k == 0) { 334 if (containsNullKey) 335 return n; 336 containsNullKey = true; 337 pos = n; 338 } else { 339 int curr; 340 final int[] key = this.key; 341 // The starting point. 342 if ((curr = key[pos = (HashCommon.mix(k)) & mask]) != 0) { 343 if (curr == k) 344 return pos; 345 while ((curr = key[pos = (pos + 1) & mask]) != 0) 346 if (curr == k) 347 return pos; 348 } 349 } 350 key[pos] = k; 351 value[pos] = v; 352 order.add(pos); 353 if (size++ >= maxFill) 354 rehash(arraySize(size + 1, f)); 355 return -1; 356 } 357 private int insertAt(final int k, final int v, final int idx) { 358 int pos; 359 if (k == 0) { 360 if (containsNullKey) 361 { 362 fixOrder(n); 363 order.insert(idx, n); 364 return n; 365 } 366 containsNullKey = true; 367 pos = n; 368 } else { 369 int curr; 370 final int[] key = this.key; 371 // The starting point. 372 if ((curr = key[pos = (HashCommon.mix(k)) & mask]) != 0) { 373 if (curr == k) 374 { 375 fixOrder(pos); 376 order.insert(idx, pos); 377 return pos; 378 } 379 while ((curr = key[pos = (pos + 1) & mask]) != 0) 380 if (curr == k) 381 { 382 fixOrder(pos); 383 order.insert(idx, pos); 384 return pos; 385 } 386 } 387 } 388 key[pos] = k; 389 value[pos] = v; 390 order.insert(idx, pos); 391 if (size++ >= maxFill) 392 rehash(arraySize(size + 1, f)); 393 return -1; 394 } 395 public int put(final int k, final int v) { 396 final int pos = insert(k, v); 397 if (pos < 0) 398 return defRetValue; 399 final int oldValue = value[pos]; 400 value[pos] = v; 401 return oldValue; 402 } 403 public int putAt(final int k, final int v, final int idx) { 404 final int pos = insertAt(k, v, idx); 405 if (pos < 0) 406 return defRetValue; 407 final int oldValue = value[pos]; 408 value[pos] = v; 409 return oldValue; 410 } 411 /** 412 * Shifts left entries with the specified hash code, starting at the 413 * specified position, and empties the resulting free entry. 414 * 415 * @param pos 416 * a starting position. 417 */ 418 protected final void shiftKeys(int pos) { 419 // Shift entries with the same hash. 420 int last, slot; 421 int curr; 422 final int[] key = this.key; 423 for (;;) { 424 pos = ((last = pos) + 1) & mask; 425 for (;;) { 426 if ((curr = key[pos]) == 0) { 427 key[last] = 0; 428 return; 429 } 430 slot = (HashCommon.mix(curr)) 431 & mask; 432 if (last <= pos ? last >= slot || slot > pos : last >= slot 433 && slot > pos) 434 break; 435 pos = (pos + 1) & mask; 436 } 437 key[last] = curr; 438 value[last] = value[pos]; 439 fixOrder(pos, last); 440 } 441 } 442 public int remove(final int k) { 443 if (k == 0) { 444 if (containsNullKey) 445 return removeNullEntry(); 446 return defRetValue; 447 } 448 int curr; 449 final int[] key = this.key; 450 int pos; 451 // The starting point. 452 if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0) 453 return defRetValue; 454 if (k == curr) 455 return removeEntry(pos); 456 while (true) { 457 if ((curr = key[pos = (pos + 1) & mask]) == 0) 458 return defRetValue; 459 if (k == curr) 460 return removeEntry(pos); 461 } 462 } 463 private int setValue(final int pos, final int v) { 464 final int oldValue = value[pos]; 465 value[pos] = v; 466 return oldValue; 467 } 468 /** 469 * Removes the mapping associated with the first key in iteration order. 470 * 471 * @return the value previously associated with the first key in iteration 472 * order. 473 * @throws NoSuchElementException 474 * is this map is empty. 475 */ 476 public int removeFirst() { 477 return removeAt(0); 478 } 479 /** 480 * Removes the mapping associated with the last key in iteration order. 481 * 482 * @return the value previously associated with the last key in iteration 483 * order. 484 * @throws NoSuchElementException 485 * is this map is empty. 486 */ 487 public int removeLast() { 488 return removeAt(size-1); 489 } 490 public int get(final int k) { 491 if (k == 0) 492 return containsNullKey ? value[n] : defRetValue; 493 int curr; 494 final int[] key = this.key; 495 int pos; 496 // The starting point. 497 if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0) 498 return defRetValue; 499 if (k == curr) 500 return value[pos]; 501 // There's always an unused entry. 502 while (true) { 503 if ((curr = key[pos = (pos + 1) & mask]) == 0) 504 return defRetValue; 505 if (k == curr) 506 return value[pos]; 507 } 508 } 509 510 511 public int getOrDefault(final int k, final int defaultValue) { 512 if (k == 0) 513 return containsNullKey ? value[n] : defaultValue; 514 int curr; 515 final int[] key = this.key; 516 int pos; 517 // The starting point. 518 if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0) 519 return defaultValue; 520 if (k == curr) 521 return value[pos]; 522 // There's always an unused entry. 523 while (true) { 524 if ((curr = key[pos = (pos + 1) & mask]) == 0) 525 return defaultValue; 526 if (k == curr) 527 return value[pos]; 528 } 529 } 530 531 protected int positionOf(final int k) { 532 if (k == 0) 533 { 534 if(containsNullKey) 535 return n; 536 else 537 return -1; 538 } 539 int curr; 540 final int[] key = this.key; 541 int pos; 542 // The starting point. 543 if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0) 544 return -1; 545 if (k == curr) 546 return pos; 547 // There's always an unused entry. 548 while (true) { 549 if ((curr = key[pos = pos + 1 & mask]) == 0) 550 return -1; 551 if (k == curr) 552 return pos; 553 } 554 } 555 556 /** 557 * Gets the position in the ordering of the given key, though not as efficiently as some data structures can do it 558 * (e.g. {@link Arrangement} can access ordering position very quickly but doesn't store other values on its own). 559 * Returns a value that is at least 0 if it found k, or -1 if k was not present. 560 * @param k a key or possible key that this should find the index of 561 * @return the index of k, if present, or -1 if it is not present in this OrderedMap 562 */ 563 public int indexOf(final int k) 564 { 565 int pos = positionOf(k); 566 return (pos < 0) ? -1 : order.indexOf(pos); 567 } 568 569 /** 570 * Swaps the positions in the ordering for the given items, if they are both present. Returns true if the ordering 571 * changed as a result of this call, or false if it stayed the same (which can be because left or right was not 572 * present, or because left and right are the same reference (so swapping would do nothing)). 573 * @param left an item that should be present in this OrderedMap 574 * @param right an item that should be present in this OrderedMap 575 * @return true if this OrderedMap changed in ordering as a result of this call, or false otherwise 576 */ 577 public boolean swap(final int left, final int right) 578 { 579 if(left == right) return false; 580 int l = indexOf(left); 581 if(l < 0) return false; 582 int r = indexOf(right); 583 if(r < 0) return false; 584 order.swap(l, r); 585 return true; 586 } 587 /** 588 * Swaps the given indices in the ordering, if they are both valid int indices. Returns true if the ordering 589 * changed as a result of this call, or false if it stayed the same (which can be because left or right referred to 590 * an out-of-bounds index, or because left and right are equal (so swapping would do nothing)). 591 * @param left an index of an item in this OrderedMap, at least 0 and less than {@link #size()} 592 * @param right an index of an item in this OrderedMap, at least 0 and less than {@link #size()} 593 * @return true if this OrderedMap changed in ordering as a result of this call, or false otherwise 594 */ 595 public boolean swapIndices(final int left, final int right) 596 { 597 if(left < 0 || right < 0 || left >= order.size || right >= order.size || left == right) return false; 598 order.swap(left, right); 599 return true; 600 } 601 602 603 public boolean containsKey(final int k) { 604 if (k == 0) 605 return containsNullKey; 606 int curr; 607 final int[] key = this.key; 608 int pos; 609 // The starting point. 610 if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0) 611 return false; 612 if (k == curr) 613 return true; 614 // There's always an unused entry. 615 while (true) { 616 if ((curr = key[pos = (pos + 1) & mask]) == 0) 617 return false; 618 if (k == curr) 619 return true; 620 } 621 } 622 public boolean containsValue(final int v) { 623 final int[] value = this.value; 624 final int[] key = this.key; 625 if (containsNullKey && value[n] == v) 626 return true; 627 for (int i = n; i-- != 0;) 628 if (key[i] != 0 && value[i] == v) 629 return true; 630 return false; 631 } 632 /* 633 * Removes all elements from this map. 634 * 635 * <P>To increase object reuse, this method does not change the table size. 636 * If you want to reduce the table size, you must use {@link #trim()}. 637 */ 638 public void clear() { 639 if (size == 0) 640 return; 641 size = 0; 642 containsNullKey = false; 643 Arrays.fill(key, 0); 644 order.clear(); 645 } 646 647 public int size() { 648 return size; 649 } 650 651 public boolean isEmpty() { 652 return size == 0; 653 } 654 655 /** 656 * Looks up the key {@code k} in this map, remembers the associated value (which will be 657 * {@link #defaultReturnValue()} if k wasn't found), adds {@code increment} to the actual associated value in the 658 * map, and returns the remembered value. 659 * @param k a key to look up 660 * @param increment an int to add to the value associated with {@code k} 661 * @return the previous value associated with k, or {@link #defaultReturnValue()} if k wasn't found 662 */ 663 public int getAndIncrement(int k, int increment) { 664 if (k == 0) { 665 if (containsNullKey) { 666 int got = value[n]; 667 value[n] += increment; 668 return got; 669 } else { 670 value[n] = defRetValue + increment; 671 return defRetValue; 672 } 673 } 674 int curr; 675 final int[] key = this.key; 676 int pos; 677 // The starting point. 678 if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0) 679 { 680 put(k, defRetValue + increment); 681 return defRetValue; 682 } 683 if (k == curr) 684 { 685 int got = value[pos]; 686 value[pos] += increment; 687 return got; 688 } 689 // There's always an unused entry. 690 while (true) { 691 if ((curr = key[pos = (pos + 1) & mask]) == 0) 692 { 693 put(k, defRetValue + increment); 694 return defRetValue; 695 } 696 if (k == curr) 697 { 698 int got = value[pos]; 699 value[pos] += increment; 700 return got; 701 } 702 } 703 } 704 705 /** 706 * 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 707 * {@link MapEntry#setValue(int)} are reflected in the map 708 */ 709 public final class MapEntry { 710 // The table index this entry refers to, or -1 if this entry has been 711 // deleted. 712 int index; 713 MapEntry(final int index) { 714 this.index = index; 715 } 716 MapEntry() { 717 } 718 public int getKey() { 719 return key[index]; 720 } 721 public int getValue() { 722 return value[index]; 723 } 724 public int setValue(final int v) { 725 final int oldValue = value[index]; 726 value[index] = v; 727 return oldValue; 728 } 729 public boolean equals(final Object o) { 730 if (!(o instanceof MapEntry)) 731 return false; 732 MapEntry e = (MapEntry) o; 733 return (key[index] == e.getKey()) 734 && (value[index] == e.getValue()); 735 } 736 public int hashCode() { 737 return HashCommon.mix(key[index]) 738 ^ HashCommon.mix(HashCommon.mix(value[index])); 739 } 740 @Override 741 public String toString() { 742 return key[index] + "=>" + value[index]; 743 } 744 } 745 746 /** 747 * Modifies the ordering so that the given entry is removed. This method will complete in logarithmic time. 748 * 749 * @param i the index of an entry. 750 * @return the iteration-order index of the removed entry 751 */ 752 protected int fixOrder(final int i) { 753 if (size == 0) { 754 order.clear(); 755 return -1; 756 } 757 return order.removeValue(i); 758 } 759 760 /** 761 * Modifies the ordering for a shift from s to d. 762 * <br> 763 * This method will complete in logarithmic time or better. 764 * 765 * @param s the source position. 766 * @param d the destination position. 767 */ 768 protected void fixOrder(int s, int d) { 769 if(size == 0) 770 return; 771 if (size == 1 || order.items[0] == s) { 772 order.set(0, d); 773 } 774 else if (order.items[order.size-1] == s) { 775 order.set(order.size - 1, d); 776 } 777 else 778 { 779 order.set(order.indexOf(s), d); 780 } 781 } 782 783 /** 784 * Returns the first key of this map in iteration order. 785 * 786 * @return the first key in iteration order. 787 */ 788 public int firstKey() { 789 if (size == 0) 790 throw new NoSuchElementException(); 791 return key[order.items[0]]; 792 } 793 /** 794 * Returns the last key of this map in iteration order. 795 * 796 * @return the last key in iteration order. 797 */ 798 public int lastKey() { 799 if (size == 0) 800 throw new NoSuchElementException(); 801 return key[order.items[order.size-1]]; 802 } 803 /** 804 * A list iterator over a OrderedMap. 805 * 806 * <P> 807 * This class provides a list iterator over a OrderedMap. The 808 * constructor runs in constant time. 809 */ 810 private class MapIterator { 811 /** 812 * The entry that will be returned by the next call to 813 * {@link ListIterator#previous()} (or <code>null</code> if no 814 * previous entry exists). 815 */ 816 int prev = -1; 817 /** 818 * The entry that will be returned by the next call to 819 * {@link ListIterator#next()} (or <code>null</code> if no 820 * next entry exists). 821 */ 822 int next; 823 /** 824 * The last entry that was returned (or -1 if we did not iterate or used 825 * {@link Iterator#remove()}). 826 */ 827 int curr = -1; 828 /** 829 * The current index (in the sense of a {@link ListIterator}). 830 * Note that this value is not meaningful when this iterator has been 831 * created using the nonempty constructor. 832 */ 833 int index; 834 private MapIterator() { 835 next = size == 0 ? -1 : order.items[0]; 836 index = 0; 837 } 838 /* 839 private MapIterator(final K from) { 840 if (((from) == null)) { 841 if (containsNullKey) { 842 next = (int) link[n]; 843 prev = n; 844 return; 845 } else 846 throw new NoSuchElementException("The key null" 847 + " does not belong to this map."); 848 } 849 if (((key[last]) != null && (key[last]).equals(from))) { 850 prev = last; 851 index = size; 852 return; 853 } 854 // The starting point. 855 int pos = (((from).hashCode())) 856 & mask; 857 // There's always an unused entry. 858 while (!((key[pos]) == null)) { 859 if (((key[pos]).equals(from))) { 860 // Note: no valid index known. 861 next = (int) link[pos]; 862 prev = pos; 863 return; 864 } 865 pos = (pos + 1) & mask; 866 } 867 throw new NoSuchElementException("The key " + from 868 + " does not belong to this map."); 869 }*/ 870 public boolean hasNext() { 871 return next != -1; 872 } 873 public boolean hasPrevious() { 874 return prev != -1; 875 } 876 private void ensureIndexKnown() { 877 if (index >= 0) 878 return; 879 if (prev == -1) { 880 index = 0; 881 return; 882 } 883 if (next == -1) { 884 index = size; 885 return; 886 } 887 index = 0; 888 /*while (pos != prev) { 889 pos = (int) link[pos]; 890 index++; 891 }*/ 892 } 893 public int nextIndex() { 894 ensureIndexKnown(); 895 return index + 1; 896 } 897 public int previousIndex() { 898 ensureIndexKnown(); 899 return index - 1; 900 } 901 public int nextEntry() { 902 if (!hasNext()) 903 throw new NoSuchElementException(); 904 curr = next; 905 if(++index >= order.size) 906 next = -1; 907 else 908 next = order.get(index);//(int) link[curr]; 909 prev = curr; 910 return curr; 911 } 912 public int previousEntry() { 913 if (!hasPrevious()) 914 throw new NoSuchElementException(); 915 curr = prev; 916 if(--index < 1) 917 prev = -1; 918 else 919 prev = order.get(index - 1); 920 //prev = (int) (link[curr] >>> 32); 921 next = curr; 922 return curr; 923 } 924 public void remove() { 925 ensureIndexKnown(); 926 if (curr == -1) 927 throw new IllegalStateException(); 928 if (curr == prev) { 929 /* 930 * If the last operation was a next(), we are removing an entry 931 * that precedes the current index, and thus we must decrement 932 * it. 933 */ 934 if(--index >= 1) 935 prev = order.get(index - 1); //(int) (link[curr] >>> 32); 936 else 937 prev = -1; 938 } else { 939 if(index < order.size - 1) 940 next = order.get(index + 1); 941 else 942 next = -1; 943 } 944 order.removeIndex(index); 945 size--; 946 int last, slot, pos = curr; 947 curr = -1; 948 if (pos == n) { 949 containsNullKey = false; 950 } else { 951 int curr; 952 final int[] key = IntIntOrderedMap.this.key; 953 // We have to horribly duplicate the shiftKeys() code because we 954 // need to update next/prev. 955 for (;;) { 956 pos = ((last = pos) + 1) & mask; 957 for (;;) { 958 if ((curr = key[pos]) == 0) { 959 key[last] = 0; 960 return; 961 } 962 slot = (HashCommon.mix(curr)) & mask; 963 if (last <= pos 964 ? last >= slot || slot > pos 965 : last >= slot && slot > pos) 966 break; 967 pos = (pos + 1) & mask; 968 } 969 key[last] = curr; 970 value[last] = value[pos]; 971 if (next == pos) 972 next = last; 973 if (prev == pos) 974 prev = last; 975 fixOrder(pos, last); 976 } 977 } 978 } 979 public int skip(final int n) { 980 int i = n; 981 while (i-- != 0 && hasNext()) 982 nextEntry(); 983 return n - i - 1; 984 } 985 public int back(final int n) { 986 int i = n; 987 while (i-- != 0 && hasPrevious()) 988 previousEntry(); 989 return n - i - 1; 990 } 991 } 992 private class EntryIterator extends MapIterator 993 implements 994 Iterator<MapEntry>, Serializable { 995 private static final long serialVersionUID = 0L; 996 997 private MapEntry entry; 998 public EntryIterator() { 999 } 1000 public MapEntry next() { 1001 return entry = new MapEntry(nextEntry()); 1002 } 1003 public MapEntry previous() { 1004 return entry = new MapEntry(previousEntry()); 1005 } 1006 @Override 1007 public void remove() { 1008 super.remove(); 1009 entry.index = -1; // You cannot use a deleted entry. 1010 } 1011 } 1012 1013 public class FastEntryIterator extends MapIterator implements ListIterator<MapEntry>, Serializable { 1014 private static final long serialVersionUID = 0L; 1015 1016 final MapEntry entry = new MapEntry(); 1017 1018 public FastEntryIterator() { 1019 } 1020 public MapEntry next() { 1021 entry.index = nextEntry(); 1022 return entry; 1023 } 1024 public MapEntry previous() { 1025 entry.index = previousEntry(); 1026 return entry; 1027 } 1028 public void set(MapEntry ok) { 1029 throw new UnsupportedOperationException(); 1030 } 1031 public void add(MapEntry ok) { 1032 throw new UnsupportedOperationException(); 1033 } 1034 } 1035 public final class MapEntrySet 1036 implements Cloneable, SortedSet<MapEntry>, Set<MapEntry>, Serializable { 1037 private static final long serialVersionUID = 0L; 1038 public EntryIterator iterator() { 1039 return new EntryIterator(); 1040 } 1041 public Comparator<? super MapEntry> comparator() { 1042 return null; 1043 } 1044 public SortedSet<MapEntry> subSet( 1045 MapEntry fromElement, 1046 MapEntry toElement) { 1047 throw new UnsupportedOperationException(); 1048 } 1049 public SortedSet<MapEntry> headSet( 1050 MapEntry toElement) { 1051 throw new UnsupportedOperationException(); 1052 } 1053 public SortedSet<MapEntry> tailSet( 1054 MapEntry fromElement) { 1055 throw new UnsupportedOperationException(); 1056 } 1057 public MapEntry first() { 1058 if (size == 0) 1059 throw new NoSuchElementException(); 1060 return new MapEntry(order.items[0]); 1061 } 1062 public MapEntry last() { 1063 if (size == 0) 1064 throw new NoSuchElementException(); 1065 return new MapEntry(order.items[order.size-1]); 1066 } 1067 public boolean contains(final Object o) { 1068 if (!(o instanceof MapEntry)) 1069 return false; 1070 final MapEntry e = (MapEntry) o; 1071 final int k = e.getKey(); 1072 final int v = e.getValue(); 1073 if (k == 0) 1074 return containsNullKey && (value[n] == v); 1075 int curr; 1076 final int[] key = IntIntOrderedMap.this.key; 1077 int pos; 1078 // The starting point. 1079 if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0) 1080 return false; 1081 if (k == curr) 1082 return value[pos] == v; 1083 // There's always an unused entry. 1084 while (true) { 1085 if ((curr = key[pos = (pos + 1) & mask]) == 0) 1086 return false; 1087 if (k == curr) 1088 return value[pos] == v; 1089 } 1090 } 1091 public boolean remove(final Object o) { 1092 if (!(o instanceof MapEntry)) 1093 return false; 1094 final MapEntry e = (MapEntry) o; 1095 final int k = e.getKey(); 1096 final int v = e.getValue(); 1097 if (k == 0) { 1098 if (containsNullKey && value[n] == v) { 1099 removeNullEntry(); 1100 return true; 1101 } 1102 return false; 1103 } 1104 int curr; 1105 final int[] key = IntIntOrderedMap.this.key; 1106 int pos; 1107 // The starting point. 1108 if ((curr = key[pos = (HashCommon.mix(k)) & mask]) == 0) 1109 return false; 1110 if (curr == k) { 1111 if (value[pos] == v) { 1112 removeEntry(pos); 1113 return true; 1114 } 1115 return false; 1116 } 1117 while (true) { 1118 if ((curr = key[pos = (pos + 1) & mask]) == 0) 1119 return false; 1120 if (curr == k) { 1121 if (value[pos] == v) { 1122 removeEntry(pos); 1123 return true; 1124 } 1125 } 1126 } 1127 } 1128 public int size() { 1129 return size; 1130 } 1131 public void clear() { 1132 IntIntOrderedMap.this.clear(); 1133 } 1134 1135 public FastEntryIterator fastIterator() { 1136 return new FastEntryIterator(); 1137 } 1138 1139 @Override 1140 public boolean equals(final Object o) { 1141 if (o == this) 1142 return true; 1143 if (!(o instanceof Set)) 1144 return false; 1145 Set<?> s = (Set<?>) o; 1146 return s.size() == size() && containsAll(s); 1147 } 1148 1149 public Object[] toArray() { 1150 final Object[] a = new Object[size()]; 1151 objectUnwrap(iterator(), a); 1152 return a; 1153 } 1154 1155 @SuppressWarnings("unchecked") 1156 public <T> T[] toArray(T[] a) { 1157 if (a == null || a.length < size()) a = (T[]) new Object[size()]; 1158 objectUnwrap(iterator(), a); 1159 return a; 1160 } 1161 1162 /** 1163 * Unsupported. 1164 * 1165 * @param c ignored 1166 * @return nothing, throws UnsupportedOperationException 1167 * @throws UnsupportedOperationException always 1168 */ 1169 public boolean addAll(Collection<? extends MapEntry> c) { 1170 throw new UnsupportedOperationException("addAll not supported"); 1171 } 1172 1173 /** 1174 * Unsupported. 1175 * 1176 * @param k ignored 1177 * @return nothing, throws UnsupportedOperationException 1178 * @throws UnsupportedOperationException always 1179 */ 1180 public boolean add(MapEntry k) { 1181 throw new UnsupportedOperationException("add not supported"); 1182 } 1183 1184 /** 1185 * Checks whether this collection contains all elements from the given 1186 * collection. 1187 * 1188 * @param c a collection. 1189 * @return <code>true</code> if this collection contains all elements of the 1190 * argument. 1191 */ 1192 public boolean containsAll(Collection<?> c) { 1193 int n = c.size(); 1194 final Iterator<?> i = c.iterator(); 1195 while (n-- != 0) 1196 if (!contains(i.next())) 1197 return false; 1198 return true; 1199 } 1200 1201 /** 1202 * Retains in this collection only elements from the given collection. 1203 * 1204 * @param c a collection. 1205 * @return <code>true</code> if this collection changed as a result of the 1206 * call. 1207 */ 1208 public boolean retainAll(Collection<?> c) { 1209 boolean retVal = false; 1210 int n = size(); 1211 final Iterator<?> i = iterator(); 1212 while (n-- != 0) { 1213 if (!c.contains(i.next())) { 1214 i.remove(); 1215 retVal = true; 1216 } 1217 } 1218 return retVal; 1219 } 1220 1221 /** 1222 * Remove from this collection all elements in the given collection. If the 1223 * collection is an instance of this class, it uses faster iterators. 1224 * 1225 * @param c a collection. 1226 * @return <code>true</code> if this collection changed as a result of the 1227 * call. 1228 */ 1229 public boolean removeAll(Collection<?> c) { 1230 boolean retVal = false; 1231 int n = c.size(); 1232 final Iterator<?> i = c.iterator(); 1233 while (n-- != 0) 1234 if (remove(i.next())) 1235 retVal = true; 1236 return retVal; 1237 } 1238 1239 public boolean isEmpty() { 1240 return size() == 0; 1241 } 1242 1243 @Override 1244 public String toString() { 1245 final StringBuilder s = new StringBuilder(); 1246 final EntryIterator i = iterator(); 1247 int n = size(); 1248 MapEntry k; 1249 boolean first = true; 1250 s.append("{"); 1251 while (n-- != 0) { 1252 if (first) 1253 first = false; 1254 else 1255 s.append(", "); 1256 k = i.next(); 1257 s.append(key[k.index]).append("=>").append(value[k.index]); 1258 } 1259 s.append("}"); 1260 return s.toString(); 1261 } 1262 1263 } 1264 1265 public SortedSet<MapEntry> entrySet() { 1266 if (entries == null) entries = new MapEntrySet(); 1267 return entries; 1268 } 1269 1270 /** 1271 * An iterator on keys. 1272 * <p> 1273 * <P>We simply override the {@link ListIterator#next()}/{@link ListIterator#previous()} methods (and possibly their type-specific counterparts) so that they return keys 1274 * instead of entries. 1275 */ 1276 public final class KeyIterator extends MapIterator implements Iterator<Integer>, Serializable { 1277 private static final long serialVersionUID = 0L; 1278 public Integer previous() { 1279 return key[previousEntry()]; 1280 } 1281 public int previousInt() { 1282 return key[previousEntry()]; 1283 } 1284 public void set(Integer k) { 1285 throw new UnsupportedOperationException(); 1286 } 1287 public void add(Integer k) { 1288 throw new UnsupportedOperationException(); 1289 } 1290 public KeyIterator() {} 1291 public Integer next() { 1292 return key[nextEntry()]; 1293 } 1294 public int nextInt() { 1295 return key[nextEntry()]; 1296 } 1297 public void remove() { super.remove(); } 1298 } 1299 1300 public final class KeySet implements SortedSet<Integer>, Serializable { 1301 private static final long serialVersionUID = 0L; 1302 1303 public KeyIterator iterator() { 1304 return new KeyIterator(); 1305 } 1306 1307 public int size() { 1308 return size; 1309 } 1310 1311 public void clear() { 1312 IntIntOrderedMap.this.clear(); 1313 } 1314 1315 public Integer first() { 1316 if (size == 0) throw new NoSuchElementException(); 1317 return key[order.items[0]]; 1318 } 1319 1320 public Integer last() { 1321 if (size == 0) throw new NoSuchElementException(); 1322 return key[order.items[order.size-1]]; 1323 } 1324 1325 public Comparator<Integer> comparator() { 1326 return null; 1327 } 1328 1329 public final SortedSet<Integer> tailSet(Integer from) { 1330 throw new UnsupportedOperationException(); 1331 } 1332 1333 public final SortedSet<Integer> headSet(Integer to) { 1334 throw new UnsupportedOperationException(); 1335 } 1336 1337 public final SortedSet<Integer> subSet(Integer from, Integer to) { 1338 throw new UnsupportedOperationException(); 1339 } 1340 1341 @SuppressWarnings("unchecked") 1342 @Override 1343 public <T> T[] toArray(T[] a) { 1344 if (a == null || a.length < size()) a = (T[]) new Object[size()]; 1345 unwrap(iterator(), a); 1346 return a; 1347 } 1348 1349 /** 1350 * Always throws an UnsupportedOperationException 1351 */ 1352 public boolean remove(Object ok) { 1353 throw new UnsupportedOperationException("Cannot remove from the key set directly"); 1354 } 1355 1356 /** 1357 * Always throws an UnsupportedOperationException 1358 */ 1359 public boolean add(final Integer o) { 1360 throw new UnsupportedOperationException("Cannot add to the key set directly"); 1361 } 1362 1363 /** 1364 * Delegates to the corresponding type-specific method. 1365 */ 1366 public boolean contains(final Object o) { 1367 return o instanceof Integer && containsKey((Integer) o); 1368 } 1369 1370 /** 1371 * Checks whether this collection contains all elements from the given type-specific collection. 1372 * 1373 * @param c a type-specific collection. 1374 * @return <code>true</code> if this collection contains all elements of the argument. 1375 */ 1376 public boolean containsAll(Collection<?> c) { 1377 final Iterator<?> i = c.iterator(); 1378 int n = c.size(); 1379 while (n-- != 0) 1380 if (!contains(i.next())) return false; 1381 return true; 1382 } 1383 1384 /** 1385 * Retains in this collection only elements from the given type-specific collection. 1386 * 1387 * @param c a type-specific collection. 1388 * @return <code>true</code> if this collection changed as a result of the call. 1389 */ 1390 public boolean retainAll(Collection<?> c) { 1391 boolean retVal = false; 1392 int n = size(); 1393 final Iterator<?> i = iterator(); 1394 while (n-- != 0) { 1395 if (!c.contains(i.next())) { 1396 i.remove(); 1397 retVal = true; 1398 } 1399 } 1400 return retVal; 1401 } 1402 1403 /** 1404 * Remove from this collection all elements in the given type-specific collection. 1405 * 1406 * @param c a type-specific collection. 1407 * @return <code>true</code> if this collection changed as a result of the call. 1408 */ 1409 public boolean removeAll(Collection<?> c) { 1410 boolean retVal = false; 1411 int n = c.size(); 1412 final Iterator<?> i = c.iterator(); 1413 while (n-- != 0) 1414 if (remove(i.next())) retVal = true; 1415 return false; 1416 } 1417 1418 public Object[] toArray() { 1419 final Object[] a = new Object[size()]; 1420 objectUnwrap(iterator(), a); 1421 return a; 1422 } 1423 1424 /** 1425 * Adds all elements of the given collection to this collection. 1426 * 1427 * @param c a collection. 1428 * @return <code>true</code> if this collection changed as a result of the call. 1429 */ 1430 public boolean addAll(Collection<? extends Integer> c) { 1431 boolean retVal = false; 1432 final Iterator<? extends Integer> i = c.iterator(); 1433 int n = c.size(); 1434 while (n-- != 0) 1435 if (add(i.next())) retVal = true; 1436 return false; 1437 } 1438 1439 @Override 1440 public boolean equals(final Object o) { 1441 if (o == this) 1442 return true; 1443 if (!(o instanceof Set)) 1444 return false; 1445 Set<?> s = (Set<?>) o; 1446 if (s.size() != size()) 1447 return false; 1448 return containsAll(s); 1449 } 1450 /** 1451 * Unwraps an iterator into an array starting at a given offset for a given number of elements. 1452 * <p> 1453 * <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 1454 * 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). 1455 * 1456 * @param i a type-specific iterator. 1457 * @param array an array to contain the output of the iterator. 1458 * @param offset the first element of the array to be returned. 1459 * @param max the maximum number of elements to unwrap. 1460 * @return the number of elements unwrapped. 1461 */ 1462 public int unwrap(final KeyIterator i, final int[] array, int offset, final int max) { 1463 if (max < 0) throw new IllegalArgumentException("The maximum number of elements (" + max + ") is negative"); 1464 if (offset < 0 || offset + max > array.length) throw new IllegalArgumentException(); 1465 int j = max; 1466 while (j-- != 0 && i.hasNext()) 1467 array[offset++] = i.nextInt(); 1468 return max - j - 1; 1469 } 1470 /** 1471 * Unwraps an iterator into an array. 1472 * <p> 1473 * <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 1474 * of the array has been reached. 1475 * 1476 * @param i a type-specific iterator. 1477 * @param array an array to contain the output of the iterator. 1478 * @return the number of elements unwrapped. 1479 */ 1480 public int unwrap(final KeyIterator i, final int[] array) { 1481 return unwrap(i, array, 0, array.length); 1482 } 1483 public int[] toIntArray() { 1484 int[] a = new int[size()]; 1485 unwrap(iterator(), a); 1486 return a; 1487 } 1488 1489 public int[] toIntArray(int[] a) { 1490 if (a == null || a.length < size()) a = new int[size()]; 1491 unwrap(iterator(), a); 1492 return a; 1493 } 1494 1495 /** 1496 * Unwraps an iterator into an array starting at a given offset for a given number of elements. 1497 * <p> 1498 * <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 1499 * 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). 1500 * 1501 * @param i a type-specific iterator. 1502 * @param array an array to contain the output of the iterator. 1503 * @param offset the first element of the array to be returned. 1504 * @param max the maximum number of elements to unwrap. 1505 * @return the number of elements unwrapped. 1506 */ 1507 public int unwrap(final KeyIterator i, final Object[] array, int offset, final int max) { 1508 if (max < 0) throw new IllegalArgumentException("The maximum number of elements (" + max + ") is negative"); 1509 if (offset < 0 || offset + max > array.length) throw new IllegalArgumentException(); 1510 int j = max; 1511 while (j-- != 0 && i.hasNext()) 1512 array[offset++] = i.next(); 1513 return max - j - 1; 1514 } 1515 1516 /** 1517 * Unwraps an iterator into an array. 1518 * <p> 1519 * <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 1520 * of the array has been reached. 1521 * 1522 * @param i a type-specific iterator. 1523 * @param array an array to contain the output of the iterator. 1524 * @return the number of elements unwrapped. 1525 */ 1526 public int unwrap(final KeyIterator i, final Object[] array) { 1527 return unwrap(i, array, 0, array.length); 1528 } 1529 1530 public boolean isEmpty() { 1531 return size() == 0; 1532 } 1533 1534 @Override 1535 public String toString() { 1536 final StringBuilder s = new StringBuilder(); 1537 final KeyIterator i = iterator(); 1538 int n = size(); 1539 boolean first = true; 1540 s.append("{"); 1541 while (n-- != 0) { 1542 if (first) first = false; 1543 else s.append(", "); 1544 s.append(i.next()); 1545 } 1546 s.append("}"); 1547 return s.toString(); 1548 } 1549 } 1550 1551 public KeySet keySet() { 1552 if (keys == null) keys = new KeySet(); 1553 return keys; 1554 } 1555 1556 public OrderedSet<Integer> keysAsOrderedSet() 1557 { 1558 OrderedSet<Integer> os = new OrderedSet<>(size, f); 1559 for (int i = 0; i < size; i++) { 1560 os.add(keyAt(i)); 1561 } 1562 return os; 1563 } 1564 public int[] keysAsArray() { 1565 return keySet().toIntArray(); 1566 } 1567 1568 /** 1569 * An iterator on values. 1570 * <p> 1571 * <P>We simply override the {@link ListIterator#next()}/{@link ListIterator#previous()} methods (and possibly their type-specific counterparts) so that they return values 1572 * instead of entries. 1573 */ 1574 public final class ValueIterator extends MapIterator implements ListIterator<Integer>, Serializable { 1575 private static final long serialVersionUID = 0L; 1576 1577 public Integer previous() { 1578 return value[previousEntry()]; 1579 } 1580 public void set(Integer v) { 1581 throw new UnsupportedOperationException(); 1582 } 1583 public void add(Integer v) { 1584 throw new UnsupportedOperationException(); 1585 } 1586 public ValueIterator() {} 1587 public Integer next() { 1588 return value[nextEntry()]; 1589 } 1590 public void remove() { super.remove(); } 1591 } 1592 public final class ValueCollection extends AbstractCollection<Integer> implements Serializable 1593 { 1594 private static final long serialVersionUID = 0L; 1595 public ValueIterator iterator() { 1596 return new ValueIterator(); 1597 } 1598 public int size() { 1599 return size; 1600 } 1601 public boolean contains(Object v) { 1602 return v instanceof Integer && containsValue((Integer)v); 1603 } 1604 public void clear() { 1605 IntIntOrderedMap.this.clear(); 1606 } 1607 } 1608 public Collection<Integer> values() { 1609 if (values == null) values = new ValueCollection(); 1610 return values; 1611 } 1612 1613 public IntVLA valuesAsList() 1614 { 1615 IntVLA ls = new IntVLA(size); 1616 for (int i = 0; i < size; i++) { 1617 ls.add(getAt(i)); 1618 } 1619 return ls; 1620 } 1621 1622 /** 1623 * Rehashes the map, making the table as small as possible. 1624 * <p> 1625 * <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. 1626 * <p> 1627 * <P>If the table size is already the minimum possible, this method does nothing. 1628 * 1629 * @return true if there was enough memory to trim the map. 1630 * @see #trim(int) 1631 */ 1632 public boolean trim() { 1633 final int l = arraySize(size, f); 1634 if (l >= n || size > maxFill(l, f)) return true; 1635 try { 1636 rehash(l); 1637 } catch (Exception cantDoIt) { 1638 return false; 1639 } 1640 return true; 1641 } 1642 1643 /** 1644 * Rehashes this map if the table is too large. 1645 * <p> 1646 * <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 1647 * <var>N</var>, this method does nothing. Otherwise, it rehashes this map in a table of size <var>N</var>. 1648 * <p> 1649 * <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 1650 * size to avoid keeping around a very large table just because of a few large transient maps. 1651 * 1652 * @param n the threshold for the trimming. 1653 * @return true if there was enough memory to trim the map. 1654 * @see #trim() 1655 */ 1656 public boolean trim(final int n) { 1657 final int l = HashCommon.nextPowerOfTwo((int) Math.ceil(n / f)); 1658 if (l >= n || size > maxFill(l, f)) return true; 1659 try { 1660 rehash(l); 1661 } catch (Exception cantDoIt) { 1662 return false; 1663 } 1664 return true; 1665 } 1666 1667 /** 1668 * Rehashes the map. 1669 * 1670 * <P> 1671 * This method implements the basic rehashing strategy, and may be overriden 1672 * by subclasses implementing different rehashing strategies (e.g., 1673 * disk-based rehashing). However, you should not override this method 1674 * unless you understand the internal workings of this class. 1675 * 1676 * @param newN 1677 * the new size 1678 */ 1679 1680 protected void rehash(final int newN) { 1681 final int[] key = this.key; 1682 final int[] value = this.value; 1683 final int mask = newN - 1; // Note that this is used by the hashing macro 1684 final int[] newKey = new int[newN + 1]; 1685 final int[] newValue = new int[newN + 1]; 1686 final int sz = order.size; 1687 int k; 1688 int i, pos; 1689 final int[] oi = order.items; 1690 for (int q = 0; q < sz; q++) { 1691 i = oi[q]; 1692 if ((k = key[i]) == 0) 1693 pos = newN; 1694 else { 1695 pos = (HashCommon.mix(k)) & mask; 1696 while (newKey[pos] != 0) 1697 pos = (pos + 1) & mask; 1698 } 1699 newKey[pos] = k; 1700 newValue[pos] = value[i]; 1701 oi[q] = pos; 1702 } 1703 n = newN; 1704 this.mask = mask; 1705 maxFill = maxFill(n, f); 1706 this.key = newKey; 1707 this.value = newValue; 1708 } 1709 /* 1710 @SuppressWarnings("unchecked") 1711 protected void rehash(final int newN) { 1712 final K key[] = this.key; 1713 final V value[] = this.value; 1714 final int mask = newN - 1; // Note that this is used by the hashing 1715 // macro 1716 final K newKey[] = (K[]) new Object[newN + 1]; 1717 final V newValue[] = (V[]) new Object[newN + 1]; 1718 int i = first, prev = -1, newPrev = -1, t, pos; 1719 final long link[] = this.link; 1720 final long newLink[] = new long[newN + 1]; 1721 first = -1; 1722 for (int j = size; j-- != 0;) { 1723 if (((key[i]) == null)) 1724 pos = newN; 1725 else { 1726 pos = (((key[i]).hashCode())) & mask; 1727 while (!((newKey[pos]) == null)) 1728 pos = (pos + 1) & mask; 1729 } 1730 newKey[pos] = key[i]; 1731 newValue[pos] = value[i]; 1732 if (prev != -1) { 1733 newLink[newPrev] ^= ((newLink[newPrev] ^ (pos & 0xFFFFFFFFL)) & 0xFFFFFFFFL); 1734 newLink[pos] ^= ((newLink[pos] ^ ((newPrev & 0xFFFFFFFFL) << 32)) & 0xFFFFFFFF00000000L); 1735 newPrev = pos; 1736 } else { 1737 newPrev = first = pos; 1738 // Special case of SET(newLink[ pos ], -1, -1); 1739 newLink[pos] = -1L; 1740 } 1741 t = i; 1742 i = (int) link[i]; 1743 prev = t; 1744 } 1745 this.link = newLink; 1746 this.last = newPrev; 1747 if (newPrev != -1) 1748 // Special case of SET_NEXT( newLink[ newPrev ], -1 ); 1749 newLink[newPrev] |= -1 & 0xFFFFFFFFL; 1750 n = newN; 1751 this.mask = mask; 1752 maxFill = maxFill(n, f); 1753 this.key = newKey; 1754 this.value = newValue; 1755 } 1756 */ 1757 /** 1758 * Returns a deep copy of this map. 1759 * 1760 * <P> 1761 * This method performs a deep copy of this OrderedMap; the data stored in the 1762 * map, however, is not cloned. Note that this makes a difference only for 1763 * object keys. 1764 * 1765 * @return a deep copy of this map. 1766 */ 1767 @GwtIncompatible 1768 public IntIntOrderedMap clone() { 1769 IntIntOrderedMap c; 1770 try { 1771 c = (IntIntOrderedMap) super.clone(); 1772 c.key = new int[n + 1]; 1773 System.arraycopy(key, 0, c.key, 0, n + 1); 1774 c.value = new int[n + 1]; 1775 System.arraycopy(value, 0, c.value, 0, n + 1); 1776 c.order = (IntVLA) order.clone(); 1777 return c; 1778 } catch (Exception cantHappen) { 1779 throw new UnsupportedOperationException(cantHappen + (cantHappen.getMessage() != null ? 1780 "; " + cantHappen.getMessage() : "")); 1781 } 1782 } 1783 /** 1784 * Returns a hash code for this map. 1785 * 1786 * @return a hash code for this map. 1787 */ 1788 public int hashCode() { 1789 int h = 0; 1790 for (int j = realSize(), i = 0, t; j-- != 0;) { 1791 while (key[i] == 0) 1792 i++; 1793 t = HashCommon.mix(key[i]) ^ HashCommon.mix(value[i] ^ HashCommon.INV_INT_PHI); 1794 h += t; 1795 i++; 1796 } 1797 // Zero / null keys have hash zero. 1798 if (containsNullKey) 1799 h += HashCommon.mix(value[n] ^ HashCommon.INV_INT_PHI); 1800 return h; 1801 } 1802 1803 public long hash64() 1804 { 1805 return 31L * (31L * CrossHash.hash64(key) + CrossHash.hash64(value)) + size; 1806 } 1807 /** 1808 * Returns the maximum number of entries that can be filled before rehashing. 1809 * 1810 * @param n the size of the backing array. 1811 * @param f the load factor. 1812 * @return the maximum number of entries before rehashing. 1813 */ 1814 public static int maxFill(final int n, final float f) { 1815 /* We must guarantee that there is always at least 1816 * one free entry (even with pathological load factors). */ 1817 return Math.min((int)(n * f + 0.99999994f), n - 1); 1818 } 1819 1820 /** 1821 * 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>. 1822 * 1823 * @param expected the expected number of elements in a hash table. 1824 * @param f the load factor. 1825 * @return the minimum possible size for a backing array. 1826 * @throws IllegalArgumentException if the necessary size is larger than 2<sup>30</sup>. 1827 */ 1828 public static int arraySize(final int expected, final float f) { 1829 final long s = Math.max(2, HashCommon.nextPowerOfTwo((long) Math.ceil(expected / f))); 1830 if (s > (1 << 30)) 1831 throw new IllegalArgumentException("Too large (" + expected + " expected elements with load factor " + f + ")"); 1832 return (int) s; 1833 } 1834 1835 /** 1836 * Unwraps an iterator into an array starting at a given offset for a given number of elements. 1837 * <p> 1838 * <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 1839 * 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). 1840 * 1841 * @param i a type-specific iterator. 1842 * @param array an array to contain the output of the iterator. 1843 * @param offset the first element of the array to be returned. 1844 * @param max the maximum number of elements to unwrap. 1845 * @return the number of elements unwrapped. 1846 */ 1847 private int unwrap(final ValueIterator i, final Object[] array, int offset, final int max) { 1848 if (max < 0) throw new IllegalArgumentException("The maximum number of elements (" + max + ") is negative"); 1849 if (offset < 0 || offset + max > array.length) throw new IllegalArgumentException(); 1850 int j = max; 1851 while (j-- != 0 && i.hasNext()) 1852 array[offset++] = i.next(); 1853 return max - j - 1; 1854 } 1855 1856 /** 1857 * Unwraps an iterator into an array. 1858 * <p> 1859 * <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 1860 * of the array has been reached. 1861 * 1862 * @param i a type-specific iterator. 1863 * @param array an array to contain the output of the iterator. 1864 * @return the number of elements unwrapped. 1865 */ 1866 private int unwrap(final ValueIterator i, final Object[] array) { 1867 return unwrap(i, array, 0, array.length); 1868 } 1869 1870 1871 /** Unwraps an iterator into an array starting at a given offset for a given number of elements. 1872 * 1873 * <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 1874 * 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). 1875 * 1876 * @param i a type-specific iterator. 1877 * @param array an array to contain the output of the iterator. 1878 * @param offset the first element of the array to be returned. 1879 * @param max the maximum number of elements to unwrap. 1880 * @return the number of elements unwrapped. */ 1881 private static <K> int objectUnwrap(final Iterator<? extends K> i, final K[] array, int offset, final int max ) { 1882 if ( max < 0 ) throw new IllegalArgumentException( "The maximum number of elements (" + max + ") is negative" ); 1883 if ( offset < 0 || offset + max > array.length ) throw new IllegalArgumentException(); 1884 int j = max; 1885 while ( j-- != 0 && i.hasNext() ) 1886 array[ offset++ ] = i.next(); 1887 return max - j - 1; 1888 } 1889 1890 /** Unwraps an iterator into an array. 1891 * 1892 * <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 1893 * of the array has been reached. 1894 * 1895 * @param i a type-specific iterator. 1896 * @param array an array to contain the output of the iterator. 1897 * @return the number of elements unwrapped. */ 1898 private static <K> int objectUnwrap(final Iterator<? extends K> i, final K[] array) { 1899 return objectUnwrap(i, array, 0, array.length ); 1900 } 1901 1902 @Override 1903 public String toString() { 1904 final StringBuilder s = new StringBuilder(); 1905 int n = size(), i = 0; 1906 boolean first = true; 1907 s.append("IntIntOrderedMap{"); 1908 while (i < n) { 1909 if (first) first = false; 1910 else s.append(", "); 1911 s.append(entryAt(i++)); 1912 } 1913 s.append("}"); 1914 return s.toString(); 1915 } 1916 @Override 1917 public boolean equals(Object o) { 1918 if (o == this) 1919 return true; 1920 if (!(o instanceof IntIntOrderedMap)) 1921 return false; 1922 IntIntOrderedMap m = (IntIntOrderedMap) o; 1923 if (m.size() != size()) 1924 return false; 1925 return entrySet().containsAll(m.entrySet()); 1926 } 1927 1928 @GwtIncompatible 1929 private void writeObject(java.io.ObjectOutputStream s) 1930 throws java.io.IOException { 1931 final int[] key = this.key; 1932 final int[] value = this.value; 1933 final MapIterator i = new MapIterator(); 1934 s.defaultWriteObject(); 1935 for (int j = size, e; j-- != 0;) { 1936 e = i.nextEntry(); 1937 s.writeInt(key[e]); 1938 s.writeInt(value[e]); 1939 } 1940 } 1941 @GwtIncompatible 1942 private void readObject(java.io.ObjectInputStream s) 1943 throws java.io.IOException, ClassNotFoundException { 1944 s.defaultReadObject(); 1945 n = arraySize(size, f); 1946 maxFill = maxFill(n, f); 1947 mask = n - 1; 1948 final int[] key = this.key = new int[n + 1]; 1949 final int[] value = this.value = new int[n + 1]; 1950 final IntVLA order = this.order = new IntVLA(n + 1); 1951 int k; 1952 int v; 1953 for (int i = size, pos; i-- != 0;) { 1954 k = s.readInt(); 1955 v = s.readInt(); 1956 if (k == 0) { 1957 pos = n; 1958 containsNullKey = true; 1959 } else { 1960 pos = (HashCommon.mix(k)) 1961 & mask; 1962 while (!(key[pos] == 0)) 1963 pos = (pos + 1) & mask; 1964 } 1965 1966 key[pos] = k; 1967 value[pos] = v; 1968 order.add(pos); 1969 } 1970 } 1971 1972 /** 1973 * Gets the value at the given index in the iteration order in constant time (random-access). 1974 * @param idx the index in the iteration order of the value to fetch 1975 * @return the value at the index, if the index is valid, otherwise the default return value 1976 */ 1977 public int getAt(final int idx) { 1978 int pos; 1979 if (idx < 0 || idx >= order.size) 1980 return defRetValue; 1981 // The starting point. 1982 if (key[pos = order.get(idx)] == 0) 1983 return containsNullKey ? value[n] : defRetValue; 1984 return value[pos]; 1985 } 1986 /** 1987 * Gets the key at the given index in the iteration order in constant time (random-access). 1988 * @param idx the index in the iteration order of the key to fetch 1989 * @return the key at the index, if the index is valid, otherwise 0 1990 */ 1991 public int keyAt(final int idx) { 1992 if (idx < 0 || idx >= order.size) 1993 return 0; 1994 // The starting point. 1995 return key[order.get(idx)]; 1996 } 1997 1998 /** 1999 * Gets the key-value Map.Entry at the given index in the iteration order in constant time (random-access). 2000 * @param idx the index in the iteration order of the entry to fetch 2001 * @return the key-value entry at the index, if the index is valid, otherwise null 2002 */ 2003 public MapEntry entryAt(final int idx) 2004 { 2005 if (idx < 0 || idx >= order.size) 2006 return null; 2007 return new MapEntry(order.get(idx)); 2008 } 2009 2010 /** 2011 * Removes the key and value at the given index in the iteration order in not-exactly constant time (though it still 2012 * should be efficient). 2013 * @param idx the index in the iteration order of the key and value to remove 2014 * @return the value removed, if there was anything removed, or the default return value otherwise (often null) 2015 */ 2016 public int removeAt(final int idx) { 2017 2018 if (idx < 0 || idx >= order.size) 2019 return defRetValue; 2020 int pos = order.get(idx); 2021 if (key[pos] == 0) { 2022 if (containsNullKey) 2023 return removeNullEntry(); 2024 return defRetValue; 2025 } 2026 return removeEntry(pos); 2027 } 2028 /** 2029 * Gets a random value from this OrderedMap in constant time, using the given IRNG to generate a random number. 2030 * @param rng used to generate a random index for a value 2031 * @return a random value from this OrderedMap 2032 */ 2033 public int randomValue(IRNG rng) 2034 { 2035 return getAt(rng.nextInt(order.size)); 2036 } 2037 2038 /** 2039 * Gets a random key from this OrderedMap in constant time, using the given IRNG to generate a random number. 2040 * @param rng used to generate a random index for a key 2041 * @return a random key from this OrderedMap 2042 */ 2043 public int randomKey(IRNG rng) 2044 { 2045 return keyAt(rng.nextInt(order.size)); 2046 } 2047 2048 /** 2049 * Gets a random entry from this OrderedMap in constant time, using the given IRNG to generate a random number. 2050 * @param rng used to generate a random index for a entry 2051 * @return a random key-value entry from this OrderedMap 2052 */ 2053 public MapEntry randomEntry(IRNG rng) 2054 { 2055 return new MapEntry(order.getRandomElement(rng)); 2056 } 2057 2058 /** 2059 * Randomly alters the iteration order for this OrderedMap using the given IRNG to shuffle. 2060 * @param rng used to generate a random ordering 2061 * @return this for chaining 2062 */ 2063 public IntIntOrderedMap shuffle(IRNG rng) 2064 { 2065 if(size < 2) 2066 return this; 2067 order.shuffle(rng); 2068 return this; 2069 } 2070 2071 /** 2072 * Given an array or varargs of replacement indices for this OrderedMap's iteration order, reorders this so the 2073 * first item in the returned version is the same as {@code getAt(ordering[0])} (with some care taken for negative 2074 * or too-large indices), the second item in the returned version is the same as {@code getAt(ordering[1])}, etc. 2075 * <br> 2076 * Negative indices are considered reversed distances from the end of ordering, so -1 refers to the same index as 2077 * {@code ordering[ordering.length - 1]}. If ordering is smaller than {@code size()}, only the indices up to the 2078 * length of ordering will be modified. If ordering is larger than {@code size()}, only as many indices will be 2079 * affected as {@code size()}, and reversed distances are measured from the end of this Map's entries instead of 2080 * the end of ordering. Duplicate values in ordering will produce duplicate values in the returned Map. 2081 * <br> 2082 * This method modifies this OrderedMap in-place and also returns it for chaining. 2083 * @param ordering an array or varargs of int indices, where the nth item in ordering changes the nth item in this 2084 * Map to have the value currently in this Map at the index specified by the value in ordering 2085 * @return this for chaining, after modifying it in-place 2086 */ 2087 public IntIntOrderedMap reorder(int... ordering) 2088 { 2089 order.reorder(ordering); 2090 return this; 2091 } 2092 private int alterEntry(final int pos) { 2093 int idx = fixOrder(pos); 2094 size--; 2095 shiftKeys(pos); 2096 return idx; 2097 } 2098 private int alterNullEntry() { 2099 int idx = fixOrder(n); 2100 containsNullKey = false; 2101 size--; 2102 return idx; 2103 } 2104 /** 2105 * Swaps a key, original, for another key, replacement, while keeping replacement at the same point in the iteration 2106 * order as original and keeping it associated with the same value (which also keeps its iteration index). Unlike 2107 * the similar method {@link #alter(int, int)}, this will not change this OrderedMap if replacement is already 2108 * present. To contrast, alter() can reduce the size of the OrderedMap if both original and replacement are already 2109 * in the Map. If replacement is found, this returns the default return value, otherwise it switches out original 2110 * for replacement and returns whatever was associated with original. 2111 * @param original the key to find and swap out 2112 * @param replacement the key to replace original with 2113 * @return the value associated with original before, and replacement now 2114 */ 2115 public int alterCarefully(final int original, final int replacement) { 2116 if(!containsKey(replacement)) 2117 return alter(original, replacement); 2118 else 2119 return defRetValue; 2120 } 2121 /** 2122 * Swaps a key, original, for another key, replacement, while keeping replacement at the same point in the iteration 2123 * order as original and keeping it associated with the same value (which also keeps its iteration index). 2124 * Be aware that if both original and replacement are present in the OrderedMap, this will still replace original 2125 * with replacement but will also remove the other occurrence of replacement to avoid duplicate keys. This can throw 2126 * off the expected order because the duplicate could be at any point in the ordering when it is removed. You may 2127 * want to prefer {@link #alterCarefully(int, int)} if you don't feel like checking by hand for whether 2128 * replacement is already present, but using this method is perfectly reasonable if you know overlaps won't happen. 2129 * @param original the key to find and swap out 2130 * @param replacement the key to replace original with 2131 * @return the value associated with original before, and replacement now 2132 */ 2133 public int alter(final int original, final int replacement) { 2134 int v; 2135 int idx; 2136 if (original == 0) { 2137 if (containsNullKey) { 2138 v = value[n]; 2139 idx = alterNullEntry(); 2140 putAt(replacement, v, idx); 2141 return v; 2142 } 2143 else 2144 v = defRetValue; 2145 return v; 2146 } 2147 int curr; 2148 final int[] key = this.key; 2149 int pos; 2150 // The starting point. 2151 if ((curr = key[pos = (HashCommon.mix(original)) & mask]) == 0) 2152 return defRetValue; 2153 if (original == curr) 2154 { 2155 v = value[pos]; 2156 idx = alterEntry(pos); 2157 putAt(replacement, v, idx); 2158 return v; 2159 } 2160 while (true) { 2161 if ((curr = key[pos = (pos + 1) & mask]) == 0) 2162 return defRetValue; 2163 if (original == curr) 2164 { 2165 v = value[pos]; 2166 idx = alterEntry(pos); 2167 putAt(replacement, v, idx); 2168 return v; 2169 } 2170 } 2171 } 2172 2173 public IntVLA getMany(int... keys) 2174 { 2175 if(keys == null) 2176 return new IntVLA(1); 2177 final int len = keys.length; 2178 IntVLA vals = new IntVLA(len); 2179 for (int i = 0; i < len; i++) { 2180 vals.add(get(keys[i])); 2181 } 2182 return vals; 2183 } 2184 /** 2185 * Changes the int at the given index to replacement while keeping replacement at the same point in the ordering. 2186 * Be aware that if replacement is present in the OrderedMap, this will still replace the given index 2187 * with replacement but will also remove the other occurrence of replacement to avoid duplicate keys. This can throw 2188 * off the expected order because the duplicate could be at any point in the ordering when it is removed. You may 2189 * want to prefer {@link #alterAtCarefully(int, int)} if you don't feel like checking by hand for whether 2190 * replacement is already present, but using this method is perfectly reasonable if you know overlaps won't happen. 2191 * @param index an index to replace the int key at 2192 * @param replacement another int key that will replace the original at the remembered index 2193 * @return the value associated with the possibly-altered key 2194 */ 2195 public int alterAt(int index, int replacement) 2196 { 2197 return alter(keyAt(index), replacement); 2198 } 2199 /** 2200 * Changes the int at the given index to replacement while keeping replacement at the same point in the ordering. 2201 * Unlike the similar method {@link #alterAt(int, int)}, this will not change this OrderedMap if replacement is 2202 * already present. To contrast, alterAt() can reduce the size of the OrderedMap if replacement is already 2203 * in the Map. If replacement is found, this returns the default return value, otherwise it switches out the index 2204 * for replacement and returns whatever value was at the index before. 2205 * @param index an index to replace the int key at 2206 * @param replacement another int key that will replace the original at the remembered index 2207 * @return the value associated with the key at the altered index before, and replacement now 2208 */ 2209 public int alterAtCarefully(int index, int replacement) 2210 { 2211 return alterCarefully(keyAt(index), replacement); 2212 } 2213 2214 /** 2215 * If the specified key is not already associated with a value, associates it with the given value 2216 * and returns that value, else returns the current value without changing anything. 2217 * 2218 * @param key key with which the specified value is to be associated 2219 * @param value value to be associated with the specified key 2220 * @return the previous value associated with the specified key, or 2221 * {@code value} if there was no mapping for the key. 2222 */ 2223 public int putIfAbsent(int key, int value) { 2224 if(containsKey(key)) 2225 return get(key); 2226 put(key, value); 2227 return value; 2228 } 2229 2230 /** 2231 * Removes the entry for the specified key only if it is currently 2232 * mapped to the specified value. 2233 * 2234 * @param key key with which the specified value is associated 2235 * @param value value expected to be associated with the specified key 2236 * @return {@code true} if the value was removed 2237 */ 2238 public boolean remove(int key, int value) { 2239 if (containsKey(key) && get(key) == value) { 2240 remove(key); 2241 return true; 2242 } else 2243 return false; 2244 } 2245 2246 /** 2247 * Replaces the entry for the specified key only if currently 2248 * mapped to the specified value. The position in the iteration 2249 * order is retained. 2250 * 2251 * @param key key with which the specified value is associated 2252 * @param oldValue value expected to be associated with the specified key 2253 * @param newValue value to be associated with the specified key 2254 * @return {@code true} if the value was replaced 2255 */ 2256 public boolean replace(int key, int oldValue, int newValue) { 2257 if (containsKey(key) && get(key) == oldValue) { 2258 put(key, newValue); 2259 return true; 2260 } else 2261 return false; 2262 } 2263 2264 /** 2265 * Replaces the entry for the specified key only if it is 2266 * currently mapped to some value. Preserves the existing key's 2267 * position in the iteration order. 2268 * 2269 * @param key key with which the specified value is associated 2270 * @param value value to be associated with the specified key 2271 * @return the previous value associated with the specified key, or 2272 * {@code null} if there was no mapping for the key. 2273 * (A {@code null} return can also indicate that the map 2274 * previously associated {@code null} with the key.) 2275 */ 2276 public int replace(int key, int value) { 2277 if (containsKey(key)) { 2278 return put(key, value); 2279 } else 2280 return defRetValue; 2281 } 2282 /** 2283 * Given alternating key and value arguments in pairs, puts each key-value pair into this OrderedMap as if by 2284 * calling {@link #put(int, int)} repeatedly for each pair. This mimics the parameter syntax used for 2285 * {@link #makeMap(int, int, int...)}, and can be used to retain that style of insertion after an 2286 * IntIntOrderedMap has been instantiated. 2287 * @param k0 the first key to add 2288 * @param v0 the first value to add 2289 * @param rest an array or vararg of keys and values in pairs; should contain alternating only int elements 2290 * @return this, after adding all viable key-value pairs given 2291 */ 2292 public IntIntOrderedMap putPairs(int k0, int v0, int... rest) 2293 { 2294 if(rest == null || rest.length == 0) 2295 { 2296 put(k0, v0); 2297 return this; 2298 } 2299 put(k0, v0); 2300 2301 for (int i = 0; i < rest.length - 1; i+=2) { 2302 put(rest[i], rest[i + 1]); 2303 } 2304 return this; 2305 } 2306 2307 /** 2308 * Makes an IntIntOrderedMap using the given int keys and values in alternating key-value-key-value order. If rest 2309 * has an odd-number length, then it discards the last item. If any item in rest is not an int, this will not 2310 * compile. This is similar to the makeOM method in the Maker class, but produces an IntIntOrderedMap. 2311 * <br> 2312 * This is named makeMap to indicate that it expects key and value parameters, unlike a Set or List. This convention 2313 * may be extended to other data structures that also have static methods for instantiation. 2314 * @param k0 the first key; used to infer the types of other keys if generic parameters aren't specified. 2315 * @param v0 the first value; used to infer the types of other values if generic parameters aren't specified. 2316 * @param rest an array or vararg of keys and values in pairs; should contain only int elements 2317 * @return a freshly-made IntIntOrderedMap, using k0, v0, and the contents of rest to fill it 2318 */ 2319 public static IntIntOrderedMap makeMap(int k0, int v0, int... rest) 2320 { 2321 if(rest == null || rest.length == 0) 2322 { 2323 IntIntOrderedMap om = new IntIntOrderedMap(2); 2324 om.put(k0, v0); 2325 return om; 2326 } 2327 IntIntOrderedMap om = new IntIntOrderedMap(1 + (rest.length >> 1)); 2328 om.put(k0, v0); 2329 2330 for (int i = 0; i < rest.length - 1; i+=2) { 2331 try { 2332 om.put(rest[i], rest[i + 1]); 2333 }catch (ClassCastException ignored) { 2334 } 2335 } 2336 return om; 2337 } 2338 2339 /** 2340 * Makes an empty IntIntOrderedMap.This method is provided for completeness relative to makeMap() with 2 or more 2341 * parameters. 2342 * @return an empty IntIntOrderedMap 2343 */ 2344 public static IntIntOrderedMap makeMap() 2345 { 2346 return new IntIntOrderedMap(); 2347 } 2348 2349 /** 2350 * Reverses the iteration order in linear time. 2351 */ 2352 public void reverse() 2353 { 2354 order.reverse(); 2355 } 2356}