1 19 package bak.pcj.set; 20 21 import bak.pcj.ShortCollection; 22 import bak.pcj.ShortIterator; 23 import bak.pcj.hash.ShortHashFunction; 24 import bak.pcj.hash.DefaultShortHashFunction; 25 import bak.pcj.util.Exceptions; 26 27 import java.io.Serializable ; 28 import java.io.IOException ; 29 import java.io.ObjectInputStream ; 30 import java.io.ObjectOutputStream ; 31 32 45 public class ShortOpenHashSet extends AbstractShortSet implements ShortSet, Cloneable , Serializable { 46 47 48 private static final int GROWTH_POLICY_RELATIVE = 0; 49 50 51 private static final int GROWTH_POLICY_ABSOLUTE = 1; 52 53 58 private static final int DEFAULT_GROWTH_POLICY = GROWTH_POLICY_RELATIVE; 59 60 61 public static final double DEFAULT_GROWTH_FACTOR = 1.0; 62 63 64 public static final int DEFAULT_GROWTH_CHUNK = 10; 65 66 67 public static final int DEFAULT_CAPACITY = 11; 68 69 70 public static final double DEFAULT_LOAD_FACTOR = 0.75; 71 72 76 private ShortHashFunction keyhash; 77 78 82 private int size; 83 84 89 private transient short[] data; 90 91 92 private transient byte[] states; 93 94 private static final byte EMPTY = 0; 95 private static final byte OCCUPIED = 1; 96 private static final byte REMOVED = 2; 97 98 99 private transient int used; 100 101 105 private int growthPolicy; 106 107 112 private double growthFactor; 113 114 119 private int growthChunk; 120 121 125 private double loadFactor; 126 127 131 private int expandAt; 132 133 private ShortOpenHashSet(ShortHashFunction keyhash, int capacity, int growthPolicy, double growthFactor, int growthChunk, double loadFactor) { 134 if (keyhash == null) 135 Exceptions.nullArgument("hash function"); 136 if (capacity < 0) 137 Exceptions.negativeArgument("capacity", String.valueOf(capacity)); 138 if (growthFactor <= 0.0) 139 Exceptions.negativeOrZeroArgument("growthFactor", String.valueOf(growthFactor)); 140 if (growthChunk <= 0) 141 Exceptions.negativeOrZeroArgument("growthChunk", String.valueOf(growthChunk)); 142 if (loadFactor <= 0.0) 143 Exceptions.negativeOrZeroArgument("loadFactor", String.valueOf(loadFactor)); 144 this.keyhash = keyhash; 145 capacity = bak.pcj.hash.Primes.nextPrime(capacity); 146 data = new short[capacity]; 147 this.states = new byte[capacity]; 148 size = 0; 149 expandAt = (int)Math.round(loadFactor*capacity); 150 used = 0; 151 this.growthPolicy = growthPolicy; 152 this.growthFactor = growthFactor; 153 this.growthChunk = growthChunk; 154 this.loadFactor = loadFactor; 155 } 156 157 private ShortOpenHashSet(int capacity, int growthPolicy, double growthFactor, int growthChunk, double loadFactor) { 158 this(DefaultShortHashFunction.INSTANCE, capacity, growthPolicy, growthFactor, growthChunk, loadFactor); 159 } 160 161 165 public ShortOpenHashSet() { 166 this(DEFAULT_CAPACITY); 167 } 168 169 180 public ShortOpenHashSet(ShortCollection c) { 181 this(); 182 addAll(c); 183 } 184 185 198 public ShortOpenHashSet(short[] a) { 199 this(); 200 for (int i = 0; i < a.length; i++) 201 add(a[i]); 202 } 203 204 214 public ShortOpenHashSet(int capacity) { 215 this(capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR); 216 } 217 218 228 public ShortOpenHashSet(double loadFactor) { 229 this(DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor); 230 } 231 232 246 public ShortOpenHashSet(int capacity, double loadFactor) { 247 this(capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor); 248 } 249 250 273 public ShortOpenHashSet(int capacity, double loadFactor, double growthFactor) { 274 this(capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK, loadFactor); 275 } 276 277 300 public ShortOpenHashSet(int capacity, double loadFactor, int growthChunk) { 301 this(capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor); 302 } 303 304 308 318 public ShortOpenHashSet(ShortHashFunction keyhash) { 319 this(keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR); 320 } 321 322 338 public ShortOpenHashSet(ShortHashFunction keyhash, int capacity) { 339 this(keyhash, capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR); 340 } 341 342 358 public ShortOpenHashSet(ShortHashFunction keyhash, double loadFactor) { 359 this(keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor); 360 } 361 362 382 public ShortOpenHashSet(ShortHashFunction keyhash, int capacity, double loadFactor) { 383 this(keyhash, capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor); 384 } 385 386 415 public ShortOpenHashSet(ShortHashFunction keyhash, int capacity, double loadFactor, double growthFactor) { 416 this(keyhash, capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK, loadFactor); 417 } 418 419 448 public ShortOpenHashSet(ShortHashFunction keyhash, int capacity, double loadFactor, int growthChunk) { 449 this(keyhash, capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor); 450 } 451 452 456 private void ensureCapacity(int elements) { 457 if (elements >= expandAt) { 458 int newcapacity; 459 if (growthPolicy == GROWTH_POLICY_RELATIVE) 460 newcapacity = (int)(data.length * (1.0 + growthFactor)); 461 else 462 newcapacity = data.length + growthChunk; 463 if (newcapacity*loadFactor < elements) 464 newcapacity = (int)Math.round(((double)elements/loadFactor)); 465 newcapacity = bak.pcj.hash.Primes.nextPrime(newcapacity); 466 expandAt = (int)Math.round(loadFactor*newcapacity); 467 468 short[] newdata = new short[newcapacity]; 469 byte[] newstates = new byte[newcapacity]; 470 471 used = 0; 472 for (int i = 0; i < data.length; i++) { 474 if (states[i] == OCCUPIED) { 475 used++; 476 short v = data[i]; 477 int h = Math.abs(keyhash.hash(v)); 479 int n = h % newcapacity; 480 if (newstates[n] == OCCUPIED) { 481 int c = 1 + (h % (newcapacity - 2)); 483 for (;;) { 484 n -= c; 485 if (n < 0) 486 n += newcapacity; 487 if (newstates[n] == EMPTY) 488 break; 489 } 490 } 491 newstates[n] = OCCUPIED; 492 newdata[n] = v; 493 } 494 } 495 496 data = newdata; 497 states = newstates; 498 } 499 } 500 501 505 public boolean add(short v) { 506 ensureCapacity(used+1); 507 508 int h = Math.abs(keyhash.hash(v)); 510 int i = h % data.length; 511 if (states[i] == OCCUPIED) { 512 if (data[i] == v) 513 return false; 514 int c = 1 + (h % (data.length - 2)); 516 for (;;) { 517 i -= c; 518 if (i < 0) 519 i += data.length; 520 if (states[i] == EMPTY || states[i] == REMOVED) 522 break; 523 if (states[i] == OCCUPIED && data[i] == v) 524 return false; 525 } 526 } 527 if (states[i] == EMPTY) 528 used++; 529 states[i] = OCCUPIED; 530 data[i] = v; 531 size++; 532 return true; 533 } 534 535 public ShortIterator iterator() { 536 return new ShortIterator() { 537 int nextEntry = nextEntry(0); 538 int lastEntry = -1; 539 540 int nextEntry(int index) { 541 while (index < data.length && states[index] != OCCUPIED) 542 index++; 543 return index; 544 } 545 546 public boolean hasNext() { 547 return nextEntry < data.length; 548 } 549 550 public short next() { 551 if (!hasNext()) 552 Exceptions.endOfIterator(); 553 lastEntry = nextEntry; 554 nextEntry = nextEntry(nextEntry+1); 555 return data[lastEntry]; 556 } 557 558 public void remove() { 559 if (lastEntry == -1) 560 Exceptions.noElementToRemove(); 561 states[lastEntry] = REMOVED; 562 size--; 563 lastEntry = -1; 564 } 565 }; 566 } 567 568 public void trimToSize() 569 { } 570 571 578 public Object clone() { 579 try { 580 ShortOpenHashSet c = (ShortOpenHashSet)super.clone(); 581 c.data = new short[data.length]; 582 System.arraycopy(data, 0, c.data, 0, data.length); 583 c.states = new byte[data.length]; 584 System.arraycopy(states, 0, c.states, 0, states.length); 585 return c; 586 } catch (CloneNotSupportedException e) { 587 Exceptions.cloning(); throw new RuntimeException (); 588 } 589 } 590 591 595 public int size() 596 { return size; } 597 598 public void clear() { 599 size = 0; 600 used = 0; 601 java.util.Arrays.fill(states, EMPTY); 602 } 603 604 public boolean contains(short v) { 605 int h = Math.abs(keyhash.hash(v)); 606 int i = h % data.length; 607 if (states[i] != EMPTY) { 608 if (states[i] == OCCUPIED && data[i] == v) 609 return true; 610 611 int c = 1 + (h % (data.length - 2)); 613 for (;;) { 614 i -= c; 615 if (i < 0) 616 i += data.length; 617 if (states[i] == EMPTY) 618 return false; 619 if (states[i] == OCCUPIED && data[i] == v) 620 return true; 621 } 622 } 623 return false; 624 } 625 626 public int hashCode() { 627 int h = 0; 628 for (int i = 0; i < data.length; i++) 629 if (states[i] == OCCUPIED) 630 h += data[i]; 631 return h; 632 } 633 634 public boolean remove(short v) { 635 int h = Math.abs(keyhash.hash(v)); 636 int i = h % data.length; 637 if (states[i] != EMPTY) { 638 if (states[i] == OCCUPIED && data[i] == v) { 639 states[i] = REMOVED; 640 size--; 641 return true; 642 } 643 int c = 1 + (h % (data.length - 2)); 645 for (;;) { 646 i -= c; 647 if (i < 0) 648 i += data.length; 649 if (states[i] == EMPTY) 650 return false; 651 if (states[i] == OCCUPIED && data[i] == v) { 652 states[i] = REMOVED; 653 size--; 654 return true; 655 } 656 } 657 } 658 return false; 659 } 660 661 public short[] toArray(short[] a) { 662 if (a == null || a.length < size) 663 a = new short[size]; 664 665 int p = 0; 666 for (int i = 0; i < data.length; i++) 667 if (states[i] == OCCUPIED) 668 a[p++] = data[i]; 669 return a; 670 } 671 672 676 683 private void writeObject(ObjectOutputStream s) throws IOException { 684 s.defaultWriteObject(); 685 s.writeInt(data.length); 686 ShortIterator i = iterator(); 687 while (i.hasNext()) { 688 short x = i.next(); 689 s.writeShort(x); 690 } 691 } 692 693 696 private void readObject(ObjectInputStream s) throws IOException , ClassNotFoundException { 697 s.defaultReadObject(); 698 data = new short[s.readInt()]; 699 states = new byte[data.length]; 700 used = size; 701 for (int n = 0; n < size; n++) { 702 short v = s.readShort(); 703 704 int h = Math.abs(keyhash.hash(v)); 706 int i = h % data.length; 707 if (states[i] == OCCUPIED) { 708 int c = 1 + (h % (data.length - 2)); 710 for (;;) { 711 i -= c; 712 if (i < 0) 713 i += data.length; 714 if (states[i] == EMPTY) 715 break; 716 } 717 } 718 states[i] = OCCUPIED; 719 data[i] = v; 720 } 721 } 722 723 } 724 | Popular Tags |