< prev index next >

src/java.base/share/classes/java/util/ArrayList.java

Print this page
rev 13550 : [mq]: 8079136-Nested-SubLists
   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>


< prev index next >