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    }