8143850: retrofit ArrayDeque to implement List

[Alex Foster]

Hi again,

I updated ArrayDeque with your last idea (adding all list methods but not implementing List) and added a subclass ArrayDeque.List which overrides equals and hashcode and implements List. There is also a subclass ArrayDeque.WithNulls that accepts null elements. ArrayDeque has removeAt(int index) instead of remove(index) to avoid overloading remove(Object).

I also added shared empty arrays similar to Arraylist, and a reallocate method which can do the same things as trimToSize and ensure capacity in Arraylist. It also allows you to trim to a specific capacity other than the size or skip trimming if the capacity is within a specified distance of the target capacity.

Also the bulk add methods call collection.toArray, then check the array for illegal elements, then add the array, which means that a collection could keep the array it returns from toArray and modify it from another thread after it has been checked but before it has been added which could lead to illegal elements being added to the ArrayDeque. We could maybe avoid this by cloning the array or checking the elements after adding them but I'm not sure if it's worth it...

What do you think?

I also changed the WhiteBox test a bit:

--- a/test/jdk/java/util/ArrayDeque/WhiteBox.java
+++ b/test/jdk/java/util/ArrayDeque/WhiteBox.java
@@ -88,7 +88,10 @@

     @Test
     public void defaultConstructor() {
-        checkCapacity(new ArrayDeque(), 16);
+        ArrayDeque d = new ArrayDeque();
+        d.add(new Object());
+        d.clear();
+        checkCapacity(d, 16);
     }

     @Test
@@ -131,7 +134,7 @@
             if (rnd.nextBoolean()) d.add(99);
             ArrayDeque clone = serialClone(d);
             assertInvariants(clone);
-            assertNotSame(elements(d), elements(clone));
+            assertTrue(d.isEmpty() || elements(d) != elements(clone));
             assertEquals(d, clone);
         }
     }

Alex