jdk/src/java.base/share/classes/java/util/ArrayList.java
author mchung
Fri, 22 May 2015 16:43:39 -0700
changeset 30789 9eca83469588
parent 25859 3317bb8137f4
child 31540 6efd719b3330
permissions -rw-r--r--
8074431: Remove native2ascii tool Reviewed-by: erikj, alanb, okutsu, mfang, naoto
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     1
/*
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
     2
 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     3
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
90ce3da70b43 Initial load
duke
parents:
diff changeset
     4
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
     5
 * This code is free software; you can redistribute it and/or modify it
90ce3da70b43 Initial load
duke
parents:
diff changeset
     6
 * under the terms of the GNU General Public License version 2 only, as
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 5466
diff changeset
     7
 * published by the Free Software Foundation.  Oracle designates this
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     8
 * particular file as subject to the "Classpath" exception as provided
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 5466
diff changeset
     9
 * by Oracle in the LICENSE file that accompanied this code.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    10
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    11
 * This code is distributed in the hope that it will be useful, but WITHOUT
90ce3da70b43 Initial load
duke
parents:
diff changeset
    12
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
90ce3da70b43 Initial load
duke
parents:
diff changeset
    13
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
90ce3da70b43 Initial load
duke
parents:
diff changeset
    14
 * version 2 for more details (a copy is included in the LICENSE file that
90ce3da70b43 Initial load
duke
parents:
diff changeset
    15
 * accompanied this code).
90ce3da70b43 Initial load
duke
parents:
diff changeset
    16
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    17
 * You should have received a copy of the GNU General Public License version
90ce3da70b43 Initial load
duke
parents:
diff changeset
    18
 * 2 along with this work; if not, write to the Free Software Foundation,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    19
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    20
 *
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 5466
diff changeset
    21
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 5466
diff changeset
    22
 * or visit www.oracle.com if you need additional information or have any
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 5466
diff changeset
    23
 * questions.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    24
 */
90ce3da70b43 Initial load
duke
parents:
diff changeset
    25
90ce3da70b43 Initial load
duke
parents:
diff changeset
    26
package java.util;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    27
17166
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
    28
import java.util.function.Consumer;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
    29
import java.util.function.Predicate;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
    30
import java.util.function.UnaryOperator;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
    31
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    32
/**
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
    33
 * Resizable-array implementation of the {@code List} interface.  Implements
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    34
 * all optional list operations, and permits all elements, including
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
    35
 * {@code null}.  In addition to implementing the {@code List} interface,
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    36
 * this class provides methods to manipulate the size of the array that is
90ce3da70b43 Initial load
duke
parents:
diff changeset
    37
 * used internally to store the list.  (This class is roughly equivalent to
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
    38
 * {@code Vector}, except that it is unsynchronized.)
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    39
 *
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
    40
 * <p>The {@code size}, {@code isEmpty}, {@code get}, {@code set},
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
    41
 * {@code iterator}, and {@code listIterator} operations run in constant
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
    42
 * time.  The {@code add} operation runs in <i>amortized constant time</i>,
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    43
 * that is, adding n elements requires O(n) time.  All of the other operations
90ce3da70b43 Initial load
duke
parents:
diff changeset
    44
 * run in linear time (roughly speaking).  The constant factor is low compared
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
    45
 * to that for the {@code LinkedList} implementation.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    46
 *
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
    47
 * <p>Each {@code ArrayList} instance has a <i>capacity</i>.  The capacity is
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    48
 * the size of the array used to store the elements in the list.  It is always
90ce3da70b43 Initial load
duke
parents:
diff changeset
    49
 * at least as large as the list size.  As elements are added to an ArrayList,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    50
 * its capacity grows automatically.  The details of the growth policy are not
90ce3da70b43 Initial load
duke
parents:
diff changeset
    51
 * specified beyond the fact that adding an element has constant amortized
90ce3da70b43 Initial load
duke
parents:
diff changeset
    52
 * time cost.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    53
 *
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
    54
 * <p>An application can increase the capacity of an {@code ArrayList} instance
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
    55
 * before adding a large number of elements using the {@code ensureCapacity}
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    56
 * operation.  This may reduce the amount of incremental reallocation.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    57
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    58
 * <p><strong>Note that this implementation is not synchronized.</strong>
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
    59
 * If multiple threads access an {@code ArrayList} instance concurrently,
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    60
 * and at least one of the threads modifies the list structurally, it
90ce3da70b43 Initial load
duke
parents:
diff changeset
    61
 * <i>must</i> be synchronized externally.  (A structural modification is
90ce3da70b43 Initial load
duke
parents:
diff changeset
    62
 * any operation that adds or deletes one or more elements, or explicitly
90ce3da70b43 Initial load
duke
parents:
diff changeset
    63
 * resizes the backing array; merely setting the value of an element is not
90ce3da70b43 Initial load
duke
parents:
diff changeset
    64
 * a structural modification.)  This is typically accomplished by
90ce3da70b43 Initial load
duke
parents:
diff changeset
    65
 * synchronizing on some object that naturally encapsulates the list.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    66
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    67
 * If no such object exists, the list should be "wrapped" using the
90ce3da70b43 Initial load
duke
parents:
diff changeset
    68
 * {@link Collections#synchronizedList Collections.synchronizedList}
90ce3da70b43 Initial load
duke
parents:
diff changeset
    69
 * method.  This is best done at creation time, to prevent accidental
90ce3da70b43 Initial load
duke
parents:
diff changeset
    70
 * unsynchronized access to the list:<pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    71
 *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    72
 *
24196
61c9885d76e2 8029451: Tidy warnings cleanup for java.util package; minor changes in java.nio, java.sql
yan
parents: 24122
diff changeset
    73
 * <p id="fail-fast">
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    74
 * The iterators returned by this class's {@link #iterator() iterator} and
24196
61c9885d76e2 8029451: Tidy warnings cleanup for java.util package; minor changes in java.nio, java.sql
yan
parents: 24122
diff changeset
    75
 * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    76
 * if the list is structurally modified at any time after the iterator is
90ce3da70b43 Initial load
duke
parents:
diff changeset
    77
 * created, in any way except through the iterator's own
90ce3da70b43 Initial load
duke
parents:
diff changeset
    78
 * {@link ListIterator#remove() remove} or
90ce3da70b43 Initial load
duke
parents:
diff changeset
    79
 * {@link ListIterator#add(Object) add} methods, the iterator will throw a
90ce3da70b43 Initial load
duke
parents:
diff changeset
    80
 * {@link ConcurrentModificationException}.  Thus, in the face of
90ce3da70b43 Initial load
duke
parents:
diff changeset
    81
 * concurrent modification, the iterator fails quickly and cleanly, rather
90ce3da70b43 Initial load
duke
parents:
diff changeset
    82
 * than risking arbitrary, non-deterministic behavior at an undetermined
90ce3da70b43 Initial load
duke
parents:
diff changeset
    83
 * time in the future.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    84
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    85
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
90ce3da70b43 Initial load
duke
parents:
diff changeset
    86
 * as it is, generally speaking, impossible to make any hard guarantees in the
90ce3da70b43 Initial load
duke
parents:
diff changeset
    87
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
90ce3da70b43 Initial load
duke
parents:
diff changeset
    88
 * throw {@code ConcurrentModificationException} on a best-effort basis.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    89
 * Therefore, it would be wrong to write a program that depended on this
90ce3da70b43 Initial load
duke
parents:
diff changeset
    90
 * exception for its correctness:  <i>the fail-fast behavior of iterators
90ce3da70b43 Initial load
duke
parents:
diff changeset
    91
 * should be used only to detect bugs.</i>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    92
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    93
 * <p>This class is a member of the
90ce3da70b43 Initial load
duke
parents:
diff changeset
    94
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
90ce3da70b43 Initial load
duke
parents:
diff changeset
    95
 * Java Collections Framework</a>.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    96
 *
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
    97
 * @param <E> the type of elements in this list
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
    98
 *
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    99
 * @author  Josh Bloch
90ce3da70b43 Initial load
duke
parents:
diff changeset
   100
 * @author  Neal Gafter
90ce3da70b43 Initial load
duke
parents:
diff changeset
   101
 * @see     Collection
90ce3da70b43 Initial load
duke
parents:
diff changeset
   102
 * @see     List
90ce3da70b43 Initial load
duke
parents:
diff changeset
   103
 * @see     LinkedList
90ce3da70b43 Initial load
duke
parents:
diff changeset
   104
 * @see     Vector
90ce3da70b43 Initial load
duke
parents:
diff changeset
   105
 * @since   1.2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   106
 */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   107
90ce3da70b43 Initial load
duke
parents:
diff changeset
   108
public class ArrayList<E> extends AbstractList<E>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   109
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
90ce3da70b43 Initial load
duke
parents:
diff changeset
   110
{
90ce3da70b43 Initial load
duke
parents:
diff changeset
   111
    private static final long serialVersionUID = 8683452581122892189L;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   112
90ce3da70b43 Initial load
duke
parents:
diff changeset
   113
    /**
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   114
     * Default initial capacity.
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   115
     */
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   116
    private static final int DEFAULT_CAPACITY = 10;
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   117
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   118
    /**
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   119
     * Shared empty array instance used for empty instances.
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   120
     */
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   121
    private static final Object[] EMPTY_ELEMENTDATA = {};
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   122
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   123
    /**
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   124
     * Shared empty array instance used for default sized empty instances. We
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   125
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   126
     * first element is added.
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   127
     */
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   128
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   129
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   130
    /**
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   131
     * The array buffer into which the elements of the ArrayList are stored.
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   132
     * The capacity of the ArrayList is the length of this array buffer. Any
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   133
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   134
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   135
     */
17168
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   136
    transient Object[] elementData; // non-private to simplify nested class access
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   137
90ce3da70b43 Initial load
duke
parents:
diff changeset
   138
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   139
     * The size of the ArrayList (the number of elements it contains).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   140
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   141
     * @serial
90ce3da70b43 Initial load
duke
parents:
diff changeset
   142
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   143
    private int size;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   144
90ce3da70b43 Initial load
duke
parents:
diff changeset
   145
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   146
     * Constructs an empty list with the specified initial capacity.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   147
     *
7518
0282db800fe1 7003745: Code style cleanups (sync from Dougs CVS)
dl
parents: 7020
diff changeset
   148
     * @param  initialCapacity  the initial capacity of the list
0282db800fe1 7003745: Code style cleanups (sync from Dougs CVS)
dl
parents: 7020
diff changeset
   149
     * @throws IllegalArgumentException if the specified initial capacity
0282db800fe1 7003745: Code style cleanups (sync from Dougs CVS)
dl
parents: 7020
diff changeset
   150
     *         is negative
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   151
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   152
    public ArrayList(int initialCapacity) {
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   153
        if (initialCapacity > 0) {
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   154
            this.elementData = new Object[initialCapacity];
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   155
        } else if (initialCapacity == 0) {
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   156
            this.elementData = EMPTY_ELEMENTDATA;
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   157
        } else {
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   158
            throw new IllegalArgumentException("Illegal Capacity: "+
90ce3da70b43 Initial load
duke
parents:
diff changeset
   159
                                               initialCapacity);
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   160
        }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   161
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   162
90ce3da70b43 Initial load
duke
parents:
diff changeset
   163
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   164
     * Constructs an empty list with an initial capacity of ten.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   165
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   166
    public ArrayList() {
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   167
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   168
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   169
90ce3da70b43 Initial load
duke
parents:
diff changeset
   170
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   171
     * Constructs a list containing the elements of the specified
90ce3da70b43 Initial load
duke
parents:
diff changeset
   172
     * collection, in the order they are returned by the collection's
90ce3da70b43 Initial load
duke
parents:
diff changeset
   173
     * iterator.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   174
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   175
     * @param c the collection whose elements are to be placed into this list
90ce3da70b43 Initial load
duke
parents:
diff changeset
   176
     * @throws NullPointerException if the specified collection is null
90ce3da70b43 Initial load
duke
parents:
diff changeset
   177
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   178
    public ArrayList(Collection<? extends E> c) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   179
        elementData = c.toArray();
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   180
        if ((size = elementData.length) != 0) {
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   181
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   182
            if (elementData.getClass() != Object[].class)
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   183
                elementData = Arrays.copyOf(elementData, size, Object[].class);
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   184
        } else {
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   185
            // replace with empty array.
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   186
            this.elementData = EMPTY_ELEMENTDATA;
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   187
        }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   188
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   189
90ce3da70b43 Initial load
duke
parents:
diff changeset
   190
    /**
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   191
     * Trims the capacity of this {@code ArrayList} instance to be the
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   192
     * list's current size.  An application can use this operation to minimize
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   193
     * the storage of an {@code ArrayList} instance.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   194
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   195
    public void trimToSize() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   196
        modCount++;
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   197
        if (size < elementData.length) {
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   198
            elementData = (size == 0)
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   199
              ? EMPTY_ELEMENTDATA
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   200
              : Arrays.copyOf(elementData, size);
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   201
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   202
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   203
90ce3da70b43 Initial load
duke
parents:
diff changeset
   204
    /**
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   205
     * Increases the capacity of this {@code ArrayList} instance, if
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   206
     * necessary, to ensure that it can hold at least the number of elements
90ce3da70b43 Initial load
duke
parents:
diff changeset
   207
     * specified by the minimum capacity argument.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   208
     *
7518
0282db800fe1 7003745: Code style cleanups (sync from Dougs CVS)
dl
parents: 7020
diff changeset
   209
     * @param   minCapacity   the desired minimum capacity
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   210
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   211
    public void ensureCapacity(int minCapacity) {
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   212
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   213
            // any size if not default element table
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   214
            ? 0
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   215
            // larger than default for default empty table. It's already
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   216
            // supposed to be at default size.
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   217
            : DEFAULT_CAPACITY;
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   218
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   219
        if (minCapacity > minExpand) {
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   220
            ensureExplicitCapacity(minCapacity);
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   221
        }
7020
25638687fe82 6992121: StringBuilder.ensureCapacity(int minCap) throws OutOfMemoryError with minCap=Integer.MIN_VALUE
mchung
parents: 5506
diff changeset
   222
    }
25638687fe82 6992121: StringBuilder.ensureCapacity(int minCap) throws OutOfMemoryError with minCap=Integer.MIN_VALUE
mchung
parents: 5506
diff changeset
   223
25638687fe82 6992121: StringBuilder.ensureCapacity(int minCap) throws OutOfMemoryError with minCap=Integer.MIN_VALUE
mchung
parents: 5506
diff changeset
   224
    private void ensureCapacityInternal(int minCapacity) {
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   225
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   226
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   227
        }
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   228
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   229
        ensureExplicitCapacity(minCapacity);
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   230
    }
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   231
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   232
    private void ensureExplicitCapacity(int minCapacity) {
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   233
        modCount++;
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   234
5466
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   235
        // overflow-conscious code
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   236
        if (minCapacity - elementData.length > 0)
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   237
            grow(minCapacity);
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   238
    }
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   239
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   240
    /**
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   241
     * The maximum size of array to allocate.
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   242
     * Some VMs reserve some header words in an array.
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   243
     * Attempts to allocate larger arrays may result in
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   244
     * OutOfMemoryError: Requested array size exceeds VM limit
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   245
     */
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   246
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   247
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   248
    /**
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   249
     * Increases the capacity to ensure that it can hold at least the
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   250
     * number of elements specified by the minimum capacity argument.
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   251
     *
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   252
     * @param minCapacity the desired minimum capacity
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   253
     */
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   254
    private void grow(int minCapacity) {
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   255
        // overflow-conscious code
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   256
        int oldCapacity = elementData.length;
5466
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   257
        int newCapacity = oldCapacity + (oldCapacity >> 1);
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   258
        if (newCapacity - minCapacity < 0)
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   259
            newCapacity = minCapacity;
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   260
        if (newCapacity - MAX_ARRAY_SIZE > 0)
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   261
            newCapacity = hugeCapacity(minCapacity);
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   262
        // minCapacity is usually close to size, so this is a win:
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   263
        elementData = Arrays.copyOf(elementData, newCapacity);
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   264
    }
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   265
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   266
    private static int hugeCapacity(int minCapacity) {
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   267
        if (minCapacity < 0) // overflow
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   268
            throw new OutOfMemoryError();
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   269
        return (minCapacity > MAX_ARRAY_SIZE) ?
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   270
            Integer.MAX_VALUE :
f130bb07764b 6933217: Huge arrays handled poorly in core libraries
martin
parents: 2178
diff changeset
   271
            MAX_ARRAY_SIZE;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   272
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   273
90ce3da70b43 Initial load
duke
parents:
diff changeset
   274
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   275
     * Returns the number of elements in this list.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   276
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   277
     * @return the number of elements in this list
90ce3da70b43 Initial load
duke
parents:
diff changeset
   278
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   279
    public int size() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   280
        return size;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   281
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   282
90ce3da70b43 Initial load
duke
parents:
diff changeset
   283
    /**
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   284
     * Returns {@code true} if this list contains no elements.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   285
     *
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   286
     * @return {@code true} if this list contains no elements
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   287
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   288
    public boolean isEmpty() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   289
        return size == 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   290
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   291
90ce3da70b43 Initial load
duke
parents:
diff changeset
   292
    /**
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   293
     * Returns {@code true} if this list contains the specified element.
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   294
     * More formally, returns {@code true} if and only if this list contains
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   295
     * at least one element {@code e} such that
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   296
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   297
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   298
     * @param o element whose presence in this list is to be tested
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   299
     * @return {@code true} if this list contains the specified element
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   300
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   301
    public boolean contains(Object o) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   302
        return indexOf(o) >= 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   303
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   304
90ce3da70b43 Initial load
duke
parents:
diff changeset
   305
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   306
     * Returns the index of the first occurrence of the specified element
90ce3da70b43 Initial load
duke
parents:
diff changeset
   307
     * in this list, or -1 if this list does not contain the element.
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   308
     * More formally, returns the lowest index {@code i} such that
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   309
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   310
     * or -1 if there is no such index.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   311
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   312
    public int indexOf(Object o) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   313
        if (o == null) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   314
            for (int i = 0; i < size; i++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   315
                if (elementData[i]==null)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   316
                    return i;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   317
        } else {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   318
            for (int i = 0; i < size; i++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   319
                if (o.equals(elementData[i]))
90ce3da70b43 Initial load
duke
parents:
diff changeset
   320
                    return i;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   321
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   322
        return -1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   323
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   324
90ce3da70b43 Initial load
duke
parents:
diff changeset
   325
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   326
     * Returns the index of the last occurrence of the specified element
90ce3da70b43 Initial load
duke
parents:
diff changeset
   327
     * in this list, or -1 if this list does not contain the element.
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   328
     * More formally, returns the highest index {@code i} such that
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   329
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   330
     * or -1 if there is no such index.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   331
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   332
    public int lastIndexOf(Object o) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   333
        if (o == null) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   334
            for (int i = size-1; i >= 0; i--)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   335
                if (elementData[i]==null)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   336
                    return i;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   337
        } else {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   338
            for (int i = size-1; i >= 0; i--)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   339
                if (o.equals(elementData[i]))
90ce3da70b43 Initial load
duke
parents:
diff changeset
   340
                    return i;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   341
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   342
        return -1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   343
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   344
90ce3da70b43 Initial load
duke
parents:
diff changeset
   345
    /**
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   346
     * Returns a shallow copy of this {@code ArrayList} instance.  (The
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   347
     * elements themselves are not copied.)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   348
     *
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   349
     * @return a clone of this {@code ArrayList} instance
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   350
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   351
    public Object clone() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   352
        try {
12448
b95438b17098 7157893: Warnings Cleanup in java.util.*
khazra
parents: 10419
diff changeset
   353
            ArrayList<?> v = (ArrayList<?>) super.clone();
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   354
            v.elementData = Arrays.copyOf(elementData, size);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   355
            v.modCount = 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   356
            return v;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   357
        } catch (CloneNotSupportedException e) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   358
            // this shouldn't happen, since we are Cloneable
10419
12c063b39232 7084245: Update usages of InternalError to use exception chaining
sherman
parents: 9503
diff changeset
   359
            throw new InternalError(e);
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   360
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   361
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   362
90ce3da70b43 Initial load
duke
parents:
diff changeset
   363
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   364
     * Returns an array containing all of the elements in this list
90ce3da70b43 Initial load
duke
parents:
diff changeset
   365
     * in proper sequence (from first to last element).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   366
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   367
     * <p>The returned array will be "safe" in that no references to it are
90ce3da70b43 Initial load
duke
parents:
diff changeset
   368
     * maintained by this list.  (In other words, this method must allocate
90ce3da70b43 Initial load
duke
parents:
diff changeset
   369
     * a new array).  The caller is thus free to modify the returned array.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   370
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   371
     * <p>This method acts as bridge between array-based and collection-based
90ce3da70b43 Initial load
duke
parents:
diff changeset
   372
     * APIs.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   373
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   374
     * @return an array containing all of the elements in this list in
90ce3da70b43 Initial load
duke
parents:
diff changeset
   375
     *         proper sequence
90ce3da70b43 Initial load
duke
parents:
diff changeset
   376
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   377
    public Object[] toArray() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   378
        return Arrays.copyOf(elementData, size);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   379
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   380
90ce3da70b43 Initial load
duke
parents:
diff changeset
   381
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   382
     * Returns an array containing all of the elements in this list in proper
90ce3da70b43 Initial load
duke
parents:
diff changeset
   383
     * sequence (from first to last element); the runtime type of the returned
90ce3da70b43 Initial load
duke
parents:
diff changeset
   384
     * array is that of the specified array.  If the list fits in the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   385
     * specified array, it is returned therein.  Otherwise, a new array is
90ce3da70b43 Initial load
duke
parents:
diff changeset
   386
     * allocated with the runtime type of the specified array and the size of
90ce3da70b43 Initial load
duke
parents:
diff changeset
   387
     * this list.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   388
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   389
     * <p>If the list fits in the specified array with room to spare
90ce3da70b43 Initial load
duke
parents:
diff changeset
   390
     * (i.e., the array has more elements than the list), the element in
90ce3da70b43 Initial load
duke
parents:
diff changeset
   391
     * the array immediately following the end of the collection is set to
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   392
     * {@code null}.  (This is useful in determining the length of the
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   393
     * list <i>only</i> if the caller knows that the list does not contain
90ce3da70b43 Initial load
duke
parents:
diff changeset
   394
     * any null elements.)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   395
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   396
     * @param a the array into which the elements of the list are to
90ce3da70b43 Initial load
duke
parents:
diff changeset
   397
     *          be stored, if it is big enough; otherwise, a new array of the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   398
     *          same runtime type is allocated for this purpose.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   399
     * @return an array containing the elements of the list
90ce3da70b43 Initial load
duke
parents:
diff changeset
   400
     * @throws ArrayStoreException if the runtime type of the specified array
90ce3da70b43 Initial load
duke
parents:
diff changeset
   401
     *         is not a supertype of the runtime type of every element in
90ce3da70b43 Initial load
duke
parents:
diff changeset
   402
     *         this list
90ce3da70b43 Initial load
duke
parents:
diff changeset
   403
     * @throws NullPointerException if the specified array is null
90ce3da70b43 Initial load
duke
parents:
diff changeset
   404
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   405
    @SuppressWarnings("unchecked")
90ce3da70b43 Initial load
duke
parents:
diff changeset
   406
    public <T> T[] toArray(T[] a) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   407
        if (a.length < size)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   408
            // Make a new array of a's runtime type, but my contents:
90ce3da70b43 Initial load
duke
parents:
diff changeset
   409
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
90ce3da70b43 Initial load
duke
parents:
diff changeset
   410
        System.arraycopy(elementData, 0, a, 0, size);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   411
        if (a.length > size)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   412
            a[size] = null;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   413
        return a;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   414
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   415
90ce3da70b43 Initial load
duke
parents:
diff changeset
   416
    // Positional Access Operations
90ce3da70b43 Initial load
duke
parents:
diff changeset
   417
90ce3da70b43 Initial load
duke
parents:
diff changeset
   418
    @SuppressWarnings("unchecked")
90ce3da70b43 Initial load
duke
parents:
diff changeset
   419
    E elementData(int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   420
        return (E) elementData[index];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   421
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   422
90ce3da70b43 Initial load
duke
parents:
diff changeset
   423
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   424
     * Returns the element at the specified position in this list.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   425
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   426
     * @param  index index of the element to return
90ce3da70b43 Initial load
duke
parents:
diff changeset
   427
     * @return the element at the specified position in this list
90ce3da70b43 Initial load
duke
parents:
diff changeset
   428
     * @throws IndexOutOfBoundsException {@inheritDoc}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   429
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   430
    public E get(int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   431
        rangeCheck(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   432
90ce3da70b43 Initial load
duke
parents:
diff changeset
   433
        return elementData(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   434
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   435
90ce3da70b43 Initial load
duke
parents:
diff changeset
   436
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   437
     * Replaces the element at the specified position in this list with
90ce3da70b43 Initial load
duke
parents:
diff changeset
   438
     * the specified element.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   439
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   440
     * @param index index of the element to replace
90ce3da70b43 Initial load
duke
parents:
diff changeset
   441
     * @param element element to be stored at the specified position
90ce3da70b43 Initial load
duke
parents:
diff changeset
   442
     * @return the element previously at the specified position
90ce3da70b43 Initial load
duke
parents:
diff changeset
   443
     * @throws IndexOutOfBoundsException {@inheritDoc}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   444
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   445
    public E set(int index, E element) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   446
        rangeCheck(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   447
90ce3da70b43 Initial load
duke
parents:
diff changeset
   448
        E oldValue = elementData(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   449
        elementData[index] = element;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   450
        return oldValue;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   451
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   452
90ce3da70b43 Initial load
duke
parents:
diff changeset
   453
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   454
     * Appends the specified element to the end of this list.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   455
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   456
     * @param e element to be appended to this list
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   457
     * @return {@code true} (as specified by {@link Collection#add})
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   458
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   459
    public boolean add(E e) {
7020
25638687fe82 6992121: StringBuilder.ensureCapacity(int minCap) throws OutOfMemoryError with minCap=Integer.MIN_VALUE
mchung
parents: 5506
diff changeset
   460
        ensureCapacityInternal(size + 1);  // Increments modCount!!
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   461
        elementData[size++] = e;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   462
        return true;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   463
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   464
90ce3da70b43 Initial load
duke
parents:
diff changeset
   465
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   466
     * Inserts the specified element at the specified position in this
90ce3da70b43 Initial load
duke
parents:
diff changeset
   467
     * list. Shifts the element currently at that position (if any) and
90ce3da70b43 Initial load
duke
parents:
diff changeset
   468
     * any subsequent elements to the right (adds one to their indices).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   469
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   470
     * @param index index at which the specified element is to be inserted
90ce3da70b43 Initial load
duke
parents:
diff changeset
   471
     * @param element element to be inserted
90ce3da70b43 Initial load
duke
parents:
diff changeset
   472
     * @throws IndexOutOfBoundsException {@inheritDoc}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   473
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   474
    public void add(int index, E element) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   475
        rangeCheckForAdd(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   476
7020
25638687fe82 6992121: StringBuilder.ensureCapacity(int minCap) throws OutOfMemoryError with minCap=Integer.MIN_VALUE
mchung
parents: 5506
diff changeset
   477
        ensureCapacityInternal(size + 1);  // Increments modCount!!
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   478
        System.arraycopy(elementData, index, elementData, index + 1,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   479
                         size - index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   480
        elementData[index] = element;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   481
        size++;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   482
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   483
90ce3da70b43 Initial load
duke
parents:
diff changeset
   484
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   485
     * Removes the element at the specified position in this list.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   486
     * Shifts any subsequent elements to the left (subtracts one from their
90ce3da70b43 Initial load
duke
parents:
diff changeset
   487
     * indices).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   488
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   489
     * @param index the index of the element to be removed
90ce3da70b43 Initial load
duke
parents:
diff changeset
   490
     * @return the element that was removed from the list
90ce3da70b43 Initial load
duke
parents:
diff changeset
   491
     * @throws IndexOutOfBoundsException {@inheritDoc}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   492
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   493
    public E remove(int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   494
        rangeCheck(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   495
90ce3da70b43 Initial load
duke
parents:
diff changeset
   496
        modCount++;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   497
        E oldValue = elementData(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   498
90ce3da70b43 Initial load
duke
parents:
diff changeset
   499
        int numMoved = size - index - 1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   500
        if (numMoved > 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   501
            System.arraycopy(elementData, index+1, elementData, index,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   502
                             numMoved);
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   503
        elementData[--size] = null; // clear to let GC do its work
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   504
90ce3da70b43 Initial load
duke
parents:
diff changeset
   505
        return oldValue;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   506
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   507
90ce3da70b43 Initial load
duke
parents:
diff changeset
   508
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   509
     * Removes the first occurrence of the specified element from this list,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   510
     * if it is present.  If the list does not contain the element, it is
90ce3da70b43 Initial load
duke
parents:
diff changeset
   511
     * unchanged.  More formally, removes the element with the lowest index
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   512
     * {@code i} such that
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   513
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   514
     * (if such an element exists).  Returns {@code true} if this list
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   515
     * contained the specified element (or equivalently, if this list
90ce3da70b43 Initial load
duke
parents:
diff changeset
   516
     * changed as a result of the call).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   517
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   518
     * @param o element to be removed from this list, if present
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   519
     * @return {@code true} if this list contained the specified element
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   520
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   521
    public boolean remove(Object o) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   522
        if (o == null) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   523
            for (int index = 0; index < size; index++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   524
                if (elementData[index] == null) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   525
                    fastRemove(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   526
                    return true;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   527
                }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   528
        } else {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   529
            for (int index = 0; index < size; index++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   530
                if (o.equals(elementData[index])) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   531
                    fastRemove(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   532
                    return true;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   533
                }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   534
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   535
        return false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   536
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   537
90ce3da70b43 Initial load
duke
parents:
diff changeset
   538
    /*
90ce3da70b43 Initial load
duke
parents:
diff changeset
   539
     * Private remove method that skips bounds checking and does not
90ce3da70b43 Initial load
duke
parents:
diff changeset
   540
     * return the value removed.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   541
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   542
    private void fastRemove(int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   543
        modCount++;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   544
        int numMoved = size - index - 1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   545
        if (numMoved > 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   546
            System.arraycopy(elementData, index+1, elementData, index,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   547
                             numMoved);
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   548
        elementData[--size] = null; // clear to let GC do its work
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   549
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   550
90ce3da70b43 Initial load
duke
parents:
diff changeset
   551
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   552
     * Removes all of the elements from this list.  The list will
90ce3da70b43 Initial load
duke
parents:
diff changeset
   553
     * be empty after this call returns.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   554
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   555
    public void clear() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   556
        modCount++;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   557
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   558
        // clear to let GC do its work
16725
9e7cfcc4ff6a 8011199: Backout changeset JDK-7143928 (2b34a1eb3153)
mduigou
parents: 16723
diff changeset
   559
        for (int i = 0; i < size; i++)
9e7cfcc4ff6a 8011199: Backout changeset JDK-7143928 (2b34a1eb3153)
mduigou
parents: 16723
diff changeset
   560
            elementData[i] = null;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   561
90ce3da70b43 Initial load
duke
parents:
diff changeset
   562
        size = 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   563
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   564
90ce3da70b43 Initial load
duke
parents:
diff changeset
   565
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   566
     * Appends all of the elements in the specified collection to the end of
90ce3da70b43 Initial load
duke
parents:
diff changeset
   567
     * this list, in the order that they are returned by the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   568
     * specified collection's Iterator.  The behavior of this operation is
90ce3da70b43 Initial load
duke
parents:
diff changeset
   569
     * undefined if the specified collection is modified while the operation
90ce3da70b43 Initial load
duke
parents:
diff changeset
   570
     * is in progress.  (This implies that the behavior of this call is
90ce3da70b43 Initial load
duke
parents:
diff changeset
   571
     * undefined if the specified collection is this list, and this
90ce3da70b43 Initial load
duke
parents:
diff changeset
   572
     * list is nonempty.)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   573
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   574
     * @param c collection containing elements to be added to this list
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   575
     * @return {@code true} if this list changed as a result of the call
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   576
     * @throws NullPointerException if the specified collection is null
90ce3da70b43 Initial load
duke
parents:
diff changeset
   577
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   578
    public boolean addAll(Collection<? extends E> c) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   579
        Object[] a = c.toArray();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   580
        int numNew = a.length;
7020
25638687fe82 6992121: StringBuilder.ensureCapacity(int minCap) throws OutOfMemoryError with minCap=Integer.MIN_VALUE
mchung
parents: 5506
diff changeset
   581
        ensureCapacityInternal(size + numNew);  // Increments modCount
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   582
        System.arraycopy(a, 0, elementData, size, numNew);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   583
        size += numNew;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   584
        return numNew != 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   585
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   586
90ce3da70b43 Initial load
duke
parents:
diff changeset
   587
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   588
     * Inserts all of the elements in the specified collection into this
90ce3da70b43 Initial load
duke
parents:
diff changeset
   589
     * list, starting at the specified position.  Shifts the element
90ce3da70b43 Initial load
duke
parents:
diff changeset
   590
     * currently at that position (if any) and any subsequent elements to
90ce3da70b43 Initial load
duke
parents:
diff changeset
   591
     * the right (increases their indices).  The new elements will appear
90ce3da70b43 Initial load
duke
parents:
diff changeset
   592
     * in the list in the order that they are returned by the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   593
     * specified collection's iterator.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   594
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   595
     * @param index index at which to insert the first element from the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   596
     *              specified collection
90ce3da70b43 Initial load
duke
parents:
diff changeset
   597
     * @param c collection containing elements to be added to this list
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   598
     * @return {@code true} if this list changed as a result of the call
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   599
     * @throws IndexOutOfBoundsException {@inheritDoc}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   600
     * @throws NullPointerException if the specified collection is null
90ce3da70b43 Initial load
duke
parents:
diff changeset
   601
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   602
    public boolean addAll(int index, Collection<? extends E> c) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   603
        rangeCheckForAdd(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   604
90ce3da70b43 Initial load
duke
parents:
diff changeset
   605
        Object[] a = c.toArray();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   606
        int numNew = a.length;
7020
25638687fe82 6992121: StringBuilder.ensureCapacity(int minCap) throws OutOfMemoryError with minCap=Integer.MIN_VALUE
mchung
parents: 5506
diff changeset
   607
        ensureCapacityInternal(size + numNew);  // Increments modCount
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   608
90ce3da70b43 Initial load
duke
parents:
diff changeset
   609
        int numMoved = size - index;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   610
        if (numMoved > 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   611
            System.arraycopy(elementData, index, elementData, index + numNew,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   612
                             numMoved);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   613
90ce3da70b43 Initial load
duke
parents:
diff changeset
   614
        System.arraycopy(a, 0, elementData, index, numNew);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   615
        size += numNew;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   616
        return numNew != 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   617
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   618
90ce3da70b43 Initial load
duke
parents:
diff changeset
   619
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   620
     * Removes from this list all of the elements whose index is between
90ce3da70b43 Initial load
duke
parents:
diff changeset
   621
     * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   622
     * Shifts any succeeding elements to the left (reduces their index).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   623
     * This call shortens the list by {@code (toIndex - fromIndex)} elements.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   624
     * (If {@code toIndex==fromIndex}, this operation has no effect.)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   625
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   626
     * @throws IndexOutOfBoundsException if {@code fromIndex} or
90ce3da70b43 Initial load
duke
parents:
diff changeset
   627
     *         {@code toIndex} is out of range
90ce3da70b43 Initial load
duke
parents:
diff changeset
   628
     *         ({@code fromIndex < 0 ||
90ce3da70b43 Initial load
duke
parents:
diff changeset
   629
     *          toIndex > size() ||
90ce3da70b43 Initial load
duke
parents:
diff changeset
   630
     *          toIndex < fromIndex})
90ce3da70b43 Initial load
duke
parents:
diff changeset
   631
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   632
    protected void removeRange(int fromIndex, int toIndex) {
23580
1055a611c69b 8014066: Remove redundant restriction from ArrayList#removeRange() spec
igerasim
parents: 22078
diff changeset
   633
        if (fromIndex > toIndex) {
1055a611c69b 8014066: Remove redundant restriction from ArrayList#removeRange() spec
igerasim
parents: 22078
diff changeset
   634
            throw new IndexOutOfBoundsException(
1055a611c69b 8014066: Remove redundant restriction from ArrayList#removeRange() spec
igerasim
parents: 22078
diff changeset
   635
                    outOfBoundsMsg(fromIndex, toIndex));
1055a611c69b 8014066: Remove redundant restriction from ArrayList#removeRange() spec
igerasim
parents: 22078
diff changeset
   636
        }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   637
        modCount++;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   638
        int numMoved = size - toIndex;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   639
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   640
                         numMoved);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   641
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   642
        // clear to let GC do its work
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   643
        int newSize = size - (toIndex-fromIndex);
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   644
        for (int i = newSize; i < size; i++) {
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   645
            elementData[i] = null;
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   646
        }
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   647
        size = newSize;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   648
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   649
90ce3da70b43 Initial load
duke
parents:
diff changeset
   650
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   651
     * Checks if the given index is in range.  If not, throws an appropriate
90ce3da70b43 Initial load
duke
parents:
diff changeset
   652
     * runtime exception.  This method does *not* check if the index is
90ce3da70b43 Initial load
duke
parents:
diff changeset
   653
     * negative: It is always used immediately prior to an array access,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   654
     * which throws an ArrayIndexOutOfBoundsException if index is negative.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   655
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   656
    private void rangeCheck(int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   657
        if (index >= size)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   658
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
90ce3da70b43 Initial load
duke
parents:
diff changeset
   659
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   660
90ce3da70b43 Initial load
duke
parents:
diff changeset
   661
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   662
     * A version of rangeCheck used by add and addAll.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   663
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   664
    private void rangeCheckForAdd(int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   665
        if (index > size || index < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   666
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
90ce3da70b43 Initial load
duke
parents:
diff changeset
   667
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   668
90ce3da70b43 Initial load
duke
parents:
diff changeset
   669
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   670
     * Constructs an IndexOutOfBoundsException detail message.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   671
     * Of the many possible refactorings of the error handling code,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   672
     * this "outlining" performs best with both server and client VMs.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   673
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   674
    private String outOfBoundsMsg(int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   675
        return "Index: "+index+", Size: "+size;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   676
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   677
90ce3da70b43 Initial load
duke
parents:
diff changeset
   678
    /**
23580
1055a611c69b 8014066: Remove redundant restriction from ArrayList#removeRange() spec
igerasim
parents: 22078
diff changeset
   679
     * A version used in checking (fromIndex > toIndex) condition
1055a611c69b 8014066: Remove redundant restriction from ArrayList#removeRange() spec
igerasim
parents: 22078
diff changeset
   680
     */
1055a611c69b 8014066: Remove redundant restriction from ArrayList#removeRange() spec
igerasim
parents: 22078
diff changeset
   681
    private static String outOfBoundsMsg(int fromIndex, int toIndex) {
1055a611c69b 8014066: Remove redundant restriction from ArrayList#removeRange() spec
igerasim
parents: 22078
diff changeset
   682
        return "From Index: " + fromIndex + " > To Index: " + toIndex;
1055a611c69b 8014066: Remove redundant restriction from ArrayList#removeRange() spec
igerasim
parents: 22078
diff changeset
   683
    }
1055a611c69b 8014066: Remove redundant restriction from ArrayList#removeRange() spec
igerasim
parents: 22078
diff changeset
   684
1055a611c69b 8014066: Remove redundant restriction from ArrayList#removeRange() spec
igerasim
parents: 22078
diff changeset
   685
    /**
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   686
     * Removes from this list all of its elements that are contained in the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   687
     * specified collection.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   688
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   689
     * @param c collection containing elements to be removed from this list
90ce3da70b43 Initial load
duke
parents:
diff changeset
   690
     * @return {@code true} if this list changed as a result of the call
90ce3da70b43 Initial load
duke
parents:
diff changeset
   691
     * @throws ClassCastException if the class of an element of this list
9503
588cf31d584a 6546713: link the word (optional) in exception specifications to the text which provides explanation and context.
mduigou
parents: 7668
diff changeset
   692
     *         is incompatible with the specified collection
588cf31d584a 6546713: link the word (optional) in exception specifications to the text which provides explanation and context.
mduigou
parents: 7668
diff changeset
   693
     * (<a href="Collection.html#optional-restrictions">optional</a>)
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   694
     * @throws NullPointerException if this list contains a null element and the
9503
588cf31d584a 6546713: link the word (optional) in exception specifications to the text which provides explanation and context.
mduigou
parents: 7668
diff changeset
   695
     *         specified collection does not permit null elements
588cf31d584a 6546713: link the word (optional) in exception specifications to the text which provides explanation and context.
mduigou
parents: 7668
diff changeset
   696
     * (<a href="Collection.html#optional-restrictions">optional</a>),
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   697
     *         or if the specified collection is null
90ce3da70b43 Initial load
duke
parents:
diff changeset
   698
     * @see Collection#contains(Object)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   699
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   700
    public boolean removeAll(Collection<?> c) {
17441
5ae43433d158 4802647: Throw required NPEs from removeAll()/retainAll()
mduigou
parents: 17432
diff changeset
   701
        Objects.requireNonNull(c);
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   702
        return batchRemove(c, false);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   703
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   704
90ce3da70b43 Initial load
duke
parents:
diff changeset
   705
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   706
     * Retains only the elements in this list that are contained in the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   707
     * specified collection.  In other words, removes from this list all
90ce3da70b43 Initial load
duke
parents:
diff changeset
   708
     * of its elements that are not contained in the specified collection.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   709
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   710
     * @param c collection containing elements to be retained in this list
90ce3da70b43 Initial load
duke
parents:
diff changeset
   711
     * @return {@code true} if this list changed as a result of the call
90ce3da70b43 Initial load
duke
parents:
diff changeset
   712
     * @throws ClassCastException if the class of an element of this list
9503
588cf31d584a 6546713: link the word (optional) in exception specifications to the text which provides explanation and context.
mduigou
parents: 7668
diff changeset
   713
     *         is incompatible with the specified collection
588cf31d584a 6546713: link the word (optional) in exception specifications to the text which provides explanation and context.
mduigou
parents: 7668
diff changeset
   714
     * (<a href="Collection.html#optional-restrictions">optional</a>)
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   715
     * @throws NullPointerException if this list contains a null element and the
9503
588cf31d584a 6546713: link the word (optional) in exception specifications to the text which provides explanation and context.
mduigou
parents: 7668
diff changeset
   716
     *         specified collection does not permit null elements
588cf31d584a 6546713: link the word (optional) in exception specifications to the text which provides explanation and context.
mduigou
parents: 7668
diff changeset
   717
     * (<a href="Collection.html#optional-restrictions">optional</a>),
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   718
     *         or if the specified collection is null
90ce3da70b43 Initial load
duke
parents:
diff changeset
   719
     * @see Collection#contains(Object)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   720
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   721
    public boolean retainAll(Collection<?> c) {
17441
5ae43433d158 4802647: Throw required NPEs from removeAll()/retainAll()
mduigou
parents: 17432
diff changeset
   722
        Objects.requireNonNull(c);
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   723
        return batchRemove(c, true);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   724
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   725
90ce3da70b43 Initial load
duke
parents:
diff changeset
   726
    private boolean batchRemove(Collection<?> c, boolean complement) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   727
        final Object[] elementData = this.elementData;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   728
        int r = 0, w = 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   729
        boolean modified = false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   730
        try {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   731
            for (; r < size; r++)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   732
                if (c.contains(elementData[r]) == complement)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   733
                    elementData[w++] = elementData[r];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   734
        } finally {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   735
            // Preserve behavioral compatibility with AbstractCollection,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   736
            // even if c.contains() throws.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   737
            if (r != size) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   738
                System.arraycopy(elementData, r,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   739
                                 elementData, w,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   740
                                 size - r);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   741
                w += size - r;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   742
            }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   743
            if (w != size) {
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   744
                // clear to let GC do its work
16725
9e7cfcc4ff6a 8011199: Backout changeset JDK-7143928 (2b34a1eb3153)
mduigou
parents: 16723
diff changeset
   745
                for (int i = w; i < size; i++)
9e7cfcc4ff6a 8011199: Backout changeset JDK-7143928 (2b34a1eb3153)
mduigou
parents: 16723
diff changeset
   746
                    elementData[i] = null;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   747
                modCount += size - w;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   748
                size = w;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   749
                modified = true;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   750
            }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   751
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   752
        return modified;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   753
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   754
90ce3da70b43 Initial load
duke
parents:
diff changeset
   755
    /**
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   756
     * Save the state of the {@code ArrayList} instance to a stream (that
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   757
     * is, serialize it).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   758
     *
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   759
     * @serialData The length of the array backing the {@code ArrayList}
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   760
     *             instance is emitted (int), followed by all of its elements
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   761
     *             (each an {@code Object}) in the proper order.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   762
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   763
    private void writeObject(java.io.ObjectOutputStream s)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   764
        throws java.io.IOException{
90ce3da70b43 Initial load
duke
parents:
diff changeset
   765
        // Write out element count, and any hidden stuff
90ce3da70b43 Initial load
duke
parents:
diff changeset
   766
        int expectedModCount = modCount;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   767
        s.defaultWriteObject();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   768
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   769
        // Write out size as capacity for behavioural compatibility with clone()
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   770
        s.writeInt(size);
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   771
90ce3da70b43 Initial load
duke
parents:
diff changeset
   772
        // Write out all elements in the proper order.
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   773
        for (int i=0; i<size; i++) {
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   774
            s.writeObject(elementData[i]);
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   775
        }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   776
90ce3da70b43 Initial load
duke
parents:
diff changeset
   777
        if (modCount != expectedModCount) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   778
            throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   779
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   780
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   781
90ce3da70b43 Initial load
duke
parents:
diff changeset
   782
    /**
24122
75b332affee0 8035584: ArrayList(c) should avoid inflation if c is empty
mduigou
parents: 23580
diff changeset
   783
     * Reconstitute the {@code ArrayList} instance from a stream (that is,
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   784
     * deserialize it).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   785
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   786
    private void readObject(java.io.ObjectInputStream s)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   787
        throws java.io.IOException, ClassNotFoundException {
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   788
        elementData = EMPTY_ELEMENTDATA;
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   789
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   790
        // Read in size, and any hidden stuff
90ce3da70b43 Initial load
duke
parents:
diff changeset
   791
        s.defaultReadObject();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   792
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   793
        // Read in capacity
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   794
        s.readInt(); // ignored
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   795
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   796
        if (size > 0) {
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   797
            // be like clone(), allocate array based upon size not capacity
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   798
            ensureCapacityInternal(size);
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   799
16855
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   800
            Object[] a = elementData;
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   801
            // Read in all elements in the proper order.
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   802
            for (int i=0; i<size; i++) {
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   803
                a[i] = s.readObject();
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   804
            }
106eaf391fbc 8011200: (coll) Optimize empty HashMap and ArrayList
mduigou
parents: 16725
diff changeset
   805
        }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   806
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   807
90ce3da70b43 Initial load
duke
parents:
diff changeset
   808
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   809
     * Returns a list iterator over the elements in this list (in proper
90ce3da70b43 Initial load
duke
parents:
diff changeset
   810
     * sequence), starting at the specified position in the list.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   811
     * The specified index indicates the first element that would be
90ce3da70b43 Initial load
duke
parents:
diff changeset
   812
     * returned by an initial call to {@link ListIterator#next next}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   813
     * An initial call to {@link ListIterator#previous previous} would
90ce3da70b43 Initial load
duke
parents:
diff changeset
   814
     * return the element with the specified index minus one.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   815
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   816
     * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   817
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   818
     * @throws IndexOutOfBoundsException {@inheritDoc}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   819
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   820
    public ListIterator<E> listIterator(int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   821
        if (index < 0 || index > size)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   822
            throw new IndexOutOfBoundsException("Index: "+index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   823
        return new ListItr(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   824
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   825
90ce3da70b43 Initial load
duke
parents:
diff changeset
   826
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   827
     * Returns a list iterator over the elements in this list (in proper
90ce3da70b43 Initial load
duke
parents:
diff changeset
   828
     * sequence).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   829
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   830
     * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   831
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   832
     * @see #listIterator(int)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   833
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   834
    public ListIterator<E> listIterator() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   835
        return new ListItr(0);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   836
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   837
90ce3da70b43 Initial load
duke
parents:
diff changeset
   838
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   839
     * Returns an iterator over the elements in this list in proper sequence.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   840
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   841
     * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   842
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   843
     * @return an iterator over the elements in this list in proper sequence
90ce3da70b43 Initial load
duke
parents:
diff changeset
   844
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   845
    public Iterator<E> iterator() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   846
        return new Itr();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   847
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   848
90ce3da70b43 Initial load
duke
parents:
diff changeset
   849
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   850
     * An optimized version of AbstractList.Itr
90ce3da70b43 Initial load
duke
parents:
diff changeset
   851
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   852
    private class Itr implements Iterator<E> {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   853
        int cursor;       // index of next element to return
90ce3da70b43 Initial load
duke
parents:
diff changeset
   854
        int lastRet = -1; // index of last element returned; -1 if no such
90ce3da70b43 Initial load
duke
parents:
diff changeset
   855
        int expectedModCount = modCount;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   856
90ce3da70b43 Initial load
duke
parents:
diff changeset
   857
        public boolean hasNext() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   858
            return cursor != size;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   859
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   860
90ce3da70b43 Initial load
duke
parents:
diff changeset
   861
        @SuppressWarnings("unchecked")
90ce3da70b43 Initial load
duke
parents:
diff changeset
   862
        public E next() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   863
            checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   864
            int i = cursor;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   865
            if (i >= size)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   866
                throw new NoSuchElementException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   867
            Object[] elementData = ArrayList.this.elementData;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   868
            if (i >= elementData.length)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   869
                throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   870
            cursor = i + 1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   871
            return (E) elementData[lastRet = i];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   872
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   873
90ce3da70b43 Initial load
duke
parents:
diff changeset
   874
        public void remove() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   875
            if (lastRet < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   876
                throw new IllegalStateException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   877
            checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   878
90ce3da70b43 Initial load
duke
parents:
diff changeset
   879
            try {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   880
                ArrayList.this.remove(lastRet);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   881
                cursor = lastRet;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   882
                lastRet = -1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   883
                expectedModCount = modCount;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   884
            } catch (IndexOutOfBoundsException ex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   885
                throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   886
            }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   887
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   888
17168
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   889
        @Override
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   890
        @SuppressWarnings("unchecked")
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   891
        public void forEachRemaining(Consumer<? super E> consumer) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   892
            Objects.requireNonNull(consumer);
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   893
            final int size = ArrayList.this.size;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   894
            int i = cursor;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   895
            if (i >= size) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   896
                return;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   897
            }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   898
            final Object[] elementData = ArrayList.this.elementData;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   899
            if (i >= elementData.length) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   900
                throw new ConcurrentModificationException();
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   901
            }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   902
            while (i != size && modCount == expectedModCount) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   903
                consumer.accept((E) elementData[i++]);
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   904
            }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   905
            // update once at end of iteration to reduce heap write traffic
17432
efdf6eb85a17 8013150: Iterator.remove and forEachRemaining relationship not specified
mduigou
parents: 17180
diff changeset
   906
            cursor = i;
efdf6eb85a17 8013150: Iterator.remove and forEachRemaining relationship not specified
mduigou
parents: 17180
diff changeset
   907
            lastRet = i - 1;
17168
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   908
            checkForComodification();
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   909
        }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
   910
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   911
        final void checkForComodification() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   912
            if (modCount != expectedModCount)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   913
                throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   914
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   915
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   916
90ce3da70b43 Initial load
duke
parents:
diff changeset
   917
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   918
     * An optimized version of AbstractList.ListItr
90ce3da70b43 Initial load
duke
parents:
diff changeset
   919
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   920
    private class ListItr extends Itr implements ListIterator<E> {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   921
        ListItr(int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   922
            super();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   923
            cursor = index;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   924
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   925
90ce3da70b43 Initial load
duke
parents:
diff changeset
   926
        public boolean hasPrevious() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   927
            return cursor != 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   928
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   929
90ce3da70b43 Initial load
duke
parents:
diff changeset
   930
        public int nextIndex() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   931
            return cursor;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   932
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   933
90ce3da70b43 Initial load
duke
parents:
diff changeset
   934
        public int previousIndex() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   935
            return cursor - 1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   936
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   937
90ce3da70b43 Initial load
duke
parents:
diff changeset
   938
        @SuppressWarnings("unchecked")
90ce3da70b43 Initial load
duke
parents:
diff changeset
   939
        public E previous() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   940
            checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   941
            int i = cursor - 1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   942
            if (i < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   943
                throw new NoSuchElementException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   944
            Object[] elementData = ArrayList.this.elementData;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   945
            if (i >= elementData.length)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   946
                throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   947
            cursor = i;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   948
            return (E) elementData[lastRet = i];
90ce3da70b43 Initial load
duke
parents:
diff changeset
   949
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   950
90ce3da70b43 Initial load
duke
parents:
diff changeset
   951
        public void set(E e) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   952
            if (lastRet < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   953
                throw new IllegalStateException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   954
            checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   955
90ce3da70b43 Initial load
duke
parents:
diff changeset
   956
            try {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   957
                ArrayList.this.set(lastRet, e);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   958
            } catch (IndexOutOfBoundsException ex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   959
                throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   960
            }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   961
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   962
90ce3da70b43 Initial load
duke
parents:
diff changeset
   963
        public void add(E e) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   964
            checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   965
90ce3da70b43 Initial load
duke
parents:
diff changeset
   966
            try {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   967
                int i = cursor;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   968
                ArrayList.this.add(i, e);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   969
                cursor = i + 1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   970
                lastRet = -1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   971
                expectedModCount = modCount;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   972
            } catch (IndexOutOfBoundsException ex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   973
                throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   974
            }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   975
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   976
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   977
90ce3da70b43 Initial load
duke
parents:
diff changeset
   978
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   979
     * Returns a view of the portion of this list between the specified
90ce3da70b43 Initial load
duke
parents:
diff changeset
   980
     * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.  (If
90ce3da70b43 Initial load
duke
parents:
diff changeset
   981
     * {@code fromIndex} and {@code toIndex} are equal, the returned list is
90ce3da70b43 Initial load
duke
parents:
diff changeset
   982
     * empty.)  The returned list is backed by this list, so non-structural
90ce3da70b43 Initial load
duke
parents:
diff changeset
   983
     * changes in the returned list are reflected in this list, and vice-versa.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   984
     * The returned list supports all of the optional list operations.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   985
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   986
     * <p>This method eliminates the need for explicit range operations (of
90ce3da70b43 Initial load
duke
parents:
diff changeset
   987
     * the sort that commonly exist for arrays).  Any operation that expects
90ce3da70b43 Initial load
duke
parents:
diff changeset
   988
     * a list can be used as a range operation by passing a subList view
90ce3da70b43 Initial load
duke
parents:
diff changeset
   989
     * instead of a whole list.  For example, the following idiom
90ce3da70b43 Initial load
duke
parents:
diff changeset
   990
     * removes a range of elements from a list:
90ce3da70b43 Initial load
duke
parents:
diff changeset
   991
     * <pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   992
     *      list.subList(from, to).clear();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   993
     * </pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   994
     * Similar idioms may be constructed for {@link #indexOf(Object)} and
90ce3da70b43 Initial load
duke
parents:
diff changeset
   995
     * {@link #lastIndexOf(Object)}, and all of the algorithms in the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   996
     * {@link Collections} class can be applied to a subList.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   997
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   998
     * <p>The semantics of the list returned by this method become undefined if
90ce3da70b43 Initial load
duke
parents:
diff changeset
   999
     * the backing list (i.e., this list) is <i>structurally modified</i> in
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1000
     * any way other than via the returned list.  (Structural modifications are
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1001
     * those that change the size of this list, or otherwise perturb it in such
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1002
     * a fashion that iterations in progress may yield incorrect results.)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1003
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1004
     * @throws IndexOutOfBoundsException {@inheritDoc}
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1005
     * @throws IllegalArgumentException {@inheritDoc}
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1006
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1007
    public List<E> subList(int fromIndex, int toIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1008
        subListRangeCheck(fromIndex, toIndex, size);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1009
        return new SubList(this, 0, fromIndex, toIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1010
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1011
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1012
    static void subListRangeCheck(int fromIndex, int toIndex, int size) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1013
        if (fromIndex < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1014
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1015
        if (toIndex > size)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1016
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1017
        if (fromIndex > toIndex)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1018
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1019
                                               ") > toIndex(" + toIndex + ")");
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1020
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1021
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1022
    private class SubList extends AbstractList<E> implements RandomAccess {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1023
        private final AbstractList<E> parent;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1024
        private final int parentOffset;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1025
        private final int offset;
51
6fe31bc95bbc 6600143: Remove another 450 unnecessary casts
martin
parents: 2
diff changeset
  1026
        int size;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1027
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1028
        SubList(AbstractList<E> parent,
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1029
                int offset, int fromIndex, int toIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1030
            this.parent = parent;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1031
            this.parentOffset = fromIndex;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1032
            this.offset = offset + fromIndex;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1033
            this.size = toIndex - fromIndex;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1034
            this.modCount = ArrayList.this.modCount;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1035
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1036
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1037
        public E set(int index, E e) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1038
            rangeCheck(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1039
            checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1040
            E oldValue = ArrayList.this.elementData(offset + index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1041
            ArrayList.this.elementData[offset + index] = e;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1042
            return oldValue;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1043
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1044
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1045
        public E get(int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1046
            rangeCheck(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1047
            checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1048
            return ArrayList.this.elementData(offset + index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1049
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1050
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1051
        public int size() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1052
            checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1053
            return this.size;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1054
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1055
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1056
        public void add(int index, E e) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1057
            rangeCheckForAdd(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1058
            checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1059
            parent.add(parentOffset + index, e);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1060
            this.modCount = parent.modCount;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1061
            this.size++;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1062
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1063
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1064
        public E remove(int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1065
            rangeCheck(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1066
            checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1067
            E result = parent.remove(parentOffset + index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1068
            this.modCount = parent.modCount;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1069
            this.size--;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1070
            return result;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1071
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1072
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1073
        protected void removeRange(int fromIndex, int toIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1074
            checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1075
            parent.removeRange(parentOffset + fromIndex,
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1076
                               parentOffset + toIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1077
            this.modCount = parent.modCount;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1078
            this.size -= toIndex - fromIndex;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1079
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1080
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1081
        public boolean addAll(Collection<? extends E> c) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1082
            return addAll(this.size, c);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1083
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1084
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1085
        public boolean addAll(int index, Collection<? extends E> c) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1086
            rangeCheckForAdd(index);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1087
            int cSize = c.size();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1088
            if (cSize==0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1089
                return false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1090
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1091
            checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1092
            parent.addAll(parentOffset + index, c);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1093
            this.modCount = parent.modCount;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1094
            this.size += cSize;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1095
            return true;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1096
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1097
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1098
        public Iterator<E> iterator() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1099
            return listIterator();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1100
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1101
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1102
        public ListIterator<E> listIterator(final int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1103
            checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1104
            rangeCheckForAdd(index);
51
6fe31bc95bbc 6600143: Remove another 450 unnecessary casts
martin
parents: 2
diff changeset
  1105
            final int offset = this.offset;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1106
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1107
            return new ListIterator<E>() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1108
                int cursor = index;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1109
                int lastRet = -1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1110
                int expectedModCount = ArrayList.this.modCount;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1111
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1112
                public boolean hasNext() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1113
                    return cursor != SubList.this.size;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1114
                }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1115
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1116
                @SuppressWarnings("unchecked")
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1117
                public E next() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1118
                    checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1119
                    int i = cursor;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1120
                    if (i >= SubList.this.size)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1121
                        throw new NoSuchElementException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1122
                    Object[] elementData = ArrayList.this.elementData;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1123
                    if (offset + i >= elementData.length)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1124
                        throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1125
                    cursor = i + 1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1126
                    return (E) elementData[offset + (lastRet = i)];
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1127
                }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1128
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1129
                public boolean hasPrevious() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1130
                    return cursor != 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1131
                }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1132
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1133
                @SuppressWarnings("unchecked")
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1134
                public E previous() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1135
                    checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1136
                    int i = cursor - 1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1137
                    if (i < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1138
                        throw new NoSuchElementException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1139
                    Object[] elementData = ArrayList.this.elementData;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1140
                    if (offset + i >= elementData.length)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1141
                        throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1142
                    cursor = i;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1143
                    return (E) elementData[offset + (lastRet = i)];
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1144
                }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1145
17168
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1146
                @SuppressWarnings("unchecked")
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1147
                public void forEachRemaining(Consumer<? super E> consumer) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1148
                    Objects.requireNonNull(consumer);
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1149
                    final int size = SubList.this.size;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1150
                    int i = cursor;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1151
                    if (i >= size) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1152
                        return;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1153
                    }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1154
                    final Object[] elementData = ArrayList.this.elementData;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1155
                    if (offset + i >= elementData.length) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1156
                        throw new ConcurrentModificationException();
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1157
                    }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1158
                    while (i != size && modCount == expectedModCount) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1159
                        consumer.accept((E) elementData[offset + (i++)]);
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1160
                    }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1161
                    // update once at end of iteration to reduce heap write traffic
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1162
                    lastRet = cursor = i;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1163
                    checkForComodification();
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1164
                }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1165
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1166
                public int nextIndex() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1167
                    return cursor;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1168
                }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1169
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1170
                public int previousIndex() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1171
                    return cursor - 1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1172
                }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1173
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1174
                public void remove() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1175
                    if (lastRet < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1176
                        throw new IllegalStateException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1177
                    checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1178
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1179
                    try {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1180
                        SubList.this.remove(lastRet);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1181
                        cursor = lastRet;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1182
                        lastRet = -1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1183
                        expectedModCount = ArrayList.this.modCount;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1184
                    } catch (IndexOutOfBoundsException ex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1185
                        throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1186
                    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1187
                }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1188
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1189
                public void set(E e) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1190
                    if (lastRet < 0)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1191
                        throw new IllegalStateException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1192
                    checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1193
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1194
                    try {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1195
                        ArrayList.this.set(offset + lastRet, e);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1196
                    } catch (IndexOutOfBoundsException ex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1197
                        throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1198
                    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1199
                }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1200
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1201
                public void add(E e) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1202
                    checkForComodification();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1203
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1204
                    try {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1205
                        int i = cursor;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1206
                        SubList.this.add(i, e);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1207
                        cursor = i + 1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1208
                        lastRet = -1;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1209
                        expectedModCount = ArrayList.this.modCount;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1210
                    } catch (IndexOutOfBoundsException ex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1211
                        throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1212
                    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1213
                }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1214
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1215
                final void checkForComodification() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1216
                    if (expectedModCount != ArrayList.this.modCount)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1217
                        throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1218
                }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1219
            };
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1220
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1221
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1222
        public List<E> subList(int fromIndex, int toIndex) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1223
            subListRangeCheck(fromIndex, toIndex, size);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1224
            return new SubList(this, offset, fromIndex, toIndex);
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1225
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1226
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1227
        private void rangeCheck(int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1228
            if (index < 0 || index >= this.size)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1229
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1230
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1231
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1232
        private void rangeCheckForAdd(int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1233
            if (index < 0 || index > this.size)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1234
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1235
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1236
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1237
        private String outOfBoundsMsg(int index) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1238
            return "Index: "+index+", Size: "+this.size;
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1239
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1240
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1241
        private void checkForComodification() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1242
            if (ArrayList.this.modCount != this.modCount)
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1243
                throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1244
        }
17168
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1245
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1246
        public Spliterator<E> spliterator() {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1247
            checkForComodification();
22078
bdec5d53e98c 8030851: Update code in java.util to use newer language features
psandoz
parents: 19435
diff changeset
  1248
            return new ArrayListSpliterator<>(ArrayList.this, offset,
bdec5d53e98c 8030851: Update code in java.util to use newer language features
psandoz
parents: 19435
diff changeset
  1249
                                              offset + this.size, this.modCount);
17168
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1250
        }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1251
    }
17166
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1252
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1253
    @Override
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1254
    public void forEach(Consumer<? super E> action) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1255
        Objects.requireNonNull(action);
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1256
        final int expectedModCount = modCount;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1257
        @SuppressWarnings("unchecked")
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1258
        final E[] elementData = (E[]) this.elementData;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1259
        final int size = this.size;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1260
        for (int i=0; modCount == expectedModCount && i < size; i++) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1261
            action.accept(elementData[i]);
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1262
        }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1263
        if (modCount != expectedModCount) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1264
            throw new ConcurrentModificationException();
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1265
        }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1266
    }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1267
19435
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18829
diff changeset
  1268
    /**
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18829
diff changeset
  1269
     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18829
diff changeset
  1270
     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18829
diff changeset
  1271
     * list.
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18829
diff changeset
  1272
     *
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18829
diff changeset
  1273
     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18829
diff changeset
  1274
     * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18829
diff changeset
  1275
     * Overriding implementations should document the reporting of additional
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18829
diff changeset
  1276
     * characteristic values.
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18829
diff changeset
  1277
     *
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18829
diff changeset
  1278
     * @return a {@code Spliterator} over the elements in this list
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18829
diff changeset
  1279
     * @since 1.8
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18829
diff changeset
  1280
     */
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18829
diff changeset
  1281
    @Override
17168
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1282
    public Spliterator<E> spliterator() {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1283
        return new ArrayListSpliterator<>(this, 0, -1, 0);
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1284
    }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1285
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1286
    /** Index-based split-by-two, lazily initialized Spliterator */
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1287
    static final class ArrayListSpliterator<E> implements Spliterator<E> {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1288
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1289
        /*
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1290
         * If ArrayLists were immutable, or structurally immutable (no
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1291
         * adds, removes, etc), we could implement their spliterators
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1292
         * with Arrays.spliterator. Instead we detect as much
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1293
         * interference during traversal as practical without
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1294
         * sacrificing much performance. We rely primarily on
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1295
         * modCounts. These are not guaranteed to detect concurrency
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1296
         * violations, and are sometimes overly conservative about
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1297
         * within-thread interference, but detect enough problems to
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1298
         * be worthwhile in practice. To carry this out, we (1) lazily
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1299
         * initialize fence and expectedModCount until the latest
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1300
         * point that we need to commit to the state we are checking
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1301
         * against; thus improving precision.  (This doesn't apply to
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1302
         * SubLists, that create spliterators with current non-lazy
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1303
         * values).  (2) We perform only a single
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1304
         * ConcurrentModificationException check at the end of forEach
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1305
         * (the most performance-sensitive method). When using forEach
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1306
         * (as opposed to iterators), we can normally only detect
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1307
         * interference after actions, not before. Further
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1308
         * CME-triggering checks apply to all other possible
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1309
         * violations of assumptions for example null or too-small
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1310
         * elementData array given its size(), that could only have
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1311
         * occurred due to interference.  This allows the inner loop
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1312
         * of forEach to run without any further checks, and
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1313
         * simplifies lambda-resolution. While this does entail a
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1314
         * number of checks, note that in the common case of
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1315
         * list.stream().forEach(a), no checks or other computation
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1316
         * occur anywhere other than inside forEach itself.  The other
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1317
         * less-often-used methods cannot take advantage of most of
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1318
         * these streamlinings.
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1319
         */
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1320
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1321
        private final ArrayList<E> list;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1322
        private int index; // current index, modified on advance/split
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1323
        private int fence; // -1 until used; then one past last index
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1324
        private int expectedModCount; // initialized when fence set
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1325
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1326
        /** Create new spliterator covering the given  range */
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1327
        ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1328
                             int expectedModCount) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1329
            this.list = list; // OK if null unless traversed
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1330
            this.index = origin;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1331
            this.fence = fence;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1332
            this.expectedModCount = expectedModCount;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1333
        }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1334
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1335
        private int getFence() { // initialize fence to size on first use
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1336
            int hi; // (a specialized variant appears in method forEach)
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1337
            ArrayList<E> lst;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1338
            if ((hi = fence) < 0) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1339
                if ((lst = list) == null)
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1340
                    hi = fence = 0;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1341
                else {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1342
                    expectedModCount = lst.modCount;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1343
                    hi = fence = lst.size;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1344
                }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1345
            }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1346
            return hi;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1347
        }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1348
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1349
        public ArrayListSpliterator<E> trySplit() {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1350
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1351
            return (lo >= mid) ? null : // divide range in half unless too small
22078
bdec5d53e98c 8030851: Update code in java.util to use newer language features
psandoz
parents: 19435
diff changeset
  1352
                new ArrayListSpliterator<>(list, lo, index = mid,
bdec5d53e98c 8030851: Update code in java.util to use newer language features
psandoz
parents: 19435
diff changeset
  1353
                                           expectedModCount);
17168
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1354
        }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1355
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1356
        public boolean tryAdvance(Consumer<? super E> action) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1357
            if (action == null)
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1358
                throw new NullPointerException();
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1359
            int hi = getFence(), i = index;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1360
            if (i < hi) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1361
                index = i + 1;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1362
                @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1363
                action.accept(e);
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1364
                if (list.modCount != expectedModCount)
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1365
                    throw new ConcurrentModificationException();
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1366
                return true;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1367
            }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1368
            return false;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1369
        }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1370
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1371
        public void forEachRemaining(Consumer<? super E> action) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1372
            int i, hi, mc; // hoist accesses and checks from loop
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1373
            ArrayList<E> lst; Object[] a;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1374
            if (action == null)
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1375
                throw new NullPointerException();
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1376
            if ((lst = list) != null && (a = lst.elementData) != null) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1377
                if ((hi = fence) < 0) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1378
                    mc = lst.modCount;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1379
                    hi = lst.size;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1380
                }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1381
                else
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1382
                    mc = expectedModCount;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1383
                if ((i = index) >= 0 && (index = hi) <= a.length) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1384
                    for (; i < hi; ++i) {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1385
                        @SuppressWarnings("unchecked") E e = (E) a[i];
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1386
                        action.accept(e);
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1387
                    }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1388
                    if (lst.modCount == mc)
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1389
                        return;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1390
                }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1391
            }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1392
            throw new ConcurrentModificationException();
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1393
        }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1394
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1395
        public long estimateSize() {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1396
            return (long) (getFence() - index);
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1397
        }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1398
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1399
        public int characteristics() {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1400
            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1401
        }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1402
    }
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 17166
diff changeset
  1403
17166
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1404
    @Override
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1405
    public boolean removeIf(Predicate<? super E> filter) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1406
        Objects.requireNonNull(filter);
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1407
        // figure out which elements are to be removed
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1408
        // any exception thrown from the filter predicate at this stage
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1409
        // will leave the collection unmodified
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1410
        int removeCount = 0;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1411
        final BitSet removeSet = new BitSet(size);
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1412
        final int expectedModCount = modCount;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1413
        final int size = this.size;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1414
        for (int i=0; modCount == expectedModCount && i < size; i++) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1415
            @SuppressWarnings("unchecked")
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1416
            final E element = (E) elementData[i];
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1417
            if (filter.test(element)) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1418
                removeSet.set(i);
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1419
                removeCount++;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1420
            }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1421
        }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1422
        if (modCount != expectedModCount) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1423
            throw new ConcurrentModificationException();
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1424
        }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1425
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1426
        // shift surviving elements left over the spaces left by removed elements
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1427
        final boolean anyToRemove = removeCount > 0;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1428
        if (anyToRemove) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1429
            final int newSize = size - removeCount;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1430
            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1431
                i = removeSet.nextClearBit(i);
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1432
                elementData[j] = elementData[i];
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1433
            }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1434
            for (int k=newSize; k < size; k++) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1435
                elementData[k] = null;  // Let gc do its work
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1436
            }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1437
            this.size = newSize;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1438
            if (modCount != expectedModCount) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1439
                throw new ConcurrentModificationException();
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1440
            }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1441
            modCount++;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1442
        }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1443
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1444
        return anyToRemove;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1445
    }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1446
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1447
    @Override
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1448
    @SuppressWarnings("unchecked")
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1449
    public void replaceAll(UnaryOperator<E> operator) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1450
        Objects.requireNonNull(operator);
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1451
        final int expectedModCount = modCount;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1452
        final int size = this.size;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1453
        for (int i=0; modCount == expectedModCount && i < size; i++) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1454
            elementData[i] = operator.apply((E) elementData[i]);
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1455
        }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1456
        if (modCount != expectedModCount) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1457
            throw new ConcurrentModificationException();
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1458
        }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1459
        modCount++;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1460
    }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1461
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1462
    @Override
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1463
    @SuppressWarnings("unchecked")
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1464
    public void sort(Comparator<? super E> c) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1465
        final int expectedModCount = modCount;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1466
        Arrays.sort((E[]) elementData, 0, size, c);
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1467
        if (modCount != expectedModCount) {
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1468
            throw new ConcurrentModificationException();
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1469
        }
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1470
        modCount++;
c83a0fa44906 8001647: default methods for Collections - forEach, removeIf, replaceAll, sort
akhil
parents: 16855
diff changeset
  1471
    }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
  1472
}