Generify Multimap<K, V> to Multimap<K, V, C extends Collection<V>>

[GoogleCodeExporter]

Currently the type of value in a Multimap is the concrete Collection<V> and a 
lot of code is 
dedicated to actually providing covariant returns for the implementations like 
ListMultimap, 
SetMultimap etc. An alternative approach is to generify Multimap's collection 
type so that 
ListMultimap<Key, Value> becomes Multimap<Key, Value, List<Value>>.

I had a go at this this morning and got everything to compile. I am attaching a 
patch from 
yesterday's checkout for perusal. I obviously cannot run the tests against it, 
and produce it as a 
proof-of-concept only. There are probably some things around the 
SortedSetMultimap interface 
that could be broken at the moment, and I also haven't aggressively removed all 
the code that 
the generification makes possible (a lot of the concrete implementation classes 
and code become 
redundant).

There are a couple of wrinkles, the createCollection() template method 
generally needs a cast, 
although it is safe. There are a couple of other casts as well.

Apologies in advance for the noise in this patch, there is unrelated noise due 
to the finalisation 
of parameters and other things Eclipse helpfully adds on save. I tried to keep 
everything as close 
to the style of the originals.

It would also probably/arguably be better to make this signature Multimap<K, V, 
Iterable<V> I 
may have a go at that next week.

Original issue reported on code.google.com by jed.wesl...@gmail.com on 13 Jun 2008 at 5:59

Attachments:

• genericMultimap.patch

[GoogleCodeExporter]

Thanks for providing this patch! It looks like you did some really impressive 
work.
I'll look it over in more detail later, but here's my initial reaction.

My biggest concern is about adding a new generic parameter to the public 
interfaces
and classes.

Specifically, you changed
  public interface Multimap<K, V>
to
  public interface Multimap<K, V, C extends Collection<V>>

Since most Java programmers have a limited understanding of generics, I'm 
afraid that
they'd find the new interface more confusing than the existing interface. And 
keeping
the public APIs simple is more important than simplifying the implementation 
code.

Original comment by jared.l....@gmail.com on 13 Jun 2008 at 4:01

[GoogleCodeExporter]

Actually I'd like to propose the following signature:

public interface Multimap<K, V, C extends Iterable<V>>

Certainly the change does make the interface a little more complicated - in 
that the Collection type is 
specified and the value type is then duplicated, but I would argue this 
additional complexity is warranted given 
the additional power it gives. Specifically it does away with the kludgy 
sub-interfaces ListMultimap, 
SetMultimap etc. and does away with the need for additional sub-interfaces to 
support other currently 
unsupported collection types such as Queue, Deque, BlockingQueue, NavigableSet 
and the like. It also allows 
the specification of an implementation type such as a CopyOnWriteArrayList if 
particular runtime semantics 
are required. This change also removes the need for the many versions of 
factory method 
Multimaps.newMultimap(Map, Supplier) as the generified collection type for the 
map value and supplier 
covers all requirements.

Lastly, as hinted before, concerns such as this: 
http://code.google.com/p/google-collections/issues/detail?
id=51#c4 disappear as there is actually a reduction in implementation 
complexity with this change.

Original comment by jed.wesl...@gmail.com on 14 Jun 2008 at 3:45

[GoogleCodeExporter]

Oh, I forgot the other glaring omission in the current Multimap support 
MultisetMultimap!

or Multimap<K, V, C extends Multiset<V>>

Original comment by jed.wesl...@gmail.com on 14 Jun 2008 at 3:55

[GoogleCodeExporter]

BTW. I thought I created this as an Enhancement not a defect. It is clearly the 
former.

Original comment by jed.wesl...@gmail.com on 14 Jun 2008 at 4:56

[GoogleCodeExporter]

Though you bring up some valid points, a Multimap<K, V> interface analogous to 
Map<K,
V> is more natural from a user perspective.

However, I did something similar when I implemented a concurrent multimap 
several
months ago. That code, which isn't ready for release, leaves the Multimap 
interface
as-is but defines the class

abstract class StandardConcurrentMultimap<K, V, C extends Collection<V>>
    implements Multimap<K, V>, Serializable {

whose get method uses covariant return types:
  public C get(K key)

It has the subclass

public final class ConcurrentListMultimap<K, V>
    extends StandardConcurrentMultimap<K, V, CopyOnWriteArrayList<V>>
    implements ListMultimap<K, V> {

which returns a specific collection.
  @Override public CopyOnWriteArrayList<V> get(K key) {

I seriously considered whether to replace StandardMultimap with something of 
that
form, but without the concurrency logic. The main advantages of doing so are 
gaining
access to all collection-specific methods (which is especially nice for 
TreeSet),
having get() return a serializable class, and some more elegant code. However, 
the
current StandardMultimap gains some benefits by returning a view, such as the 
ability
to remove empty collections from the backing map to avoid memory leaks.

In the end, I decided to keep the current StandardMultimap for pragmatic 
reasons.
There wasn't a strong demand for the additional functionality that the change 
would
provide. The current multimap code has been used extensively at Google for 2 
years,
and has been thoroughly reviewed and tested. That made me reluctant to replace 
it,
though I may release a CovariantMultimap implementation at some point in 
addition to
the current implementation.

FYI, the SetMultimap and ListMultimap interfaces are still needed to define 
equals()
correctly. Regarding 
http://code.google.com/p/google-collections/issues/detail?id=51
note that your proposal will provide all methods on the value collection, but 
won't
add any new methods on the keys.

Original comment by jared.l....@gmail.com on 16 Jun 2008 at 5:08

• Added labels: Type-Enhancement
• Removed labels: Type-Defect

[GoogleCodeExporter]

Thanks for the response. I'm not sure about equals(), all you are actually 
doing is explicitly stating the 
contract for List and Set and their composition as part of the Map interface 
equality (each key must map to an 
equal value) - necessary as the mapped value in your case is a Collection, but 
not necessary in the generified 
version as there does not seem to be any new information here.

The StandardMultimap in the patch does not functionally differ from the source 
version. The only significant 
change is in the WrappedCollection where the Ancestor stuff was moved to a 
subclass. It _should_ be 
functionally identical. 

As far as supporting Iterable goes, extracting an immutable 
StandardIterableMultimap class from 
StandardMultimap would be far more preferable rather than making 
StandardMultimap do it. There are all 
sorts of things you obviously could not support.

As far as the #51 comment, you are quite correct and I should have made that 
clear - maybe we should 
parameterise the underlying map :-) Multimap does not implement Map and is 
incompatible so interface 
extension to match NavigableMap would be a copy paste excercise anyway.

Ultimately whether this is accepted comes down to a value call: is the 
parameterisation of the collection a 
burden on the average user of the library or a benefit. I personally (rather 
obviously) vote benefit as I want to 
use it with BlockingQueue.

Original comment by jed.wesl...@gmail.com on 17 Jun 2008 at 8:46

[GoogleCodeExporter]

The current plan to leave the existing interface and implementations as-is. 
However,
we'll add the interface you suggested:

public interface CovariantMultimap<K, V, C extends Collection<V>>
   extends Multimap<K, V> {
 C get(@Nullable K key);
 C replaceValues(K key, Iterable<? extends V> values);
 C removeAll(@Nullable Object key);
}

A new Multimaps method will create instances satisfying that interface:

public static <K, V, C extends Collection<V>> CovariantMultimap<K, V, C>
     newCovariantMultimap(Map<K, C> map, Supplier<? extends C> factory) {

Hopefully, we can find a better name than CovariantMultimap.

That enhancement might come after version 1.0 of Google Collections, since we'd
rather not delay the 1.0 release any longer than necessary.

Thanks for suggesting this!

Original comment by jared.l....@gmail.com on 27 Jun 2008 at 9:06

[GoogleCodeExporter]

Good stuff Jared. I understand the "do no evil" concerns with regard to 
disturbing existing API.

How about GenericMultimap as a name or even GMultimap*? Also, Multimap<K,V> can 
extend 
Generic/Covariant/SuperDuperMultimap<K, V, Collection<V> rather than the other 
way around?

* I quite like the G prefix as it actually means generic but is in the Google 
collections and has the old school 
single letter vibe! probably silly, but kinda amusing...

Original comment by jed.wesl...@gmail.com on 28 Jun 2008 at 9:30

[GoogleCodeExporter]

I've implemented this class, and it will probably be in our next release.

The class is currently called ConcreteMultimap, which isn't a great name. Other
suggestions are welcome.

Original comment by jared.l....@gmail.com on 12 Sep 2008 at 5:46

[GoogleCodeExporter]

Original comment by jared.l....@gmail.com on 12 Sep 2008 at 5:47

• Changed state: Fixed

[GoogleCodeExporter]

Hi Jared,

Is this concrete or covariant MultiMap implementation going to see the light of 
day?

Original comment by jed.wesl...@gmail.com on 30 Jun 2009 at 1:59

[GoogleCodeExporter]

Unforuntately, nobody at Google is using the ConcreteMultimap class. We 
open-source
only those classes that would be heavily used, to keep the library more
comprehensible and to reduce the amount of open-source code we need to maintain.

That's disappointing, since there are cases when it would be helpful, as you're
aware, and I spent a decent amount of time writing ConcreteMultimap.  

Original comment by jared.l....@gmail.com on 30 Jun 2009 at 4:05

[GoogleCodeExporter]

Ah, that's a shame. I ended up writing one for internal use at Atlassian as 
well – which gets some use, and was 
hoping we'd be able to at least compare notes.

Thanks for the update though.

Original comment by jed.wesl...@gmail.com on 1 Jul 2009 at 2:11

[GoogleCodeExporter]

I think that feature would be nice. I am very interesting in MultisetMultimap 
since
that is a easy way to build two dimensions histogram.

Original comment by rcreze...@gmail.com on 28 Oct 2009 at 12:38

[GoogleCodeExporter]

Sorry to bump this issue after over two years of inactivity, but is there any 
way that something like ConcreteMultimap might be resurrected and made 
available for public use?

Nowadays, people are more familiar with complex generics, Multisets, and 
Multimaps, so maybe it would be used more frequently now than when it was 
written.

If not, then a MultisetMultimap would be very handy to have as a consolation 
class.

Thanks!

Original comment by ross.gol...@gmail.com on 22 Dec 2011 at 6:10