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 <marti...@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.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
