--- jsr166/src/main/java/util/ArrayDeque.java 2005/05/17 06:36:47 1.11 +++ jsr166/src/main/java/util/ArrayDeque.java 2005/09/16 23:59:27 1.22 @@ -4,6 +4,7 @@ */ package java.util; +import java.util.*; // for javadoc (till 6280605 is fixed) import java.io.*; /** @@ -202,7 +203,8 @@ public class ArrayDeque extends Abstr /** * Inserts the specified element at the end of this deque. - * This method is equivalent to {@link #add} and {@link #push}. + * + *

This method is equivalent to {@link #add}. * * @param e the element to add * @throws NullPointerException if the specified element is null @@ -219,7 +221,7 @@ public class ArrayDeque extends Abstr * Inserts the specified element at the front of this deque. * * @param e the element to add - * @return true (as per the spec for {@link Deque#offerFirst}) + * @return true (as specified by {@link Deque#offerFirst}) * @throws NullPointerException if the specified element is null */ public boolean offerFirst(E e) { @@ -231,7 +233,7 @@ public class ArrayDeque extends Abstr * Inserts the specified element at the end of this deque. * * @param e the element to add - * @return true (as per the spec for {@link Deque#offerLast}) + * @return true (as specified by {@link Deque#offerLast}) * @throws NullPointerException if the specified element is null */ public boolean offerLast(E e) { @@ -313,8 +315,8 @@ public class ArrayDeque extends Abstr * 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). + * 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 @@ -341,8 +343,8 @@ public class ArrayDeque extends Abstr * 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). + * 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 @@ -371,7 +373,7 @@ public class ArrayDeque extends Abstr *

This method is equivalent to {@link #addLast}. * * @param e the element to add - * @return true (as per the spec for {@link Collection#add}) + * @return true (as specified by {@link Collection#add}) * @throws NullPointerException if the specified element is null */ public boolean add(E e) { @@ -385,7 +387,7 @@ public class ArrayDeque extends Abstr *

This method is equivalent to {@link #offerLast}. * * @param e the element to add - * @return true (as per the spec for {@link Queue#offer}) + * @return true (as specified by {@link Queue#offer}) * @throws NullPointerException if the specified element is null */ public boolean offer(E e) { @@ -394,7 +396,8 @@ public class ArrayDeque extends Abstr /** * Retrieves and removes the head of the queue represented by this deque. - * This method differs from {@link #poll} only in that it throws an + * + * 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}. @@ -422,8 +425,8 @@ public class ArrayDeque extends Abstr /** * Retrieves, but does not remove, the head of the queue represented by - * this deque. This method differs from {@link #peek} only in that it - * throws an exception if this deque is empty. + * 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}. * @@ -488,25 +491,37 @@ public class ArrayDeque extends Abstr */ private boolean delete(int i) { int mask = elements.length - 1; + int front = (i - head) & mask; + int back = (tail - i) & mask; // Invariant: head <= i < tail mod circularity - if (((i - head) & mask) >= ((tail - head) & mask)) + if (front >= ((tail - head) & mask)) throw new ConcurrentModificationException(); - // Case 1: Deque doesn't wrap - // Case 2: Deque does wrap and removed element is in the head portion - if (i >= head) { - System.arraycopy(elements, head, elements, head + 1, i - head); - elements[head] = null; - head = (head + 1) & mask; + // Optimize for least element motion + if (front < back) { + if (head <= i) { + System.arraycopy(elements, head, elements, head + 1, front); + } else { // Wrap around + System.arraycopy(elements, 0, elements, 1, i); + elements[0] = elements[mask]; + 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 + System.arraycopy(elements, i + 1, elements, i, mask - i); + elements[mask] = elements[0]; + System.arraycopy(elements, 1, elements, 0, t); + } + return true; + } } // *** Collection Methods *** @@ -535,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. @@ -579,13 +598,52 @@ 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 @@ -613,8 +671,8 @@ public class ArrayDeque extends Abstr * 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). + * Returns 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}. * @@ -650,7 +708,7 @@ public class ArrayDeque extends Abstr *

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. * @@ -744,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; - } } /**