8143850: retrofit ArrayDeque to implement List

[Martin Buchholz]

(As usual, I don't have enough time to devote to this at the moment)

I sort of like the idea of adding all of those List methods to ArrayDeque,
but it's __weird__ for java code to do that, and remove(int) is a problem
when you have ArrayDeque<Integer>, so it will probably end up rejected.

---

Similarly, the idea of an ArrayDeque subclass that accepts nulls will be
unpopular - null elements have fallen out of favor.

While Deque implementations are not strictly required to prohibit the
insertion of null elements, they are strongly encouraged to do so. Users of
any Deque implementations that do allow null elements are strongly
encouraged *not* to take advantage of the ability to insert nulls. This is
so because null is used as a special return value by various methods to
indicate that the deque is empty.

---

It makes some sense for ArrayDeque's growth policy to be very similar to
ArrayList's - that should be done as an independent change.  Are there any
lessons to be learned from ArrayList's experience?  Is the world filled
with empty ArrayDeques that could share a common backing array?

---

I do like the idea of having ArrayDeque's List-implementing subclass be a
nestmate of ArrayDeque, to share implementation details and to help
discovery and naming.  I'm not thrilled with reusing "List" in
ArrayDeque.List but I don't have a great alternative to suggest.


On Mon, Jul 16, 2018 at 10:36 AM, Alex Foster <alexfoster at hotmail.ca> wrote:

> 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
>