Comparables and Generics

[Josef Garvi]

How do I express "A Comparable that can be compared to itself" in generics?

I have a method that takes as parameter an array of Comparables.
Whilst trying to "modernize" this code, I can no longer write simply:

public void myMethod(Comparable[] primaryKeyValues)

but need to add "generic info" to Comparable.
The only requirement I have is that the objects should be able to run a
compareTo() on an instance of their own classes.

--
Josef Garvi

"Reversing desertification through drought tolerant trees"
http://www.eden-foundation.org/

new income - better environment - more food - less poverty

 

[pole]

How do I express "A Comparable that can be compared to itself" in generics?

I have a method that takes as parameter an array of Comparables.
Whilst trying to "modernize" this code, I can no longer write simply:

public void myMethod(Comparable[] primaryKeyValues)

Do you mean taking an array of Comparable of a speficic type?
This is a declaration for a method which takes an array of Comparable<T>
instances:

public <T> void myMethod( Comparable<T>[] primaryKeyValues )

pole

 

[John C. Bollinger]

How do I express "A Comparable that can be compared to itself" in generics?

I have a method that takes as parameter an array of Comparables.
Whilst trying to "modernize" this code, I can no longer write simply:

public void myMethod(Comparable[] primaryKeyValues)

but need to add "generic info" to Comparable.
The only requirement I have is that the objects should be able to run a
compareTo() on an instance of their own classes.

The signature

public <T extends Comparable<T>> void myMethod(T[] primaryKeyValues)

should do the trick. That reads in English something like "a public
method making use of a type, T, that is comparable to itself; returning
no result; and taking as a parameter an array of objects of the
aforementioned type T."

For utmost generality, however, you would want

public <T extends Comparable<? super T>> void myMethod(T[] primaryKeyValues)

which differs from the first example in that it allows key types that
are Comparable to a superclass of their own class. This allows more
types for the keys while still ensuring that all the array elements are
mutually comparable.

 

[Josef Garvi]

How do I express "A Comparable that can be compared to itself" in
generics?

I have a method that takes as parameter an array of Comparables.
Whilst trying to "modernize" this code, I can no longer write simply:

public void myMethod(Comparable[] primaryKeyValues)

Do you mean taking an array of Comparable of a speficic type?
This is a declaration for a method which takes an array of Comparable<T>
instances:

public <T> void myMethod( Comparable<T>[] primaryKeyValues )

pole

Will all the Comparables in primaryKeyValues now have to be of the same
class, or can they be of varying classes (within the same array instance).

I would like to call it like this:

myMethod(new Comparable[] {new Integer(12), new String("Good morning")});

I use Comparable[] rather than Object[] as argument, as each value in the
array should be possible to compare with other values, but only other
values of the same type as itself. (meaning the String will never be
compared to an Integer).


--
Josef Garvi

"Reversing desertification through drought tolerant trees"
http://www.eden-foundation.org/

new income - better environment - more food - less poverty

 

[Josef Garvi]

For utmost generality, however, you would want

public <T extends Comparable<? super T>> void myMethod(T[]
primaryKeyValues)

which differs from the first example in that it allows key types that
are Comparable to a superclass of their own class. This allows more
types for the keys while still ensuring that all the array elements are
mutually comparable.

Whooh, the syntax is overwhelming!
Thanks.

How can I now store the primaryKeyValues into a field of my class?
For example, I'm not allowed to write:

private Comparable<T extends Comparable<? super T>>[] keyValues;


I'm getting the impression that using the function compareTo was a whole
lot easier before Generics... :-(

--
Josef Garvi

"Reversing desertification through drought tolerant trees"
http://www.eden-foundation.org/

new income - better environment - more food - less poverty

 

[John C. Bollinger]

How do I express "A Comparable that can be compared to itself" in
generics?

I have a method that takes as parameter an array of Comparables.
Whilst trying to "modernize" this code, I can no longer write simply:

public void myMethod(Comparable[] primaryKeyValues)

Do you mean taking an array of Comparable of a speficic type?

He was pretty clear, I thought, about "a comparable that can be compared
to itself". This keys on the concept, formalized with generics, that
Comparables are not all comparable to each other, with the implicit
corollary that a particular Comparable is not necessarily even
comparable to itself.

The original declaration translates directly to generics as

public void myMethod(Comparable<?>[] primaryKeyValues)

but that does not achieve what he wants, because it does not constrain
what the Comparables are comparable _to_.

This is a declaration for a method which takes an array of Comparable<T>
instances:

public <T> void myMethod( Comparable<T>[] primaryKeyValues )

That is a little better in that it ensures that the Comparables are all
comparable to the same type, and it also makes that type accessible in
the method body via the type parameter. It does not, however, ensure
that the type T implements Comparable at all, much less Comparable<T>.
See my response to the OP for two related solutions that do solve the
problem.

 

[Josef Garvi]

To clarify things a bit:
What I'm trying to do is to convert the following class so that it works
with Generics (and thus does not cause a compiler warning anymore):


public class ComplexKey implements Comparable<ComplexKey> {

private Comparable[] keyValues;

public ComplexKey(Comparable[] keyValues) {
super();
this.keyValues = keyValues;
}

public int compareTo(ComplexKey compareWith) {
if (compareWith.keyValues.length == keyValues.length) {
for (int i = 0; i < keyValues.length; i++) {
int x =
keyValues.compareTo(compareWith.keyValues); // <- WARNING
if (x != 0) return x;
}
return 0;
} else
throw new ClassCastException("Number of key values do not match.");
}

[...a few other methods...]

}

The purpose of the class is to contain the primary key values of a database
record so it can be used as key in a HashMap.

I get a pesky warning about not being type safe on the line indicated with
the comment, and I can't completely figure out how to rebuild my class:
"Type safety: The method compareTo(Object) belongs to the raw type
Comparable. References to generic type Comparable<T> should be
parameterized"


--
Josef Garvi

"Reversing desertification through drought tolerant trees"
http://www.eden-foundation.org/

new income - better environment - more food - less poverty

 

[John C. Bollinger]

To clarify things a bit:
What I'm trying to do is to convert the following class so that it works
with Generics (and thus does not cause a compiler warning anymore):


public class ComplexKey implements Comparable<ComplexKey> {

private Comparable[] keyValues;

public ComplexKey(Comparable[] keyValues) {
super();
this.keyValues = keyValues;
}

public int compareTo(ComplexKey compareWith) {
if (compareWith.keyValues.length == keyValues.length) {
for (int i = 0; i < keyValues.length; i++) {
int x =
keyValues.compareTo(compareWith.keyValues); // <- WARNING
if (x != 0) return x;
}
return 0;
} else
throw new ClassCastException("Number of key values do not match.");
}

[...a few other methods...]

}

The purpose of the class is to contain the primary key values of a
database record so it can be used as key in a HashMap.

I get a pesky warning about not being type safe on the line indicated
with the comment, and I can't completely figure out how to rebuild my
class:
"Type safety: The method compareTo(Object) belongs to the raw type
Comparable. References to generic type Comparable<T> should be
parameterized"

Before you can solve the problem, you have a fundamental question to
answer: what type are the specific key values supposed to be comparable
to? You can describe the type by means of a type parameter, if you
like, in which case you will need to make the ComplexKey class generic,
with the appropriately chosen type parameter. It might look like this:

public class ComplexKey <T extends Comparable<T>>
implements Comparable<ComplexKey<T>> {

private T[] keyValues;

[...]

public int compareTo(ComplexKey<T> compareWith) {
[...]
int x = keyValues.compareTo(compareWith.keyValues);
[...]
}
}


I suspect, however, that you still have a problem: the key values'
classes in that scheme are going to need to all inherit from (or be) a
common superclass that is Comparable to itself, because putting them all
in the same array requires that they all have types compatible with the
element type of the array. If I am correctly inferring your use of this
class, then this is a fundamental type safety problem with your
approach. (In the sense that its type safety cannot be verified by
compile-time checks.)

 

[Josef Garvi]

Before you can solve the problem, you have a fundamental question to
answer: what type are the specific key values supposed to be comparable
to?

A single instance of ComplexKey might hold something like: a String, an
Integer and a Double. Simply put, the type of values you could find in the
fields of a primary key in a relational db.

You can describe the type by means of a type parameter, if you
like, in which case you will need to make the ComplexKey class generic,
with the appropriately chosen type parameter. It might look like this:

public class ComplexKey <T extends Comparable<T>>
implements Comparable<ComplexKey<T>> {

private T[] keyValues;

[...]

public int compareTo(ComplexKey<T> compareWith) {
[...]
int x = keyValues.compareTo(compareWith.keyValues);
[...]
}
}


I suspect, however, that you still have a problem: the key values'
classes in that scheme are going to need to all inherit from (or be) a
common superclass that is Comparable to itself, because putting them all
in the same array requires that they all have types compatible with the
element type of the array. If I am correctly inferring your use of this
class, then this is a fundamental type safety problem with your
approach. (In the sense that its type safety cannot be verified by
compile-time checks.)

Yes, I think you're correct here.
A single instance of the ComplexKey can hold several different types in its
array, with the only common denominator being that they are comparable to
their own types - not to each other.

They all must implement Comparable, because otherwise the ComplexKey itself
can't become Comparable. (So changing the signature to accepting an array
of Objects would not be satisfactory).

Basically, the ComplexKey class is used for caching record keys from db
tables. In practice, this means that ComplexKeys are compared with other
ComplexKeys built with records from the same table (same order of class
instances in the keyValues array). To be more concrete, an instance of
ComplexKey holding a reference to a record in table "Orders" will only be
compared to other ComplexKeys referencing that same table, "Orders", never
to records in a table "Farmers". Attempting this would most likely throw a
run-time error, as two different tables are likely to have different types
of primary keys.

Does this mean that I should create a subclass of ComplexKey for every
possible combination of field types in the primary key? Rather than
accepting an array with field values, each subclass would have a different
constructor:

public ComplexKey(Integer farmerId)
public ComplexKey(Integer farmerId, Integer Year, Integer speciesId)

This would create an explosion of classes and seems like a lot of work...
:-( And seem a lot less "generic" than what I'm doing today!

--
Josef Garvi

"Reversing desertification through drought tolerant trees"
http://www.eden-foundation.org/

new income - better environment - more food - less poverty

 

[Chris Uppal]

Basically, the ComplexKey class is used for caching record keys from db
tables. In practice, this means that ComplexKeys are compared with other
ComplexKeys built with records from the same table (same order of class
instances in the keyValues array). To be more concrete, an instance of
ComplexKey holding a reference to a record in table "Orders" will only be
compared to other ComplexKeys referencing that same table, "Orders", never
to records in a table "Farmers". Attempting this would most likely throw a
run-time error, as two different tables are likely to have different types
of primary keys.

Then attempting to force static type checking using generics strikes me as a
massive waste of time. You are /only/ arguing with the compiler about whether
you know what you are doing, not producing productive code.

I'd treat everything as Objects; let generics go hang. Stick some type
assertions in to make the design more self-documenting and to aid debugging if
you feel you need it.

-- chris

 

[pole]

He was pretty clear, I thought, about "a comparable that can be compared
to itself". This keys on the concept, formalized with generics, that
Comparables are not all comparable to each other, with the implicit
corollary that a particular Comparable is not necessarily even
comparable to itself.
[...]

Ok, I agree whith you, even if I could never imagine a Comparable which
is not comparable to itself .

 

[Josef Garvi]

Then attempting to force static type checking using generics strikes me as a
massive waste of time. You are /only/ arguing with the compiler about whether
you know what you are doing, not producing productive code.

True indeed.

I'd treat everything as Objects; let generics go hang. Stick some type
assertions in to make the design more self-documenting and to aid debugging if
you feel you need it.

That's sounds fine.
But even if I treat the keyValues array as Object[], how can I compare it's
items without throwing compiler warnings?

For instance:
int x = ((Comparable)keyValues).compareTo(compareWith.keyValues);

will still bug me with the lack of type safety...
Put in it's context it looks like this:


public int compareTo(ComplexKey arg0) {
ComplexKey compareWith = arg0;
if (compareWith.keyValues.length == keyValues.length) {
for (int i = 0; i < keyValues.length; i++) {
// Warning on the line below.
int x = ((Comparable)keyValues).
compareTo(compareWith.keyValues);
if (x != 0) return x;
}
return 0;
} else
throw new ClassCastException("Number of key values do not match.");
}


I don't want to turn off generics warnings for my entire project, as they
are good to have in other circumstances.


--
Josef Garvi

"Reversing desertification through drought tolerant trees"
http://www.eden-foundation.org/

new income - better environment - more food - less poverty

 

[John C. Bollinger]

A single instance of ComplexKey might hold something like: a String, an
Integer and a Double. Simply put, the type of values you could find in
the fields of a primary key in a relational db.

That's as I guessed.

Yes, I think you're correct here.
A single instance of the ComplexKey can hold several different types in
its array, with the only common denominator being that they are
comparable to their own types - not to each other.

They all must implement Comparable, because otherwise the ComplexKey
itself can't become Comparable. (So changing the signature to accepting
an array of Objects would not be satisfactory).

Basically, the ComplexKey class is used for caching record keys from db
tables. In practice, this means that ComplexKeys are compared with other
ComplexKeys built with records from the same table (same order of class
instances in the keyValues array). To be more concrete, an instance of
ComplexKey holding a reference to a record in table "Orders" will only
be compared to other ComplexKeys referencing that same table, "Orders",
never to records in a table "Farmers". Attempting this would most likely
throw a run-time error, as two different tables are likely to have
different types of primary keys.

So why do the ComplexKey objects need to be Comparable? That's wholly
unnecessary for simple caching. Is there some other requirement here
that you haven't discussed yet?

Does this mean that I should create a subclass of ComplexKey for every
possible combination of field types in the primary key? Rather than
accepting an array with field values, each subclass would have a different
constructor:

public ComplexKey(Integer farmerId)
public ComplexKey(Integer farmerId, Integer Year, Integer speciesId)

This would create an explosion of classes and seems like a lot of
work... :-( And seem a lot less "generic" than what I'm doing today!

And it would not get you where you want to be without even more work
than you may realize. As I wrote before, you have a *fundamental* type
safety problem with your current code. Even if there were a way to
express them, the type constraints you want are not sufficient to
guarantee type safety for the elements of an array as you wish to use
them. On the other hand, type constraints sufficient to guarantee type
safety for your problem are stronger than you can work with. The same
would apply if you were using a List of the key fields instead of an
array. The only way I can see that you could obtain type safety is to
write ComplexKey subclasses that were completely independent, storing
the key fields in individual instance variables and not relying on a
common comparison engine. In principle one could write code to generate
such classes on the fly, but that's an extreme workaround for a minor
problem.

I encourage you, therefore, to take this opportunity to look at the
bigger picture. Do ComplexKey objects _really_ need to be Comparable?
My general rule of thumb is to rely on the DB to do what DBs are good
at, and sorting records is one of those things.

 

[Josef Garvi]

[...]

I encourage you, therefore, to take this opportunity to look at the
bigger picture. Do ComplexKey objects _really_ need to be Comparable?
My general rule of thumb is to rely on the DB to do what DBs are good
at, and sorting records is one of those things.

Thanks for your great help and advice.
The Comparable interface was meant to allow sorting, but after looking at
it closely, I do think I can live without that. A bit frustrating though,
when new language features "cripple" ones possibilities... Ok, I know,
it's just a question of adjusting mentally to the new paradigms....

--
Josef Garvi

"Reversing desertification through drought tolerant trees"
http://www.eden-foundation.org/

new income - better environment - more food - less poverty

 

[John C. Bollinger]

[...]

I encourage you, therefore, to take this opportunity to look at the
bigger picture. Do ComplexKey objects _really_ need to be Comparable?
My general rule of thumb is to rely on the DB to do what DBs are good
at, and sorting records is one of those things.

Thanks for your great help and advice.

You're welcome.

The Comparable interface was meant to allow sorting, but after looking
at it closely, I do think I can live without that. A bit frustrating
though, when new language features "cripple" ones possibilities...
Ok, I know, it's just a question of adjusting mentally to the new
paradigms....

Nothing has been crippled. You can continue to do as you have always
done, and put up with the type safety warnings. Type safety checking is
helpful in developing correct code, but it should not be viewed as a
straight jacket. If you have sufficient reason for confidence that your
scheme will not in practice ever produce a ClassCastException or
otherwise produce type-related mysterious failures, then you should feel
justified in documenting and subsequently ignoring the warnings. If you
do not have such confidence then by resolving the warnings you will have
made your product more robust.

Good luck,