655 */
656 private void rangeCheck(int index) {
657 if (index >= size)
658 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
659 }
660
661 /**
662 * A version of rangeCheck used by add and addAll.
663 */
664 private void rangeCheckForAdd(int index) {
665 if (index > size || index < 0)
666 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
667 }
668
669 /**
670 * Constructs an IndexOutOfBoundsException detail message.
671 * Of the many possible refactorings of the error handling code,
672 * this "outlining" performs best with both server and client VMs.
673 */
674 private String outOfBoundsMsg(int index) {
675 return "Index: "+index+", Size: "+size;
676 }
677
678 /**
679 * A version used in checking (fromIndex > toIndex) condition
680 */
681 private static String outOfBoundsMsg(int fromIndex, int toIndex) {
682 return "From Index: " + fromIndex + " > To Index: " + toIndex;
683 }
684
685 /**
686 * Removes from this list all of its elements that are contained in the
687 * specified collection.
688 *
689 * @param c collection containing elements to be removed from this list
690 * @return {@code true} if this list changed as a result of the call
691 * @throws ClassCastException if the class of an element of this list
692 * is incompatible with the specified collection
693 * (<a href="Collection.html#optional-restrictions">optional</a>)
694 * @throws NullPointerException if this list contains a null element and the
695 * specified collection does not permit null elements
989 * instead of a whole list. For example, the following idiom
990 * removes a range of elements from a list:
991 * <pre>
992 * list.subList(from, to).clear();
993 * </pre>
994 * Similar idioms may be constructed for {@link #indexOf(Object)} and
995 * {@link #lastIndexOf(Object)}, and all of the algorithms in the
996 * {@link Collections} class can be applied to a subList.
997 *
998 * <p>The semantics of the list returned by this method become undefined if
999 * the backing list (i.e., this list) is <i>structurally modified</i> in
1000 * any way other than via the returned list. (Structural modifications are
1001 * those that change the size of this list, or otherwise perturb it in such
1002 * a fashion that iterations in progress may yield incorrect results.)
1003 *
1004 * @throws IndexOutOfBoundsException {@inheritDoc}
1005 * @throws IllegalArgumentException {@inheritDoc}
1006 */
1007 public List<E> subList(int fromIndex, int toIndex) {
1008 subListRangeCheck(fromIndex, toIndex, size);
1009 return new SubList(this, 0, fromIndex, toIndex);
1010 }
1011
1012 static void subListRangeCheck(int fromIndex, int toIndex, int size) {
1013 if (fromIndex < 0)
1014 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
1015 if (toIndex > size)
1016 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
1017 if (fromIndex > toIndex)
1018 throw new IllegalArgumentException("fromIndex(" + fromIndex +
1019 ") > toIndex(" + toIndex + ")");
1020 }
1021
1022 private class SubList extends AbstractList<E> implements RandomAccess {
1023 private final AbstractList<E> parent;
1024 private final int parentOffset;
1025 private final int offset;
1026 int size;
1027
1028 SubList(AbstractList<E> parent,
1029 int offset, int fromIndex, int toIndex) {
1030 this.parent = parent;
1031 this.parentOffset = fromIndex;
1032 this.offset = offset + fromIndex;
1033 this.size = toIndex - fromIndex;
1034 this.modCount = ArrayList.this.modCount;
1035 }
1036
1037 public E set(int index, E e) {
1038 rangeCheck(index);
1039 checkForComodification();
1040 E oldValue = ArrayList.this.elementData(offset + index);
1041 ArrayList.this.elementData[offset + index] = e;
1042 return oldValue;
1043 }
1044
1045 public E get(int index) {
1046 rangeCheck(index);
1047 checkForComodification();
1048 return ArrayList.this.elementData(offset + index);
1049 }
1050
1051 public int size() {
1052 checkForComodification();
1053 return this.size;
1054 }
1055
1056 public void add(int index, E e) {
1057 rangeCheckForAdd(index);
1058 checkForComodification();
1059 parent.add(parentOffset + index, e);
1060 this.modCount = parent.modCount;
1061 this.size++;
1062 }
1063
1064 public E remove(int index) {
1065 rangeCheck(index);
1066 checkForComodification();
1067 E result = parent.remove(parentOffset + index);
1068 this.modCount = parent.modCount;
1069 this.size--;
1070 return result;
1071 }
1072
1073 protected void removeRange(int fromIndex, int toIndex) {
1074 checkForComodification();
1075 parent.removeRange(parentOffset + fromIndex,
1076 parentOffset + toIndex);
1077 this.modCount = parent.modCount;
1078 this.size -= toIndex - fromIndex;
1079 }
1080
1081 public boolean addAll(Collection<? extends E> c) {
1082 return addAll(this.size, c);
1083 }
1084
1085 public boolean addAll(int index, Collection<? extends E> c) {
1086 rangeCheckForAdd(index);
1087 int cSize = c.size();
1088 if (cSize==0)
1089 return false;
1090
1091 checkForComodification();
1092 parent.addAll(parentOffset + index, c);
1093 this.modCount = parent.modCount;
1094 this.size += cSize;
1095 return true;
1096 }
1097
1098 public Iterator<E> iterator() {
1099 return listIterator();
1100 }
1101
1102 public ListIterator<E> listIterator(final int index) {
1103 checkForComodification();
1104 rangeCheckForAdd(index);
1105 final int offset = this.offset;
1106
1107 return new ListIterator<E>() {
1108 int cursor = index;
1109 int lastRet = -1;
1110 int expectedModCount = ArrayList.this.modCount;
1111
1112 public boolean hasNext() {
1113 return cursor != SubList.this.size;
1114 }
1115
1116 @SuppressWarnings("unchecked")
1117 public E next() {
1118 checkForComodification();
1119 int i = cursor;
1120 if (i >= SubList.this.size)
1121 throw new NoSuchElementException();
1122 Object[] elementData = ArrayList.this.elementData;
1123 if (offset + i >= elementData.length)
1124 throw new ConcurrentModificationException();
1125 cursor = i + 1;
1126 return (E) elementData[offset + (lastRet = i)];
1127 }
1128
1129 public boolean hasPrevious() {
1130 return cursor != 0;
1131 }
1132
1133 @SuppressWarnings("unchecked")
1134 public E previous() {
1135 checkForComodification();
1136 int i = cursor - 1;
1137 if (i < 0)
1138 throw new NoSuchElementException();
1139 Object[] elementData = ArrayList.this.elementData;
1140 if (offset + i >= elementData.length)
1141 throw new ConcurrentModificationException();
1142 cursor = i;
1143 return (E) elementData[offset + (lastRet = i)];
1144 }
1145
1146 @SuppressWarnings("unchecked")
1147 public void forEachRemaining(Consumer<? super E> consumer) {
1148 Objects.requireNonNull(consumer);
1149 final int size = SubList.this.size;
1150 int i = cursor;
1151 if (i >= size) {
1152 return;
1153 }
1154 final Object[] elementData = ArrayList.this.elementData;
1155 if (offset + i >= elementData.length) {
1156 throw new ConcurrentModificationException();
1157 }
1158 while (i != size && modCount == expectedModCount) {
1159 consumer.accept((E) elementData[offset + (i++)]);
1160 }
1161 // update once at end of iteration to reduce heap write traffic
1162 lastRet = cursor = i;
1163 checkForComodification();
1164 }
1165
1166 public int nextIndex() {
1167 return cursor;
1168 }
1169
1170 public int previousIndex() {
1171 return cursor - 1;
1172 }
1173
1174 public void remove() {
1175 if (lastRet < 0)
1176 throw new IllegalStateException();
1177 checkForComodification();
1178
1179 try {
1180 SubList.this.remove(lastRet);
1181 cursor = lastRet;
1182 lastRet = -1;
1183 expectedModCount = ArrayList.this.modCount;
1184 } catch (IndexOutOfBoundsException ex) {
1185 throw new ConcurrentModificationException();
1186 }
1187 }
1188
1189 public void set(E e) {
1190 if (lastRet < 0)
1191 throw new IllegalStateException();
1192 checkForComodification();
1193
1194 try {
1195 ArrayList.this.set(offset + lastRet, e);
1196 } catch (IndexOutOfBoundsException ex) {
1197 throw new ConcurrentModificationException();
1198 }
1199 }
1200
1201 public void add(E e) {
1202 checkForComodification();
1203
1204 try {
1205 int i = cursor;
1206 SubList.this.add(i, e);
1207 cursor = i + 1;
1208 lastRet = -1;
1209 expectedModCount = ArrayList.this.modCount;
1210 } catch (IndexOutOfBoundsException ex) {
1211 throw new ConcurrentModificationException();
1212 }
1213 }
1214
1215 final void checkForComodification() {
1216 if (expectedModCount != ArrayList.this.modCount)
1217 throw new ConcurrentModificationException();
1218 }
1219 };
1220 }
1221
1222 public List<E> subList(int fromIndex, int toIndex) {
1223 subListRangeCheck(fromIndex, toIndex, size);
1224 return new SubList(this, offset, fromIndex, toIndex);
1225 }
1226
1227 private void rangeCheck(int index) {
1228 if (index < 0 || index >= this.size)
1229 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1230 }
1231
1232 private void rangeCheckForAdd(int index) {
1233 if (index < 0 || index > this.size)
1234 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1235 }
1236
1237 private String outOfBoundsMsg(int index) {
1238 return "Index: "+index+", Size: "+this.size;
1239 }
1240
1241 private void checkForComodification() {
1242 if (ArrayList.this.modCount != this.modCount)
1243 throw new ConcurrentModificationException();
1244 }
1245
1246 public Spliterator<E> spliterator() {
1247 checkForComodification();
1248 return new ArrayListSpliterator<>(ArrayList.this, offset,
1249 offset + this.size, this.modCount);
1250 }
1251 }
1252
1253 @Override
1254 public void forEach(Consumer<? super E> action) {
1255 Objects.requireNonNull(action);
1256 final int expectedModCount = modCount;
1257 @SuppressWarnings("unchecked")
1258 final E[] elementData = (E[]) this.elementData;
1259 final int size = this.size;
1260 for (int i=0; modCount == expectedModCount && i < size; i++) {
1261 action.accept(elementData[i]);
1262 }
1263 if (modCount != expectedModCount) {
1264 throw new ConcurrentModificationException();
1265 }
1266 }
1267
1268 /**
1269 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
|
655 */
656 private void rangeCheck(int index) {
657 if (index >= size)
658 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
659 }
660
661 /**
662 * A version of rangeCheck used by add and addAll.
663 */
664 private void rangeCheckForAdd(int index) {
665 if (index > size || index < 0)
666 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
667 }
668
669 /**
670 * Constructs an IndexOutOfBoundsException detail message.
671 * Of the many possible refactorings of the error handling code,
672 * this "outlining" performs best with both server and client VMs.
673 */
674 private String outOfBoundsMsg(int index) {
675 return "Index: " + index + ", Size: " + size;
676 }
677
678 /**
679 * A version used in checking (fromIndex > toIndex) condition
680 */
681 private static String outOfBoundsMsg(int fromIndex, int toIndex) {
682 return "From Index: " + fromIndex + " > To Index: " + toIndex;
683 }
684
685 /**
686 * Removes from this list all of its elements that are contained in the
687 * specified collection.
688 *
689 * @param c collection containing elements to be removed from this list
690 * @return {@code true} if this list changed as a result of the call
691 * @throws ClassCastException if the class of an element of this list
692 * is incompatible with the specified collection
693 * (<a href="Collection.html#optional-restrictions">optional</a>)
694 * @throws NullPointerException if this list contains a null element and the
695 * specified collection does not permit null elements
989 * instead of a whole list. For example, the following idiom
990 * removes a range of elements from a list:
991 * <pre>
992 * list.subList(from, to).clear();
993 * </pre>
994 * Similar idioms may be constructed for {@link #indexOf(Object)} and
995 * {@link #lastIndexOf(Object)}, and all of the algorithms in the
996 * {@link Collections} class can be applied to a subList.
997 *
998 * <p>The semantics of the list returned by this method become undefined if
999 * the backing list (i.e., this list) is <i>structurally modified</i> in
1000 * any way other than via the returned list. (Structural modifications are
1001 * those that change the size of this list, or otherwise perturb it in such
1002 * a fashion that iterations in progress may yield incorrect results.)
1003 *
1004 * @throws IndexOutOfBoundsException {@inheritDoc}
1005 * @throws IllegalArgumentException {@inheritDoc}
1006 */
1007 public List<E> subList(int fromIndex, int toIndex) {
1008 subListRangeCheck(fromIndex, toIndex, size);
1009 return new SubList<>(this, fromIndex, toIndex);
1010 }
1011
1012 private static class SubList<E> extends AbstractList<E> implements RandomAccess {
1013 private final ArrayList<E> root;
1014 private final SubList<E> parent;
1015 private final int offset;
1016 private int size;
1017
1018 /**
1019 * Constructs a sublist of an arbitrary ArrayList.
1020 */
1021 public SubList(ArrayList<E> root, int fromIndex, int toIndex) {
1022 this.root = root;
1023 this.parent = null;
1024 this.offset = fromIndex;
1025 this.size = toIndex - fromIndex;
1026 this.modCount = root.modCount;
1027 }
1028
1029 /**
1030 * Constructs a sublist of another SubList.
1031 */
1032 private SubList(SubList<E> parent, int fromIndex, int toIndex) {
1033 this.root = parent.root;
1034 this.parent = parent;
1035 this.offset = parent.offset + fromIndex;
1036 this.size = toIndex - fromIndex;
1037 this.modCount = root.modCount;
1038 }
1039
1040 public E set(int index, E element) {
1041 rangeCheck(index);
1042 checkForComodification();
1043 E oldValue = root.elementData(offset + index);
1044 root.elementData[offset + index] = element;
1045 return oldValue;
1046 }
1047
1048 public E get(int index) {
1049 rangeCheck(index);
1050 checkForComodification();
1051 return root.elementData(offset + index);
1052 }
1053
1054 public int size() {
1055 checkForComodification();
1056 return size;
1057 }
1058
1059 public void add(int index, E element) {
1060 rangeCheckForAdd(index);
1061 checkForComodification();
1062 root.add(offset + index, element);
1063 updateSizeAndModCount(1);
1064 }
1065
1066 public E remove(int index) {
1067 rangeCheck(index);
1068 checkForComodification();
1069 E result = root.remove(offset + index);
1070 updateSizeAndModCount(-1);
1071 return result;
1072 }
1073
1074 protected void removeRange(int fromIndex, int toIndex) {
1075 checkForComodification();
1076 root.removeRange(offset + fromIndex, offset + toIndex);
1077 updateSizeAndModCount(fromIndex - toIndex);
1078 }
1079
1080 public boolean addAll(Collection<? extends E> c) {
1081 return addAll(this.size, c);
1082 }
1083
1084 public boolean addAll(int index, Collection<? extends E> c) {
1085 rangeCheckForAdd(index);
1086 int cSize = c.size();
1087 if (cSize == 0)
1088 return false;
1089 checkForComodification();
1090 root.addAll(offset + index, c);
1091 updateSizeAndModCount(cSize);
1092 return true;
1093 }
1094
1095 public Iterator<E> iterator() {
1096 return listIterator();
1097 }
1098
1099 public ListIterator<E> listIterator(int index) {
1100 checkForComodification();
1101 rangeCheckForAdd(index);
1102
1103 return new ListIterator<E>() {
1104 int cursor = index;
1105 int lastRet = -1;
1106 int expectedModCount = root.modCount;
1107
1108 public boolean hasNext() {
1109 return cursor != SubList.this.size;
1110 }
1111
1112 @SuppressWarnings("unchecked")
1113 public E next() {
1114 checkForComodification();
1115 int i = cursor;
1116 if (i >= SubList.this.size)
1117 throw new NoSuchElementException();
1118 Object[] elementData = root.elementData;
1119 if (offset + i >= elementData.length)
1120 throw new ConcurrentModificationException();
1121 cursor = i + 1;
1122 return (E) elementData[offset + (lastRet = i)];
1123 }
1124
1125 public boolean hasPrevious() {
1126 return cursor != 0;
1127 }
1128
1129 @SuppressWarnings("unchecked")
1130 public E previous() {
1131 checkForComodification();
1132 int i = cursor - 1;
1133 if (i < 0)
1134 throw new NoSuchElementException();
1135 Object[] elementData = root.elementData;
1136 if (offset + i >= elementData.length)
1137 throw new ConcurrentModificationException();
1138 cursor = i;
1139 return (E) elementData[offset + (lastRet = i)];
1140 }
1141
1142 @SuppressWarnings("unchecked")
1143 public void forEachRemaining(Consumer<? super E> consumer) {
1144 Objects.requireNonNull(consumer);
1145 final int size = SubList.this.size;
1146 int i = cursor;
1147 if (i >= size) {
1148 return;
1149 }
1150 final Object[] elementData = root.elementData;
1151 if (offset + i >= elementData.length) {
1152 throw new ConcurrentModificationException();
1153 }
1154 while (i != size && modCount == expectedModCount) {
1155 consumer.accept((E) elementData[offset + (i++)]);
1156 }
1157 // update once at end of iteration to reduce heap write traffic
1158 lastRet = cursor = i;
1159 checkForComodification();
1160 }
1161
1162 public int nextIndex() {
1163 return cursor;
1164 }
1165
1166 public int previousIndex() {
1167 return cursor - 1;
1168 }
1169
1170 public void remove() {
1171 if (lastRet < 0)
1172 throw new IllegalStateException();
1173 checkForComodification();
1174
1175 try {
1176 SubList.this.remove(lastRet);
1177 cursor = lastRet;
1178 lastRet = -1;
1179 expectedModCount = root.modCount;
1180 } catch (IndexOutOfBoundsException ex) {
1181 throw new ConcurrentModificationException();
1182 }
1183 }
1184
1185 public void set(E e) {
1186 if (lastRet < 0)
1187 throw new IllegalStateException();
1188 checkForComodification();
1189
1190 try {
1191 root.set(offset + lastRet, e);
1192 } catch (IndexOutOfBoundsException ex) {
1193 throw new ConcurrentModificationException();
1194 }
1195 }
1196
1197 public void add(E e) {
1198 checkForComodification();
1199
1200 try {
1201 int i = cursor;
1202 SubList.this.add(i, e);
1203 cursor = i + 1;
1204 lastRet = -1;
1205 expectedModCount = root.modCount;
1206 } catch (IndexOutOfBoundsException ex) {
1207 throw new ConcurrentModificationException();
1208 }
1209 }
1210
1211 final void checkForComodification() {
1212 if (root.modCount != expectedModCount)
1213 throw new ConcurrentModificationException();
1214 }
1215 };
1216 }
1217
1218 public List<E> subList(int fromIndex, int toIndex) {
1219 subListRangeCheck(fromIndex, toIndex, size);
1220 return new SubList<>(this, fromIndex, toIndex);
1221 }
1222
1223 private void rangeCheck(int index) {
1224 if (index < 0 || index >= size)
1225 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1226 }
1227
1228 private void rangeCheckForAdd(int index) {
1229 if (index < 0 || index > size)
1230 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1231 }
1232
1233 private String outOfBoundsMsg(int index) {
1234 return "Index: " + index + ", Size: " + size;
1235 }
1236
1237 private void checkForComodification() {
1238 if (root.modCount != modCount)
1239 throw new ConcurrentModificationException();
1240 }
1241
1242 private void updateSizeAndModCount(int sizeChange) {
1243 SubList<E> slist = this;
1244 do {
1245 slist.size += sizeChange;
1246 slist.modCount = root.modCount;
1247 slist = slist.parent;
1248 } while (slist != null);
1249 }
1250
1251 public Spliterator<E> spliterator() {
1252 checkForComodification();
1253 return new ArrayListSpliterator<>(root, offset,
1254 offset + size, modCount);
1255 }
1256 }
1257
1258 @Override
1259 public void forEach(Consumer<? super E> action) {
1260 Objects.requireNonNull(action);
1261 final int expectedModCount = modCount;
1262 @SuppressWarnings("unchecked")
1263 final E[] elementData = (E[]) this.elementData;
1264 final int size = this.size;
1265 for (int i=0; modCount == expectedModCount && i < size; i++) {
1266 action.accept(elementData[i]);
1267 }
1268 if (modCount != expectedModCount) {
1269 throw new ConcurrentModificationException();
1270 }
1271 }
1272
1273 /**
1274 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
|