On 02/07/2014 01:59 PM, Martin Buchholz wrote:
ArrayDeque should implement most of the methods in List, notably get(i).
ArrayDeque should not actually implement List itself, because the change in
contract/behavior for hashCode/equals would be too great.
Right. My vague recollection is that these were among initial reasons
for not implementing List. Also, the List.sublist method is questionable
for a Queue.
Too bad there is no interface with only get(index), set(index, x),
and indexOf(x). Implementing only these would probably satisfy
all candidate usages.
But we can
provide a
List asList()
method.
This might be the best compromise. Possibly with the sublist
method returning an unmodifiable list (which is legal and
probably not too surprising). Maybe even similarly for listIterator.
-Doug
If we have agreement, we can do the relatively easy implementation.
On Fri, Feb 7, 2014 at 10:07 AM, David M. Lloyd <david.ll...@redhat.com>wrote:
Just want to say that we've also had the need to implement an array-backed
Deque+List; we found no surprises implementing it and thus I believe that
extending ArrayDeque to implement List would be a positive change. Failing
that, a combined ArrayListAndDeque class seems like a good idea.
I think that calling it "Masters' thesis" material is perhaps overblowing
the complexity a bit though. ;) Given that the basic algorithmic
complexity of ArrayList is well-understood and is well-suited to many (some
would say "most") applications, going for a O(sqrt(N)) middle insert/remove
complexity would be something I would consider "scope creep"; LinkedList is
usually a fine choice for these cases.
On 02/07/2014 11:44 AM, Dan Smith wrote:
I noticed recently that the javac scanner is making use of
ArrayList.remove(0) when it consumes a buffer. Obviously this is an
inefficient way to implement a buffer, so I thought I'd try to fix it [1].
ArrayDeque seems to provide just the behavior I need, with one fatal flaw:
despite encoding its data with an array, the class exposes no random-access
operations. For lookahead, I need to be able to call get(int).
This seems to be a fairly common complaint [2][3].
I found an old bug requesting that ArrayDeque be enhanced to implement
List [4], as well as a thread from 2010 that included a proof-of-concept
ArrayDeque+List [5] and had a note from Martin Buchholz saying he regrets
that ArrayDeque doesn't already implement List [6].
Is there any hope of ArrayDeque being enhanced in the near future to
provide random access? There's some risk that any such initiative would be
derailed by a quest for an uber-collection. I think a lot of people would
be quite happy just to have a (trivial) 'get(int)' method added to
ArrayDeque.
—Dan
[1] https://bugs.openjdk.java.net/browse/JDK-8033158
[2] http://en.wikipedia.org/wiki/Deque#Language_support
[3] https://www.google.com/#q=arraydeque+%22random+access%22
[4] https://bugs.openjdk.java.net/browse/JDK-6368844
[5] http://mail.openjdk.java.net/pipermail/core-libs-dev/2010-
April/004038.html
[6] http://mail.openjdk.java.net/pipermail/core-libs-dev/2010-
April/004031.html
--
- DML
