10. Generics Lesson

Java Generics

Java Generics

Show Collapsed Show Notes Show Solutions Full Page Print Max Width Show All Hide All

Lesson Objectives

Motivate and introduce generic classes. We will use the generic Node class as our example. The focus is on code interpretation and understanding how to use an existing generic class.

Part 1: Motivation

Getting Started: Removing Method Redundancy

Is there a better way to write code to print stars than what is presented below? Discuss with your groups. What would you do instead? If you have an alternative, discuss why yours is better.

Example Code

public static void printFourStars() {
   for (int i = 0; i < 4; i++) {
      System.out.print("*");
   } // for
   System.out.println();
} // printFourStars

public static void printFiveStars() {
   for (int i = 0; i < 5; i++) {
      System.out.print("*");
   } // for
   System.out.println();
} // printFiveStars

Sample Solution

public static void printStars(int count) {
   for (int i = 0; i < count; i++) {
      System.out.print("*");
   } // for
   System.out.println();
} // printStars

Factor out the common code into a single method that use one a method parameter to so that callers can supply different values, as needed!

Motivating Example: Removing Class Redundancy

GOAL: Imagine we want to create a linked list that can store items with a datatype other than String. For example, maybe you are implementing a playlist (of type Song) or a wait list (of type People).

ONE IDEA: You might be tempted to create multiple versions of the Node class as seen below:

What is problematic about this approach?

We have multiple files with essentially the same code!

The class names (and constructors) and datatypes for item and next are different, but everything else is the same.

Can an interfaces or inheritance relationship help?

If there was a common method with the exact same signature that we want to make polymorphic calls to, then an interface or a parent class could help, but there are no such methods depicted.

If there was a common instance variable or method with the same signature and the same code, then placing it into a parent class would help us write that once instead of multiple times, but no such methods are depicted.

What can we do?

GENERICIZE: Factor out the differences into a single generic class with a type parameter.

This is the same thing we saw with the method example example, but instead of factoring out a value into a parameter, you factor out a type into a parameter using Java's generics syntax.

Solution: Removing Class Redundancy

Instead of creating separate classes for each type, Generics allow us to create a single generic class with a type parameter.

Without Generics

With Generics

Note

We won't implement this in class - we implement a similar class (ShippingContainer) in the "Generic Classes" video assigned earlier this week.

• When the generic class is used, we parameterize it – that simply means that we supply a type argument for its type parameter. This is similar to how we supply an argument for a method parameter when calling a method.

• Therefore, a type parameter is essentially a variable for a type, and a type argument is a specific type that we supply for a a type parameter.

Can you name all of type parameters declared by Node?

• There is only one type parameter.

• The name of that type parameter is ItemType.

Part 2: Code Interpretation

Activity: Code Interpretation (1)

What is the output of the code below?

Important

Assume the Person class exists and has a constructor that takes the name of the person. You can also assume it has a getter and setter for name.

Node<String> head1 = null;
head1 = new Node<String>("a", head1);
head1 = new Node<String>("b", head1);

System.out.println(head1.getItem());

Person joe = new Person("Joe");
Person sally = new Person("Sally");

Node<Person> head2 = new Node<Person>(sally);
head2.setNext(new Node<Person>(joe));
Node<Person> tail2 = head2.getNext();

System.out.println(tail2.getItem().getName());

Solution

Listing 82 Output from the code above

b
joe

Activity: Code Interpretation (2)

For each line below, state whether it is a proper use of the generic Node class. If not, say why not.

Important

Assume the Person class exists and has a constructor that takes the name of the person. You can also assume it has a getter and setter for name.

Node head1 = null;
Node<String> head2 = new Node<>("A");
Node<Person> head3 = new Node<>(4.2);

Node<Person> head4 = new Node<Person>(new Person("Joe"));
String val = head4.getItem();

head4.setNext(new Node<String>("Sally"));

Node<Double> head5 = new Node<Double>(4.2);
head5.setItem("ABC");

Node head6 = new Node("Sally");

Solution

1. No, this is a raw type
2. Yes, this is valid
3. No, this will not compile because we are putting a
   floating point value into a ``Node<Person>``.
5. Yes, this is valid
6. No, the return type of ``getItem`` when called
   on ``head4`` will be ``Person``.
8. No, the ``setNext`` method expects a ``Node<Person>``
   when called on ``head4``.
10. Yes, this is valid.
11. No, this will not compile. The ``setItem`` method
    expects a ``Double`` when called on ``head5``.
13. No, this uses a raw type.

Part 3: Code Writing with Node<ItemType>

Getting Started

Consider the following method:

Listing 83 In Driver.java

/**
 * Return the item at the specified {@code index} position in a linked list.
 * @param head The first node in the linked list.
 * @param index The position of the node (distance from the first node).
 * @return The item in the node at the specified {@code index}.
 */
public static String getListItem(Node<String> head, int index) {
    throw new UnsupportedOperationException("not implemented");
} // getListItem

Example: Code using the getListItem method

Listing 84 In Driver.java

public static void main(String[] args) {

    // d, c, b, a
    Node<String> head1 = null;
    head1 = new Node<String>("a", head1);
    head1 = new Node<String>("b", head1);
    head1 = new Node<String>("c", head1);
    head1 = new Node<String>("d", head1);

    String second = Driver.getListItem(head1, 1);

    System.out.println(second);
    System.out.println(second.length());

} // main

• What are the outputs?

Solution

Listing 85 Output from the code above

c
1

Activity: Write the getListItem method

public static String getListItem(Node<String> head, int index) {
    //
    // your code here
    //
} // getListItem

In your groups, write the code for getListItem on your exit ticket (and in your own notes). Be sure to include the method signature. Do not include the Javadoc comment, unless you need it for your notes.

Sample Solution: The getListItem method (1)

Listing 86 In Driver.java: Without Temporary Variable

public class Driver {

    public static String getListItem(Node<String> head, int index) {
        for (int i = 0; i < index; i++) {
            head = head.getNext();
        } // for
        return head.getItem();
    } // getListItem

} // Driver

Sample Solution: The getListItem method (2)

Listing 87 In Driver.java: With Temporary Variable

public class Driver {

    public static String getListItem(Node<String> head, int index) {
        Node<String> current = head;
        for (int i = 0; i < index; i++) {
            current = current.getNext();
        } // for
        return current.getItem();
    } // getListItem

} // Driver

Part 4: Writing Generic Methods

Generic Methods

Consider the method below (repeated from the previous section). Is it currently a generic method?

Listing 88 In Driver.java

/**
 * Return the item at the specified {@code index} position in a linked list.
 * @param head The first node in the linked list.
 * @param index The position of the node (distance from the first node).
 * @return The item in the node at the specified {@code index}.
 */
public static String getListItem(Node<String> head, int index) {
   // ...
} // getListItem

Solution

This is not a generic method as it does not have a generic type parameter. While the Node class is generic, the head variable is of type Node<String> which uses a specific type argument that doesn't change.

Discussion: Generic Methods

What if we want to be able to get a specific item from a linked list where all of the nodes refer to Song objects? What about Person objects and other kinds of object?

public static String getListItem(Node<String> head, int index) { ...

public static Song getListItem(Node<Song> head, int index) { ...

public static Person getListItem(Node<Person> head, int index) { ...

public static Shape getListItem(Node<Shape> head, int index) { ...

Can we write one method that works for all reference types?

Our solution should be one drop in replacement that works in all of these scenarios:

Would this Work?

public static Object getListItem(Node<Object> head, int index) { ...

Thinking about getListItem with Node<Object>

This will NOT work as a drop in replacement! In your groups,

1. Write down two or more reasons why the the last version of getListItem with Node<Object> cannot be used as a drop in replacement for the other versions of getListItem in all cases.

2. Write down one small code example of something that you can do with one of the other versions of getListItem that you cannot do with the one with Node<Object>.

Sample Solutions

1. Reasons:

   1. The return type is less specific; and

   2. None of the other parameterized Node<ItemType> types are compatible with Node<Object>.

2. Our example from earlier illustrates this:

   Listing 89 Assuming String getListItem(Node<String>, int)

   // c, b, a
   Node<String> head1 = ...;
   
   String second = Driver.getListItem(head1, 1);
   
   System.out.println(second);
   System.out.println(second.length());
   

   Listing 90 Assuming Object getListItem(Node<Object>, int)

   // c, b, a
   Node<String> head1 = ...;
   
   String second = Driver.getListItem(head1, 1); // will not compile
   
   System.out.println(second);
   System.out.println(second.length());
   

   Listing 91 Assuming Object getListItem(Node<Object>, int)

   // c, b, a
   Node<String> head1 = ...;
   
   Object second = Driver.getListItem(head1, 1); // still won't compile, but let's pretend
   
   System.out.println(second);
   System.out.println(second.length()); // will not compile
   

Lack of Covariance

Parameterized types are NOT covariant in Java. Here is the actual hierarchy that we are working with:

For example:

• String extends Object

• Node<String> extends Object (NOT Node<Object>)

Genericize!

Activity: Write the generic getListItem signature

In your groups, write the method signature for the generic getListItem method on your exit ticket. Make sure to include a type parameter!

Solution

public static <T> T getListItem(Node<T> head, int index) { ... }

Write the generic getListItem method

Let's write the method body together.

Sample Solution: The generic getListItem method

public class Driver {

    /**
     * Return the item at the specified {@code index} position in a linked list.
     * @param <T> The item type.
     * @param head The first node in the linked list.
     * @param index The position of the node (distance from the first node).
     * @return The item in the node at the specified {@code index}.
     */
    public static <T> T getListItem(Node<T> head, int index) {
        for (int i = 0; i < index; i++) {
            head = head.getNext();
        } // for
        return head.getItem();
    } // getListItem

} // Driver

Note the placement of <T>. It declares that getListItem has one type parameter named T

• it is used in the return type; and

• it is used as the type argument for ItemType in Node<T>.

Example: Code using the generic getListItem method

Node<String>

// c, b, a
Node<String> head1 = null;
head1 = new Node<String>("a", head1);
head1 = new Node<String>("b", head1);
head1 = new Node<String>("c", head1);

// Fill in the code below to get the second item in the list using getListItem
String second = ______________;

System.out.println(second);
System.out.println(second.length());

Solution

Listing 92 The line with the blank should be:

String second = Driver.<String>getListItem(head1, 1);

Node<Person>

// Pam, Bob, Sue
Node<Person> head1 = null;
head1 = new Node<Person>(new Person("Sue"), head1);
head1 = new Node<Person>(new Person("Bob"), head1);
head1 = new Node<Person>(new Person("Pam"), head1);

// Fill in the code below to get the second item in the list using getListItem
Person second = _______________;

System.out.println(second.getName());
System.out.println(second.getName().length());

Solution

Listing 93 The line with the blank should be:

Person second = Driver.<Person>getListItem(head1, 1);

Discussion: Node<Shape>

Code Interpretation (1)

Will this code compile? Write your answer on your exit ticket. If not, say why not. If so, what is the output?

// Rectangle(w=2.0, h=1.0), Square(side=1.0), Circle(r=1.0)
Node<Shape> head1 = null;
head1 = new Node<Shape>(new Rectangle(2.0, 1.0), head1);
head1 = new Node<Shape>(new Square(1.0), head1);
head1 = new Node<Shape>(new Circle(1.0), head1);

Shape second = Driver.<Shape>getListItem(head1, 1);

System.out.println(second.getArea());

Solution

Yes, it will compile!

Code Interpretation (2)

Will this code compile? Write your answer on your exit ticket. If not, say why not. If so, what is the output?

// Rectangle(w=2.0, h=1.0), Square(side=1.0), Circle(r=1.0)
Node<Shape> head1 = null;
head1 = new Node<Rectangle>(new Rectangle(2.0, 1.0), head1);
head1 = new Node<Square>(new Square(1.0), head1);
head1 = new Node<Circle>(new Circle(1.0), head1);

Shape second = Driver.<Shape>getListItem(head1, 1);

System.out.println(second.getArea());

Solution

No, it will not compile. Node<Rectangle> is not compatible with Node<Shape>.

Lack of Covariance

Parameterized types are NOT covariant in Java. Here is the actual hierarchy that we are working with:

Generic Code Writing Activities

prepend

Activity: Write the prepend method

Listing 94 The prepend method

/**
 * Prepend an item to a linked list (add to beginning).
 * @param <T> The item type.
 * @param head The first node in the linked list.
 * @param item The item to prepend.
 * @return The first node in the updated linked list.
 */
public static <T> Node<T> prepend(Node<T> head, T item) {
    throw new UnsupportedOperationException("not implemented");
} // prepend

In your groups, write the code for prepend on your exit ticket (and in your own notes). Be sure to include the method signature. Do not include a Javadoc comment, unless you need it for your notes.

Listing 95 Example code using prepend.

// a, b, c
Node<String> head = null;
head = Driver.<String>prepend(head, "c");
head = Driver.<String>prepend(head, "b");
head = Driver.<String>prepend(head, "a");

Sample Solution: The prepend method (1)

public static <T> Node<T> prepend(Node<T> head, T item) {
    Node<T> newNode = new Node<T>(item, head);
    return newNode;
} // prepend

Sample Solution: The prepend method (2)

public static <T> Node<T> prepend(Node<T> head, T item) {
    return new Node<T>(item, head);
} // prepend

append

Activity: Write the append method

Listing 96 The append method.

/**
 * Append an item to a linked list (add to end).
 * @param <T> The item type.
 * @param head The first node in the linked list.
 * @param item The item to append.
 * @return The first node in the updated linked list.
 */
public static <T> Node<T> append(Node<T> head, T item) {
    throw new UnsupportedOperationException("not implemented");
} // append

In your groups, write the code for append on your exit ticket (and in your own notes). Be sure to include the method signature. Do not include a Javadoc comment, unless you need it for your notes.

Listing 97 Example code using append.

// c, b, a
Node<String> head = null;
head = Driver.<String>append(head, "c");
head = Driver.<String>append(head, "b");
head = Driver.<String>append(head, "a");

Sample Solution: The append method

public static <T> Node<T> append(Node<T> head, T item) {
    Node<T> newNode = new Node<T>(item);
    Node<T> current = head;
    if (head == null) {
        // list is empty, so the new node is now the head
        head = newNode;
    } else {
        // list is not empty, so find the last node
        while (current.getNext() != null) {
            current = current.getNext();
        } // while
        current.setNext(newNode);
    } // if
    return head;
} // append

setAll

Activity: Write the setAll method

Listing 98 The setAll method.

/**
 * Set all the items in a linked list to the specified item value.
 * @param <T> The item type.
 * @param head The first node in the linked list.
 * @param item The item value to set.
 * @return The first node in the updated linked list.
 */
public static <T> Node<T> setAll(Node<T> head, T item) {
    throw new UnsupportedOperationException("not implemented");
} // setAll

In your groups, write the code for setAll on your exit ticket (and in your own notes). Be sure to include the method signature. Do not include a Javadoc comment, unless you need it for your notes.

Listing 99 Example code using setAll.

// hello, world
Node<String> head = null;
head = Driver.<String>append(head, "hello");
head = Driver.<String>append(head, "world");

// again, again
head = Driver.<String>setAll(head, "again");

Sample Solution: The setAll method

public static <T> Node<T> setAll(Node<T> head, T item) {
    Node<T> current = head;
    while (current != null) {
        current.setItem(item);
        current = current.getNext();
    } // while
    return head;
} // setAll

max

Activity: Write the max method

Listing 100 The max method.

/**
 * Return the max value (or a max value) in the linked list.
 * @param <T> The item type.
 * @param head The first node in the linked list.
 * @throws NullPointerException If {@code head} is {@code null}.
 * @return The max value.
 */
public static <T> T max(Node<T> head) {
   throw new UnsupportedOperationException("not implemented");
} // max

In your groups, write the code for max on your exit ticket (and in your own notes). Be sure to include the method signature. Do not include a Javadoc comment, unless you need it for your notes.

Listing 101 Example code using max.

// 7, 10, 8
Node<Integer> head = null;
head = Driver.<Integer>append(head, 7);
head = Driver.<Integer>append(head, 10);
head = Driver.<Integer>append(head, 8);

// prints 10
System.out.println(Driver.<Integer>max(head));

Sample Solution: The max method

Not possible! It is not actually possible to write the max method with the method signature that was provided. Let's discuss why not…

• What can T be replaced with?

• Given two items of type T, is it possible to:

  • determine whether they are considered equal?

  • determine which one is considered greater?

Part 5: A Generic max method?

Discussion: The bounded generic max method

What do we need to be able to guarantee about the things in the array? Is there a way to guarantee that types have certain methods in Java?

public static <T> T max(T[] items) {
    //
    // ...
    //
} // max

Activity: Write the bounded generic max method

public static <T extends Comparable<T>> T max(T[] items) {
   T maxItem = ________;                       // Line 1
   for (int i = 1; i < items.length; i++) {
       T item = _______;                       // Line 2
       int result = _______;                   // Line 3
       if (result > 0) {
           maxItem = item;
       } // if
   } // for
   return maxItem;
} // max

Write the code for the bounded max method on your exit ticket (and in your own notes). Be sure to include the method signature. Do not include a Javadoc comment, unless you need it for your notes.

Sample Solution: The bounded generic max method

public static <T extends Comparable<T>> T max(T[] items) {
      T maxItem = items[0];
      for (int i = 1; i < items.length; i++) {
          T item = items[i];
          int result = item.compareTo(maxItem);
          if (result > 0) {
              maxItem = item;
          } // if
      } // for
      return maxItem;
} // max

Discussion: Leveraging the bounded generic max method

Can we use the bounded version of the max method to find a max String in a String[]? If so, how will it do the comparisons?

• java.base/java.lang.String

Solution

Yes! String implements Comparable<String> so it is a valid replacement for the type parameter T. The comparisons will be done using the built-in compareTo method in the String class.

Discussion: Will max work?

Can we use our bounded version of the max method with Movie and Person? In other words, are Movie and Person valid type replacements for T?

• cs1302.oracle.model.Movie

• cs1302.oracle.model.Person

Solution

Movie does not implement Comparable<Movie>, so it is not a valid type replacement for T. Person does implement Comparable<Person>, so it is a valid type replacement for T.