Sets.transform(Set<F>, InvertibleFunction<F, T>)

[GoogleCodeExporter]

I'd like to use method: 
Sets.transform(Set<F> fromSet, Function<? super F,? extends T> function)

But there is no such method. I would expect it would behave the way similar
to one in List.transform()

thanks.

Peter B.

Original issue reported on code.google.com by butko...@gmail.com on 13 Aug 2009 at 11:52

[GoogleCodeExporter]

How would you implement Set<T>.contains(Object) in the resulting set? (Or if 
that set 
was not lazy, you wouldn't need this method). Well, you would need the inverse 
function 
T --> F as well (which would imply that such an inverse function *exists*). So 
it's 
lost more complicated than that, and I'm not sure that's the only issue.

Original comment by jim.andreou on 13 Aug 2009 at 11:59

[GoogleCodeExporter]

I didn't notice it's implemented lazy for list, sorry, only now I checked the 
sources.
OK, that's probably too much complicated then.

Original comment by butko...@gmail.com on 13 Aug 2009 at 12:11

[GoogleCodeExporter]

Sets.transform isn't feasible. The problem is that the function could map two 
distinct 
elements in fromSet to the same value, which would violate the requirement that 
all 
elements in the returned set must be unique.

Instead, you can pass a set to Collections2.transform(). If you need a set at 
output, 
copy the collection generated by Collections2.transform() into a set.

Original comment by jared.l....@gmail.com on 13 Aug 2009 at 1:57

• Changed state: WontFix

[GoogleCodeExporter]

To complement Jared response, he describes a situation where there wouldn't 
exist an 
inverse function.

But we should note that if there was a "Bijection" interface, which defined 
both 
directions of a function, such a transform method would be easily defined in 
terms of 
that. 

Original comment by jim.andreou on 13 Aug 2009 at 2:13

[GoogleCodeExporter]

I have a use case for this, where I'm trying to implement a Map. I want the 
keySet to
be a view over the EntrySet, not just a copy. In this (admittedly limited) 
scenario
we have the advantage of being able to guarantee that the transformed elements 
will
indeed be unique. The function here would simply be to pull out the key from the
entry. Of course, as Jim Andreou points out above, you'd need a little more
cleverness for contains(Object), remove etc, but these could be achieved by a
function that boils down to key->underlyingMap.getEntry(key).

The simplest solution is to extend AbstractSet and implement iterator() using
Iterators.transform, but then most operations degenerate to a linear trawl, and 
I
can't easily delegate back to the entrySet/underlying map to do the work.

What would you recommend to implement this? Just a fuller implementation of
AbstractSet? Would there be any scope for requiring the inverse function to be 
given?
You'd shift the burden for guaranteeing correctness to the implementation of the
functions, but would only need it to be valid over the domain of the contents 
of the set.

Set<F> transform(Set<F> fromSet, Function<? super F,? extends T> function, 
Function<?
extends T,? super F> inverse) // generics would need more thought

I realise that this would be a rather complex addition at this stage, but I'd be
interested to hear others' thoughts. My point is that though this won't work in
general, there is a class of cases where you can provide the required 
guarantees such
that it could be well-defined and indeed useful.

Thanks,
Joe

Original comment by joe.kear...@gtempaccount.com on 13 Aug 2009 at 2:29

[GoogleCodeExporter]

Joe, what features do you need that AbstractMap.keySet() doesn't provide?  A 
fast
remove()?  The ability to easily use the keySet() implementation without 
extending
AbstractMap?

Original comment by cpov...@google.com on 13 Aug 2009 at 3:12

[GoogleCodeExporter]

Yes, sort of. I'm not using AbstractMap, but in any case that implementation of
keySet() just creates an AbstractSet over the keys in the entrySet iterator, so 
most
operations are still linear.

We're not using an AbstractMap for slightly obscure memory reasons, we're 
optimising
for a slightly unfortunate case we have where we see a vast number of small or 
empty
maps. The keySet and entrySet fields from AbstractMap turned out to be a 
noticeable
chunk of the memory used. It's an array-backed map akin to the LinearMap 
suggestion
in another bug report. The reason I'm still looking for better-than-linear
performance in the key-set methods is that we're using a binary search over the
(Comparable) keys. Maybe LogarithmicMap would have been better...

I don't think it's particularly complex to just delegate everything back to the
underlying map and translate the details, it would just be nice to have a 
utility to
do it for me. Then again, maybe this doesn't come up that often.

Original comment by joe.kear...@gtempaccount.com on 13 Aug 2009 at 3:38

[GoogleCodeExporter]

Reopening, because in the future we likely will have an invertible Function (we 
call 
it Converter, for better or worse), and when we do, this method is worth 
considering. 
It would simply have to document that your converter had darn well better be a 
strict 
bijection (so no String<->Double or things like that!).

Original comment by kevin...@gmail.com on 4 Nov 2009 at 11:04

• Changed title: Sets.transform(Set, InvertibleFunction<F, T>)
• Changed state: Accepted
• Added labels: Milestone-Post1.0

[GoogleCodeExporter]

This issue has been moved to the Guava project (keeping the same id number). 
Simply replace 'google-collections' with 'guava-libraries' in your address 
bar and it should take you there.

Original comment by kevinb@google.com on 5 Jan 2010 at 11:09

• Changed state: Moved