1 19 package gnu.trove; 20 21 import java.io.Serializable; 22 import java.util.Arrays; 23 import java.util.Random; 24 import java.io.ObjectOutputStream; 25 import java.io.ObjectInputStream; 26 import java.io.IOException; 27 28 36 37 public class TIntArrayList implements Serializable, Cloneable { 38 39 40 protected transient int[] _data; 41 42 43 protected transient int _pos; 44 45 46 protected static final int DEFAULT_CAPACITY = 10; 47 48 52 public TIntArrayList() { 53 this(DEFAULT_CAPACITY); 54 } 55 56 62 public TIntArrayList(int capacity) { 63 _data = new int[capacity]; 64 _pos = 0; 65 } 66 67 75 public TIntArrayList(int[] values) { 76 this(Math.max(values.length, DEFAULT_CAPACITY)); 77 add(values); 78 } 79 80 82 90 public void ensureCapacity(int capacity) { 91 if (capacity > _data.length) { 92 int newCap = Math.max(_data.length << 1, capacity); 93 int[] tmp = new int[newCap]; 94 System.arraycopy(_data, 0, tmp, 0, _data.length); 95 _data = tmp; 96 } 97 } 98 99 104 public int size() { 105 return _pos; 106 } 107 108 113 public boolean isEmpty() { 114 return _pos == 0; 115 } 116 117 121 public void trimToSize() { 122 if (_data.length > size()) { 123 int[] tmp = new int[size()]; 124 toNativeArray(tmp, 0, tmp.length); 125 _data = tmp; 126 } 127 } 128 129 131 136 public void add(int val) { 137 ensureCapacity(_pos + 1); 138 _data[_pos++] = val; 139 } 140 141 147 public void add(int[] vals) { 148 add(vals, 0, vals.length); 149 } 150 151 159 public void add(int[] vals, int offset, int length) { 160 ensureCapacity(_pos + length); 161 System.arraycopy(vals, offset, _data, _pos, length); 162 _pos += length; 163 } 164 165 173 public void insert(int offset, int value) { 174 if (offset == _pos) { 175 add(value); 176 return; 177 } 178 ensureCapacity(_pos + 1); 179 System.arraycopy(_data, offset, _data, offset + 1, _pos - offset); 181 _data[offset] = value; 183 _pos++; 184 } 185 186 194 public void insert(int offset, int[] values) { 195 insert(offset, values, 0, values.length); 196 } 197 198 209 public void insert(int offset, int[] values, int valOffset, int len) { 210 if (offset == _pos) { 211 add(values, valOffset, len); 212 return; 213 } 214 215 ensureCapacity(_pos + len); 216 System.arraycopy(_data, offset, _data, offset + len, _pos - offset); 218 System.arraycopy(values, valOffset, _data, offset, len); 220 _pos += len; 221 } 222 223 229 public int get(int offset) { 230 if (offset >= _pos) { 231 throw new ArrayIndexOutOfBoundsException(offset); 232 } 233 return _data[offset]; 234 } 235 236 243 public int getQuick(int offset) { 244 return _data[offset]; 245 } 246 247 253 public void set(int offset, int val) { 254 if (offset >= _pos) { 255 throw new ArrayIndexOutOfBoundsException(offset); 256 } 257 _data[offset] = val; 258 } 259 260 268 public int getSet(int offset, int val) { 269 if (offset >= _pos) { 270 throw new ArrayIndexOutOfBoundsException(offset); 271 } 272 int old = _data[offset]; 273 _data[offset] = val; 274 return old; 275 } 276 277 284 public void set(int offset, int[] values) { 285 set(offset, values, 0, values.length); 286 } 287 288 298 public void set(int offset, int[] values, int valOffset, int length) { 299 if (offset < 0 || offset + length >= _pos) { 300 throw new ArrayIndexOutOfBoundsException(offset); 301 } 302 System.arraycopy(values, valOffset, _data, offset, length); 303 } 304 305 312 public void setQuick(int offset, int val) { 313 _data[offset] = val; 314 } 315 316 320 public void clear() { 321 clear(DEFAULT_CAPACITY); 322 } 323 324 330 public void clear(int capacity) { 331 _data = new int[capacity]; 332 _pos = 0; 333 } 334 335 343 public void reset() { 344 _pos = 0; 345 fill(0); 346 } 347 348 362 public void resetQuick() { 363 _pos = 0; 364 } 365 366 372 public int remove(int offset) { 373 int old = get(offset); 374 remove(offset, 1); 375 return old; 376 } 377 378 385 public void remove(int offset, int length) { 386 if (offset < 0 || offset >= _pos) { 387 throw new ArrayIndexOutOfBoundsException(offset); 388 } 389 390 if (offset == 0) { 391 System.arraycopy(_data, length, _data, 0, _pos - length); 393 } else if (_pos - length == offset) { 394 } else { 397 System.arraycopy(_data, offset + length, 399 _data, offset, _pos - (offset + length)); 400 } 401 _pos -= length; 402 } 406 407 412 public void transformValues(TIntFunction function) { 413 for (int i = _pos; i-- > 0;) { 414 _data[i] = function.execute(_data[i]); 415 } 416 } 417 418 421 public void reverse() { 422 reverse(0, _pos); 423 } 424 425 431 public void reverse(int from, int to) { 432 if (from == to) { 433 return; } 435 if (from > to) { 436 throw new IllegalArgumentException("from cannot be greater than to"); 437 } 438 for (int i = from, j = to - 1; i < j; i++, j--) { 439 swap(i, j); 440 } 441 } 442 443 449 public void shuffle(Random rand) { 450 for (int i = _pos; i-- > 1;) { 451 swap(i, rand.nextInt(i)); 452 } 453 } 454 455 461 private final void swap(int i, int j) { 462 int tmp = _data[i]; 463 _data[i] = _data[j]; 464 _data[j] = tmp; 465 } 466 467 469 475 public Object clone() { 476 TIntArrayList clone = null; 477 try { 478 clone = (TIntArrayList)super.clone(); 479 clone._data = (int[])_data.clone(); 480 } catch (CloneNotSupportedException e) { 481 } return clone; 484 } 485 486 491 public int[] toNativeArray() { 492 return toNativeArray(0, _pos); 493 } 494 495 502 public int[] toNativeArray(int offset, int len) { 503 int[] rv = new int[len]; 504 toNativeArray(rv, offset, len); 505 return rv; 506 } 507 508 515 public void toNativeArray(int[] dest, int offset, int len) { 516 if (len == 0) { 517 return; } 519 if (offset < 0 || offset >= _pos) { 520 throw new ArrayIndexOutOfBoundsException(offset); 521 } 522 System.arraycopy(_data, offset, dest, 0, len); 523 } 524 525 527 534 public boolean equals(Object other) { 535 if (other == this) { 536 return true; 537 } else if (other instanceof TIntArrayList) { 538 TIntArrayList that = (TIntArrayList)other; 539 if (that.size() != this.size()) { 540 return false; 541 } else { 542 for (int i = _pos; i-- > 0;) { 543 if (this._data[i] != that._data[i]) { 544 return false; 545 } 546 } 547 return true; 548 } 549 } else { 550 return false; 551 } 552 } 553 554 public int hashCode() { 555 int h = 0; 556 for (int i = _pos; i-- > 0;) { 557 h += _data[i]; 558 } 559 return h; 560 } 561 562 564 571 public boolean forEach(TIntProcedure procedure) { 572 for (int i = 0; i < _pos; i++) { 573 if (! procedure.execute(_data[i])) { 574 return false; 575 } 576 } 577 return true; 578 } 579 580 587 public boolean forEachDescending(TIntProcedure procedure) { 588 for (int i = _pos; i-- > 0;) { 589 if (! procedure.execute(_data[i])) { 590 return false; 591 } 592 } 593 return true; 594 } 595 596 598 604 public void sort() { 605 Arrays.sort(_data, 0, _pos); 606 } 607 608 616 public void sort(int fromIndex, int toIndex) { 617 Arrays.sort(_data, fromIndex, toIndex); 618 } 619 620 622 627 public void fill(int val) { 628 Arrays.fill(_data, 0, _pos, val); 629 } 630 631 638 public void fill(int fromIndex, int toIndex, int val) { 639 if (toIndex > _pos) { 640 ensureCapacity(toIndex); 641 _pos = toIndex; 642 } 643 Arrays.fill(_data, fromIndex, toIndex, val); 644 } 645 646 648 657 public int binarySearch(int value) { 658 return binarySearch(value, 0, _pos); 659 } 660 661 672 public int binarySearch(int value, int fromIndex, int toIndex) { 673 if (fromIndex < 0) { 674 throw new ArrayIndexOutOfBoundsException(fromIndex); 675 } 676 if (toIndex > _pos) { 677 throw new ArrayIndexOutOfBoundsException(toIndex); 678 } 679 680 int low = fromIndex; 681 int high = toIndex - 1; 682 683 while (low <= high) { 684 int mid = (low + high) >> 1; 685 int midVal = _data[mid]; 686 687 if (midVal < value) { 688 low = mid + 1; 689 } else if (midVal > value) { 690 high = mid - 1; 691 } else { 692 return mid; } 694 } 695 return -(low + 1); } 697 698 707 public int indexOf(int value) { 708 return indexOf(0, value); 709 } 710 711 722 public int indexOf(int offset, int value) { 723 for (int i = offset; i < _pos; i++) { 724 if (_data[i] == value) { 725 return i; 726 } 727 } 728 return -1; 729 } 730 731 740 public int lastIndexOf(int value) { 741 return lastIndexOf(_pos, value); 742 } 743 744 755 public int lastIndexOf(int offset, int value) { 756 for (int i = offset; i-- > 0;) { 757 if (_data[i] == value) { 758 return i; 759 } 760 } 761 return -1; 762 } 763 764 770 public boolean contains(int value) { 771 return lastIndexOf(value) >= 0; 772 } 773 774 781 public TIntArrayList grep(TIntProcedure condition) { 782 TIntArrayList list = new TIntArrayList(); 783 for (int i = 0; i < _pos; i++) { 784 if (condition.execute(_data[i])) { 785 list.add(_data[i]); 786 } 787 } 788 return list; 789 } 790 791 798 public TIntArrayList inverseGrep(TIntProcedure condition) { 799 TIntArrayList list = new TIntArrayList(); 800 for (int i = 0; i < _pos; i++) { 801 if (! condition.execute(_data[i])) { 802 list.add(_data[i]); 803 } 804 } 805 return list; 806 } 807 808 814 public int max() { 815 if (size() == 0) { 816 throw new IllegalStateException("cannot find maximum of an empty list"); 817 } 818 int max = _data[_pos - 1]; 819 for (int i = _pos - 1; i-- > 0;) { 820 if (_data[i] > max) { 821 max = _data[i]; 822 } 823 } 824 return max; 825 } 826 827 833 public int min() { 834 if (size() == 0) { 835 throw new IllegalStateException("cannot find minimum of an empty list"); 836 } 837 int min = _data[_pos - 1]; 838 for (int i = _pos - 1; i-- > 0;) { 839 if (_data[i] < min) { 840 min = _data[i]; 841 } 842 } 843 return min; 844 } 845 846 848 853 public String toString() { 854 StringBuffer buf = new StringBuffer("{"); 855 for (int i = 0, end = _pos - 1; i < end; i++) { 856 buf.append(_data[i]); 857 buf.append(", "); 858 } 859 if (size() > 0) { 860 buf.append(_data[_pos - 1]); 861 } 862 buf.append("}"); 863 return buf.toString(); 864 } 865 866 private void writeObject(ObjectOutputStream stream) 867 throws IOException { 868 stream.defaultWriteObject(); 869 870 stream.writeInt(size()); 872 873 SerializationProcedure writeProcedure = new SerializationProcedure(stream); 874 if (! forEach(writeProcedure)) { 875 throw writeProcedure.exception; 876 } 877 } 878 879 private void readObject(ObjectInputStream stream) 880 throws IOException, ClassNotFoundException { 881 stream.defaultReadObject(); 882 883 int size = stream.readInt(); 884 _data = new int[size]; 885 while (size-- > 0) { 886 int val = stream.readInt(); 887 add(val); 888 } 889 } 890 891 } | Popular Tags |