--- jsr166/src/jsr166x/ArrayDeque.java 2004/12/26 20:13:15 1.2 +++ jsr166/src/jsr166x/ArrayDeque.java 2013/01/16 00:51:11 1.11 @@ -1,6 +1,6 @@ /* * Written by Josh Bloch of Google Inc. and released to the public domain, - * as explained at http://creativecommons.org/licenses/publicdomain. + * as explained at http://creativecommons.org/publicdomain/zero/1.0/. */ package jsr166x; // XXX This belongs in java.util!!! XXX @@ -13,17 +13,17 @@ import java.io.*; * usage. They are not thread-safe; in the absence of external * synchronization, they do not support concurrent access by multiple threads. * Null elements are prohibited. This class is likely to be faster than - * {@link Stack} when used as as a stack, and faster than {@link LinkedList} + * {@link Stack} when used as a stack, and faster than {@link LinkedList} * when used as a queue. * - *

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 method, the * iterator will generally throw a {@link ConcurrentModificationException}. @@ -34,7 +34,7 @@ import java.io.*; *

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. @@ -86,11 +86,11 @@ public class ArrayDeque extends Abstr // ****** Array allocation and resizing utilities ****** /** - * Allocate empty array to hold the given number of elements. + * Allocates empty array to hold the given number of elements. * - * @param numElements the number of elements to hold. + * @param numElements the number of elements to hold */ - private void allocateElements(int numElements) { + private void allocateElements(int numElements) { int initialCapacity = MIN_INITIAL_CAPACITY; // Find the best power of two to hold elements. // Tests "<=" because arrays aren't kept full. @@ -110,11 +110,11 @@ public class ArrayDeque extends Abstr } /** - * Double the capacity of this deque. Call only when full, i.e., + * 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() { - assert head == tail; + assert head == tail; int p = head; int n = elements.length; int r = n - p; // number of elements to the right of p @@ -130,7 +130,7 @@ public class ArrayDeque extends Abstr } /** - * Copy the elements from our element array into the specified array, + * Copies the elements from our element array into the specified array, * in order (from first to last element in the deque). It is assumed * that the array is large enough to hold all elements in the deque. * @@ -188,13 +188,13 @@ public class ArrayDeque extends Abstr * Inserts the specified element to the front this deque. * * @param e the element to insert - * @throws NullPointerException if e is null + * @throws NullPointerException if {@code e} is null */ public void addFirst(E e) { if (e == null) throw new NullPointerException(); elements[head = (head - 1) & (elements.length - 1)] = e; - if (head == tail) + if (head == tail) doubleCapacity(); } @@ -204,7 +204,7 @@ public class ArrayDeque extends Abstr * {@link #push}. * * @param e the element to insert - * @throws NullPointerException if e is null + * @throws NullPointerException if {@code e} is null */ public void addLast(E e) { if (e == null) @@ -216,9 +216,9 @@ public class ArrayDeque extends Abstr /** * Retrieves and removes the first element of this deque, or - * null if this deque is empty. + * {@code null} if this deque is empty. * - * @return the first element of this deque, or null if + * @return the first element of this deque, or {@code null} if * this deque is empty */ public E pollFirst() { @@ -233,9 +233,9 @@ public class ArrayDeque extends Abstr /** * Retrieves and removes the last element of this deque, or - * null if this deque is empty. + * {@code null} if this deque is empty. * - * @return the last element of this deque, or null if + * @return the last element of this deque, or {@code null} if * this deque is empty */ public E pollLast() { @@ -243,7 +243,7 @@ public class ArrayDeque extends Abstr E result = elements[t]; if (result == null) return null; - elements[t] = null; + elements[t] = null; tail = t; return result; } @@ -252,8 +252,8 @@ public class ArrayDeque extends Abstr * Inserts the specified element to the front this deque. * * @param e the element to insert - * @return true (as per the spec for {@link Deque#offerFirst}) - * @throws NullPointerException if e is null + * @return {@code true} (as per the spec for {@link Deque#offerFirst}) + * @throws NullPointerException if {@code e} is null */ public boolean offerFirst(E e) { addFirst(e); @@ -264,8 +264,8 @@ public class ArrayDeque extends Abstr * Inserts the specified element to the end this deque. * * @param e the element to insert - * @return true (as per the spec for {@link Deque#offerLast}) - * @throws NullPointerException if e is null + * @return {@code true} (as per the spec for {@link Deque#offerLast}) + * @throws NullPointerException if {@code e} is null */ public boolean offerLast(E e) { addLast(e); @@ -274,7 +274,7 @@ public class ArrayDeque extends Abstr /** * Retrieves and removes the first element of this deque. This method - * differs from the pollFirst method in that it throws an + * differs from the {@code pollFirst} method in that it throws an * exception if this deque is empty. * * @return the first element of this deque @@ -289,7 +289,7 @@ public class ArrayDeque extends Abstr /** * Retrieves and removes the last element of this deque. This method - * differs from the pollLast method in that it throws an + * differs from the {@code pollLast} method in that it throws an * exception if this deque is empty. * * @return the last element of this deque @@ -304,9 +304,9 @@ public class ArrayDeque extends Abstr /** * Retrieves, but does not remove, the first element of this deque, - * returning null if this deque is empty. + * returning {@code null} if this deque is empty. * - * @return the first element of this deque, or null if + * @return the first element of this deque, or {@code null} if * this deque is empty */ public E peekFirst() { @@ -315,9 +315,9 @@ public class ArrayDeque extends Abstr /** * Retrieves, but does not remove, the last element of this deque, - * returning null if this deque is empty. + * returning {@code null} if this deque is empty. * - * @return the last element of this deque, or null if this deque + * @return the last element of this deque, or {@code null} if this deque * is empty */ public E peekLast() { @@ -326,7 +326,7 @@ public class ArrayDeque extends Abstr /** * Retrieves, but does not remove, the first element of this - * deque. This method differs from the peek method only + * deque. This method differs from the {@code peek} method only * in that it throws an exception if this deque is empty. * * @return the first element of this deque @@ -341,7 +341,7 @@ public class ArrayDeque extends Abstr /** * Retrieves, but does not remove, the last element of this - * deque. This method differs from the peek method only + * deque. This method differs from the {@code peek} method only * in that it throws an exception if this deque is empty. * * @return the last element of this deque @@ -360,7 +360,7 @@ public class ArrayDeque extends Abstr * does not contain the element, it is unchanged. * * @param e 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 e) { if (e == null) @@ -384,7 +384,7 @@ public class ArrayDeque extends Abstr * does not contain the element, it is unchanged. * * @param e 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 e) { if (e == null) @@ -410,8 +410,8 @@ public class ArrayDeque extends Abstr *

This method is equivalent to {@link #offerLast}. * * @param e the element to insert - * @return true (as per the spec for {@link Queue#offer}) - * @throws NullPointerException if e is null + * @return {@code true} (as per the spec for {@link Queue#offer}) + * @throws NullPointerException if {@code e} is null */ public boolean offer(E e) { return offerLast(e); @@ -423,8 +423,8 @@ public class ArrayDeque extends Abstr *

This method is equivalent to {@link #addLast}. * * @param e the element to insert - * @return true (as per the spec for {@link Collection#add}) - * @throws NullPointerException if e is null + * @return {@code true} (as per the spec for {@link Collection#add}) + * @throws NullPointerException if {@code e} is null */ public boolean add(E e) { addLast(e); @@ -433,13 +433,13 @@ public class ArrayDeque extends Abstr /** * Retrieves and removes the head of the queue represented by - * this deque, or null if this deque is empty. In other words, - * retrieves and removes the first element of this deque, or null + * this deque, or {@code null} if this deque is empty. In other words, + * retrieves and removes the first element of this deque, or {@code null} * if this deque is empty. * *

This method is equivalent to {@link #pollFirst}. * - * @return the first element of this deque, or null if + * @return the first element of this deque, or {@code null} if * this deque is empty */ public E poll() { @@ -448,7 +448,7 @@ public class ArrayDeque extends Abstr /** * Retrieves and removes the head of the queue represented by this deque. - * This method differs from the poll method in that it throws an + * This method differs from the {@code poll} method in that it throws an * exception if this deque is empty. * *

This method is equivalent to {@link #removeFirst}. @@ -462,12 +462,12 @@ public class ArrayDeque extends Abstr /** * Retrieves, but does not remove, the head of the queue represented by - * this deque, returning null if this deque is empty. + * this deque, returning {@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(); @@ -475,7 +475,7 @@ public class ArrayDeque extends Abstr /** * Retrieves, but does not remove, the head of the queue represented by - * this deque. This method differs from the peek method only in + * this deque. This method differs from the {@code peek} method only in * that it throws an exception if this deque is empty. * *

This method is equivalent to {@link #getFirst} @@ -496,7 +496,7 @@ public class ArrayDeque extends Abstr *

This method is equivalent to {@link #addFirst}. * * @param e the element to push - * @throws NullPointerException if e is null + * @throws NullPointerException if {@code e} is null */ public void push(E e) { addFirst(e); @@ -504,7 +504,7 @@ public class ArrayDeque extends Abstr /** * Pops an element from the stack represented by this deque. In other - * words, removes and returns the the first element of this deque. + * words, removes and returns the first element of this deque. * *

This method is equivalent to {@link #removeFirst()}. * @@ -517,13 +517,13 @@ public class ArrayDeque extends Abstr } /** - * Remove the element at the specified position in the elements array, + * Removes the element at the specified position in the elements array, * adjusting head, tail, and size as necessary. This can result in * motion of elements backwards or forwards in the array. * *

This method is called delete rather than remove to emphasize the * that that its semantics differ from those of List.remove(int). - * + * * @return true if elements moved backwards */ private boolean delete(int i) { @@ -555,9 +555,9 @@ public class ArrayDeque extends Abstr } /** - * Returns true if this collection contains no elements.

+ * Returns {@code true} if this collection contains no elements. * - * @return true if this collection contains no elements. + * @return {@code true} if this collection contains no elements */ public boolean isEmpty() { return head == tail; @@ -568,8 +568,8 @@ public class ArrayDeque extends Abstr * will be ordered from first (head) to last (tail). This is the same * order that elements would be dequeued (via successive calls to * {@link #remove} or popped (via successive calls to {@link #pop}). - * - * @return an Iterator over the elements in this deque + * + * @return an {@code Iterator} over the elements in this deque */ public Iterator iterator() { return new DeqIterator(); @@ -621,13 +621,13 @@ public class ArrayDeque extends Abstr } /** - * 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 - * e.equals(o). + * 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 e.equals(o)}. * * @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) @@ -648,7 +648,7 @@ public class ArrayDeque extends Abstr * This method is equivalent to {@link #removeFirstOccurrence}. * * @param e 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 e) { return removeFirstOccurrence(e); @@ -667,7 +667,7 @@ public class ArrayDeque extends Abstr do { elements[i] = null; i = (i + 1) & mask; - } while(i != t); + } while (i != t); } } @@ -676,10 +676,10 @@ public class ArrayDeque extends Abstr * in the correct order. * * @return an array containing all of the elements in this list - * in the correct order + * in the correct order */ public Object[] toArray() { - return copyElements(new Object[size()]); + return copyElements(new Object[size()]); } /** @@ -691,11 +691,11 @@ public class ArrayDeque extends Abstr * *

If the deque fits in the specified array with room to spare (i.e., * the array has more elements than the deque), the element in the array - * immediately following the end of the collection is set to null. + * immediately following the end of the collection is set to {@code null}. * * @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 - * same runtime type is allocated for this purpose + * be stored, if it is big enough; otherwise, a new array of the + * same runtime type is allocated for this purpose * @return an array containing the elements of the deque * @throws ArrayStoreException if the runtime type of a is not a supertype * of the runtime type of every element in this deque @@ -705,7 +705,7 @@ public class ArrayDeque extends Abstr if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); - copyElements(a); + copyElements(a); if (a.length > size) a[size] = null; return a; @@ -719,14 +719,14 @@ public class ArrayDeque extends Abstr * @return a copy of this deque */ public ArrayDeque clone() { - try { + try { ArrayDeque result = (ArrayDeque) super.clone(); // These two lines are currently faster than cloning the array: result.elements = (E[]) new Object[elements.length]; System.arraycopy(elements, 0, result.elements, 0, elements.length); return result; - } catch (CloneNotSupportedException e) { + } catch (CloneNotSupportedException e) { throw new AssertionError(); } } @@ -737,9 +737,9 @@ public class ArrayDeque extends Abstr private static final long serialVersionUID = 2340985798034038923L; /** - * Serialize this deque. + * Serializes this deque. * - * @serialData The current size (int) of the deque, + * @serialData The current size ({@code int}) of the deque, * followed by all of its elements (each an object reference) in * first-to-last order. */ @@ -760,7 +760,7 @@ public class ArrayDeque extends Abstr } /** - * Deserialize this deque. + * Deserializes this deque. */ private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {