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
1150 }
1151
1152 private void rangeCheck(int index) {
1153 if (index < 0 || index >= this.size)
1154 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1155 }
1156
1157 private void rangeCheckForAdd(int index) {
1158 if (index < 0 || index > this.size)
1159 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1160 }
1161
1162 private String outOfBoundsMsg(int index) {
1163 return "Index: "+index+", Size: "+this.size;
1164 }
1165
1166 private void checkForComodification() {
1167 if (ArrayList.this.modCount != this.modCount)
1168 throw new ConcurrentModificationException();
1169 }
1170 }
1171 }
|
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.Consumer;
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
1154 }
1155
1156 private void rangeCheck(int index) {
1157 if (index < 0 || index >= this.size)
1158 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1159 }
1160
1161 private void rangeCheckForAdd(int index) {
1162 if (index < 0 || index > this.size)
1163 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1164 }
1165
1166 private String outOfBoundsMsg(int index) {
1167 return "Index: "+index+", Size: "+this.size;
1168 }
1169
1170 private void checkForComodification() {
1171 if (ArrayList.this.modCount != this.modCount)
1172 throw new ConcurrentModificationException();
1173 }
1174 }
1175
1176 @Override
1177 public void forEach(Consumer<? super E> action) {
1178 Objects.requireNonNull(action);
1179 final int expectedModCount = modCount;
1180 @SuppressWarnings("unchecked")
1181 final E[] elementData = (E[]) this.elementData;
1182 final int size = this.size;
1183 for (int i=0; modCount == expectedModCount && i < size; i++) {
1184 action.accept(elementData[i]);
1185 }
1186 if (modCount != expectedModCount) {
1187 throw new ConcurrentModificationException();
1188 }
1189 }
1190
1191 @Override
1192 public boolean removeIf(Predicate<? super E> filter) {
1193 Objects.requireNonNull(filter);
1194 // figure out which elements are to be removed
1195 // any exception thrown from the filter predicate at this stage
1196 // will leave the collection unmodified
1197 int removeCount = 0;
1198 final BitSet removeSet = new BitSet(size);
1199 final int expectedModCount = modCount;
1200 final int size = this.size;
1201 for (int i=0; modCount == expectedModCount && i < size; i++) {
1202 @SuppressWarnings("unchecked")
1203 final E element = (E) elementData[i];
1204 if (filter.test(element)) {
1205 removeSet.set(i);
1206 removeCount++;
1207 }
1208 }
1209 if (modCount != expectedModCount) {
1210 throw new ConcurrentModificationException();
1211 }
1212
1213 // shift surviving elements left over the spaces left by removed elements
1214 final boolean anyToRemove = removeCount > 0;
1215 if (anyToRemove) {
1216 final int newSize = size - removeCount;
1217 for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
1218 i = removeSet.nextClearBit(i);
1219 elementData[j] = elementData[i];
1220 }
1221 for (int k=newSize; k < size; k++) {
1222 elementData[k] = null; // Let gc do its work
1223 }
1224 this.size = newSize;
1225 if (modCount != expectedModCount) {
1226 throw new ConcurrentModificationException();
1227 }
1228 modCount++;
1229 }
1230
1231 return anyToRemove;
1232 }
1233
1234 @Override
1235 @SuppressWarnings("unchecked")
1236 public void replaceAll(UnaryOperator<E> operator) {
1237 Objects.requireNonNull(operator);
1238 final int expectedModCount = modCount;
1239 final int size = this.size;
1240 for (int i=0; modCount == expectedModCount && i < size; i++) {
1241 elementData[i] = operator.apply((E) elementData[i]);
1242 }
1243 if (modCount != expectedModCount) {
1244 throw new ConcurrentModificationException();
1245 }
1246 modCount++;
1247 }
1248
1249 @Override
1250 @SuppressWarnings("unchecked")
1251 public void sort(Comparator<? super E> c) {
1252 final int expectedModCount = modCount;
1253 Arrays.sort((E[]) elementData, 0, size, c);
1254 if (modCount != expectedModCount) {
1255 throw new ConcurrentModificationException();
1256 }
1257 modCount++;
1258 }
1259 }
|