[ Osvaldo Pinali Doederlein ] [ Osvaldo Pinali Doederlein ] [concurrency-interest] need to use collection.sort w. CopyOnWriteArrayList but cant.....

Osvaldo Pinali Doederlein osvaldo@visionnaire.com.br
Fri, 04 Jun 2004 09:28:51 -0300

Gregg G. Wonderly wrote:
>>The current implementation of Collections.sort() breaks
>>the semantics of the collections API: sort(List) should work with any
>>implementation of List (I'm not requiring a performant behavior, only
>>correct behavior). (...)
> This is an oversight in documentation for sure.  I understand you feelings 
> about this.  But, specifically, the ListIterator is the optimal implementation 
> of access to the list members, and so I can see why sort(List) uses that for 
> write access, as the reply related to linked lists pointed out already.
> I thinking that a more type centric fix at this point would be to create 
> something like the following interfaces. The existing Collections.sort(List) 
> could be deprecated, and a new Collections.sort(WriteableList) could be added 
> that would make the contract visible with type information.
> public interface WriteableList extends List {
> 	public WriteableListIterator writeableListIterator();
> }
> public interface WriteableListIterator extends ListIterator {
> 	public void set( Object obj ) throws
> 		ClassCastException,
> 		IllegalArgumentException,
> 		IllegalStateException;
> }

These new interfaces are a good idea (if there is time for this).
Considering that other types of collections, like Map, can also be
writeable or not, I suggest more general interfaces.

* Writeable -- collection that can clear(), and where other optional
                mutators (ad(), put(), remove() etc.) are implemented
* WriteIterable -- collection which iterators are WriteableIterator
* WriteableIterator -- iterator which mutators are implemented

Notice that for collections, we need separate concepts of ("writeable"
and "writeable through iterator"), for example in CopyOnWriteArrayList.


* ArrayList is both Writeable and WriteIterable.
* "ListIterator ArrayList.listIterator()" returns a WriteableIterator;
   the user must use a typecast if he wants a WriteableIterator, but
   this cast is safe if the collection is Writeable.  It's a compromise
   to not need a new method like writeableListIterator().
* CopyOnWriteArrayList is Writeable, but not WriteIterable.
* Collections.sort(List) is unchanged, but it documents that the list
   must be (WriteIterable || Writeable && RandomAccess).

Notice that deprecating sort(List) and introducing sort(WriteIterable)
is not acceptable because the latter method wouldn't sort lists that
are Writeable and RandomAccess, but not WriteIterable, which should
certainly be a supported scenario (it's the CopyOnWriteArrayList case).
So my modified algorithm is still necessary, but changed:

if (list instanceof Writeable && list instanceof RandomAccess) {
   loop to put elements with set();
} else { // WriteIterable; otherwise, UnsupportedOperationException
   loop to put elements with ListIterator;

This is much better because we don't rely on catching of exceptions
(which is expensive and a bad practice) to handle valid arguments.
Perhaps it's better to change the algorithm (check WriteIterable first)
to favor the traditional behavior for lists that pass all conditions,
but IMHO it's better to favor use of set() when possible because (in a
RandomAccess list) it's faster than ListIterator (though marginally).

Another possibility is relaxing the constraints of sort(), like:

if (list instanceof Writeable &&
   (list instanceof RandomAccess || !(list instanceof WriteIterable))){
   loop to put elements with set();
} else {
   loop to put elements with ListIterator;

This last version will work for any kind of list that's not totally
immutable (the single functional constraint that sort() should impose),
including some list that is WriteIterable but not Writeable (this is a
strange possibility, maybe we should specify 'WriteIterable extends
Writeable' to avoid this).  In the worst case, if the list is Writeable
but not ListIterable nor RandomAccess, then the sort() method will use
set() and this will work but with inferior performance.  This should be
documented, it changes the current performance guarantess but only for
lists that cannot be sorted at all today.  But I'd agree that this is a
rare possibility, and a new feature (allows writing code that links,
but fails to work, on older J2SE releases), and it may cover developer
sloppiness by supporting broken custom lists.

In any case, it's important to document precisely which list the sort()
method can handle.  The current API specification allows a portability
problem: a different implementation (say, a clean-room library like GNU
Classpath) allows an alternative implementation of Collections.sort()
to support some collections that throw UnsupportedOperationException in
the Sun JRE. They only need to use the algorithm in my previous email
(trying both ListIterator and set(), if the first attempt raises UOE).
And that implementation would pass the JCK (unless the JCK requires
an UnsupportedOperationException in cases where it shouldn't), allowing
people to write valid code that runs in the other JRE but not in Sun's.


Osvaldo Pinali Doederlein                   Visionnaire Informática S/A
osvaldo@visionnaire.com.br                http://www.visionnaire.com.br
Arquiteto de Tecnologia                          +55 (41) 373-7400 #228