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
415 if (a.length > size)
416 a[size] = null;
417 return a;
418 }
419
420 // Positional Access Operations
421
422 @SuppressWarnings("unchecked")
423 E elementData(int index) {
424 return (E) elementData[index];
425 }
426
427 /**
428 * Returns the element at the specified position in this list.
429 *
430 * @param index index of the element to return
431 * @return the element at the specified position in this list
432 * @throws IndexOutOfBoundsException {@inheritDoc}
433 */
434 public E get(int index) {
435 rangeCheck(index);
436
437 return elementData(index);
438 }
439
440 /**
441 * Replaces the element at the specified position in this list with
442 * the specified element.
443 *
444 * @param index index of the element to replace
445 * @param element element to be stored at the specified position
446 * @return the element previously at the specified position
447 * @throws IndexOutOfBoundsException {@inheritDoc}
448 */
449 public E set(int index, E element) {
450 rangeCheck(index);
451
452 E oldValue = elementData(index);
453 elementData[index] = element;
454 return oldValue;
455 }
456
457 /**
458 * This helper method split out from add(E) to keep method
459 * bytecode size under 35 (the -XX:MaxInlineSize default value),
460 * which helps when add(E) is called in a C1-compiled loop.
461 */
462 private void add(E e, Object[] elementData, int s) {
463 if (s == elementData.length)
464 elementData = grow();
465 elementData[s] = e;
466 size = s + 1;
467 }
468
469 /**
470 * Appends the specified element to the end of this list.
471 *
494 Object[] elementData;
495 if ((s = size) == (elementData = this.elementData).length)
496 elementData = grow();
497 System.arraycopy(elementData, index,
498 elementData, index + 1,
499 s - index);
500 elementData[index] = element;
501 size = s + 1;
502 }
503
504 /**
505 * Removes the element at the specified position in this list.
506 * Shifts any subsequent elements to the left (subtracts one from their
507 * indices).
508 *
509 * @param index the index of the element to be removed
510 * @return the element that was removed from the list
511 * @throws IndexOutOfBoundsException {@inheritDoc}
512 */
513 public E remove(int index) {
514 rangeCheck(index);
515
516 modCount++;
517 E oldValue = elementData(index);
518
519 int numMoved = size - index - 1;
520 if (numMoved > 0)
521 System.arraycopy(elementData, index+1, elementData, index,
522 numMoved);
523 elementData[--size] = null; // clear to let GC do its work
524
525 return oldValue;
526 }
527
528 /**
529 * Removes the first occurrence of the specified element from this list,
530 * if it is present. If the list does not contain the element, it is
531 * unchanged. More formally, removes the element with the lowest index
532 * {@code i} such that
533 * {@code Objects.equals(o, get(i))}
534 * (if such an element exists). Returns {@code true} if this list
663 */
664 protected void removeRange(int fromIndex, int toIndex) {
665 if (fromIndex > toIndex) {
666 throw new IndexOutOfBoundsException(
667 outOfBoundsMsg(fromIndex, toIndex));
668 }
669 modCount++;
670 int numMoved = size - toIndex;
671 System.arraycopy(elementData, toIndex, elementData, fromIndex,
672 numMoved);
673
674 // clear to let GC do its work
675 int newSize = size - (toIndex-fromIndex);
676 for (int i = newSize; i < size; i++) {
677 elementData[i] = null;
678 }
679 size = newSize;
680 }
681
682 /**
683 * Checks if the given index is in range. If not, throws an appropriate
684 * runtime exception. This method does *not* check if the index is
685 * negative: It is always used immediately prior to an array access,
686 * which throws an ArrayIndexOutOfBoundsException if index is negative.
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) {
837 } else if (size == 0) {
838 elementData = EMPTY_ELEMENTDATA;
839 } else {
840 throw new java.io.InvalidObjectException("Invalid size: " + size);
841 }
842 }
843
844 /**
845 * Returns a list iterator over the elements in this list (in proper
846 * sequence), starting at the specified position in the list.
847 * The specified index indicates the first element that would be
848 * returned by an initial call to {@link ListIterator#next next}.
849 * An initial call to {@link ListIterator#previous previous} would
850 * return the element with the specified index minus one.
851 *
852 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
853 *
854 * @throws IndexOutOfBoundsException {@inheritDoc}
855 */
856 public ListIterator<E> listIterator(int index) {
857 if (index < 0 || index > size)
858 throw new IndexOutOfBoundsException("Index: "+index);
859 return new ListItr(index);
860 }
861
862 /**
863 * Returns a list iterator over the elements in this list (in proper
864 * sequence).
865 *
866 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
867 *
868 * @see #listIterator(int)
869 */
870 public ListIterator<E> listIterator() {
871 return new ListItr(0);
872 }
873
874 /**
875 * Returns an iterator over the elements in this list in proper sequence.
876 *
877 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
878 *
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
415 if (a.length > size)
416 a[size] = null;
417 return a;
418 }
419
420 // Positional Access Operations
421
422 @SuppressWarnings("unchecked")
423 E elementData(int index) {
424 return (E) elementData[index];
425 }
426
427 /**
428 * Returns the element at the specified position in this list.
429 *
430 * @param index index of the element to return
431 * @return the element at the specified position in this list
432 * @throws IndexOutOfBoundsException {@inheritDoc}
433 */
434 public E get(int index) {
435 Objects.checkIndex(index, size);
436 return elementData(index);
437 }
438
439 /**
440 * Replaces the element at the specified position in this list with
441 * the specified element.
442 *
443 * @param index index of the element to replace
444 * @param element element to be stored at the specified position
445 * @return the element previously at the specified position
446 * @throws IndexOutOfBoundsException {@inheritDoc}
447 */
448 public E set(int index, E element) {
449 Objects.checkIndex(index, size);
450 E oldValue = elementData(index);
451 elementData[index] = element;
452 return oldValue;
453 }
454
455 /**
456 * This helper method split out from add(E) to keep method
457 * bytecode size under 35 (the -XX:MaxInlineSize default value),
458 * which helps when add(E) is called in a C1-compiled loop.
459 */
460 private void add(E e, Object[] elementData, int s) {
461 if (s == elementData.length)
462 elementData = grow();
463 elementData[s] = e;
464 size = s + 1;
465 }
466
467 /**
468 * Appends the specified element to the end of this list.
469 *
492 Object[] elementData;
493 if ((s = size) == (elementData = this.elementData).length)
494 elementData = grow();
495 System.arraycopy(elementData, index,
496 elementData, index + 1,
497 s - index);
498 elementData[index] = element;
499 size = s + 1;
500 }
501
502 /**
503 * Removes the element at the specified position in this list.
504 * Shifts any subsequent elements to the left (subtracts one from their
505 * indices).
506 *
507 * @param index the index of the element to be removed
508 * @return the element that was removed from the list
509 * @throws IndexOutOfBoundsException {@inheritDoc}
510 */
511 public E remove(int index) {
512 Objects.checkIndex(index, size);
513
514 modCount++;
515 E oldValue = elementData(index);
516
517 int numMoved = size - index - 1;
518 if (numMoved > 0)
519 System.arraycopy(elementData, index+1, elementData, index,
520 numMoved);
521 elementData[--size] = null; // clear to let GC do its work
522
523 return oldValue;
524 }
525
526 /**
527 * Removes the first occurrence of the specified element from this list,
528 * if it is present. If the list does not contain the element, it is
529 * unchanged. More formally, removes the element with the lowest index
530 * {@code i} such that
531 * {@code Objects.equals(o, get(i))}
532 * (if such an element exists). Returns {@code true} if this list
661 */
662 protected void removeRange(int fromIndex, int toIndex) {
663 if (fromIndex > toIndex) {
664 throw new IndexOutOfBoundsException(
665 outOfBoundsMsg(fromIndex, toIndex));
666 }
667 modCount++;
668 int numMoved = size - toIndex;
669 System.arraycopy(elementData, toIndex, elementData, fromIndex,
670 numMoved);
671
672 // clear to let GC do its work
673 int newSize = size - (toIndex-fromIndex);
674 for (int i = newSize; i < size; i++) {
675 elementData[i] = null;
676 }
677 size = newSize;
678 }
679
680 /**
681 * A version of rangeCheck used by add and addAll.
682 */
683 private void rangeCheckForAdd(int index) {
684 if (index > size || index < 0)
685 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
686 }
687
688 /**
689 * Constructs an IndexOutOfBoundsException detail message.
690 * Of the many possible refactorings of the error handling code,
691 * this "outlining" performs best with both server and client VMs.
692 */
693 private String outOfBoundsMsg(int index) {
694 return "Index: "+index+", Size: "+size;
695 }
696
697 /**
698 * A version used in checking (fromIndex > toIndex) condition
699 */
700 private static String outOfBoundsMsg(int fromIndex, int toIndex) {
824 } else if (size == 0) {
825 elementData = EMPTY_ELEMENTDATA;
826 } else {
827 throw new java.io.InvalidObjectException("Invalid size: " + size);
828 }
829 }
830
831 /**
832 * Returns a list iterator over the elements in this list (in proper
833 * sequence), starting at the specified position in the list.
834 * The specified index indicates the first element that would be
835 * returned by an initial call to {@link ListIterator#next next}.
836 * An initial call to {@link ListIterator#previous previous} would
837 * return the element with the specified index minus one.
838 *
839 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
840 *
841 * @throws IndexOutOfBoundsException {@inheritDoc}
842 */
843 public ListIterator<E> listIterator(int index) {
844 rangeCheckForAdd(index);
845 return new ListItr(index);
846 }
847
848 /**
849 * Returns a list iterator over the elements in this list (in proper
850 * sequence).
851 *
852 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
853 *
854 * @see #listIterator(int)
855 */
856 public ListIterator<E> listIterator() {
857 return new ListItr(0);
858 }
859
860 /**
861 * Returns an iterator over the elements in this list in proper sequence.
862 *
863 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
864 *
1011 * instead of a whole list. For example, the following idiom
1012 * removes a range of elements from a list:
1013 * <pre>
1014 * list.subList(from, to).clear();
1015 * </pre>
1016 * Similar idioms may be constructed for {@link #indexOf(Object)} and
1017 * {@link #lastIndexOf(Object)}, and all of the algorithms in the
1018 * {@link Collections} class can be applied to a subList.
1019 *
1020 * <p>The semantics of the list returned by this method become undefined if
1021 * the backing list (i.e., this list) is <i>structurally modified</i> in
1022 * any way other than via the returned list. (Structural modifications are
1023 * those that change the size of this list, or otherwise perturb it in such
1024 * a fashion that iterations in progress may yield incorrect results.)
1025 *
1026 * @throws IndexOutOfBoundsException {@inheritDoc}
1027 * @throws IllegalArgumentException {@inheritDoc}
1028 */
1029 public List<E> subList(int fromIndex, int toIndex) {
1030 subListRangeCheck(fromIndex, toIndex, size);
1031 return new SubList<>(this, fromIndex, toIndex);
1032 }
1033
1034 private static class SubList<E> extends AbstractList<E> implements RandomAccess {
1035 private final ArrayList<E> root;
1036 private final SubList<E> parent;
1037 private final int offset;
1038 private int size;
1039
1040 /**
1041 * Constructs a sublist of an arbitrary ArrayList.
1042 */
1043 public SubList(ArrayList<E> root, int fromIndex, int toIndex) {
1044 this.root = root;
1045 this.parent = null;
1046 this.offset = fromIndex;
1047 this.size = toIndex - fromIndex;
1048 this.modCount = root.modCount;
1049 }
1050
1051 /**
1052 * Constructs a sublist of another SubList.
1053 */
1054 private SubList(SubList<E> parent, int fromIndex, int toIndex) {
1055 this.root = parent.root;
1056 this.parent = parent;
1057 this.offset = parent.offset + fromIndex;
1058 this.size = toIndex - fromIndex;
1059 this.modCount = root.modCount;
1060 }
1061
1062 public E set(int index, E element) {
1063 Objects.checkIndex(index, size);
1064 checkForComodification();
1065 E oldValue = root.elementData(offset + index);
1066 root.elementData[offset + index] = element;
1067 return oldValue;
1068 }
1069
1070 public E get(int index) {
1071 Objects.checkIndex(index, size);
1072 checkForComodification();
1073 return root.elementData(offset + index);
1074 }
1075
1076 public int size() {
1077 checkForComodification();
1078 return size;
1079 }
1080
1081 public void add(int index, E element) {
1082 rangeCheckForAdd(index);
1083 checkForComodification();
1084 root.add(offset + index, element);
1085 updateSizeAndModCount(1);
1086 }
1087
1088 public E remove(int index) {
1089 Objects.checkIndex(index, size);
1090 checkForComodification();
1091 E result = root.remove(offset + index);
1092 updateSizeAndModCount(-1);
1093 return result;
1094 }
1095
1096 protected void removeRange(int fromIndex, int toIndex) {
1097 checkForComodification();
1098 root.removeRange(offset + fromIndex, offset + toIndex);
1099 updateSizeAndModCount(fromIndex - toIndex);
1100 }
1101
1102 public boolean addAll(Collection<? extends E> c) {
1103 return addAll(this.size, c);
1104 }
1105
1106 public boolean addAll(int index, Collection<? extends E> c) {
1107 rangeCheckForAdd(index);
1108 int cSize = c.size();
1109 if (cSize==0)
1110 return false;
1111 checkForComodification();
1112 root.addAll(offset + index, c);
1113 updateSizeAndModCount(cSize);
1114 return true;
1115 }
1116
1117 public Iterator<E> iterator() {
1118 return listIterator();
1119 }
1120
1121 public ListIterator<E> listIterator(int index) {
1122 checkForComodification();
1123 rangeCheckForAdd(index);
1124
1125 return new ListIterator<E>() {
1126 int cursor = index;
1127 int lastRet = -1;
1128 int expectedModCount = root.modCount;
1129
1130 public boolean hasNext() {
1131 return cursor != SubList.this.size;
1132 }
1133
1134 @SuppressWarnings("unchecked")
1135 public E next() {
1136 checkForComodification();
1137 int i = cursor;
1138 if (i >= SubList.this.size)
1139 throw new NoSuchElementException();
1140 Object[] elementData = root.elementData;
1141 if (offset + i >= elementData.length)
1142 throw new ConcurrentModificationException();
1143 cursor = i + 1;
1144 return (E) elementData[offset + (lastRet = i)];
1145 }
1146
1147 public boolean hasPrevious() {
1148 return cursor != 0;
1149 }
1150
1151 @SuppressWarnings("unchecked")
1152 public E previous() {
1153 checkForComodification();
1154 int i = cursor - 1;
1155 if (i < 0)
1156 throw new NoSuchElementException();
1157 Object[] elementData = root.elementData;
1158 if (offset + i >= elementData.length)
1159 throw new ConcurrentModificationException();
1160 cursor = i;
1161 return (E) elementData[offset + (lastRet = i)];
1162 }
1163
1164 @SuppressWarnings("unchecked")
1165 public void forEachRemaining(Consumer<? super E> consumer) {
1166 Objects.requireNonNull(consumer);
1167 final int size = SubList.this.size;
1168 int i = cursor;
1169 if (i >= size) {
1170 return;
1171 }
1172 final Object[] elementData = root.elementData;
1173 if (offset + i >= elementData.length) {
1174 throw new ConcurrentModificationException();
1175 }
1176 while (i != size && modCount == expectedModCount) {
1177 consumer.accept((E) elementData[offset + (i++)]);
1178 }
1179 // update once at end of iteration to reduce heap write traffic
1180 lastRet = cursor = i;
1181 checkForComodification();
1182 }
1183
1184 public int nextIndex() {
1185 return cursor;
1186 }
1187
1188 public int previousIndex() {
1189 return cursor - 1;
1190 }
1191
1192 public void remove() {
1193 if (lastRet < 0)
1194 throw new IllegalStateException();
1195 checkForComodification();
1196
1197 try {
1198 SubList.this.remove(lastRet);
1199 cursor = lastRet;
1200 lastRet = -1;
1201 expectedModCount = root.modCount;
1202 } catch (IndexOutOfBoundsException ex) {
1203 throw new ConcurrentModificationException();
1204 }
1205 }
1206
1207 public void set(E e) {
1208 if (lastRet < 0)
1209 throw new IllegalStateException();
1210 checkForComodification();
1211
1212 try {
1213 root.set(offset + lastRet, e);
1214 } catch (IndexOutOfBoundsException ex) {
1215 throw new ConcurrentModificationException();
1216 }
1217 }
1218
1219 public void add(E e) {
1220 checkForComodification();
1221
1222 try {
1223 int i = cursor;
1224 SubList.this.add(i, e);
1225 cursor = i + 1;
1226 lastRet = -1;
1227 expectedModCount = root.modCount;
1228 } catch (IndexOutOfBoundsException ex) {
1229 throw new ConcurrentModificationException();
1230 }
1231 }
1232
1233 final void checkForComodification() {
1234 if (root.modCount != expectedModCount)
1235 throw new ConcurrentModificationException();
1236 }
1237 };
1238 }
1239
1240 public List<E> subList(int fromIndex, int toIndex) {
1241 subListRangeCheck(fromIndex, toIndex, size);
1242 return new SubList<>(this, fromIndex, toIndex);
1243 }
1244
1245 private void rangeCheckForAdd(int index) {
1246 if (index < 0 || index > this.size)
1247 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1248 }
1249
1250 private String outOfBoundsMsg(int index) {
1251 return "Index: "+index+", Size: "+this.size;
1252 }
1253
1254 private void checkForComodification() {
1255 if (root.modCount != modCount)
1256 throw new ConcurrentModificationException();
1257 }
1258
1259 private void updateSizeAndModCount(int sizeChange) {
1260 SubList<E> slist = this;
1261 do {
1262 slist.size += sizeChange;
1263 slist.modCount = root.modCount;
1264 slist = slist.parent;
1265 } while (slist != null);
1266 }
1267
1268 public Spliterator<E> spliterator() {
1269 checkForComodification();
1270 return new ArrayListSpliterator<>(root, offset,
1271 offset + size, modCount);
1272 }
1273 }
1274
1275 @Override
1276 public void forEach(Consumer<? super E> action) {
1277 Objects.requireNonNull(action);
1278 final int expectedModCount = modCount;
1279 @SuppressWarnings("unchecked")
1280 final E[] elementData = (E[]) this.elementData;
1281 final int size = this.size;
1282 for (int i=0; modCount == expectedModCount && i < size; i++) {
1283 action.accept(elementData[i]);
1284 }
1285 if (modCount != expectedModCount) {
1286 throw new ConcurrentModificationException();
1287 }
1288 }
1289
1290 /**
1291 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
|