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 }