Most ArrayDeque operations run in amortized constant time. + *
Most {@code ArrayDeque} operations run in amortized constant time. * Exceptions include {@link #remove(Object) remove}, {@link * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence * removeLastOccurrence}, {@link #contains contains}, {@link #iterator * iterator.remove()}, and the bulk operations, all of which run in linear * time. * - *
The iterators returned by this class's iterator method are + *
The iterators returned by this class's {@code iterator} method are * fail-fast: If the deque is modified at any time after the iterator - * is created, in any way except through the iterator's own remove + * is created, in any way except through the iterator's own {@code remove} * method, the iterator will generally throw a {@link * ConcurrentModificationException}. Thus, in the face of concurrent * modification, the iterator fails quickly and cleanly, rather than risking @@ -63,7 +69,7 @@ *
Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification. Fail-fast iterators - * throw ConcurrentModificationException on a best-effort basis. + * throw {@code ConcurrentModificationException} on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: the fail-fast behavior of iterators * should be used only to detect bugs. @@ -93,7 +99,7 @@ * other. We also guarantee that all array cells not holding * deque elements are always null. */ - private transient E[] elements; + private transient Object[] elements; /** * The index of the element at the head of the deque (which is the @@ -116,12 +122,7 @@ // ****** Array allocation and resizing utilities ****** - /** - * Allocate empty array to hold the given number of elements. - * - * @param numElements the number of elements to hold - */ - private void allocateElements(int numElements) { + private static int calculateSize(int numElements) { int initialCapacity = MIN_INITIAL_CAPACITY; // Find the best power of two to hold elements. // Tests "<=" because arrays aren't kept full. @@ -137,11 +138,20 @@ if (initialCapacity < 0) // Too many elements, must back off initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements } - elements = (E[]) new Object[initialCapacity]; + return initialCapacity; } /** - * Double the capacity of this deque. Call only when full, i.e., + * Allocates empty array to hold the given number of elements. + * + * @param numElements the number of elements to hold + */ + private void allocateElements(int numElements) { + elements = new Object[calculateSize(numElements)]; + } + + /** + * Doubles the capacity of this deque. Call only when full, i.e., * when head and tail have wrapped around to become equal. */ private void doubleCapacity() { @@ -183,7 +193,7 @@ * sufficient to hold 16 elements. */ public ArrayDeque() { - elements = (E[]) new Object[16]; + elements = new Object[16]; } /** @@ -249,7 +259,7 @@ * Inserts the specified element at the front of this deque. * * @param e the element to add - * @return true (as specified by {@link Deque#offerFirst}) + * @return {@code true} (as specified by {@link Deque#offerFirst}) * @throws NullPointerException if the specified element is null */ public boolean offerFirst(E e) { @@ -261,7 +271,7 @@ * Inserts the specified element at the end of this deque. * * @param e the element to add - * @return true (as specified by {@link Deque#offerLast}) + * @return {@code true} (as specified by {@link Deque#offerLast}) * @throws NullPointerException if the specified element is null */ public boolean offerLast(E e) { @@ -291,7 +301,9 @@ public E pollFirst() { int h = head; - E result = elements[h]; // Element is null if deque empty + @SuppressWarnings("unchecked") + E result = (E) elements[h]; + // Element is null if deque empty if (result == null) return null; elements[h] = null; // Must null out slot @@ -301,7 +313,8 @@ public E pollLast() { int t = (tail - 1) & (elements.length - 1); - E result = elements[t]; + @SuppressWarnings("unchecked") + E result = (E) elements[t]; if (result == null) return null; elements[t] = null; @@ -313,48 +326,53 @@ * @throws NoSuchElementException {@inheritDoc} */ public E getFirst() { - E x = elements[head]; - if (x == null) + @SuppressWarnings("unchecked") + E result = (E) elements[head]; + if (result == null) throw new NoSuchElementException(); - return x; + return result; } /** * @throws NoSuchElementException {@inheritDoc} */ public E getLast() { - E x = elements[(tail - 1) & (elements.length - 1)]; - if (x == null) + @SuppressWarnings("unchecked") + E result = (E) elements[(tail - 1) & (elements.length - 1)]; + if (result == null) throw new NoSuchElementException(); - return x; + return result; } + @SuppressWarnings("unchecked") public E peekFirst() { - return elements[head]; // elements[head] is null if deque empty + // elements[head] is null if deque empty + return (E) elements[head]; } + @SuppressWarnings("unchecked") public E peekLast() { - return elements[(tail - 1) & (elements.length - 1)]; + return (E) elements[(tail - 1) & (elements.length - 1)]; } /** * Removes the first occurrence of the specified element in this * deque (when traversing the deque from head to tail). * If the deque does not contain the element, it is unchanged. - * More formally, removes the first element e such that - * o.equals(e) (if such an element exists). - * Returns true if this deque contained the specified element + * More formally, removes the first element {@code e} such that + * {@code o.equals(e)} (if such an element exists). + * Returns {@code true} if this deque contained the specified element * (or equivalently, if this deque changed as a result of the call). * * @param o element to be removed from this deque, if present - * @return true if the deque contained the specified element + * @return {@code true} if the deque contained the specified element */ public boolean removeFirstOccurrence(Object o) { if (o == null) return false; int mask = elements.length - 1; int i = head; - E x; + Object x; while ( (x = elements[i]) != null) { if (o.equals(x)) { delete(i); @@ -369,20 +387,20 @@ * Removes the last occurrence of the specified element in this * deque (when traversing the deque from head to tail). * If the deque does not contain the element, it is unchanged. - * More formally, removes the last element e such that - * o.equals(e) (if such an element exists). - * Returns true if this deque contained the specified element + * More formally, removes the last element {@code e} such that + * {@code o.equals(e)} (if such an element exists). + * Returns {@code true} if this deque contained the specified element * (or equivalently, if this deque changed as a result of the call). * * @param o element to be removed from this deque, if present - * @return true if the deque contained the specified element + * @return {@code true} if the deque contained the specified element */ public boolean removeLastOccurrence(Object o) { if (o == null) return false; int mask = elements.length - 1; int i = (tail - 1) & mask; - E x; + Object x; while ( (x = elements[i]) != null) { if (o.equals(x)) { delete(i); @@ -401,7 +419,7 @@ *
This method is equivalent to {@link #addLast}. * * @param e the element to add - * @return true (as specified by {@link Collection#add}) + * @return {@code true} (as specified by {@link Collection#add}) * @throws NullPointerException if the specified element is null */ public boolean add(E e) { @@ -415,7 +433,7 @@ *
This method is equivalent to {@link #offerLast}. * * @param e the element to add - * @return true (as specified by {@link Queue#offer}) + * @return {@code true} (as specified by {@link Queue#offer}) * @throws NullPointerException if the specified element is null */ public boolean offer(E e) { @@ -440,12 +458,12 @@ /** * Retrieves and removes the head of the queue represented by this deque * (in other words, the first element of this deque), or returns - * null if this deque is empty. + * {@code null} if this deque is empty. * *
This method is equivalent to {@link #pollFirst}. * * @return the head of the queue represented by this deque, or - * null if this deque is empty + * {@code null} if this deque is empty */ public E poll() { return pollFirst(); @@ -467,12 +485,12 @@ /** * Retrieves, but does not remove, the head of the queue represented by - * this deque, or returns null if this deque is empty. + * this deque, or returns {@code null} if this deque is empty. * *
This method is equivalent to {@link #peekFirst}. * * @return the head of the queue represented by this deque, or - * null if this deque is empty + * {@code null} if this deque is empty */ public E peek() { return peekFirst(); @@ -527,7 +545,7 @@ */ private boolean delete(int i) { checkInvariants(); - final E[] elements = this.elements; + final Object[] elements = this.elements; final int mask = elements.length - 1; final int h = head; final int t = tail; @@ -576,9 +594,9 @@ } /** - * Returns true if this deque contains no elements. + * Returns {@code true} if this deque contains no elements. * - * @return true if this deque contains no elements + * @return {@code true} if this deque contains no elements */ public boolean isEmpty() { return head == tail; @@ -625,7 +643,8 @@ public E next() { if (cursor == fence) throw new NoSuchElementException(); - E result = elements[cursor]; + @SuppressWarnings("unchecked") + E result = (E) elements[cursor]; // This check doesn't catch all possible comodifications, // but does catch the ones that corrupt traversal if (tail != fence || result == null) @@ -664,7 +683,8 @@ if (cursor == fence) throw new NoSuchElementException(); cursor = (cursor - 1) & (elements.length - 1); - E result = elements[cursor]; + @SuppressWarnings("unchecked") + E result = (E) elements[cursor]; if (head != fence || result == null) throw new ConcurrentModificationException(); lastRet = cursor; @@ -683,19 +703,19 @@ } /** - * Returns true if this deque contains the specified element. - * More formally, returns true if and only if this deque contains - * at least one element e such that o.equals(e). + * Returns {@code true} if this deque contains the specified element. + * More formally, returns {@code true} if and only if this deque contains + * at least one element {@code e} such that {@code o.equals(e)}. * * @param o object to be checked for containment in this deque - * @return true if this deque contains the specified element + * @return {@code true} if this deque contains the specified element */ public boolean contains(Object o) { if (o == null) return false; int mask = elements.length - 1; int i = head; - E x; + Object x; while ( (x = elements[i]) != null) { if (o.equals(x)) return true; @@ -707,15 +727,15 @@ /** * Removes a single instance of the specified element from this deque. * If the deque does not contain the element, it is unchanged. - * More formally, removes the first element e such that - * o.equals(e) (if such an element exists). - * Returns true if this deque contained the specified element + * More formally, removes the first element {@code e} such that + * {@code o.equals(e)} (if such an element exists). + * Returns {@code true} if this deque contained the specified element * (or equivalently, if this deque changed as a result of the call). * - *
This method is equivalent to {@link #removeFirstOccurrence}. + *
This method is equivalent to {@link #removeFirstOccurrence(Object)}. * * @param o element to be removed from this deque, if present - * @return true if this deque contained the specified element + * @return {@code true} if this deque contained the specified element */ public boolean remove(Object o) { return removeFirstOccurrence(o); @@ -767,22 +787,21 @@ *
If this deque fits in the specified array with room to spare * (i.e., the array has more elements than this deque), the element in * the array immediately following the end of the deque is set to - * null. + * {@code null}. * *
Like the {@link #toArray()} method, this method acts as bridge between * array-based and collection-based APIs. Further, this method allows * precise control over the runtime type of the output array, and may, * under certain circumstances, be used to save allocation costs. * - *
Suppose x is a deque known to contain only strings. + *
Suppose {@code x} is a deque known to contain only strings. * The following code can be used to dump the deque into a newly - * allocated array of String: + * allocated array of {@code String}: * - *
- * String[] y = x.toArray(new String[0]);+ *
{@code String[] y = x.toArray(new String[0]);}
*
- * Note that toArray(new Object[0]) is identical in function to
- * toArray().
+ * Note that {@code toArray(new Object[0])} is identical in function to
+ * {@code toArray()}.
*
* @param a the array into which the elements of the deque are to
* be stored, if it is big enough; otherwise, a new array of the
@@ -813,10 +832,10 @@
*/
public ArrayDeque