Random access in ArrayDeque

[Ivan Gerasimov]

Wouldn't it be  convenient, if negative indices were allowed for the 
get() method here?
So that get(-1) would return the last element, like in some other 
languages such as Perl or Python.

I understand it violates the spec for the List#get(), but this is the 
'Double Ended' queue, so we may want to access it from the both ends.

Sincerely yours,
Ivan

On 07.02.2014 23:07, Martin Buchholz wrote:
> 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
>>>
>>
>