--- jsr166/src/main/java/util/ArrayDeque.java	2005/09/16 11:15:41	1.19
+++ 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 ***