Deque question

[toton]

Hi,
Java ArrayDeque is an Deque implementation over an array. However if
the array is gull it expands it, otherwise wraps the head and tail.
That is what I want.
However as it is an implementation over an array, I expect an random
access like E get(index i) method. But such method is not present. Why?
It is present in ArrayList or any other random access container! Though
it gives an delete(index i) method, which causes it to shift some of
the elements!

can anyone give a little insight?

Thanks
abir

 

[Thomas Hawtin]

Java ArrayDeque is an Deque implementation over an array. However if
the array is gull it expands it, otherwise wraps the head and tail.
That is what I want.
However as it is an implementation over an array, I expect an random
access like E get(index i) method. But such method is not present. Why?
It is present in ArrayList or any other random access container! Though
it gives an delete(index i) method, which causes it to shift some of
the elements!

I can only guess that it is to make it easier to subclass. Personally, I
would have made it implement List (and RandomAccess, but not Cloneable).

Tom Hawtin

 

[heysc0tt]

Java ArrayDeque is an Deque implementation over an array. However if
the array is gull it expands it, otherwise wraps the head and tail.
That is what I want.
However as it is an implementation over an array, I expect an random
access like E get(index i) method. But such method is not present. Why?
It is present in ArrayList or any other random access container! Though
it gives an delete(index i) method, which causes it to shift some of
the elements!

It seems to me that this is line with the design of the interface.
Being a Queue at heart it seems logical to disallow index based
operations and try to restrict access to only head and tail elements.

 

[hiwa]

Being a Queue at heart it seems logical to disallow index based
operations and try to restrict access to only head and tail elements.

Quite right.

 

[toton]

Quite right.

However it allows index based deletion! What is the problem with index
based access? Otherwise what is the necessity to implement it over an
Array? Surprisingly enough LinkedList , which is not backed by and
array, and implements Deque has an index based access! A Deque property
does not get lost giving index based access, it looses the property
when it allows index based insert and remove (which it has already
done!)

Thanks

 

[Chris Uppal]

However as it is an implementation over an array, I expect an random
access like E get(index i) method. But such method is not present. Why?

I Assume you're talking about the ArrayDeque in JDK1.6 ?

If so then I can't see any good reason. It seems daft to me.

Looking at the code, it seems that the only reason for that omission (and also
the only reason for the equally odd restriction that the inserted values cannot
be null) is to simplify the code a little and reduce the amount of arithmetic
bounds checking needed. If so then (IMO) that/those are very poor reasons, and
not at all what I would expect when:

@author Josh Bloch and Doug Lea

Note that the iterator /does/ make use (internally) of indexed access...

Still, 1.6 is beta software, so maybe this'll change before release.

-- chris

 

[Patricia Shanahan]

However it allows index based deletion! What is the problem with index
based access? Otherwise what is the necessity to implement it over an
Array? Surprisingly enough LinkedList , which is not backed by and
array, and implements Deque has an index based access! A Deque property
does not get lost giving index based access, it looses the property
when it allows index based insert and remove (which it has already
done!)

Thanks

Isn't the index based delete method private?
http://download.java.net/jdk6/doc/api/java/util/ArrayDeque.html does not
mention it.

Patricia

 

[Thomas Hawtin]

Looking at the code, it seems that the only reason for that omission (and also
the only reason for the equally odd restriction that the inserted values cannot
be null) is to simplify the code a little and reduce the amount of arithmetic
bounds checking needed. If so then (IMO) that/those are very poor reasons, and
not at all what I would expect when:

@author Josh Bloch and Doug Lea

As a rule, collection classes written by Josh Bloch permit nulls, those
written by Doug Lea do not.

Note that the iterator /does/ make use (internally) of indexed access...

I would hope so. Note, the iterator does support remove...

Tom Hawtin

 

[toton]

I Assume you're talking about the ArrayDeque in JDK1.6 ?

Yes, ArrayDeque in JDK1.6 beta . This class is a very important
addition (esp for me!, and may be a very strong reason why I am using
1.6, apart from Those taskbar icons etc).

If so then I can't see any good reason. It seems daft to me.

But it is beta version. I don't think API will change after a beta
release.

Looking at the code, it seems that the only reason for that omission (and also
the only reason for the equally odd restriction that the inserted values cannot
be null) is to simplify the code a little and reduce the amount of arithmetic
bounds checking needed. If so then (IMO) that/those are very poor reasons, and
not at all what I would expect when:

@author Josh Bloch and Doug Lea

Is he same person as Joshua Bloc of effective Java? Then I have a
reason! He was in hurry while leaving Sun (and joining Google) I
have an old code by them also, a non-generic version.

Note that the iterator /does/ make use (internally) of indexed access...

Yes, everything uses indexed access, and that is natural when it is
implemented over an array!
And oh! The delete(int index ) is private, and have a special use in
removeLastOccurrence and removeFirstOccurrence. It shifts the
references using arraycopy.

Still, 1.6 is beta software, so maybe this'll change before release.

Hope so!
Thanks