Table<R,C,V> - a two-tier map

[GoogleCodeExporter]

Sometimes we just want to specify several keys to one single value.

What we usually implement is this:

Map<String,Map<String,Integer>> map = Maps.newHashMap();
Map<String,Integer> tmp = Maps.newHashMap();
map.put("my",tmp);
// We lose tmp somewhere
map.get("my").put("test",3);
map.get("my").put("number",4);

Is it possible to create some multikey builder? So that we can easily
create a container with several objets and that container would be the key.

Typical interface:

public interface Key {
  public Object get(int index);
  public int getCount();
  public boolean equals(Object o);
  public int hashCode();
  public static interface Arg2<A,B> extends Key {
    public A get1();
    public B get2();
  }
  public static interface Arg3<A,B,C> extends Key {
    public A get1();
    public B get2();
    public C get3();
  }
  // Continuing up to 4 or 5.
}
public interface ComparableKey extends Key, Comparable<ComparableKey> {
  public static interface Arg2<A,B> extends ComparableKey {
    public A get1();
    public B get2();
  }
  // Continuing up to 4 or 5.
}

Then, using it could be straight:

Map<Key.Arg2<String,String>,Integer> map = Maps.newHashMap();
map.put(Maps.key("my","test"), 3);
map.put(Maps.key("my","number"), 4);
// Shorter than previous... and more readable

And if we don't want to specify a number of arguments:

Map<Key,Integer> map = Maps.newHashMap();
map.put(Maps.key("my","test"), 3);
map.put(Maps.key("my","other","test"), 4);

Is the basic idea good?

I've also thought about a MultiKeyMap as implementation, but it would be
much more difficult to implement, I guess. The idea would be to be able to
use get(key1,key2,key3). But how to insert the keys? How to manage the
generics? Too difficult, I think.

Original issue reported on code.google.com by ogregoire on 21 May 2009 at 10:13

[GoogleCodeExporter]

There are several ways you could accomplish this, although it really depends on 
the
types of your composite keys and how you need to be able to access entries. If 
you're
always accessing your values via a full composite key, you should be able to
accomplish this using existing functionality. If you have homogeneous composite 
key
types (all parts of the key are the same type such as your example where your 
key is
all String), you could just use an ImmutableList [1] to build your keys in 
order (or
an ImmutableMap [2] if you want named keys and arbitrary order for constructing 
the
composite key). If you have very small composite keys, you could use a generic 
tuple
such as Pair or Triple and that would also work for heterogeneous key types [3].

    Map<ImmutableList<String>, Integer> listKeyMap = Maps.newHashMap();
    listKeyMap.put(ImmutableList.of("my", "test"), 3);
    listKeyMap.put(ImmutableList.of("my", "number"), 4);

    Map<ImmutableMap<String, String>, Integer> mapKeyMap = Maps.newHashMap();
    mapKeyMap.put(ImmutableMap.of("arg1", "my", "arg2", "test"), 3);
    mapKeyMap.put(ImmutableMap.of("arg1", "my", "arg2", "number"), 4);

    Map<T2<String, String>, Integer> tupleKeyMap = Maps.newHashMap();
    tupleKeyMap.put(t("my", "test"), 3);
    tupleKeyMap.put(t("my", "number"), 4);

    Map<T2<String, Integer>, Integer> heterogeneousTupleKeyMap = Maps.newHashMap();
    heterogeneousTupleKeyMap.put(t("my", 1), 3);
    heterogeneousTupleKeyMap.put(t("my", 2), 4);

For reference, there was a JDK RFE for this a while back that was closed with 
the
comment "This is the sort of special-purpose collection that is more at home in 
third
party libraries than the core Java platform libraries." [4].

[1]:
http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/col
lect/ImmutableList.html
[2]:
http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/col
lect/ImmutableMap.html
[3]: http://code.google.com/p/google-collections/issues/detail?id=43
[4]: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4810923

Original comment by schlo...@gmail.com on 22 May 2009 at 2:54

[GoogleCodeExporter]

Yes, indeed. I don't know why I didn't think about the lists and other 
ImmutableXXX
when creating this ticket. Maybe it was already too late for me ;)

However, I suggested this enhancement essentially for the case #4 that you 
showed.
Where we can have instances of several classes as key. The "Tuple solution" is 
very
interesting indeed, but was apparently ruled out without reason ("I don't see us
including this in the Google Collection Libraries.") 

I think I'll simply take the Tuple.java, after checking if the license is OK 
for our
project.

Original comment by ogregoire on 22 May 2009 at 7:51

[GoogleCodeExporter]

I created a Table interface that maps a two-part key (a row and a column) to a 
value. 
It includes methods like

  V put(R rowKey, C columnKey, V value) 
  V get(Object rowKey, Object columnKey) 

We'd like the Table implementations to be more heavily used within Google 
before we 
open-source them. That way, we can let the design mature, in response to user 
feedback, before exposing it to the outside world.

Original comment by jared.l....@gmail.com on 23 May 2009 at 4:37

[GoogleCodeExporter]

Well, since nearly all multi-key I need are pairs, I think that this will 
indeed be
exactly what I need. So, I'm looking forward to seeing this "validated" and 
implemented.

Original comment by ogregoire on 25 May 2009 at 6:14

[GoogleCodeExporter]

I'd rather see tuple classes. Then all your maps, special and not-so-special,
automagically support multikeys - no need for HashTables, TreeTables,
ConcurrentHashTables, ConcurrentSkipListTables, ImmutableTables, WhateverTables.

Original comment by earwin@gmail.com on 18 Jul 2009 at 8:13

[GoogleCodeExporter]

You can always create your own value classes. That leads to more readable code 
than a 
general tuple.

Original comment by jared.l....@gmail.com on 19 Jul 2009 at 6:49

[GoogleCodeExporter]

Our Table abstraction is actually quite a bit more powerful than you can get 
with just 
tuples-as-keys.

We have a bit of trouble because of the conflict between the idea of a "sparse" 
table 
which is like a map-of-maps and an int-indexed table where every cell is 
assumed to be 
present, which is the kind of table most people are used to. We're working 
through 
this and when we're done we should be able to get the code out to you before 
long.

Original comment by kevin...@gmail.com on 17 Sep 2009 at 5:50

• Changed title: Table<R,C,V> - a two-tier map
• Changed state: Accepted
• Added labels: Milestone-Post1.0

[GoogleCodeExporter]

Original comment by kevin...@gmail.com on 17 Sep 2009 at 5:57

• Added labels: Type-Enhancement

[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