1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation. Oracle designates this
7 * particular file as subject to the "Classpath" exception as provided
8 * by Oracle in the LICENSE file that accompanied this code.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 */
24
25 /*
26 * This file is available under and governed by the GNU General Public
27 * License version 2 only, as published by the Free Software Foundation.
28 * However, the following notice accompanied the original version of this
29 * file:
30 *
31 * Written by Josh Bloch of Google Inc. and released to the public domain,
32 * as explained at http://creativecommons.org/publicdomain/zero/1.0/.
33 */
34
35 package java.util;
36
37 import java.io.Serializable;
38 import java.util.function.Consumer;
39
40 /**
41 * Resizable-array implementation of the {@link Deque} interface. Array
42 * deques have no capacity restrictions; they grow as necessary to support
43 * usage. They are not thread-safe; in the absence of external
44 * synchronization, they do not support concurrent access by multiple threads.
45 * Null elements are prohibited. This class is likely to be faster than
46 * {@link Stack} when used as a stack, and faster than {@link LinkedList}
47 * when used as a queue.
48 *
49 * <p>Most {@code ArrayDeque} operations run in amortized constant time.
50 * Exceptions include {@link #remove(Object) remove}, {@link
51 * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
52 * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
53 * iterator.remove()}, and the bulk operations, all of which run in linear
54 * time.
55 *
56 * <p>The iterators returned by this class's {@code iterator} method are
57 * <i>fail-fast</i>: If the deque is modified at any time after the iterator
58 * is created, in any way except through the iterator's own {@code remove}
59 * method, the iterator will generally throw a {@link
60 * ConcurrentModificationException}. Thus, in the face of concurrent
61 * modification, the iterator fails quickly and cleanly, rather than risking
62 * arbitrary, non-deterministic behavior at an undetermined time in the
63 * future.
64 *
65 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
66 * as it is, generally speaking, impossible to make any hard guarantees in the
67 * presence of unsynchronized concurrent modification. Fail-fast iterators
68 * throw {@code ConcurrentModificationException} on a best-effort basis.
69 * Therefore, it would be wrong to write a program that depended on this
70 * exception for its correctness: <i>the fail-fast behavior of iterators
71 * should be used only to detect bugs.</i>
72 *
73 * <p>This class and its iterator implement all of the
74 * <em>optional</em> methods of the {@link Collection} and {@link
75 * Iterator} interfaces.
76 *
77 * <p>This class is a member of the
78 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
79 * Java Collections Framework</a>.
80 *
81 * @author Josh Bloch and Doug Lea
82 * @since 1.6
83 * @param <E> the type of elements held in this collection
84 */
85 public class ArrayDeque<E> extends AbstractCollection<E>
86 implements Deque<E>, Cloneable, Serializable
87 {
88 /**
89 * The array in which the elements of the deque are stored.
90 * The capacity of the deque is the length of this array, which is
91 * always a power of two. The array is never allowed to become
92 * full, except transiently within an addX method where it is
93 * resized (see doubleCapacity) immediately upon becoming full,
94 * thus avoiding head and tail wrapping around to equal each
95 * other. We also guarantee that all array cells not holding
96 * deque elements are always null.
97 */
98 transient Object[] elements; // non-private to simplify nested class access
99
100 /**
101 * The index of the element at the head of the deque (which is the
102 * element that would be removed by remove() or pop()); or an
103 * arbitrary number equal to tail if the deque is empty.
104 */
105 transient int head;
106
107 /**
108 * The index at which the next element would be added to the tail
109 * of the deque (via addLast(E), add(E), or push(E)).
110 */
111 transient int tail;
112
113 /**
114 * The minimum capacity that we'll use for a newly created deque.
115 * Must be a power of 2.
116 */
117 private static final int MIN_INITIAL_CAPACITY = 8;
118
119 // ****** Array allocation and resizing utilities ******
120
121 /**
122 * Allocates empty array to hold the given number of elements.
123 *
124 * @param numElements the number of elements to hold
125 */
126 private void allocateElements(int numElements) {
127 int initialCapacity = MIN_INITIAL_CAPACITY;
128 // Find the best power of two to hold elements.
129 // Tests "<=" because arrays aren't kept full.
130 if (numElements >= initialCapacity) {
131 initialCapacity = numElements;
132 initialCapacity |= (initialCapacity >>> 1);
133 initialCapacity |= (initialCapacity >>> 2);
134 initialCapacity |= (initialCapacity >>> 4);
135 initialCapacity |= (initialCapacity >>> 8);
136 initialCapacity |= (initialCapacity >>> 16);
137 initialCapacity++;
138
139 if (initialCapacity < 0) // Too many elements, must back off
140 initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
141 }
142 elements = new Object[initialCapacity];
143 }
144
145 /**
146 * Doubles the capacity of this deque. Call only when full, i.e.,
147 * when head and tail have wrapped around to become equal.
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;
155 if (newCapacity < 0)
156 throw new IllegalStateException("Sorry, deque too big");
157 Object[] a = new Object[newCapacity];
158 System.arraycopy(elements, p, a, 0, r);
159 System.arraycopy(elements, 0, a, r, p);
160 elements = a;
161 head = 0;
162 tail = n;
163 }
164
165 /**
166 * Copies the elements from our element array into the specified array,
167 * in order (from first to last element in the deque). It is assumed
168 * that the array is large enough to hold all elements in the deque.
169 *
170 * @return its argument
171 */
172 private <T> T[] copyElements(T[] a) {
173 if (head < tail) {
174 System.arraycopy(elements, head, a, 0, size());
175 } else if (head > tail) {
176 int headPortionLen = elements.length - head;
177 System.arraycopy(elements, head, a, 0, headPortionLen);
178 System.arraycopy(elements, 0, a, headPortionLen, tail);
179 }
180 return a;
181 }
182
183 /**
184 * Constructs an empty array deque with an initial capacity
185 * sufficient to hold 16 elements.
186 */
187 public ArrayDeque() {
188 elements = new Object[16];
189 }
190
191 /**
192 * Constructs an empty array deque with an initial capacity
193 * sufficient to hold the specified number of elements.
194 *
195 * @param numElements lower bound on initial capacity of the deque
196 */
197 public ArrayDeque(int numElements) {
198 allocateElements(numElements);
199 }
200
201 /**
202 * Constructs a deque containing the elements of the specified
203 * collection, in the order they are returned by the collection's
204 * iterator. (The first element returned by the collection's
205 * iterator becomes the first element, or <i>front</i> of the
206 * deque.)
207 *
208 * @param c the collection whose elements are to be placed into the deque
209 * @throws NullPointerException if the specified collection is null
210 */
211 public ArrayDeque(Collection<? extends E> c) {
212 allocateElements(c.size());
213 addAll(c);
214 }
215
216 // The main insertion and extraction methods are addFirst,
217 // addLast, pollFirst, pollLast. The other methods are defined in
218 // terms of these.
219
220 /**
221 * Inserts the specified element at the front of this deque.
222 *
223 * @param e the element to add
224 * @throws NullPointerException if the specified element is null
225 */
226 public void addFirst(E e) {
227 if (e == null)
228 throw new NullPointerException();
229 elements[head = (head - 1) & (elements.length - 1)] = e;
230 if (head == tail)
231 doubleCapacity();
232 }
233
234 /**
235 * Inserts the specified element at the end of this deque.
236 *
237 * <p>This method is equivalent to {@link #add}.
238 *
239 * @param e the element to add
240 * @throws NullPointerException if the specified element is null
241 */
242 public void addLast(E e) {
243 if (e == null)
244 throw new NullPointerException();
245 elements[tail] = e;
246 if ( (tail = (tail + 1) & (elements.length - 1)) == head)
247 doubleCapacity();
248 }
249
250 /**
251 * Inserts the specified element at the front of this deque.
252 *
253 * @param e the element to add
254 * @return {@code true} (as specified by {@link Deque#offerFirst})
255 * @throws NullPointerException if the specified element is null
256 */
257 public boolean offerFirst(E e) {
258 addFirst(e);
259 return true;
260 }
261
262 /**
263 * Inserts the specified element at the end of this deque.
264 *
265 * @param e the element to add
266 * @return {@code true} (as specified by {@link Deque#offerLast})
267 * @throws NullPointerException if the specified element is null
268 */
269 public boolean offerLast(E e) {
270 addLast(e);
271 return true;
272 }
273
274 /**
275 * @throws NoSuchElementException {@inheritDoc}
276 */
277 public E removeFirst() {
278 E x = pollFirst();
279 if (x == null)
280 throw new NoSuchElementException();
281 return x;
282 }
283
284 /**
285 * @throws NoSuchElementException {@inheritDoc}
286 */
287 public E removeLast() {
288 E x = pollLast();
289 if (x == null)
290 throw new NoSuchElementException();
291 return x;
292 }
293
294 public E pollFirst() {
295 int h = head;
296 @SuppressWarnings("unchecked")
297 E result = (E) elements[h];
298 // Element is null if deque empty
299 if (result == null)
300 return null;
301 elements[h] = null; // Must null out slot
302 head = (h + 1) & (elements.length - 1);
303 return result;
304 }
305
306 public E pollLast() {
307 int t = (tail - 1) & (elements.length - 1);
308 @SuppressWarnings("unchecked")
309 E result = (E) elements[t];
310 if (result == null)
311 return null;
312 elements[t] = null;
313 tail = t;
314 return result;
315 }
316
317 /**
318 * @throws NoSuchElementException {@inheritDoc}
319 */
320 public E getFirst() {
321 @SuppressWarnings("unchecked")
322 E result = (E) elements[head];
323 if (result == null)
324 throw new NoSuchElementException();
325 return result;
326 }
327
328 /**
329 * @throws NoSuchElementException {@inheritDoc}
330 */
331 public E getLast() {
332 @SuppressWarnings("unchecked")
333 E result = (E) elements[(tail - 1) & (elements.length - 1)];
334 if (result == null)
335 throw new NoSuchElementException();
336 return result;
337 }
338
339 @SuppressWarnings("unchecked")
340 public E peekFirst() {
341 // elements[head] is null if deque empty
342 return (E) elements[head];
343 }
344
345 @SuppressWarnings("unchecked")
346 public E peekLast() {
347 return (E) elements[(tail - 1) & (elements.length - 1)];
348 }
349
350 /**
351 * Removes the first occurrence of the specified element in this
352 * deque (when traversing the deque from head to tail).
353 * If the deque does not contain the element, it is unchanged.
354 * More formally, removes the first element {@code e} such that
355 * {@code o.equals(e)} (if such an element exists).
356 * Returns {@code true} if this deque contained the specified element
357 * (or equivalently, if this deque changed as a result of the call).
358 *
359 * @param o element to be removed from this deque, if present
360 * @return {@code true} if the deque contained the specified element
361 */
362 public boolean removeFirstOccurrence(Object o) {
363 if (o == null)
364 return false;
365 int mask = elements.length - 1;
366 int i = head;
367 Object x;
368 while ( (x = elements[i]) != null) {
369 if (o.equals(x)) {
370 delete(i);
371 return true;
372 }
373 i = (i + 1) & mask;
374 }
375 return false;
376 }
377
378 /**
379 * Removes the last occurrence of the specified element in this
380 * deque (when traversing the deque from head to tail).
381 * If the deque does not contain the element, it is unchanged.
382 * More formally, removes the last element {@code e} such that
383 * {@code o.equals(e)} (if such an element exists).
384 * Returns {@code true} if this deque contained the specified element
385 * (or equivalently, if this deque changed as a result of the call).
386 *
387 * @param o element to be removed from this deque, if present
388 * @return {@code true} if the deque contained the specified element
389 */
390 public boolean removeLastOccurrence(Object o) {
391 if (o == null)
392 return false;
393 int mask = elements.length - 1;
394 int i = (tail - 1) & mask;
395 Object x;
396 while ( (x = elements[i]) != null) {
397 if (o.equals(x)) {
398 delete(i);
399 return true;
400 }
401 i = (i - 1) & mask;
402 }
403 return false;
404 }
405
406 // *** Queue methods ***
407
408 /**
409 * Inserts the specified element at the end of this deque.
410 *
411 * <p>This method is equivalent to {@link #addLast}.
412 *
413 * @param e the element to add
414 * @return {@code true} (as specified by {@link Collection#add})
415 * @throws NullPointerException if the specified element is null
416 */
417 public boolean add(E e) {
418 addLast(e);
419 return true;
420 }
421
422 /**
423 * Inserts the specified element at the end of this deque.
424 *
425 * <p>This method is equivalent to {@link #offerLast}.
426 *
427 * @param e the element to add
428 * @return {@code true} (as specified by {@link Queue#offer})
429 * @throws NullPointerException if the specified element is null
430 */
431 public boolean offer(E e) {
432 return offerLast(e);
433 }
434
435 /**
436 * Retrieves and removes the head of the queue represented by this deque.
437 *
438 * This method differs from {@link #poll poll} only in that it throws an
439 * exception if this deque is empty.
440 *
441 * <p>This method is equivalent to {@link #removeFirst}.
442 *
443 * @return the head of the queue represented by this deque
444 * @throws NoSuchElementException {@inheritDoc}
445 */
446 public E remove() {
447 return removeFirst();
448 }
449
450 /**
451 * Retrieves and removes the head of the queue represented by this deque
452 * (in other words, the first element of this deque), or returns
453 * {@code null} if this deque is empty.
454 *
455 * <p>This method is equivalent to {@link #pollFirst}.
456 *
457 * @return the head of the queue represented by this deque, or
458 * {@code null} if this deque is empty
459 */
460 public E poll() {
461 return pollFirst();
462 }
463
464 /**
465 * Retrieves, but does not remove, the head of the queue represented by
466 * this deque. This method differs from {@link #peek peek} only in
467 * that it throws an exception if this deque is empty.
468 *
469 * <p>This method is equivalent to {@link #getFirst}.
470 *
471 * @return the head of the queue represented by this deque
472 * @throws NoSuchElementException {@inheritDoc}
473 */
474 public E element() {
475 return getFirst();
476 }
477
478 /**
479 * Retrieves, but does not remove, the head of the queue represented by
480 * this deque, or returns {@code null} if this deque is empty.
481 *
482 * <p>This method is equivalent to {@link #peekFirst}.
483 *
484 * @return the head of the queue represented by this deque, or
485 * {@code null} if this deque is empty
486 */
487 public E peek() {
488 return peekFirst();
489 }
490
491 // *** Stack methods ***
492
493 /**
494 * Pushes an element onto the stack represented by this deque. In other
495 * words, inserts the element at the front of this deque.
496 *
497 * <p>This method is equivalent to {@link #addFirst}.
498 *
499 * @param e the element to push
500 * @throws NullPointerException if the specified element is null
501 */
502 public void push(E e) {
503 addFirst(e);
504 }
505
506 /**
507 * Pops an element from the stack represented by this deque. In other
508 * words, removes and returns the first element of this deque.
509 *
510 * <p>This method is equivalent to {@link #removeFirst()}.
511 *
512 * @return the element at the front of this deque (which is the top
513 * of the stack represented by this deque)
514 * @throws NoSuchElementException {@inheritDoc}
515 */
516 public E pop() {
517 return removeFirst();
518 }
519
520 private void checkInvariants() {
521 assert elements[tail] == null;
522 assert head == tail ? elements[head] == null :
523 (elements[head] != null &&
524 elements[(tail - 1) & (elements.length - 1)] != null);
525 assert elements[(head - 1) & (elements.length - 1)] == null;
526 }
527
528 /**
529 * Removes the element at the specified position in the elements array,
530 * adjusting head and tail as necessary. This can result in motion of
531 * elements backwards or forwards in the array.
532 *
533 * <p>This method is called delete rather than remove to emphasize
534 * that its semantics differ from those of {@link List#remove(int)}.
535 *
536 * @return true if elements moved backwards
537 */
538 private boolean delete(int i) {
539 checkInvariants();
540 final Object[] elements = this.elements;
541 final int mask = elements.length - 1;
542 final int h = head;
543 final int t = tail;
544 final int front = (i - h) & mask;
545 final int back = (t - i) & mask;
546
547 // Invariant: head <= i < tail mod circularity
548 if (front >= ((t - h) & mask))
549 throw new ConcurrentModificationException();
550
551 // Optimize for least element motion
552 if (front < back) {
553 if (h <= i) {
554 System.arraycopy(elements, h, elements, h + 1, front);
555 } else { // Wrap around
556 System.arraycopy(elements, 0, elements, 1, i);
557 elements[0] = elements[mask];
558 System.arraycopy(elements, h, elements, h + 1, mask - h);
559 }
560 elements[h] = null;
561 head = (h + 1) & mask;
562 return false;
563 } else {
564 if (i < t) { // Copy the null tail as well
565 System.arraycopy(elements, i + 1, elements, i, back);
566 tail = t - 1;
567 } else { // Wrap around
568 System.arraycopy(elements, i + 1, elements, i, mask - i);
569 elements[mask] = elements[0];
570 System.arraycopy(elements, 1, elements, 0, t);
571 tail = (t - 1) & mask;
572 }
573 return true;
574 }
575 }
576
577 // *** Collection Methods ***
578
579 /**
580 * Returns the number of elements in this deque.
581 *
582 * @return the number of elements in this deque
583 */
584 public int size() {
585 return (tail - head) & (elements.length - 1);
586 }
587
588 /**
589 * Returns {@code true} if this deque contains no elements.
590 *
591 * @return {@code true} if this deque contains no elements
592 */
593 public boolean isEmpty() {
594 return head == tail;
595 }
596
597 /**
598 * Returns an iterator over the elements in this deque. The elements
599 * will be ordered from first (head) to last (tail). This is the same
600 * order that elements would be dequeued (via successive calls to
601 * {@link #remove} or popped (via successive calls to {@link #pop}).
602 *
603 * @return an iterator over the elements in this deque
604 */
605 public Iterator<E> iterator() {
606 return new DeqIterator();
607 }
608
609 public Iterator<E> descendingIterator() {
610 return new DescendingIterator();
611 }
612
613 private class DeqIterator implements Iterator<E> {
614 /**
615 * Index of element to be returned by subsequent call to next.
616 */
617 private int cursor = head;
618
619 /**
620 * Tail recorded at construction (also in remove), to stop
621 * iterator and also to check for comodification.
622 */
623 private int fence = tail;
624
625 /**
626 * Index of element returned by most recent call to next.
627 * Reset to -1 if element is deleted by a call to remove.
628 */
629 private int lastRet = -1;
630
631 public boolean hasNext() {
632 return cursor != fence;
633 }
634
635 public E next() {
636 if (cursor == fence)
637 throw new NoSuchElementException();
638 @SuppressWarnings("unchecked")
639 E result = (E) elements[cursor];
640 // This check doesn't catch all possible comodifications,
641 // but does catch the ones that corrupt traversal
642 if (tail != fence || result == null)
643 throw new ConcurrentModificationException();
644 lastRet = cursor;
645 cursor = (cursor + 1) & (elements.length - 1);
646 return result;
647 }
648
649 public void remove() {
650 if (lastRet < 0)
651 throw new IllegalStateException();
652 if (delete(lastRet)) { // if left-shifted, undo increment in next()
653 cursor = (cursor - 1) & (elements.length - 1);
654 fence = tail;
655 }
656 lastRet = -1;
657 }
658
659 public void forEachRemaining(Consumer<? super E> action) {
660 Objects.requireNonNull(action);
661 Object[] a = elements;
662 int m = a.length - 1, f = fence, i = cursor;
663 cursor = f;
664 while (i != f) {
665 @SuppressWarnings("unchecked") E e = (E)a[i];
666 i = (i + 1) & m;
667 if (e == null)
668 throw new ConcurrentModificationException();
669 action.accept(e);
670 }
671 }
672 }
673
674 private class DescendingIterator implements Iterator<E> {
675 /*
676 * This class is nearly a mirror-image of DeqIterator, using
677 * tail instead of head for initial cursor, and head instead of
678 * tail for fence.
679 */
680 private int cursor = tail;
681 private int fence = head;
682 private int lastRet = -1;
683
684 public boolean hasNext() {
685 return cursor != fence;
686 }
687
688 public E next() {
689 if (cursor == fence)
690 throw new NoSuchElementException();
691 cursor = (cursor - 1) & (elements.length - 1);
692 @SuppressWarnings("unchecked")
693 E result = (E) elements[cursor];
694 if (head != fence || result == null)
695 throw new ConcurrentModificationException();
696 lastRet = cursor;
697 return result;
698 }
699
700 public void remove() {
701 if (lastRet < 0)
702 throw new IllegalStateException();
703 if (!delete(lastRet)) {
704 cursor = (cursor + 1) & (elements.length - 1);
705 fence = head;
706 }
707 lastRet = -1;
708 }
709 }
710
711 /**
712 * Returns {@code true} if this deque contains the specified element.
713 * More formally, returns {@code true} if and only if this deque contains
714 * at least one element {@code e} such that {@code o.equals(e)}.
715 *
716 * @param o object to be checked for containment in this deque
717 * @return {@code true} if this deque contains the specified element
718 */
719 public boolean contains(Object o) {
720 if (o == null)
721 return false;
722 int mask = elements.length - 1;
723 int i = head;
724 Object x;
725 while ( (x = elements[i]) != null) {
726 if (o.equals(x))
727 return true;
728 i = (i + 1) & mask;
729 }
730 return false;
731 }
732
733 /**
734 * Removes a single instance of the specified element from this deque.
735 * If the deque does not contain the element, it is unchanged.
736 * More formally, removes the first element {@code e} such that
737 * {@code o.equals(e)} (if such an element exists).
738 * Returns {@code true} if this deque contained the specified element
739 * (or equivalently, if this deque changed as a result of the call).
740 *
741 * <p>This method is equivalent to {@link #removeFirstOccurrence(Object)}.
742 *
743 * @param o element to be removed from this deque, if present
744 * @return {@code true} if this deque contained the specified element
745 */
746 public boolean remove(Object o) {
747 return removeFirstOccurrence(o);
748 }
749
750 /**
751 * Removes all of the elements from this deque.
752 * The deque will be empty after this call returns.
753 */
754 public void clear() {
755 int h = head;
756 int t = tail;
757 if (h != t) { // clear all cells
758 head = tail = 0;
759 int i = h;
760 int mask = elements.length - 1;
761 do {
762 elements[i] = null;
763 i = (i + 1) & mask;
764 } while (i != t);
765 }
766 }
767
768 /**
769 * Returns an array containing all of the elements in this deque
770 * in proper sequence (from first to last element).
771 *
772 * <p>The returned array will be "safe" in that no references to it are
773 * maintained by this deque. (In other words, this method must allocate
774 * a new array). The caller is thus free to modify the returned array.
775 *
776 * <p>This method acts as bridge between array-based and collection-based
777 * APIs.
778 *
779 * @return an array containing all of the elements in this deque
780 */
781 public Object[] toArray() {
782 return copyElements(new Object[size()]);
783 }
784
785 /**
786 * Returns an array containing all of the elements in this deque in
787 * proper sequence (from first to last element); the runtime type of the
788 * returned array is that of the specified array. If the deque fits in
789 * the specified array, it is returned therein. Otherwise, a new array
790 * is allocated with the runtime type of the specified array and the
791 * size of this deque.
792 *
793 * <p>If this deque fits in the specified array with room to spare
794 * (i.e., the array has more elements than this deque), the element in
795 * the array immediately following the end of the deque is set to
796 * {@code null}.
797 *
798 * <p>Like the {@link #toArray()} method, this method acts as bridge between
799 * array-based and collection-based APIs. Further, this method allows
800 * precise control over the runtime type of the output array, and may,
801 * under certain circumstances, be used to save allocation costs.
802 *
803 * <p>Suppose {@code x} is a deque known to contain only strings.
804 * The following code can be used to dump the deque into a newly
805 * allocated array of {@code String}:
806 *
807 * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
808 *
809 * Note that {@code toArray(new Object[0])} is identical in function to
810 * {@code toArray()}.
811 *
812 * @param a the array into which the elements of the deque are to
813 * be stored, if it is big enough; otherwise, a new array of the
814 * same runtime type is allocated for this purpose
815 * @return an array containing all of the elements in this deque
816 * @throws ArrayStoreException if the runtime type of the specified array
817 * is not a supertype of the runtime type of every element in
818 * this deque
819 * @throws NullPointerException if the specified array is null
820 */
821 @SuppressWarnings("unchecked")
822 public <T> T[] toArray(T[] a) {
823 int size = size();
824 if (a.length < size)
825 a = (T[])java.lang.reflect.Array.newInstance(
826 a.getClass().getComponentType(), size);
827 copyElements(a);
828 if (a.length > size)
829 a[size] = null;
830 return a;
831 }
832
833 // *** Object methods ***
834
835 /**
836 * Returns a copy of this deque.
837 *
838 * @return a copy of this deque
839 */
840 public ArrayDeque<E> clone() {
841 try {
842 @SuppressWarnings("unchecked")
843 ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
844 result.elements = Arrays.copyOf(elements, elements.length);
845 return result;
846 } catch (CloneNotSupportedException e) {
847 throw new AssertionError();
848 }
849 }
850
851 private static final long serialVersionUID = 2340985798034038923L;
852
853 /**
854 * Saves this deque to a stream (that is, serializes it).
855 *
856 * @serialData The current size ({@code int}) of the deque,
857 * followed by all of its elements (each an object reference) in
858 * first-to-last order.
859 */
860 private void writeObject(java.io.ObjectOutputStream s)
861 throws java.io.IOException {
862 s.defaultWriteObject();
863
864 // Write out size
865 s.writeInt(size());
866
867 // Write out elements in order.
868 int mask = elements.length - 1;
869 for (int i = head; i != tail; i = (i + 1) & mask)
870 s.writeObject(elements[i]);
871 }
872
873 /**
874 * Reconstitutes this deque from a stream (that is, deserializes it).
875 */
876 private void readObject(java.io.ObjectInputStream s)
877 throws java.io.IOException, ClassNotFoundException {
878 s.defaultReadObject();
879
880 // Read in size and allocate array
881 int size = s.readInt();
882 allocateElements(size);
883 head = 0;
884 tail = size;
885
886 // Read in all elements in the proper order.
887 for (int i = 0; i < size; i++)
888 elements[i] = s.readObject();
889 }
890
891 /**
892 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
893 * and <em>fail-fast</em> {@link Spliterator} over the elements in this
894 * deque.
895 *
896 * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
897 * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
898 * {@link Spliterator#NONNULL}. Overriding implementations should document
899 * the reporting of additional characteristic values.
900 *
901 * @return a {@code Spliterator} over the elements in this deque
902 * @since 1.8
903 */
904 public Spliterator<E> spliterator() {
905 return new DeqSpliterator<E>(this, -1, -1);
906 }
907
908 static final class DeqSpliterator<E> implements Spliterator<E> {
909 private final ArrayDeque<E> deq;
910 private int fence; // -1 until first use
911 private int index; // current index, modified on traverse/split
912
913 /** Creates new spliterator covering the given array and range */
914 DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
915 this.deq = deq;
916 this.index = origin;
917 this.fence = fence;
918 }
919
920 private int getFence() { // force initialization
921 int t;
922 if ((t = fence) < 0) {
923 t = fence = deq.tail;
924 index = deq.head;
925 }
926 return t;
927 }
928
929 public DeqSpliterator<E> trySplit() {
930 int t = getFence(), h = index, n = deq.elements.length;
931 if (h != t && ((h + 1) & (n - 1)) != t) {
932 if (h > t)
933 t += n;
934 int m = ((h + t) >>> 1) & (n - 1);
935 return new DeqSpliterator<>(deq, h, index = m);
936 }
937 return null;
938 }
939
940 public void forEachRemaining(Consumer<? super E> consumer) {
941 if (consumer == null)
942 throw new NullPointerException();
943 Object[] a = deq.elements;
944 int m = a.length - 1, f = getFence(), i = index;
945 index = f;
946 while (i != f) {
947 @SuppressWarnings("unchecked") E e = (E)a[i];
948 i = (i + 1) & m;
949 if (e == null)
950 throw new ConcurrentModificationException();
951 consumer.accept(e);
952 }
953 }
954
955 public boolean tryAdvance(Consumer<? super E> consumer) {
956 if (consumer == null)
957 throw new NullPointerException();
958 Object[] a = deq.elements;
959 int m = a.length - 1, f = getFence(), i = index;
960 if (i != fence) {
961 @SuppressWarnings("unchecked") E e = (E)a[i];
962 index = (i + 1) & m;
963 if (e == null)
964 throw new ConcurrentModificationException();
965 consumer.accept(e);
966 return true;
967 }
968 return false;
969 }
970
971 public long estimateSize() {
972 int n = getFence() - index;
973 if (n < 0)
974 n += deq.elements.length;
975 return (long) n;
976 }
977
978 @Override
979 public int characteristics() {
980 return Spliterator.ORDERED | Spliterator.SIZED |
981 Spliterator.NONNULL | Spliterator.SUBSIZED;
982 }
983 }
984
985 }