--- jsr166/src/main/java/util/ArrayDeque.java 2005/05/02 04:19:58 1.8 +++ jsr166/src/main/java/util/ArrayDeque.java 2005/09/16 23:17:05 1.21 @@ -4,6 +4,7 @@ */ package java.util; +import java.util.*; // for javadoc (till 6280605 is fixed) import java.io.*; /** @@ -18,7 +19,7 @@ import java.io.*; *

Most ArrayDeque operations run in amortized constant time. * Exceptions include {@link #remove(Object) remove}, {@link * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence - * removeLastOccurrence}, {@link #contains contains }, {@link #iterator + * removeLastOccurrence}, {@link #contains contains}, {@link #iterator * iterator.remove()}, and the bulk operations, all of which run in linear * time. * @@ -40,10 +41,12 @@ import java.io.*; * should be used only to detect bugs. * *

This class and its iterator implement all of the - * optional methods of the {@link Collection} and {@link - * Iterator} interfaces. This class is a member of the Java Collections - * Framework. + * optional methods of the {@link Collection} and {@link + * Iterator} interfaces. + * + *

This class is a member of the + * + * Java Collections Framework. * * @author Josh Bloch and Doug Lea * @since 1.6 @@ -88,7 +91,7 @@ public class ArrayDeque extends Abstr /** * Allocate 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) { int initialCapacity = MIN_INITIAL_CAPACITY; @@ -187,8 +190,8 @@ public class ArrayDeque extends Abstr /** * Inserts the specified element at the front of this deque. * - * @param e the element to insert - * @throws NullPointerException if e is null + * @param e the element to add + * @throws NullPointerException if the specified element is null */ public void addFirst(E e) { if (e == null) @@ -200,11 +203,11 @@ public class ArrayDeque extends Abstr /** * Inserts the specified element at the end of this deque. - * This method is equivalent to {@link Collection#add} and - * {@link #push}. * - * @param e the element to insert - * @throws NullPointerException if e is null + *

This method is equivalent to {@link #add}. + * + * @param e the element to add + * @throws NullPointerException if the specified element is null */ public void addLast(E e) { if (e == null) @@ -215,45 +218,11 @@ public class ArrayDeque extends Abstr } /** - * Retrieves and removes the first element of this deque, or - * null if this deque is empty. - * - * @return the first element of this deque, or null if - * this deque is empty - */ - public E pollFirst() { - int h = head; - E result = elements[h]; // Element is null if deque empty - if (result == null) - return null; - elements[h] = null; // Must null out slot - head = (h + 1) & (elements.length - 1); - return result; - } - - /** - * Retrieves and removes the last element of this deque, or - * null if this deque is empty. - * - * @return the last element of this deque, or null if - * this deque is empty - */ - public E pollLast() { - int t = (tail - 1) & (elements.length - 1); - E result = elements[t]; - if (result == null) - return null; - elements[t] = null; - tail = t; - return result; - } - - /** * Inserts the specified element at the front of this deque. * - * @param e the element to insert - * @return true (as per the spec for {@link Deque#offerFirst}) - * @throws NullPointerException if e is null + * @param e the element to add + * @return true (as specified by {@link Deque#offerFirst}) + * @throws NullPointerException if the specified element is null */ public boolean offerFirst(E e) { addFirst(e); @@ -263,9 +232,9 @@ public class ArrayDeque extends Abstr /** * Inserts the specified element at the end of this deque. * - * @param e the element to insert - * @return true (as per the spec for {@link Deque#offerLast}) - * @throws NullPointerException if e is null + * @param e the element to add + * @return true (as specified by {@link Deque#offerLast}) + * @throws NullPointerException if the specified element is null */ public boolean offerLast(E e) { addLast(e); @@ -273,12 +242,7 @@ public class ArrayDeque extends Abstr } /** - * Retrieves and removes the first element of this deque. This method - * differs from the {@link #pollFirst} method only in that it throws an - * exception if this deque is empty. - * - * @return the first element of this deque - * @throws NoSuchElementException if this deque is empty + * @throws NoSuchElementException {@inheritDoc} */ public E removeFirst() { E x = pollFirst(); @@ -288,12 +252,7 @@ public class ArrayDeque extends Abstr } /** - * Retrieves and removes the last element of this deque. This method - * differs from the {@link #pollLast} method only in that it throws an - * exception if this deque is empty. - * - * @return the last element of this deque - * @throws NoSuchElementException if this deque is empty + * @throws NoSuchElementException {@inheritDoc} */ public E removeLast() { E x = pollLast(); @@ -302,35 +261,28 @@ public class ArrayDeque extends Abstr return x; } - /** - * Retrieves, but does not remove, the first element of this deque, - * returning null if this deque is empty. - * - * @return the first element of this deque, or null if - * this deque is empty - */ - public E peekFirst() { - return elements[head]; // elements[head] is null if deque empty + public E pollFirst() { + int h = head; + E result = elements[h]; // Element is null if deque empty + if (result == null) + return null; + elements[h] = null; // Must null out slot + head = (h + 1) & (elements.length - 1); + return result; } - /** - * Retrieves, but does not remove, the last element of this deque, - * returning null if this deque is empty. - * - * @return the last element of this deque, or null if this deque - * is empty - */ - public E peekLast() { - return elements[(tail - 1) & (elements.length - 1)]; + public E pollLast() { + int t = (tail - 1) & (elements.length - 1); + E result = elements[t]; + if (result == null) + return null; + elements[t] = null; + tail = t; + return result; } /** - * Retrieves, but does not remove, the first element of this - * deque. This method differs from the {@link #peekFirst} method only - * in that it throws an exception if this deque is empty. - * - * @return the first element of this deque - * @throws NoSuchElementException if this deque is empty + * @throws NoSuchElementException {@inheritDoc} */ public E getFirst() { E x = elements[head]; @@ -340,12 +292,7 @@ public class ArrayDeque extends Abstr } /** - * Retrieves, but does not remove, the last element of this - * deque. This method differs from the {@link #peekLast} method only - * in that it throws an exception if this deque is empty. - * - * @return the last element of this deque - * @throws NoSuchElementException if this deque is empty + * @throws NoSuchElementException {@inheritDoc} */ public E getLast() { E x = elements[(tail - 1) & (elements.length - 1)]; @@ -354,12 +301,22 @@ public class ArrayDeque extends Abstr return x; } + public E peekFirst() { + return elements[head]; // elements[head] is null if deque empty + } + + public E peekLast() { + return 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). More - * formally, removes the first element e such that (o==null ? - * e==null : o.equals(e)). If the deque does not contain the - * element, it is unchanged. + * 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 + * (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 @@ -382,10 +339,12 @@ public class ArrayDeque extends Abstr /** * Removes the last occurrence of the specified element in this - * deque (when traversing the deque from head to tail). More - * formally, removes the last element e such that (o==null ? - * e==null : o.equals(e)). If the deque - * does not contain the element, it is unchanged. + * 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 + * (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 @@ -411,24 +370,11 @@ public class ArrayDeque extends Abstr /** * Inserts the specified element at the end of this deque. * - *

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 - */ - public boolean offer(E e) { - return offerLast(e); - } - - /** - * Inserts the specified element at the end of this deque. - * *

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 + * @param e the element to add + * @return true (as specified by {@link Collection#add}) + * @throws NullPointerException if the specified element is null */ public boolean add(E e) { addLast(e); @@ -436,61 +382,74 @@ 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 - * if this deque is empty. + * Inserts the specified element at the end of this deque. * - *

This method is equivalent to {@link #pollFirst}. + *

This method is equivalent to {@link #offerLast}. * - * @return the first element of this deque, or null if - * this deque is empty + * @param e the element to add + * @return true (as specified by {@link Queue#offer}) + * @throws NullPointerException if the specified element is null */ - public E poll() { - return pollFirst(); + public boolean offer(E e) { + return offerLast(e); } /** * Retrieves and removes the head of the queue represented by this deque. - * This method differs from the {@link #poll} method only in that it - * throws an exception if this deque is empty. + * + * This method differs from {@link #poll poll} only in that it throws an + * exception if this deque is empty. * *

This method is equivalent to {@link #removeFirst}. * * @return the head of the queue represented by this deque - * @throws NoSuchElementException if this deque is empty + * @throws NoSuchElementException {@inheritDoc} */ public E remove() { return removeFirst(); } /** - * Retrieves, but does not remove, the head of the queue represented by - * this deque, returning null if this deque is empty. + * 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. * - *

This method is equivalent to {@link #peekFirst}. + *

This method is equivalent to {@link #pollFirst}. * * @return the head of the queue represented by this deque, or - * null if this deque is empty + * null if this deque is empty */ - public E peek() { - return peekFirst(); + public E poll() { + return pollFirst(); } /** * Retrieves, but does not remove, the head of the queue represented by - * this deque. This method differs from the {@link #peek} method only in + * this deque. This method differs from {@link #peek peek} only in * that it throws an exception if this deque is empty. * *

This method is equivalent to {@link #getFirst}. * * @return the head of the queue represented by this deque - * @throws NoSuchElementException if this deque is empty + * @throws NoSuchElementException {@inheritDoc} */ public E element() { return getFirst(); } + /** + * Retrieves, but does not remove, the head of the queue represented by + * this deque, or returns 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 + */ + public E peek() { + return peekFirst(); + } + // *** Stack methods *** /** @@ -500,7 +459,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 the specified element is null */ public void push(E e) { addFirst(e); @@ -513,8 +472,8 @@ public class ArrayDeque extends Abstr *

This method is equivalent to {@link #removeFirst()}. * * @return the element at the front of this deque (which is the top - * of the stack represented by this deque) - * @throws NoSuchElementException if this deque is empty + * of the stack represented by this deque) + * @throws NoSuchElementException {@inheritDoc} */ public E pop() { return removeFirst(); @@ -522,29 +481,47 @@ public class ArrayDeque extends Abstr /** * 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. + * adjusting head and tail 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 - * that its semantics differ from those of List.remove(int). + * that its semantics differ from those of {@link List#remove(int)}. * * @return true if elements moved backwards */ private boolean delete(int i) { - // Case 1: Deque doesn't wrap - // Case 2: Deque does wrap and removed element is in the head portion - if ((head < tail || tail == 0) || i >= head) { - System.arraycopy(elements, head, elements, head + 1, i - head); - elements[head] = null; - head = (head + 1) & (elements.length - 1); + int mask = elements.length - 1; + int front = (i - head) & mask; + int back = (tail - i) & mask; + + // Invariant: head <= i < tail mod circularity + if (front >= ((tail - head) & mask)) + throw new ConcurrentModificationException(); + + // Optimize for least element motion + if (front < back) { + if (head <= i) { + System.arraycopy(elements, head, elements, head + 1, front); + } else { // Wrap around + elements[0] = elements[mask]; + System.arraycopy(elements, 0, elements, 1, i); + System.arraycopy(elements, head, elements, head + 1, mask - head); + } + elements[head] = null; + head = (head + 1) & mask; return false; - } - - // Case 3: Deque wraps and removed element is in the tail portion - tail--; - System.arraycopy(elements, i + 1, elements, i, tail - i); - elements[tail] = null; - return true; + } else { + int t = tail; + tail = (tail - 1) & mask; + if (i < t) { // Copy the null tail as well + System.arraycopy(elements, i + 1, elements, i, back); + } else { // Wrap around + elements[mask] = elements[0]; + System.arraycopy(elements, i + 1, elements, i, mask - i); + System.arraycopy(elements, 1, elements, 0, t); + } + return true; + } } // *** Collection Methods *** @@ -559,9 +536,9 @@ public class ArrayDeque extends Abstr } /** - * Returns true if this deque contains no elements.

+ * Returns true if this deque contains no elements. * - * @return true if this deque contains no elements. + * @return true if this deque contains no elements */ public boolean isEmpty() { return head == tail; @@ -573,12 +550,16 @@ public class ArrayDeque extends Abstr * 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 iterator over the elements in this deque */ public Iterator iterator() { return new DeqIterator(); } + public Iterator descendingIterator() { + return new DescendingIterator(); + } + private class DeqIterator implements Iterator { /** * Index of element to be returned by subsequent call to next. @@ -617,18 +598,56 @@ public class ArrayDeque extends Abstr public void remove() { if (lastRet < 0) throw new IllegalStateException(); - if (delete(lastRet)) - cursor--; + if (delete(lastRet)) // if left-shifted, undo increment in next() + cursor = (cursor - 1) & (elements.length - 1); lastRet = -1; fence = tail; } } + + private class DescendingIterator implements Iterator { + /* + * This class is nearly a mirror-image of DeqIterator, using + * (tail-1) instead of head for initial cursor, (head-1) + * instead of tail for fence, and elements.length instead of -1 + * for sentinel. It shares the same structure, but not many + * actual lines of code. + */ + private int cursor = (tail - 1) & (elements.length - 1); + private int fence = (head - 1) & (elements.length - 1); + private int lastRet = elements.length; + + public boolean hasNext() { + return cursor != fence; + } + + public E next() { + E result; + if (cursor == fence) + throw new NoSuchElementException(); + if (((head - 1) & (elements.length - 1)) != fence || + (result = elements[cursor]) == null) + throw new ConcurrentModificationException(); + lastRet = cursor; + cursor = (cursor - 1) & (elements.length - 1); + return result; + } + + public void remove() { + if (lastRet >= elements.length) + throw new IllegalStateException(); + if (!delete(lastRet)) + cursor = (cursor + 1) & (elements.length - 1); + lastRet = elements.length; + fence = (head - 1) & (elements.length - 1); + } + } + /** - * 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 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). * * @param o object to be checked for containment in this deque * @return true if this deque contains the specified element @@ -649,13 +668,19 @@ public class ArrayDeque extends Abstr /** * Removes a single instance of the specified element from this deque. - * This method is equivalent to {@link #removeFirstOccurrence}. + * 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 + * (or equivalently, if this deque changed as a result of the call). * - * @param e element to be removed from this deque, if present + *

This method is equivalent to {@link #removeFirstOccurrence}. + * + * @param o element to be removed from this deque, if present * @return true if this deque contained the specified element */ - public boolean remove(Object e) { - return removeFirstOccurrence(e); + public boolean remove(Object o) { + return removeFirstOccurrence(o); } /** @@ -672,38 +697,63 @@ public class ArrayDeque extends Abstr do { elements[i] = null; i = (i + 1) & mask; - } while(i != t); + } while (i != t); } } /** * Returns an array containing all of the elements in this deque - * in the correct order. + * in proper sequence (from first to last element). + * + *

The returned array will be "safe" in that no references to it are + * maintained by this deque. (In other words, this method must allocate + * a new array). The caller is thus free to modify the returned array. + * + *

This method acts as bridge between array-based and collection-based + * APIs. * * @return an array containing all of the elements in this deque - * in the correct order */ public Object[] toArray() { return copyElements(new Object[size()]); } /** - * Returns an array containing all of the elements in this deque in the - * correct order; the runtime type of the returned array is that of the - * specified array. If the deque fits in the specified array, it is - * returned therein. Otherwise, a new array is allocated with the runtime - * type of the specified array and the size of this deque. - * - *

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. + * Returns an array containing all of the elements in this deque in + * proper sequence (from first to last element); the runtime type of the + * returned array is that of the specified array. If the deque fits in + * the specified array, it is returned therein. Otherwise, a new array + * is allocated with the runtime type of the specified array and the + * size of this deque. + * + *

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. + * + *

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. + * The following code can be used to dump the deque into a newly + * allocated array of String: + * + * 

+     *     String[] y = x.toArray(new String[0]);
+ * + * Note that toArray(new Object[0]) is identical in function to + * 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 - * 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 + * 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 all of the elements in this deque + * @throws ArrayStoreException if the runtime type of the specified array + * is not a supertype of the runtime type of every element in + * this deque + * @throws NullPointerException if the specified array is null */ public T[] toArray(T[] a) { int size = size(); @@ -752,16 +802,12 @@ public class ArrayDeque extends Abstr s.defaultWriteObject(); // Write out size - int size = size(); - s.writeInt(size); + s.writeInt(size()); // Write out elements in order. - int i = head; int mask = elements.length - 1; - for (int j = 0; j < size; j++) { + for (int i = head; i != tail; i = (i + 1) & mask) s.writeObject(elements[i]); - i = (i + 1) & mask; - } } /**