Generic generics help

[wizard of oz]

I'm trying to write a data class using generics. This class is a Sparse
Matrix meaning that it can have many dimensions but not many entries (e.g. a
100 by 100 matrix, but there might only be 10 entries in the matrix).

I intend to use LinkedLists or Trees to manage the row and column keys and
probably a hash Map to manage the cells - but that's not important right
now.

My first step is that in my add method, I need to ensure that my row and
column keys are in my list. I would like to use one common routine for this.
The problem is I can't figure out the right generics syntax.

Here is what I started with:

public class SparseMatrix<R, C, E> {

private TreeSet<R> rowHeaders = new TreeSet<R> ();
private TreeSet<C> colHeaders = new TreeSet<C> ();

public void add (R rowKey, C colKey, E element) {

ensureExists (rowHeaders, rowKey);
ensureExists (colHeaders, colKey);
}

private void ensureExists (TreeSet<? extends Object> treeSet, Object
key) {
Iterator<? extends Object> keyIt = treeSet.iterator();
Object k = null;
while (keyIt.hasNext()) {
k = keyIt.next();
if (k.equals(key)) {
break;
}
k = null;
}
if (k == null) {
treeSet.add (key);
}
}
}


The problem is that the compiler is complaining about the treeSet.add (key)
near the bottom. The error is:
symbol : method add(java.lang.Object)
location: class java.util.TreeSet<capture#346 of ? extends java.lang.Object>
treeSet.add (key);

So far I've searched google for the error message and tried various (random)
combinations of ensureExists method signatures, but just can't get it to
work. The only thing I've found to work is if I duplicate the routine and
overload it as in:
private void ensureExists (TreeSet<R> treeSet, R key) {
....
private void ensureExists (TreeSet<C> treeSet, C key) {
....

Obviously I'd rather not duplicate the method - that seems silly.

Any help appreciated.

TIA

 

[lscharen]

My first step is that in my add method, I need to ensure that my row and
column keys are in my list. I would like to use one common routine for this.
The problem is I can't figure out the right generics syntax.

I think you need to do something like this (untested code). BTW, why
iterate through the set? The contains() method is meant to be used
for membership testing.

    private <K> void ensureExists (TreeSet<K> treeSet, K key) {
if ( !treeSet.contains( key ))
treeSet.add( key );
    }

Honestly, since a set is guaranteed to not have duplicate items, you
don't need the ensureExists() method at all. You could write your add
method as:

private Map<R, Map<C, E>> sparseMap = new HashMap<R, Map<C, E>>();

public void add (R rowKey, C colKey, E element) {

if ( !sparseMap.containsKey( rowKey ))
sparseMap.put( rowKey, new HashMap<C, E>() );

sparseMap.get( rowKey ).put( colKey, element );
}

-Lucas

 

[Mark Space]

public class SparseMatrix<R, C, E> {

private TreeSet<R> rowHeaders = new TreeSet<R> ();
private TreeSet<C> colHeaders = new TreeSet<C> ();

public void add (R rowKey, C colKey, E element) {

ensureExists (rowHeaders, rowKey);
ensureExists (colHeaders, colKey);
}

private void ensureExists (TreeSet<? extends Object> treeSet, Object

The problem is that the compiler is complaining about the treeSet.add

Well, the problem is that "rowHeaders" and "colHeaders" contain types of
R and C respectively, and you're trying to add a type of Object.

If you want to ensure that some type R "rowKey" exists in rowHeaders, then

boolean exists = rowHeaders.contains( rowKey );

will do the whole thing for you. I think however you are confused as to
what a Set like TreeSet will actually do for you. You seem to be trying
to ensure that the /pair/ R, E exists, in which case you need a Map, not
a Set.

E tempElement;
if( (tempElement = rowMap.get( rowKey )) != null ) {
// the pair (rowKey, element) exist
}


You might even put rowKey and colKey together in one single object
though and just do look-ups on that. Faster and easier.

 

[wizard of oz]

Thanks to Mark and Lucas for your replies.

You are both of course correct, in fact I simply add the new keys to the row
and column headers. Because they are sets, I don't get any dups.

However the question is still relevant. What if I want to have a single
method that can manipulate either one of the headers and accept a parameter
appropriate to the "type" of header (i.e. an R or C)?

The signature
private void ensureExists (TreeSet<? extends Object> treeSet, Object
key) {

Allows me to pass either type of header set (row or column), but I can't
pass the parameter, so my question is about how do I get something like
these to work:
private void someMethod (TreeSet<? extends Object> treeSet, <? extends
Object> key) {
or
private void someMethod (TreeSet<? extends Object> treeSet, ? key) {
or
private void someMethod (TreeSet<X> treeSet, X key) {

None of the above worked for me.
Another variant is
private TreeSet<X> subset (TreeSet<X> treeSet, X startKey, X endKey) {
Where X is either an R or C. and the subset returns a subset of values
between the start and end key values.

Surely this is possible!?!?!

 

[lscharen]

However the question is still relevant. What if I want to have a single
method that can manipulate either one of the headers and accept a parameter
appropriate to the "type" of header (i.e. an R or C)?
[snip]

Surely this is possible!?!?!

Yes. Use this method signature

public <K> void ensureExists (TreeSet<K> treeSet, K key)
^^^

I've highlighted the difference between it and the signature of your
method in case you missed the change the first time.

-Lucas

 

[Mark Space]

Surely this is possible!?!?!

No it's not.

In general you may have to abandon generics or pass around type tokens.
Check out _Effective Java_ by Joshua Bloch for more information on
ways to actually use generics.

However for your specific case this will do pretty well:

private <T> boolean ensureExists( Set<T> s, T key ) {
return s.contains( key );
}

Your program does have serious logic errors, you should use the design
Lucas gave you. In particular, ensureExists() won't tell you that the
/pair/ R, C exists, only that someone has stored some R and C in the
structure previously.

 

[wizard of oz]

You're correct, I totally missed it, thanks for highlighting it.

However the question is still relevant. What if I want to have a single
method that can manipulate either one of the headers and accept a
parameter
appropriate to the "type" of header (i.e. an R or C)?
[snip]

Surely this is possible!?!?!

Yes. Use this method signature

public <K> void ensureExists (TreeSet<K> treeSet, K key)
^^^

I've highlighted the difference between it and the signature of your
method in case you missed the change the first time.

-Lucas

 

[Mike Schilling]

Does anyone think Java generics are misnamed?

Suppose I have the following:

LinkedList myList;
LinkedList <Foo> yourList;

Isn't "myList" *more* generic, since it can hold
any type of Object, and can hold a mixture of
Objects (that is, the Objects in myList can have
different types)? Isn't "yourList" *less* generic,
since it can only hold Objects of type <Foo> ?

Look at it this way: a LinkedList (pre-1.5) is a list of Objects.
put() takes an Object, get() returns an Object, etc. If I wanted a
class that was a LinkedList of Strings, I'd have to write one.
Likewise if I wanted a LinkedList of anything else. Each class has to
be coded specifically for the element type I want.

In 1.5, I have LinkedList<T>, which can be a List of any
(non-primitve) type I like. It's *generic*.