8143850: retrofit ArrayDeque to implement List

[Stuart Marks]

OK, great.


It looks like a heavily modified version of ArrayDeque.java. This makes it a bit 
difficult to understand what the changes are. Would you mind if I rehosted this 
to cr.openjdk.java.net and generated a webrev for it?


Thanks,


s'marks


On 7/28/18 11:05 PM, Alex Foster wrote:
>
> Hi,
>
>
> Here's my current proposal: https://pastebin.com/EABgwLYS 
> <https://pastebin.com/EABgwLYS>
>
>
> Alex
>
>
>
> --------------------------------------------------------------------------------
> *From:* Stuart Marks <stuart.marks at oracle.com>
> *Sent:* July 28, 2018 8:11 PM
> *To:* Martin Buchholz; Alex Foster
> *Cc:* Doug Lea; core-libs-dev at openjdk.java.net
> *Subject:* Re: 8143850: retrofit ArrayDeque to implement List
> Hi, I finally got some time to get my head around this.
>
> Conceptually, I like the idea of a List that's stored in a circular array, like
> ArrayDeque. The best way to manifest this in the API isn't obvious though. I
> filed the bug as "retrofit ArrayDeque to implement List" but of course it
> doesn't have to be this way.
>
> I also think we want to reuse an existing implementation as much as possible.
> There's already too much duplication between ArrayList and ArrayDeque; we don't
> want a third similar implementation that will need to be maintained in parallel.
>
> To Martin's points:
>
> * Adding List-like methods to ArrayDeque without it implementing List is indeed
> odd, but not necessarily fatal. It does seem to raise the question "Isn't there
> a better way?" though.
>
> * I don't want to have to add null support if at all possible, for the reasons
> Martin mentioned. Also, it's an implementation and maintenance headache. Of
> course the implementations like ArrayList and HashMap are proof that it can be
> done. But each time HashMap has been enhanced significantly, there's been a bug
> tail where null checking was missed in certain cases.
>
> * Growth policy. The shared null array setup for ArrayList was added when we
> observed that a significant number of ArrayLists are created with the default
> constructor and then never populated. Allocating the backing array lazily
> resulted in a considerable space savings. I think this would be a good idea to
> do for ArrayDeque, but this is somewhat orthogonal to the current "retrofit
> List" discussion.
>
> * Regarding nestmates, I don't think the use of nestmates has any advantage or
> disadvantage over package-level access between top-level classes in the same
> package. I think we should decide what we want the API to look like first, and
> then figure out how to factor things so that we can get the code sharing and
> coupling that we want. We might not be forced into contorting the API in order
> to get better sharing/coupling, but let's wait to cross that bridge if we come
> to it.
>
> --
>
> Alex, I'm not sure where your current proposal stands. Have you sent an update
> since the head of the thread? If you had included something as an attachment, it
> has likely been stripped.
>
> Thanks,
>
> s'marks
>
>
>
>
>
> On 7/23/18 8:46 PM, Martin Buchholz wrote:
> > (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
> > <mailto: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
> >
> >