Java > Open Source Codes > org > apache > commons > collections > FastArrayList


1 /*
2  * Copyright 2001-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package org.apache.commons.collections;
17
18 import java.util.ArrayList ;
19 import java.util.Collection ;
20 import java.util.ConcurrentModificationException ;
21 import java.util.Iterator ;
22 import java.util.List ;
23 import java.util.ListIterator ;
24
25 /**
26  * <p>A customized implementation of <code>java.util.ArrayList</code> designed
27  * to operate in a multithreaded environment where the large majority of
28  * method calls are read-only, instead of structural changes. When operating
29  * in "fast" mode, read calls are non-synchronized and write calls perform the
30  * following steps:</p>
31  * <ul>
32  * <li>Clone the existing collection
33  * <li>Perform the modification on the clone
34  * <li>Replace the existing collection with the (modified) clone
35  * </ul>
36  * <p>When first created, objects of this class default to "slow" mode, where
37  * all accesses of any type are synchronized but no cloning takes place. This
38  * is appropriate for initially populating the collection, followed by a switch
39  * to "fast" mode (by calling <code>setFast(true)</code>) after initialization
40  * is complete.</p>
41  *
42  * <p><strong>NOTE</strong>: If you are creating and accessing an
43  * <code>ArrayList</code> only within a single thread, you should use
44  * <code>java.util.ArrayList</code> directly (with no synchronization), for
45  * maximum performance.</p>
46  *
47  * <p><strong>NOTE</strong>: <i>This class is not cross-platform.
48  * Using it may cause unexpected failures on some architectures.</i>
49  * It suffers from the same problems as the double-checked locking idiom.
50  * In particular, the instruction that clones the internal collection and the
51  * instruction that sets the internal reference to the clone can be executed
52  * or perceived out-of-order. This means that any read operation might fail
53  * unexpectedly, as it may be reading the state of the internal collection
54  * before the internal collection is fully formed.
55  * For more information on the double-checked locking idiom, see the
56  * <a HREF="http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html">
57  * Double-Checked Locking Idiom Is Broken Declaration</a>.</p>
58  *
59  * @since Commons Collections 1.0
60  * @version $Revision: 1.15 $ $Date: 2004/02/18 01:15:42 $
61  *
62  * @author Craig R. McClanahan
63  */
64 public class FastArrayList extends ArrayList {
65
66
67     // ----------------------------------------------------------- Constructors
68
69
70     /**
71      * Construct a an empty list.
72      */
73     public FastArrayList() {
74
75         super();
76         this.list = new ArrayList ();
77
78     }
79
80
81     /**
82      * Construct an empty list with the specified capacity.
83      *
84      * @param capacity The initial capacity of the empty list
85      */
86     public FastArrayList(int capacity) {
87
88         super();
89         this.list = new ArrayList (capacity);
90
91     }
92
93
94     /**
95      * Construct a list containing the elements of the specified collection,
96      * in the order they are returned by the collection's iterator.
97      *
98      * @param collection The collection whose elements initialize the contents
99      * of this list
100      */
101     public FastArrayList(Collection collection) {
102
103         super();
104         this.list = new ArrayList (collection);
105
106     }
107
108
109     // ----------------------------------------------------- Instance Variables
110
111
112     /**
113      * The underlying list we are managing.
114      */
115     protected ArrayList list = null;
116
117
118     // ------------------------------------------------------------- Properties
119
120
121     /**
122      * Are we operating in "fast" mode?
123      */
124     protected boolean fast = false;
125
126
127     /**
128      * Returns true if this list is operating in fast mode.
129      *
130      * @return true if this list is operating in fast mode
131      */
132     public boolean getFast() {
133         return (this.fast);
134     }
135
136     /**
137      * Sets whether this list will operate in fast mode.
138      *
139      * @param fast true if the list should operate in fast mode
140      */
141     public void setFast(boolean fast) {
142         this.fast = fast;
143     }
144
145
146     // --------------------------------------------------------- Public Methods
147
148
149     /**
150      * Appends the specified element to the end of this list.
151      *
152      * @param element The element to be appended
153      */
154     public boolean add(Object element) {
155
156         if (fast) {
157             synchronized (this) {
158                 ArrayList temp = (ArrayList ) list.clone();
159                 boolean result = temp.add(element);
160                 list = temp;
161                 return (result);
162             }
163         } else {
164             synchronized (list) {
165                 return (list.add(element));
166             }
167         }
168
169     }
170
171
172     /**
173      * Insert the specified element at the specified position in this list,
174      * and shift all remaining elements up one position.
175      *
176      * @param index Index at which to insert this element
177      * @param element The element to be inserted
178      *
179      * @exception IndexOutOfBoundsException if the index is out of range
180      */
181     public void add(int index, Object element) {
182
183         if (fast) {
184             synchronized (this) {
185                 ArrayList temp = (ArrayList ) list.clone();
186                 temp.add(index, element);
187                 list = temp;
188             }
189         } else {
190             synchronized (list) {
191                 list.add(index, element);
192             }
193         }
194
195     }
196
197
198     /**
199      * Append all of the elements in the specified Collection to the end
200      * of this list, in the order that they are returned by the specified
201      * Collection's Iterator.
202      *
203      * @param collection The collection to be appended
204      */
205     public boolean addAll(Collection collection) {
206
207         if (fast) {
208             synchronized (this) {
209                 ArrayList temp = (ArrayList ) list.clone();
210                 boolean result = temp.addAll(collection);
211                 list = temp;
212                 return (result);
213             }
214         } else {
215             synchronized (list) {
216                 return (list.addAll(collection));
217             }
218         }
219
220     }
221
222
223     /**
224      * Insert all of the elements in the specified Collection at the specified
225      * position in this list, and shift any previous elements upwards as
226      * needed.
227      *
228      * @param index Index at which insertion takes place
229      * @param collection The collection to be added
230      *
231      * @exception IndexOutOfBoundsException if the index is out of range
232      */
233     public boolean addAll(int index, Collection collection) {
234
235         if (fast) {
236             synchronized (this) {
237                 ArrayList temp = (ArrayList ) list.clone();
238                 boolean result = temp.addAll(index, collection);
239                 list = temp;
240                 return (result);
241             }
242         } else {
243             synchronized (list) {
244                 return (list.addAll(index, collection));
245             }
246         }
247
248     }
249
250
251     /**
252      * Remove all of the elements from this list. The list will be empty
253      * after this call returns.
254      *
255      * @exception UnsupportedOperationException if <code>clear()</code>
256      * is not supported by this list
257      */
258     public void clear() {
259
260         if (fast) {
261             synchronized (this) {
262                 ArrayList temp = (ArrayList ) list.clone();
263                 temp.clear();
264                 list = temp;
265             }
266         } else {
267             synchronized (list) {
268                 list.clear();
269             }
270         }
271
272     }
273
274
275     /**
276      * Return a shallow copy of this <code>FastArrayList</code> instance.
277      * The elements themselves are not copied.
278      */
279     public Object clone() {
280
281         FastArrayList results = null;
282         if (fast) {
283             results = new FastArrayList(list);
284         } else {
285             synchronized (list) {
286                 results = new FastArrayList(list);
287             }
288         }
289         results.setFast(getFast());
290         return (results);
291
292     }
293
294
295     /**
296      * Return <code>true</code> if this list contains the specified element.
297      *
298      * @param element The element to test for
299      */
300     public boolean contains(Object element) {
301
302         if (fast) {
303             return (list.contains(element));
304         } else {
305             synchronized (list) {
306                 return (list.contains(element));
307             }
308         }
309
310     }
311
312
313     /**
314      * Return <code>true</code> if this list contains all of the elements
315      * in the specified Collection.
316      *
317      * @param collection Collection whose elements are to be checked
318      */
319     public boolean containsAll(Collection collection) {
320
321         if (fast) {
322             return (list.containsAll(collection));
323         } else {
324             synchronized (list) {
325                 return (list.containsAll(collection));
326             }
327         }
328
329     }
330
331
332     /**
333      * Increase the capacity of this <code>ArrayList</code> instance, if
334      * necessary, to ensure that it can hold at least the number of elements
335      * specified by the minimum capacity argument.
336      *
337      * @param capacity The new minimum capacity
338      */
339     public void ensureCapacity(int capacity) {
340
341         if (fast) {
342             synchronized (this) {
343                 ArrayList temp = (ArrayList ) list.clone();
344                 temp.ensureCapacity(capacity);
345                 list = temp;
346             }
347         } else {
348             synchronized (list) {
349                 list.ensureCapacity(capacity);
350             }
351         }
352
353     }
354
355
356     /**
357      * Compare the specified object with this list for equality. This
358      * implementation uses exactly the code that is used to define the
359      * list equals function in the documentation for the
360      * <code>List.equals</code> method.
361      *
362      * @param o Object to be compared to this list
363      */
364     public boolean equals(Object o) {
365
366         // Simple tests that require no synchronization
367 if (o == this)
368             return (true);
369         else if (!(o instanceof List ))
370             return (false);
371         List lo = (List ) o;
372
373         // Compare the sets of elements for equality
374 if (fast) {
375             ListIterator li1 = list.listIterator();
376             ListIterator li2 = lo.listIterator();
377             while (li1.hasNext() && li2.hasNext()) {
378                 Object o1 = li1.next();
379                 Object o2 = li2.next();
380                 if (!(o1 == null ? o2 == null : o1.equals(o2)))
381                     return (false);
382             }
383             return (!(li1.hasNext() || li2.hasNext()));
384         } else {
385             synchronized (list) {
386                 ListIterator li1 = list.listIterator();
387                 ListIterator li2 = lo.listIterator();
388                 while (li1.hasNext() && li2.hasNext()) {
389                     Object o1 = li1.next();
390                     Object o2 = li2.next();
391                     if (!(o1 == null ? o2 == null : o1.equals(o2)))
392                         return (false);
393                 }
394                 return (!(li1.hasNext() || li2.hasNext()));
395             }
396         }
397
398     }
399
400
401     /**
402      * Return the element at the specified position in the list.
403      *
404      * @param index The index of the element to return
405      *
406      * @exception IndexOutOfBoundsException if the index is out of range
407      */
408     public Object get(int index) {
409
410         if (fast) {
411             return (list.get(index));
412         } else {
413             synchronized (list) {
414                 return (list.get(index));
415             }
416         }
417
418     }
419
420
421     /**
422      * Return the hash code value for this list. This implementation uses
423      * exactly the code that is used to define the list hash function in the
424      * documentation for the <code>List.hashCode</code> method.
425      */
426     public int hashCode() {
427
428         if (fast) {
429             int hashCode = 1;
430             java.util.Iterator i = list.iterator();
431             while (i.hasNext()) {
432                 Object o = i.next();
433                 hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode());
434             }
435             return (hashCode);
436         } else {
437             synchronized (list) {
438                 int hashCode = 1;
439                 java.util.Iterator i = list.iterator();
440                 while (i.hasNext()) {
441                     Object o = i.next();
442                     hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode());
443                 }
444                 return (hashCode);
445             }
446         }
447
448     }
449
450
451     /**
452      * Search for the first occurrence of the given argument, testing
453      * for equality using the <code>equals()</code> method, and return
454      * the corresponding index, or -1 if the object is not found.
455      *
456      * @param element The element to search for
457      */
458     public int indexOf(Object element) {
459
460         if (fast) {
461             return (list.indexOf(element));
462         } else {
463             synchronized (list) {
464                 return (list.indexOf(element));
465             }
466         }
467
468     }
469
470
471     /**
472      * Test if this list has no elements.
473      */
474     public boolean isEmpty() {
475
476         if (fast) {
477             return (list.isEmpty());
478         } else {
479             synchronized (list) {
480                 return (list.isEmpty());
481             }
482         }
483
484     }
485
486
487     /**
488      * Return an iterator over the elements in this list in proper sequence.
489      * <br><br>
490      * <strong>IMPLEMENTATION NOTE</strong> - If the list is operating in fast
491      * mode, an Iterator is returned, and a structural modification to the
492      * list is made, then the Iterator will continue over the previous contents
493      * of the list (at the time that the Iterator was created), rather than
494      * failing due to concurrent modifications.
495      */
496     public Iterator iterator() {
497         if (fast) {
498             return new ListIter(0);
499         } else {
500             return list.iterator();
501         }
502     }
503
504
505     /**
506      * Search for the last occurrence of the given argument, testing
507      * for equality using the <code>equals()</code> method, and return
508      * the corresponding index, or -1 if the object is not found.
509      *
510      * @param element The element to search for
511      */
512     public int lastIndexOf(Object element) {
513
514         if (fast) {
515             return (list.lastIndexOf(element));
516         } else {
517             synchronized (list) {
518                 return (list.lastIndexOf(element));
519             }
520         }
521
522     }
523
524
525     /**
526      * Return an iterator of the elements of this list, in proper sequence.
527      * See the implementation note on <code>iterator()</code>.
528      */
529     public ListIterator listIterator() {
530         if (fast) {
531             return new ListIter(0);
532         } else {
533             return list.listIterator();
534         }
535     }
536
537
538     /**
539      * Return an iterator of the elements of this list, in proper sequence,
540      * starting at the specified position.
541      * See the implementation note on <code>iterator()</code>.
542      *
543      * @param index The starting position of the iterator to return
544      *
545      * @exception IndexOutOfBoundsException if the index is out of range
546      */
547     public ListIterator listIterator(int index) {
548         if (fast) {
549             return new ListIter(index);
550         } else {
551             return list.listIterator(index);
552         }
553     }
554
555
556     /**
557      * Remove the element at the specified position in the list, and shift
558      * any subsequent elements down one position.
559      *
560      * @param index Index of the element to be removed
561      *
562      * @exception IndexOutOfBoundsException if the index is out of range
563      */
564     public Object remove(int index) {
565
566         if (fast) {
567             synchronized (this) {
568                 ArrayList temp = (ArrayList ) list.clone();
569                 Object result = temp.remove(index);
570                 list = temp;
571                 return (result);
572             }
573         } else {
574             synchronized (list) {
575                 return (list.remove(index));
576             }
577         }
578
579     }
580
581
582     /**
583      * Remove the first occurrence of the specified element from the list,
584      * and shift any subsequent elements down one position.
585      *
586      * @param element Element to be removed
587      */
588     public boolean remove(Object element) {
589
590         if (fast) {
591             synchronized (this) {
592                 ArrayList temp = (ArrayList ) list.clone();
593                 boolean result = temp.remove(element);
594                 list = temp;
595                 return (result);
596             }
597         } else {
598             synchronized (list) {
599                 return (list.remove(element));
600             }
601         }
602
603     }
604
605
606     /**
607      * Remove from this collection all of its elements that are contained
608      * in the specified collection.
609      *
610      * @param collection Collection containing elements to be removed
611      *
612      * @exception UnsupportedOperationException if this optional operation
613      * is not supported by this list
614      */
615     public boolean removeAll(Collection collection) {
616
617         if (fast) {
618             synchronized (this) {
619                 ArrayList temp = (ArrayList ) list.clone();
620                 boolean result = temp.removeAll(collection);
621                 list = temp;
622                 return (result);
623             }
624         } else {
625             synchronized (list) {
626                 return (list.removeAll(collection));
627             }
628         }
629
630     }
631
632
633     /**
634      * Remove from this collection all of its elements except those that are
635      * contained in the specified collection.
636      *
637      * @param collection Collection containing elements to be retained
638      *
639      * @exception UnsupportedOperationException if this optional operation
640      * is not supported by this list
641      */
642     public boolean retainAll(Collection collection) {
643
644         if (fast) {
645             synchronized (this) {
646                 ArrayList temp = (ArrayList ) list.clone();
647                 boolean result = temp.retainAll(collection);
648                 list = temp;
649                 return (result);
650             }
651         } else {
652             synchronized (list) {
653                 return (list.retainAll(collection));
654             }
655         }
656
657     }
658
659
660     /**
661      * Replace the element at the specified position in this list with
662      * the specified element. Returns the previous object at that position.
663      * <br><br>
664      * <strong>IMPLEMENTATION NOTE</strong> - This operation is specifically
665      * documented to not be a structural change, so it is safe to be performed
666      * without cloning.
667      *
668      * @param index Index of the element to replace
669      * @param element The new element to be stored
670      *
671      * @exception IndexOutOfBoundsException if the index is out of range
672      */
673     public Object set(int index, Object element) {
674
675         if (fast) {
676             return (list.set(index, element));
677         } else {
678             synchronized (list) {
679                 return (list.set(index, element));
680             }
681         }
682
683     }
684
685
686     /**
687      * Return the number of elements in this list.
688      */
689     public int size() {
690
691         if (fast) {
692             return (list.size());
693         } else {
694             synchronized (list) {
695                 return (list.size());
696             }
697         }
698
699     }
700
701
702     /**
703      * Return a view of the portion of this list between fromIndex
704      * (inclusive) and toIndex (exclusive). The returned list is backed
705      * by this list, so non-structural changes in the returned list are
706      * reflected in this list. The returned list supports
707      * all of the optional list operations supported by this list.
708      *
709      * @param fromIndex The starting index of the sublist view
710      * @param toIndex The index after the end of the sublist view
711      *
712      * @exception IndexOutOfBoundsException if an index is out of range
713      */
714     public List subList(int fromIndex, int toIndex) {
715         if (fast) {
716             return new SubList(fromIndex, toIndex);
717         } else {
718             return list.subList(fromIndex, toIndex);
719         }
720     }
721
722
723     /**
724      * Return an array containing all of the elements in this list in the
725      * correct order.
726      */
727     public Object [] toArray() {
728
729         if (fast) {
730             return (list.toArray());
731         } else {
732             synchronized (list) {
733                 return (list.toArray());
734             }
735         }
736
737     }
738
739
740     /**
741      * Return an array containing all of the elements in this list in the
742      * correct order. The runtime type of the returned array is that of
743      * the specified array. If the list fits in the specified array, it is
744      * returned therein. Otherwise, a new array is allocated with the
745      * runtime type of the specified array, and the size of this list.
746      *
747      * @param array Array defining the element type of the returned list
748      *
749      * @exception ArrayStoreException if the runtime type of <code>array</code>
750      * is not a supertype of the runtime type of every element in this list
751      */
752     public Object [] toArray(Object array[]) {
753
754         if (fast) {
755             return (list.toArray(array));
756         } else {
757             synchronized (list) {
758                 return (list.toArray(array));
759             }
760         }
761
762     }
763
764
765     /**
766      * Return a String representation of this object.
767      */
768     public String toString() {
769
770         StringBuffer sb = new StringBuffer ("FastArrayList[");
771         sb.append(list.toString());
772         sb.append("]");
773         return (sb.toString());
774
775     }
776
777
778     /**
779      * Trim the capacity of this <code>ArrayList</code> instance to be the
780      * list's current size. An application can use this operation to minimize
781      * the storage of an <code>ArrayList</code> instance.
782      */
783     public void trimToSize() {
784
785         if (fast) {
786             synchronized (this) {
787                 ArrayList temp = (ArrayList ) list.clone();
788                 temp.trimToSize();
789                 list = temp;
790             }
791         } else {
792             synchronized (list) {
793                 list.trimToSize();
794             }
795         }
796
797     }
798
799
800
801     private class SubList implements List {
802
803         private int first;
804         private int last;
805         private List expected;
806
807
808         public SubList(int first, int last) {
809             this.first = first;
810             this.last = last;
811             this.expected = list;
812         }
813
814         private List get(List l) {
815             if (list != expected) {
816                 throw new ConcurrentModificationException ();
817             }
818             return l.subList(first, last);
819         }
820
821         public void clear() {
822             if (fast) {
823                 synchronized (FastArrayList.this) {
824                     ArrayList temp = (ArrayList ) list.clone();
825                     get(temp).clear();
826                     last = first;
827                     list = temp;
828                     expected = temp;
829                 }
830             } else {
831                 synchronized (list) {
832                     get(expected).clear();
833                 }
834             }
835         }
836
837         public boolean remove(Object o) {
838             if (fast) {
839                 synchronized (FastArrayList.this) {
840                     ArrayList temp = (ArrayList ) list.clone();
841                     boolean r = get(temp).remove(o);
842                     if (r) last--;
843                     list = temp;
844                     expected = temp;
845                     return r;
846                 }
847             } else {
848                 synchronized (list) {
849                     return get(expected).remove(o);
850                 }
851             }
852         }
853
854         public boolean removeAll(Collection o) {
855             if (fast) {
856                 synchronized (FastArrayList.this) {
857                     ArrayList temp = (ArrayList ) list.clone();
858                     List sub = get(temp);
859                     boolean r = sub.removeAll(o);
860                     if (r) last = first + sub.size();
861                     list = temp;
862                     expected = temp;
863                     return r;
864                 }
865             } else {
866                 synchronized (list) {
867                     return get(expected).removeAll(o);
868                 }
869             }
870         }
871
872         public boolean retainAll(Collection o) {
873             if (fast) {
874                 synchronized (FastArrayList.this) {
875                     ArrayList temp = (ArrayList ) list.clone();
876                     List sub = get(temp);
877                     boolean r = sub.retainAll(o);
878                     if (r) last = first + sub.size();
879                     list = temp;
880                     expected = temp;
881                     return r;
882                 }
883             } else {
884                 synchronized (list) {
885                     return get(expected).retainAll(o);
886                 }
887             }
888         }
889
890         public int size() {
891             if (fast) {
892                 return get(expected).size();
893             } else {
894                 synchronized (list) {
895                     return get(expected).size();
896                 }
897             }
898         }
899
900
901         public boolean isEmpty() {
902             if (fast) {
903                 return get(expected).isEmpty();
904             } else {
905                 synchronized (list) {
906                     return get(expected).isEmpty();
907                 }
908             }
909         }
910
911         public boolean contains(Object o) {
912             if (fast) {
913                 return get(expected).contains(o);
914             } else {
915                 synchronized (list) {
916                     return get(expected).contains(o);
917                 }
918             }
919         }
920
921         public boolean containsAll(Collection