Unit 23: Generics

Learning Objectives

After completing this unit, students should be able to:

• define and use generic classes and generic methods with appropriate type parameters
• distinguish clearly between type parameters, type arguments, and parameterized types
• explain how generics enforce compile-time type safety and eliminate certain classes of runtime errors
• apply bounded type parameters to constrain permissible operations on type variables
• reason about how generics reduce code duplication while preserving static typing guarantees

Overview

In earlier units, we saw how polymorphism allows us to write general code that works for many types, often by treating objects uniformly as Object or through interfaces. While flexible, this approach can sacrifice type precision and shift certain errors from compile time to run time.

This unit introduces generics, a language mechanism that allows us to write reusable and abstract code without giving up static type safety. By parameterizing classes and methods with types, we let the compiler track and enforce relationships between values, preventing common mistakes such as invalid casts. Generics form a key bridge between abstraction and safety in Java, and understanding them is essential for reasoning about correctness in larger systems.

The Pair class

Sometimes it is useful to have a lightweight class to bundle a pair of variables together. One could, for instance, write a method that returns two values. The example defines a class IntPair that bundles two int variables together. This is a utility class with no semantics or methods associated with it. So, we did not attempt to hide the implementation details.

class IntPair {
  private int first;
  private int second;

  public IntPair(int first, int second) {
    this.first = first;
    this.second = second;
  }

  int getFirst() {
    return this.first;
  }

  int getSecond() {
    return this.second;
  }
}

This class can be used, for instance, in a function that returns two int values.

IntPair findMinMax(int[] array) {
  int min = Integer.MAX_VALUE;  // stores the min
  int max = Integer.MIN_VALUE;  // stores the max
  for (int i : array) {
    if (i < min)  {
      min = i;
    }
    if (i > max) {
      max = i;
    }
  }
  return new IntPair(min, max);
}

We could similarly define a pair class for two doubles (DoublePair), two booleans (BooleanPair), etc. In other situations, it is useful to define a pair class that bundles two variables of two different types, say, a Customer and a ServiceCounter; a String and an int; etc.

We should not, however, create one class for each possible combination of types. A better idea is to define a class that stores two Object references:

class Pair {
  private Object first;
  private Object second;

  public Pair(Object first, Object second) {
    this.first = first;
    this.second = second;
  }

  Object getFirst() {
    return this.first;
  }

  Object getSecond() {
    return this.second;
  }
}

At the cost of using a wrapper class in place of primitive types, we get a single class that can be used to store any type of value.

You might recall that we used a similar approach for our contains method to implement a general method that works for any type of object. Here, we are using this approach for a general class that encapsulates any type of object.

Unfortunately, the issues we faced with narrowing type conversion and potential runtime errors apply to the Pair class as well. Suppose that a function returns a Pair containing a String and an Integer, and we accidentally treat this as an Integer and a String instead, the compiler will not be able to detect the type mismatch and stop the program from crashing during runtime.

Pair foo() {
  return new Pair("hello", 4);
}

Pair p = foo();
Integer i = (Integer) p.getFirst(); // runtime ClassCastException

To reduce the risk of human error, what we need is a way to specify the following: suppose the type of first is \(S\) and type of second is \(T\), then we want the return type of getFirst to be \(S\) and of getSecond to be \(T\).

Generic Types

In Java and many other programming languages, the mechanism to do this is called generics or templates. Java allows us to define a generic type that takes other types as type parameters, just like how we can write methods that take in variables as parameters.

Declaring a Generic Type

Let's see how we can do this for Pair:

class Pair<S,T> {
  private S first;
  private T second;

  public Pair(S first, T second) {
    this.first = first;
    this.second = second;
  }

  public S getFirst() {
    return this.first;
  }

  public T getSecond() {
    return this.second;
  }
}

We declare a generic type by specifying its type parameters between < and > when we declare the type. Similar to how the parameters to a method can be used as variables within the method, type parameters can be used as type variables . By convention, we use a single capital letter to name each type variable. These type variables are scoped within the definition of the generic type.

In the example above, we have a generic class Pair<S,T> (read "pair of S and T") with S and T as type parameters. This declaration of generic class also declares S and T as type variables. We can then use S and T as the type of the fields first and second. We ensure that getFirst() returns type S and getSecond() returns type T, so that the compiler will give an error if we mix up the types.

Note that the constructor for Pair is still declared as Pair (without the type parameters).

Just like a variable must be declared before it is used, a type variable must be declared as a type parameter before it is used. For instance, the following would result in a compilation error:

class A {
    T x; // compilation error: T not declared
}

Here is a summary of the two approaches towards writing generic code:

Aspect	Using Object	Using Generics
Type checking	Run time	Compile time
Casts required	Yes	No
Risk of ClassCastException	High	Eliminated
Code readability	Lower	Higher
Compiler assistance	Minimal	Strong

Generics allow us to encode relationships between types directly in method and class definitions, so that the compiler, not the programmer, checks these relationship.

Using/Instantiating a Generic Type

To use a generic type, we have to pass in type arguments, which itself can be a non-generic type, a generic type, or another type parameter that has been declared. Once a generic type is instantiated, it is called a parameterized type.

To avoid human errors that could lead to ClassCastException in the example above, we can use the generic version of Pair as follows, taking in two non-generic types:

Pair<String,Integer> foo() {
  return new Pair<String,Integer>("hello", 4);
}

Pair<String,Integer> p = foo();
Integer i = (Integer) p.getFirst(); // compile-time error

With the parameterized type Pair<String,Integer>, the return type of getFirst is bound to String, and the compiler now has enough type information to check and give us an error since we try to cast a String to an Integer.

Note that we use Integer instead of int, since only reference types can be used as type arguments.

Just like you can pass a parameter of a method to another method, we can pass the type parameter of a generic type to another:

class DictEntry<T> extends Pair<String,T> {
    :
}

We define a generic class called DictEntry<T> with a single type parameter T that extends from Pair<String,T>, where String is the first type argument (in place of S), while the type parameter T from DictEntry<T> is passed as the type argument for T of Pair<String,T>. Now, if we want a dictionary entry that maps a String to an Integer, we can use the parameterized type DictEntry<Integer>.

Generic Methods

Methods can be parameterized with a type parameter as well. Consider the contains method, which we now put within a class for clarity.

class A {
  public static boolean contains(Object[] array, Object obj) {
    for (Object curr : array) {
      if (curr.equals(obj)) {
        return true;
      }
    }
    return false;
  }
}

While using this method does not involve narrowing type conversion and type casting, it is a little too general — it allows us to call contains in a nonsensical way, like this:

String[] strArray = new String[] { "hello", "world" };
A.contains(strArray, 123);

Searching for an integer within an array of strings is a futile attempt! Let's constrain the type of the object to search for to be the same as the type of the array. We can make this type the parameter to this method:

class A {
  public static <T> boolean contains(T[] array, T obj) {
    for (T curr : array) {
      if (curr.equals(obj)) {
        return true;
      }
    }
    return false;
  }
}

The above shows an example of a generic method. The type variable T is declared within < and > and is added before the return type of the method. This variable T is then scoped within the whole method.

To call a generic method, we need to pass in the type argument placed before the name of the method¹. For instance,

String[] strArray = new String[] { "hello", "world" };
A.<String>contains(strArray, 123); // type mismatch error

The code above won't compile since the compiler expects the second argument to also be a String.

Bounded Type Parameters

Let's now try to apply our newly acquired trick to fix the issue with findLargest. Recall that we have the following findLargest method (which we now put into an ad hoc class just for clarity), which requires us to perform a narrowing type conversion to cast from GetAreable and possibly lead to a runtime error.

class A {
  public static GetAreable findLargest(GetAreable[] array) {
    double maxArea = 0;
    GetAreable maxObj = null;
    for (GetAreable curr : array) {
      double area = curr.getArea();
      if (area > maxArea) {
        maxArea = area;
        maxObj = curr;
      }
    }
    return maxObj;
  }
}

Let's try to make this method generic, by forcing the return type to be the same as the type of the elements in the input array,

class A {
  public static <T> T findLargest(T[] array) {
    double maxArea = 0;
    T maxObj = null;
    for (T curr : array) {
      double area = curr.getArea();
      if (area > maxArea) {
        maxArea = area;
        maxObj = curr;
      }
    }
    return maxObj;
  }
}

The code above won't compile, since the compiler cannot be sure that it can find the method getArea() in type T. In contrast, when we run contains, we have no issue since we are invoking the method equals, which exists in any reference type in Java.

Since we intend to use findLargest only in classes that implement the GetAreable interface and support the getArea() method, we can put a constraint on T. We can say that T must be a subtype of GetAreable when we specify the type parameter:

class A {
  public static <T extends GetAreable> T findLargest(T[] array) {
    double maxArea = 0;
    T maxObj = null;
    for (T curr : array) {
      double area = curr.getArea();
      if (area > maxArea) {
        maxArea = area;
        maxObj = curr;
      }
    }
    return maxObj;
  }
}

We use the keyword extends here to indicate that T must be a subtype of GetAreable. It is unfortunate that Java decides to use the term extends for any type of subtyping when declaring a bounded type parameter, even if the supertype (such as GetAreable) is an interface.

We can use bounded type parameters for declaring generic classes as well. For instance, Java has a generic interface Comparable<T>, which dictates the implementation of the following int compareTo(T t) for any concrete class that implements the interface. Any class that implements the Comparable<T> interface can be compared with an instance of type T to establish an ordering. Such ordering can be useful for sorting objects, for instance.

Suppose we want to compare two Pair instances, by comparing the first element in the pair, we could do the following:

class Pair<S extends Comparable<S>,T> implements Comparable<Pair<S,T>> {
  private S first;
  private T second;

  public Pair(S first, T second) {
    this.first = first;
    this.second = second;
  }

  public S getFirst() {
    return this.first;
  }

  public T getSecond() {
    return this.second;
  }

  @Override
  public int compareTo(Pair<S,T> s1) {
    return this.first.compareTo(s1.first);
  }

  @Override
  public String toString() {
    return this.first + " " + this.second;
  }
}

Let's look at what it means:

• We declared Pair to be a generic type of two type parameters: the first one S is bounded and must be a subtype of Comparable<S>. This bound is self-referential, but it is intuitive — we say that S must be comparable to itself, which is common in many use cases.
• Since we want to compare two Pair instances, we make Pair implement the Comparable interface too, passing in Pair<S,T> as the type argument to Comparable.

Let's see this in action with Arrays::sort method, which sorts an array based on the ordering defined by compareTo.

Object[] array = new Object[] {
  new Pair<String,Integer>("Alice", 1),
  new Pair<String,Integer>("Carol", 2),
  new Pair<String,Integer>("Bob", 3),
  new Pair<String,Integer>("Dave", 4),
};

java.util.Arrays.sort(array);

for (Object o : array) {
  System.out.println(o);
}

You will see the pairs are sorted by the first element.

Summary of Terms

We introduce multiple new terms in this unit. Here is a summary:

Term	Definition	Example
Type Variable	A placeholder for a type, declared in the definition of a generic class or method, and can be used throughout the code within scope.	S and T
Type Parameter	Type variable used in the definition of a generic class or method.	S and T in Pair<S, T>
Generic Type	A class or interface that is parameterized by one or more type parameters.	Pair<S,T>
Type Argument	A concrete type or type variable passed to a generic type or method when it is instantiated or invoked.	String and Integer in Pair<String, Integer>; T in Pair<String, T> when defining DictEntry<T>
Parameterized Type	A generic type with specific type arguments.	Pair<String,Integer>

---

1. Java actually can infer the type using the type inference mechanism and allows us to skip the type argument, but for clarity, we insist on specifying the type explicitly until students get used to the generic types and reasoning about types. ↩