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.ArrayTools; 019import squidpony.annotation.GwtIncompatible; 020 021import java.io.Serializable; 022import java.util.*; 023 024/** 025 * A bi-directional mapping of non-unique objects to positions in an ordering (which this generates), and vice versa. 026 * This class is very similar to {@link Arrangement}, but is bag-like instead of set-like, allowing repeats of the same 027 * key with different positions in the ordering. Useful for various indirection techniques where you want to be able to 028 * retrieve a value in several ways, such as with multiple MultiArrangements all sharing the same ordering but with 029 * different types for keys. 030 * <br> 031 * Originally, this started as a generic linked hash map with with a fast implementation, originally from fastutil as 032 * Object2IntLinkedOpenHashMap but modified to support indexed access. The code is extremely close to {@link OrderedMap}, 033 * and like OrderedMap you can look up keys by index, but this is specialized to int values which it can automatically assign. 034 * <br> 035 * <p>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 036 * 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 037 * process. 038 * </p> 039 * <p>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 040 * you reuse instances of this class. 041 * </p> 042 * <p>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 043 * 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 044 * class' {@link #reorder(int...)} and {@link #shuffle(IRNG)} methods, among other tools. 045 * </p> 046 * <p>This class implements the interface of a sorted map, so to allow easy access of the iteration order: for instance, you can get the first key in iteration order with {@code firstKey()} without 047 * having to create an iterator; however, this class partially violates the {@link SortedMap} contract because all submap methods throw an exception and {@link #comparator()} returns always 048 * <code>null</code>. 049 * </p> 050 * <p> 051 * Additional methods, such as <code>getAndMoveToFirst()</code>, make it easy to use instances of this class as a cache (e.g., with LRU policy). 052 * </p> 053 * <br> 054 * Thank you, Sebastiano Vigna, for making FastUtil available to the public with such high quality. 055 * <br> 056 * See https://github.com/vigna/fastutil for the original library. 057 * 058 * @author Sebastiano Vigna (responsible for all the hard parts) 059 * @author Tommy Ettinger (mostly responsible for squashing several layers of parent classes into one monster class) 060 */ 061public class MultiArrangement<K> implements Iterable<K>, Serializable, Cloneable { 062 private static final long serialVersionUID = 0L; 063 /** 064 * The array of keys. 065 */ 066 protected K[] key; 067 /** 068 * The array of values. 069 */ 070 protected IntVLA[] value; 071 /** 072 * The mask for wrapping a position counter. 073 */ 074 protected int mask; 075 /** 076 * Whether this set contains the key zero. 077 */ 078 protected boolean containsNullKey; 079 /** 080 * The index of the first entry in iteration order. It is valid iff {@link #size} is nonzero; otherwise, it contains -1. 081 */ 082 protected int first = -1; 083 /** 084 * The index of the last entry in iteration order. It is valid iff {@link #size} is nonzero; otherwise, it contains -1. 085 */ 086 protected int last = -1; 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 /** 107 * Cached set of keys. 108 */ 109 protected volatile KeyList keys; 110 /** 111 * Cached collection of values. 112 */ 113 protected volatile IntVLA values; 114 /** 115 * Default return value. 116 */ 117 protected final int defRetValue = -1; 118 119 /** 120 * The initial default size of a hash table. 121 */ 122 public static final int DEFAULT_INITIAL_SIZE = 16; 123 /** 124 * The default load factor of a hash table. 125 */ 126 public static final float DEFAULT_LOAD_FACTOR = .75f; // .375f // .1875f; // .75f; 127 /** 128 * The load factor for a (usually small) table that is meant to be particularly fast. 129 */ 130 public static final float FAST_LOAD_FACTOR = .5f; 131 /** 132 * The load factor for a (usually very small) table that is meant to be extremely fast. 133 */ 134 public static final float VERY_FAST_LOAD_FACTOR = .25f; 135 136 protected CrossHash.IHasher hasher; 137 138 /** 139 * Creates a new MultiArrangement. 140 * <p> 141 * <p>The actual table size will be the least power of two greater than <code>expected</code>/<code>f</code>. 142 * 143 * @param expected the expected number of elements in the hash set. 144 * @param f the load factor. 145 */ 146 147 @SuppressWarnings("unchecked") 148 public MultiArrangement(final int expected, final float f) { 149 if (f <= 0 || f > 1) 150 throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than or equal to 1"); 151 if (expected < 0) throw new IllegalArgumentException("The expected number of elements must be nonnegative"); 152 this.f = f; 153 n = arraySize(expected, f); 154 mask = n - 1; 155 maxFill = maxFill(n, f); 156 key = (K[]) new Object[n + 1]; 157 value = new IntVLA[n + 1]; 158 //link = new long[n + 1]; 159 order = new IntVLA(expected); 160 hasher = CrossHash.defaultHasher; 161 } 162 163 /** 164 * Creates a new MultiArrangement with 0.5f as load factor. 165 * 166 * @param expected the expected number of elements in the MultiArrangement. 167 */ 168 public MultiArrangement(final int expected) { 169 this(expected, DEFAULT_LOAD_FACTOR); 170 } 171 172 /** 173 * Creates a new MultiArrangement with initial expected 16 entries and 0.5f as load factor. 174 */ 175 public MultiArrangement() { 176 this(DEFAULT_INITIAL_SIZE, DEFAULT_LOAD_FACTOR); 177 } 178 179 180 public MultiArrangement(final MultiArrangement<? extends K> a) { 181 this(a.size(), a.f, a.hasher); 182 ensureCapacity(a.size()); // The resulting map will be sized for 183 System.arraycopy(a.key, 0, key, 0, a.key.length); 184 System.arraycopy(a.value, 0, value, 0, a.value.length); 185 order.addAll(a.order); 186 containsNullKey = a.containsNullKey; 187 } 188 189 /** 190 * Creates a new MultiArrangement using the elements of an array. 191 * 192 * @param keyArray the array of keys of the new MultiArrangement. 193 * @param f the load factor. 194 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 195 */ 196 public MultiArrangement(final K[] keyArray, final float f) { 197 this(keyArray.length, f); 198 for (int i = 0; i < keyArray.length; i++) 199 add(keyArray[i]); 200 } 201 202 /** 203 * Creates a new Arrangement using the elements of an array. 204 * 205 * @param keyColl the collection of keys of the new Arrangement. 206 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 207 */ 208 public MultiArrangement(final Collection<K> keyColl) { 209 this(keyColl, DEFAULT_LOAD_FACTOR); 210 } 211 /** 212 * Creates a new Arrangement using the given collection of keys. 213 * 214 * @param keyColl the collection of keys of the new Arrangement. 215 * @param f the load factor. 216 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 217 */ 218 public MultiArrangement(final Collection<K> keyColl, final float f) { 219 this(keyColl.size(), f); 220 Iterator<K> ki = keyColl.iterator(); 221 int idx = 0; 222 while (ki.hasNext()) 223 { 224 add(ki.next()); 225 } 226 } 227 228 /** 229 * Creates a new Arrangement with 0.5f as load factor using the elements of an array. 230 * 231 * @param keyArray the array of keys of the new Arrangement. 232 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 233 */ 234 public MultiArrangement(final K[] keyArray) { 235 this(keyArray, DEFAULT_LOAD_FACTOR); 236 } 237 238 /** 239 * Creates a new Arrangement. 240 * <p> 241 * <p>The actual table size will be the least power of two greater than <code>expected</code>/<code>f</code>. 242 * 243 * @param expected the expected number of elements in the hash set. 244 * @param f the load factor. 245 * @param hasher used to hash items; typically only needed when K is an array, where CrossHash has implementations 246 */ 247 @SuppressWarnings("unchecked") 248 public MultiArrangement(final int expected, final float f, CrossHash.IHasher hasher) { 249 if (f <= 0 || f > 1) 250 throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than or equal to 1"); 251 if (expected < 0) throw new IllegalArgumentException("The expected number of elements must be nonnegative"); 252 this.f = f; 253 n = arraySize(expected, f); 254 mask = n - 1; 255 maxFill = maxFill(n, f); 256 key = (K[]) new Object[n + 1]; 257 value = new IntVLA[n + 1]; 258 //link = new long[n + 1]; 259 order = new IntVLA(expected); 260 this.hasher = (hasher == null) ? CrossHash.defaultHasher : hasher; 261 } 262 /** 263 * Creates a new Arrangement with 0.5f as load factor. 264 * 265 * @param expected the expected number of elements in the Arrangement. 266 * @param hasher used to hash items; typically only needed when K is an array, where CrossHash has implementations 267 */ 268 public MultiArrangement(final int expected, CrossHash.IHasher hasher) { 269 this(expected, DEFAULT_LOAD_FACTOR, hasher); 270 } 271 272 /** 273 * Creates a new Arrangement with initial expected 16 entries and 0.5f as load factor. 274 */ 275 public MultiArrangement(CrossHash.IHasher hasher) { 276 this(DEFAULT_INITIAL_SIZE, DEFAULT_LOAD_FACTOR, hasher); 277 } 278 279 /** 280 * Creates a new Arrangement using the elements of two parallel arrays. 281 * 282 * @param keyArray the array of keys of the new Arrangement. 283 * @param f the load factor. 284 * @param hasher used to hash items; typically only needed when K is an array, where CrossHash has implementations 285 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 286 */ 287 public MultiArrangement(final K[] keyArray, final float f, CrossHash.IHasher hasher) { 288 this(keyArray.length, f, hasher); 289 290 for (int i = 0; i < keyArray.length; i++) 291 add(keyArray[i]); 292 } 293 /** 294 * Creates a new Arrangement with 0.5f as load factor using the elements of two parallel arrays. 295 * 296 * @param keyArray the array of keys of the new Arrangement. 297 * @param hasher used to hash items; typically only needed when K is an array, where CrossHash has implementations 298 * @throws IllegalArgumentException if <code>k</code> and <code>v</code> have different lengths. 299 */ 300 public MultiArrangement(final K[] keyArray, CrossHash.IHasher hasher) { 301 this(keyArray, DEFAULT_LOAD_FACTOR, hasher); 302 } 303 304 private int realSize() { 305 return containsNullKey ? size - 1 : size; 306 } 307 private void ensureCapacity(final int capacity) { 308 final int needed = arraySize(capacity, f); 309 if (needed > n) 310 rehash(needed); 311 } 312 private void tryCapacity(final long capacity) { 313 final int needed = (int) Math.min( 314 1 << 30, 315 Math.max(2, HashCommon.nextPowerOfTwo((long) Math.ceil(capacity 316 / f)))); 317 if (needed > n) 318 rehash(needed); 319 } 320 private int removeEntry(final int pos) { 321 final IntVLA oldValue = value[pos]; 322 final int popped = oldValue.pop(); 323 if(oldValue.size == 0) --size; 324 fixOrder(pos); 325 shiftKeys(pos); 326 fixValues(); 327 if (oldValue.size == 0 && size < (maxFill >>> 2) && n > DEFAULT_INITIAL_SIZE) 328 rehash(n / 2); 329 return popped; 330 } 331 private int removeNullEntry() { 332 containsNullKey = false; 333 key[n] = null; 334 final IntVLA oldValue = value[n]; 335 final int popped = oldValue.pop(); 336 if(oldValue.size == 0) --size; 337 fixOrder(n); 338 fixValues(); 339 if (oldValue.size == 0 && size < (maxFill >>> 2) && n > DEFAULT_INITIAL_SIZE) 340 rehash(n / 2); 341 return popped; 342 } 343 344 public void addAll(K[] keyArray) { 345 if (f <= .5) 346 ensureCapacity(keyArray.length); // The resulting map will be sized for 347 // m.size() elements 348 else 349 tryCapacity(size() + keyArray.length); // The resulting map will be 350 int n = keyArray.length; 351 for (int i = 0; i < n; i++) { 352 add(keyArray[i]); 353 } 354 } 355 356 public void addAll(Collection<? extends K> keyArray) { 357 if (f <= .5) 358 ensureCapacity(keyArray.size()); // The resulting map will be sized for 359 // m.size() elements 360 else 361 tryCapacity(size() + keyArray.size()); // The resulting map will be 362 Iterator<? extends K> it = keyArray.iterator(); 363 while (it.hasNext()) 364 add(it.next()); 365 } 366 public void addAllIfAbsent(Map<? extends K, ? extends Integer> m) { 367 if (f <= .5) 368 ensureCapacity(m.size()); // The resulting map will be sized for 369 // m.size() elements 370 else 371 tryCapacity(size() + m.size()); // The resulting map will be 372 int n = m.size(); 373 final Iterator<? extends K> i = m 374 .keySet().iterator(); 375 while (n-- != 0) { 376 addIfAbsent(i.next()); 377 } 378 } 379 380 public void addAllIfAbsent(K[] keyArray) { 381 if (f <= .5) 382 ensureCapacity(keyArray.length); 383 else 384 tryCapacity(size() + keyArray.length); 385 int n = keyArray.length; 386 for (int i = 0; i < n; i++) { 387 addIfAbsent(keyArray[i]); 388 } 389 } 390 391 public void addAllIfAbsent(Collection<? extends K> keyArray) { 392 if (f <= .5) 393 ensureCapacity(keyArray.size()); 394 else 395 tryCapacity(size() + keyArray.size()); 396 Iterator<? extends K> it = keyArray.iterator(); 397 while (it.hasNext()) 398 addIfAbsent(it.next()); 399 } 400 401 private int insert(final K k) { 402 return insertAt(k, order.size); 403 } 404 private int insertAt(final K k, final int at) { 405 int pos; 406 if (k == null) { 407 if (containsNullKey) { 408 value[n].add(at); 409 order.add(n); 410 return n; 411 } 412 containsNullKey = true; 413 pos = n; 414 } else { 415 K curr; 416 final K[] key = this.key; 417 // The starting point. 418 if ((curr = key[pos = (hasher.hash(k)) & mask]) != null) { 419 if (hasher.areEqual(curr, k)) { 420 value[pos].add(at); 421 order.insert(at, pos); 422 return pos; 423 } 424 while ((curr = key[pos = (pos + 1) & mask]) != null) 425 if (hasher.areEqual(curr, k)) { 426 value[pos].add(at); 427 order.insert(at, pos); 428 return pos; 429 } 430 } 431 } 432 key[pos] = k; 433 if (size == 0) { 434 first = last = pos; 435 } else { 436 last = pos; 437 } 438 order.insert(at, pos); 439 value[pos] = new IntVLA(8); 440 value[pos].add(at); 441 if (size++ >= maxFill) 442 rehash(arraySize(size + 1, f)); 443 return -1; 444 } 445 446 public int add(final K k) { 447 final int pos = insert(k); 448 if (pos < 0) 449 return defRetValue; 450 final IntVLA oldValue = value[pos]; 451 oldValue.add(order.size - 1); 452 return order.size - 1; 453 } 454 455 public int addIfAbsent(final K k) 456 { 457 int kPos; 458 if(containsKey(k)) 459 return add(k); 460 return -1; 461 } 462 463 protected void fixValues() 464 { 465 for (int i = 0; i < order.size; i++) { 466 value[order.items[i]].clear(); 467 } 468 for (int i = 0; i < order.size; i++) { 469 value[order.items[i]].add(i); 470 } 471 } 472 473 /** 474 * Shifts left entries with the specified hash code, starting at the 475 * specified position, and empties the resulting free entry. 476 * 477 * @param pos 478 * a starting position. 479 */ 480 protected final void shiftKeys(int pos) { 481 // Shift entries with the same hash. 482 int last, slot; 483 K curr; 484 final K[] key = this.key; 485 for (;;) { 486 pos = ((last = pos) + 1) & mask; 487 for (;;) { 488 if ((curr = key[pos]) == null) { 489 key[last] = null; 490 return; 491 } 492 slot = (hasher.hash(curr)) 493 & mask; 494 if (last <= pos ? last >= slot || slot > pos : last >= slot 495 && slot > pos) 496 break; 497 pos = (pos + 1) & mask; 498 } 499 key[last] = curr; 500 fixOrder(pos, last); 501 } 502 } 503 /** 504 * Shifts left entries with the specified hash code, starting at the 505 * specified position, and empties the resulting free entry. 506 * 507 * @param pos 508 * a starting position. 509 */ 510 protected final void shiftKeysValues(int pos) { 511 // Shift entries with the same hash. 512 int last, slot; 513 K curr; 514 IntVLA v; 515 final K[] key = this.key; 516 final IntVLA[] val = this.value; 517 for (;;) { 518 pos = ((last = pos) + 1) & mask; 519 for (;;) { 520 if ((curr = key[pos]) == null) { 521 key[last] = null; 522 val[last] = null; 523 return; 524 } 525 v = val[pos]; 526 slot = (hasher.hash(curr)) 527 & mask; 528 if (last <= pos ? last >= slot || slot > pos : last >= slot 529 && slot > pos) 530 break; 531 pos = (pos + 1) & mask; 532 } 533 key[last] = curr; 534 val[last] = v; 535 fixOrder(pos, last); 536 } 537 } 538 539 protected int rem(final Object k) { 540 if (k == null) { 541 if (containsNullKey) 542 return removeNullEntry(); 543 return defRetValue; 544 } 545 K curr; 546 final K[] key = this.key; 547 int pos; 548 // The starting point. 549 if ((curr = key[pos = (hasher.hash(k)) & mask]) == null) 550 return defRetValue; 551 if (hasher.areEqual(k, curr)) 552 return removeEntry(pos); 553 while (true) { 554 if ((curr = key[pos = (pos + 1) & mask]) == null) 555 return defRetValue; 556 if (hasher.areEqual(k, curr)) 557 return removeEntry(pos); 558 } 559 } 560 public int remove(Object o) 561 { 562 return rem(o); 563 } 564 public int removeInt(final Object k) { 565 if (k == null) { 566 if (containsNullKey) 567 return removeNullEntry(); 568 return defRetValue; 569 } 570 K curr; 571 final K[] key = this.key; 572 int pos; 573 // The starting point. 574 if ((curr = key[pos = (hasher.hash(k)) & mask]) == null) 575 return defRetValue; 576 if (hasher.areEqual(k, curr)) 577 return removeEntry(pos); 578 while (true) { 579 if ((curr = key[pos = (pos + 1) & mask]) == null) 580 return defRetValue; 581 if (hasher.areEqual(k, curr)) 582 return removeEntry(pos); 583 } 584 } 585 /** 586 * Removes the mapping associated with the first key in iteration order. 587 * 588 * @return the value previously associated with the first key in iteration 589 * order. 590 * @throws NoSuchElementException 591 * is this map is empty. 592 */ 593 public K removeFirst() { 594 return removeAt(0); 595 596 } 597 /** 598 * Removes the mapping associated with the last key in iteration order. 599 * 600 * @return the value previously associated with the last key in iteration 601 * order. 602 * @throws NoSuchElementException 603 * is this map is empty. 604 */ 605 public K removeLast() { 606 return removeAt(order.size - 1); 607 608 } 609 private void moveIndexToFirst(final int i) { 610 if(order.size <= 1 || first == i) 611 return; 612 order.moveToFirst(i); 613 if (last == i) { 614 last = order.peek(); 615 //last = (int) (link[i] >>> 32); 616 // Special case of SET_NEXT( link[ last ], -1 ); 617 //link[last] |= -1 & 0xFFFFFFFFL; 618 }/* else { 619 final long linki = link[i]; 620 final int prev = (int) (linki >>> 32); 621 final int next = (int) linki; 622 link[prev] ^= ((link[prev] ^ (linki & 0xFFFFFFFFL)) & 0xFFFFFFFFL); 623 link[next] ^= ((link[next] ^ (linki & 0xFFFFFFFF00000000L)) & 0xFFFFFFFF00000000L); 624 } 625 link[first] ^= ((link[first] ^ ((i & 0xFFFFFFFFL) << 32)) & 0xFFFFFFFF00000000L); 626 link[i] = ((-1 & 0xFFFFFFFFL) << 32) | (first & 0xFFFFFFFFL); 627 */ 628 first = i; 629 fixValues(); 630 } 631 private void moveIndexToLast(final int i) { 632 if(order.size <= 1 || last == i) 633 return; 634 order.moveToLast(i); 635 if (first == i) { 636 first = order.get(0); 637 //first = (int) link[i]; 638 // Special case of SET_PREV( link[ first ], -1 ); 639 //link[first] |= (-1 & 0xFFFFFFFFL) << 32; 640 } /*else { 641 final long linki = link[i]; 642 final int prev = (int) (linki >>> 32); 643 final int next = (int) linki; 644 link[prev] ^= ((link[prev] ^ (linki & 0xFFFFFFFFL)) & 0xFFFFFFFFL); 645 link[next] ^= ((link[next] ^ (linki & 0xFFFFFFFF00000000L)) & 0xFFFFFFFF00000000L); 646 } 647 link[last] ^= ((link[last] ^ (i & 0xFFFFFFFFL)) & 0xFFFFFFFFL); 648 link[i] = ((last & 0xFFFFFFFFL) << 32) | (-1 & 0xFFFFFFFFL); 649 */ 650 last = i; 651 fixValues(); 652 } 653 654 /** 655 * Different from the typical get method; clears the non-null IntVLA, container, and fills it with any positions 656 * associated with k in this MultiArrangement. If you want to append to container instead of clearing it, use 657 * {@link #append(IntVLA, Object)}. 658 * @param container a non-null IntVLA; will be modified! Even if no entries are added, will be cleared 659 * @param k a K object or something that can be treated as one to search for 660 * @return the number of items added to container; 0 if none were added 661 */ 662 public int get(final IntVLA container, final Object k) { 663 container.clear(); 664 return append(container, k); 665 } 666 /** 667 * Different from the typical get method; adds to the non-null IntVLA, container, filling with any positions 668 * associated with k in this MultiArrangement. If you want a more convenient method for the case where you want 669 * container to hold only the items associated with k (discarding old contents), use {@link #get(IntVLA, Object)}. 670 * @param container a non-null IntVLA; will be modified unless nothing is associated with k 671 * @param k a K object or something that can be treated as one to search for 672 * @return the number of items added to container; 0 if none were added 673 */ 674 public int append(final IntVLA container, final Object k) { 675 if (k == null) 676 { 677 if(containsNullKey) { 678 container.addAll(value[n]); 679 return value[n].size; 680 } 681 else 682 return 0; 683 } 684 K curr; 685 final K[] key = this.key; 686 int pos; 687 // The starting point. 688 if ((curr = key[pos = (hasher.hash(k)) & mask]) == null) 689 return 0; 690 if (hasher.areEqual(k, curr)) { 691 container.addAll(value[pos]); 692 return value[pos].size; 693 } 694 // There's always an unused entry. 695 while (true) { 696 if ((curr = key[pos = (pos + 1) & mask]) == null) 697 return 0; 698 if (hasher.areEqual(k, curr)) 699 { 700 container.addAll(value[pos]); 701 return value[pos].size; 702 } 703 } 704 } 705 706 public boolean containsKey(final Object k) { 707 if (k == null) 708 return containsNullKey; 709 K curr; 710 final K[] key = this.key; 711 int pos; 712 // The starting point. 713 if ((curr = key[pos = (hasher.hash(k)) & mask]) == null) 714 return false; 715 if (hasher.areEqual(k, curr)) 716 return true; 717 // There's always an unused entry. 718 while (true) { 719 if ((curr = key[pos = (pos + 1) & mask]) == null) 720 return false; 721 if (hasher.areEqual(k, curr)) 722 return true; 723 } 724 } 725 public boolean containsValue(final int v) { 726 return v >= 0 && v < order.size; 727 } 728 public boolean containsValue(final Object ov) { 729 return ov != null && containsValue(((Integer) ov).intValue()); 730 } 731 /* 732 * Removes all elements from this map. 733 * 734 * <P>To increase object reuse, this method does not change the table size. 735 * If you want to reduce the table size, you must use {@link #trim()}. 736 */ 737 public void clear() { 738 if (size == 0) 739 return; 740 size = 0; 741 containsNullKey = false; 742 Arrays.fill(key, null); 743 Arrays.fill(value, null); 744 first = last = -1; 745 order.clear(); 746 } 747 748 public int size() { 749 return order.size; 750 } 751 752 public boolean isEmpty() { 753 return size == 0; 754 } 755 756 /** 757 * Returns an iterator over elements of type {@code T}. 758 * 759 * @return an Iterator. 760 */ 761 @Override 762 public Iterator<K> iterator() { 763 return new KeyIterator(); 764 } 765 766 protected void fixOrder(final int i) { 767 if (size == 0) { 768 order.clear(); 769 first = last = -1; 770 return; 771 } 772 order.removeValue(i); 773 if (first == i) { 774 first = order.get(0); 775 //first = (int) link[i]; 776 /* 777 if (0 <= first) { 778 // Special case of SET_PREV( link[ first ], -1 ) 779 link[first] |= (-1 & 0xFFFFFFFFL) << 32; 780 } 781 return; 782 */ 783 } 784 if (last == i) { 785 last = order.peek(); 786 //last = (int) (link[i] >>> 32); 787 /*if (0 <= last) { 788 // Special case of SET_NEXT( link[ last ], -1 ) 789 link[last] |= -1 & 0xFFFFFFFFL; 790 } 791 return; 792 */ 793 } 794 /* 795 final long linki = link[i]; 796 final int prev = (int) (linki >>> 32); 797 final int next = (int) linki; 798 link[prev] ^= ((link[prev] ^ (linki & 0xFFFFFFFFL)) & 0xFFFFFFFFL); 799 link[next] ^= ((link[next] ^ (linki & 0xFFFFFFFF00000000L)) & 0xFFFFFFFF00000000L); 800 */ 801 } 802 803 /** 804 * Modifies the link vector for a shift from s to d. 805 * <br> 806 * This method will complete in logarithmic time or better. 807 * 808 * @param s the source position. 809 * @param d the destination position. 810 */ 811 protected void fixOrder(int s, int d) { 812 if (order.size == 1) { 813 first = last = d; 814 // Special case of SET_UPPER_LOWER( link[ d ], -1, -1 ) 815 //link[d] = -1L; 816 order.set(0, d); 817 } 818 else if (first == s) { 819 first = d; 820 order.set(0, d); 821 //link[(int) link[s]] ^= ((link[(int) link[s]] ^ ((d & 0xFFFFFFFFL) << 32)) & 0xFFFFFFFF00000000L); 822 //link[d] = link[s]; 823 } 824 else if (last == s) { 825 last = d; 826 order.set(order.size - 1, d); 827 //link[(int) (link[s] >>> 32)] ^= ((link[(int) (link[s] >>> 32)] ^ (d & 0xFFFFFFFFL)) & 0xFFFFFFFFL); 828 //link[d] = link[s]; 829 } 830 else 831 { 832 order.set(order.indexOf(s), d); 833 } 834 /* 835 final long links = link[s]; 836 final int prev = (int) (links >>> 32); 837 final int next = (int) links; 838 link[prev] ^= ((link[prev] ^ (d & 0xFFFFFFFFL)) & 0xFFFFFFFFL); 839 link[next] ^= ((link[next] ^ ((d & 0xFFFFFFFFL) << 32)) & 0xFFFFFFFF00000000L); 840 link[d] = links; 841 */ 842 } 843 844 /** 845 * Returns the first key of this map in iteration order. 846 * 847 * @return the first key in iteration order. 848 */ 849 public K firstKey() { 850 if (size == 0) 851 throw new NoSuchElementException(); 852 return key[first]; 853 } 854 /** 855 * Returns the last key of this map in iteration order. 856 * 857 * @return the last key in iteration order. 858 */ 859 public K lastKey() { 860 if (size == 0) 861 throw new NoSuchElementException(); 862 return key[last]; 863 } 864 /** 865 * Retains in this collection only elements from the given collection. 866 * 867 * @param c a collection. 868 * @return <code>true</code> if this collection changed as a result of the 869 * call. 870 */ 871 public boolean retainAll(Collection<?> c) { 872 boolean retVal = false; 873 int n = order.size; 874 while (n-- != 0) { 875 if (!c.contains(key[order.get(n)])) { 876 removeAt(n); 877 retVal = true; 878 } 879 } 880 return retVal; 881 } 882 883 public Comparator<? super K> comparator() { 884 return null; 885 } 886 public SortedMap<K, Integer> tailMap(K from) { 887 throw new UnsupportedOperationException(); 888 } 889 public SortedMap<K, Integer> headMap(K to) { 890 throw new UnsupportedOperationException(); 891 } 892 public SortedMap<K, Integer> subMap(K from, K to) { 893 throw new UnsupportedOperationException(); 894 } 895 /** 896 * A list iterator over a MultiArrangement. 897 * 898 * <P> 899 * This class provides a list iterator over a MultiArrangement. The 900 * constructor runs in constant time. 901 */ 902 private class MapIterator { 903 /** 904 * The entry that will be returned by the next call to 905 * {@link ListIterator#previous()} (or <code>null</code> if no 906 * previous entry exists). 907 */ 908 int prev = -1; 909 /** 910 * The entry that will be returned by the next call to 911 * {@link ListIterator#next()} (or <code>null</code> if no 912 * next entry exists). 913 */ 914 int next = -1; 915 /** 916 * The last entry that was returned (or -1 if we did not iterate or used 917 * {@link Iterator#remove()}). 918 */ 919 int curr = -1; 920 /** 921 * The current index (in the sense of a {@link ListIterator}). 922 * Note that this value is not meaningful when this iterator has been 923 * created using the nonempty constructor. 924 */ 925 int index; 926 private MapIterator() { 927 next = first; 928 index = 0; 929 } 930 /* 931 private MapIterator(final K from) { 932 if (((from) == null)) { 933 if (containsNullKey) { 934 next = (int) link[n]; 935 prev = n; 936 return; 937 } else 938 throw new NoSuchElementException("The key null" 939 + " does not belong to this map."); 940 } 941 if (((key[last]) != null && (key[last]).equals(from))) { 942 prev = last; 943 index = size; 944 return; 945 } 946 // The starting point. 947 int pos = (((from).hashCode())) 948 & mask; 949 // There's always an unused entry. 950 while (!((key[pos]) == null)) { 951 if (((key[pos]).equals(from))) { 952 // Note: no valid index known. 953 next = (int) link[pos]; 954 prev = pos; 955 return; 956 } 957 pos = (pos + 1) & mask; 958 } 959 throw new NoSuchElementException("The key " + from 960 + " does not belong to this map."); 961 }*/ 962 public boolean hasNext() { 963 return next != -1; 964 } 965 public boolean hasPrevious() { 966 return prev != -1; 967 } 968 private void ensureIndexKnown() { 969 if (index >= 0) 970 return; 971 if (prev == -1) { 972 index = 0; 973 return; 974 } 975 if (next == -1) { 976 index = order.size; 977 return; 978 } 979 index = 0; 980 /*while (pos != prev) { 981 pos = (int) link[pos]; 982 index++; 983 }*/ 984 } 985 public int nextIndex() { 986 ensureIndexKnown(); 987 return index + 1; 988 } 989 public int previousIndex() { 990 ensureIndexKnown(); 991 return index - 1; 992 } 993 public int nextEntry() { 994 if (!hasNext()) 995 throw new NoSuchElementException(); 996 curr = next; 997 if(++index >= order.size) 998 next = -1; 999 else 1000 next = order.get(index);//(int) link[curr]; 1001 prev = curr; 1002 return curr; 1003 } 1004 public int previousEntry() { 1005 if (!hasPrevious()) 1006 throw new NoSuchElementException(); 1007 curr = prev; 1008 if(--index < 1) 1009 prev = -1; 1010 else 1011 prev = order.get(index - 1); 1012 //prev = (int) (link[curr] >>> 32); 1013 next = curr; 1014 return curr; 1015 } 1016 public void remove() { 1017 ensureIndexKnown(); 1018 if (curr == -1) 1019 throw new IllegalStateException(); 1020 if (curr == prev) { 1021 /* 1022 * If the last operation was a next(), we are removing an entry 1023 * that precedes the current index, and thus we must decrement 1024 * it. 1025 */ 1026 if(--index >= 1) 1027 prev = order.get(index - 1); //(int) (link[curr] >>> 32); 1028 else 1029 prev = -1; 1030 } else { 1031 if(index < order.size - 1) 1032 next = order.get(index + 1); 1033 else 1034 next = -1; 1035 } 1036 /* 1037 * Now we manually fix the pointers. Because of our knowledge of 1038 * next and prev, this is going to be faster than calling 1039 * fixOrder(). 1040 */ 1041 if (prev == -1) 1042 first = next; 1043 if (next == -1) 1044 last = prev; 1045 final IntVLA iv = value[order.removeIndex(index)]; 1046 iv.removeValue(index); 1047 if(iv.size == 0) 1048 size--; 1049 int last, slot, pos = curr; 1050 curr = -1; 1051 if (pos == n) { 1052 containsNullKey = false; 1053 key[n] = null; 1054 } else { 1055 K curr; 1056 final K[] key = MultiArrangement.this.key; 1057 // We have to horribly duplicate the shiftKeys() code because we 1058 // need to update next/prev. 1059 for (;;) { 1060 pos = ((last = pos) + 1) & mask; 1061 for (;;) { 1062 if ((curr = key[pos]) == null) { 1063 key[last] = null; 1064 fixValues(); 1065 return; 1066 } 1067 slot = (hasher.hash(curr)) & mask; 1068 if (last <= pos 1069 ? last >= slot || slot > pos 1070 : last >= slot && slot > pos) 1071 break; 1072 pos = (pos + 1) & mask; 1073 } 1074 key[last] = curr; 1075 if (next == pos) 1076 next = last; 1077 if (prev == pos) 1078 prev = last; 1079 fixOrder(pos, last); 1080 } 1081 } 1082 } 1083 public int skip(final int n) { 1084 int i = n; 1085 while (i-- != 0 && hasNext()) 1086 nextEntry(); 1087 return n - i - 1; 1088 } 1089 public int back(final int n) { 1090 int i = n; 1091 while (i-- != 0 && hasPrevious()) 1092 previousEntry(); 1093 return n - i - 1; 1094 } 1095 } 1096 1097 /** 1098 * An iterator on keys. 1099 * <p> 1100 * <P>We simply override the {@link ListIterator#next()}/{@link ListIterator#previous()} methods (and possibly their type-specific counterparts) so that they return keys 1101 * instead of entries. 1102 */ 1103 public final class KeyIterator extends MapIterator implements Iterator<K>, Serializable { 1104 private static final long serialVersionUID = 0L; 1105 public K previous() { 1106 return key[previousEntry()]; 1107 } 1108 public void set(K k) { 1109 throw new UnsupportedOperationException(); 1110 } 1111 public void add(K k) { 1112 throw new UnsupportedOperationException(); 1113 } 1114 public KeyIterator() {} 1115 public K next() { 1116 return key[nextEntry()]; 1117 } 1118 public void remove() { super.remove(); } 1119 } 1120 1121 public final class KeyList extends AbstractList<K> implements Serializable { 1122 private static final long serialVersionUID = 0L; 1123 1124 public KeyIterator iterator() { 1125 return new KeyIterator(); 1126 } 1127 1128 public int size() { 1129 return order.size; 1130 } 1131 1132 public void clear() { 1133 MultiArrangement.this.clear(); 1134 } 1135 1136 public K first() { 1137 if (size == 0) throw new NoSuchElementException(); 1138 return key[first]; 1139 } 1140 1141 public K last() { 1142 if (size == 0) throw new NoSuchElementException(); 1143 return key[last]; 1144 } 1145 1146 @SuppressWarnings("unchecked") 1147 @Override 1148 public <T> T[] toArray(T[] a) { 1149 if (a == null || a.length < size()) a = (T[]) new Object[size()]; 1150 unwrap(iterator(), a); 1151 return a; 1152 } 1153 1154 /** 1155 * Always throws an UnsupportedOperationException 1156 */ 1157 public boolean remove(Object ok) { 1158 throw new UnsupportedOperationException("Cannot remove from the key set directly"); 1159 } 1160 1161 /** 1162 * Always throws an UnsupportedOperationException 1163 */ 1164 public boolean add(final K o) { 1165 throw new UnsupportedOperationException("Cannot add to the key set directly"); 1166 } 1167 1168 /** 1169 * {@inheritDoc} 1170 * 1171 * @param index 1172 * @throws IndexOutOfBoundsException {@inheritDoc} 1173 */ 1174 @Override 1175 public K get(int index) { 1176 return keyAt(index); 1177 } 1178 1179 /** 1180 * Delegates to the corresponding type-specific method. 1181 */ 1182 public boolean contains(final Object o) { 1183 return containsKey(o); 1184 } 1185 1186 /** 1187 * Checks whether this collection contains all elements from the given type-specific collection. 1188 * 1189 * @param c a type-specific collection. 1190 * @return <code>true</code> if this collection contains all elements of the argument. 1191 */ 1192 public boolean containsAll(Collection<?> c) { 1193 final Iterator<?> i = c.iterator(); 1194 int n = c.size(); 1195 while (n-- != 0) 1196 if (!contains(i.next())) return false; 1197 return true; 1198 } 1199 1200 /** 1201 * Retains in this collection only elements from the given type-specific collection. 1202 * 1203 * @param c a type-specific collection. 1204 * @return <code>true</code> if this collection changed as a result of the call. 1205 */ 1206 public boolean retainAll(Collection<?> c) { 1207 throw new UnsupportedOperationException("Cannot remove from the key set directly"); 1208 } 1209 1210 /** 1211 * Remove from this collection all elements in the given type-specific collection. 1212 * 1213 * @param c a type-specific collection. 1214 * @return <code>true</code> if this collection changed as a result of the call. 1215 */ 1216 public boolean removeAll(Collection<?> c) { 1217 throw new UnsupportedOperationException("Cannot remove from the key set directly"); 1218 } 1219 1220 public Object[] toArray() { 1221 final Object[] a = new Object[size()]; 1222 objectUnwrap(iterator(), a); 1223 return a; 1224 } 1225 1226 /** 1227 * Always throws an UnsupportedOperationException. 1228 * @param c disregarded; always throws Exception 1229 * @return nothing; always throws Exception 1230 */ 1231 public boolean addAll(Collection<? extends K> c) { 1232 throw new UnsupportedOperationException("Cannot add to the key set directly"); 1233 } 1234 1235 @Override 1236 public boolean equals(final Object o) { 1237 if (o == this) 1238 return true; 1239 if (!(o instanceof List)) 1240 return false; 1241 1242 KeyIterator e1 = iterator(); 1243 ListIterator<?> e2 = ((List<?>) o).listIterator(); 1244 while (e1.hasNext() && e2.hasNext()) { 1245 K o1 = e1.next(); 1246 Object o2 = e2.next(); 1247 if (!(o1==null ? o2==null : o1.equals(o2))) 1248 return false; 1249 } 1250 return !(e1.hasNext() || e2.hasNext()); 1251 } 1252 /** 1253 * Unwraps an iterator into an array starting at a given offset for a given number of elements. 1254 * <p> 1255 * <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 1256 * 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). 1257 * 1258 * @param i a type-specific iterator. 1259 * @param array an array to contain the output of the iterator. 1260 * @param offset the first element of the array to be returned. 1261 * @param max the maximum number of elements to unwrap. 1262 * @return the number of elements unwrapped. 1263 */ 1264 public int unwrap(final KeyIterator i, final Object[] array, int offset, final int max) { 1265 if (max < 0) throw new IllegalArgumentException("The maximum number of elements (" + max + ") is negative"); 1266 if (offset < 0 || offset + max > array.length) throw new IllegalArgumentException(); 1267 int j = max; 1268 while (j-- != 0 && i.hasNext()) 1269 array[offset++] = i.next(); 1270 return max - j - 1; 1271 } 1272 1273 /** 1274 * Unwraps an iterator into an array. 1275 * <p> 1276 * <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 1277 * of the array has been reached. 1278 * 1279 * @param i a type-specific iterator. 1280 * @param array an array to contain the output of the iterator. 1281 * @return the number of elements unwrapped. 1282 */ 1283 public int unwrap(final KeyIterator i, final Object[] array) { 1284 return unwrap(i, array, 0, array.length); 1285 } 1286 1287 public boolean isEmpty() { 1288 return size() == 0; 1289 } 1290 1291 @Override 1292 public String toString() { 1293 final StringBuilder s = new StringBuilder(); 1294 final KeyIterator i = iterator(); 1295 int n = size(); 1296 boolean first = true; 1297 s.append("{"); 1298 while (n-- != 0) { 1299 if (first) first = false; 1300 else s.append(", "); 1301 s.append(i.next()); 1302 } 1303 s.append("}"); 1304 return s.toString(); 1305 } 1306 } 1307 1308 public KeyList keyList() { 1309 if (keys == null) keys = new KeyList(); 1310 return keys; 1311 } 1312 1313 public ArrayList<K> keysAsArrayList() 1314 { 1315 ArrayList<K> al = new ArrayList<>(order.size); 1316 for (int i = 0; i < order.size; i++) { 1317 al.add(keyAt(i)); 1318 } 1319 return al; 1320 } 1321 1322 /** 1323 * An iterator on values. 1324 * <p> 1325 * <P>We simply override the {@link ListIterator#next()}/{@link ListIterator#previous()} methods (and possibly their type-specific counterparts) so that they return values 1326 * instead of entries. 1327 */ 1328 public final class ValueIterator extends MapIterator implements ListIterator<Integer>, Serializable { 1329 private static final long serialVersionUID = 0L; 1330 1331 public Integer previous() { 1332 return (index < 0) ? -1 : --index; 1333 } 1334 public int previousInt() { 1335 return (index < 0) ? -1 : --index; 1336 } 1337 public void set(Integer v) { 1338 throw new UnsupportedOperationException(); 1339 } 1340 public void add(Integer v) { 1341 throw new UnsupportedOperationException(); 1342 } 1343 public ValueIterator() {} 1344 public Integer next() { 1345 return (index >= order.size - 1) ? -1 : ++index; 1346 } 1347 public int nextInt() { 1348 return (index >= order.size - 1) ? -1 : ++index; 1349 } 1350 public void remove() { super.remove(); } 1351 } 1352 public final class ValueCollection extends AbstractCollection<Integer> implements Serializable 1353 { 1354 private static final long serialVersionUID = 0L; 1355 public ValueIterator iterator() { 1356 return new ValueIterator(); 1357 } 1358 public int size() { 1359 return size; 1360 } 1361 public boolean contains(Object v) { 1362 return containsValue(v); 1363 } 1364 public void clear() { 1365 MultiArrangement.this.clear(); 1366 } 1367 } 1368 public ArrayList<Integer> values() { 1369 ArrayList<Integer> v = new ArrayList<>(order.size); 1370 for (int i = 0; i < order.size; i++) { 1371 v.add(i); 1372 } 1373 return v; 1374 } 1375 1376 public ArrayList<Integer> valuesAsList() 1377 { 1378 return values(); 1379 } 1380 1381 public IntVLA valuesAsIntVLA() 1382 { 1383 return new IntVLA(ArrayTools.range(size)); 1384 } 1385 public int[] valuesAsArray() 1386 { 1387 return ArrayTools.range(size); 1388 } 1389 1390 /** 1391 * Rehashes the map, making the table as small as possible. 1392 * <p> 1393 * <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. 1394 * <p> 1395 * <P>If the table size is already the minimum possible, this method does nothing. 1396 * 1397 * @return true if there was enough memory to trim the map. 1398 * @see #trim(int) 1399 */ 1400 public boolean trim() { 1401 final int l = arraySize(size, f); 1402 if (l >= n || size > maxFill(l, f)) return true; 1403 try { 1404 rehash(l); 1405 } catch (Exception cantDoIt) { 1406 return false; 1407 } 1408 return true; 1409 } 1410 1411 /** 1412 * Rehashes this map if the table is too large. 1413 * <p> 1414 * <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 1415 * <var>N</var>, this method does nothing. Otherwise, it rehashes this map in a table of size <var>N</var>. 1416 * <p> 1417 * <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 1418 * size to avoid keeping around a very large table just because of a few large transient maps. 1419 * 1420 * @param n the threshold for the trimming. 1421 * @return true if there was enough memory to trim the map. 1422 * @see #trim() 1423 */ 1424 public boolean trim(final int n) { 1425 final int l = HashCommon.nextPowerOfTwo((int) Math.ceil(n / f)); 1426 if (l >= n || size > maxFill(l, f)) return true; 1427 try { 1428 rehash(l); 1429 } catch (Exception cantDoIt) { 1430 return false; 1431 } 1432 return true; 1433 } 1434 1435 /** 1436 * Rehashes the map. 1437 * 1438 * <P> 1439 * This method implements the basic rehashing strategy, and may be overriden 1440 * by subclasses implementing different rehashing strategies (e.g., 1441 * disk-based rehashing). However, you should not override this method 1442 * unless you understand the internal workings of this class. 1443 * 1444 * @param newN 1445 * the new size 1446 */ 1447 1448 @SuppressWarnings("unchecked") 1449 protected void rehash(final int newN) { 1450 final K[] key = this.key; 1451 final IntVLA[] value = this.value; 1452 final int mask = newN - 1; // Note that this is used by the hashing macro 1453 final K[] newKey = (K[]) new Object[newN + 1]; 1454 K k; 1455 final IntVLA[] newValue = new IntVLA[newN + 1]; 1456 int i, pos, sz = order.size, originalFirst = first, originalLast = last; 1457 for (int q = 0; q < sz; q++) { 1458 i = order.get(q); 1459 if ((k = key[i]) == null) 1460 pos = newN; 1461 else { 1462 pos = (hasher.hash(k)) & mask; 1463 while (!(newKey[pos] == null)) 1464 pos = (pos + 1) & mask; 1465 } 1466 newKey[pos] = k; 1467 newValue[pos] = value[i]; 1468 order.set(q, pos); 1469 if(i == originalFirst) 1470 first = pos; 1471 if(i == originalLast) 1472 last = pos; 1473 } 1474 n = newN; 1475 this.mask = mask; 1476 maxFill = maxFill(n, f); 1477 this.key = newKey; 1478 this.value = newValue; 1479 } 1480 /** 1481 * Returns a deep copy of this map. 1482 * 1483 * <P> 1484 * This method performs a deep copy of this MultiArrangement; the data stored in the 1485 * map, however, is not cloned. Note that this makes a difference only for 1486 * object keys. 1487 * 1488 * @return a deep copy of this map. 1489 */ 1490 @SuppressWarnings("unchecked") 1491 @GwtIncompatible 1492 public MultiArrangement<K> clone() { 1493 MultiArrangement<K> c; 1494 try { 1495 c = (MultiArrangement<K>) super.clone(); 1496 c.key = (K[]) new Object[n + 1]; 1497 System.arraycopy(key, 0, c.key, 0, n + 1); 1498 c.value = new IntVLA[n + 1]; 1499 System.arraycopy(value, 0, c.value, 0, n + 1); 1500 c.order = (IntVLA) order.clone(); 1501 c.hasher = hasher; 1502 return c; 1503 } catch (Exception cantHappen) { 1504 throw new UnsupportedOperationException(cantHappen + (cantHappen.getMessage() != null ? 1505 "; " + cantHappen.getMessage() : "")); 1506 } 1507 } 1508 /** 1509 * Returns a hash code for this map. 1510 * 1511 * This method overrides the generic method provided by the superclass. 1512 * Since <code>equals()</code> is not overriden, it is important that the 1513 * value returned by this method is the same value as the one returned by 1514 * the overriden method. 1515 * 1516 * @return a hash code for this map. 1517 */ 1518 public int hashCode() { 1519 int h = 0; 1520 for (int j = realSize(), i = 0, t = 0; j-- != 0;) { 1521 while (key[i] == null) 1522 i++; 1523 if (this != key[i]) 1524 t = hasher.hash(key[i]); 1525 t ^= value[i].hashHive(); 1526 h += t; 1527 i++; 1528 } 1529 // Zero / null keys have hash zero. 1530 if (containsNullKey) 1531 h += value[n].hashHive(); 1532 return h; 1533 } 1534 /** 1535 * Returns the maximum number of entries that can be filled before rehashing. 1536 * 1537 * @param n the size of the backing array. 1538 * @param f the load factor. 1539 * @return the maximum number of entries before rehashing. 1540 */ 1541 public static int maxFill(final int n, final float f) { 1542 /* We must guarantee that there is always at least 1543 * one free entry (even with pathological load factors). */ 1544 return Math.min((int) Math.ceil(n * f), n - 1); 1545 } 1546 1547 /** 1548 * Returns the maximum number of entries that can be filled before rehashing. 1549 * 1550 * @param n the size of the backing array. 1551 * @param f the load factor. 1552 * @return the maximum number of entries before rehashing. 1553 */ 1554 public static long maxFill(final long n, final float f) { 1555 /* We must guarantee that there is always at least 1556 * one free entry (even with pathological load factors). */ 1557 return Math.min((long) Math.ceil(n * f), n - 1); 1558 } 1559 1560 /** 1561 * 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>. 1562 * 1563 * @param expected the expected number of elements in a hash table. 1564 * @param f the load factor. 1565 * @return the minimum possible size for a backing array. 1566 * @throws IllegalArgumentException if the necessary size is larger than 2<sup>30</sup>. 1567 */ 1568 public static int arraySize(final int expected, final float f) { 1569 final long s = Math.max(2, HashCommon.nextPowerOfTwo((long) Math.ceil(expected / f))); 1570 if (s > (1 << 30)) 1571 throw new IllegalArgumentException("Too large (" + expected + " expected elements with load factor " + f + ")"); 1572 return (int) s; 1573 } 1574 1575 /** 1576 * Unwraps an iterator into an array starting at a given offset for a given number of elements. 1577 * <p> 1578 * <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 1579 * 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). 1580 * 1581 * @param i a type-specific iterator. 1582 * @param array an array to contain the output of the iterator. 1583 * @param offset the first element of the array to be returned. 1584 * @param max the maximum number of elements to unwrap. 1585 * @return the number of elements unwrapped. 1586 */ 1587 private int unwrap(final ValueIterator i, final Object[] array, int offset, final int max) { 1588 if (max < 0) throw new IllegalArgumentException("The maximum number of elements (" + max + ") is negative"); 1589 if (offset < 0 || offset + max > array.length) throw new IllegalArgumentException(); 1590 int j = max; 1591 while (j-- != 0 && i.hasNext()) 1592 array[offset++] = i.next(); 1593 return max - j - 1; 1594 } 1595 1596 /** 1597 * Unwraps an iterator into an array. 1598 * <p> 1599 * <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 1600 * of the array has been reached. 1601 * 1602 * @param i a type-specific iterator. 1603 * @param array an array to contain the output of the iterator. 1604 * @return the number of elements unwrapped. 1605 */ 1606 private int unwrap(final ValueIterator i, final Object[] array) { 1607 return unwrap(i, array, 0, array.length); 1608 } 1609 1610 1611 /** Unwraps an iterator into an array starting at a given offset for a given number of elements. 1612 * 1613 * <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 1614 * 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). 1615 * 1616 * @param i a type-specific iterator. 1617 * @param array an array to contain the output of the iterator. 1618 * @param offset the first element of the array to be returned. 1619 * @param max the maximum number of elements to unwrap. 1620 * @return the number of elements unwrapped. */ 1621 private static <K> int objectUnwrap(final Iterator<? extends K> i, final K[] array, int offset, final int max ) { 1622 if ( max < 0 ) throw new IllegalArgumentException( "The maximum number of elements (" + max + ") is negative" ); 1623 if ( offset < 0 || offset + max > array.length ) throw new IllegalArgumentException(); 1624 int j = max; 1625 while ( j-- != 0 && i.hasNext() ) 1626 array[ offset++ ] = i.next(); 1627 return max - j - 1; 1628 } 1629 1630 /** Unwraps an iterator into an array. 1631 * 1632 * <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 1633 * of the array has been reached. 1634 * 1635 * @param i a type-specific iterator. 1636 * @param array an array to contain the output of the iterator. 1637 * @return the number of elements unwrapped. */ 1638 private static <K> int objectUnwrap(final Iterator<? extends K> i, final K[] array) { 1639 return objectUnwrap(i, array, 0, array.length ); 1640 } 1641 1642 @Override 1643 public String toString() { 1644 final StringBuilder s = new StringBuilder(); 1645 int n = size(), i = 0; 1646 boolean first = true; 1647 s.append("Arrangement{"); 1648 while (i < n) { 1649 if (first) first = false; 1650 else s.append(", "); 1651 s.append(keyAt(i)).append(':').append(i++); 1652 } 1653 s.append("}"); 1654 return s.toString(); 1655 } 1656 @Override 1657 public boolean equals(Object o) { 1658 if (o == this) 1659 return true; 1660 if (!(o instanceof MultiArrangement)) 1661 return false; 1662 MultiArrangement<?> m = (MultiArrangement<?>) o; 1663 if (m.size() != size()) 1664 return false; 1665 if(!m.order.equals(order)) 1666 return false; 1667 for (int i = 0; i < order.size; i++) { 1668 if(!keyAt(i).equals(m.keyAt(i))) return false; 1669 } 1670 return true; 1671 } 1672 1673 1674 /** 1675 * Gets the value at the given index in the iteration order in constant time (random-access). 1676 * @param idx the index in the iteration order of the value to fetch 1677 * @return the value at the index, if the index is valid, otherwise the default return value 1678 */ 1679 public int getAt(final int idx) { 1680 if (idx < 0 || idx >= order.size) 1681 return defRetValue; 1682 return idx; 1683 } 1684 /** 1685 * Gets the key at the given index in the iteration order in constant time (random-access). 1686 * @param idx the index in the iteration order of the key to fetch 1687 * @return the key at the index, if the index is valid, otherwise null 1688 */ 1689 public K keyAt(final int idx) { 1690 if (idx < 0 || idx >= order.size) 1691 return null; 1692 // The starting point. 1693 return key[order.get(idx)]; 1694 } 1695 1696 /** 1697 * Removes the key and value at the given index in the iteration order in not-exactly constant time (though it still 1698 * should be efficient). 1699 * @param idx the index in the iteration order of the key and value to remove 1700 * @return the key removed, if there was anything removed, or null otherwise 1701 */ 1702 public K removeAt(final int idx) { 1703 1704 if (idx < 0 || idx >= order.size) 1705 return null; 1706 int pos = order.get(idx); 1707 K k; 1708 if ((k = key[pos]) == null) { 1709 if (containsNullKey) { 1710 removeNullEntry(); 1711 } 1712 return null; 1713 } 1714 removeEntry(pos); 1715 return k; 1716 } 1717 1718 /** 1719 * Equivalent to {@link #add(Object)}, except that it can place k at any point in the ordering (shifting up later 1720 * entries and changing their values to match their new positions in the ordering). 1721 * @param idx the position in the ordering to place k at; will not be used if negative or greater than the current size (it can be equal to the current size) 1722 * @param k the key to add into this MultiArrangement; its value will be idx 1723 * @return the previous position in the ordering that k had if already present, the previous size of the MultiArrangement if k was just added now, or -1 if idx is invalid 1724 */ 1725 public int addAt(final int idx, final K k) { 1726 if(idx < 0 || idx > order.size) 1727 return -1; 1728 final int pos = insertAt(k, idx); 1729 if (pos < 0) return defRetValue; 1730 final IntVLA oldValue = value[pos]; 1731 oldValue.add(idx); 1732 fixValues(); 1733 return idx; 1734 } 1735 1736 /** 1737 * Gets a random key from this MultiArrangement in constant time, using the given IRNG to generate a random number. 1738 * @param rng used to generate a random index for a key 1739 * @return a random key from this MultiArrangement, or null if this is empty 1740 */ 1741 public K randomKey(IRNG rng) 1742 { 1743 if(rng == null) 1744 return null; 1745 return keyAt(rng.nextInt(order.size)); 1746 } 1747 1748 /** 1749 * Randomly alters the iteration order for this MultiArrangement using the given IRNG to shuffle. 1750 * @param rng used to generate a random ordering 1751 * @return this for chaining 1752 */ 1753 public MultiArrangement<K> shuffle(IRNG rng) 1754 { 1755 if(order.size < 2) 1756 return this; 1757 order.shuffle(rng); 1758 first = order.get(0); 1759 last = order.peek(); 1760 fixValues(); 1761 return this; 1762 } 1763 1764 /** 1765 * Given an array or varargs of replacement indices for this MultiArrangement's iteration order, reorders this so the 1766 * first item in the returned version is the same as {@code getAt(ordering[0])} (with some care taken for negative 1767 * or too-large indices), the second item in the returned version is the same as {@code getAt(ordering[1])}, etc. 1768 * <br> 1769 * Negative indices are considered reversed distances from the end of ordering, so -1 refers to the same index as 1770 * {@code ordering[ordering.length - 1]}. If ordering is smaller than {@code size()}, only the indices up to the 1771 * length of ordering will be modified. If ordering is larger than {@code size()}, only as many indices will be 1772 * affected as {@code size()}, and reversed distances are measured from the end of this Map's entries instead of 1773 * the end of ordering. Duplicate values in ordering will produce duplicate values in the returned Map. 1774 * <br> 1775 * This method modifies this MultiArrangement in-place and also returns it for chaining. 1776 * @param ordering an array or varargs of int indices, where the nth item in ordering changes the nth item in this 1777 * Map to have the value currently in this Map at the index specified by the value in ordering 1778 * @return this for chaining, after modifying it in-place 1779 */ 1780 public MultiArrangement<K> reorder(int... ordering) 1781 { 1782 if(ordering == null || ordering.length <= 0) 1783 return this; 1784 order.reorder(ordering); 1785 first = order.get(0); 1786 last = order.peek(); 1787 fixValues(); 1788 return this; 1789 } 1790 private boolean alterEntry(final int pos, final K replacement) { 1791 final IntVLA[] value = this.value; 1792 final IntVLA v = value[pos]; 1793 final int op = order.indexOf(pos); 1794 final boolean isFirst = op == 0, isLast = op == order.size - 1; 1795 shiftKeysValues(pos); 1796 1797 int rep; 1798 if (replacement == null) { 1799 if (containsNullKey) 1800 { 1801 value[n].addAll(v); 1802 return true; 1803 } 1804 rep = n; 1805 containsNullKey = true; 1806 } else { 1807 K curr; 1808 final K[] key = this.key; 1809 1810 // The starting point. 1811 if (!((curr = key[rep = (hasher.hash(replacement)) & mask]) == null)) { 1812 if (hasher.areEqual(curr, replacement)) 1813 { 1814 value[rep].addAll(v); 1815 return true; 1816 } 1817 while ((curr = key[rep = (rep + 1) & mask]) != null) 1818 { 1819 if (hasher.areEqual(curr, replacement)) 1820 { 1821 value[rep].addAll(v); 1822 return true; 1823 } 1824 } 1825 } 1826 key[rep] = replacement; 1827 value[rep] = v; 1828 } 1829 order.set(op, rep); 1830 if(isFirst) 1831 first = rep; 1832 if(isLast) 1833 last = rep; 1834 return false; 1835 } 1836 private boolean alterNullEntry(final K replacement) { 1837 containsNullKey = false; 1838 key[n] = null; 1839 final IntVLA[] value = this.value; 1840 final IntVLA v = value[n]; 1841 value[n] = null; 1842 1843 int rep; 1844 if (replacement == null) { 1845 rep = n; 1846 containsNullKey = true; 1847 } else { 1848 K curr; 1849 final K[] key = this.key; 1850 // The starting point. 1851 if ((curr = key[rep = (hasher.hash(replacement)) & mask]) != null) { 1852 if (hasher.areEqual(curr, replacement)) 1853 { 1854 value[rep].addAll(v); 1855 return true; 1856 } 1857 while ((curr = key[rep = (rep + 1) & mask]) != null) 1858 { 1859 if (hasher.areEqual(curr, replacement)) 1860 { 1861 value[rep].addAll(v); 1862 return true; 1863 } 1864 } 1865 } 1866 key[rep] = replacement; 1867 value[rep] = v; 1868 } 1869 fixOrder(n, rep); 1870 return false; 1871 } 1872 1873 /** 1874 * Swaps a key, original, for another key, replacement, while keeping replacement at the same point in the iteration 1875 * order as original and keeping it associated with the same value (which also keeps its iteration index). 1876 * @param original the key to find and swap out 1877 * @param replacement the key to replace original with 1878 * @return the value associated with original before, and replacement now 1879 */ 1880 public boolean alter(final K original, final K replacement) { 1881 if (original == null) { 1882 if (containsNullKey) { 1883 return alterNullEntry(replacement); 1884 } 1885 else 1886 return add(replacement) >= 0; 1887 } 1888 else if(hasher.areEqual(original, replacement)) 1889 return false; 1890 K curr; 1891 final K[] key = this.key; 1892 int pos; 1893 // The starting point. 1894 if ((curr = key[pos = (hasher.hash(original)) & mask]) == null) 1895 return add(replacement) >= 0; 1896 if (hasher.areEqual(original, curr)) 1897 return alterEntry(pos, replacement); 1898 while (true) { 1899 if ((curr = key[pos = (pos + 1) & mask]) == null) 1900 return add(replacement) >= 0; 1901 if (hasher.areEqual(original, curr)) 1902 return alterEntry(pos, replacement); 1903 } 1904 } 1905 1906 public int[] getArray(K[] keys) 1907 { 1908 if(keys == null) 1909 return new int[0]; 1910 int len = keys.length; 1911 IntVLA container = new IntVLA(len); 1912 for (int i = 0; i < len; i++) { 1913 append(container, keys[i]); 1914 } 1915 return container.toArray(); 1916 } 1917 1918 public int[] getArray(Collection<? extends K> keys) 1919 { 1920 if(keys == null) 1921 return new int[0]; 1922 int len = keys.size(), i = 0; 1923 IntVLA container = new IntVLA(len); 1924 for(K k : keys) 1925 { 1926 append(container, k); 1927 } 1928 return container.toArray(); 1929 } 1930 1931 public IntVLA getMany(Iterable<? extends K> keys) 1932 { 1933 if(keys == null) 1934 return new IntVLA(); 1935 IntVLA vals = new IntVLA(); 1936 for(K k : keys) 1937 { 1938 append(vals, k); 1939 } 1940 return vals; 1941 } 1942 1943 public OrderedSet<K> keysAt(int... positions) 1944 { 1945 if(keys == null || positions == null || positions.length <= 0) 1946 return new OrderedSet<K>(); 1947 OrderedSet<K> ks = new OrderedSet<>(positions.length); 1948 for(int i = 0; i < positions.length; i++) 1949 { 1950 ks.add(keyAt(positions[i])); 1951 } 1952 return ks; 1953 } 1954 public OrderedSet<K> keysAt(IntVLA positions) 1955 { 1956 if(keys == null || positions == null || positions.size <= 0) 1957 return new OrderedSet<K>(); 1958 OrderedSet<K> ks = new OrderedSet<>(positions.size); 1959 for(int i = 0; i < positions.size; i++) 1960 { 1961 ks.add(keyAt(positions.get(i))); 1962 } 1963 return ks; 1964 } 1965 1966 /** 1967 * Produces a copy of this MultiArrangement, but only using up to the given amount of items to take. Does a shallow copy 1968 * of individual keys, so the references will be shared. 1969 * @param amount the number of items to copy from this MultiArrangement; will copy all items if greater than size 1970 * @return a new MultiArrangement with up to amount items copied from this into it. 1971 */ 1972 public MultiArrangement<K> take(int amount) 1973 { 1974 amount = Math.min(order.size, Math.max(0, amount)); 1975 MultiArrangement<K> nx = new MultiArrangement<>(amount, f); 1976 for (int i = 0; i < amount; i++) { 1977 nx.add(keyAt(i)); 1978 } 1979 return nx; 1980 } 1981 protected int positionOf(final Object k) { 1982 if (k == null) 1983 { 1984 return (containsNullKey) ? n : -1; 1985 } 1986 K curr; 1987 final K[] key = this.key; 1988 int pos; 1989 // The starting point. 1990 if ((curr = key[pos = (hasher.hash(k)) & mask]) == null) 1991 return -1; 1992 if (hasher.areEqual(k, curr)) 1993 return pos; 1994 // There's always an unused entry. 1995 while (true) { 1996 if ((curr = key[pos = pos + 1 & mask]) == null) 1997 return -1; 1998 if (hasher.areEqual(k, curr)) 1999 return pos; 2000 } 2001 } 2002 2003 /** 2004 * Swaps the positions in the ordering for the given items, if they are both present. Returns true if the ordering 2005 * changed as a result of this call, or false if it stayed the same (which can be because left or right was not 2006 * present, or because left and right are the same reference (so swapping would do nothing)). 2007 * @param left an item that should be present in this OrderedSet 2008 * @param right an item that should be present in this OrderedSet 2009 * @return true if this OrderedSet changed in ordering as a result of this call, or false otherwise 2010 */ 2011 public boolean swap(final K left, final K right) 2012 { 2013 if(left == right) return false; 2014 int posL = positionOf(left), posR = positionOf(right); 2015 IntVLA l = value[posL]; 2016 if(l == null) return false; 2017 IntVLA r = value[posR]; 2018 if(r == null) return false; 2019 value[posR] = l; 2020 value[posL] = r; 2021 for (int i = 0; i < l.size; i++) { 2022 order.set(l.get(i), posR); 2023 } 2024 for (int i = 0; i < r.size; i++) { 2025 order.set(r.get(i), posL); 2026 } 2027 return true; 2028 } 2029 /** 2030 * Swaps the given indices in the ordering, if they are both ints between 0 and size. Returns true if the ordering 2031 * changed as a result of this call, or false if it stayed the same (which can be because left or right referred to 2032 * an out-of-bounds index, or because left and right are equal (so swapping would do nothing)). 2033 * @param left an index of an item in this OrderedSet, at least 0 and less than {@link #size()} 2034 * @param right an index of an item in this OrderedSet, at least 0 and less than {@link #size()} 2035 * @return true if this OrderedSet changed in ordering as a result of this call, or false otherwise 2036 */ 2037 public boolean swapIndices(final int left, final int right) 2038 { 2039 if(left < 0 || right < 0 || left >= order.size || right >= order.size || left == right) return false; 2040 int posL = order.get(left), posR = order.get(right); 2041 value[posL].set(value[posL].indexOf(left), right); 2042 value[posR].set(value[posR].indexOf(right), left); 2043 order.swap(left, right); 2044 return true; 2045 } 2046 2047}