Hi Joe,
Joe Gottman said:
Giovanni Azua wrote:
I think that we have a philosophical difference here. You think that an
ArrayDeque should ONLY be used as a queue. I think that it [snip]
Well not exactly. I think that any implementation, in this case an
ArrayDeque should be used as whatever interface(s) it implements, no more
but no less.
If you have very specific needs and in very rare cases you could resort to
extending the closest match in the Collections API and creating an ad
hoc implementation that fits your needs e.g. if you needed something like a
"CircularPriorityQueue" then you would extend PriorityQueue (or preferably
use the Decorator Pattern) and add the circularity feature.
Dequeue main use-case is to manipulate and retrieve elements from the ends
and that's O(c) complexity, not linear. If you try using a helicopter as a
blender then you are getting into troubles no one could have ever predicted
like ending up in a very inefficient usage.
should be usable as a queue, and for whatever other uses a coder desires,
as long as those uses don't make it less efficient when used as a Queue.
Note that an ArrayList can be used as either a List or a Queue, even
though it is has linear complexity on its get() method.
I disagree, ArrayList should be only used as what its official contract
offers i.e. its implemented interfaces. ArrayList only offers to customers
the List and RandomAccess contracts. As you know you are free to leave the
contracts and get into slightly hacking arena but then you will be on your
own like now. ArrayList does not offer fast search per se, it is not built
for that purpose. If you need fast retrieval you should use e.g.
- TreeSet O(log N)
- TreeMap O(log N)
As it is currently implemented, ArrayDeque could be given a
constant-complexity get() method.
I think this is not possible without implementing the ArrayDeque to
internally manipulate a redundant data structure optimized for searching.
But then it would not be an ArrayDeque anymore but something else.
What I would myself do in this case is:
1) create a new interface e.g. LogNSearchDeque extends Deque and adds a
method search(Element anElement)
2) introduce new class LogNSearchArrayDeque that implements #1 and extends
ArrayDeque. This implementation could e.g. aggregate and delegate to a
redundant collection optimized for search like the ones above or do it
yourself using a sorted ArrayList and Collections.binarySearch:
http://java.sun.com/javase/6/docs/a...arch(java.util.List, T, java.util.Comparator)
I find it annoying that in my use-case (a data structure
with allowing indexing everywhere and insertions and deletions at the
ends) the standard demands I either use a highly inefficient class or
write my own. This is not an uncommon use case; see for example the C++
deque class, which has precisely these semantics.
I checked the deque class in std and it does not offer a fast search get
method. I can only see the access "operator[]" and "at" methods where you
should provide the position index:
http://www.cplusplus.com/reference/stl/deque/
http://www.cplusplus.com/reference/stl/deque/at.html
Since ArrayDeque lacks a get(i) you can easily do:
Deque<String> myDeque = new ArrayDeque<String>();
// ... insert elements
// get the i-th element
int i = 3;
String myThirdElement = myDeque.toArray(new String[0])
;
HTH,
Best regards,
Giovanni
