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

Print this page
rev 6197 : [mq]: collections


   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 




  28 /**
  29  * Resizable-array implementation of the <tt>List</tt> interface.  Implements
  30  * all optional list operations, and permits all elements, including
  31  * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
  32  * this class provides methods to manipulate the size of the array that is
  33  * used internally to store the list.  (This class is roughly equivalent to
  34  * <tt>Vector</tt>, except that it is unsynchronized.)
  35  *
  36  * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
  37  * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
  38  * time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
  39  * that is, adding n elements requires O(n) time.  All of the other operations
  40  * run in linear time (roughly speaking).  The constant factor is low compared
  41  * to that for the <tt>LinkedList</tt> implementation.
  42  *
  43  * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
  44  * the size of the array used to store the elements in the list.  It is always
  45  * at least as large as the list size.  As elements are added to an ArrayList,
  46  * its capacity grows automatically.  The details of the growth policy are not
  47  * specified beyond the fact that adding an element has constant amortized


1110         }
1111 
1112         private void rangeCheck(int index) {
1113             if (index < 0 || index >= this.size)
1114                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1115         }
1116 
1117         private void rangeCheckForAdd(int index) {
1118             if (index < 0 || index > this.size)
1119                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1120         }
1121 
1122         private String outOfBoundsMsg(int index) {
1123             return "Index: "+index+", Size: "+this.size;
1124         }
1125 
1126         private void checkForComodification() {
1127             if (ArrayList.this.modCount != this.modCount)
1128                 throw new ConcurrentModificationException();
1129         }






















































































1130     }
1131 }


   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 
  28 import java.util.function.Block;
  29 import java.util.function.Predicate;
  30 import java.util.function.UnaryOperator;
  31 
  32 /**
  33  * Resizable-array implementation of the <tt>List</tt> interface.  Implements
  34  * all optional list operations, and permits all elements, including
  35  * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
  36  * this class provides methods to manipulate the size of the array that is
  37  * used internally to store the list.  (This class is roughly equivalent to
  38  * <tt>Vector</tt>, except that it is unsynchronized.)
  39  *
  40  * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
  41  * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
  42  * time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
  43  * that is, adding n elements requires O(n) time.  All of the other operations
  44  * run in linear time (roughly speaking).  The constant factor is low compared
  45  * to that for the <tt>LinkedList</tt> implementation.
  46  *
  47  * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
  48  * the size of the array used to store the elements in the list.  It is always
  49  * at least as large as the list size.  As elements are added to an ArrayList,
  50  * its capacity grows automatically.  The details of the growth policy are not
  51  * specified beyond the fact that adding an element has constant amortized


1114         }
1115 
1116         private void rangeCheck(int index) {
1117             if (index < 0 || index >= this.size)
1118                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1119         }
1120 
1121         private void rangeCheckForAdd(int index) {
1122             if (index < 0 || index > this.size)
1123                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1124         }
1125 
1126         private String outOfBoundsMsg(int index) {
1127             return "Index: "+index+", Size: "+this.size;
1128         }
1129 
1130         private void checkForComodification() {
1131             if (ArrayList.this.modCount != this.modCount)
1132                 throw new ConcurrentModificationException();
1133         }
1134     }
1135 
1136     @Override
1137     public void forEach(Block<? super E> block) {
1138         Objects.requireNonNull(block);
1139         final int expectedModCount = modCount;
1140         final E[] elementData = (E[]) this.elementData;
1141         final int size = this.size;
1142         for (int i=0; modCount == expectedModCount && i < size; i++) {
1143             block.accept(elementData[i]);
1144         }
1145         if (modCount != expectedModCount) {
1146             throw new ConcurrentModificationException();
1147         }
1148     }
1149 
1150     @Override
1151     public boolean removeAll(Predicate<? super E> filter) {
1152         Objects.requireNonNull(filter);
1153         // figure out which elements are to be removed
1154         // any exception thrown from the filter predicate at this stage
1155         // will leave the collection unmodified
1156         int removeCount = 0;
1157         final BitSet removeSet = new BitSet(size);
1158         final int expectedModCount = modCount;
1159         final int size = this.size;
1160         for (int i=0; modCount == expectedModCount && i < size; i++) {
1161             @SuppressWarnings("unchecked")
1162             final E element = (E) elementData[i];
1163             if (filter.test(element)) {
1164                 removeSet.set(i);
1165                 removeCount++;
1166             }
1167         }
1168 
1169         if (modCount != expectedModCount) {
1170             throw new ConcurrentModificationException();
1171         }
1172 
1173         // shift surviving elements left over the spaces left by removed elements
1174         final boolean anyToRemove = removeCount > 0;
1175         if (anyToRemove) {
1176             final int newSize = size - removeCount;
1177             for (int i=0, j=0; modCount == expectedModCount &&
1178                     (i < size) && (j < newSize); i++, j++) {
1179                 i = removeSet.nextClearBit(i);
1180                 elementData[j] = elementData[i];
1181             }
1182             for (int k=newSize; modCount == expectedModCount && k < size; k++) {
1183                 elementData[k] = null;  // Let gc do its work
1184             }
1185             this.size = newSize;
1186             if (modCount != expectedModCount) {
1187                 throw new ConcurrentModificationException();
1188             }
1189             modCount++;
1190         }
1191 
1192         return anyToRemove;
1193     }
1194 
1195     @Override
1196     @SuppressWarnings("unchecked")
1197     public void replaceAll(UnaryOperator<E> operator) {
1198         Objects.requireNonNull(operator);
1199         final int expectedModCount = modCount;
1200         final int size = this.size;
1201         for (int i=0; modCount == expectedModCount && i < size; i++) {
1202             elementData[i] = operator.operate((E) elementData[i]);
1203         }
1204         if (modCount != expectedModCount) {
1205             throw new ConcurrentModificationException();
1206         }
1207         modCount++;
1208     }
1209 
1210     @Override
1211     @SuppressWarnings("unchecked")
1212     public void sort(Comparator<? super E> c) {
1213         Objects.requireNonNull(c);
1214         final int expectedModCount = modCount;
1215         Arrays.sort((E[]) elementData, 0, size, c);
1216         if (modCount != expectedModCount) {
1217             throw new ConcurrentModificationException();
1218         }
1219         modCount++;
1220     }
1221 }