ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/ArrayDeque.java
(Generate patch)

Comparing jsr166/src/main/java/util/ArrayDeque.java (file contents):
Revision 1.7 by jsr166, Tue Apr 26 19:54:03 2005 UTC vs.
Revision 1.105 by jsr166, Tue Nov 1 21:42:45 2016 UTC

# Line 1 | Line 1
1   /*
2   * Written by Josh Bloch of Google Inc. and released to the public domain,
3 < * as explained at http://creativecommons.org/licenses/publicdomain.
3 > * as explained at http://creativecommons.org/publicdomain/zero/1.0/.
4   */
5  
6   package java.util;
7 < import java.io.*;
7 >
8 > import java.io.Serializable;
9 > import java.util.function.Consumer;
10 > import java.util.function.Predicate;
11 > import java.util.function.UnaryOperator;
12  
13   /**
14   * Resizable-array implementation of the {@link Deque} interface.  Array
# Line 15 | Line 19 | import java.io.*;
19   * {@link Stack} when used as a stack, and faster than {@link LinkedList}
20   * when used as a queue.
21   *
22 < * <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
23 < * Exceptions include {@link #remove(Object) remove}, {@link
24 < * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
25 < * removeLastOccurrence}, {@link #contains contains }, {@link #iterator
26 < * iterator.remove()}, and the bulk operations, all of which run in linear
27 < * time.
22 > * <p>Most {@code ArrayDeque} operations run in amortized constant time.
23 > * Exceptions include
24 > * {@link #remove(Object) remove},
25 > * {@link #removeFirstOccurrence removeFirstOccurrence},
26 > * {@link #removeLastOccurrence removeLastOccurrence},
27 > * {@link #contains contains},
28 > * {@link #iterator iterator.remove()},
29 > * and the bulk operations, all of which run in linear time.
30   *
31 < * <p>The iterators returned by this class's <tt>iterator</tt> method are
32 < * <i>fail-fast</i>: If the deque is modified at any time after the iterator
33 < * is created, in any way except through the iterator's own <tt>remove</tt>
34 < * method, the iterator will generally throw a {@link
31 > * <p>The iterators returned by this class's {@link #iterator() iterator}
32 > * method are <em>fail-fast</em>: If the deque is modified at any time after
33 > * the iterator is created, in any way except through the iterator's own
34 > * {@code remove} method, the iterator will generally throw a {@link
35   * ConcurrentModificationException}.  Thus, in the face of concurrent
36   * modification, the iterator fails quickly and cleanly, rather than risking
37   * arbitrary, non-deterministic behavior at an undetermined time in the
# Line 34 | Line 40 | import java.io.*;
40   * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
41   * as it is, generally speaking, impossible to make any hard guarantees in the
42   * presence of unsynchronized concurrent modification.  Fail-fast iterators
43 < * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
43 > * throw {@code ConcurrentModificationException} on a best-effort basis.
44   * Therefore, it would be wrong to write a program that depended on this
45   * exception for its correctness: <i>the fail-fast behavior of iterators
46   * should be used only to detect bugs.</i>
47   *
48   * <p>This class and its iterator implement all of the
49 < * optional methods of the {@link Collection} and {@link
50 < * Iterator} interfaces.  This class is a member of the <a
51 < * href="{@docRoot}/../guide/collections/index.html"> Java Collections
52 < * Framework</a>.
49 > * <em>optional</em> methods of the {@link Collection} and {@link
50 > * Iterator} interfaces.
51 > *
52 > * <p>This class is a member of the
53 > * <a href="{@docRoot}/../technotes/guides/collections/index.html">
54 > * Java Collections Framework</a>.
55   *
56   * @author  Josh Bloch and Doug Lea
57 + * @param <E> the type of elements held in this deque
58   * @since   1.6
50 * @param <E> the type of elements held in this collection
59   */
60   public class ArrayDeque<E> extends AbstractCollection<E>
61                             implements Deque<E>, Cloneable, Serializable
62   {
63      /**
64       * The array in which the elements of the deque are stored.
65 <     * The capacity of the deque is the length of this array, which is
66 <     * always a power of two. The array is never allowed to become
59 <     * full, except transiently within an addX method where it is
60 <     * resized (see doubleCapacity) immediately upon becoming full,
61 <     * thus avoiding head and tail wrapping around to equal each
62 <     * other.  We also guarantee that all array cells not holding
63 <     * deque elements are always null.
65 >     * We guarantee that all array cells not holding deque elements
66 >     * are always null.
67       */
68 <    private transient E[] elements;
68 >    transient Object[] elements;
69  
70      /**
71       * The index of the element at the head of the deque (which is the
72       * element that would be removed by remove() or pop()); or an
73 <     * arbitrary number equal to tail if the deque is empty.
71 <     */
72 <    private transient int head;
73 <
74 <    /**
75 <     * The index at which the next element would be added to the tail
76 <     * of the deque (via addLast(E), add(E), or push(E)).
77 <     */
78 <    private transient int tail;
79 <
80 <    /**
81 <     * The minimum capacity that we'll use for a newly created deque.
82 <     * Must be a power of 2.
73 >     * arbitrary number 0 <= head < elements.length if the deque is empty.
74       */
75 <    private static final int MIN_INITIAL_CAPACITY = 8;
75 >    transient int head;
76  
77 <    // ******  Array allocation and resizing utilities ******
77 >    /** Number of elements in this collection. */
78 >    transient int size;
79  
80      /**
81 <     * Allocate empty array to hold the given number of elements.
82 <     *
83 <     * @param numElements  the number of elements to hold.
84 <     */
85 <    private void allocateElements(int numElements) {
86 <        int initialCapacity = MIN_INITIAL_CAPACITY;
87 <        // Find the best power of two to hold elements.
88 <        // Tests "<=" because arrays aren't kept full.
89 <        if (numElements >= initialCapacity) {
90 <            initialCapacity = numElements;
91 <            initialCapacity |= (initialCapacity >>>  1);
92 <            initialCapacity |= (initialCapacity >>>  2);
93 <            initialCapacity |= (initialCapacity >>>  4);
94 <            initialCapacity |= (initialCapacity >>>  8);
95 <            initialCapacity |= (initialCapacity >>> 16);
96 <            initialCapacity++;
81 >     * The maximum size of array to allocate.
82 >     * Some VMs reserve some header words in an array.
83 >     * Attempts to allocate larger arrays may result in
84 >     * OutOfMemoryError: Requested array size exceeds VM limit
85 >     */
86 >    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
87 >
88 >    /**
89 >     * Increases the capacity of this deque by at least the given amount.
90 >     *
91 >     * @param needed the required minimum extra capacity; must be positive
92 >     */
93 >    private Object[] grow(int needed) {
94 >        // overflow-conscious code
95 >        // checkInvariants();
96 >        final int oldCapacity = elements.length;
97 >        int newCapacity;
98 >        // Double size if small; else grow by 50%
99 >        int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
100 >        if (jump < needed
101 >            || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
102 >            newCapacity = newCapacity(needed, jump);
103 >        elements = Arrays.copyOf(elements, newCapacity);
104 >        if (oldCapacity - head < size) {
105 >            // wrap around; slide first leg forward to end of array
106 >            int newSpace = newCapacity - oldCapacity;
107 >            System.arraycopy(elements, head,
108 >                             elements, head + newSpace,
109 >                             oldCapacity - head);
110 >            Arrays.fill(elements, head, head + newSpace, null);
111 >            head += newSpace;
112 >        }
113 >        return elements;
114 >        // checkInvariants();
115 >    }
116  
117 <            if (initialCapacity < 0)   // Too many elements, must back off
118 <                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
117 >    /** Capacity calculation for edge conditions, especially overflow. */
118 >    private int newCapacity(int needed, int jump) {
119 >        final int oldCapacity = elements.length, minCapacity;
120 >        if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
121 >            if (minCapacity < 0)
122 >                throw new IllegalStateException("Sorry, deque too big");
123 >            return Integer.MAX_VALUE;
124          }
125 <        elements = (E[]) new Object[initialCapacity];
125 >        if (needed > jump)
126 >            return minCapacity;
127 >        return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
128 >            ? oldCapacity + jump
129 >            : MAX_ARRAY_SIZE;
130      }
131  
132      /**
133 <     * Double the capacity of this deque.  Call only when full, i.e.,
134 <     * when head and tail have wrapped around to become equal.
133 >     * Increases the internal storage of this collection, if necessary,
134 >     * to ensure that it can hold at least the given number of elements.
135 >     *
136 >     * @param minCapacity the desired minimum capacity
137 >     * @since TBD
138       */
139 <    private void doubleCapacity() {
140 <        assert head == tail;
141 <        int p = head;
142 <        int n = elements.length;
120 <        int r = n - p; // number of elements to the right of p
121 <        int newCapacity = n << 1;
122 <        if (newCapacity < 0)
123 <            throw new IllegalStateException("Sorry, deque too big");
124 <        Object[] a = new Object[newCapacity];
125 <        System.arraycopy(elements, p, a, 0, r);
126 <        System.arraycopy(elements, 0, a, r, p);
127 <        elements = (E[])a;
128 <        head = 0;
129 <        tail = n;
139 >    /* public */ void ensureCapacity(int minCapacity) {
140 >        if (minCapacity > elements.length)
141 >            grow(minCapacity - elements.length);
142 >        // checkInvariants();
143      }
144  
145      /**
146 <     * Copies the elements from our element array into the specified array,
134 <     * in order (from first to last element in the deque).  It is assumed
135 <     * that the array is large enough to hold all elements in the deque.
146 >     * Minimizes the internal storage of this collection.
147       *
148 <     * @return its argument
148 >     * @since TBD
149       */
150 <    private <T> T[] copyElements(T[] a) {
151 <        if (head < tail) {
152 <            System.arraycopy(elements, head, a, 0, size());
153 <        } else if (head > tail) {
143 <            int headPortionLen = elements.length - head;
144 <            System.arraycopy(elements, head, a, 0, headPortionLen);
145 <            System.arraycopy(elements, 0, a, headPortionLen, tail);
150 >    /* public */ void trimToSize() {
151 >        if (size < elements.length) {
152 >            elements = toArray();
153 >            head = 0;
154          }
155 <        return a;
155 >        // checkInvariants();
156      }
157  
158      /**
# Line 152 | Line 160 | public class ArrayDeque<E> extends Abstr
160       * sufficient to hold 16 elements.
161       */
162      public ArrayDeque() {
163 <        elements = (E[]) new Object[16];
163 >        elements = new Object[16];
164      }
165  
166      /**
167       * Constructs an empty array deque with an initial capacity
168       * sufficient to hold the specified number of elements.
169       *
170 <     * @param numElements  lower bound on initial capacity of the deque
170 >     * @param numElements lower bound on initial capacity of the deque
171       */
172      public ArrayDeque(int numElements) {
173 <        allocateElements(numElements);
173 >        elements = new Object[numElements];
174      }
175  
176      /**
# Line 176 | Line 184 | public class ArrayDeque<E> extends Abstr
184       * @throws NullPointerException if the specified collection is null
185       */
186      public ArrayDeque(Collection<? extends E> c) {
187 <        allocateElements(c.size());
188 <        addAll(c);
187 >        Object[] es = c.toArray();
188 >        // defend against c.toArray (incorrectly) not returning Object[]
189 >        // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
190 >        if (es.getClass() != Object[].class)
191 >            es = Arrays.copyOf(es, es.length, Object[].class);
192 >        for (Object obj : es)
193 >            Objects.requireNonNull(obj);
194 >        this.elements = es;
195 >        this.size = es.length;
196 >    }
197 >
198 >    /**
199 >     * Increments i, mod modulus.
200 >     * Precondition and postcondition: 0 <= i < modulus.
201 >     */
202 >    static final int inc(int i, int modulus) {
203 >        if (++i >= modulus) i = 0;
204 >        return i;
205 >    }
206 >
207 >    /**
208 >     * Decrements i, mod modulus.
209 >     * Precondition and postcondition: 0 <= i < modulus.
210 >     */
211 >    static final int dec(int i, int modulus) {
212 >        if (--i < 0) i = modulus - 1;
213 >        return i;
214 >    }
215 >
216 >    /**
217 >     * Adds i and j, mod modulus.
218 >     * Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
219 >     */
220 >    static final int add(int i, int j, int modulus) {
221 >        if ((i += j) - modulus >= 0) i -= modulus;
222 >        return i;
223 >    }
224 >
225 >    /**
226 >     * Returns the array index of the last element.
227 >     * May return invalid index -1 if there are no elements.
228 >     */
229 >    final int tail() {
230 >        return add(head, size - 1, elements.length);
231 >    }
232 >
233 >    /**
234 >     * Returns element at array index i.
235 >     */
236 >    @SuppressWarnings("unchecked")
237 >    private E elementAt(int i) {
238 >        return (E) elements[i];
239 >    }
240 >
241 >    /**
242 >     * A version of elementAt that checks for null elements.
243 >     * This check doesn't catch all possible comodifications,
244 >     * but does catch ones that corrupt traversal.  It's a little
245 >     * surprising that javac allows this abuse of generics.
246 >     */
247 >    static final <E> E nonNullElementAt(Object[] es, int i) {
248 >        @SuppressWarnings("unchecked") E e = (E) es[i];
249 >        if (e == null)
250 >            throw new ConcurrentModificationException();
251 >        return e;
252      }
253  
254      // The main insertion and extraction methods are addFirst,
# Line 187 | Line 258 | public class ArrayDeque<E> extends Abstr
258      /**
259       * Inserts the specified element at the front of this deque.
260       *
261 <     * @param e the element to insert
262 <     * @throws NullPointerException if <tt>e</tt> is null
261 >     * @param e the element to add
262 >     * @throws NullPointerException if the specified element is null
263       */
264      public void addFirst(E e) {
265 <        if (e == null)
266 <            throw new NullPointerException();
267 <        elements[head = (head - 1) & (elements.length - 1)] = e;
268 <        if (head == tail)
269 <            doubleCapacity();
265 >        // checkInvariants();
266 >        Objects.requireNonNull(e);
267 >        Object[] es;
268 >        int capacity, h;
269 >        final int s;
270 >        if ((s = size) == (capacity = (es = elements).length))
271 >            capacity = (es = grow(1)).length;
272 >        if ((h = head - 1) < 0) h = capacity - 1;
273 >        es[head = h] = e;
274 >        size = s + 1;
275 >        // checkInvariants();
276      }
277  
278      /**
279       * Inserts the specified element at the end of this deque.
203     * This method is equivalent to {@link Collection#add} and
204     * {@link #push}.
280       *
281 <     * @param e the element to insert
207 <     * @throws NullPointerException if <tt>e</tt> is null
208 <     */
209 <    public void addLast(E e) {
210 <        if (e == null)
211 <            throw new NullPointerException();
212 <        elements[tail] = e;
213 <        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
214 <            doubleCapacity();
215 <    }
216 <
217 <    /**
218 <     * Retrieves and removes the first element of this deque, or
219 <     * <tt>null</tt> if this deque is empty.
281 >     * <p>This method is equivalent to {@link #add}.
282       *
283 <     * @return the first element of this deque, or <tt>null</tt> if
284 <     *     this deque is empty
283 >     * @param e the element to add
284 >     * @throws NullPointerException if the specified element is null
285       */
286 <    public E pollFirst() {
287 <        int h = head;
288 <        E result = elements[h]; // Element is null if deque empty
289 <        if (result == null)
290 <            return null;
291 <        elements[h] = null;     // Must null out slot
292 <        head = (h + 1) & (elements.length - 1);
293 <        return result;
286 >    public void addLast(E e) {
287 >        // checkInvariants();
288 >        Objects.requireNonNull(e);
289 >        Object[] es;
290 >        int capacity;
291 >        final int s;
292 >        if ((s = size) == (capacity = (es = elements).length))
293 >            capacity = (es = grow(1)).length;
294 >        es[add(head, s, capacity)] = e;
295 >        size = s + 1;
296 >        // checkInvariants();
297      }
298  
299      /**
300 <     * Retrieves and removes the last element of this deque, or
301 <     * <tt>null</tt> if this deque is empty.
302 <     *
303 <     * @return the last element of this deque, or <tt>null</tt> if
304 <     *     this deque is empty
305 <     */
306 <    public E pollLast() {
307 <        int t = (tail - 1) & (elements.length - 1);
308 <        E result = elements[t];
309 <        if (result == null)
310 <            return null;
311 <        elements[t] = null;
312 <        tail = t;
313 <        return result;
300 >     * Adds all of the elements in the specified collection at the end
301 >     * of this deque, as if by calling {@link #addLast} on each one,
302 >     * in the order that they are returned by the collection's
303 >     * iterator.
304 >     *
305 >     * @param c the elements to be inserted into this deque
306 >     * @return {@code true} if this deque changed as a result of the call
307 >     * @throws NullPointerException if the specified collection or any
308 >     *         of its elements are null
309 >     */
310 >    public boolean addAll(Collection<? extends E> c) {
311 >        final int s = size, needed = c.size() - (elements.length - s);
312 >        if (needed > 0)
313 >            grow(needed);
314 >        c.forEach((e) -> addLast(e));
315 >        // checkInvariants();
316 >        return size > s;
317      }
318  
319      /**
320       * Inserts the specified element at the front of this deque.
321       *
322 <     * @param e the element to insert
323 <     * @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
324 <     * @throws NullPointerException if <tt>e</tt> is null
322 >     * @param e the element to add
323 >     * @return {@code true} (as specified by {@link Deque#offerFirst})
324 >     * @throws NullPointerException if the specified element is null
325       */
326      public boolean offerFirst(E e) {
327          addFirst(e);
# Line 263 | Line 331 | public class ArrayDeque<E> extends Abstr
331      /**
332       * Inserts the specified element at the end of this deque.
333       *
334 <     * @param e the element to insert
335 <     * @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
336 <     * @throws NullPointerException if <tt>e</tt> is null
334 >     * @param e the element to add
335 >     * @return {@code true} (as specified by {@link Deque#offerLast})
336 >     * @throws NullPointerException if the specified element is null
337       */
338      public boolean offerLast(E e) {
339          addLast(e);
# Line 273 | Line 341 | public class ArrayDeque<E> extends Abstr
341      }
342  
343      /**
344 <     * Retrieves and removes the first element of this deque.  This method
277 <     * differs from the <tt>pollFirst</tt> method in that it throws an
278 <     * exception if this deque is empty.
279 <     *
280 <     * @return the first element of this deque
281 <     * @throws NoSuchElementException if this deque is empty
344 >     * @throws NoSuchElementException {@inheritDoc}
345       */
346      public E removeFirst() {
347 <        E x = pollFirst();
348 <        if (x == null)
347 >        // checkInvariants();
348 >        E e = pollFirst();
349 >        if (e == null)
350              throw new NoSuchElementException();
351 <        return x;
351 >        return e;
352      }
353  
354      /**
355 <     * Retrieves and removes the last element of this deque.  This method
292 <     * differs from the <tt>pollLast</tt> method in that it throws an
293 <     * exception if this deque is empty.
294 <     *
295 <     * @return the last element of this deque
296 <     * @throws NoSuchElementException if this deque is empty
355 >     * @throws NoSuchElementException {@inheritDoc}
356       */
357      public E removeLast() {
358 <        E x = pollLast();
359 <        if (x == null)
358 >        // checkInvariants();
359 >        E e = pollLast();
360 >        if (e == null)
361              throw new NoSuchElementException();
362 <        return x;
362 >        return e;
363      }
364  
365 <    /**
366 <     * Retrieves, but does not remove, the first element of this deque,
367 <     * returning <tt>null</tt> if this deque is empty.
368 <     *
369 <     * @return the first element of this deque, or <tt>null</tt> if
370 <     *     this deque is empty
371 <     */
372 <    public E peekFirst() {
373 <        return elements[head]; // elements[head] is null if deque empty
365 >    public E pollFirst() {
366 >        // checkInvariants();
367 >        int s, h;
368 >        if ((s = size) <= 0)
369 >            return null;
370 >        final Object[] es = elements;
371 >        @SuppressWarnings("unchecked") E e = (E) es[h = head];
372 >        es[h] = null;
373 >        if (++h >= es.length) h = 0;
374 >        head = h;
375 >        size = s - 1;
376 >        return e;
377      }
378  
379 <    /**
380 <     * Retrieves, but does not remove, the last element of this deque,
381 <     * returning <tt>null</tt> if this deque is empty.
382 <     *
383 <     * @return the last element of this deque, or <tt>null</tt> if this deque
384 <     *     is empty
385 <     */
386 <    public E peekLast() {
387 <        return elements[(tail - 1) & (elements.length - 1)];
379 >    public E pollLast() {
380 >        // checkInvariants();
381 >        final int s, tail;
382 >        if ((s = size) <= 0)
383 >            return null;
384 >        final Object[] es = elements;
385 >        @SuppressWarnings("unchecked")
386 >        E e = (E) es[tail = add(head, s - 1, es.length)];
387 >        es[tail] = null;
388 >        size = s - 1;
389 >        return e;
390      }
391  
392      /**
393 <     * Retrieves, but does not remove, the first element of this
329 <     * deque.  This method differs from the <tt>peekFirst</tt> method only
330 <     * in that it throws an exception if this deque is empty.
331 <     *
332 <     * @return the first element of this deque
333 <     * @throws NoSuchElementException if this deque is empty
393 >     * @throws NoSuchElementException {@inheritDoc}
394       */
395      public E getFirst() {
396 <        E x = elements[head];
397 <        if (x == null)
398 <            throw new NoSuchElementException();
339 <        return x;
396 >        // checkInvariants();
397 >        if (size <= 0) throw new NoSuchElementException();
398 >        return elementAt(head);
399      }
400  
401      /**
402 <     * Retrieves, but does not remove, the last element of this
344 <     * deque.  This method differs from the <tt>peekLast</tt> method only
345 <     * in that it throws an exception if this deque is empty.
346 <     *
347 <     * @return the last element of this deque
348 <     * @throws NoSuchElementException if this deque is empty
402 >     * @throws NoSuchElementException {@inheritDoc}
403       */
404 +    @SuppressWarnings("unchecked")
405      public E getLast() {
406 <        E x = elements[(tail - 1) & (elements.length - 1)];
407 <        if (x == null)
408 <            throw new NoSuchElementException();
409 <        return x;
406 >        // checkInvariants();
407 >        final int s;
408 >        if ((s = size) <= 0) throw new NoSuchElementException();
409 >        final Object[] es = elements;
410 >        return (E) es[add(head, s - 1, es.length)];
411 >    }
412 >
413 >    public E peekFirst() {
414 >        // checkInvariants();
415 >        return (size <= 0) ? null : elementAt(head);
416 >    }
417 >
418 >    @SuppressWarnings("unchecked")
419 >    public E peekLast() {
420 >        // checkInvariants();
421 >        final int s;
422 >        if ((s = size) <= 0) return null;
423 >        final Object[] es = elements;
424 >        return (E) es[add(head, s - 1, es.length)];
425      }
426  
427      /**
428       * Removes the first occurrence of the specified element in this
429 <     * deque (when traversing the deque from head to tail).  More
430 <     * formally, removes the first element e such that (o==null ?
431 <     * e==null : o.equals(e)). If the deque does not contain the
432 <     * element, it is unchanged.
429 >     * deque (when traversing the deque from head to tail).
430 >     * If the deque does not contain the element, it is unchanged.
431 >     * More formally, removes the first element {@code e} such that
432 >     * {@code o.equals(e)} (if such an element exists).
433 >     * Returns {@code true} if this deque contained the specified element
434 >     * (or equivalently, if this deque changed as a result of the call).
435       *
436       * @param o element to be removed from this deque, if present
437 <     * @return <tt>true</tt> if the deque contained the specified element
437 >     * @return {@code true} if the deque contained the specified element
438       */
439      public boolean removeFirstOccurrence(Object o) {
440 <        if (o == null)
441 <            return false;
442 <        int mask = elements.length - 1;
443 <        int i = head;
444 <        E x;
445 <        while ( (x = elements[i]) != null) {
446 <            if (o.equals(x)) {
447 <                delete(i);
448 <                return true;
440 >        if (o != null) {
441 >            final Object[] es = elements;
442 >            int i, end, to, todo;
443 >            todo = (end = (i = head) + size)
444 >                - (to = (es.length - end >= 0) ? end : es.length);
445 >            for (;; to = todo, todo = 0, i = 0) {
446 >                for (; i < to; i++)
447 >                    if (o.equals(es[i])) {
448 >                        delete(i);
449 >                        return true;
450 >                    }
451 >                if (todo == 0) break;
452              }
378            i = (i + 1) & mask;
453          }
454          return false;
455      }
456  
457      /**
458       * Removes the last occurrence of the specified element in this
459 <     * deque (when traversing the deque from head to tail). More
460 <     * formally, removes the last element e such that (o==null ?
461 <     * e==null : o.equals(e)). If the deque
462 <     * does not contain the element, it is unchanged.
459 >     * deque (when traversing the deque from head to tail).
460 >     * If the deque does not contain the element, it is unchanged.
461 >     * More formally, removes the last element {@code e} such that
462 >     * {@code o.equals(e)} (if such an element exists).
463 >     * Returns {@code true} if this deque contained the specified element
464 >     * (or equivalently, if this deque changed as a result of the call).
465       *
466       * @param o element to be removed from this deque, if present
467 <     * @return <tt>true</tt> if the deque contained the specified element
467 >     * @return {@code true} if the deque contained the specified element
468       */
469      public boolean removeLastOccurrence(Object o) {
470 <        if (o == null)
471 <            return false;
472 <        int mask = elements.length - 1;
473 <        int i = (tail - 1) & mask;
474 <        E x;
475 <        while ( (x = elements[i]) != null) {
476 <            if (o.equals(x)) {
477 <                delete(i);
478 <                return true;
470 >        if (o != null) {
471 >            final Object[] es = elements;
472 >            int i, to, end, todo;
473 >            todo = (to = ((end = (i = tail()) - size) >= -1) ? end : -1) - end;
474 >            for (;; to = (i = es.length - 1) - todo, todo = 0) {
475 >                for (; i > to; i--)
476 >                    if (o.equals(es[i])) {
477 >                        delete(i);
478 >                        return true;
479 >                    }
480 >                if (todo == 0) break;
481              }
404            i = (i - 1) & mask;
482          }
483          return false;
484      }
# Line 411 | Line 488 | public class ArrayDeque<E> extends Abstr
488      /**
489       * Inserts the specified element at the end of this deque.
490       *
414     * <p>This method is equivalent to {@link #offerLast}.
415     *
416     * @param e the element to insert
417     * @return <tt>true</tt> (as per the spec for {@link Queue#offer})
418     * @throws NullPointerException if <tt>e</tt> is null
419     */
420    public boolean offer(E e) {
421        return offerLast(e);
422    }
423
424    /**
425     * Inserts the specified element at the end of this deque.
426     *
491       * <p>This method is equivalent to {@link #addLast}.
492       *
493 <     * @param e the element to insert
494 <     * @return <tt>true</tt> (as per the spec for {@link Collection#add})
495 <     * @throws NullPointerException if <tt>e</tt> is null
493 >     * @param e the element to add
494 >     * @return {@code true} (as specified by {@link Collection#add})
495 >     * @throws NullPointerException if the specified element is null
496       */
497      public boolean add(E e) {
498          addLast(e);
# Line 436 | Line 500 | public class ArrayDeque<E> extends Abstr
500      }
501  
502      /**
503 <     * Retrieves and removes the head of the queue represented by
440 <     * this deque, or <tt>null</tt> if this deque is empty.  In other words,
441 <     * retrieves and removes the first element of this deque, or <tt>null</tt>
442 <     * if this deque is empty.
503 >     * Inserts the specified element at the end of this deque.
504       *
505 <     * <p>This method is equivalent to {@link #pollFirst}.
505 >     * <p>This method is equivalent to {@link #offerLast}.
506       *
507 <     * @return the first element of this deque, or <tt>null</tt> if
508 <     *     this deque is empty
507 >     * @param e the element to add
508 >     * @return {@code true} (as specified by {@link Queue#offer})
509 >     * @throws NullPointerException if the specified element is null
510       */
511 <    public E poll() {
512 <        return pollFirst();
511 >    public boolean offer(E e) {
512 >        return offerLast(e);
513      }
514  
515      /**
516       * Retrieves and removes the head of the queue represented by this deque.
517 <     * This method differs from the <tt>poll</tt> method in that it throws an
517 >     *
518 >     * This method differs from {@link #poll poll} only in that it throws an
519       * exception if this deque is empty.
520       *
521       * <p>This method is equivalent to {@link #removeFirst}.
522       *
523       * @return the head of the queue represented by this deque
524 <     * @throws NoSuchElementException if this deque is empty
524 >     * @throws NoSuchElementException {@inheritDoc}
525       */
526      public E remove() {
527          return removeFirst();
528      }
529  
530      /**
531 <     * Retrieves, but does not remove, the head of the queue represented by
532 <     * this deque, returning <tt>null</tt> if this deque is empty.
531 >     * Retrieves and removes the head of the queue represented by this deque
532 >     * (in other words, the first element of this deque), or returns
533 >     * {@code null} if this deque is empty.
534       *
535 <     * <p>This method is equivalent to {@link #peekFirst}
535 >     * <p>This method is equivalent to {@link #pollFirst}.
536       *
537       * @return the head of the queue represented by this deque, or
538 <     *     <tt>null</tt> if this deque is empty
538 >     *         {@code null} if this deque is empty
539       */
540 <    public E peek() {
541 <        return peekFirst();
540 >    public E poll() {
541 >        return pollFirst();
542      }
543  
544      /**
545       * Retrieves, but does not remove, the head of the queue represented by
546 <     * this deque.  This method differs from the <tt>peek</tt> method only in
546 >     * this deque.  This method differs from {@link #peek peek} only in
547       * that it throws an exception if this deque is empty.
548       *
549 <     * <p>This method is equivalent to {@link #getFirst}
549 >     * <p>This method is equivalent to {@link #getFirst}.
550       *
551       * @return the head of the queue represented by this deque
552 <     * @throws NoSuchElementException if this deque is empty
552 >     * @throws NoSuchElementException {@inheritDoc}
553       */
554      public E element() {
555          return getFirst();
556      }
557  
558 +    /**
559 +     * Retrieves, but does not remove, the head of the queue represented by
560 +     * this deque, or returns {@code null} if this deque is empty.
561 +     *
562 +     * <p>This method is equivalent to {@link #peekFirst}.
563 +     *
564 +     * @return the head of the queue represented by this deque, or
565 +     *         {@code null} if this deque is empty
566 +     */
567 +    public E peek() {
568 +        return peekFirst();
569 +    }
570 +
571      // *** Stack methods ***
572  
573      /**
# Line 500 | Line 577 | public class ArrayDeque<E> extends Abstr
577       * <p>This method is equivalent to {@link #addFirst}.
578       *
579       * @param e the element to push
580 <     * @throws NullPointerException if <tt>e</tt> is null
580 >     * @throws NullPointerException if the specified element is null
581       */
582      public void push(E e) {
583          addFirst(e);
# Line 513 | Line 590 | public class ArrayDeque<E> extends Abstr
590       * <p>This method is equivalent to {@link #removeFirst()}.
591       *
592       * @return the element at the front of this deque (which is the top
593 <     *     of the stack represented by this deque)
594 <     * @throws NoSuchElementException if this deque is empty
593 >     *         of the stack represented by this deque)
594 >     * @throws NoSuchElementException {@inheritDoc}
595       */
596      public E pop() {
597          return removeFirst();
598      }
599  
600      /**
601 <     * Removes the element at the specified position in the elements array,
602 <     * adjusting head, tail, and size as necessary.  This can result in
603 <     * motion of elements backwards or forwards in the array.
601 >     * Removes the element at the specified position in the elements array.
602 >     * This can result in forward or backwards motion of array elements.
603 >     * We optimize for least element motion.
604       *
605       * <p>This method is called delete rather than remove to emphasize
606 <     * that its semantics differ from those of List.remove(int).
606 >     * that its semantics differ from those of {@link List#remove(int)}.
607       *
608       * @return true if elements moved backwards
609       */
610 <    private boolean delete(int i) {
611 <        // Case 1: Deque doesn't wrap
612 <        // Case 2: Deque does wrap and removed element is in the head portion
613 <        if ((head < tail || tail == 0) || i >= head) {
614 <            System.arraycopy(elements, head, elements, head + 1, i - head);
615 <            elements[head] = null;
616 <            head = (head + 1) & (elements.length - 1);
610 >    boolean delete(int i) {
611 >        // checkInvariants();
612 >        final Object[] es = elements;
613 >        final int capacity = es.length;
614 >        final int h = head;
615 >        int front;              // number of elements before to-be-deleted elt
616 >        if ((front = i - h) < 0) front += capacity;
617 >        final int back = size - front - 1; // number of elements after
618 >        if (front < back) {
619 >            // move front elements forwards
620 >            if (h <= i) {
621 >                System.arraycopy(es, h, es, h + 1, front);
622 >            } else { // Wrap around
623 >                System.arraycopy(es, 0, es, 1, i);
624 >                es[0] = es[capacity - 1];
625 >                System.arraycopy(es, h, es, h + 1, front - (i + 1));
626 >            }
627 >            es[h] = null;
628 >            if ((head = (h + 1)) >= capacity) head = 0;
629 >            size--;
630 >            // checkInvariants();
631              return false;
632 +        } else {
633 +            // move back elements backwards
634 +            int tail = tail();
635 +            if (i <= tail) {
636 +                System.arraycopy(es, i + 1, es, i, back);
637 +            } else { // Wrap around
638 +                int firstLeg = capacity - (i + 1);
639 +                System.arraycopy(es, i + 1, es, i, firstLeg);
640 +                es[capacity - 1] = es[0];
641 +                System.arraycopy(es, 1, es, 0, back - firstLeg - 1);
642 +            }
643 +            es[tail] = null;
644 +            size--;
645 +            // checkInvariants();
646 +            return true;
647          }
542
543        // Case 3: Deque wraps and removed element is in the tail portion
544        tail--;
545        System.arraycopy(elements, i + 1, elements, i, tail - i);
546        elements[tail] = null;
547        return true;
648      }
649  
650      // *** Collection Methods ***
# Line 555 | Line 655 | public class ArrayDeque<E> extends Abstr
655       * @return the number of elements in this deque
656       */
657      public int size() {
658 <        return (tail - head) & (elements.length - 1);
658 >        return size;
659      }
660  
661      /**
662 <     * Returns <tt>true</tt> if this deque contains no elements.<p>
662 >     * Returns {@code true} if this deque contains no elements.
663       *
664 <     * @return <tt>true</tt> if this deque contains no elements.
664 >     * @return {@code true} if this deque contains no elements
665       */
666      public boolean isEmpty() {
667 <        return head == tail;
667 >        return size == 0;
668      }
669  
670      /**
# Line 573 | Line 673 | public class ArrayDeque<E> extends Abstr
673       * order that elements would be dequeued (via successive calls to
674       * {@link #remove} or popped (via successive calls to {@link #pop}).
675       *
676 <     * @return an <tt>Iterator</tt> over the elements in this deque
676 >     * @return an iterator over the elements in this deque
677       */
678      public Iterator<E> iterator() {
679          return new DeqIterator();
680      }
681  
682 +    public Iterator<E> descendingIterator() {
683 +        return new DescendingIterator();
684 +    }
685 +
686      private class DeqIterator implements Iterator<E> {
687 <        /**
688 <         * Index of element to be returned by subsequent call to next.
585 <         */
586 <        private int cursor = head;
687 >        /** Index of element to be returned by subsequent call to next. */
688 >        int cursor;
689  
690 <        /**
691 <         * Tail recorded at construction (also in remove), to stop
590 <         * iterator and also to check for comodification.
591 <         */
592 <        private int fence = tail;
690 >        /** Number of elements yet to be returned. */
691 >        int remaining = size;
692  
693          /**
694           * Index of element returned by most recent call to next.
695           * Reset to -1 if element is deleted by a call to remove.
696           */
697 <        private int lastRet = -1;
697 >        int lastRet = -1;
698 >
699 >        DeqIterator() { cursor = head; }
700  
701 <        public boolean hasNext() {
702 <            return cursor != fence;
701 >        public final boolean hasNext() {
702 >            return remaining > 0;
703          }
704  
705          public E next() {
706 <            E result;
606 <            if (cursor == fence)
706 >            if (remaining <= 0)
707                  throw new NoSuchElementException();
708 <            // This check doesn't catch all possible comodifications,
709 <            // but does catch the ones that corrupt traversal
610 <            if (tail != fence || (result = elements[cursor]) == null)
611 <                throw new ConcurrentModificationException();
708 >            final Object[] es = elements;
709 >            E e = nonNullElementAt(es, cursor);
710              lastRet = cursor;
711 <            cursor = (cursor + 1) & (elements.length - 1);
712 <            return result;
711 >            if (++cursor >= es.length) cursor = 0;
712 >            remaining--;
713 >            return e;
714          }
715  
716 <        public void remove() {
716 >        void postDelete(boolean leftShifted) {
717 >            if (leftShifted)
718 >                if (--cursor < 0) cursor = elements.length - 1;
719 >        }
720 >
721 >        public final void remove() {
722              if (lastRet < 0)
723                  throw new IllegalStateException();
724 <            if (delete(lastRet))
621 <                cursor--;
724 >            postDelete(delete(lastRet));
725              lastRet = -1;
726 <            fence = tail;
726 >        }
727 >
728 >        public void forEachRemaining(Consumer<? super E> action) {
729 >            Objects.requireNonNull(action);
730 >            final int k;
731 >            if ((k = remaining) > 0) {
732 >                remaining = 0;
733 >                ArrayDeque.forEachRemaining(action, elements, cursor, k);
734 >                if ((lastRet = cursor + k - 1) >= elements.length)
735 >                    lastRet -= elements.length;
736 >            }
737 >        }
738 >    }
739 >
740 >    private class DescendingIterator extends DeqIterator {
741 >        DescendingIterator() { cursor = tail(); }
742 >
743 >        public final E next() {
744 >            if (remaining <= 0)
745 >                throw new NoSuchElementException();
746 >            final Object[] es = elements;
747 >            E e = nonNullElementAt(es, cursor);
748 >            lastRet = cursor;
749 >            if (--cursor < 0) cursor = es.length - 1;
750 >            remaining--;
751 >            return e;
752 >        }
753 >
754 >        void postDelete(boolean leftShifted) {
755 >            if (!leftShifted)
756 >                if (++cursor >= elements.length) cursor = 0;
757 >        }
758 >
759 >        public final void forEachRemaining(Consumer<? super E> action) {
760 >            Objects.requireNonNull(action);
761 >            final int k;
762 >            if ((k = remaining) > 0) {
763 >                remaining = 0;
764 >                final Object[] es = elements;
765 >                int i, end, to, todo;
766 >                todo = (to = ((end = (i = cursor) - k) >= -1) ? end : -1) - end;
767 >                for (;; to = (i = es.length - 1) - todo, todo = 0) {
768 >                    for (; i > to; i--)
769 >                        action.accept(nonNullElementAt(es, i));
770 >                    if (todo == 0) break;
771 >                }
772 >                if ((lastRet = cursor - (k - 1)) < 0)
773 >                    lastRet += es.length;
774 >            }
775 >        }
776 >    }
777 >
778 >    /**
779 >     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
780 >     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
781 >     * deque.
782 >     *
783 >     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
784 >     * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
785 >     * {@link Spliterator#NONNULL}.  Overriding implementations should document
786 >     * the reporting of additional characteristic values.
787 >     *
788 >     * @return a {@code Spliterator} over the elements in this deque
789 >     * @since 1.8
790 >     */
791 >    public Spliterator<E> spliterator() {
792 >        return new ArrayDequeSpliterator();
793 >    }
794 >
795 >    final class ArrayDequeSpliterator implements Spliterator<E> {
796 >        private int cursor;
797 >        private int remaining; // -1 until late-binding first use
798 >
799 >        /** Constructs late-binding spliterator over all elements. */
800 >        ArrayDequeSpliterator() {
801 >            this.remaining = -1;
802 >        }
803 >
804 >        /** Constructs spliterator over the given slice. */
805 >        ArrayDequeSpliterator(int cursor, int count) {
806 >            this.cursor = cursor;
807 >            this.remaining = count;
808 >        }
809 >
810 >        /** Ensures late-binding initialization; then returns remaining. */
811 >        private int remaining() {
812 >            if (remaining < 0) {
813 >                cursor = head;
814 >                remaining = size;
815 >            }
816 >            return remaining;
817 >        }
818 >
819 >        public ArrayDequeSpliterator trySplit() {
820 >            final int mid;
821 >            if ((mid = remaining() >> 1) > 0) {
822 >                int oldCursor = cursor;
823 >                cursor = add(cursor, mid, elements.length);
824 >                remaining -= mid;
825 >                return new ArrayDequeSpliterator(oldCursor, mid);
826 >            }
827 >            return null;
828 >        }
829 >
830 >        public void forEachRemaining(Consumer<? super E> action) {
831 >            Objects.requireNonNull(action);
832 >            final int k = remaining(); // side effect!
833 >            remaining = 0;
834 >            ArrayDeque.forEachRemaining(action, elements, cursor, k);
835 >        }
836 >
837 >        public boolean tryAdvance(Consumer<? super E> action) {
838 >            Objects.requireNonNull(action);
839 >            final int k;
840 >            if ((k = remaining()) <= 0)
841 >                return false;
842 >            action.accept(nonNullElementAt(elements, cursor));
843 >            if (++cursor >= elements.length) cursor = 0;
844 >            remaining = k - 1;
845 >            return true;
846 >        }
847 >
848 >        public long estimateSize() {
849 >            return remaining();
850 >        }
851 >
852 >        public int characteristics() {
853 >            return Spliterator.NONNULL
854 >                | Spliterator.ORDERED
855 >                | Spliterator.SIZED
856 >                | Spliterator.SUBSIZED;
857 >        }
858 >    }
859 >
860 >    @SuppressWarnings("unchecked")
861 >    public void forEach(Consumer<? super E> action) {
862 >        Objects.requireNonNull(action);
863 >        final Object[] es = elements;
864 >        int i, end, to, todo;
865 >        todo = (end = (i = head) + size)
866 >            - (to = (es.length - end >= 0) ? end : es.length);
867 >        for (;; to = todo, todo = 0, i = 0) {
868 >            for (; i < to; i++)
869 >                action.accept((E) es[i]);
870 >            if (todo == 0) break;
871 >        }
872 >        // checkInvariants();
873 >    }
874 >
875 >    /**
876 >     * Calls action on remaining elements, starting at index i and
877 >     * traversing in ascending order.  A variant of forEach that also
878 >     * checks for concurrent modification, for use in iterators.
879 >     */
880 >    static <E> void forEachRemaining(
881 >        Consumer<? super E> action, Object[] es, int i, int remaining) {
882 >        int end, to, todo;
883 >        todo = (end = i + remaining)
884 >            - (to = (es.length - end >= 0) ? end : es.length);
885 >        for (;; to = todo, todo = 0, i = 0) {
886 >            for (; i < to; i++)
887 >                action.accept(nonNullElementAt(es, i));
888 >            if (todo == 0) break;
889          }
890      }
891  
892      /**
893 <     * Returns <tt>true</tt> if this deque contains the specified
894 <     * element.  More formally, returns <tt>true</tt> if and only if this
895 <     * deque contains at least one element <tt>e</tt> such that
896 <     * <tt>e.equals(o)</tt>.
893 >     * Replaces each element of this deque with the result of applying the
894 >     * operator to that element, as specified by {@link List#replaceAll}.
895 >     *
896 >     * @param operator the operator to apply to each element
897 >     * @since TBD
898 >     */
899 >    @SuppressWarnings("unchecked")
900 >    /* public */ void replaceAll(UnaryOperator<E> operator) {
901 >        Objects.requireNonNull(operator);
902 >        final Object[] es = elements;
903 >        int i, end, to, todo;
904 >        todo = (end = (i = head) + size)
905 >            - (to = (es.length - end >= 0) ? end : es.length);
906 >        for (;; to = todo, todo = 0, i = 0) {
907 >            for (; i < to; i++)
908 >                es[i] = operator.apply((E) es[i]);
909 >            if (todo == 0) break;
910 >        }
911 >        // checkInvariants();
912 >    }
913 >
914 >    /**
915 >     * @throws NullPointerException {@inheritDoc}
916 >     */
917 >    public boolean removeIf(Predicate<? super E> filter) {
918 >        Objects.requireNonNull(filter);
919 >        return bulkRemove(filter);
920 >    }
921 >
922 >    /**
923 >     * @throws NullPointerException {@inheritDoc}
924 >     */
925 >    public boolean removeAll(Collection<?> c) {
926 >        Objects.requireNonNull(c);
927 >        return bulkRemove(e -> c.contains(e));
928 >    }
929 >
930 >    /**
931 >     * @throws NullPointerException {@inheritDoc}
932 >     */
933 >    public boolean retainAll(Collection<?> c) {
934 >        Objects.requireNonNull(c);
935 >        return bulkRemove(e -> !c.contains(e));
936 >    }
937 >
938 >    /** Implementation of bulk remove methods. */
939 >    @SuppressWarnings("unchecked")
940 >    private boolean bulkRemove(Predicate<? super E> filter) {
941 >        // checkInvariants();
942 >        final Object[] es = elements;
943 >        int i, end, to, todo;
944 >        todo = (end = (i = head) + size)
945 >            - (to = (es.length - end >= 0) ? end : es.length);
946 >        // Optimize for initial run of non-removed elements
947 >        findFirstRemoved:
948 >        for (;; to = todo, todo = 0, i = 0) {
949 >            for (; i < to; i++)
950 >                if (filter.test((E) es[i]))
951 >                    break findFirstRemoved;
952 >            if (todo == 0) return false;
953 >        }
954 >        bulkRemoveModified(filter, i, to, todo);
955 >        return true;
956 >    }
957 >
958 >    /**
959 >     * Helper for bulkRemove, in case of at least one deletion.
960 >     * @param i valid index of first element to be deleted
961 >     */
962 >    @SuppressWarnings("unchecked")
963 >    private void bulkRemoveModified(
964 >        Predicate<? super E> filter, int i, int to, int todo) {
965 >        final Object[] es = elements;
966 >        final int capacity = es.length;
967 >        // a two-finger algorithm, with hare i and tortoise j
968 >        int j = i++;
969 >        try {
970 >            for (;;) {
971 >                E e;
972 >                // In this loop, i and j are on the same leg, with i > j
973 >                for (; i < to; i++)
974 >                    if (!filter.test(e = (E) es[i]))
975 >                        es[j++] = e;
976 >                if (todo == 0) break;
977 >                // In this loop, j is on the first leg, i on the second
978 >                for (to = todo, todo = 0, i = 0; i < to && j < capacity; i++)
979 >                    if (!filter.test(e = (E) es[i]))
980 >                        es[j++] = e;
981 >                if (i >= to) break;
982 >                j = 0;          // j rejoins i on second leg
983 >            }
984 >            bulkRemoveClear(es, j, i);
985 >            // checkInvariants();
986 >        } catch (Throwable ex) {
987 >            // copy remaining elements
988 >            for (int remaining = (to - i) + todo; --remaining >= 0;) {
989 >                es[j] = es[i];
990 >                if (++i >= capacity) i = 0;
991 >                if (++j >= capacity) j = 0;
992 >            }
993 >            bulkRemoveClear(es, j, i);
994 >            // checkInvariants();
995 >            throw ex;
996 >        }
997 >    }
998 >
999 >    /**
1000 >     * Nulls out all elements from index j upto index i.
1001 >     */
1002 >    private void bulkRemoveClear(Object[] es, int j, int i) {
1003 >        int deleted;
1004 >        if ((deleted = i - j) <= 0) deleted += es.length;
1005 >        size -= deleted;
1006 >        circularClear(es, j, deleted);
1007 >    }
1008 >
1009 >    /**
1010 >     * Returns {@code true} if this deque contains the specified element.
1011 >     * More formally, returns {@code true} if and only if this deque contains
1012 >     * at least one element {@code e} such that {@code o.equals(e)}.
1013       *
1014       * @param o object to be checked for containment in this deque
1015 <     * @return <tt>true</tt> if this deque contains the specified element
1015 >     * @return {@code true} if this deque contains the specified element
1016       */
1017      public boolean contains(Object o) {
1018 <        if (o == null)
1019 <            return false;
1020 <        int mask = elements.length - 1;
1021 <        int i = head;
1022 <        E x;
1023 <        while ( (x = elements[i]) != null) {
1024 <            if (o.equals(x))
1025 <                return true;
1026 <            i = (i + 1) & mask;
1018 >        if (o != null) {
1019 >            final Object[] es = elements;
1020 >            int i, end, to, todo;
1021 >            todo = (end = (i = head) + size)
1022 >                - (to = (es.length - end >= 0) ? end : es.length);
1023 >            for (;; to = todo, todo = 0, i = 0) {
1024 >                for (; i < to; i++)
1025 >                    if (o.equals(es[i]))
1026 >                        return true;
1027 >                if (todo == 0) break;
1028 >            }
1029          }
1030          return false;
1031      }
1032  
1033      /**
1034       * Removes a single instance of the specified element from this deque.
1035 <     * This method is equivalent to {@link #removeFirstOccurrence}.
1035 >     * If the deque does not contain the element, it is unchanged.
1036 >     * More formally, removes the first element {@code e} such that
1037 >     * {@code o.equals(e)} (if such an element exists).
1038 >     * Returns {@code true} if this deque contained the specified element
1039 >     * (or equivalently, if this deque changed as a result of the call).
1040       *
1041 <     * @param e element to be removed from this deque, if present
1042 <     * @return <tt>true</tt> if this deque contained the specified element
1041 >     * <p>This method is equivalent to {@link #removeFirstOccurrence(Object)}.
1042 >     *
1043 >     * @param o element to be removed from this deque, if present
1044 >     * @return {@code true} if this deque contained the specified element
1045       */
1046 <    public boolean remove(Object e) {
1047 <        return removeFirstOccurrence(e);
1046 >    public boolean remove(Object o) {
1047 >        return removeFirstOccurrence(o);
1048      }
1049  
1050      /**
# Line 663 | Line 1052 | public class ArrayDeque<E> extends Abstr
1052       * The deque will be empty after this call returns.
1053       */
1054      public void clear() {
1055 <        int h = head;
1056 <        int t = tail;
1057 <        if (h != t) { // clear all cells
1058 <            head = tail = 0;
1059 <            int i = h;
1060 <            int mask = elements.length - 1;
1061 <            do {
1062 <                elements[i] = null;
1063 <                i = (i + 1) & mask;
1064 <            } while(i != t);
1055 >        circularClear(elements, head, size);
1056 >        size = head = 0;
1057 >        // checkInvariants();
1058 >    }
1059 >
1060 >    /**
1061 >     * Nulls out count elements, starting at array index from.
1062 >     * Special case (from == es.length) is treated the same as (from == 0).
1063 >     */
1064 >    private static void circularClear(Object[] es, int from, int count) {
1065 >        int end, to, todo;
1066 >        todo = (end = from + count)
1067 >            - (to = (es.length - end >= 0) ? end : es.length);
1068 >        for (;; to = todo, todo = 0, from = 0) {
1069 >            Arrays.fill(es, from, to, null);
1070 >            if (todo == 0) break;
1071          }
1072      }
1073  
1074      /**
1075       * Returns an array containing all of the elements in this deque
1076 <     * in the correct order.
1076 >     * in proper sequence (from first to last element).
1077 >     *
1078 >     * <p>The returned array will be "safe" in that no references to it are
1079 >     * maintained by this deque.  (In other words, this method must allocate
1080 >     * a new array).  The caller is thus free to modify the returned array.
1081 >     *
1082 >     * <p>This method acts as bridge between array-based and collection-based
1083 >     * APIs.
1084       *
1085       * @return an array containing all of the elements in this deque
684     *         in the correct order
1086       */
1087      public Object[] toArray() {
1088 <        return copyElements(new Object[size()]);
1088 >        return toArray(Object[].class);
1089 >    }
1090 >
1091 >    private <T> T[] toArray(Class<T[]> klazz) {
1092 >        final Object[] es = elements;
1093 >        final T[] a;
1094 >        final int head, len, end, todo;
1095 >        todo = size - (len = Math.min(size, es.length - (head = this.head)));
1096 >        if ((end = head + size) >= 0) {
1097 >            a = Arrays.copyOfRange(es, head, end, klazz);
1098 >        } else {
1099 >            // integer overflow!
1100 >            a = Arrays.copyOfRange(es, 0, size, klazz);
1101 >            System.arraycopy(es, head, a, 0, len);
1102 >        }
1103 >        if (todo > 0)
1104 >            System.arraycopy(es, 0, a, len, todo);
1105 >        return a;
1106      }
1107  
1108      /**
1109 <     * Returns an array containing all of the elements in this deque in the
1110 <     * correct order; the runtime type of the returned array is that of the
1111 <     * specified array.  If the deque fits in the specified array, it is
1112 <     * returned therein.  Otherwise, a new array is allocated with the runtime
1113 <     * type of the specified array and the size of this deque.
1109 >     * Returns an array containing all of the elements in this deque in
1110 >     * proper sequence (from first to last element); the runtime type of the
1111 >     * returned array is that of the specified array.  If the deque fits in
1112 >     * the specified array, it is returned therein.  Otherwise, a new array
1113 >     * is allocated with the runtime type of the specified array and the
1114 >     * size of this deque.
1115 >     *
1116 >     * <p>If this deque fits in the specified array with room to spare
1117 >     * (i.e., the array has more elements than this deque), the element in
1118 >     * the array immediately following the end of the deque is set to
1119 >     * {@code null}.
1120 >     *
1121 >     * <p>Like the {@link #toArray()} method, this method acts as bridge between
1122 >     * array-based and collection-based APIs.  Further, this method allows
1123 >     * precise control over the runtime type of the output array, and may,
1124 >     * under certain circumstances, be used to save allocation costs.
1125 >     *
1126 >     * <p>Suppose {@code x} is a deque known to contain only strings.
1127 >     * The following code can be used to dump the deque into a newly
1128 >     * allocated array of {@code String}:
1129       *
1130 <     * <p>If the deque fits in the specified array with room to spare (i.e.,
1131 <     * the array has more elements than the deque), the element in the array
1132 <     * immediately following the end of the collection is set to <tt>null</tt>.
1130 >     * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
1131 >     *
1132 >     * Note that {@code toArray(new Object[0])} is identical in function to
1133 >     * {@code toArray()}.
1134       *
1135       * @param a the array into which the elements of the deque are to
1136 <     *          be stored, if it is big enough; otherwise, a new array of the
1137 <     *          same runtime type is allocated for this purpose
1138 <     * @return an array containing the elements of the deque
1139 <     * @throws ArrayStoreException if the runtime type of a is not a supertype
1140 <     *         of the runtime type of every element in this deque
1136 >     *          be stored, if it is big enough; otherwise, a new array of the
1137 >     *          same runtime type is allocated for this purpose
1138 >     * @return an array containing all of the elements in this deque
1139 >     * @throws ArrayStoreException if the runtime type of the specified array
1140 >     *         is not a supertype of the runtime type of every element in
1141 >     *         this deque
1142 >     * @throws NullPointerException if the specified array is null
1143       */
1144 +    @SuppressWarnings("unchecked")
1145      public <T> T[] toArray(T[] a) {
1146 <        int size = size();
1147 <        if (a.length < size)
1148 <            a = (T[])java.lang.reflect.Array.newInstance(
1149 <                    a.getClass().getComponentType(), size);
1150 <        copyElements(a);
1151 <        if (a.length > size)
1146 >        final int size;
1147 >        if ((size = this.size) > a.length)
1148 >            return toArray((Class<T[]>) a.getClass());
1149 >        final Object[] es = elements;
1150 >        int i, j, len, todo;
1151 >        todo = size - (len = Math.min(size, es.length - (i = head)));
1152 >        for (j = 0;; j += len, len = todo, todo = 0, i = 0) {
1153 >            System.arraycopy(es, i, a, j, len);
1154 >            if (todo == 0) break;
1155 >        }
1156 >        if (size < a.length)
1157              a[size] = null;
1158          return a;
1159      }
# Line 725 | Line 1167 | public class ArrayDeque<E> extends Abstr
1167       */
1168      public ArrayDeque<E> clone() {
1169          try {
1170 +            @SuppressWarnings("unchecked")
1171              ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
1172 <            // These two lines are currently faster than cloning the array:
730 <            result.elements = (E[]) new Object[elements.length];
731 <            System.arraycopy(elements, 0, result.elements, 0, elements.length);
1172 >            result.elements = Arrays.copyOf(elements, elements.length);
1173              return result;
733
1174          } catch (CloneNotSupportedException e) {
1175              throw new AssertionError();
1176          }
1177      }
1178  
739    /**
740     * Appease the serialization gods.
741     */
1179      private static final long serialVersionUID = 2340985798034038923L;
1180  
1181      /**
1182 <     * Serialize this deque.
1182 >     * Saves this deque to a stream (that is, serializes it).
1183       *
1184 <     * @serialData The current size (<tt>int</tt>) of the deque,
1184 >     * @param s the stream
1185 >     * @throws java.io.IOException if an I/O error occurs
1186 >     * @serialData The current size ({@code int}) of the deque,
1187       * followed by all of its elements (each an object reference) in
1188       * first-to-last order.
1189       */
1190 <    private void writeObject(ObjectOutputStream s) throws IOException {
1190 >    private void writeObject(java.io.ObjectOutputStream s)
1191 >            throws java.io.IOException {
1192          s.defaultWriteObject();
1193  
1194          // Write out size
755        int size = size();
1195          s.writeInt(size);
1196  
1197          // Write out elements in order.
1198 <        int i = head;
1199 <        int mask = elements.length - 1;
1200 <        for (int j = 0; j < size; j++) {
1201 <            s.writeObject(elements[i]);
1202 <            i = (i + 1) & mask;
1198 >        final Object[] es = elements;
1199 >        int i, end, to, todo;
1200 >        todo = (end = (i = head) + size)
1201 >            - (to = (es.length - end >= 0) ? end : es.length);
1202 >        for (;; to = todo, todo = 0, i = 0) {
1203 >            for (; i < to; i++)
1204 >                s.writeObject(es[i]);
1205 >            if (todo == 0) break;
1206          }
1207      }
1208  
1209      /**
1210 <     * Deserialize this deque.
1210 >     * Reconstitutes this deque from a stream (that is, deserializes it).
1211 >     * @param s the stream
1212 >     * @throws ClassNotFoundException if the class of a serialized object
1213 >     *         could not be found
1214 >     * @throws java.io.IOException if an I/O error occurs
1215       */
1216 <    private void readObject(ObjectInputStream s)
1217 <            throws IOException, ClassNotFoundException {
1216 >    private void readObject(java.io.ObjectInputStream s)
1217 >            throws java.io.IOException, ClassNotFoundException {
1218          s.defaultReadObject();
1219  
1220          // Read in size and allocate array
1221 <        int size = s.readInt();
776 <        allocateElements(size);
777 <        head = 0;
778 <        tail = size;
1221 >        elements = new Object[size = s.readInt()];
1222  
1223          // Read in all elements in the proper order.
1224          for (int i = 0; i < size; i++)
1225 <            elements[i] = (E)s.readObject();
1225 >            elements[i] = s.readObject();
1226 >    }
1227  
1228 +    /** debugging */
1229 +    void checkInvariants() {
1230 +        try {
1231 +            int capacity = elements.length;
1232 +            // assert size >= 0 && size <= capacity;
1233 +            // assert head >= 0;
1234 +            // assert capacity == 0 || head < capacity;
1235 +            // assert size == 0 || elements[head] != null;
1236 +            // assert size == 0 || elements[tail()] != null;
1237 +            // assert size == capacity || elements[dec(head, capacity)] == null;
1238 +            // assert size == capacity || elements[inc(tail(), capacity)] == null;
1239 +        } catch (Throwable t) {
1240 +            System.err.printf("head=%d size=%d capacity=%d%n",
1241 +                              head, size, elements.length);
1242 +            System.err.printf("elements=%s%n",
1243 +                              Arrays.toString(elements));
1244 +            throw t;
1245 +        }
1246      }
1247 +
1248   }

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines