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