1 /*
2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
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
687 */
688 private void rangeCheck(int index) {
689 if (index >= size)
690 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
691 }
692
693 /**
694 * A version of rangeCheck used by add and addAll.
695 */
696 private void rangeCheckForAdd(int index) {
697 if (index > size || index < 0)
698 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
699 }
700
701 /**
702 * Constructs an IndexOutOfBoundsException detail message.
703 * Of the many possible refactorings of the error handling code,
704 * this "outlining" performs best with both server and client VMs.
705 */
706 private String outOfBoundsMsg(int index) {
707 return "Index: "+index+", Size: "+size;
708 }
709
710 /**
711 * A version used in checking (fromIndex > toIndex) condition
712 */
713 private static String outOfBoundsMsg(int fromIndex, int toIndex) {
714 return "From Index: " + fromIndex + " > To Index: " + toIndex;
715 }
716
717 /**
718 * Removes from this list all of its elements that are contained in the
719 * specified collection.
720 *
721 * @param c collection containing elements to be removed from this list
722 * @return {@code true} if this list changed as a result of the call
723 * @throws ClassCastException if the class of an element of this list
724 * is incompatible with the specified collection
725 * (<a href="Collection.html#optional-restrictions">optional</a>)
726 * @throws NullPointerException if this list contains a null element and the
727 * specified collection does not permit null elements
1025 * instead of a whole list. For example, the following idiom
1026 * removes a range of elements from a list:
1027 * <pre>
1028 * list.subList(from, to).clear();
1029 * </pre>
1030 * Similar idioms may be constructed for {@link #indexOf(Object)} and
1031 * {@link #lastIndexOf(Object)}, and all of the algorithms in the
1032 * {@link Collections} class can be applied to a subList.
1033 *
1034 * <p>The semantics of the list returned by this method become undefined if
1035 * the backing list (i.e., this list) is <i>structurally modified</i> in
1036 * any way other than via the returned list. (Structural modifications are
1037 * those that change the size of this list, or otherwise perturb it in such
1038 * a fashion that iterations in progress may yield incorrect results.)
1039 *
1040 * @throws IndexOutOfBoundsException {@inheritDoc}
1041 * @throws IllegalArgumentException {@inheritDoc}
1042 */
1043 public List<E> subList(int fromIndex, int toIndex) {
1044 subListRangeCheck(fromIndex, toIndex, size);
1045 return new SubList(this, 0, fromIndex, toIndex);
1046 }
1047
1048 static void subListRangeCheck(int fromIndex, int toIndex, int size) {
1049 if (fromIndex < 0)
1050 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
1051 if (toIndex > size)
1052 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
1053 if (fromIndex > toIndex)
1054 throw new IllegalArgumentException("fromIndex(" + fromIndex +
1055 ") > toIndex(" + toIndex + ")");
1056 }
1057
1058 private class SubList extends AbstractList<E> implements RandomAccess {
1059 private final AbstractList<E> parent;
1060 private final int parentOffset;
1061 private final int offset;
1062 int size;
1063
1064 SubList(AbstractList<E> parent,
1065 int offset, int fromIndex, int toIndex) {
1066 this.parent = parent;
1067 this.parentOffset = fromIndex;
1068 this.offset = offset + fromIndex;
1069 this.size = toIndex - fromIndex;
1070 this.modCount = ArrayList.this.modCount;
1071 }
1072
1073 public E set(int index, E e) {
1074 rangeCheck(index);
1075 checkForComodification();
1076 E oldValue = ArrayList.this.elementData(offset + index);
1077 ArrayList.this.elementData[offset + index] = e;
1078 return oldValue;
1079 }
1080
1081 public E get(int index) {
1082 rangeCheck(index);
1083 checkForComodification();
1084 return ArrayList.this.elementData(offset + index);
1085 }
1086
1087 public int size() {
1088 checkForComodification();
1089 return this.size;
1090 }
1091
1092 public void add(int index, E e) {
1093 rangeCheckForAdd(index);
1094 checkForComodification();
1095 parent.add(parentOffset + index, e);
1096 this.modCount = parent.modCount;
1097 this.size++;
1098 }
1099
1100 public E remove(int index) {
1101 rangeCheck(index);
1102 checkForComodification();
1103 E result = parent.remove(parentOffset + index);
1104 this.modCount = parent.modCount;
1105 this.size--;
1106 return result;
1107 }
1108
1109 protected void removeRange(int fromIndex, int toIndex) {
1110 checkForComodification();
1111 parent.removeRange(parentOffset + fromIndex,
1112 parentOffset + toIndex);
1113 this.modCount = parent.modCount;
1114 this.size -= toIndex - fromIndex;
1115 }
1116
1117 public boolean addAll(Collection<? extends E> c) {
1118 return addAll(this.size, c);
1119 }
1120
1121 public boolean addAll(int index, Collection<? extends E> c) {
1122 rangeCheckForAdd(index);
1123 int cSize = c.size();
1124 if (cSize==0)
1125 return false;
1126
1127 checkForComodification();
1128 parent.addAll(parentOffset + index, c);
1129 this.modCount = parent.modCount;
1130 this.size += cSize;
1131 return true;
1132 }
1133
1134 public Iterator<E> iterator() {
1135 return listIterator();
1136 }
1137
1138 public ListIterator<E> listIterator(final int index) {
1139 checkForComodification();
1140 rangeCheckForAdd(index);
1141 final int offset = this.offset;
1142
1143 return new ListIterator<E>() {
1144 int cursor = index;
1145 int lastRet = -1;
1146 int expectedModCount = ArrayList.this.modCount;
1147
1148 public boolean hasNext() {
1149 return cursor != SubList.this.size;
1150 }
1151
1152 @SuppressWarnings("unchecked")
1153 public E next() {
1154 checkForComodification();
1155 int i = cursor;
1156 if (i >= SubList.this.size)
1157 throw new NoSuchElementException();
1158 Object[] elementData = ArrayList.this.elementData;
1159 if (offset + i >= elementData.length)
1160 throw new ConcurrentModificationException();
1161 cursor = i + 1;
1162 return (E) elementData[offset + (lastRet = i)];
1163 }
1164
1165 public boolean hasPrevious() {
1166 return cursor != 0;
1167 }
1168
1169 @SuppressWarnings("unchecked")
1170 public E previous() {
1171 checkForComodification();
1172 int i = cursor - 1;
1173 if (i < 0)
1174 throw new NoSuchElementException();
1175 Object[] elementData = ArrayList.this.elementData;
1176 if (offset + i >= elementData.length)
1177 throw new ConcurrentModificationException();
1178 cursor = i;
1179 return (E) elementData[offset + (lastRet = i)];
1180 }
1181
1182 @SuppressWarnings("unchecked")
1183 public void forEachRemaining(Consumer<? super E> consumer) {
1184 Objects.requireNonNull(consumer);
1185 final int size = SubList.this.size;
1186 int i = cursor;
1187 if (i >= size) {
1188 return;
1189 }
1190 final Object[] elementData = ArrayList.this.elementData;
1191 if (offset + i >= elementData.length) {
1192 throw new ConcurrentModificationException();
1193 }
1194 while (i != size && modCount == expectedModCount) {
1195 consumer.accept((E) elementData[offset + (i++)]);
1196 }
1197 // update once at end of iteration to reduce heap write traffic
1198 lastRet = cursor = i;
1199 checkForComodification();
1200 }
1201
1202 public int nextIndex() {
1203 return cursor;
1204 }
1205
1206 public int previousIndex() {
1207 return cursor - 1;
1208 }
1209
1210 public void remove() {
1211 if (lastRet < 0)
1212 throw new IllegalStateException();
1213 checkForComodification();
1214
1215 try {
1216 SubList.this.remove(lastRet);
1217 cursor = lastRet;
1218 lastRet = -1;
1219 expectedModCount = ArrayList.this.modCount;
1220 } catch (IndexOutOfBoundsException ex) {
1221 throw new ConcurrentModificationException();
1222 }
1223 }
1224
1225 public void set(E e) {
1226 if (lastRet < 0)
1227 throw new IllegalStateException();
1228 checkForComodification();
1229
1230 try {
1231 ArrayList.this.set(offset + lastRet, e);
1232 } catch (IndexOutOfBoundsException ex) {
1233 throw new ConcurrentModificationException();
1234 }
1235 }
1236
1237 public void add(E e) {
1238 checkForComodification();
1239
1240 try {
1241 int i = cursor;
1242 SubList.this.add(i, e);
1243 cursor = i + 1;
1244 lastRet = -1;
1245 expectedModCount = ArrayList.this.modCount;
1246 } catch (IndexOutOfBoundsException ex) {
1247 throw new ConcurrentModificationException();
1248 }
1249 }
1250
1251 final void checkForComodification() {
1252 if (expectedModCount != ArrayList.this.modCount)
1253 throw new ConcurrentModificationException();
1254 }
1255 };
1256 }
1257
1258 public List<E> subList(int fromIndex, int toIndex) {
1259 subListRangeCheck(fromIndex, toIndex, size);
1260 return new SubList(this, offset, fromIndex, toIndex);
1261 }
1262
1263 private void rangeCheck(int index) {
1264 if (index < 0 || index >= this.size)
1265 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1266 }
1267
1268 private void rangeCheckForAdd(int index) {
1269 if (index < 0 || index > this.size)
1270 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1271 }
1272
1273 private String outOfBoundsMsg(int index) {
1274 return "Index: "+index+", Size: "+this.size;
1275 }
1276
1277 private void checkForComodification() {
1278 if (ArrayList.this.modCount != this.modCount)
1279 throw new ConcurrentModificationException();
1280 }
1281
1282 public Spliterator<E> spliterator() {
1283 checkForComodification();
1284 return new ArrayListSpliterator<>(ArrayList.this, offset,
1285 offset + this.size, this.modCount);
1286 }
1287 }
1288
1289 @Override
1290 public void forEach(Consumer<? super E> action) {
1291 Objects.requireNonNull(action);
1292 final int expectedModCount = modCount;
1293 @SuppressWarnings("unchecked")
1294 final E[] elementData = (E[]) this.elementData;
1295 final int size = this.size;
1296 for (int i=0; modCount == expectedModCount && i < size; i++) {
1297 action.accept(elementData[i]);
1298 }
1299 if (modCount != expectedModCount) {
1300 throw new ConcurrentModificationException();
1301 }
1302 }
1303
1304 /**
1305 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
|
1 /*
2 * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
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
687 */
688 private void rangeCheck(int index) {
689 if (index >= size)
690 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
691 }
692
693 /**
694 * A version of rangeCheck used by add and addAll.
695 */
696 private void rangeCheckForAdd(int index) {
697 if (index > size || index < 0)
698 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
699 }
700
701 /**
702 * Constructs an IndexOutOfBoundsException detail message.
703 * Of the many possible refactorings of the error handling code,
704 * this "outlining" performs best with both server and client VMs.
705 */
706 private String outOfBoundsMsg(int index) {
707 return "Index: " + index + ", Size: " + size;
708 }
709
710 /**
711 * A version used in checking (fromIndex > toIndex) condition
712 */
713 private static String outOfBoundsMsg(int fromIndex, int toIndex) {
714 return "From Index: " + fromIndex + " > To Index: " + toIndex;
715 }
716
717 /**
718 * Removes from this list all of its elements that are contained in the
719 * specified collection.
720 *
721 * @param c collection containing elements to be removed from this list
722 * @return {@code true} if this list changed as a result of the call
723 * @throws ClassCastException if the class of an element of this list
724 * is incompatible with the specified collection
725 * (<a href="Collection.html#optional-restrictions">optional</a>)
726 * @throws NullPointerException if this list contains a null element and the
727 * specified collection does not permit null elements
1025 * instead of a whole list. For example, the following idiom
1026 * removes a range of elements from a list:
1027 * <pre>
1028 * list.subList(from, to).clear();
1029 * </pre>
1030 * Similar idioms may be constructed for {@link #indexOf(Object)} and
1031 * {@link #lastIndexOf(Object)}, and all of the algorithms in the
1032 * {@link Collections} class can be applied to a subList.
1033 *
1034 * <p>The semantics of the list returned by this method become undefined if
1035 * the backing list (i.e., this list) is <i>structurally modified</i> in
1036 * any way other than via the returned list. (Structural modifications are
1037 * those that change the size of this list, or otherwise perturb it in such
1038 * a fashion that iterations in progress may yield incorrect results.)
1039 *
1040 * @throws IndexOutOfBoundsException {@inheritDoc}
1041 * @throws IllegalArgumentException {@inheritDoc}
1042 */
1043 public List<E> subList(int fromIndex, int toIndex) {
1044 subListRangeCheck(fromIndex, toIndex, size);
1045 return new SubList<>(this, fromIndex, toIndex);
1046 }
1047
1048 private static class SubList<E> extends AbstractList<E> implements RandomAccess {
1049 private final ArrayList<E> root;
1050 private final SubList<E> parent;
1051 private final int offset;
1052 private int size;
1053
1054 /**
1055 * Constructs a sublist of an arbitrary ArrayList.
1056 */
1057 public SubList(ArrayList<E> root, int fromIndex, int toIndex) {
1058 this.root = root;
1059 this.parent = null;
1060 this.offset = fromIndex;
1061 this.size = toIndex - fromIndex;
1062 this.modCount = root.modCount;
1063 }
1064
1065 /**
1066 * Constructs a sublist of another SubList.
1067 */
1068 private SubList(SubList<E> parent, int fromIndex, int toIndex) {
1069 this.root = parent.root;
1070 this.parent = parent;
1071 this.offset = parent.offset + fromIndex;
1072 this.size = toIndex - fromIndex;
1073 this.modCount = root.modCount;
1074 }
1075
1076 public E set(int index, E element) {
1077 rangeCheck(index);
1078 checkForComodification();
1079 E oldValue = root.elementData(offset + index);
1080 root.elementData[offset + index] = element;
1081 return oldValue;
1082 }
1083
1084 public E get(int index) {
1085 rangeCheck(index);
1086 checkForComodification();
1087 return root.elementData(offset + index);
1088 }
1089
1090 public int size() {
1091 checkForComodification();
1092 return size;
1093 }
1094
1095 public void add(int index, E element) {
1096 rangeCheckForAdd(index);
1097 checkForComodification();
1098 root.add(offset + index, element);
1099 updateSizeAndModCount(1);
1100 }
1101
1102 public E remove(int index) {
1103 rangeCheck(index);
1104 checkForComodification();
1105 E result = root.remove(offset + index);
1106 updateSizeAndModCount(-1);
1107 return result;
1108 }
1109
1110 protected void removeRange(int fromIndex, int toIndex) {
1111 checkForComodification();
1112 root.removeRange(offset + fromIndex, offset + toIndex);
1113 updateSizeAndModCount(fromIndex - toIndex);
1114 }
1115
1116 public boolean addAll(Collection<? extends E> c) {
1117 return addAll(this.size, c);
1118 }
1119
1120 public boolean addAll(int index, Collection<? extends E> c) {
1121 rangeCheckForAdd(index);
1122 int cSize = c.size();
1123 if (cSize == 0)
1124 return false;
1125 checkForComodification();
1126 root.addAll(offset + index, c);
1127 updateSizeAndModCount(cSize);
1128 return true;
1129 }
1130
1131 public Iterator<E> iterator() {
1132 return listIterator();
1133 }
1134
1135 public ListIterator<E> listIterator(int index) {
1136 checkForComodification();
1137 rangeCheckForAdd(index);
1138
1139 return new ListIterator<E>() {
1140 int cursor = index;
1141 int lastRet = -1;
1142 int expectedModCount = root.modCount;
1143
1144 public boolean hasNext() {
1145 return cursor != SubList.this.size;
1146 }
1147
1148 @SuppressWarnings("unchecked")
1149 public E next() {
1150 checkForComodification();
1151 int i = cursor;
1152 if (i >= SubList.this.size)
1153 throw new NoSuchElementException();
1154 Object[] elementData = root.elementData;
1155 if (offset + i >= elementData.length)
1156 throw new ConcurrentModificationException();
1157 cursor = i + 1;
1158 return (E) elementData[offset + (lastRet = i)];
1159 }
1160
1161 public boolean hasPrevious() {
1162 return cursor != 0;
1163 }
1164
1165 @SuppressWarnings("unchecked")
1166 public E previous() {
1167 checkForComodification();
1168 int i = cursor - 1;
1169 if (i < 0)
1170 throw new NoSuchElementException();
1171 Object[] elementData = root.elementData;
1172 if (offset + i >= elementData.length)
1173 throw new ConcurrentModificationException();
1174 cursor = i;
1175 return (E) elementData[offset + (lastRet = i)];
1176 }
1177
1178 @SuppressWarnings("unchecked")
1179 public void forEachRemaining(Consumer<? super E> consumer) {
1180 Objects.requireNonNull(consumer);
1181 final int size = SubList.this.size;
1182 int i = cursor;
1183 if (i >= size) {
1184 return;
1185 }
1186 final Object[] elementData = root.elementData;
1187 if (offset + i >= elementData.length) {
1188 throw new ConcurrentModificationException();
1189 }
1190 while (i != size && modCount == expectedModCount) {
1191 consumer.accept((E) elementData[offset + (i++)]);
1192 }
1193 // update once at end of iteration to reduce heap write traffic
1194 lastRet = cursor = i;
1195 checkForComodification();
1196 }
1197
1198 public int nextIndex() {
1199 return cursor;
1200 }
1201
1202 public int previousIndex() {
1203 return cursor - 1;
1204 }
1205
1206 public void remove() {
1207 if (lastRet < 0)
1208 throw new IllegalStateException();
1209 checkForComodification();
1210
1211 try {
1212 SubList.this.remove(lastRet);
1213 cursor = lastRet;
1214 lastRet = -1;
1215 expectedModCount = root.modCount;
1216 } catch (IndexOutOfBoundsException ex) {
1217 throw new ConcurrentModificationException();
1218 }
1219 }
1220
1221 public void set(E e) {
1222 if (lastRet < 0)
1223 throw new IllegalStateException();
1224 checkForComodification();
1225
1226 try {
1227 root.set(offset + lastRet, e);
1228 } catch (IndexOutOfBoundsException ex) {
1229 throw new ConcurrentModificationException();
1230 }
1231 }
1232
1233 public void add(E e) {
1234 checkForComodification();
1235
1236 try {
1237 int i = cursor;
1238 SubList.this.add(i, e);
1239 cursor = i + 1;
1240 lastRet = -1;
1241 expectedModCount = root.modCount;
1242 } catch (IndexOutOfBoundsException ex) {
1243 throw new ConcurrentModificationException();
1244 }
1245 }
1246
1247 final void checkForComodification() {
1248 if (root.modCount != expectedModCount)
1249 throw new ConcurrentModificationException();
1250 }
1251 };
1252 }
1253
1254 public List<E> subList(int fromIndex, int toIndex) {
1255 subListRangeCheck(fromIndex, toIndex, size);
1256 return new SubList<>(this, fromIndex, toIndex);
1257 }
1258
1259 private void rangeCheck(int index) {
1260 if (index < 0 || index >= size)
1261 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1262 }
1263
1264 private void rangeCheckForAdd(int index) {
1265 if (index < 0 || index > size)
1266 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1267 }
1268
1269 private String outOfBoundsMsg(int index) {
1270 return "Index: " + index + ", Size: " + size;
1271 }
1272
1273 private void checkForComodification() {
1274 if (root.modCount != modCount)
1275 throw new ConcurrentModificationException();
1276 }
1277
1278 private void updateSizeAndModCount(int sizeChange) {
1279 SubList<E> slist = this;
1280 do {
1281 slist.size += sizeChange;
1282 slist.modCount = root.modCount;
1283 slist = slist.parent;
1284 } while (slist != null);
1285 }
1286
1287 public Spliterator<E> spliterator() {
1288 checkForComodification();
1289 return new ArrayListSpliterator<>(root, offset,
1290 offset + size, modCount);
1291 }
1292 }
1293
1294 @Override
1295 public void forEach(Consumer<? super E> action) {
1296 Objects.requireNonNull(action);
1297 final int expectedModCount = modCount;
1298 @SuppressWarnings("unchecked")
1299 final E[] elementData = (E[]) this.elementData;
1300 final int size = this.size;
1301 for (int i=0; modCount == expectedModCount && i < size; i++) {
1302 action.accept(elementData[i]);
1303 }
1304 if (modCount != expectedModCount) {
1305 throw new ConcurrentModificationException();
1306 }
1307 }
1308
1309 /**
1310 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
|