More Generics warnings.

[Roedy Green]

Every time I look at generics it is like I am having a bad dream. The
symbols swirl about in meaningless patterns. It is like trying to
make sense of a Christian speaking in tongues.

Here another puzzle. This little demo QuickSort generates three
generics warnings. I tried many things to get rid of them and gave
up.

Any hints would be appreciated, including ways to think about generics
so they make sense.


// QuickSort.java

package com.mindprod.quicksort;

import java.util.Comparator;

/*
Source code for Hoare's QuickSort

copyright (c) 1996-2008

Roedy Green
Canadian Mind Products
#101 - 2536 Wark Street
Victoria, BC Canada V8T 4G8
tel: (250) 361-9093
mailto:[email protected]
http://mindprod.com

May be freely distributed for any purpose but military.

Version 1.0
1.1 1998-11-10 - add name and address.
1.2 1998-12-28 - JDK 1.2 style Comparator
1.3 2002-02-19 - java.util.Comparator by default.
1.4 2002-03-30 - tidy code.
1.5 2003-05-30 - add dummy private constructor
1.6 2008-01-01 - add generics to comparator

Eric van Bezooijen <[email protected]> was the
original author of this version of QuickSort. I modified
the version he posted to comp.lang.java to use a callback
delegate object. I also made a few optimisations.

I have also posted source for HeapSort and RadixSort both
of which run faster than QuickSort.

*/

// author:Eric van Bezooijen <xxxx>
// modifed by Roedy Green <xxxx>

// to a use a Comparator callback delegate
/**
* QuickSort for objects
*/
public class QuickSort
{
// ------------------------------ FIELDS
------------------------------

private static final boolean DEBUGGING = false;

private static final String EmbeddedCopyright =
"copyright (c) 1996-2008 Roedy Green, Canadian Mind
Products, http://mindprod.com";

// callback object we are passed that has
// a Comparator(Object a, Object b) method.
private Comparator comparator;

// pointer to the array of user's objects we are sorting
private Object[] userArray;

// -------------------------- PUBLIC STATIC METHODS
--------------------------

/**
* sort the user's array
*
* @param userArray Array of Objects to be sorted.
* @param comparator Comparator delegate that can compare two
Objects and tell which should come first.
*/

public static <T> void sort( T[] userArray, Comparator<? super T>
comparator )

{
QuickSort h = new QuickSort();
h.comparator = comparator;
h.userArray = userArray;
if ( h.isAlreadySorted() )
{
return;
}
h.quicksort( 0, userArray.length - 1 );
if ( h.isAlreadySorted() )
{
return;
}
if ( DEBUGGING )
{
// debug ensure sort is working
if ( !h.isAlreadySorted() )
{
System.out.println( "Sort failed" );
}
}
return;
}// end sort

// --------------------------- CONSTRUCTORS
---------------------------

/**
* dummy constructor to prevent its use. Use static method sort.
*/

private QuickSort()
{
}

// -------------------------- OTHER METHODS
--------------------------

// check if user's array is already sorted

private boolean isAlreadySorted()
{
for ( int i = 1; i < userArray.length; i++ )
{
// Clever generics should get rid of the warning here.
// I don't understand generics well enough to fix this.
if ( comparator.compare( userArray[ i ], userArray[ i - 1
] ) < 0 )
{
return false;
}
}

return true;
}// end isAlreadySorted

// Partition by splitting this chunk to sort in two and
// get all big elements on one side of the pivot and all
// the small elements on the other.
private int partition( int lo, int hi )
{
Object pivot = userArray[ lo ];
while ( true )
{
// Clever generics should get rid of the warning here.
// I don't understand generics well enough to fix this.
while ( comparator.compare( userArray[ hi ], pivot ) >= 0
&&
lo < hi )
{
hi--;
}
// Clever generics should get rid of the warning here.
// I don't understand generics well enough to fix this.
while ( comparator.compare( userArray[ lo ], pivot ) < 0
&&
lo < hi )
{
lo++;
}
if ( lo < hi )
{
// exchange objects on either side of the pivot
Object T = userArray[ lo ];
userArray[ lo ] = userArray[ hi ];
userArray[ hi ] = T;
}
else
{
return hi;
}
}// end while
}// end partition

// recursive quicksort that breaks array up into sub
// arrays and sorts each of them.
private void quicksort( int p, int r )
{
if ( p < r )
{
int q = partition( p, r );
if ( q == r )
{
q--;
}
quicksort( p, q );
quicksort( q + 1, r );
}// end if

}// end quicksort

}// end class QuickSort

 

[Lew]

Any hints would be appreciated, including ways to think about generics
so they make sense.

I think you only have to make the class itself generic - see if my mods do any
good. I haven't tried it yet.

// QuickSort.java

package com.mindprod.quicksort;

import java.util.Comparator;

/*
Source code for Hoare's QuickSort

copyright (c) 1996-2008

Roedy Green
Canadian Mind Products
#101 - 2536 Wark Street
Victoria, BC Canada V8T 4G8
tel: (250) 361-9093
mailto:[email protected]
http://mindprod.com

May be freely distributed for any purpose but military.

Version 1.0
1.1 1998-11-10 - add name and address.
1.2 1998-12-28 - JDK 1.2 style Comparator
1.3 2002-02-19 - java.util.Comparator by default.
1.4 2002-03-30 - tidy code.
1.5 2003-05-30 - add dummy private constructor
1.6 2008-01-01 - add generics to comparator

Eric van Bezooijen <[email protected] the
original author of this version of QuickSort. I modified
the version he posted to comp.lang.java to use a callback
delegate object. I also made a few optimisations.

I have also posted source for HeapSort and RadixSort both
of which run faster than QuickSort.

*/

// author:Eric van Bezooijen <xxxx>
// modifed by Roedy Green <xxxx>

// to a use a Comparator callback delegate
/**
* QuickSort for objects
*/
public class QuickSort <T> // <=== !!
{
// ------------------------------ FIELDS
------------------------------

private static final boolean DEBUGGING = false;

private static final String EmbeddedCopyright =
"copyright (c) 1996-2008 Roedy Green, Canadian Mind
Products, http://mindprod.com";

// callback object we are passed that has
// a Comparator( <? super T> a, <? super T> b ) method.
private Comparator <? super T> comparator;

// pointer to the array of user's objects we are sorting
private T [] userArray;

// -------------------------- PUBLIC STATIC METHODS
--------------------------

/**
* sort the user's array
*
* @param userArray Array of Objects to be sorted.
* @param comparator Comparator delegate that can compare two
Objects and tell which should come first.
*/

public static <T> void sort( T[] userArray, Comparator<? super T>
comparator )

{
QuickSort <T> h = new QuickSort <T> ();
h.comparator = comparator;
h.userArray = userArray;
if ( h.isAlreadySorted() )
{
return;
}
h.quicksort( 0, userArray.length - 1 );

assert h.isAlreadySorted(); // asserts can be switched off

if ( h.isAlreadySorted() )
{
return;
}
if ( DEBUGGING )
{
// debug ensure sort is working
if ( !h.isAlreadySorted() )
{
System.out.println( "Sort failed" );
}
}
return;
}// end sort

// --------------------------- CONSTRUCTORS
---------------------------

/**
* dummy constructor to prevent its use. Use static method sort.
*/

private QuickSort()
{
}

// -------------------------- OTHER METHODS
--------------------------

// check if user's array is already sorted

private boolean isAlreadySorted()
{
for ( int i = 1; i < userArray.length; i++ )
{
// Clever generics should get rid of the warning here.
// I don't understand generics well enough to fix this.
if ( comparator.compare( userArray[ i ], userArray[ i - 1
] ) < 0 )
{
return false;
}
}

return true;
}// end isAlreadySorted

// Partition by splitting this chunk to sort in two and
// get all big elements on one side of the pivot and all
// the small elements on the other.
private int partition( int lo, int hi )
{
T pivot = userArray[ lo ];
while ( true )
{
// Clever generics should get rid of the warning here.
// I don't understand generics well enough to fix this.
while ( comparator.compare( userArray[ hi ], pivot ) >= 0
&&
lo < hi )
{
hi--;
}
// Clever generics should get rid of the warning here.
// I don't understand generics well enough to fix this.
while ( comparator.compare( userArray[ lo ], pivot ) < 0
&&
lo < hi )
{
lo++;
}
if ( lo < hi )
{
// exchange objects on either side of the pivot
T tmp = userArray[ lo ];
userArray[ lo ] = userArray[ hi ];
userArray[ hi ] = tmp;
}
else
{
return hi;
}
}// end while
}// end partition

// recursive quicksort that breaks array up into sub
// arrays and sorts each of them.
private void quicksort( int p, int r )
{
if ( p < r )
{
int q = partition( p, r );
if ( q == r )
{
q--;
}
quicksort( p, q );
quicksort( q + 1, r );
}// end if

}// end quicksort

}// end class QuickSort

 

[Owen Jacobson]

I think you only have to make the class itself generic - see if my mods do any
good.  I haven't tried it yet.

Looks good to me (damn you for being faster on the draw, too).

Since Lew has already solved the basic problem I'll take this as a
chance to ruminate about generics in the hopes of shedding some light
on them.

I came to Java from a C++ background, so I already had a working
understanding of C++'s implementation of generics (templates) to
compare to. This has been invaluable for me. In C++, a templated
class or function is not a function itself, but can be used at compile
time to create whole families of related functions. For example,

template <typename T>
T hello () {
return T ();
}

allows the creation of many functions with concrete types. Calling,
for example, hello<string> () causes the compiler to emit code like

template <>
string hello () {
return string (); // an empty string, maybe
}

Java's generics don't work this way, but for simple cases, it's a
useful model. You can pretend that QuickSort.sort (...) is actually a
family of functions, each taking a specific array type (one for
String[], one for Integer[], one for MyFavouriteClass[], et cetera),
and that the compiler uses the right definition at compile time.

The one place this comparison breaks down is in type bounds.

References do not have to have the same type as their referrent. This
is something we deal with regularly, eg., with List: a List reference
might be referring to an ArrayList object. Type bounds on a reference
constrain the set of types allowed in objects assigned to the
reference, like so:

The simplest type bound is the wildcard bound, ?, which means that
objects with any generic type can be assigned to the reference, but
that the generic type cannot be assigned to. Concrete example:

List<?> someList = anyFunctionReturningAList ();

We can be certain that someList refers either to null or to a list of
a single homogenous type (anyFunction might have returned, say,
List<String>, which is a list only containing strings), but we don't
know/care what type that is. This means that code operating on
someList cannot insert elements into the list without a cast, and that
objects can only be read out of the list as Object:

assert (someList.size() > 0);
Object o = someList.get (0);

// someList.add ("Hello, Roedy!"); would be an error

// ((List<Object>) someList).add ("Hello, Roedy!");
// would provoke a warning since it likely breaks the
// type constraint on someList's concrete referrent.

The wildcard constraint can be reduced from "Object" to some more
specific type using the 'extends' constraint. If we wanted to operate
on a List of some subtype of Runnable, to pick a cheesy and unlikely
example, you could write

List<? extends Runnable> someList2 = someSourceOfTasks ();

where someSourceOfTasks might return List<Runnable> or
List<MyTaskType> (assuming MyTaskType extends Runnable).

In fact, the bare wildcard constraint ? is exactly equivalent to the
extends constraint "? extends Object", and we can use Runnable with
someList2 the same way we used Object with someList:

assert (someList2.size () > 0);
Runnable task = someList2.get(0); // This is valid

// MyTaskType task = someList2.get(0); // needs cast

The 'super' constraint goes the other direction: instead of saying
that the generic type must be assignable *to* a specific type, it says
that the generic type must be assignable *from* a specific type.
Cheesy example 3:

public static void populate (List<? super Runnable> tasks) {
tasks.add (new Runnable () { /* ... */ }); // valid
// Runnable r = tasks.get (0); // [0]
}

The line [0] is not valid, because the super constraint imposes no
upper bound on the wildcard. The only type elements of the list are
guaranteed to be assignable to is Object.

Wildcards in class and method declarations work the same way, except
that instead of leaving the specific type anonymous, they create a
type parameter that names it. For example, List's type parameter is
<T>, which is an unconstrained but named type: List instances can be
Lists of any specific type (List<Object>, List<String>, et cetera).
You can also use 'extends' and 'super' constraints; the following
example

public interface TaskList<R extends Runnable> {
}

defines a trivial interface whose type parameter accepts only Runnable
and subtypes of Runnable; within the class references of type R will
be assignable to type Runnable but Runnable is NOT assignable to R.
It's rare to see a super constraint in this context, but it's valid.

Generic promotion works slightly differently from reference
promotion. Using List and ArrayList as examples, the following
promoting assignments are valid:

ArrayList<CharSequence> strings = ... ;

// Constraint includes type:
// CharSequence is a superclass of String.
ArrayList<? super String> a = strings;

// Constraint includes type:
// CharSequence is a subclass of Object.
ArrayList<? extends Object> b = strings;

// Constraint includes type:
// CharSequence is a type.
ArrayList<?> c = strings;


List<CharSequence> d = strings; // widening the base type

 

[Owen Jacobson]

... crud. Posted too early.

Generic promotion works slightly differently from reference
promotion.  Using List and ArrayList as examples, the following
promoting assignments are valid:

  ArrayList<CharSequence> strings = ... ;
  // Constraint includes type:
  // CharSequence is a superclass of String.
  ArrayList<? super String> a = strings;

  // Constraint includes type:
  // CharSequence is a subclass of Object.
  ArrayList<? extends Object> b = strings;

  // Constraint includes type:
  // CharSequence is a type.
  ArrayList<?> c = strings;

  List<CharSequence> d = strings; // widening the base type

// Widen the base type *and* constraint captures type
List<? extends Object> e = strings;

// Widen the base type *and* constraint captures type
List<? super String> f = strings;

and this notable assignment is NOT valid

List<Object> bogus = strings;

for a good reason. Consider the following:

bogus.add (new Object ());
for (CharSequence seq : strings)
System.out.println (seq.length ());

If you force this example using a cast during assignment, you will
discover a ClassCastException during the for loop part, when the JVM
casts the list elements back to CharSequence.

Hope that helps; I have a fairly good grip on generics, so please, if
anything needs more illumination just ask.

-o

 

[Roedy Green]

I think you only have to make the class itself generic - see if my mods do any
good. I haven't tried it yet.

It did not quite work, but when I replaced a couple of Objects with T,
off it went, no errors. Thanks!

I also had a variable named T (violating the convention) that had to
be renamed.

Now if I can only figure out what it means.

 

[Lew]

It did not quite work, but when I replaced a couple of Objects with T,
off it went, no errors. Thanks!

You mean as in

T pivot = userArray[ lo ]; ?

I also had a variable named T (violating the convention) that had to
be renamed.

I saw that. I figured you'd catch it pretty quickly. The version I reposted
had at least some of these changes.

Now if I can only figure out what it means.

I doubt I have Owen's keen grasp, but here's my operational simplification:

1) Any time you see a raw type with any generic anything, get rid of the raw
type. Inverting, that means add a generic decoration to every raw type possible.

public static <T> void sort( T[] userArray, Comparator<? super T>
comparator )

{
QuickSort h = new QuickSort();
h.comparator = comparator;

where the member is defined

private Comparator comparator;

Rule of thumb moves a T into that:

private Comparator <? super T> comparator;

Now the signature matches that of the argument to the static method.

2) A generic member means it belongs to a generic class.

That means

public class QuickSort
becomes
public class QuickSort <T>

at least at first. (Do you want to restrict T? In this case, not.)

3) Anywhere inside the class (with certain @Override exceptions) that you see
'Object' make it 'T'.

private Object[] userArray;
becomes
private T [] userArray;

Whoa! This brings up

4) Generics and arrays don't mix.

But here they do. Why?

5) Inside the warm nest of a generic class you can declare an array statically
as the generic type. Here I mean "statically" not as in "static" but as
opposed to "dynamically" - i.e., "compile-time".

That's enough to make all the changes except renaming variable T. The
compiler alerts you to that if you don't catch it, I think.

I actually named the parametrized type "T" before I realized there was a
variable by that name.

I hope my simplifications prove useful. I am not fully comfortable with
generics yet, although it helps to remember

6) Generics only exist at compile time.

This helps distinguish the use cases for, e.g., using a generic array and when
it doesn't work.