001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. 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 package org.apache.commons.collections; 018 019 import java.util.ArrayList; 020 import java.util.Collection; 021 import java.util.ConcurrentModificationException; 022 import java.util.Iterator; 023 import java.util.List; 024 import java.util.ListIterator; 025 026 /** 027 * <p>A customized implementation of <code>java.util.ArrayList</code> designed 028 * to operate in a multithreaded environment where the large majority of 029 * method calls are read-only, instead of structural changes. When operating 030 * in "fast" mode, read calls are non-synchronized and write calls perform the 031 * following steps:</p> 032 * <ul> 033 * <li>Clone the existing collection 034 * <li>Perform the modification on the clone 035 * <li>Replace the existing collection with the (modified) clone 036 * </ul> 037 * <p>When first created, objects of this class default to "slow" mode, where 038 * all accesses of any type are synchronized but no cloning takes place. This 039 * is appropriate for initially populating the collection, followed by a switch 040 * to "fast" mode (by calling <code>setFast(true)</code>) after initialization 041 * is complete.</p> 042 * 043 * <p><strong>NOTE</strong>: If you are creating and accessing an 044 * <code>ArrayList</code> only within a single thread, you should use 045 * <code>java.util.ArrayList</code> directly (with no synchronization), for 046 * maximum performance.</p> 047 * 048 * <p><strong>NOTE</strong>: <i>This class is not cross-platform. 049 * Using it may cause unexpected failures on some architectures.</i> 050 * It suffers from the same problems as the double-checked locking idiom. 051 * In particular, the instruction that clones the internal collection and the 052 * instruction that sets the internal reference to the clone can be executed 053 * or perceived out-of-order. This means that any read operation might fail 054 * unexpectedly, as it may be reading the state of the internal collection 055 * before the internal collection is fully formed. 056 * For more information on the double-checked locking idiom, see the 057 * <a href="http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html"> 058 * Double-Checked Locking Idiom Is Broken Declaration</a>.</p> 059 * 060 * @since Commons Collections 1.0 061 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ 062 * 063 * @author Craig R. McClanahan 064 * @author Stephen Colebourne 065 */ 066 public class FastArrayList extends ArrayList { 067 068 069 // ----------------------------------------------------------- Constructors 070 071 072 /** 073 * Construct a an empty list. 074 */ 075 public FastArrayList() { 076 077 super(); 078 this.list = new ArrayList(); 079 080 } 081 082 083 /** 084 * Construct an empty list with the specified capacity. 085 * 086 * @param capacity The initial capacity of the empty list 087 */ 088 public FastArrayList(int capacity) { 089 090 super(); 091 this.list = new ArrayList(capacity); 092 093 } 094 095 096 /** 097 * Construct a list containing the elements of the specified collection, 098 * in the order they are returned by the collection's iterator. 099 * 100 * @param collection The collection whose elements initialize the contents 101 * of this list 102 */ 103 public FastArrayList(Collection collection) { 104 105 super(); 106 this.list = new ArrayList(collection); 107 108 } 109 110 111 // ----------------------------------------------------- Instance Variables 112 113 114 /** 115 * The underlying list we are managing. 116 */ 117 protected ArrayList list = null; 118 119 120 // ------------------------------------------------------------- Properties 121 122 123 /** 124 * Are we operating in "fast" mode? 125 */ 126 protected boolean fast = false; 127 128 129 /** 130 * Returns true if this list is operating in fast mode. 131 * 132 * @return true if this list is operating in fast mode 133 */ 134 public boolean getFast() { 135 return (this.fast); 136 } 137 138 /** 139 * Sets whether this list will operate in fast mode. 140 * 141 * @param fast true if the list should operate in fast mode 142 */ 143 public void setFast(boolean fast) { 144 this.fast = fast; 145 } 146 147 148 // --------------------------------------------------------- Public Methods 149 150 151 /** 152 * Appends the specified element to the end of this list. 153 * 154 * @param element The element to be appended 155 */ 156 public boolean add(Object element) { 157 158 if (fast) { 159 synchronized (this) { 160 ArrayList temp = (ArrayList) list.clone(); 161 boolean result = temp.add(element); 162 list = temp; 163 return (result); 164 } 165 } else { 166 synchronized (list) { 167 return (list.add(element)); 168 } 169 } 170 171 } 172 173 174 /** 175 * Insert the specified element at the specified position in this list, 176 * and shift all remaining elements up one position. 177 * 178 * @param index Index at which to insert this element 179 * @param element The element to be inserted 180 * 181 * @exception IndexOutOfBoundsException if the index is out of range 182 */ 183 public void add(int index, Object element) { 184 185 if (fast) { 186 synchronized (this) { 187 ArrayList temp = (ArrayList) list.clone(); 188 temp.add(index, element); 189 list = temp; 190 } 191 } else { 192 synchronized (list) { 193 list.add(index, element); 194 } 195 } 196 197 } 198 199 200 /** 201 * Append all of the elements in the specified Collection to the end 202 * of this list, in the order that they are returned by the specified 203 * Collection's Iterator. 204 * 205 * @param collection The collection to be appended 206 */ 207 public boolean addAll(Collection collection) { 208 209 if (fast) { 210 synchronized (this) { 211 ArrayList temp = (ArrayList) list.clone(); 212 boolean result = temp.addAll(collection); 213 list = temp; 214 return (result); 215 } 216 } else { 217 synchronized (list) { 218 return (list.addAll(collection)); 219 } 220 } 221 222 } 223 224 225 /** 226 * Insert all of the elements in the specified Collection at the specified 227 * position in this list, and shift any previous elements upwards as 228 * needed. 229 * 230 * @param index Index at which insertion takes place 231 * @param collection The collection to be added 232 * 233 * @exception IndexOutOfBoundsException if the index is out of range 234 */ 235 public boolean addAll(int index, Collection collection) { 236 237 if (fast) { 238 synchronized (this) { 239 ArrayList temp = (ArrayList) list.clone(); 240 boolean result = temp.addAll(index, collection); 241 list = temp; 242 return (result); 243 } 244 } else { 245 synchronized (list) { 246 return (list.addAll(index, collection)); 247 } 248 } 249 250 } 251 252 253 /** 254 * Remove all of the elements from this list. The list will be empty 255 * after this call returns. 256 * 257 * @exception UnsupportedOperationException if <code>clear()</code> 258 * is not supported by this list 259 */ 260 public void clear() { 261 262 if (fast) { 263 synchronized (this) { 264 ArrayList temp = (ArrayList) list.clone(); 265 temp.clear(); 266 list = temp; 267 } 268 } else { 269 synchronized (list) { 270 list.clear(); 271 } 272 } 273 274 } 275 276 277 /** 278 * Return a shallow copy of this <code>FastArrayList</code> instance. 279 * The elements themselves are not copied. 280 */ 281 public Object clone() { 282 283 FastArrayList results = null; 284 if (fast) { 285 results = new FastArrayList(list); 286 } else { 287 synchronized (list) { 288 results = new FastArrayList(list); 289 } 290 } 291 results.setFast(getFast()); 292 return (results); 293 294 } 295 296 297 /** 298 * Return <code>true</code> if this list contains the specified element. 299 * 300 * @param element The element to test for 301 */ 302 public boolean contains(Object element) { 303 304 if (fast) { 305 return (list.contains(element)); 306 } else { 307 synchronized (list) { 308 return (list.contains(element)); 309 } 310 } 311 312 } 313 314 315 /** 316 * Return <code>true</code> if this list contains all of the elements 317 * in the specified Collection. 318 * 319 * @param collection Collection whose elements are to be checked 320 */ 321 public boolean containsAll(Collection collection) { 322 323 if (fast) { 324 return (list.containsAll(collection)); 325 } else { 326 synchronized (list) { 327 return (list.containsAll(collection)); 328 } 329 } 330 331 } 332 333 334 /** 335 * Increase the capacity of this <code>ArrayList</code> instance, if 336 * necessary, to ensure that it can hold at least the number of elements 337 * specified by the minimum capacity argument. 338 * 339 * @param capacity The new minimum capacity 340 */ 341 public void ensureCapacity(int capacity) { 342 343 if (fast) { 344 synchronized (this) { 345 ArrayList temp = (ArrayList) list.clone(); 346 temp.ensureCapacity(capacity); 347 list = temp; 348 } 349 } else { 350 synchronized (list) { 351 list.ensureCapacity(capacity); 352 } 353 } 354 355 } 356 357 358 /** 359 * Compare the specified object with this list for equality. This 360 * implementation uses exactly the code that is used to define the 361 * list equals function in the documentation for the 362 * <code>List.equals</code> method. 363 * 364 * @param o Object to be compared to this list 365 */ 366 public boolean equals(Object o) { 367 368 // Simple tests that require no synchronization 369 if (o == this) 370 return (true); 371 else if (!(o instanceof List)) 372 return (false); 373 List lo = (List) o; 374 375 // Compare the sets of elements for equality 376 if (fast) { 377 ListIterator li1 = list.listIterator(); 378 ListIterator li2 = lo.listIterator(); 379 while (li1.hasNext() && li2.hasNext()) { 380 Object o1 = li1.next(); 381 Object o2 = li2.next(); 382 if (!(o1 == null ? o2 == null : o1.equals(o2))) 383 return (false); 384 } 385 return (!(li1.hasNext() || li2.hasNext())); 386 } else { 387 synchronized (list) { 388 ListIterator li1 = list.listIterator(); 389 ListIterator li2 = lo.listIterator(); 390 while (li1.hasNext() && li2.hasNext()) { 391 Object o1 = li1.next(); 392 Object o2 = li2.next(); 393 if (!(o1 == null ? o2 == null : o1.equals(o2))) 394 return (false); 395 } 396 return (!(li1.hasNext() || li2.hasNext())); 397 } 398 } 399 400 } 401 402 403 /** 404 * Return the element at the specified position in the list. 405 * 406 * @param index The index of the element to return 407 * 408 * @exception IndexOutOfBoundsException if the index is out of range 409 */ 410 public Object get(int index) { 411 412 if (fast) { 413 return (list.get(index)); 414 } else { 415 synchronized (list) { 416 return (list.get(index)); 417 } 418 } 419 420 } 421 422 423 /** 424 * Return the hash code value for this list. This implementation uses 425 * exactly the code that is used to define the list hash function in the 426 * documentation for the <code>List.hashCode</code> method. 427 */ 428 public int hashCode() { 429 430 if (fast) { 431 int hashCode = 1; 432 java.util.Iterator i = list.iterator(); 433 while (i.hasNext()) { 434 Object o = i.next(); 435 hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode()); 436 } 437 return (hashCode); 438 } else { 439 synchronized (list) { 440 int hashCode = 1; 441 java.util.Iterator i = list.iterator(); 442 while (i.hasNext()) { 443 Object o = i.next(); 444 hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode()); 445 } 446 return (hashCode); 447 } 448 } 449 450 } 451 452 453 /** 454 * Search for the first occurrence of the given argument, testing 455 * for equality using the <code>equals()</code> method, and return 456 * the corresponding index, or -1 if the object is not found. 457 * 458 * @param element The element to search for 459 */ 460 public int indexOf(Object element) { 461 462 if (fast) { 463 return (list.indexOf(element)); 464 } else { 465 synchronized (list) { 466 return (list.indexOf(element)); 467 } 468 } 469 470 } 471 472 473 /** 474 * Test if this list has no elements. 475 */ 476 public boolean isEmpty() { 477 478 if (fast) { 479 return (list.isEmpty()); 480 } else { 481 synchronized (list) { 482 return (list.isEmpty()); 483 } 484 } 485 486 } 487 488 489 /** 490 * Return an iterator over the elements in this list in proper sequence. 491 * <p> 492 * <b>Thread safety</b><br /> 493 * The iterator returned is thread-safe ONLY in FAST mode. 494 * In slow mode there is no way to synchronize, or make the iterator thread-safe. 495 * <p> 496 * In fast mode iteration and modification may occur in parallel on different threads, 497 * however there is a restriction. Modification must be EITHER via the Iterator 498 * interface methods OR the List interface. If a mixture of modification 499 * methods is used a ConcurrentModificationException is thrown from the iterator 500 * modification method. If the List modification methods are used the changes are 501 * NOT visible in the iterator (it shows the list contents at the time the iterator 502 * was created). 503 * 504 * @return the iterator 505 */ 506 public Iterator iterator() { 507 if (fast) { 508 return new ListIter(0); 509 } else { 510 return list.iterator(); 511 } 512 } 513 514 515 /** 516 * Search for the last occurrence of the given argument, testing 517 * for equality using the <code>equals()</code> method, and return 518 * the corresponding index, or -1 if the object is not found. 519 * 520 * @param element The element to search for 521 */ 522 public int lastIndexOf(Object element) { 523 524 if (fast) { 525 return (list.lastIndexOf(element)); 526 } else { 527 synchronized (list) { 528 return (list.lastIndexOf(element)); 529 } 530 } 531 532 } 533 534 535 /** 536 * Return an iterator of the elements of this list, in proper sequence. 537 * <p> 538 * <b>Thread safety</b><br /> 539 * The iterator returned is thread-safe ONLY in FAST mode. 540 * In slow mode there is no way to synchronize, or make the iterator thread-safe. 541 * <p> 542 * In fast mode iteration and modification may occur in parallel on different threads, 543 * however there is a restriction. Modification must be EITHER via the Iterator 544 * interface methods OR the List interface. If a mixture of modification 545 * methods is used a ConcurrentModificationException is thrown from the iterator 546 * modification method. If the List modification methods are used the changes are 547 * NOT visible in the iterator (it shows the list contents at the time the iterator 548 * was created). 549 * 550 * @return the list iterator 551 */ 552 public ListIterator listIterator() { 553 if (fast) { 554 return new ListIter(0); 555 } else { 556 return list.listIterator(); 557 } 558 } 559 560 561 /** 562 * Return an iterator of the elements of this list, in proper sequence, 563 * starting at the specified position. 564 * <p> 565 * <b>Thread safety</b><br /> 566 * The iterator returned is thread-safe ONLY in FAST mode. 567 * In slow mode there is no way to synchronize, or make the iterator thread-safe. 568 * <p> 569 * In fast mode iteration and modification may occur in parallel on different threads, 570 * however there is a restriction. Modification must be EITHER via the Iterator 571 * interface methods OR the List interface. If a mixture of modification 572 * methods is used a ConcurrentModificationException is thrown from the iterator 573 * modification method. If the List modification methods are used the changes are 574 * NOT visible in the iterator (it shows the list contents at the time the iterator 575 * was created). 576 * 577 * @param index The starting position of the iterator to return 578 * @return the list iterator 579 * @exception IndexOutOfBoundsException if the index is out of range 580 */ 581 public ListIterator listIterator(int index) { 582 if (fast) { 583 return new ListIter(index); 584 } else { 585 return list.listIterator(index); 586 } 587 } 588 589 590 /** 591 * Remove the element at the specified position in the list, and shift 592 * any subsequent elements down one position. 593 * 594 * @param index Index of the element to be removed 595 * 596 * @exception IndexOutOfBoundsException if the index is out of range 597 */ 598 public Object remove(int index) { 599 600 if (fast) { 601 synchronized (this) { 602 ArrayList temp = (ArrayList) list.clone(); 603 Object result = temp.remove(index); 604 list = temp; 605 return (result); 606 } 607 } else { 608 synchronized (list) { 609 return (list.remove(index)); 610 } 611 } 612 613 } 614 615 616 /** 617 * Remove the first occurrence of the specified element from the list, 618 * and shift any subsequent elements down one position. 619 * 620 * @param element Element to be removed 621 */ 622 public boolean remove(Object element) { 623 624 if (fast) { 625 synchronized (this) { 626 ArrayList temp = (ArrayList) list.clone(); 627 boolean result = temp.remove(element); 628 list = temp; 629 return (result); 630 } 631 } else { 632 synchronized (list) { 633 return (list.remove(element)); 634 } 635 } 636 637 } 638 639 640 /** 641 * Remove from this collection all of its elements that are contained 642 * in the specified collection. 643 * 644 * @param collection Collection containing elements to be removed 645 * 646 * @exception UnsupportedOperationException if this optional operation 647 * is not supported by this list 648 */ 649 public boolean removeAll(Collection collection) { 650 651 if (fast) { 652 synchronized (this) { 653 ArrayList temp = (ArrayList) list.clone(); 654 boolean result = temp.removeAll(collection); 655 list = temp; 656 return (result); 657 } 658 } else { 659 synchronized (list) { 660 return (list.removeAll(collection)); 661 } 662 } 663 664 } 665 666 667 /** 668 * Remove from this collection all of its elements except those that are 669 * contained in the specified collection. 670 * 671 * @param collection Collection containing elements to be retained 672 * 673 * @exception UnsupportedOperationException if this optional operation 674 * is not supported by this list 675 */ 676 public boolean retainAll(Collection collection) { 677 678 if (fast) { 679 synchronized (this) { 680 ArrayList temp = (ArrayList) list.clone(); 681 boolean result = temp.retainAll(collection); 682 list = temp; 683 return (result); 684 } 685 } else { 686 synchronized (list) { 687 return (list.retainAll(collection)); 688 } 689 } 690 691 } 692 693 694 /** 695 * Replace the element at the specified position in this list with 696 * the specified element. Returns the previous object at that position. 697 * <br><br> 698 * <strong>IMPLEMENTATION NOTE</strong> - This operation is specifically 699 * documented to not be a structural change, so it is safe to be performed 700 * without cloning. 701 * 702 * @param index Index of the element to replace 703 * @param element The new element to be stored 704 * 705 * @exception IndexOutOfBoundsException if the index is out of range 706 */ 707 public Object set(int index, Object element) { 708 709 if (fast) { 710 return (list.set(index, element)); 711 } else { 712 synchronized (list) { 713 return (list.set(index, element)); 714 } 715 } 716 717 } 718 719 720 /** 721 * Return the number of elements in this list. 722 */ 723 public int size() { 724 725 if (fast) { 726 return (list.size()); 727 } else { 728 synchronized (list) { 729 return (list.size()); 730 } 731 } 732 733 } 734 735 736 /** 737 * Return a view of the portion of this list between fromIndex 738 * (inclusive) and toIndex (exclusive). The returned list is backed 739 * by this list, so non-structural changes in the returned list are 740 * reflected in this list. The returned list supports 741 * all of the optional list operations supported by this list. 742 * 743 * @param fromIndex The starting index of the sublist view 744 * @param toIndex The index after the end of the sublist view 745 * 746 * @exception IndexOutOfBoundsException if an index is out of range 747 */ 748 public List subList(int fromIndex, int toIndex) { 749 if (fast) { 750 return new SubList(fromIndex, toIndex); 751 } else { 752 return list.subList(fromIndex, toIndex); 753 } 754 } 755 756 757 /** 758 * Return an array containing all of the elements in this list in the 759 * correct order. 760 */ 761 public Object[] toArray() { 762 763 if (fast) { 764 return (list.toArray()); 765 } else { 766 synchronized (list) { 767 return (list.toArray()); 768 } 769 } 770 771 } 772 773 774 /** 775 * Return an array containing all of the elements in this list in the 776 * correct order. The runtime type of the returned array is that of 777 * the specified array. If the list fits in the specified array, it is 778 * returned therein. Otherwise, a new array is allocated with the 779 * runtime type of the specified array, and the size of this list. 780 * 781 * @param array Array defining the element type of the returned list 782 * 783 * @exception ArrayStoreException if the runtime type of <code>array</code> 784 * is not a supertype of the runtime type of every element in this list 785 */ 786 public Object[] toArray(Object array[]) { 787 788 if (fast) { 789 return (list.toArray(array)); 790 } else { 791 synchronized (list) { 792 return (list.toArray(array)); 793 } 794 } 795 796 } 797 798 799 /** 800 * Return a String representation of this object. 801 */ 802 public String toString() { 803 804 StringBuffer sb = new StringBuffer("FastArrayList["); 805 sb.append(list.toString()); 806 sb.append("]"); 807 return (sb.toString()); 808 809 } 810 811 812 /** 813 * Trim the capacity of this <code>ArrayList</code> instance to be the 814 * list's current size. An application can use this operation to minimize 815 * the storage of an <code>ArrayList</code> instance. 816 */ 817 public void trimToSize() { 818 819 if (fast) { 820 synchronized (this) { 821 ArrayList temp = (ArrayList) list.clone(); 822 temp.trimToSize(); 823 list = temp; 824 } 825 } else { 826 synchronized (list) { 827 list.trimToSize(); 828 } 829 } 830 831 } 832 833 834 835 private class SubList implements List { 836 837 private int first; 838 private int last; 839 private List expected; 840 841 842 public SubList(int first, int last) { 843 this.first = first; 844 this.last = last; 845 this.expected = list; 846 } 847 848 private List get(List l) { 849 if (list != expected) { 850 throw new ConcurrentModificationException(); 851 } 852 return l.subList(first, last); 853 } 854 855 public void clear() { 856 if (fast) { 857 synchronized (FastArrayList.this) { 858 ArrayList temp = (ArrayList) list.clone(); 859 get(temp).clear(); 860 last = first; 861 list = temp; 862 expected = temp; 863 } 864 } else { 865 synchronized (list) { 866 get(expected).clear(); 867 } 868 } 869 } 870 871 public boolean remove(Object o) { 872 if (fast) { 873 synchronized (FastArrayList.this) { 874 ArrayList temp = (ArrayList) list.clone(); 875 boolean r = get(temp).remove(o); 876 if (r) last--; 877 list = temp; 878 expected = temp; 879 return r; 880 } 881 } else { 882 synchronized (list) { 883 return get(expected).remove(o); 884 } 885 } 886 } 887 888 public boolean removeAll(Collection o) { 889 if (fast) { 890 synchronized (FastArrayList.this) { 891 ArrayList temp = (ArrayList) list.clone(); 892 List sub = get(temp); 893 boolean r = sub.removeAll(o); 894 if (r) last = first + sub.size(); 895 list = temp; 896 expected = temp; 897 return r; 898 } 899 } else { 900 synchronized (list) { 901 return get(expected).removeAll(o); 902 } 903 } 904 } 905 906 public boolean retainAll(Collection o) { 907 if (fast) { 908 synchronized (FastArrayList.this) { 909 ArrayList temp = (ArrayList) list.clone(); 910 List sub = get(temp); 911 boolean r = sub.retainAll(o); 912 if (r) last = first + sub.size(); 913 list = temp; 914 expected = temp; 915 return r; 916 } 917 } else { 918 synchronized (list) { 919 return get(expected).retainAll(o); 920 } 921 } 922 } 923 924 public int size() { 925 if (fast) { 926 return get(expected).size(); 927 } else { 928 synchronized (list) { 929 return get(expected).size(); 930 } 931 } 932 } 933 934 935 public boolean isEmpty() { 936 if (fast) { 937 return get(expected).isEmpty(); 938 } else { 939 synchronized (list) { 940 return get(expected).isEmpty(); 941 } 942 } 943 } 944 945 public boolean contains(Object o) { 946 if (fast) { 947 return get(expected).contains(o); 948 } else { 949 synchronized (list) { 950 return get(expected).contains(o); 951 } 952 } 953 } 954 955 public boolean containsAll(Collection o) { 956 if (fast) { 957 return get(expected).containsAll(o); 958 } else { 959 synchronized (list) { 960 return get(expected).containsAll(o); 961 } 962 } 963 } 964 965 public Object[] toArray(Object[] o) { 966 if (fast) { 967 return get(expected).toArray(o); 968 } else { 969 synchronized (list) { 970 return get(expected).toArray(o); 971 } 972 } 973 } 974 975 public Object[] toArray() { 976 if (fast) { 977 return get(expected).toArray(); 978 } else { 979 synchronized (list) { 980 return get(expected).toArray(); 981 } 982 } 983 } 984 985 986 public boolean equals(Object o) { 987 if (o == this) return true; 988 if (fast) { 989 return get(expected).equals(o); 990 } else { 991 synchronized (list) { 992 return get(expected).equals(o); 993 } 994 } 995 } 996 997 public int hashCode() { 998 if (fast) { 999 return get(expected).hashCode(); 1000 } else { 1001 synchronized (list) { 1002 return get(expected).hashCode(); 1003 } 1004 } 1005 } 1006 1007 public boolean add(Object o) { 1008 if (fast) { 1009 synchronized (FastArrayList.this) { 1010 ArrayList temp = (ArrayList) list.clone(); 1011 boolean r = get(temp).add(o); 1012 if (r) last++; 1013 list = temp; 1014 expected = temp; 1015 return r; 1016 } 1017 } else { 1018 synchronized (list) { 1019 return get(expected).add(o); 1020 } 1021 } 1022 } 1023 1024 public boolean addAll(Collection o) { 1025 if (fast) { 1026 synchronized (FastArrayList.this) { 1027 ArrayList temp = (ArrayList) list.clone(); 1028 boolean r = get(temp).addAll(o); 1029 if (r) last += o.size(); 1030 list = temp; 1031 expected = temp; 1032 return r; 1033 } 1034 } else { 1035 synchronized (list) { 1036 return get(expected).addAll(o); 1037 } 1038 } 1039 } 1040 1041 public void add(int i, Object o) { 1042 if (fast) { 1043 synchronized (FastArrayList.this) { 1044 ArrayList temp = (ArrayList) list.clone(); 1045 get(temp).add(i, o); 1046 last++; 1047 list = temp; 1048 expected = temp; 1049 } 1050 } else { 1051 synchronized (list) { 1052 get(expected).add(i, o); 1053 } 1054 } 1055 } 1056 1057 public boolean addAll(int i, Collection o) { 1058 if (fast) { 1059 synchronized (FastArrayList.this) { 1060 ArrayList temp = (ArrayList) list.clone(); 1061 boolean r = get(temp).addAll(i, o); 1062 list = temp; 1063 if (r) last += o.size(); 1064 expected = temp; 1065 return r; 1066 } 1067 } else { 1068 synchronized (list) { 1069 return get(expected).addAll(i, o); 1070 } 1071 } 1072 } 1073 1074 public Object remove(int i) { 1075 if (fast) { 1076 synchronized (FastArrayList.this) { 1077 ArrayList temp = (ArrayList) list.clone(); 1078 Object o = get(temp).remove(i); 1079 last--; 1080 list = temp; 1081 expected = temp; 1082 return o; 1083 } 1084 } else { 1085 synchronized (list) { 1086 return get(expected).remove(i); 1087 } 1088 } 1089 } 1090 1091 public Object set(int i, Object a) { 1092 if (fast) { 1093 synchronized (FastArrayList.this) { 1094 ArrayList temp = (ArrayList) list.clone(); 1095 Object o = get(temp).set(i, a); 1096 list = temp; 1097 expected = temp; 1098 return o; 1099 } 1100 } else { 1101 synchronized (list) { 1102 return get(expected).set(i, a); 1103 } 1104 } 1105 } 1106 1107 1108 public Iterator iterator() { 1109 return new SubListIter(0); 1110 } 1111 1112 public ListIterator listIterator() { 1113 return new SubListIter(0); 1114 } 1115 1116 public ListIterator listIterator(int i) { 1117 return new SubListIter(i); 1118 } 1119 1120 1121 public Object get(int i) { 1122 if (fast) { 1123 return get(expected).get(i); 1124 } else { 1125 synchronized (list) { 1126 return get(expected).get(i); 1127 } 1128 } 1129 } 1130 1131 public int indexOf(Object o) { 1132 if (fast) { 1133 return get(expected).indexOf(o); 1134 } else { 1135 synchronized (list) { 1136 return get(expected).indexOf(o); 1137 } 1138 } 1139 } 1140 1141 1142 public int lastIndexOf(Object o) { 1143 if (fast) { 1144 return get(expected).lastIndexOf(o); 1145 } else { 1146 synchronized (list) { 1147 return get(expected).lastIndexOf(o); 1148 } 1149 } 1150 } 1151 1152 1153 public List subList(int f, int l) { 1154 if (list != expected) { 1155 throw new ConcurrentModificationException(); 1156 } 1157 return new SubList(first + f, f + l); 1158 } 1159 1160 1161 private class SubListIter implements ListIterator { 1162 1163 private List expected; 1164 private ListIterator iter; 1165 private int lastReturnedIndex = -1; 1166 1167 1168 public SubListIter(int i) { 1169 this.expected = list; 1170 this.iter = SubList.this.get(expected).listIterator(i); 1171 } 1172 1173 private void checkMod() { 1174 if (list != expected) { 1175 throw new ConcurrentModificationException(); 1176 } 1177 } 1178 1179 List get() { 1180 return SubList.this.get(expected); 1181 } 1182 1183 public boolean hasNext() { 1184 checkMod(); 1185 return iter.hasNext(); 1186 } 1187 1188 public Object next() { 1189 checkMod(); 1190 lastReturnedIndex = iter.nextIndex(); 1191 return iter.next(); 1192 } 1193 1194 public boolean hasPrevious() { 1195 checkMod(); 1196 return iter.hasPrevious(); 1197 } 1198 1199 public Object previous() { 1200 checkMod(); 1201 lastReturnedIndex = iter.previousIndex(); 1202 return iter.previous(); 1203 } 1204 1205 public int previousIndex() { 1206 checkMod(); 1207 return iter.previousIndex(); 1208 } 1209 1210 public int nextIndex() { 1211 checkMod(); 1212 return iter.nextIndex(); 1213 } 1214 1215 public void remove() { 1216 checkMod(); 1217 if (lastReturnedIndex < 0) { 1218 throw new IllegalStateException(); 1219 } 1220 get().remove(lastReturnedIndex); 1221 last--; 1222 expected = list; 1223 iter = get().listIterator(lastReturnedIndex); 1224 lastReturnedIndex = -1; 1225 } 1226 1227 public void set(Object o) { 1228 checkMod(); 1229 if (lastReturnedIndex < 0) { 1230 throw new IllegalStateException(); 1231 } 1232 get().set(lastReturnedIndex, o); 1233 expected = list; 1234 iter = get().listIterator(previousIndex() + 1); 1235 } 1236 1237 public void add(Object o) { 1238 checkMod(); 1239 int i = nextIndex(); 1240 get().add(i, o); 1241 last++; 1242 expected = list; 1243 iter = get().listIterator(i + 1); 1244 lastReturnedIndex = -1; 1245 } 1246 1247 } 1248 1249 1250 } 1251 1252 1253 1254 private class ListIter implements ListIterator { 1255 1256 private List expected; 1257 private ListIterator iter; 1258 private int lastReturnedIndex = -1; 1259 1260 1261 public ListIter(int i) { 1262 this.expected = list; 1263 this.iter = get().listIterator(i); 1264 } 1265 1266 private void checkMod() { 1267 if (list != expected) { 1268 throw new ConcurrentModificationException(); 1269 } 1270 } 1271 1272 List get() { 1273 return expected; 1274 } 1275 1276 public boolean hasNext() { 1277 return iter.hasNext(); 1278 } 1279 1280 public Object next() { 1281 lastReturnedIndex = iter.nextIndex(); 1282 return iter.next(); 1283 } 1284 1285 public boolean hasPrevious() { 1286 return iter.hasPrevious(); 1287 } 1288 1289 public Object previous() { 1290 lastReturnedIndex = iter.previousIndex(); 1291 return iter.previous(); 1292 } 1293 1294 public int previousIndex() { 1295 return iter.previousIndex(); 1296 } 1297 1298 public int nextIndex() { 1299 return iter.nextIndex(); 1300 } 1301 1302 public void remove() { 1303 checkMod(); 1304 if (lastReturnedIndex < 0) { 1305 throw new IllegalStateException(); 1306 } 1307 get().remove(lastReturnedIndex); 1308 expected = list; 1309 iter = get().listIterator(lastReturnedIndex); 1310 lastReturnedIndex = -1; 1311 } 1312 1313 public void set(Object o) { 1314 checkMod(); 1315 if (lastReturnedIndex < 0) { 1316 throw new IllegalStateException(); 1317 } 1318 get().set(lastReturnedIndex, o); 1319 expected = list; 1320 iter = get().listIterator(previousIndex() + 1); 1321 } 1322 1323 public void add(Object o) { 1324 checkMod(); 1325 int i = nextIndex(); 1326 get().add(i, o); 1327 expected = list; 1328 iter = get().listIterator(i + 1); 1329 lastReturnedIndex = -1; 1330 } 1331 1332 } 1333 }