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.53 by dl, Wed Mar 13 12:38:56 2013 UTC vs.
Revision 1.102 by jsr166, Sun Oct 30 20:10:34 2016 UTC

# Line 4 | Line 4
4   */
5  
6   package java.util;
7 +
8   import java.io.Serializable;
9   import java.util.function.Consumer;
10 < import java.util.stream.Stream;
11 < import java.util.stream.Streams;
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 53 | Line 54 | import java.util.stream.Streams;
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
57 * @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
66 <     * full, except transiently within an addX method where it is
67 <     * resized (see doubleCapacity) immediately upon becoming full,
68 <     * thus avoiding head and tail wrapping around to equal each
69 <     * other.  We also guarantee that all array cells not holding
70 <     * deque elements are always null.
65 >     * We guarantee that all array cells not holding deque elements
66 >     * are always null.
67       */
68 <    transient Object[] elements; // non-private to simplify nested class access
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.
73 >     * arbitrary number 0 <= head < elements.length if the deque is empty.
74       */
75      transient int head;
76  
77 +    /** Number of elements in this collection. */
78 +    transient int size;
79 +
80      /**
81 <     * The index at which the next element would be added to the tail
82 <     * of the deque (via addLast(E), add(E), or push(E)).
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 <    transient int tail;
86 >    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
87  
88      /**
89 <     * The minimum capacity that we'll use for a newly created deque.
90 <     * Must be a power of 2.
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 static final int MIN_INITIAL_CAPACITY = 8;
93 >    private void 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 >        // checkInvariants();
114 >    }
115  
116 <    // ******  Array allocation and resizing utilities ******
116 >    /** Capacity calculation for edge conditions, especially overflow. */
117 >    private int newCapacity(int needed, int jump) {
118 >        final int oldCapacity = elements.length, minCapacity;
119 >        if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
120 >            if (minCapacity < 0)
121 >                throw new IllegalStateException("Sorry, deque too big");
122 >            return Integer.MAX_VALUE;
123 >        }
124 >        if (needed > jump)
125 >            return minCapacity;
126 >        return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
127 >            ? oldCapacity + jump
128 >            : MAX_ARRAY_SIZE;
129 >    }
130  
131      /**
132 <     * Allocates empty array to hold the given number of elements.
132 >     * Increases the internal storage of this collection, if necessary,
133 >     * to ensure that it can hold at least the given number of elements.
134       *
135 <     * @param numElements  the number of elements to hold
135 >     * @param minCapacity the desired minimum capacity
136 >     * @since TBD
137       */
138 <    private void allocateElements(int numElements) {
139 <        int initialCapacity = MIN_INITIAL_CAPACITY;
140 <        // Find the best power of two to hold elements.
141 <        // Tests "<=" because arrays aren't kept full.
104 <        if (numElements >= initialCapacity) {
105 <            initialCapacity = numElements;
106 <            initialCapacity |= (initialCapacity >>>  1);
107 <            initialCapacity |= (initialCapacity >>>  2);
108 <            initialCapacity |= (initialCapacity >>>  4);
109 <            initialCapacity |= (initialCapacity >>>  8);
110 <            initialCapacity |= (initialCapacity >>> 16);
111 <            initialCapacity++;
112 <
113 <            if (initialCapacity < 0)   // Too many elements, must back off
114 <                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
115 <        }
116 <        elements = new Object[initialCapacity];
138 >    /* public */ void ensureCapacity(int minCapacity) {
139 >        if (minCapacity > elements.length)
140 >            grow(minCapacity - elements.length);
141 >        // checkInvariants();
142      }
143  
144      /**
145 <     * Doubles the capacity of this deque.  Call only when full, i.e.,
146 <     * when head and tail have wrapped around to become equal.
145 >     * Minimizes the internal storage of this collection.
146 >     *
147 >     * @since TBD
148       */
149 <    private void doubleCapacity() {
150 <        assert head == tail;
151 <        int p = head;
152 <        int n = elements.length;
153 <        int r = n - p; // number of elements to the right of p
154 <        int newCapacity = n << 1;
129 <        if (newCapacity < 0)
130 <            throw new IllegalStateException("Sorry, deque too big");
131 <        Object[] a = new Object[newCapacity];
132 <        System.arraycopy(elements, p, a, 0, r);
133 <        System.arraycopy(elements, 0, a, r, p);
134 <        elements = a;
135 <        head = 0;
136 <        tail = n;
149 >    /* public */ void trimToSize() {
150 >        if (size < elements.length) {
151 >            elements = toArray();
152 >            head = 0;
153 >        }
154 >        // checkInvariants();
155      }
156  
157      /**
# Line 148 | Line 166 | public class ArrayDeque<E> extends Abstr
166       * Constructs an empty array deque with an initial capacity
167       * sufficient to hold the specified number of elements.
168       *
169 <     * @param numElements  lower bound on initial capacity of the deque
169 >     * @param numElements lower bound on initial capacity of the deque
170       */
171      public ArrayDeque(int numElements) {
172 <        allocateElements(numElements);
172 >        elements = new Object[numElements];
173      }
174  
175      /**
# Line 165 | Line 183 | public class ArrayDeque<E> extends Abstr
183       * @throws NullPointerException if the specified collection is null
184       */
185      public ArrayDeque(Collection<? extends E> c) {
186 <        allocateElements(c.size());
187 <        addAll(c);
186 >        Object[] es = c.toArray();
187 >        // defend against c.toArray (incorrectly) not returning Object[]
188 >        // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
189 >        if (es.getClass() != Object[].class)
190 >            es = Arrays.copyOf(es, es.length, Object[].class);
191 >        for (Object obj : es)
192 >            Objects.requireNonNull(obj);
193 >        this.elements = es;
194 >        this.size = es.length;
195 >    }
196 >
197 >    /**
198 >     * Increments i, mod modulus.
199 >     * Precondition and postcondition: 0 <= i < modulus.
200 >     */
201 >    static final int inc(int i, int modulus) {
202 >        if (++i >= modulus) i = 0;
203 >        return i;
204 >    }
205 >
206 >    /**
207 >     * Decrements i, mod modulus.
208 >     * Precondition and postcondition: 0 <= i < modulus.
209 >     */
210 >    static final int dec(int i, int modulus) {
211 >        if (--i < 0) i = modulus - 1;
212 >        return i;
213 >    }
214 >
215 >    /**
216 >     * Adds i and j, mod modulus.
217 >     * Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
218 >     */
219 >    static final int add(int i, int j, int modulus) {
220 >        if ((i += j) - modulus >= 0) i -= modulus;
221 >        return i;
222 >    }
223 >
224 >    /**
225 >     * Returns the array index of the last element.
226 >     * May return invalid index -1 if there are no elements.
227 >     */
228 >    final int tail() {
229 >        return add(head, size - 1, elements.length);
230 >    }
231 >
232 >    /**
233 >     * Returns element at array index i.
234 >     */
235 >    @SuppressWarnings("unchecked")
236 >    private E elementAt(int i) {
237 >        return (E) elements[i];
238 >    }
239 >
240 >    /**
241 >     * A version of elementAt that checks for null elements.
242 >     * This check doesn't catch all possible comodifications,
243 >     * but does catch ones that corrupt traversal.  It's a little
244 >     * surprising that javac allows this abuse of generics.
245 >     */
246 >    static final <E> E nonNullElementAt(Object[] es, int i) {
247 >        @SuppressWarnings("unchecked") E e = (E) es[i];
248 >        if (e == null)
249 >            throw new ConcurrentModificationException();
250 >        return e;
251      }
252  
253      // The main insertion and extraction methods are addFirst,
# Line 180 | Line 261 | public class ArrayDeque<E> extends Abstr
261       * @throws NullPointerException if the specified element is null
262       */
263      public void addFirst(E e) {
264 <        if (e == null)
265 <            throw new NullPointerException();
266 <        elements[head = (head - 1) & (elements.length - 1)] = e;
267 <        if (head == tail)
268 <            doubleCapacity();
264 >        // checkInvariants();
265 >        Objects.requireNonNull(e);
266 >        Object[] es;
267 >        int capacity, h;
268 >        final int s;
269 >        if ((s = size) == (capacity = (es = elements).length)) {
270 >            grow(1);
271 >            capacity = (es = elements).length;
272 >        }
273 >        if ((h = head - 1) < 0) h = capacity - 1;
274 >        es[head = h] = e;
275 >        size = s + 1;
276 >        // checkInvariants();
277      }
278  
279      /**
# Line 196 | Line 285 | public class ArrayDeque<E> extends Abstr
285       * @throws NullPointerException if the specified element is null
286       */
287      public void addLast(E e) {
288 <        if (e == null)
289 <            throw new NullPointerException();
290 <        elements[tail] = e;
291 <        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
292 <            doubleCapacity();
288 >        // checkInvariants();
289 >        Objects.requireNonNull(e);
290 >        Object[] es;
291 >        int capacity;
292 >        final int s;
293 >        if ((s = size) == (capacity = (es = elements).length)) {
294 >            grow(1);
295 >            capacity = (es = elements).length;
296 >        }
297 >        es[add(head, s, capacity)] = e;
298 >        size = s + 1;
299 >        // checkInvariants();
300 >    }
301 >
302 >    /**
303 >     * Adds all of the elements in the specified collection at the end
304 >     * of this deque, as if by calling {@link #addLast} on each one,
305 >     * in the order that they are returned by the collection's
306 >     * iterator.
307 >     *
308 >     * @param c the elements to be inserted into this deque
309 >     * @return {@code true} if this deque changed as a result of the call
310 >     * @throws NullPointerException if the specified collection or any
311 >     *         of its elements are null
312 >     */
313 >    public boolean addAll(Collection<? extends E> c) {
314 >        final int s = size, needed = c.size() - (elements.length - s);
315 >        if (needed > 0)
316 >            grow(needed);
317 >        c.forEach((e) -> addLast(e));
318 >        // checkInvariants();
319 >        return size > s;
320      }
321  
322      /**
# Line 231 | Line 347 | public class ArrayDeque<E> extends Abstr
347       * @throws NoSuchElementException {@inheritDoc}
348       */
349      public E removeFirst() {
350 <        E x = pollFirst();
351 <        if (x == null)
350 >        // checkInvariants();
351 >        E e = pollFirst();
352 >        if (e == null)
353              throw new NoSuchElementException();
354 <        return x;
354 >        return e;
355      }
356  
357      /**
358       * @throws NoSuchElementException {@inheritDoc}
359       */
360      public E removeLast() {
361 <        E x = pollLast();
362 <        if (x == null)
361 >        // checkInvariants();
362 >        E e = pollLast();
363 >        if (e == null)
364              throw new NoSuchElementException();
365 <        return x;
365 >        return e;
366      }
367  
368      public E pollFirst() {
369 <        int h = head;
370 <        @SuppressWarnings("unchecked")
371 <        E result = (E) elements[h];
254 <        // Element is null if deque empty
255 <        if (result == null)
369 >        // checkInvariants();
370 >        int s, h;
371 >        if ((s = size) <= 0)
372              return null;
373 <        elements[h] = null;     // Must null out slot
374 <        head = (h + 1) & (elements.length - 1);
375 <        return result;
373 >        final Object[] es = elements;
374 >        @SuppressWarnings("unchecked") E e = (E) es[h = head];
375 >        es[h] = null;
376 >        if (++h >= es.length) h = 0;
377 >        head = h;
378 >        size = s - 1;
379 >        return e;
380      }
381  
382      public E pollLast() {
383 <        int t = (tail - 1) & (elements.length - 1);
384 <        @SuppressWarnings("unchecked")
385 <        E result = (E) elements[t];
266 <        if (result == null)
383 >        // checkInvariants();
384 >        final int s, tail;
385 >        if ((s = size) <= 0)
386              return null;
387 <        elements[t] = null;
388 <        tail = t;
389 <        return result;
387 >        final Object[] es = elements;
388 >        @SuppressWarnings("unchecked")
389 >        E e = (E) es[tail = add(head, s - 1, es.length)];
390 >        es[tail] = null;
391 >        size = s - 1;
392 >        return e;
393      }
394  
395      /**
396       * @throws NoSuchElementException {@inheritDoc}
397       */
398      public E getFirst() {
399 <        @SuppressWarnings("unchecked")
400 <        E result = (E) elements[head];
401 <        if (result == null)
280 <            throw new NoSuchElementException();
281 <        return result;
399 >        // checkInvariants();
400 >        if (size <= 0) throw new NoSuchElementException();
401 >        return elementAt(head);
402      }
403  
404      /**
405       * @throws NoSuchElementException {@inheritDoc}
406       */
407 +    @SuppressWarnings("unchecked")
408      public E getLast() {
409 <        @SuppressWarnings("unchecked")
410 <        E result = (E) elements[(tail - 1) & (elements.length - 1)];
411 <        if (result == null)
412 <            throw new NoSuchElementException();
413 <        return result;
409 >        // checkInvariants();
410 >        final int s;
411 >        if ((s = size) <= 0) throw new NoSuchElementException();
412 >        final Object[] es = elements;
413 >        return (E) es[add(head, s - 1, es.length)];
414      }
415  
295    @SuppressWarnings("unchecked")
416      public E peekFirst() {
417 <        // elements[head] is null if deque empty
418 <        return (E) elements[head];
417 >        // checkInvariants();
418 >        return (size <= 0) ? null : elementAt(head);
419      }
420  
421      @SuppressWarnings("unchecked")
422      public E peekLast() {
423 <        return (E) elements[(tail - 1) & (elements.length - 1)];
423 >        // checkInvariants();
424 >        final int s;
425 >        if ((s = size) <= 0) return null;
426 >        final Object[] es = elements;
427 >        return (E) es[add(head, s - 1, es.length)];
428      }
429  
430      /**
# Line 316 | Line 440 | public class ArrayDeque<E> extends Abstr
440       * @return {@code true} if the deque contained the specified element
441       */
442      public boolean removeFirstOccurrence(Object o) {
443 <        if (o == null)
444 <            return false;
445 <        int mask = elements.length - 1;
446 <        int i = head;
447 <        Object x;
448 <        while ( (x = elements[i]) != null) {
449 <            if (o.equals(x)) {
450 <                delete(i);
451 <                return true;
443 >        if (o != null) {
444 >            final Object[] es = elements;
445 >            int i, end, to, todo;
446 >            todo = (end = (i = head) + size)
447 >                - (to = (es.length - end >= 0) ? end : es.length);
448 >            for (;; to = todo, i = 0, todo = 0) {
449 >                for (; i < to; i++)
450 >                    if (o.equals(es[i])) {
451 >                        delete(i);
452 >                        return true;
453 >                    }
454 >                if (todo == 0) break;
455              }
329            i = (i + 1) & mask;
456          }
457          return false;
458      }
# Line 344 | Line 470 | public class ArrayDeque<E> extends Abstr
470       * @return {@code true} if the deque contained the specified element
471       */
472      public boolean removeLastOccurrence(Object o) {
473 <        if (o == null)
474 <            return false;
475 <        int mask = elements.length - 1;
476 <        int i = (tail - 1) & mask;
477 <        Object x;
478 <        while ( (x = elements[i]) != null) {
479 <            if (o.equals(x)) {
480 <                delete(i);
481 <                return true;
473 >        if (o != null) {
474 >            final Object[] es = elements;
475 >            int i, to, end, todo;
476 >            todo = (to = ((end = (i = tail()) - size) >= -1) ? end : -1) - end;
477 >            for (;; to = (i = es.length - 1) - todo, todo = 0) {
478 >                for (; i > to; i--)
479 >                    if (o.equals(es[i])) {
480 >                        delete(i);
481 >                        return true;
482 >                    }
483 >                if (todo == 0) break;
484              }
357            i = (i - 1) & mask;
485          }
486          return false;
487      }
# Line 473 | Line 600 | public class ArrayDeque<E> extends Abstr
600          return removeFirst();
601      }
602  
476    private void checkInvariants() {
477        assert elements[tail] == null;
478        assert head == tail ? elements[head] == null :
479            (elements[head] != null &&
480             elements[(tail - 1) & (elements.length - 1)] != null);
481        assert elements[(head - 1) & (elements.length - 1)] == null;
482    }
483
603      /**
604 <     * Removes the element at the specified position in the elements array,
605 <     * adjusting head and tail as necessary.  This can result in motion of
606 <     * elements backwards or forwards in the array.
604 >     * Removes the element at the specified position in the elements array.
605 >     * This can result in forward or backwards motion of array elements.
606 >     * We optimize for least element motion.
607       *
608       * <p>This method is called delete rather than remove to emphasize
609       * that its semantics differ from those of {@link List#remove(int)}.
610       *
611       * @return true if elements moved backwards
612       */
613 <    private boolean delete(int i) {
614 <        checkInvariants();
615 <        final Object[] elements = this.elements;
616 <        final int mask = elements.length - 1;
613 >    boolean delete(int i) {
614 >        // checkInvariants();
615 >        final Object[] es = elements;
616 >        final int capacity = es.length;
617          final int h = head;
618 <        final int t = tail;
619 <        final int front = (i - h) & mask;
620 <        final int back  = (t - i) & mask;
502 <
503 <        // Invariant: head <= i < tail mod circularity
504 <        if (front >= ((t - h) & mask))
505 <            throw new ConcurrentModificationException();
506 <
507 <        // Optimize for least element motion
618 >        int front;              // number of elements before to-be-deleted elt
619 >        if ((front = i - h) < 0) front += capacity;
620 >        final int back = size - front - 1; // number of elements after
621          if (front < back) {
622 +            // move front elements forwards
623              if (h <= i) {
624 <                System.arraycopy(elements, h, elements, h + 1, front);
624 >                System.arraycopy(es, h, es, h + 1, front);
625              } else { // Wrap around
626 <                System.arraycopy(elements, 0, elements, 1, i);
627 <                elements[0] = elements[mask];
628 <                System.arraycopy(elements, h, elements, h + 1, mask - h);
626 >                System.arraycopy(es, 0, es, 1, i);
627 >                es[0] = es[capacity - 1];
628 >                System.arraycopy(es, h, es, h + 1, front - (i + 1));
629              }
630 <            elements[h] = null;
631 <            head = (h + 1) & mask;
630 >            es[h] = null;
631 >            if ((head = (h + 1)) >= capacity) head = 0;
632 >            size--;
633 >            // checkInvariants();
634              return false;
635          } else {
636 <            if (i < t) { // Copy the null tail as well
637 <                System.arraycopy(elements, i + 1, elements, i, back);
638 <                tail = t - 1;
636 >            // move back elements backwards
637 >            int tail = tail();
638 >            if (i <= tail) {
639 >                System.arraycopy(es, i + 1, es, i, back);
640              } else { // Wrap around
641 <                System.arraycopy(elements, i + 1, elements, i, mask - i);
642 <                elements[mask] = elements[0];
643 <                System.arraycopy(elements, 1, elements, 0, t);
644 <                tail = (t - 1) & mask;
641 >                int firstLeg = capacity - (i + 1);
642 >                System.arraycopy(es, i + 1, es, i, firstLeg);
643 >                es[capacity - 1] = es[0];
644 >                System.arraycopy(es, 1, es, 0, back - firstLeg - 1);
645              }
646 +            es[tail] = null;
647 +            size--;
648 +            // checkInvariants();
649              return true;
650          }
651      }
# Line 538 | Line 658 | public class ArrayDeque<E> extends Abstr
658       * @return the number of elements in this deque
659       */
660      public int size() {
661 <        return (tail - head) & (elements.length - 1);
661 >        return size;
662      }
663  
664      /**
# Line 547 | Line 667 | public class ArrayDeque<E> extends Abstr
667       * @return {@code true} if this deque contains no elements
668       */
669      public boolean isEmpty() {
670 <        return head == tail;
670 >        return size == 0;
671      }
672  
673      /**
# Line 567 | Line 687 | public class ArrayDeque<E> extends Abstr
687      }
688  
689      private class DeqIterator implements Iterator<E> {
690 <        /**
691 <         * Index of element to be returned by subsequent call to next.
572 <         */
573 <        private int cursor = head;
690 >        /** Index of element to be returned by subsequent call to next. */
691 >        int cursor;
692  
693 <        /**
694 <         * Tail recorded at construction (also in remove), to stop
577 <         * iterator and also to check for comodification.
578 <         */
579 <        private int fence = tail;
693 >        /** Number of elements yet to be returned. */
694 >        int remaining = size;
695  
696          /**
697           * Index of element returned by most recent call to next.
698           * Reset to -1 if element is deleted by a call to remove.
699           */
700 <        private int lastRet = -1;
700 >        int lastRet = -1;
701 >
702 >        DeqIterator() { cursor = head; }
703  
704 <        public boolean hasNext() {
705 <            return cursor != fence;
704 >        public final boolean hasNext() {
705 >            return remaining > 0;
706          }
707  
708          public E next() {
709 <            if (cursor == fence)
709 >            if (remaining <= 0)
710                  throw new NoSuchElementException();
711 <            @SuppressWarnings("unchecked")
712 <            E result = (E) elements[cursor];
596 <            // This check doesn't catch all possible comodifications,
597 <            // but does catch the ones that corrupt traversal
598 <            if (tail != fence || result == null)
599 <                throw new ConcurrentModificationException();
711 >            final Object[] es = elements;
712 >            E e = nonNullElementAt(es, cursor);
713              lastRet = cursor;
714 <            cursor = (cursor + 1) & (elements.length - 1);
715 <            return result;
714 >            if (++cursor >= es.length) cursor = 0;
715 >            remaining--;
716 >            return e;
717 >        }
718 >
719 >        void postDelete(boolean leftShifted) {
720 >            if (leftShifted)
721 >                if (--cursor < 0) cursor = elements.length - 1;
722          }
723  
724 <        public void remove() {
724 >        public final void remove() {
725              if (lastRet < 0)
726                  throw new IllegalStateException();
727 <            if (delete(lastRet)) { // if left-shifted, undo increment in next()
609 <                cursor = (cursor - 1) & (elements.length - 1);
610 <                fence = tail;
611 <            }
727 >            postDelete(delete(lastRet));
728              lastRet = -1;
729          }
730 +
731 +        public void forEachRemaining(Consumer<? super E> action) {
732 +            Objects.requireNonNull(action);
733 +            final int k;
734 +            if ((k = remaining) > 0) {
735 +                remaining = 0;
736 +                ArrayDeque.forEachRemaining(action, elements, cursor, k);
737 +                if ((lastRet = cursor + k - 1) >= elements.length)
738 +                    lastRet -= elements.length;
739 +            }
740 +        }
741 +    }
742 +
743 +    private class DescendingIterator extends DeqIterator {
744 +        DescendingIterator() { cursor = tail(); }
745 +
746 +        public final E next() {
747 +            if (remaining <= 0)
748 +                throw new NoSuchElementException();
749 +            final Object[] es = elements;
750 +            E e = nonNullElementAt(es, cursor);
751 +            lastRet = cursor;
752 +            if (--cursor < 0) cursor = es.length - 1;
753 +            remaining--;
754 +            return e;
755 +        }
756 +
757 +        void postDelete(boolean leftShifted) {
758 +            if (!leftShifted)
759 +                if (++cursor >= elements.length) cursor = 0;
760 +        }
761 +
762 +        public final void forEachRemaining(Consumer<? super E> action) {
763 +            Objects.requireNonNull(action);
764 +            final int k;
765 +            if ((k = remaining) > 0) {
766 +                remaining = 0;
767 +                final Object[] es = elements;
768 +                int i, end, to, todo;
769 +                todo = (to = ((end = (i = cursor) - k) >= -1) ? end : -1) - end;
770 +                for (;; to = (i = es.length - 1) - todo, todo = 0) {
771 +                    for (; i > to; i--)
772 +                        action.accept(nonNullElementAt(es, i));
773 +                    if (todo == 0) break;
774 +                }
775 +                if ((lastRet = cursor - (k - 1)) < 0)
776 +                    lastRet += es.length;
777 +            }
778 +        }
779      }
780  
781      /**
782 <     * This class is nearly a mirror-image of DeqIterator, using tail
783 <     * instead of head for initial cursor, and head instead of tail
784 <     * for fence.
785 <     */
786 <    private class DescendingIterator implements Iterator<E> {
787 <        private int cursor = tail;
788 <        private int fence = head;
789 <        private int lastRet = -1;
782 >     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
783 >     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
784 >     * deque.
785 >     *
786 >     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
787 >     * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
788 >     * {@link Spliterator#NONNULL}.  Overriding implementations should document
789 >     * the reporting of additional characteristic values.
790 >     *
791 >     * @return a {@code Spliterator} over the elements in this deque
792 >     * @since 1.8
793 >     */
794 >    public Spliterator<E> spliterator() {
795 >        return new ArrayDequeSpliterator();
796 >    }
797 >
798 >    final class ArrayDequeSpliterator implements Spliterator<E> {
799 >        private int cursor;
800 >        private int remaining; // -1 until late-binding first use
801  
802 <        public boolean hasNext() {
803 <            return cursor != fence;
802 >        /** Constructs late-binding spliterator over all elements. */
803 >        ArrayDequeSpliterator() {
804 >            this.remaining = -1;
805          }
806  
807 <        public E next() {
808 <            if (cursor == fence)
809 <                throw new NoSuchElementException();
810 <            cursor = (cursor - 1) & (elements.length - 1);
634 <            @SuppressWarnings("unchecked")
635 <            E result = (E) elements[cursor];
636 <            if (head != fence || result == null)
637 <                throw new ConcurrentModificationException();
638 <            lastRet = cursor;
639 <            return result;
807 >        /** Constructs spliterator over the given slice. */
808 >        ArrayDequeSpliterator(int cursor, int count) {
809 >            this.cursor = cursor;
810 >            this.remaining = count;
811          }
812  
813 <        public void remove() {
814 <            if (lastRet < 0)
815 <                throw new IllegalStateException();
816 <            if (!delete(lastRet)) {
817 <                cursor = (cursor + 1) & (elements.length - 1);
647 <                fence = head;
813 >        /** Ensures late-binding initialization; then returns remaining. */
814 >        private int remaining() {
815 >            if (remaining < 0) {
816 >                cursor = head;
817 >                remaining = size;
818              }
819 <            lastRet = -1;
819 >            return remaining;
820 >        }
821 >
822 >        public ArrayDequeSpliterator trySplit() {
823 >            final int mid;
824 >            if ((mid = remaining() >> 1) > 0) {
825 >                int oldCursor = cursor;
826 >                cursor = add(cursor, mid, elements.length);
827 >                remaining -= mid;
828 >                return new ArrayDequeSpliterator(oldCursor, mid);
829 >            }
830 >            return null;
831 >        }
832 >
833 >        public void forEachRemaining(Consumer<? super E> action) {
834 >            Objects.requireNonNull(action);
835 >            final int k = remaining(); // side effect!
836 >            remaining = 0;
837 >            ArrayDeque.forEachRemaining(action, elements, cursor, k);
838 >        }
839 >
840 >        public boolean tryAdvance(Consumer<? super E> action) {
841 >            Objects.requireNonNull(action);
842 >            final int k;
843 >            if ((k = remaining()) <= 0)
844 >                return false;
845 >            action.accept(nonNullElementAt(elements, cursor));
846 >            if (++cursor >= elements.length) cursor = 0;
847 >            remaining = k - 1;
848 >            return true;
849 >        }
850 >
851 >        public long estimateSize() {
852 >            return remaining();
853 >        }
854 >
855 >        public int characteristics() {
856 >            return Spliterator.NONNULL
857 >                | Spliterator.ORDERED
858 >                | Spliterator.SIZED
859 >                | Spliterator.SUBSIZED;
860 >        }
861 >    }
862 >
863 >    @SuppressWarnings("unchecked")
864 >    public void forEach(Consumer<? super E> action) {
865 >        Objects.requireNonNull(action);
866 >        final Object[] es = elements;
867 >        int i, end, to, todo;
868 >        todo = (end = (i = head) + size)
869 >            - (to = (es.length - end >= 0) ? end : es.length);
870 >        for (;; to = todo, i = 0, todo = 0) {
871 >            for (; i < to; i++)
872 >                action.accept((E) es[i]);
873 >            if (todo == 0) break;
874 >        }
875 >        // checkInvariants();
876 >    }
877 >
878 >    /**
879 >     * Calls action on remaining elements, starting at index i and
880 >     * traversing in ascending order.  A variant of forEach that also
881 >     * checks for concurrent modification, for use in iterators.
882 >     */
883 >    static <E> void forEachRemaining(
884 >        Consumer<? super E> action, Object[] es, int i, int remaining) {
885 >        int end, to, todo;
886 >        todo = (end = i + remaining)
887 >            - (to = (es.length - end >= 0) ? end : es.length);
888 >        for (;; to = todo, i = 0, todo = 0) {
889 >            for (; i < to; i++)
890 >                action.accept(nonNullElementAt(es, i));
891 >            if (todo == 0) break;
892 >        }
893 >    }
894 >
895 >    /**
896 >     * Replaces each element of this deque with the result of applying the
897 >     * operator to that element, as specified by {@link List#replaceAll}.
898 >     *
899 >     * @param operator the operator to apply to each element
900 >     * @since TBD
901 >     */
902 >    @SuppressWarnings("unchecked")
903 >    /* public */ void replaceAll(UnaryOperator<E> operator) {
904 >        Objects.requireNonNull(operator);
905 >        final Object[] es = elements;
906 >        int i, end, to, todo;
907 >        todo = (end = (i = head) + size)
908 >            - (to = (es.length - end >= 0) ? end : es.length);
909 >        for (;; to = todo, i = 0, todo = 0) {
910 >            for (; i < to; i++)
911 >                es[i] = operator.apply((E) es[i]);
912 >            if (todo == 0) break;
913 >        }
914 >        // checkInvariants();
915 >    }
916 >
917 >    /**
918 >     * @throws NullPointerException {@inheritDoc}
919 >     */
920 >    public boolean removeIf(Predicate<? super E> filter) {
921 >        Objects.requireNonNull(filter);
922 >        return bulkRemove(filter);
923 >    }
924 >
925 >    /**
926 >     * @throws NullPointerException {@inheritDoc}
927 >     */
928 >    public boolean removeAll(Collection<?> c) {
929 >        Objects.requireNonNull(c);
930 >        return bulkRemove(e -> c.contains(e));
931 >    }
932 >
933 >    /**
934 >     * @throws NullPointerException {@inheritDoc}
935 >     */
936 >    public boolean retainAll(Collection<?> c) {
937 >        Objects.requireNonNull(c);
938 >        return bulkRemove(e -> !c.contains(e));
939 >    }
940 >
941 >    /** Implementation of bulk remove methods. */
942 >    private boolean bulkRemove(Predicate<? super E> filter) {
943 >        // checkInvariants();
944 >        final Object[] es = elements;
945 >        final int capacity = es.length;
946 >        int i = head, j = i, remaining = size, deleted = 0;
947 >        try {
948 >            for (; remaining > 0; remaining--) {
949 >                @SuppressWarnings("unchecked") E e = (E) es[i];
950 >                if (filter.test(e))
951 >                    deleted++;
952 >                else {
953 >                    if (j != i)
954 >                        es[j] = e;
955 >                    if (++j >= capacity) j = 0;
956 >                }
957 >                if (++i >= capacity) i = 0;
958 >            }
959 >            return deleted > 0;
960 >        } catch (Throwable ex) {
961 >            if (deleted > 0)
962 >                for (; remaining > 0; remaining--) {
963 >                    es[j] = es[i];
964 >                    if (++i >= capacity) i = 0;
965 >                    if (++j >= capacity) j = 0;
966 >                }
967 >            throw ex;
968 >        } finally {
969 >            size -= deleted;
970 >            circularClear(es, j, deleted);
971 >            // checkInvariants();
972          }
973      }
974  
# Line 659 | Line 981 | public class ArrayDeque<E> extends Abstr
981       * @return {@code true} if this deque contains the specified element
982       */
983      public boolean contains(Object o) {
984 <        if (o == null)
985 <            return false;
986 <        int mask = elements.length - 1;
987 <        int i = head;
988 <        Object x;
989 <        while ( (x = elements[i]) != null) {
990 <            if (o.equals(x))
991 <                return true;
992 <            i = (i + 1) & mask;
984 >        if (o != null) {
985 >            final Object[] es = elements;
986 >            int i, end, to, todo;
987 >            todo = (end = (i = head) + size)
988 >                - (to = (es.length - end >= 0) ? end : es.length);
989 >            for (;; to = todo, i = 0, todo = 0) {
990 >                for (; i < to; i++)
991 >                    if (o.equals(es[i]))
992 >                        return true;
993 >                if (todo == 0) break;
994 >            }
995          }
996          return false;
997      }
# Line 694 | Line 1018 | public class ArrayDeque<E> extends Abstr
1018       * The deque will be empty after this call returns.
1019       */
1020      public void clear() {
1021 <        int h = head;
1022 <        int t = tail;
1023 <        if (h != t) { // clear all cells
1024 <            head = tail = 0;
1025 <            int i = h;
1026 <            int mask = elements.length - 1;
1027 <            do {
1028 <                elements[i] = null;
1029 <                i = (i + 1) & mask;
1030 <            } while (i != t);
1021 >        circularClear(elements, head, size);
1022 >        size = head = 0;
1023 >        // checkInvariants();
1024 >    }
1025 >
1026 >    /**
1027 >     * Nulls out count elements, starting at array index from.
1028 >     */
1029 >    private static void circularClear(Object[] es, int from, int count) {
1030 >        int end, to, todo;
1031 >        todo = (end = from + count)
1032 >            - (to = (es.length - end >= 0) ? end : es.length);
1033 >        for (;; to = todo, from = 0, todo = 0) {
1034 >            Arrays.fill(es, from, to, null);
1035 >            if (todo == 0) break;
1036          }
1037      }
1038  
# Line 721 | Line 1050 | public class ArrayDeque<E> extends Abstr
1050       * @return an array containing all of the elements in this deque
1051       */
1052      public Object[] toArray() {
1053 <        final int head = this.head;
1054 <        final int tail = this.tail;
1055 <        boolean wrap = (tail < head);
1056 <        int end = wrap ? tail + elements.length : tail;
1057 <        Object[] a = Arrays.copyOfRange(elements, head, end);
1058 <        if (wrap)
1059 <            System.arraycopy(elements, 0, a, elements.length - head, tail);
1053 >        return toArray(Object[].class);
1054 >    }
1055 >
1056 >    private <T> T[] toArray(Class<T[]> klazz) {
1057 >        final Object[] es = elements;
1058 >        final T[] a;
1059 >        final int head, len, end, todo;
1060 >        todo = size - (len = Math.min(size, es.length - (head = this.head)));
1061 >        if ((end = head + size) >= 0) {
1062 >            a = Arrays.copyOfRange(es, head, end, klazz);
1063 >        } else {
1064 >            // integer overflow!
1065 >            a = Arrays.copyOfRange(es, 0, size, klazz);
1066 >            System.arraycopy(es, head, a, 0, len);
1067 >        }
1068 >        if (todo > 0)
1069 >            System.arraycopy(es, 0, a, len, todo);
1070          return a;
1071      }
1072  
# Line 753 | Line 1092 | public class ArrayDeque<E> extends Abstr
1092       * The following code can be used to dump the deque into a newly
1093       * allocated array of {@code String}:
1094       *
1095 <     *  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
1095 >     * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
1096       *
1097       * Note that {@code toArray(new Object[0])} is identical in function to
1098       * {@code toArray()}.
# Line 769 | Line 1108 | public class ArrayDeque<E> extends Abstr
1108       */
1109      @SuppressWarnings("unchecked")
1110      public <T> T[] toArray(T[] a) {
1111 <        final int head = this.head;
1112 <        final int tail = this.tail;
1113 <        boolean wrap = (tail < head);
1114 <        int size = (tail - head) + (wrap ? elements.length : 0);
1115 <        int firstLeg = size - (wrap ? tail : 0);
1116 <        int len = a.length;
1117 <        if (size > len) {
1118 <            a = (T[]) Arrays.copyOfRange(elements, head, head + size,
1119 <                                         a.getClass());
781 <        } else {
782 <            System.arraycopy(elements, head, a, 0, firstLeg);
783 <            if (size < len)
784 <                a[size] = null;
1111 >        final int size;
1112 >        if ((size = this.size) > a.length)
1113 >            return toArray((Class<T[]>) a.getClass());
1114 >        final Object[] es = elements;
1115 >        int i, j, len, todo;
1116 >        todo = size - (len = Math.min(size, es.length - (i = head)));
1117 >        for (j = 0;; j += len, len = todo, todo = 0, i = 0) {
1118 >            System.arraycopy(es, i, a, j, len);
1119 >            if (todo == 0) break;
1120          }
1121 <        if (wrap)
1122 <            System.arraycopy(elements, 0, a, firstLeg, tail);
1121 >        if (size < a.length)
1122 >            a[size] = null;
1123          return a;
1124      }
1125  
# Line 811 | Line 1146 | public class ArrayDeque<E> extends Abstr
1146      /**
1147       * Saves this deque to a stream (that is, serializes it).
1148       *
1149 +     * @param s the stream
1150 +     * @throws java.io.IOException if an I/O error occurs
1151       * @serialData The current size ({@code int}) of the deque,
1152       * followed by all of its elements (each an object reference) in
1153       * first-to-last order.
# Line 820 | Line 1157 | public class ArrayDeque<E> extends Abstr
1157          s.defaultWriteObject();
1158  
1159          // Write out size
1160 <        s.writeInt(size());
1160 >        s.writeInt(size);
1161  
1162          // Write out elements in order.
1163 <        int mask = elements.length - 1;
1164 <        for (int i = head; i != tail; i = (i + 1) & mask)
1165 <            s.writeObject(elements[i]);
1163 >        final Object[] es = elements;
1164 >        int i, end, to, todo;
1165 >        todo = (end = (i = head) + size)
1166 >            - (to = (es.length - end >= 0) ? end : es.length);
1167 >        for (;; to = todo, i = 0, todo = 0) {
1168 >            for (; i < to; i++)
1169 >                s.writeObject(es[i]);
1170 >            if (todo == 0) break;
1171 >        }
1172      }
1173  
1174      /**
1175       * Reconstitutes this deque from a stream (that is, deserializes it).
1176 +     * @param s the stream
1177 +     * @throws ClassNotFoundException if the class of a serialized object
1178 +     *         could not be found
1179 +     * @throws java.io.IOException if an I/O error occurs
1180       */
1181      private void readObject(java.io.ObjectInputStream s)
1182              throws java.io.IOException, ClassNotFoundException {
1183          s.defaultReadObject();
1184  
1185          // Read in size and allocate array
1186 <        int size = s.readInt();
840 <        allocateElements(size);
841 <        head = 0;
842 <        tail = size;
1186 >        elements = new Object[size = s.readInt()];
1187  
1188          // Read in all elements in the proper order.
1189          for (int i = 0; i < size; i++)
1190              elements[i] = s.readObject();
1191      }
1192  
1193 <    public Spliterator<E> spliterator() {
1194 <        return new DeqSpliterator<E>(this, -1, -1);
1195 <    }
1196 <
1197 <    static final class DeqSpliterator<E> implements Spliterator<E> {
1198 <        private final ArrayDeque<E> deq;
1199 <        private int fence;  // -1 until first use
1200 <        private int index;  // current index, modified on traverse/split
1201 <
1202 <        /** Creates new spliterator covering the given array and range */
1203 <        DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
1204 <            this.deq = deq;
1205 <            this.index = origin;
1206 <            this.fence = fence;
1207 <        }
1208 <
1209 <        private int getFence() { // force initialization
866 <            int t;
867 <            if ((t = fence) < 0) {
868 <                t = fence = deq.tail;
869 <                index = deq.head;
870 <            }
871 <            return t;
872 <        }
873 <
874 <        public Spliterator<E> trySplit() {
875 <            int t = getFence(), h = index, n = deq.elements.length;
876 <            if (h != t && ((h + 1) & (n - 1)) != t) {
877 <                if (h > t)
878 <                    t += n;
879 <                int m = ((h + t) >>> 1) & (n - 1);
880 <                return new DeqSpliterator<>(deq, h, index = m);
881 <            }
882 <            return null;
883 <        }
884 <
885 <        public void forEach(Consumer<? super E> consumer) {
886 <            if (consumer == null)
887 <                throw new NullPointerException();
888 <            Object[] a = deq.elements;
889 <            int m = a.length - 1, f = getFence(), i = index;
890 <            index = f;
891 <            while (i != f) {
892 <                @SuppressWarnings("unchecked") E e = (E)a[i];
893 <                i = (i + 1) & m;
894 <                if (e == null)
895 <                    throw new ConcurrentModificationException();
896 <                consumer.accept(e);
897 <            }
898 <        }
899 <
900 <        public boolean tryAdvance(Consumer<? super E> consumer) {
901 <            if (consumer == null)
902 <                throw new NullPointerException();
903 <            Object[] a = deq.elements;
904 <            int m = a.length - 1, f = getFence(), i = index;
905 <            if (i != fence) {
906 <                @SuppressWarnings("unchecked") E e = (E)a[i];
907 <                index = (i + 1) & m;
908 <                if (e == null)
909 <                    throw new ConcurrentModificationException();
910 <                consumer.accept(e);
911 <                return true;
912 <            }
913 <            return false;
914 <        }
915 <
916 <        public long estimateSize() {
917 <            int n = getFence() - index;
918 <            if (n < 0)
919 <                n += deq.elements.length;
920 <            return (long) n;
921 <        }
922 <
923 <        @Override
924 <        public int characteristics() {
925 <            return Spliterator.ORDERED | Spliterator.SIZED |
926 <                Spliterator.NONNULL | Spliterator.SUBSIZED;
1193 >    /** debugging */
1194 >    void checkInvariants() {
1195 >        try {
1196 >            int capacity = elements.length;
1197 >            // assert size >= 0 && size <= capacity;
1198 >            // assert head >= 0;
1199 >            // assert capacity == 0 || head < capacity;
1200 >            // assert size == 0 || elements[head] != null;
1201 >            // assert size == 0 || elements[tail()] != null;
1202 >            // assert size == capacity || elements[dec(head, capacity)] == null;
1203 >            // assert size == capacity || elements[inc(tail(), capacity)] == null;
1204 >        } catch (Throwable t) {
1205 >            System.err.printf("head=%d size=%d capacity=%d%n",
1206 >                              head, size, elements.length);
1207 >            System.err.printf("elements=%s%n",
1208 >                              Arrays.toString(elements));
1209 >            throw t;
1210          }
1211      }
1212  

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines