Re: priority queue
On Mon, 30 Mar 2009, Eric Sosman wrote:
Tom Anderson wrote:
On Sun, 29 Mar 2009, Andreas Leitgeb wrote:
As it seems, sorting an ArrayList is a bit awkward, in that you have to
copy the contents to an array first, sort that, and then bring the array
back into an ArrayList, but I may have missed something there.
You may have missed this:
http://java.sun.com/javase/6/docs/api/java/util/Collections.html#sort(java.util.List,%20java.util.Comparator)
... which says, in part:
This implementation dumps the specified list into an array,
sorts the array, and iterates over the list resetting each
element from the corresponding position in the array.
That's pretty much the awkward operation Andreas described.
DOH! I had this idea that for lists which implemented RandomAccess, it was
done in-place. But of course, the sort is a mergesort, which is impossible
to implement in-place anyway, and would be a real pain to implement
half-in-place.
The Javadoc goes on to say:
This avoids the n^2 log(n) performance that would result from
attempting to sort a linked list in place.
... which is an admission of a drawback of the Holy Principles of
Encapsulation and Information Hiding. If the Collections class could
directly manipulate the links of a LinkedList, the sort could be done in
O(n lg(n)) time, in-place and without creating additional garbage. The
copy-sort-restore dance is not required by the inherent complexity of
the sorting problem, but by a limitation imposed by adherence to OO
purity.
Well, that and the decision to put sort in Collections rather than List.
(Of course, even an OO purist might have allowed sort() and other
utilities as methods of List itself instead of packaging them in a
separate Collections class.
Exactly.
I think the whole Collections class is a festering pile of code stink -
almost all its methods belong somewhere else. Yes, putting them in List
would mean that every implementation would have to implement them, but
there could be general-purpose implementations in AbstractList (maybe
accessible as static methods for the benefit of lists which don't extend
AbstractList), so it wouldn't impose on most implementations.
But if you pursue *that* stratagem too far, you wind up with enormous
SwissArmyKnife classes ...)
So don't pursue it too far!
tom
--
The future will accost us with boob-slapping ferocity. -- H. G. Wells