2
* Copyright 1999-2004 The Apache Software Foundation
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
8
* http://www.apache.org/licenses/LICENSE-2.0
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.
16
package org.apache.commons.collections;
19
import java.util.ArrayList;
20
import java.util.Collection;
21
import java.util.ConcurrentModificationException;
22
import java.util.Iterator;
23
import java.util.List;
24
import java.util.ListIterator;
28
* <p>A customized implementation of <code>java.util.ArrayList</code> designed
29
* to operate in a multithreaded environment where the large majority of
30
* method calls are read-only, instead of structural changes. When operating
31
* in "fast" mode, read calls are non-synchronized and write calls perform the
32
* following steps:</p>
34
* <li>Clone the existing collection
35
* <li>Perform the modification on the clone
36
* <li>Replace the existing collection with the (modified) clone
38
* <p>When first created, objects of this class default to "slow" mode, where
39
* all accesses of any type are synchronized but no cloning takes place. This
40
* is appropriate for initially populating the collection, followed by a switch
41
* to "fast" mode (by calling <code>setFast(true)</code>) after initialization
44
* <p><strong>NOTE</strong>: If you are creating and accessing an
45
* <code>ArrayList</code> only within a single thread, you should use
46
* <code>java.util.ArrayList</code> directly (with no synchronization), for
47
* maximum performance.</p>
49
* <P><strong>NOTE</strong>: <I>This class is not cross-platform.
50
* Using it may cause unexpected failures on some architectures.</I>
51
* It suffers from the same problems as the double-checked locking idiom.
52
* In particular, the instruction that clones the internal collection and the
53
* instruction that sets the internal reference to the clone can be executed
54
* or perceived out-of-order. This means that any read operation might fail
55
* unexpectedly, as it may be reading the state of the internal collection
56
* before the internal collection is fully formed.
57
* For more information on the double-checked locking idiom, see the
58
* <A Href="http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html">
59
* Double-Checked Locking Idiom Is Broken Declartion</A>.</P>
62
* @author Craig R. McClanahan
63
* @version $Revision: 1.9.2.1 $ $Date: 2004/05/22 12:14:02 $
66
public class FastArrayList extends ArrayList {
69
// ----------------------------------------------------------- Constructors
73
* Construct a an empty list.
75
public FastArrayList() {
78
this.list = new ArrayList();
84
* Construct an empty list with the specified capacity.
86
* @param capacity The initial capacity of the empty list
88
public FastArrayList(int capacity) {
91
this.list = new ArrayList(capacity);
97
* Construct a list containing the elements of the specified collection,
98
* in the order they are returned by the collection's iterator.
100
* @param collection The collection whose elements initialize the contents
103
public FastArrayList(Collection collection) {
106
this.list = new ArrayList(collection);
111
// ----------------------------------------------------- Instance Variables
115
* The underlying list we are managing.
117
protected ArrayList list = null;
120
// ------------------------------------------------------------- Properties
124
* Are we operating in "fast" mode?
126
protected boolean fast = false;
130
* Returns true if this list is operating in fast mode.
132
* @return true if this list is operating in fast mode
134
public boolean getFast() {
139
* Sets whether this list will operate in fast mode.
141
* @param fast true if the list should operate in fast mode
143
public void setFast(boolean fast) {
148
// --------------------------------------------------------- Public Methods
152
* Appends the specified element to the end of this list.
154
* @param element The element to be appended
156
public boolean add(Object element) {
159
synchronized (this) {
160
ArrayList temp = (ArrayList) list.clone();
161
boolean result = temp.add(element);
166
synchronized (list) {
167
return (list.add(element));
175
* Insert the specified element at the specified position in this list,
176
* and shift all remaining elements up one position.
178
* @param index Index at which to insert this element
179
* @param element The element to be inserted
181
* @exception IndexOutOfBoundsException if the index is out of range
183
public void add(int index, Object element) {
186
synchronized (this) {
187
ArrayList temp = (ArrayList) list.clone();
188
temp.add(index, element);
192
synchronized (list) {
193
list.add(index, element);
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.
205
* @param collection The collection to be appended
207
public boolean addAll(Collection collection) {
210
synchronized (this) {
211
ArrayList temp = (ArrayList) list.clone();
212
boolean result = temp.addAll(collection);
217
synchronized (list) {
218
return (list.addAll(collection));
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
230
* @param index Index at which insertion takes place
231
* @param collection The collection to be added
233
* @exception IndexOutOfBoundsException if the index is out of range
235
public boolean addAll(int index, Collection collection) {
238
synchronized (this) {
239
ArrayList temp = (ArrayList) list.clone();
240
boolean result = temp.addAll(index, collection);
245
synchronized (list) {
246
return (list.addAll(index, collection));
254
* Remove all of the elements from this list. The list will be empty
255
* after this call returns.
257
* @exception UnsupportedOperationException if <code>clear()</code>
258
* is not supported by this list
260
public void clear() {
263
synchronized (this) {
264
ArrayList temp = (ArrayList) list.clone();
269
synchronized (list) {
278
* Return a shallow copy of this <code>FastArrayList</code> instance.
279
* The elements themselves are not copied.
281
public Object clone() {
283
FastArrayList results = null;
285
results = new FastArrayList(list);
287
synchronized (list) {
288
results = new FastArrayList(list);
291
results.setFast(getFast());
298
* Return <code>true</code> if this list contains the specified element.
300
* @param element The element to test for
302
public boolean contains(Object element) {
305
return (list.contains(element));
307
synchronized (list) {
308
return (list.contains(element));
316
* Return <code>true</code> if this list contains all of the elements
317
* in the specified Collection.
319
* @param collection Collection whose elements are to be checked
321
public boolean containsAll(Collection collection) {
324
return (list.containsAll(collection));
326
synchronized (list) {
327
return (list.containsAll(collection));
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.
339
* @param capacity The new minimum capacity
341
public void ensureCapacity(int capacity) {
344
synchronized (this) {
345
ArrayList temp = (ArrayList) list.clone();
346
temp.ensureCapacity(capacity);
350
synchronized (list) {
351
list.ensureCapacity(capacity);
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.
364
* @param o Object to be compared to this list
366
public boolean equals(Object o) {
368
// Simple tests that require no synchronization
371
else if (!(o instanceof List))
375
// Compare the sets of elements for equality
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)))
385
return (!(li1.hasNext() || li2.hasNext()));
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)))
396
return (!(li1.hasNext() || li2.hasNext()));
404
* Return the element at the specified position in the list.
406
* @param index The index of the element to return
408
* @exception IndexOutOfBoundsException if the index is out of range
410
public Object get(int index) {
413
return (list.get(index));
415
synchronized (list) {
416
return (list.get(index));
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.
428
public int hashCode() {
432
java.util.Iterator i = list.iterator();
433
while (i.hasNext()) {
435
hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode());
439
synchronized (list) {
441
java.util.Iterator i = list.iterator();
442
while (i.hasNext()) {
444
hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode());
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.
458
* @param element The element to search for
460
public int indexOf(Object element) {
463
return (list.indexOf(element));
465
synchronized (list) {
466
return (list.indexOf(element));
474
* Test if this list has no elements.
476
public boolean isEmpty() {
479
return (list.isEmpty());
481
synchronized (list) {
482
return (list.isEmpty());
490
* Return an iterator over the elements in this list in proper sequence.
492
* <strong>IMPLEMENTATION NOTE</strong> - If the list is operating in fast
493
* mode, an Iterator is returned, and a structural modification to the
494
* list is made, then the Iterator will continue over the previous contents
495
* of the list (at the time that the Iterator was created), rather than
496
* failing due to concurrent modifications.
498
public Iterator iterator() {
500
return new ListIter(0);
502
return list.iterator();
508
* Search for the last occurrence of the given argument, testing
509
* for equality using the <code>equals()</code> method, and return
510
* the corresponding index, or -1 if the object is not found.
512
* @param element The element to search for
514
public int lastIndexOf(Object element) {
517
return (list.lastIndexOf(element));
519
synchronized (list) {
520
return (list.lastIndexOf(element));
528
* Return an iterator of the elements of this list, in proper sequence.
529
* See the implementation note on <code>iterator()</code>.
531
public ListIterator listIterator() {
533
return new ListIter(0);
535
return list.listIterator();
541
* Return an iterator of the elements of this list, in proper sequence,
542
* starting at the specified position.
543
* See the implementation note on <code>iterator()</code>.
545
* @param index The starting position of the iterator to return
547
* @exception IndexOutOfBoundsException if the index is out of range
549
public ListIterator listIterator(int index) {
551
return new ListIter(index);
553
return list.listIterator(index);
559
* Remove the element at the specified position in the list, and shift
560
* any subsequent elements down one position.
562
* @param index Index of the element to be removed
564
* @exception IndexOutOfBoundsException if the index is out of range
566
public Object remove(int index) {
569
synchronized (this) {
570
ArrayList temp = (ArrayList) list.clone();
571
Object result = temp.remove(index);
576
synchronized (list) {
577
return (list.remove(index));
585
* Remove the first occurrence of the specified element from the list,
586
* and shift any subsequent elements down one position.
588
* @param element Element to be removed
590
public boolean remove(Object element) {
593
synchronized (this) {
594
ArrayList temp = (ArrayList) list.clone();
595
boolean result = temp.remove(element);
600
synchronized (list) {
601
return (list.remove(element));
609
* Remove from this collection all of its elements that are contained
610
* in the specified collection.
612
* @param collection Collection containing elements to be removed
614
* @exception UnsupportedOperationException if this optional operation
615
* is not supported by this list
617
public boolean removeAll(Collection collection) {
620
synchronized (this) {
621
ArrayList temp = (ArrayList) list.clone();
622
boolean result = temp.removeAll(collection);
627
synchronized (list) {
628
return (list.removeAll(collection));
636
* Remove from this collection all of its elements except those that are
637
* contained in the specified collection.
639
* @param collection Collection containing elements to be retained
641
* @exception UnsupportedOperationException if this optional operation
642
* is not supported by this list
644
public boolean retainAll(Collection collection) {
647
synchronized (this) {
648
ArrayList temp = (ArrayList) list.clone();
649
boolean result = temp.retainAll(collection);
654
synchronized (list) {
655
return (list.retainAll(collection));
663
* Replace the element at the specified position in this list with
664
* the specified element. Returns the previous object at that position.
666
* <strong>IMPLEMENTATION NOTE</strong> - This operation is specifically
667
* documented to not be a structural change, so it is safe to be performed
670
* @param index Index of the element to replace
671
* @param element The new element to be stored
673
* @exception IndexOutOfBoundsException if the index is out of range
675
public Object set(int index, Object element) {
678
return (list.set(index, element));
680
synchronized (list) {
681
return (list.set(index, element));
689
* Return the number of elements in this list.
694
return (list.size());
696
synchronized (list) {
697
return (list.size());
705
* Return a view of the portion of this list between fromIndex
706
* (inclusive) and toIndex (exclusive). The returned list is backed
707
* by this list, so non-structural changes in the returned list are
708
* reflected in this list. The returned list supports
709
* all of the optional list operations supported by this list.
711
* @param fromIndex The starting index of the sublist view
712
* @param toIndex The index after the end of the sublist view
714
* @exception IndexOutOfBoundsException if an index is out of range
716
public List subList(int fromIndex, int toIndex) {
718
return new SubList(fromIndex, toIndex);
720
return list.subList(fromIndex, toIndex);
726
* Return an array containing all of the elements in this list in the
729
public Object[] toArray() {
732
return (list.toArray());
734
synchronized (list) {
735
return (list.toArray());
743
* Return an array containing all of the elements in this list in the
744
* correct order. The runtime type of the returned array is that of
745
* the specified array. If the list fits in the specified array, it is
746
* returned therein. Otherwise, a new array is allocated with the
747
* runtime type of the specified array, and the size of this list.
749
* @param array Array defining the element type of the returned list
751
* @exception ArrayStoreException if the runtime type of <code>array</code>
752
* is not a supertype of the runtime type of every element in this list
754
public Object[] toArray(Object array[]) {
757
return (list.toArray(array));
759
synchronized (list) {
760
return (list.toArray(array));
768
* Return a String representation of this object.
770
public String toString() {
772
StringBuffer sb = new StringBuffer("FastArrayList[");
773
sb.append(list.toString());
775
return (sb.toString());
781
* Trim the capacity of this <code>ArrayList</code> instance to be the
782
* list's current size. An application can use this operation to minimize
783
* the storage of an <code>ArrayList</code> instance.
785
public void trimToSize() {
788
synchronized (this) {
789
ArrayList temp = (ArrayList) list.clone();
794
synchronized (list) {
803
private class SubList implements List {
807
private List expected;
810
public SubList(int first, int last) {
813
this.expected = list;
816
private List get(List l) {
817
if (list != expected) {
818
throw new ConcurrentModificationException();
820
return l.subList(first, last);
823
public void clear() {
825
synchronized (FastArrayList.this) {
826
ArrayList temp = (ArrayList) list.clone();
833
synchronized (list) {
834
get(expected).clear();
839
public boolean remove(Object o) {
841
synchronized (FastArrayList.this) {
842
ArrayList temp = (ArrayList) list.clone();
843
boolean r = get(temp).remove(o);
850
synchronized (list) {
851
return get(expected).remove(o);
856
public boolean removeAll(Collection o) {
858
synchronized (FastArrayList.this) {
859
ArrayList temp = (ArrayList) list.clone();
860
List sub = get(temp);
861
boolean r = sub.removeAll(o);
862
if (r) last = first + sub.size();
868
synchronized (list) {
869
return get(expected).removeAll(o);
874
public boolean retainAll(Collection o) {
876
synchronized (FastArrayList.this) {
877
ArrayList temp = (ArrayList) list.clone();
878
List sub = get(temp);
879
boolean r = sub.retainAll(o);
880
if (r) last = first + sub.size();
886
synchronized (list) {
887
return get(expected).retainAll(o);
894
return get(expected).size();
896
synchronized (list) {
897
return get(expected).size();
903
public boolean isEmpty() {
905
return get(expected).isEmpty();
907
synchronized (list) {
908
return get(expected).isEmpty();
913
public boolean contains(Object o) {
915
return get(expected).contains(o);
917
synchronized (list) {
918
return get(expected).contains(o);
923
public boolean containsAll(Collection o) {
925
return get(expected).containsAll(o);
927
synchronized (list) {
928
return get(expected).containsAll(o);
933
public Object[] toArray(Object[] o) {
935
return get(expected).toArray(o);
937
synchronized (list) {
938
return get(expected).toArray(o);
943
public Object[] toArray() {
945
return get(expected).toArray();
947
synchronized (list) {
948
return get(expected).toArray();
954
public boolean equals(Object o) {
955
if (o == this) return true;
957
return get(expected).equals(o);
959
synchronized (list) {
960
return get(expected).equals(o);
965
public int hashCode() {
967
return get(expected).hashCode();
969
synchronized (list) {
970
return get(expected).hashCode();
975
public boolean add(Object o) {
977
synchronized (FastArrayList.this) {
978
ArrayList temp = (ArrayList) list.clone();
979
boolean r = get(temp).add(o);
986
synchronized (list) {
987
return get(expected).add(o);
992
public boolean addAll(Collection o) {
994
synchronized (FastArrayList.this) {
995
ArrayList temp = (ArrayList) list.clone();
996
boolean r = get(temp).addAll(o);
997
if (r) last += o.size();
1003
synchronized (list) {
1004
return get(expected).addAll(o);
1009
public void add(int i, Object o) {
1011
synchronized (FastArrayList.this) {
1012
ArrayList temp = (ArrayList) list.clone();
1013
get(temp).add(i, o);
1019
synchronized (list) {
1020
get(expected).add(i, o);
1025
public boolean addAll(int i, Collection o) {
1027
synchronized (FastArrayList.this) {
1028
ArrayList temp = (ArrayList) list.clone();
1029
boolean r = get(temp).addAll(i, o);
1031
if (r) last += o.size();
1036
synchronized (list) {
1037
return get(expected).addAll(i, o);
1042
public Object remove(int i) {
1044
synchronized (FastArrayList.this) {
1045
ArrayList temp = (ArrayList) list.clone();
1046
Object o = get(temp).remove(i);
1053
synchronized (list) {
1054
return get(expected).remove(i);
1059
public Object set(int i, Object a) {
1061
synchronized (FastArrayList.this) {
1062
ArrayList temp = (ArrayList) list.clone();
1063
Object o = get(temp).set(i, a);
1069
synchronized (list) {
1070
return get(expected).set(i, a);
1076
public Iterator iterator() {
1077
return new SubListIter(0);
1080
public ListIterator listIterator() {
1081
return new SubListIter(0);
1084
public ListIterator listIterator(int i) {
1085
return new SubListIter(i);
1089
public Object get(int i) {
1091
return get(expected).get(i);
1093
synchronized (list) {
1094
return get(expected).get(i);
1099
public int indexOf(Object o) {
1101
return get(expected).indexOf(o);
1103
synchronized (list) {
1104
return get(expected).indexOf(o);
1110
public int lastIndexOf(Object o) {
1112
return get(expected).lastIndexOf(o);
1114
synchronized (list) {
1115
return get(expected).lastIndexOf(o);
1121
public List subList(int f, int l) {
1122
if (list != expected) {
1123
throw new ConcurrentModificationException();
1125
return new SubList(first + f, f + l);
1129
private class SubListIter implements ListIterator {
1131
private List expected;
1132
private ListIterator iter;
1133
private int lastReturnedIndex = -1;
1136
public SubListIter(int i) {
1137
this.expected = list;
1138
this.iter = SubList.this.get(expected).listIterator(i);
1141
private void checkMod() {
1142
if (list != expected) {
1143
throw new ConcurrentModificationException();
1148
return SubList.this.get(expected);
1151
public boolean hasNext() {
1153
return iter.hasNext();
1156
public Object next() {
1158
lastReturnedIndex = iter.nextIndex();
1162
public boolean hasPrevious() {
1164
return iter.hasPrevious();
1167
public Object previous() {
1169
lastReturnedIndex = iter.previousIndex();
1170
return iter.previous();
1173
public int previousIndex() {
1175
return iter.previousIndex();
1178
public int nextIndex() {
1180
return iter.nextIndex();
1183
public void remove() {
1185
if (lastReturnedIndex < 0) {
1186
throw new IllegalStateException();
1188
get().remove(lastReturnedIndex);
1191
iter = get().listIterator(previousIndex());
1192
lastReturnedIndex = -1;
1195
public void set(Object o) {
1197
if (lastReturnedIndex < 0) {
1198
throw new IllegalStateException();
1200
get().set(lastReturnedIndex, o);
1202
iter = get().listIterator(previousIndex() + 1);
1205
public void add(Object o) {
1207
int i = nextIndex();
1210
iter = get().listIterator(i + 1);
1211
lastReturnedIndex = 1;
1221
private class ListIter implements ListIterator {
1223
private List expected;
1224
private ListIterator iter;
1225
private int lastReturnedIndex = -1;
1228
public ListIter(int i) {
1229
this.expected = list;
1230
this.iter = get().listIterator(i);
1233
private void checkMod() {
1234
if (list != expected) {
1235
throw new ConcurrentModificationException();
1243
public boolean hasNext() {
1245
return iter.hasNext();
1248
public Object next() {
1250
lastReturnedIndex = iter.nextIndex();
1254
public boolean hasPrevious() {
1256
return iter.hasPrevious();
1259
public Object previous() {
1261
lastReturnedIndex = iter.previousIndex();
1262
return iter.previous();
1265
public int previousIndex() {
1267
return iter.previousIndex();
1270
public int nextIndex() {
1272
return iter.nextIndex();
1275
public void remove() {
1277
if (lastReturnedIndex < 0) {
1278
throw new IllegalStateException();
1280
get().remove(lastReturnedIndex);
1282
iter = get().listIterator(previousIndex());
1283
lastReturnedIndex = -1;
1286
public void set(Object o) {
1288
if (lastReturnedIndex < 0) {
1289
throw new IllegalStateException();
1291
get().set(lastReturnedIndex, o);
1293
iter = get().listIterator(previousIndex() + 1);
1296
public void add(Object o) {
1298
int i = nextIndex();
1300
iter = get().listIterator(i + 1);
1301
lastReturnedIndex = 1;
added
removed
src/java/org/apache/commons/collections/FastArrayList.java
