2 * Written by Josh Bloch of Google Inc. and released to the public domain,
3 * as explained at http://creativecommons.org/licenses/publicdomain.
10 * Resizable-array implementation of the {@link Deque} interface. Array
11 * deques have no capacity restrictions; they grow as necessary to support
12 * usage. They are not thread-safe; in the absence of external
13 * synchronization, they do not support concurrent access by multiple threads.
14 * Null elements are prohibited. This class is likely to be faster than
15 * {@link Stack} when used as a stack, and faster than {@link LinkedList}
16 * when used as a queue.
18 * <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
19 * Exceptions include {@link #remove(Object) remove}, {@link
20 * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
21 * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
22 * iterator.remove()}, and the bulk operations, all of which run in linear
25 * <p>The iterators returned by this class's <tt>iterator</tt> method are
26 * <i>fail-fast</i>: If the deque is modified at any time after the iterator
27 * is created, in any way except through the iterator's own <tt>remove</tt>
28 * method, the iterator will generally throw a {@link
29 * ConcurrentModificationException}. Thus, in the face of concurrent
30 * modification, the iterator fails quickly and cleanly, rather than risking
31 * arbitrary, non-deterministic behavior at an undetermined time in the
34 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
35 * as it is, generally speaking, impossible to make any hard guarantees in the
36 * presence of unsynchronized concurrent modification. Fail-fast iterators
37 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
38 * Therefore, it would be wrong to write a program that depended on this
39 * exception for its correctness: <i>the fail-fast behavior of iterators
40 * should be used only to detect bugs.</i>
42 * <p>This class and its iterator implement all of the
43 * <em>optional</em> methods of the {@link Collection} and {@link
44 * Iterator} interfaces.
46 * <p>This class is a member of the
47 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
48 * Java Collections Framework</a>.
50 * @author Josh Bloch and Doug Lea
52 * @param <E> the type of elements held in this collection
54 //public class ArrayDeque<E> extends AbstractCollection<E>
55 public class ArrayDeque extends AbstractCollection
56 implements Deque/*<E>*/, Cloneable, Serializable
59 * The array in which the elements of the deque are stored.
60 * The capacity of the deque is the length of this array, which is
61 * always a power of two. The array is never allowed to become
62 * full, except transiently within an addX method where it is
63 * resized (see doubleCapacity) immediately upon becoming full,
64 * thus avoiding head and tail wrapping around to equal each
65 * other. We also guarantee that all array cells not holding
66 * deque elements are always null.
68 private transient Object/*E*/[] elements;
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.
75 private transient int head;
78 * The index at which the next element would be added to the tail
79 * of the deque (via addLast(E), add(E), or push(E)).
81 private transient int tail;
84 * The minimum capacity that we'll use for a newly created deque.
85 * Must be a power of 2.
87 private static final int MIN_INITIAL_CAPACITY = 8;
89 // ****** Array allocation and resizing utilities ******
92 * Allocate empty array to hold the given number of elements.
94 * @param numElements the number of elements to hold
96 private void allocateElements(int numElements) {
97 int initialCapacity = MIN_INITIAL_CAPACITY;
98 // Find the best power of two to hold elements.
99 // Tests "<=" because arrays aren't kept full.
100 if (numElements >= initialCapacity) {
101 initialCapacity = numElements;
102 initialCapacity |= (initialCapacity >>> 1);
103 initialCapacity |= (initialCapacity >>> 2);
104 initialCapacity |= (initialCapacity >>> 4);
105 initialCapacity |= (initialCapacity >>> 8);
106 initialCapacity |= (initialCapacity >>> 16);
109 if (initialCapacity < 0) // Too many elements, must back off
110 initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
112 elements = /*(E[])*/ new Object[initialCapacity];
116 * Double the capacity of this deque. Call only when full, i.e.,
117 * when head and tail have wrapped around to become equal.
119 private void doubleCapacity() {
120 //assert head == tail;
122 int n = elements.length;
123 int r = n - p; // number of elements to the right of p
124 int newCapacity = n << 1;
126 throw new IllegalStateException("Sorry, deque too big");
127 Object[] a = new Object[newCapacity];
128 System.arraycopy(elements, p, a, 0, r);
129 System.arraycopy(elements, 0, a, r, p);
130 elements = /*(E[])*/a;
136 * Copies the elements from our element array into the specified array,
137 * in order (from first to last element in the deque). It is assumed
138 * that the array is large enough to hold all elements in the deque.
140 * @return its argument
142 private /*<T> T*/Object[] copyElements(Object/*T*/[] a) {
144 System.arraycopy(elements, head, a, 0, size());
145 } else if (head > tail) {
146 int headPortionLen = elements.length - head;
147 System.arraycopy(elements, head, a, 0, headPortionLen);
148 System.arraycopy(elements, 0, a, headPortionLen, tail);
154 * Constructs an empty array deque with an initial capacity
155 * sufficient to hold 16 elements.
157 public ArrayDeque() {
158 elements = /*(E[])*/ new Object[16];
162 * Constructs an empty array deque with an initial capacity
163 * sufficient to hold the specified number of elements.
165 * @param numElements lower bound on initial capacity of the deque
167 public ArrayDeque(int numElements) {
168 allocateElements(numElements);
172 * Constructs a deque containing the elements of the specified
173 * collection, in the order they are returned by the collection's
174 * iterator. (The first element returned by the collection's
175 * iterator becomes the first element, or <i>front</i> of the
178 * @param c the collection whose elements are to be placed into the deque
179 * @throws NullPointerException if the specified collection is null
181 public ArrayDeque(Collection/*<? extends E>*/ c) {
182 allocateElements(c.size());
186 // The main insertion and extraction methods are addFirst,
187 // addLast, pollFirst, pollLast. The other methods are defined in
191 * Inserts the specified element at the front of this deque.
193 * @param e the element to add
194 * @throws NullPointerException if the specified element is null
196 public void addFirst(Object/*E*/ e) {
198 throw new NullPointerException();
199 elements[head = (head - 1) & (elements.length - 1)] = e;
205 * Inserts the specified element at the end of this deque.
207 * <p>This method is equivalent to {@link #add}.
209 * @param e the element to add
210 * @throws NullPointerException if the specified element is null
212 public void addLast(Object/*E*/ e) {
214 throw new NullPointerException();
216 if ( (tail = (tail + 1) & (elements.length - 1)) == head)
221 * Inserts the specified element at the front of this deque.
223 * @param e the element to add
224 * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
225 * @throws NullPointerException if the specified element is null
227 public boolean offerFirst(Object/*E*/ e) {
233 * Inserts the specified element at the end of this deque.
235 * @param e the element to add
236 * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
237 * @throws NullPointerException if the specified element is null
239 public boolean offerLast(Object/*E*/ e) {
245 * @throws NoSuchElementException {@inheritDoc}
247 public Object/*E*/ removeFirst() {
248 Object/*E*/ x = pollFirst();
250 throw new NoSuchElementException();
255 * @throws NoSuchElementException {@inheritDoc}
257 public Object/*E*/ removeLast() {
258 Object/*E*/ x = pollLast();
260 throw new NoSuchElementException();
264 public Object/*E*/ pollFirst() {
266 Object/*E*/ result = elements[h]; // Element is null if deque empty
269 elements[h] = null; // Must null out slot
270 head = (h + 1) & (elements.length - 1);
274 public Object/*E*/ pollLast() {
275 int t = (tail - 1) & (elements.length - 1);
276 Object/*E*/ result = elements[t];
285 * @throws NoSuchElementException {@inheritDoc}
287 public Object/*E*/ getFirst() {
288 Object/*E*/ x = elements[head];
290 throw new NoSuchElementException();
295 * @throws NoSuchElementException {@inheritDoc}
297 public Object/*E*/ getLast() {
298 Object/*E*/ x = elements[(tail - 1) & (elements.length - 1)];
300 throw new NoSuchElementException();
304 public Object/*E*/ peekFirst() {
305 return elements[head]; // elements[head] is null if deque empty
308 public Object/*E*/ peekLast() {
309 return elements[(tail - 1) & (elements.length - 1)];
313 * Removes the first occurrence of the specified element in this
314 * deque (when traversing the deque from head to tail).
315 * If the deque does not contain the element, it is unchanged.
316 * More formally, removes the first element <tt>e</tt> such that
317 * <tt>o.equals(e)</tt> (if such an element exists).
318 * Returns <tt>true</tt> if this deque contained the specified element
319 * (or equivalently, if this deque changed as a result of the call).
321 * @param o element to be removed from this deque, if present
322 * @return <tt>true</tt> if the deque contained the specified element
324 public boolean removeFirstOccurrence(Object o) {
327 int mask = elements.length - 1;
330 while ( (x = elements[i]) != null) {
341 * Removes the last occurrence of the specified element in this
342 * deque (when traversing the deque from head to tail).
343 * If the deque does not contain the element, it is unchanged.
344 * More formally, removes the last element <tt>e</tt> such that
345 * <tt>o.equals(e)</tt> (if such an element exists).
346 * Returns <tt>true</tt> if this deque contained the specified element
347 * (or equivalently, if this deque changed as a result of the call).
349 * @param o element to be removed from this deque, if present
350 * @return <tt>true</tt> if the deque contained the specified element
352 public boolean removeLastOccurrence(Object o) {
355 int mask = elements.length - 1;
356 int i = (tail - 1) & mask;
358 while ( (x = elements[i]) != null) {
368 // *** Queue methods ***
371 * Inserts the specified element at the end of this deque.
373 * <p>This method is equivalent to {@link #addLast}.
375 * @param e the element to add
376 * @return <tt>true</tt> (as specified by {@link Collection#add})
377 * @throws NullPointerException if the specified element is null
379 public boolean add(Object/*E*/ e) {
385 * Inserts the specified element at the end of this deque.
387 * <p>This method is equivalent to {@link #offerLast}.
389 * @param e the element to add
390 * @return <tt>true</tt> (as specified by {@link Queue#offer})
391 * @throws NullPointerException if the specified element is null
393 public boolean offer(Object/*E*/ e) {
398 * Retrieves and removes the head of the queue represented by this deque.
400 * This method differs from {@link #poll poll} only in that it throws an
401 * exception if this deque is empty.
403 * <p>This method is equivalent to {@link #removeFirst}.
405 * @return the head of the queue represented by this deque
406 * @throws NoSuchElementException {@inheritDoc}
408 public Object/*E*/ remove() {
409 return removeFirst();
413 * Retrieves and removes the head of the queue represented by this deque
414 * (in other words, the first element of this deque), or returns
415 * <tt>null</tt> if this deque is empty.
417 * <p>This method is equivalent to {@link #pollFirst}.
419 * @return the head of the queue represented by this deque, or
420 * <tt>null</tt> if this deque is empty
422 public Object/*E*/ poll() {
427 * Retrieves, but does not remove, the head of the queue represented by
428 * this deque. This method differs from {@link #peek peek} only in
429 * that it throws an exception if this deque is empty.
431 * <p>This method is equivalent to {@link #getFirst}.
433 * @return the head of the queue represented by this deque
434 * @throws NoSuchElementException {@inheritDoc}
436 public Object/*E*/ element() {
441 * Retrieves, but does not remove, the head of the queue represented by
442 * this deque, or returns <tt>null</tt> if this deque is empty.
444 * <p>This method is equivalent to {@link #peekFirst}.
446 * @return the head of the queue represented by this deque, or
447 * <tt>null</tt> if this deque is empty
449 public Object/*E*/ peek() {
453 // *** Stack methods ***
456 * Pushes an element onto the stack represented by this deque. In other
457 * words, inserts the element at the front of this deque.
459 * <p>This method is equivalent to {@link #addFirst}.
461 * @param e the element to push
462 * @throws NullPointerException if the specified element is null
464 public void push(Object/*E*/ e) {
469 * Pops an element from the stack represented by this deque. In other
470 * words, removes and returns the first element of this deque.
472 * <p>This method is equivalent to {@link #removeFirst()}.
474 * @return the element at the front of this deque (which is the top
475 * of the stack represented by this deque)
476 * @throws NoSuchElementException {@inheritDoc}
478 public Object/*E*/ pop() {
479 return removeFirst();
482 /*private void checkInvariants() {
483 assert elements[tail] == null;
484 assert head == tail ? elements[head] == null :
485 (elements[head] != null &&
486 elements[(tail - 1) & (elements.length - 1)] != null);
487 assert elements[(head - 1) & (elements.length - 1)] == null;
491 * Removes the element at the specified position in the elements array,
492 * adjusting head and tail as necessary. This can result in motion of
493 * elements backwards or forwards in the array.
495 * <p>This method is called delete rather than remove to emphasize
496 * that its semantics differ from those of {@link List#remove(int)}.
498 * @return true if elements moved backwards
500 private boolean delete(int i) {
502 final Object/*E*/[] elements = this.elements;
503 final int mask = elements.length - 1;
506 final int front = (i - h) & mask;
507 final int back = (t - i) & mask;
509 // Invariant: head <= i < tail mod circularity
510 if (front >= ((t - h) & mask))
511 throw new ConcurrentModificationException();
513 // Optimize for least element motion
516 System.arraycopy(elements, h, elements, h + 1, front);
517 } else { // Wrap around
518 System.arraycopy(elements, 0, elements, 1, i);
519 elements[0] = elements[mask];
520 System.arraycopy(elements, h, elements, h + 1, mask - h);
523 head = (h + 1) & mask;
526 if (i < t) { // Copy the null tail as well
527 System.arraycopy(elements, i + 1, elements, i, back);
529 } else { // Wrap around
530 System.arraycopy(elements, i + 1, elements, i, mask - i);
531 elements[mask] = elements[0];
532 System.arraycopy(elements, 1, elements, 0, t);
533 tail = (t - 1) & mask;
539 // *** Collection Methods ***
542 * Returns the number of elements in this deque.
544 * @return the number of elements in this deque
547 return (tail - head) & (elements.length - 1);
551 * Returns <tt>true</tt> if this deque contains no elements.
553 * @return <tt>true</tt> if this deque contains no elements
555 public boolean isEmpty() {
560 * Returns an iterator over the elements in this deque. The elements
561 * will be ordered from first (head) to last (tail). This is the same
562 * order that elements would be dequeued (via successive calls to
563 * {@link #remove} or popped (via successive calls to {@link #pop}).
565 * @return an iterator over the elements in this deque
567 public Iterator/*<E>*/ iterator() {
568 return new DeqIterator();
571 public Iterator/*<E>*/ descendingIterator() {
572 return new DescendingIterator();
575 private class DeqIterator implements Iterator/*<E>*/ {
577 * Index of element to be returned by subsequent call to next.
579 private int cursor = head;
582 * Tail recorded at construction (also in remove), to stop
583 * iterator and also to check for comodification.
585 private int fence = tail;
588 * Index of element returned by most recent call to next.
589 * Reset to -1 if element is deleted by a call to remove.
591 private int lastRet = -1;
593 public DeqIterator() {}
595 public boolean hasNext() {
596 return cursor != fence;
599 public Object/*E*/ next() {
601 throw new NoSuchElementException();
602 Object/*E*/ result = elements[cursor];
603 // This check doesn't catch all possible comodifications,
604 // but does catch the ones that corrupt traversal
605 if (tail != fence || result == null)
606 throw new ConcurrentModificationException();
608 cursor = (cursor + 1) & (elements.length - 1);
612 public void remove() {
614 throw new IllegalStateException();
615 if (delete(lastRet)) { // if left-shifted, undo increment in next()
616 cursor = (cursor - 1) & (elements.length - 1);
623 private class DescendingIterator implements Iterator/*<E>*/ {
625 * This class is nearly a mirror-image of DeqIterator, using
626 * tail instead of head for initial cursor, and head instead of
629 private int cursor = tail;
630 private int fence = head;
631 private int lastRet = -1;
633 public boolean hasNext() {
634 return cursor != fence;
637 public Object/*E*/ next() {
639 throw new NoSuchElementException();
640 cursor = (cursor - 1) & (elements.length - 1);
641 Object/*E*/ result = elements[cursor];
642 if (head != fence || result == null)
643 throw new ConcurrentModificationException();
648 public void remove() {
650 throw new IllegalStateException();
651 if (!delete(lastRet)) {
652 cursor = (cursor + 1) & (elements.length - 1);
660 * Returns <tt>true</tt> if this deque contains the specified element.
661 * More formally, returns <tt>true</tt> if and only if this deque contains
662 * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
664 * @param o object to be checked for containment in this deque
665 * @return <tt>true</tt> if this deque contains the specified element
667 public boolean contains(Object o) {
670 int mask = elements.length - 1;
673 while ( (x = elements[i]) != null) {
682 * Removes a single instance of the specified element from this deque.
683 * If the deque does not contain the element, it is unchanged.
684 * More formally, removes the first element <tt>e</tt> such that
685 * <tt>o.equals(e)</tt> (if such an element exists).
686 * Returns <tt>true</tt> if this deque contained the specified element
687 * (or equivalently, if this deque changed as a result of the call).
689 * <p>This method is equivalent to {@link #removeFirstOccurrence}.
691 * @param o element to be removed from this deque, if present
692 * @return <tt>true</tt> if this deque contained the specified element
694 public boolean remove(Object o) {
695 return removeFirstOccurrence(o);
699 * Removes all of the elements from this deque.
700 * The deque will be empty after this call returns.
702 public void clear() {
705 if (h != t) { // clear all cells
708 int mask = elements.length - 1;
717 * Returns an array containing all of the elements in this deque
718 * in proper sequence (from first to last element).
720 * <p>The returned array will be "safe" in that no references to it are
721 * maintained by this deque. (In other words, this method must allocate
722 * a new array). The caller is thus free to modify the returned array.
724 * <p>This method acts as bridge between array-based and collection-based
727 * @return an array containing all of the elements in this deque
729 public Object[] toArray() {
730 return copyElements(new Object[size()]);
734 * Returns an array containing all of the elements in this deque in
735 * proper sequence (from first to last element); the runtime type of the
736 * returned array is that of the specified array. If the deque fits in
737 * the specified array, it is returned therein. Otherwise, a new array
738 * is allocated with the runtime type of the specified array and the
739 * size of this deque.
741 * <p>If this deque fits in the specified array with room to spare
742 * (i.e., the array has more elements than this deque), the element in
743 * the array immediately following the end of the deque is set to
746 * <p>Like the {@link #toArray()} method, this method acts as bridge between
747 * array-based and collection-based APIs. Further, this method allows
748 * precise control over the runtime type of the output array, and may,
749 * under certain circumstances, be used to save allocation costs.
751 * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
752 * The following code can be used to dump the deque into a newly
753 * allocated array of <tt>String</tt>:
756 * String[] y = x.toArray(new String[0]);</pre>
758 * Note that <tt>toArray(new Object[0])</tt> is identical in function to
759 * <tt>toArray()</tt>.
761 * @param a the array into which the elements of the deque are to
762 * be stored, if it is big enough; otherwise, a new array of the
763 * same runtime type is allocated for this purpose
764 * @return an array containing all of the elements in this deque
765 * @throws ArrayStoreException if the runtime type of the specified array
766 * is not a supertype of the runtime type of every element in
768 * @throws NullPointerException if the specified array is null
770 public /*<T> T*/Object[] toArray(Object/*T*/[] a) {
773 a = new Object[size]/*(T[])java.lang.reflect.Array.newInstance(
774 a.getClass().getComponentType(), size)*/;
781 // *** Object methods ***
784 * Returns a copy of this deque.
786 * @return a copy of this deque
788 /*public ArrayDeque<E> clone() {
790 ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
791 // Classpath local: we don't have Arrays.copyOf yet.
792 // result.elements = Arrays.copyOf(elements, elements.length);
793 result.elements = elements.clone();
796 } catch (CloneNotSupportedException e) {
797 throw new AssertionError();
802 * Appease the serialization gods.
804 private static final long serialVersionUID = 2340985798034038923L;
807 * Serialize this deque.
809 * @serialData The current size (<tt>int</tt>) of the deque,
810 * followed by all of its elements (each an object reference) in
811 * first-to-last order.
813 /*private void writeObject(ObjectOutputStream s) throws IOException {
814 s.defaultWriteObject();
819 // Write out elements in order.
820 int mask = elements.length - 1;
821 for (int i = head; i != tail; i = (i + 1) & mask)
822 s.writeObject(elements[i]);
826 * Deserialize this deque.
828 /*private void readObject(ObjectInputStream s)
829 throws IOException, ClassNotFoundException {
830 s.defaultReadObject();
832 // Read in size and allocate array
833 int size = s.readInt();
834 allocateElements(size);
838 // Read in all elements in the proper order.
839 for (int i = 0; i < size; i++)
840 elements[i] = (E)s.readObject();