Description
The goal of this assignment is to gain experience with an advanced feature in Java called Generics (similar to
the notion of Templates in C++.) Begin by reading the online Java Tutorial section on Generics at
http://docs.oracle.com/javase/tutorial/java/generics/index.html
Another good resource is section 9.4 (p.445-454) of our text. Actually both of these resources offer a lot more
than is necessary for this assignment. The first few subsections of the Java tutorial, or the first 3 or 4 pages of
section 9.4 should suffice.
Java Generics allow you to abstract over types. Consider the IntegerList ADT, several incarnations of which
were covered in class. It would be a simple exercise to convert this to a List of Strings perhaps, and call the
new ADT StringList. Likewise we could write DoubleList, or BooleanList or any other kind of List ADT.
More convenient would be to build a single List-of-anything ADT that could be reused with any data type.
One way to accomplish this would be to create a List of Objects or ObjectList ADT. This is what the book
has done in Chapter 4 (p.211-213) based on an Object array, and in Chapter 5 (p.245-240) based on a linked
list whose nodes hold Object references. Study these examples if you have not already done so. Note this is
similar to what you did in pa4 by building a Queue of Objects. This approach can be problematic however
since nothing would stop the ObjectList client from creating a non-homogeneous List, i.e. one that contains
different kinds of Objects. For instance you could create a List whose first element was a String, second
element an Integer, third element a Scanner, fourth element a String, and fifth element another List. Such
structures can be useful, but Java is a strongly typed language and type mismatch errors may ensue if the Client
programmer forgets which type of Object is in which position. A more Java-like structure would be a
homogeneous List that is rigorously enforced by Java’s type checking mechanism. This is possible using Java
Generics. A limitation of both approaches is that one cannot create Lists of primitive types such as int or
double, only Lists of reference types. This is no real limitation though since every primitive type has a
corresponding reference type like Integer for int or Double for double.
Consider a simple class Pair that encapsulates two data values of the same type, String say.
class Pair{
// fields
private String first;
private String second;
// constructor
Pair(String f, String s){first = f; second = s;}
// ADT operations: getters and setters
String getFirst(){return first;}
String getSecond(){return second;}
void setFirst(String f){first = f;}
void setSecond(String s){second = s;}
// override an Object method
public String toString(){
return “(“+first+”, “+second+”)”;
}
}
2
To convert this ADT to a Generic Pair we introduce a type parameter T. This parameter can be thought of as
a variable for which one can substitute a (reference) type.
class Pair
// fields
private T first;
private T second;
// constructor
Pair(T f, T s){first = f; second = s;} //constructor
// ADT operations: getters and setters
T getFirst(){return first;}
T getSecond(){return second;}
void setFirst(T f){first = f;}
void setSecond(T s){second = s;}
// override an Object method
public String toString(){
return “(“+first.toString()+”, “+second.toString()+”)”;
}
}
Notice the use of type T’s toString() function within Pair’s toString(). This is possible since every Java
Object, including instances of T whatever they may be, have a toString() function. With the Generic Pair
in hand we can create a Pair of Strings as follows.
Pair
As one would expect, the name of the new type Pair
The same generic Pair class can be used to create a pair of Doubles. Recall that Double is the reference type
that encapsulates the double primitive type, and that Double() is its constructor.
Pair
Actually it’s not necessary to call the Double constructor in this case since the compiler can infer that from the
type argument Double. Thus
Pair
is entirely equivalent. The following test file exercises some of these options.
class PairTest{
public static void main(String[] args){
Pair
Pair
System.out.println(ps);
System.out.println(pd);
ps.setFirst(“very”);
pd.setSecond(-3.4);
System.out.println(ps);
System.out.println(pd);
Pair
Pair
System.out.println(pps);
}
}
3
Notice how we created a Pair of Pairs of Strings. Pair
basis for a new Pair type, namely Pair
equals() method to our Pair-of-anything ADT. Following the IntegerList example found on the webpage,
we might try the following as a first draft.
public boolean equals(Object rhs){
boolean eq = false;
Pair
if(rhs instanceof Pair
R = (Pair
eq = (this.first.equals(R.first) && this.second.equals(R.second));
}
return eq;
}
Inserting this into our parameterized Pair class we find that it does not compile. The problem is that the
instanceof operator does not work on parameterized types. Instead we can call the getClass() function on
both this and rhs, then compare the returned values. The public function getClass() belongs to the Object
superclass (like toString() and equals()) and returns the runtime class associated with an Object. Our
second draft is:
public boolean equals(Object rhs){
boolean eq = false;
Pair
if(this.getClass()==rhs.getClass()){
R = (Pair
eq = (this.first.equals(R.first) && this.second.equals(R.second));
}
return eq;
}
Compiling as before we find that there are no errors, but there is a note to the effect that Pair.java uses
unchecked or unsafe operations. If we re-compile with the warnings flag –Xlint, we get explicit warnings
about the cast operation (Pair
$ javac -Xlint Pair.java
Pair.java:33: warning: [unchecked] unchecked cast
R = (Pair
^
required: Pair
found: Object
where T is a type-variable:
T extends Object declared in class Pair
Pair.java:7: warning: [overrides] Class Pair overrides equals, but neither it
nor any superclass overrides hashCode method
class Pair
^
2 warnings
Even though we put the cast inside the conditional if(this.getClass()==rhs.getClass()){..}, the
compiler is not able to prove that a ClassCastException will not be thrown at runtime, and it therefore
provides a warning to the effect that the cast operation is “unchecked”. The second warning seems to say that
if you override equals() you must also override another Object method called hashCode() which we have
not studied.
4
You should always compile your Java programs with the –Xlint flag and pay close attention to the ensuing
warnings, since they often mean there is some logical inconsistency in the program. This is one situation
however where there is no logical flaw in the program and no natural way to get rid of the warnings. Java
provides a mechanism for dealing with such circumstances called Annotations. Annotations provide data about
a program that is not part of the program itself, and has no direct effect on the operation of the code they
annotate. They have several uses, among them to inform the compiler to detect certain (otherwise undetected)
errors or to suppress warnings. Annotations always begin with the ‘@’ character. You can learn more about
them at
http://docs.oracle.com/javase/tutorial/java/annotations/
The annotation we need for the first warning is @SuppressWarnings(“unchecked”) placed before the
function definition. Our third and final draft of function equals() is now:
@SuppressWarnings(“unchecked”)
public boolean equals(Object rhs){
boolean eq = false;
Pair
if(this.getClass()==rhs.getClass()){
R = (Pair
eq = (this.first.equals(R.first) && this.second.equals(R.second));
}
return eq;
}
Compiling this with the –Xlint flag results in no errors, but still one warning regarding the absence of a
hashCode() method.
$ javac -Xlint Pair.java
Pair.java:7: warning: [overrides] Class Pair overrides equals, but neither it
nor any superclass overrides hashCode method
class Pair
^
1 warning
The annotation needed for this warning is @SuppressWarnings(“overrides”). This annotation should be
placed before the class definition itself.
@SuppressWarnings(“overrides”)
class Pair
.
.
.
With both annotations in place we can compile Pair.java with the -Xlint flag and get no errors or warnings.
The complete version of the parameterized Pair class is posted on the webpage along with a test client that
exercises all ADT operations, including the equals() method.
What to Turn In
Convert the IntegerList ADT on the course webpage from a List of ints to a List-of-anything using Java
Generics. Use as starting point either the Linked List version or the Array Doubling version, both found on
the course website under Examples/Lecture/IntegerListADT/. Your new generic type will be called simply
List and will be defined in a file called List.java. Your List class will implement a generic List interface
5
defined in the file ListInterface.java also found on the webpage under Examples/Labs/lab6/. Test your
List by writing a file called ListTest.java that exercises all ADT operations. The same directory contains
files ListIndexOutOfBoundsException.java, ListClient.java, Makefile and model-out.
The Makefile makes the executable jar file ListClient which should produce output identical to the contents
of model-out, provided that your List ADT works properly. Notice that the exception class contains another
annotation @SuppressWarnings(“serial”), without which you would receive warnings under -Xlint about
the lack of a serialVersionUID definition. It seems a hassle to deal with all of these warnings regarding
aspects of Java that we have not studied, and it is tempting to just drop use of the -Xlint compiler flag to get
rid of them. This is not recommended however, since warnings are our first line of defense against logical
problems in our code. You may alter the provided Makefile, but the one you turn in must include the -Xlint
flag when compiling Java sources. Submit the following files to lab6.
Written and submitted by you:
List.java
Makefile
ListTest.java
Provided in Examples/Labs/lab6 and submitted unchanged:
ListInterface.java
ListIndexOutOfBoundsException.java
ListClient.java
The following files found in Examples/Labs/lab6 are not to be submitted: Pair.java, PairTest.java,
model-out. As always start early and ask for help if anything is not completely clear.