Random access in ArrayDeque

[Martin Buchholz]

Sorry we're all such lamers.

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.  But we can
provide a
List asList()
method.

If we have agreement, we can do the relatively easy implementation.


On Fri, Feb 7, 2014 at 10:07 AM, David M. Lloyd <david.lloyd at 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
>