001 002/******************************************************************************* 003 * Copyright 2011 See AUTHORS file. 004 * 005 * Licensed under the Apache License, Version 2.0 (the "License"); 006 * you may not use this file except in compliance with the License. 007 * You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 ******************************************************************************/ 017 018package squidpony.squidmath; 019 020import java.io.Serializable; 021import java.util.NoSuchElementException; 022 023/** An unordered set that uses short keys. This implementation uses cuckoo hashing using 3 hashes, random walking, and a 024 * small stash for problematic keys. No allocation is done except when growing the table size. Used internally by 025 * CoordPacker, and unlikely to be used outside of it. 026 * <br> 027 * This set performs very fast contains and remove (typically O(1), worst case O(log(n))). Add may be a bit slower, 028 * depending on hash collisions. Load factors greater than 0.91 greatly increase the chances the set will have to rehash 029 * to the next higher POT size. 030 * @author Nathan Sweet 031 * Ported from libGDX by Tommy Ettinger on 10/19/2015. 032 */ 033public class ShortSet implements Serializable{ 034 private static final long serialVersionUID = -4390851800502156007L; 035 036 private static final int PRIME2 = 0xb4b82e39; 037 private static final int PRIME3 = 0xced1c241; 038 private static final short EMPTY = 0; 039 040 public int size; 041 042 short[] keyTable; 043 int capacity, stashSize; 044 boolean hasZeroValue; 045 046 private float loadFactor; 047 private int hashShift, threshold; 048 private int stashCapacity; 049 private int pushIterations; 050 private int mask; 051 private static LightRNG rng; 052 053 private ShortSetIterator iterator1, iterator2; 054 055 /** Creates a new sets with an initial capacity of 32 and a load factor of 0.8. This set will hold 25 items before growing the 056 * backing table. */ 057 public ShortSet() { 058 this(32, 0.8f); 059 } 060 061 /** Creates a new set with a load factor of 0.8. This set will hold initialCapacity * 0.8 items before growing the backing 062 * table. */ 063 public ShortSet(int initialCapacity) { 064 this(initialCapacity, 0.8f); 065 } 066 067 /** Creates a new set with the specified initial capacity and load factor. This set will hold initialCapacity * loadFactor items 068 * before growing the backing table. */ 069 public ShortSet(int initialCapacity, float loadFactor) { 070 if (initialCapacity < 0) throw new IllegalArgumentException("initialCapacity must be >= 0: " + initialCapacity); 071 if (initialCapacity > 1 << 30) throw new IllegalArgumentException("initialCapacity is too large: " + initialCapacity); 072 capacity = nextPowerOfTwo(initialCapacity); 073 074 rng = new LightRNG(); 075 076 if (loadFactor <= 0) throw new IllegalArgumentException("loadFactor must be > 0: " + loadFactor); 077 this.loadFactor = loadFactor; 078 079 threshold = (int)(capacity * loadFactor); 080 mask = capacity - 1; 081 hashShift = 31 - Integer.numberOfTrailingZeros(capacity); 082 stashCapacity = Math.max(3, (int)Math.ceil(Math.log(capacity)) * 2); 083 pushIterations = Math.max(Math.min(capacity, 8), (int)Math.sqrt(capacity) / 8); 084 085 keyTable = new short[capacity + stashCapacity]; 086 } 087 088 /** Creates a new map identical to the specified map. */ 089 public ShortSet(ShortSet map) { 090 this(map.capacity, map.loadFactor); 091 stashSize = map.stashSize; 092 System.arraycopy(map.keyTable, 0, keyTable, 0, map.keyTable.length); 093 size = map.size; 094 hasZeroValue = map.hasZeroValue; 095 } 096 097 /** Returns true if the key was not already in the set. */ 098 public boolean add (short key) { 099 if (key == 0) { 100 if (hasZeroValue) return false; 101 hasZeroValue = true; 102 size++; 103 return true; 104 } 105 106 short[] keyTable = this.keyTable; 107 108 // Check for existing keys. 109 int index1 = key & mask; 110 short key1 = keyTable[index1]; 111 if (key1 == key) return false; 112 113 int index2 = hash2(key); 114 short key2 = keyTable[index2]; 115 if (key2 == key) return false; 116 117 int index3 = hash3(key); 118 short key3 = keyTable[index3]; 119 if (key3 == key) return false; 120 121 // Find key in the stash. 122 for (int i = capacity, n = i + stashSize; i < n; i++) 123 if (keyTable[i] == key) return false; 124 125 // Check for empty buckets. 126 if (key1 == EMPTY) { 127 keyTable[index1] = key; 128 if (size++ >= threshold) resize(capacity << 1); 129 return true; 130 } 131 132 if (key2 == EMPTY) { 133 keyTable[index2] = key; 134 if (size++ >= threshold) resize(capacity << 1); 135 return true; 136 } 137 138 if (key3 == EMPTY) { 139 keyTable[index3] = key; 140 if (size++ >= threshold) resize(capacity << 1); 141 return true; 142 } 143 144 push(key, index1, key1, index2, key2, index3, key3); 145 return true; 146 } 147 148 public void addAll (ShortVLA array) { 149 addAll(array, 0, array.size); 150 } 151 152 public void addAll (ShortVLA array, int offset, int length) { 153 if (offset + length > array.size) 154 throw new IllegalArgumentException("offset + length must be <= size: " + offset + " + " + length + " <= " + array.size); 155 addAll(array.items, offset, length); 156 } 157 158 public void addAll (short... array) { 159 addAll(array, 0, array.length); 160 } 161 162 public void addAll (short[] array, int offset, int length) { 163 ensureCapacity(length); 164 for (int i = offset, n = i + length; i < n; i++) 165 add(array[i]); 166 } 167 168 public void addAll (ShortSet set) { 169 ensureCapacity(set.size); 170 ShortSetIterator iterator = set.iterator(); 171 while (iterator.hasNext) 172 add(iterator.next()); 173 } 174 175 /** Skips checks for existing keys. */ 176 private void addResize (short key) { 177 if (key == 0) { 178 hasZeroValue = true; 179 return; 180 } 181 182 // Check for empty buckets. 183 int index1 = key & mask; 184 short key1 = keyTable[index1]; 185 if (key1 == EMPTY) { 186 keyTable[index1] = key; 187 if (size++ >= threshold) resize(capacity << 1); 188 return; 189 } 190 191 int index2 = hash2(key); 192 short key2 = keyTable[index2]; 193 if (key2 == EMPTY) { 194 keyTable[index2] = key; 195 if (size++ >= threshold) resize(capacity << 1); 196 return; 197 } 198 199 int index3 = hash3(key); 200 short key3 = keyTable[index3]; 201 if (key3 == EMPTY) { 202 keyTable[index3] = key; 203 if (size++ >= threshold) resize(capacity << 1); 204 return; 205 } 206 207 push(key, index1, key1, index2, key2, index3, key3); 208 } 209 210 private void push (short insertKey, int index1, short key1, int index2, short key2, int index3, short key3) { 211 short[] keyTable = this.keyTable; 212 213 int mask = this.mask; 214 215 // Push keys until an empty bucket is found. 216 short evictedKey; 217 int i = 0, pushIterations = this.pushIterations; 218 do { 219 // Replace the key and value for one of the hashes. 220 switch (rng.nextInt(2)) { 221 case 0: 222 evictedKey = key1; 223 keyTable[index1] = insertKey; 224 break; 225 case 1: 226 evictedKey = key2; 227 keyTable[index2] = insertKey; 228 break; 229 default: 230 evictedKey = key3; 231 keyTable[index3] = insertKey; 232 break; 233 } 234 235 // If the evicted key hashes to an empty bucket, put it there and stop. 236 index1 = evictedKey & mask; 237 key1 = keyTable[index1]; 238 if (key1 == EMPTY) { 239 keyTable[index1] = evictedKey; 240 if (size++ >= threshold) resize(capacity << 1); 241 return; 242 } 243 244 index2 = hash2(evictedKey); 245 key2 = keyTable[index2]; 246 if (key2 == EMPTY) { 247 keyTable[index2] = evictedKey; 248 if (size++ >= threshold) resize(capacity << 1); 249 return; 250 } 251 252 index3 = hash3(evictedKey); 253 key3 = keyTable[index3]; 254 if (key3 == EMPTY) { 255 keyTable[index3] = evictedKey; 256 if (size++ >= threshold) resize(capacity << 1); 257 return; 258 } 259 260 if (++i == pushIterations) break; 261 262 insertKey = evictedKey; 263 } while (true); 264 265 addStash(evictedKey); 266 } 267 268 private void addStash (short key) { 269 if (stashSize == stashCapacity) { 270 // Too many pushes occurred and the stash is full, increase the table size. 271 resize(capacity << 1); 272 add(key); 273 return; 274 } 275 // Store key in the stash. 276 int index = capacity + stashSize; 277 keyTable[index] = key; 278 stashSize++; 279 size++; 280 } 281 282 /** Returns true if the key was removed. */ 283 public boolean remove (short key) { 284 if (key == 0) { 285 if (!hasZeroValue) return false; 286 hasZeroValue = false; 287 size--; 288 return true; 289 } 290 291 int index = key & mask; 292 if (keyTable[index] == key) { 293 keyTable[index] = EMPTY; 294 size--; 295 return true; 296 } 297 298 index = hash2(key); 299 if (keyTable[index] == key) { 300 keyTable[index] = EMPTY; 301 size--; 302 return true; 303 } 304 305 index = hash3(key); 306 if (keyTable[index] == key) { 307 keyTable[index] = EMPTY; 308 size--; 309 return true; 310 } 311 312 return removeStash(key); 313 } 314 315 boolean removeStash (short key) { 316 short[] keyTable = this.keyTable; 317 for (int i = capacity, n = i + stashSize; i < n; i++) { 318 if (keyTable[i] == key) { 319 removeStashIndex(i); 320 size--; 321 return true; 322 } 323 } 324 return false; 325 } 326 327 void removeStashIndex (int index) { 328 // If the removed location was not last, move the last tuple to the removed location. 329 stashSize--; 330 int lastIndex = capacity + stashSize; 331 if (index < lastIndex) keyTable[index] = keyTable[lastIndex]; 332 } 333 334 /** Reduces the size of the backing arrays to be the specified capacity or less. If the capacity is already less, nothing is 335 * done. If the set contains more items than the specified capacity, the next highest power of two capacity is used instead. */ 336 public void shrink (int maximumCapacity) { 337 if (maximumCapacity < 0) throw new IllegalArgumentException("maximumCapacity must be >= 0: " + maximumCapacity); 338 if (size > maximumCapacity) maximumCapacity = size; 339 if (capacity <= maximumCapacity) return; 340 maximumCapacity = nextPowerOfTwo(maximumCapacity); 341 342 resize(maximumCapacity); 343 } 344 345 /** Clears the map and reduces the size of the backing arrays to be the specified capacity if they are larger. */ 346 public void clear (int maximumCapacity) { 347 if (capacity <= maximumCapacity) { 348 clear(); 349 return; 350 } 351 hasZeroValue = false; 352 size = 0; 353 resize(maximumCapacity); 354 } 355 356 public void clear () { 357 if (size == 0) return; 358 short[] keyTable = this.keyTable; 359 for (int i = capacity + stashSize; i-- > 0;) 360 keyTable[i] = EMPTY; 361 size = 0; 362 stashSize = 0; 363 hasZeroValue = false; 364 } 365 366 public boolean contains (short key) { 367 if (key == 0) return hasZeroValue; 368 int index = key & mask; 369 if (keyTable[index] != key) { 370 index = hash2(key); 371 if (keyTable[index] != key) { 372 index = hash3(key); 373 if (keyTable[index] != key) return containsKeyStash(key); 374 } 375 } 376 return true; 377 } 378 379 private boolean containsKeyStash (short key) { 380 short[] keyTable = this.keyTable; 381 for (int i = capacity, n = i + stashSize; i < n; i++) 382 if (keyTable[i] == key) return true; 383 return false; 384 } 385 386 public int first () { 387 if (hasZeroValue) return 0; 388 short[] keyTable = this.keyTable; 389 for (int i = 0, n = capacity + stashSize; i < n; i++) 390 if (keyTable[i] != EMPTY) return keyTable[i]; 391 throw new IllegalStateException("IntSet is empty."); 392 } 393 394 /** Increases the size of the backing array to accommodate the specified number of additional items. Useful before adding many 395 * items to avoid multiple backing array resizes. */ 396 public void ensureCapacity (int additionalCapacity) { 397 int sizeNeeded = size + additionalCapacity; 398 if (sizeNeeded >= threshold) resize(nextPowerOfTwo((int)(sizeNeeded / loadFactor))); 399 } 400 401 private void resize (int newSize) { 402 int oldEndIndex = capacity + stashSize; 403 404 capacity = newSize; 405 threshold = (int)(newSize * loadFactor); 406 mask = newSize - 1; 407 hashShift = 31 - Integer.numberOfTrailingZeros(newSize); 408 stashCapacity = Math.max(3, (int)Math.ceil(Math.log(newSize)) * 2); 409 pushIterations = Math.max(Math.min(newSize, 8), (int)Math.sqrt(newSize) / 8); 410 411 short[] oldKeyTable = keyTable; 412 413 keyTable = new short[newSize + stashCapacity]; 414 415 int oldSize = size; 416 size = hasZeroValue ? 1 : 0; 417 stashSize = 0; 418 if (oldSize > 0) { 419 for (int i = 0; i < oldEndIndex; i++) { 420 short key = oldKeyTable[i]; 421 if (key != EMPTY) addResize(key); 422 } 423 } 424 } 425 426 private int hash2 (int h) { 427 h *= PRIME2; 428 return (h ^ h >>> hashShift) & mask; 429 } 430 431 private int hash3 (int h) { 432 h *= PRIME3; 433 return (h ^ h >>> hashShift) & mask; 434 } 435 436 @Override 437 public int hashCode () { 438 int h = 0; 439 for (int i = 0, n = capacity + stashSize; i < n; i++) 440 if (keyTable[i] != EMPTY) h += keyTable[i]; 441 return h; 442 } 443 444 @Override 445 public boolean equals (Object obj) { 446 if (!(obj instanceof ShortSet)) return false; 447 ShortSet other = (ShortSet)obj; 448 if (other.size != size) return false; 449 if (other.hasZeroValue != hasZeroValue) return false; 450 for (int i = 0, n = capacity + stashSize; i < n; i++) 451 if (keyTable[i] != EMPTY && !other.contains(keyTable[i])) return false; 452 return true; 453 } 454 455 @Override 456 public String toString () { 457 if (size == 0) return "[]"; 458 StringBuilder buffer = new StringBuilder(32); 459 buffer.append('['); 460 short[] keyTable = this.keyTable; 461 int i = keyTable.length; 462 if (hasZeroValue) 463 buffer.append("0"); 464 else { 465 while (i-- > 0) { 466 int key = keyTable[i]; 467 if (key == EMPTY) continue; 468 buffer.append(key); 469 break; 470 } 471 } 472 while (i-- > 0) { 473 int key = keyTable[i]; 474 if (key == EMPTY) continue; 475 buffer.append(", "); 476 buffer.append(key); 477 } 478 buffer.append(']'); 479 return buffer.toString(); 480 } 481 482 private static int nextPowerOfTwo(int n) 483 { 484 int highest = Integer.highestOneBit(n); 485 return (highest == Integer.lowestOneBit(n)) ? highest : highest << 1; 486 } 487 488 /** Returns an iterator for the keys in the set. Remove is supported. Note that the same iterator instance is returned each time 489 * this method is called. Use the {@link ShortSetIterator} constructor for nested or multithreaded iteration. */ 490 public ShortSetIterator iterator () { 491 if (iterator1 == null) { 492 iterator1 = new ShortSetIterator(this); 493 iterator2 = new ShortSetIterator(this); 494 } 495 if (!iterator1.valid) { 496 iterator1.reset(); 497 iterator1.valid = true; 498 iterator2.valid = false; 499 return iterator1; 500 } 501 iterator2.reset(); 502 iterator2.valid = true; 503 iterator1.valid = false; 504 return iterator2; 505 } 506 507 public static ShortSet with (short... array) { 508 ShortSet set = new ShortSet(); 509 set.addAll(array); 510 return set; 511 } 512 513 public static class ShortSetIterator { 514 static final int INDEX_ILLEGAL = -2; 515 static final int INDEX_ZERO = -1; 516 517 public boolean hasNext; 518 519 final ShortSet set; 520 int nextIndex, currentIndex; 521 boolean valid = true; 522 523 public ShortSetIterator(ShortSet set) { 524 this.set = set; 525 reset(); 526 } 527 528 public void reset () { 529 currentIndex = INDEX_ILLEGAL; 530 nextIndex = INDEX_ZERO; 531 if (set.hasZeroValue) 532 hasNext = true; 533 else 534 findNextIndex(); 535 } 536 537 void findNextIndex () { 538 hasNext = false; 539 short[] keyTable = set.keyTable; 540 for (int n = set.capacity + set.stashSize; ++nextIndex < n;) { 541 if (keyTable[nextIndex] != EMPTY) { 542 hasNext = true; 543 break; 544 } 545 } 546 } 547 548 public void remove () { 549 if (currentIndex == INDEX_ZERO && set.hasZeroValue) { 550 set.hasZeroValue = false; 551 } else if (currentIndex < 0) { 552 throw new IllegalStateException("next must be called before remove."); 553 } else if (currentIndex >= set.capacity) { 554 set.removeStashIndex(currentIndex); 555 nextIndex = currentIndex - 1; 556 findNextIndex(); 557 } else { 558 set.keyTable[currentIndex] = EMPTY; 559 } 560 currentIndex = INDEX_ILLEGAL; 561 set.size--; 562 } 563 564 public short next () { 565 if (!hasNext) throw new NoSuchElementException(); 566 if (!valid) throw new RuntimeException("ShortSetIterator cannot be used nested."); 567 short key = nextIndex == INDEX_ZERO ? 0 : set.keyTable[nextIndex]; 568 currentIndex = nextIndex; 569 findNextIndex(); 570 return key; 571 } 572 573 /** Returns a new array containing the remaining keys. */ 574 public ShortVLA toArray () { 575 ShortVLA array = new ShortVLA(true, set.size); 576 while (hasNext) 577 array.add(next()); 578 return array; 579 } 580 } 581}