John Keiser wrote:
>
> > From: Stuart Ballard [mailto:[EMAIL PROTECTED]]
> >
> > For a spec that is supposed to be stable and implementable, beta4 has
> a
> > long way to go - I found another significant spec bug in the latest
> > changes to java.util.List also, which will make some common methods in
> > spec-conforming classes O(n) when a better designed spec could make
> them
> > O(1).
> >
> > <snip>
>
> I remember that they did specify the O() of many of the classes, mainly
> to highlight the tradeoffs you would take if you used the class. If
> your implementation makes the big-O of any of your operations greater
> than Sun's, or requires a great deal more space, then you are just using
> a different tradeoff. It's best in that case for you to just create a
> new gnu.java.util.BetterList class that uses the new tradeoffs.
>
> I don't know if that's the case. Perhaps you do just know a better way
> to do it and still conform to the spec.
No, it's actually a case where they obviously haven't thought out the
full ramifications of one of the spec changes they made to the List
interface itself. The change is that instead of providing a subList
wrapper class as one of the Collections utility methods, they moved this
method into the List interface and removed a couple of methods that
could be achieved more elegantly through this method.
The particular case in point is the removeRange() method. This was
removed because instead of doing l.removeRange(start, end) you can do
l.subList(start, end).clear(). So far, no problem, lovely and elegant.
They then provide an implementation of the subList method in
AbstractList, the abstract class that is provided to make it easy to
implement the List interface. This implementation of subList returns an
inner class which itself extends AbstractList, to make it easy to
implement, which is fair enough.
It doesn't override clear(), because an implementation is provided by
its superclass. This implementation iterates through all the elements,
removing them one at a time. In an "abstract" situation, that's okay,
because the "abstract" class doesn't have access to the implementation
information which makes clearing a list efficient.
But say you have a class, such as Vector, which implements List and can
remove a range a lot quicker than it can remove the elements one at a
time. What does it do? It can't override the removeRange() method, there
isn't one. It needs to override the subList().clear() method. That is,
it has to override a method in an anonymous private inner class provided
by it's superclass with no public API. It can't! It needs to provide a
whole new inner class to return from subList(), thereby reinventing the
wheel and recreating the entire problem that AbstractList is supposed to
solve.
The only alternative is to use the default implementation, which removes
the elements one at a time - think about the performance hit that would
make to Vector! O(n^2) instead of O(n), I think.
I've actually realised since posting this spec bug a better way to
address it than the one I set out in the original bug report, but I'm
still waiting for a bug number before I can submit this solution to Sun.
The solution I suggested was to reinstate the removeRange method of the
List interface and then implementing subList().clear() by calling that,
which would make it possible for AbstractList subclasses to override it.
This would work, but it would enlarge the List interface with a method
which isn't actually needed because the *API* for doing it is available
elsewhere - the only problem is in the implementation. It seems a little
inelegant to have redundancy in the whole API for such an obscure
reason.
So the solution is to fix it just in the AbstractList class. Put a
protected removeRange method in AbstractList, which subclasses can
override. This is then accessible to the inner class that implements
subList, so it can perform the operation efficiently. It doesn't add any
extra methods to List, so this interface is as easy to implement as
ever, and doesn't have any redundancy. The elegant l.subList().clear()
technique is now as efficient as the old inelegant l.removeRange().
Okay, rant over. I just wish Sun would fix this one...
Stuart.
