--- jsr166/src/main/java/util/ArrayDeque.java	2005/05/17 16:14:34	1.12
+++ jsr166/src/main/java/util/ArrayDeque.java	2006/03/03 17:12:43	1.28
@@ -202,7 +202,8 @@ public class ArrayDeque<E> extends Abstr
 
     /**
      * Inserts the specified element at the end of this deque.
-     * This method is equivalent to {@link #add} and {@link #push}.
+     *
+     * <p>This method is equivalent to {@link #add}.
      *
      * @param e the element to add
      * @throws NullPointerException if the specified element is null
@@ -219,7 +220,7 @@ public class ArrayDeque<E> extends Abstr
      * Inserts the specified element at the front of this deque.
      *
      * @param e the element to add
-     * @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
+     * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
      * @throws NullPointerException if the specified element is null
      */
     public boolean offerFirst(E e) {
@@ -231,7 +232,7 @@ public class ArrayDeque<E> extends Abstr
      * Inserts the specified element at the end of this deque.
      *
      * @param e the element to add
-     * @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
+     * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
      * @throws NullPointerException if the specified element is null
      */
     public boolean offerLast(E e) {
@@ -371,7 +372,7 @@ public class ArrayDeque<E> extends Abstr
      * <p>This method is equivalent to {@link #addLast}.
      *
      * @param e the element to add
-     * @return <tt>true</tt> (as per the spec for {@link Collection#add})
+     * @return <tt>true</tt> (as specified by {@link Collection#add})
      * @throws NullPointerException if the specified element is null
      */
     public boolean add(E e) {
@@ -385,7 +386,7 @@ public class ArrayDeque<E> extends Abstr
      * <p>This method is equivalent to {@link #offerLast}.
      *
      * @param e the element to add
-     * @return <tt>true</tt> (as per the spec for {@link Queue#offer})
+     * @return <tt>true</tt> (as specified by {@link Queue#offer})
      * @throws NullPointerException if the specified element is null
      */
     public boolean offer(E e) {
@@ -394,7 +395,8 @@ public class ArrayDeque<E> 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.
      *
      * <p>This method is equivalent to {@link #removeFirst}.
@@ -422,8 +424,8 @@ public class ArrayDeque<E> 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.
      *
      * <p>This method is equivalent to {@link #getFirst}.
      *
@@ -476,6 +478,14 @@ public class ArrayDeque<E> extends Abstr
         return removeFirst();
     }
 
+    private void checkInvariants() {
+	assert elements[tail] == null;
+	assert head == tail ? elements[head] == null :
+	    (elements[head] != null &&
+	     elements[(tail - 1) & (elements.length - 1)] != null);
+	assert elements[(head - 1) & (elements.length - 1)] == null;
+    }
+
     /**
      * Removes the element at the specified position in the elements array,
      * adjusting head and tail as necessary.  This can result in motion of
@@ -487,26 +497,42 @@ public class ArrayDeque<E> extends Abstr
      * @return true if elements moved backwards
      */
     private boolean delete(int i) {
-	int mask = elements.length - 1;
+ 	checkInvariants();
+	final E[] elements = this.elements;
+	final int mask = elements.length - 1;
+	final int h = head;
+	final int t = tail;
+	final int front = (i - h) & mask;
+	final int back  = (t - i) & mask;
 
 	// Invariant: head <= i < tail mod circularity
-	if (((i - head) & mask) >= ((tail - head) & mask))
+	if (front >= ((t - h) & 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;
-            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;
+	// Optimize for least element motion
+	if (front < back) {
+	    if (h <= i) {
+		System.arraycopy(elements, h, elements, h + 1, front);
+	    } else { // Wrap around
+		System.arraycopy(elements, 0, elements, 1, i);
+		elements[0] = elements[mask];
+		System.arraycopy(elements, h, elements, h + 1, mask - h);
+	    }
+	    elements[h] = null;
+	    head = (h + 1) & mask;
+	    return false;
+	} else {
+	    if (i < t) { // Copy the null tail as well
+		System.arraycopy(elements, i + 1, elements, i, back);
+		tail = t - 1;
+	    } else { // Wrap around
+		System.arraycopy(elements, i + 1, elements, i, mask - i);
+		elements[mask] = elements[0];
+		System.arraycopy(elements, 1, elements, 0, t);
+		tail = (t - 1) & mask;
+	    }
+	    return true;
+	}
     }
 
     // *** Collection Methods ***
@@ -535,12 +561,16 @@ public class ArrayDeque<E> extends Abstr
      * order that elements would be dequeued (via successive calls to
      * {@link #remove} or popped (via successive calls to {@link #pop}).
      *
-     * @return an <tt>Iterator</tt> over the elements in this deque
+     * @return an iterator over the elements in this deque
      */
     public Iterator<E> iterator() {
         return new DeqIterator();
     }
 
+    public Iterator<E> descendingIterator() {
+        return new DescendingIterator();
+    }
+
     private class DeqIterator implements Iterator<E> {
         /**
          * Index of element to be returned by subsequent call to next.
@@ -564,12 +594,12 @@ public class ArrayDeque<E> extends Abstr
         }
 
         public E next() {
-            E result;
             if (cursor == fence)
                 throw new NoSuchElementException();
+            E result = elements[cursor];
             // This check doesn't catch all possible comodifications,
             // but does catch the ones that corrupt traversal
-            if (tail != fence || (result = elements[cursor]) == null)
+            if (tail != fence || result == null)
                 throw new ConcurrentModificationException();
             lastRet = cursor;
             cursor = (cursor + 1) & (elements.length - 1);
@@ -579,10 +609,47 @@ public class ArrayDeque<E> 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);
+		fence = tail;
+	    }
+            lastRet = -1;
+        }
+    }
+
+    private class DescendingIterator implements Iterator<E> {
+        /*
+         * This class is nearly a mirror-image of DeqIterator, using
+         * tail instead of head for initial cursor, and head instead of
+         * tail for fence.
+         */
+        private int cursor = tail;
+        private int fence = head;
+        private int lastRet = -1;
+
+        public boolean hasNext() {
+            return cursor != fence;
+        }
+
+        public E next() {
+            if (cursor == fence)
+                throw new NoSuchElementException();
+            cursor = (cursor - 1) & (elements.length - 1);
+	    E result = elements[cursor];
+            if (head != fence || result == null)
+                throw new ConcurrentModificationException();
+            lastRet = cursor;
+            return result;
+        }
+
+        public void remove() {
+            if (lastRet < 0)
+                throw new IllegalStateException();
+            if (!delete(lastRet)) {
+                cursor = (cursor + 1) & (elements.length - 1);
+		fence = head;
+	    }
             lastRet = -1;
-            fence = tail;
         }
     }
 
@@ -650,7 +717,7 @@ public class ArrayDeque<E> extends Abstr
      * <p>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.
-     * 
+     *
      * <p>This method acts as bridge between array-based and collection-based
      * APIs.
      *
@@ -718,9 +785,7 @@ public class ArrayDeque<E> extends Abstr
     public ArrayDeque<E> clone() {
         try {
             ArrayDeque<E> result = (ArrayDeque<E>) 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);
+            result.elements = Arrays.copyOf(elements, elements.length);
             return result;
 
         } catch (CloneNotSupportedException e) {
@@ -744,16 +809,12 @@ public class ArrayDeque<E> 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;
-        }
     }
 
     /**
@@ -772,6 +833,5 @@ public class ArrayDeque<E> extends Abstr
         // Read in all elements in the proper order.
         for (int i = 0; i < size; i++)
             elements[i] = (E)s.readObject();
-
     }
 }