1 19 package bak.pcj.set; 20 21 import bak.pcj.IntCollection; 22 import bak.pcj.IntIterator; 23 import bak.pcj.hash.IntHashFunction; 24 import bak.pcj.hash.DefaultIntHashFunction; 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 IntChainedHashSet extends AbstractIntSet implements IntSet, 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 IntHashFunction keyhash; 77 78 82 private int size; 83 84 85 private transient int[][] data; 86 87 91 private int growthPolicy; 92 93 98 private double growthFactor; 99 100 105 private int growthChunk; 106 107 111 private double loadFactor; 112 113 117 private int expandAt; 118 119 private IntChainedHashSet(IntHashFunction keyhash, int capacity, int growthPolicy, double growthFactor, int growthChunk, double loadFactor) { 120 if (keyhash == null) 121 Exceptions.nullArgument("hash function"); 122 if (capacity < 0) 123 Exceptions.negativeArgument("capacity", String.valueOf(capacity)); 124 if (growthFactor < 0.0) 125 Exceptions.negativeArgument("growthFactor", String.valueOf(growthFactor)); 126 if (growthChunk < 0) 127 Exceptions.negativeArgument("growthChunk", String.valueOf(growthChunk)); 128 if (loadFactor <= 0.0) 129 Exceptions.negativeOrZeroArgument("loadFactor", String.valueOf(loadFactor)); 130 data = new int[capacity][]; 131 size = 0; 132 expandAt = (int)Math.round(loadFactor*capacity); 133 this.growthPolicy = growthPolicy; 134 this.growthFactor = growthFactor; 135 this.growthChunk = growthChunk; 136 this.loadFactor = loadFactor; 137 this.keyhash = keyhash; 138 } 139 140 private IntChainedHashSet(int capacity, int growthPolicy, double growthFactor, int growthChunk, double loadFactor) { 141 this(DefaultIntHashFunction.INSTANCE, capacity, growthPolicy, growthFactor, growthChunk, loadFactor); 142 } 143 144 148 public IntChainedHashSet() { 149 this(DEFAULT_CAPACITY); 150 } 151 152 163 public IntChainedHashSet(IntCollection c) { 164 this(); 165 addAll(c); 166 } 167 168 181 public IntChainedHashSet(int[] a) { 182 this(); 183 for (int i = 0; i < a.length; i++) 184 add(a[i]); 185 } 186 187 197 public IntChainedHashSet(int capacity) { 198 this(capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR); 199 } 200 201 211 public IntChainedHashSet(double loadFactor) { 212 this(DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor); 213 } 214 215 229 public IntChainedHashSet(int capacity, double loadFactor) { 230 this(capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor); 231 } 232 233 256 public IntChainedHashSet(int capacity, double loadFactor, double growthFactor) { 257 this(capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK, loadFactor); 258 } 259 260 283 public IntChainedHashSet(int capacity, double loadFactor, int growthChunk) { 284 this(capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor); 285 } 286 287 291 301 public IntChainedHashSet(IntHashFunction keyhash) { 302 this(keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR); 303 } 304 305 321 public IntChainedHashSet(IntHashFunction keyhash, int capacity) { 322 this(keyhash, capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR); 323 } 324 325 341 public IntChainedHashSet(IntHashFunction keyhash, double loadFactor) { 342 this(keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor); 343 } 344 345 365 public IntChainedHashSet(IntHashFunction keyhash, int capacity, double loadFactor) { 366 this(keyhash, capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor); 367 } 368 369 398 public IntChainedHashSet(IntHashFunction keyhash, int capacity, double loadFactor, double growthFactor) { 399 this(keyhash, capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK, loadFactor); 400 } 401 402 431 public IntChainedHashSet(IntHashFunction keyhash, int capacity, double loadFactor, int growthChunk) { 432 this(keyhash, capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor); 433 } 434 435 439 private void ensureCapacity(int elements) { 440 if (elements >= expandAt) { 441 int newcapacity; 442 if (growthPolicy == GROWTH_POLICY_RELATIVE) 443 newcapacity = (int)(data.length * (1.0 + growthFactor)); 444 else 445 newcapacity = data.length + growthChunk; 446 if (newcapacity*loadFactor < elements) 447 newcapacity = (int)Math.round(((double)elements/loadFactor)); 448 newcapacity = bak.pcj.hash.Primes.nextPrime(newcapacity); 449 expandAt = (int)Math.round(loadFactor*newcapacity); 450 451 int[][] newdata = new int[newcapacity][]; 452 453 for (int i = 0; i < data.length; i++) { 455 int[] list = data[i]; 456 if (list != null) { 457 for (int n = 0; n < list.length; n++) { 458 int v = list[n]; 459 int index = Math.abs(keyhash.hash(v)) % newdata.length; 460 newdata[index] = addList(newdata[index], v); 461 } 462 } 463 } 464 465 data = newdata; 466 } 467 } 468 469 private int[] addList(int[] list, int v) { 470 if (list == null) 471 return new int[]{v}; 472 int[] newlist = new int[list.length+1]; 473 for (int i = 0; i < list.length; i++) 474 newlist[i] = list[i]; 475 newlist[list.length] = v; 476 return newlist; 477 } 478 479 private int[] removeList(int[] list, int index) { 480 if (list.length == 1) 481 return null; 482 int[] newlist = new int[list.length-1]; 483 int n = 0; 484 for (int i = 0; i < index; i++) 485 newlist[n++] = list[i]; 486 for (int i = index+1; i < list.length; i++) 487 newlist[n++] = list[i]; 488 return newlist; 489 } 490 491 private int searchList(int[] list, int v) { 492 for (int i = 0; i < list.length; i++) 493 if (list[i] == v) 494 return i; 495 return -1; 496 } 497 498 502 public boolean add(int v) { 503 ensureCapacity(size+1); 504 505 int index = Math.abs(keyhash.hash(v)) % data.length; 506 int[] list = data[index]; 507 if (list == null) { 508 data[index] = new int[]{v}; 509 size++; 510 return true; 511 } 512 for (int i = 0; i < list.length; i++) 513 if (list[i] == v) 514 return false; 515 data[index] = addList(data[index], v); 516 size++; 517 return true; 518 } 519 520 public IntIterator iterator() { 521 return new IntIterator() { 522 int currList = nextList(0); 523 int currInt = 0; 524 int lastList = -1; 525 int lastInt; 526 int lastValue; 527 528 int nextList(int index) { 529 while (index < data.length && data[index] == null) 530 index++; 531 return index < data.length ? index : -1; 532 } 533 534 public boolean hasNext() { 535 return currList != -1; 536 } 537 538 public int next() { 539 if (currList == -1) 540 Exceptions.endOfIterator(); 541 lastList = currList; 542 lastInt = currInt; 543 lastValue = data[currList][currInt]; 544 if (currInt == data[currList].length-1) { 545 currList = nextList(currList+1); 546 currInt = 0; 547 } else { 548 currInt++; 549 } 550 return lastValue; 551 } 552 553 public void remove() { 554 if (lastList == -1) 555 Exceptions.noElementToRemove(); 556 if (currList == lastList) 557 currInt--; 558 data[lastList] = removeList(data[lastList], lastInt); 559 size--; 560 lastList = -1; 561 } 562 }; 563 } 564 565 public void trimToSize() 566 { } 567 568 575 public Object clone() { 576 try { 577 IntChainedHashSet c = (IntChainedHashSet)super.clone(); 578 c.data = new int[data.length][]; 579 System.arraycopy(data, 0, c.data, 0, data.length); 581 return c; 582 } catch (CloneNotSupportedException e) { 583 Exceptions.cloning(); throw new RuntimeException (); 584 } 585 } 586 587 591 public int size() 592 { return size; } 593 594 public void clear() 595 { size = 0; } 596 597 public boolean contains(int v) { 598 int[] list = data[Math.abs(keyhash.hash(v)) % data.length]; 599 if (list == null) 600 return false; 601 return searchList(list, v) != -1; 602 } 603 604 public int hashCode() { 605 int h = 0; 606 for (int i = 0; i < data.length; i++) { 607 int[] list = data[i]; 608 if (list != null) { 609 for (int n = 0; n < list.length; n++) 610 h += list[n]; 611 } 612 } 613 return h; 614 } 615 616 public boolean remove(int v) { 617 int index = Math.abs(keyhash.hash(v)) % data.length; 618 int[] list = data[index]; 619 if (list != null) { 620 int lindex = searchList(list, v); 621 if (lindex == -1) 622 return false; 623 data[index] = removeList(list, lindex); 624 size--; 625 return true; 626 } 627 return false; 628 } 629 630 public int[] toArray(int[] a) { 631 if (a == null || a.length < size) 632 a = new int[size]; 633 634 int p = 0; 635 for (int i = 0; i < data.length; i++) { 636 int[] list = data[i]; 637 if (list != null) { 638 for (int n = 0; n < list.length; n++) 639 a[p++] = list[n]; 640 } 641 } 642 return a; 643 } 644 645 649 656 private void writeObject(ObjectOutputStream s) throws IOException { 657 s.defaultWriteObject(); 658 s.writeInt(data.length); 659 IntIterator i = iterator(); 660 while (i.hasNext()) { 661 int x = i.next(); 662 s.writeInt(x); 663 } 664 } 665 666 669 private void readObject(ObjectInputStream s) throws IOException , ClassNotFoundException { 670 s.defaultReadObject(); 671 data = new int[s.readInt()][]; 672 for (int i = 0; i < size; i++) { 673 int v = s.readInt(); 674 int index = Math.abs(keyhash.hash(v)) % data.length; 675 int[] list = data[index]; 676 if (list == null) 677 data[index] = new int[]{v}; 678 else 679 data[index] = addList(data[index], v); 680 } 681 } 682 683 } 684 | Popular Tags |