--- jsr166/src/main/java/util/ArrayDeque.java	2005/09/14 23:49:59	1.16
+++ jsr166/src/main/java/util/ArrayDeque.java	2005/09/17 13:21:19	1.24
@@ -490,26 +490,41 @@ public class ArrayDeque<E> extends Abstr
      * @return true if elements moved backwards
      */
     private boolean delete(int i) {
-	int mask = elements.length - 1;
+	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 ***
@@ -538,20 +553,12 @@ 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();
     }
 
-    /**
-     * Returns an iterator over the elements in this deque in reverse
-     * sequential order.  The elements will be returned in order from
-     * last (tail) to first (head).
-     *
-     * @return an iterator over the elements in this deque in reverse
-     * sequence
-     */
     public Iterator<E> descendingIterator() {
         return new DescendingIterator();
     }
@@ -594,8 +601,8 @@ 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);
             lastRet = -1;
             fence = tail;
         }
@@ -603,15 +610,15 @@ public class ArrayDeque<E> extends Abstr
 
 
     private class DescendingIterator implements Iterator<E> {
-        /* 
-         * This class is nearly a mirror-image of DeqIterator. It
-         * shares the same structure, but not many actual lines of
-         * code. The only asymmetric part is that to simplify some
-         * checks, indices are anded with length mask only on array
-         * access rather than on each update.
+        /*
+         * 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;
-        private int fence = head - 1;
+        private int cursor = (tail - 1) & (elements.length - 1);
+        private int fence =  (head - 1) & (elements.length - 1);
         private int lastRet = elements.length;
 
         public boolean hasNext() {
@@ -622,21 +629,21 @@ public class ArrayDeque<E> extends Abstr
             E result;
             if (cursor == fence)
                 throw new NoSuchElementException();
-            if ((head - 1) != fence || 
-                (result = elements[cursor & (elements.length-1)]) == null)
+            if (((head - 1) & (elements.length - 1)) != fence ||
+                (result = elements[cursor]) == null)
                 throw new ConcurrentModificationException();
             lastRet = cursor;
-            cursor--;
+            cursor = (cursor - 1) & (elements.length - 1);
             return result;
         }
 
         public void remove() {
             if (lastRet >= elements.length)
                 throw new IllegalStateException();
-            if (delete(lastRet & (elements.length-1)))
-                cursor++;
+            if (!delete(lastRet))
+                cursor = (cursor + 1) & (elements.length - 1);
             lastRet = elements.length;
-            fence = head - 1;
+            fence = (head - 1) & (elements.length - 1);
         }
     }
 
@@ -798,16 +805,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;
-        }
     }
 
     /**