Random access in ArrayDeque

[David M. Lloyd]

On 02/07/2014 12:59 PM, Martin Buchholz wrote:
> 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.

Extending ArrayList to implement Deque might avoid this?  Though I 
suppose the chance of exciting new conflicts "in the wild" is higher 
given that ArrayList has been around since 1.2.

> But we can provide a List asList() method.

If this path is chosen, it could be perhaps interesting to have 
ArrayList and ArrayDeque act as mutual views for each other, though I'd 
hate to require the extra object when (as LinkedList shows) it is 
conceptually OK to implement List and Deque.

> 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
> <mailto: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
>         <https://bugs.openjdk.java.net/browse/JDK-8033158>
>         [2] http://en.wikipedia.org/wiki/__Deque#Language_support
>         <http://en.wikipedia.org/wiki/Deque#Language_support>
>         [3] https://www.google.com/#q=__arraydeque+%22random+access%22
>         <https://www.google.com/#q=arraydeque+%22random+access%22>
>         [4] https://bugs.openjdk.java.net/__browse/JDK-6368844
>         <https://bugs.openjdk.java.net/browse/JDK-6368844>
>         [5]
>         http://mail.openjdk.java.net/__pipermail/core-libs-dev/2010-__April/004038.html
>         <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
>         <http://mail.openjdk.java.net/pipermail/core-libs-dev/2010-April/004031.html>
>
>
>
>     --
>     - DML
>
>


-- 
- DML