Bug in Lists.transform() ?

[sylvain.mina]

Hi all, a question posted here
http://stackoverflow.com/questions/3197790/how-to-delete-elements-from-a-transformed-collection-using-a-predicate/3201732#3201732
interested me...

but I wonder why

final List<Integer> ints = Lists.newArrayList(1, 2, 3, 4, 5);
Iterables.removeIf(Iterables.transform(ints, intoDouble()),
even());
System.out.println(ints);

prints [1,3,5]

and

final ArrayList<Integer> crash = Lists.newArrayList(1, 2, 3,
4, 5);
Iterables.removeIf(Lists.transform(crash, intoDouble()),
even());
System.out.println(crash);

crash with

java.lang.UnsupportedOperationException
at java.util.AbstractList.set(AbstractList.java:115)
at
com.google.common.collect.Iterables.removeIfFromRandomAccessList(Iterables.java:
167)
at com.google.common.collect.Iterables.removeIf(Iterables.java:152)
.....

I'm guessing that the set() operation is not overriden in the
TransformingRandomAccessList...

[Ditz]

Hi,

I posted the question, but meanwhile I also come to the conclusion
this something that should work.

Unfortunately it is hardly possible to provide a set() operation for a
transformed list.
Instead Iterator.remove() is supported, but it's slow for a
RandomAccess list to delete each element individually.

The decision at Iterables:147 might be extended by other (ugly and
possibly instable) instanceof cascades
to get a special handling for a TransformingRandomAccessList:
Transform the given Predicate according to the
TransformingRandomAccessList
and delegate the removal to the original List.

btw.: I just discovered Collection.removeAll(Collection<?> c) which is
even defined in java.util.Collection.
Isn't this a disguised predicate? Will any implementation ever call
something different than c.contains()?
Would it be possible to convert the Predicate<T> into a dummy
Collection<T> and thus to delegate the
removal to the underlaying Collection itself?
Thus any ugly instanceof would become obsolete and the underlaying
Collection (or RandomAccess List) will
choose its own optimized removal algorithm.

Unfortunately Collection.removeAll() is also tagged as an "optional
operation".

Dieter.

[Chris Povirk]

Hmm, this is a pretty severe downside to the RandomAccess optimization
we have in removeIf() -- and an undocumented on at that. Can you file
a "removeIf() broken for RandomAccess lists that don't support set()"
bug for us that includes your description? Thanks.

> --
> guava-...@googlegroups.com.
> http://groups.google.com/group/guava-discuss?hl=en
> unsubscribe: guava-discus...@googlegroups.com
>
> This list is for discussion; for help, post to Stack Overflow instead:
> http://stackoverflow.com/questions/ask
> Use the tag "guava".
>

[Kevin Bourrillion]

Yep.  At a first thought, we could catch exceptions and just fall back on the slower strategy.

--
Kevin Bourrillion @ Google
http://guava-libraries.googlecode.com

[Ditz]

sorry, was stuck on old google-collection code.
But guava-r06 suffers from the same problem.
Here is a compact sample to verify it.
Funnily enough it even works in some situations!

Q: I originally started with a question at Stackoverflow.
Is it OK to go in detail here or should I keep off here and stay over
there with further contributions?

public class RemoveIf {

static final Function<Integer, Double> TO_DOUBLE = new
Function<Integer, Double>() {
public Double apply(final Integer value) {
return (double) value;
}
};

static final Predicate<Double> IS_EVEN = new Predicate<Double>() {
public boolean apply(final Double value) {
return value == 2* Math.floor(value/2);
}
};

static void testRemoval(Integer ... values) {
List<Integer> intList = Lists.newArrayList(values);
List<Double> transformedList = Lists.transform(intList,
TO_DOUBLE);
Iterables.removeIf(transformedList, IS_EVEN);
}

public static void main(String... args) {
testRemoval(1,3,5,7,2,4,6); // works accidentally
testRemoval(1,2,3,4,5,6,7); // fails
}
}

[Sylvain MINA]

Can you make a bug report ?

[Dimitris Andreou]

I suggest catching the exception thrown from set(), but not revert to the iterator solution - we know this is a RandomAccess list, so the optimization *is* important. So accumulate the unfiltered elements to another buffer, and in the end clear() the list and addAll() the elements back to it. Less than ideal due to the exception, surely, and one can't play tricks by removing the stack trace of that to make it faster, because it is important for debugging other cases.

It is an interesting issue though in itself. Perhaps there is something more to be learned here, regarding proxying/decorator designs generally. 

Ideally, all that would be needed to cleanly solve this would be a copy(int from, int to) method, which can be implemented by TransformingRandomAccessList. (Say, in a package-private interface). Alas, while this would "fix" nested transforming lists, it would quickly break if view of another kind was intercepted, e.g. Collections.synchronizedList(Lists.transform(...)), unless this other view took the measures to preserve this extra interface. Look for example a synchronized List view tries not to lose the "RandomAccess"ness of the wrapped list:

    public static <T> List<T> synchronizedList(List<T> list) { return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<T>(list) : new SynchronizedList<T>(list)); }

This clearly cannot scale in face of other interfaces advertizing capabilities in a List. This also reminds me the case where you are given an InputStream, and you cannot tell whether it is buffered or not. You could easily do an instanceof, but if it is wrapped, this capability is hidden, so one can end up with multiple, redundant buffers in a chain. In that case, a method "isBuffered()" would suffice, and it could easily be propagated in decorators, but then we would have an unbounded collection of methods. Perhaps the language is too restrictive to effectively tackle these cases.

2010/7/9 Ditz <stu...@conterra.de>

--

[Dimitris Andreou]

2010/7/9 Dimitris Andreou <jim.a...@gmail.com>

I suggest catching the exception thrown from set(), but not revert to the iterator solution - we know this is a RandomAccess list, so the optimization *is* important. So accumulate the unfiltered elements to another buffer, and in the end clear() the list and addAll() the elements back to it. Less than ideal due to the exception, surely, and one can't play tricks by removing the stack trace of that to make it faster, because it is important for debugging other cases.

Unfortunately I forgot that add() is not be possible in the transformed list. Funny that I was explaining yesterday why this can't work :)

[Willi Schönborn]

On 09/07/10 12:52, Dimitris Andreou wrote:

I suggest catching the exception thrown from set(), but not revert to the iterator solution - we know this is a RandomAccess list, so the optimization *is* important. So accumulate the unfiltered elements to another buffer, and in the end clear() the list and addAll() the elements back to it. Less than ideal due to the exception, surely, and one can't play tricks by removing the stack trace of that to make it faster, because it is important for debugging other cases.

It is an interesting issue though in itself. Perhaps there is something more to be learned here, regarding proxying/decorator designs generally. 

Ideally, all that would be needed to cleanly solve this would be a copy(int from, int to) method, which can be implemented by TransformingRandomAccessList. (Say, in a package-private interface). Alas, while this would "fix" nested transforming lists, it would quickly break if view of another kind was intercepted, e.g. Collections.synchronizedList(Lists.transform(...)), unless this other view took the measures to preserve this extra interface. Look for example a synchronized List view tries not to lose the "RandomAccess"ness of the wrapped list:

    public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<T>(list) :
new SynchronizedList<T>(list));
}

This clearly cannot scale in face of other interfaces advertizing capabilities in a List. This also reminds me the case where you are given an InputStream, and you cannot tell whether it is buffered or not. You could easily do an instanceof, but if it is wrapped, this capability is hidden, so one can end up with multiple, redundant buffers in a chain. In that case, a method "isBuffered()" would suffice, and it could easily be propagated in decorators, but then we would have an unbounded collection of methods. Perhaps the language is too restrictive to effectively tackle these cases.

This is sooo true and sooo sad.

[Dimitris Andreou]

Final remark: regarding the fall-back strategy, it should rather be a ListIterator positioned at the end going backwards, since this should be faster than the other way in cases where the removed elements are more than one, and not slower in the other cases.

2010/7/9 Dimitris Andreou <jim.a...@gmail.com>