--- jsr166/src/main/java/util/ArrayDeque.java	2005/09/16 04:41:04	1.18
+++ jsr166/src/main/java/util/ArrayDeque.java	2005/09/17 17:22:17	1.25
@@ -479,6 +479,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
@@ -490,26 +498,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 ***
@@ -593,7 +617,6 @@ public class ArrayDeque<E> extends Abstr
         }
     }
 
-
     private class DescendingIterator implements Iterator<E> {
         /*
          * This class is nearly a mirror-image of DeqIterator, using
@@ -790,16 +813,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;
-        }
     }
 
     /**
@@ -818,6 +837,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();
-
     }
 }