Random access in ArrayDeque

Martin Buchholz martinrb at google.com
Fri Feb 7 19:07:52 UTC 2014


Can't finish if we don't start.  Here's v0.1:  No rocket science here.

Index: src/main/java/util/ArrayDeque.java
===================================================================
RCS file:
/export/home/jsr166/jsr166/jsr166/src/main/java/util/ArrayDeque.java,v
retrieving revision 1.57
diff -u -r1.57 ArrayDeque.java
--- src/main/java/util/ArrayDeque.java 18 Jul 2013 18:21:22 -0000 1.57
+++ src/main/java/util/ArrayDeque.java 7 Feb 2014 19:06:15 -0000
@@ -291,6 +291,17 @@
         return result;
     }

+    /**
+     * Implements {@link List#get(int)}.
+     */
+    public E get(int index) {
+        if (index < 0 || index >= size())
+            throw new IndexOutOfBoundsException();
+        @SuppressWarnings("unchecked")
+        E result = (E) elements[(head + index) & (elements.length - 1)];
+        return result;
+    }
+
     @SuppressWarnings("unchecked")
     public E peekFirst() {
         // elements[head] is null if deque empty



On Fri, Feb 7, 2014 at 10:59 AM, Martin Buchholz <martinrb at google.com>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.  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
>>
>
>



More information about the core-libs-dev mailing list