8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 /**
29 * Resizable-array implementation of the <tt>List</tt> interface. Implements
30 * all optional list operations, and permits all elements, including
31 * <tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
32 * this class provides methods to manipulate the size of the array that is
33 * used internally to store the list. (This class is roughly equivalent to
34 * <tt>Vector</tt>, except that it is unsynchronized.)
35 *
36 * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
37 * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
38 * time. The <tt>add</tt> operation runs in <i>amortized constant time</i>,
39 * that is, adding n elements requires O(n) time. All of the other operations
40 * run in linear time (roughly speaking). The constant factor is low compared
41 * to that for the <tt>LinkedList</tt> implementation.
42 *
43 * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>. The capacity is
44 * the size of the array used to store the elements in the list. It is always
45 * at least as large as the list size. As elements are added to an ArrayList,
46 * its capacity grows automatically. The details of the growth policy are not
47 * specified beyond the fact that adding an element has constant amortized
1110 }
1111
1112 private void rangeCheck(int index) {
1113 if (index < 0 || index >= this.size)
1114 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1115 }
1116
1117 private void rangeCheckForAdd(int index) {
1118 if (index < 0 || index > this.size)
1119 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1120 }
1121
1122 private String outOfBoundsMsg(int index) {
1123 return "Index: "+index+", Size: "+this.size;
1124 }
1125
1126 private void checkForComodification() {
1127 if (ArrayList.this.modCount != this.modCount)
1128 throw new ConcurrentModificationException();
1129 }
1130 }
1131 }
|
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.util.function.Block;
29 import java.util.function.Predicate;
30 import java.util.function.UnaryOperator;
31
32 /**
33 * Resizable-array implementation of the <tt>List</tt> interface. Implements
34 * all optional list operations, and permits all elements, including
35 * <tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
36 * this class provides methods to manipulate the size of the array that is
37 * used internally to store the list. (This class is roughly equivalent to
38 * <tt>Vector</tt>, except that it is unsynchronized.)
39 *
40 * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
41 * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
42 * time. The <tt>add</tt> operation runs in <i>amortized constant time</i>,
43 * that is, adding n elements requires O(n) time. All of the other operations
44 * run in linear time (roughly speaking). The constant factor is low compared
45 * to that for the <tt>LinkedList</tt> implementation.
46 *
47 * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>. The capacity is
48 * the size of the array used to store the elements in the list. It is always
49 * at least as large as the list size. As elements are added to an ArrayList,
50 * its capacity grows automatically. The details of the growth policy are not
51 * specified beyond the fact that adding an element has constant amortized
1114 }
1115
1116 private void rangeCheck(int index) {
1117 if (index < 0 || index >= this.size)
1118 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1119 }
1120
1121 private void rangeCheckForAdd(int index) {
1122 if (index < 0 || index > this.size)
1123 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1124 }
1125
1126 private String outOfBoundsMsg(int index) {
1127 return "Index: "+index+", Size: "+this.size;
1128 }
1129
1130 private void checkForComodification() {
1131 if (ArrayList.this.modCount != this.modCount)
1132 throw new ConcurrentModificationException();
1133 }
1134 }
1135
1136 @Override
1137 public void forEach(Block<? super E> block) {
1138 Objects.requireNonNull(block);
1139 final int expectedModCount = modCount;
1140 final E[] elementData = (E[]) this.elementData;
1141 final int size = this.size;
1142 for (int i=0; modCount == expectedModCount && i < size; i++) {
1143 block.accept(elementData[i]);
1144 }
1145 if (modCount != expectedModCount) {
1146 throw new ConcurrentModificationException();
1147 }
1148 }
1149
1150 @Override
1151 public boolean removeAll(Predicate<? super E> filter) {
1152 Objects.requireNonNull(filter);
1153 // figure out which elements are to be removed
1154 // any exception thrown from the filter predicate at this stage
1155 // will leave the collection unmodified
1156 int removeCount = 0;
1157 final BitSet removeSet = new BitSet(size);
1158 final int expectedModCount = modCount;
1159 final int size = this.size;
1160 for (int i=0; modCount == expectedModCount && i < size; i++) {
1161 @SuppressWarnings("unchecked")
1162 final E element = (E) elementData[i];
1163 if (filter.test(element)) {
1164 removeSet.set(i);
1165 removeCount++;
1166 }
1167 }
1168
1169 if (modCount != expectedModCount) {
1170 throw new ConcurrentModificationException();
1171 }
1172
1173 // shift surviving elements left over the spaces left by removed elements
1174 final boolean anyToRemove = removeCount > 0;
1175 if (anyToRemove) {
1176 final int newSize = size - removeCount;
1177 for (int i=0, j=0; modCount == expectedModCount &&
1178 (i < size) && (j < newSize); i++, j++) {
1179 i = removeSet.nextClearBit(i);
1180 elementData[j] = elementData[i];
1181 }
1182 for (int k=newSize; modCount == expectedModCount && k < size; k++) {
1183 elementData[k] = null; // Let gc do its work
1184 }
1185 this.size = newSize;
1186 if (modCount != expectedModCount) {
1187 throw new ConcurrentModificationException();
1188 }
1189 modCount++;
1190 }
1191
1192 return anyToRemove;
1193 }
1194
1195 @Override
1196 @SuppressWarnings("unchecked")
1197 public void replaceAll(UnaryOperator<E> operator) {
1198 Objects.requireNonNull(operator);
1199 final int expectedModCount = modCount;
1200 final int size = this.size;
1201 for (int i=0; modCount == expectedModCount && i < size; i++) {
1202 elementData[i] = operator.operate((E) elementData[i]);
1203 }
1204 if (modCount != expectedModCount) {
1205 throw new ConcurrentModificationException();
1206 }
1207 modCount++;
1208 }
1209
1210 @Override
1211 @SuppressWarnings("unchecked")
1212 public void sort(Comparator<? super E> c) {
1213 Objects.requireNonNull(c);
1214 final int expectedModCount = modCount;
1215 Arrays.sort((E[]) elementData, 0, size, c);
1216 if (modCount != expectedModCount) {
1217 throw new ConcurrentModificationException();
1218 }
1219 modCount++;
1220 }
1221 }
|