Java Generics, part 1

The example stack class LinkedStack shown in the section about Java class structure handled items using Object references. A downside of this approach is that it does not allow us to specify a type for the items that the stack should accept. For example the following steps would be legal (compile without errors) but lead into a runtime error

LinkedStack integerStack = new LinkedStack(); // A stack for integers?
stack.push("5");      // Oops: add a string "10".
stack.push(10);       // Add integer 10.
...
Integer a = (Integer) stack.pop(); // Ok, takes the integer 10 from top of the stack.
Integer b = (Integer) stack.pop(); // Error! Now "5" was on top and is incompatibe with Integer.

This kind of type mismatch could have been averted already during compilation if LinkedStack would allow us to specify the item type in similar manner as e.g. ArrayList. In that case the first two preceding code lines woule become as shown below and the compiler could already at compile time give an error about “10” being incompatible with Integer.

LinkedStack<Integer> integerStack = new LinkedStack<>(); // An Integer stack.
stack.push("5");      // Compilation error: attempting to add String into an integer stack.

In order to change LinkedStack to use such type parameters, its definition must be made generic, that is, to accept type parameters. The Java syntax for this is quite simple: just add a type parameter list of form <typeParameter1, ..., typeParameterN> after the class name in the class definition. Type parameters work in a bit similar fashion as function parameters, but type parameters just convey types instead of values. Type parameters are associated with concrete types when code refers to a generic class together with a conrete parameter list. Type parameters are used inside the generic class definition as if they were concrete types. You are free to name type parameters quite freely, but it is a common practice to name them using single uppercase characters.

The following code illustrates the syntax of a generic class definitions:

// A generic class that takes two type parameters A and B.
public class MyGenericClass<A, B> {
  private A valA;  // A member variable whose type is given by type parameter A.
  private B valB;  // A member variable whose type is given by type parameter B.

  // Constructor initializes the members. Note that a type parameter
  // list is not given here (as it is not part of the class name).
  MyGenericClass(A valA, B valB) {
    this.valA = valA;
    this.valB = valB;
  }

  public A getValA() {
    return valA;
  }

  public B getValB() {
    return valB;
  }
}

One thing to note about generic classes is that we can refer to only such members of an object that are known to exist. If the type of an object is given as a type parameter, we can usually only refer to its members that are known to have been inherited from the Object superclass. This makes type parameters mostly suitable for handling objects in a “passive” manner; for situations where we do not need to call any member functions or refer to any other object members. Containers are the main example of such a setting: they usually do not need to know anything about what kind of members the stored items have. If our use case requires to know the item type in more detailed manner, then there would probably be little point in using a type parameter anyway: we should use the required type explicitly. E.g. if in the preceding example we would want to ensure that valB is compatible with the type Reader, we should simply define it as Reader valB and drop the type parameter B altogether.

As noted above, type parameters are associated with concrete types when a generic class is referenced together with a type parameter list. Below is a simplified example of how we could e.g. interpret the type MyGenericClass<String, Double> to mean a class MyGenericClass where the types A and B have been replaced by String and Double:

// A simplified view of how the compiler might interpret the type MyGenericClass<String, Double>.
public class MyGenericClass {
  private String valA;   // Type parameter A has become String.
  private Double valB;   // Type parameter B has become Double.

  MyGenericClass(String valA, Double valB) {  // A and B -> String and Double
    this.valA = valA;
    this.valB = valB;
  }

  public String getValA() {                   // A -> String
    return valA;
  }

  public Double getValB() {                   // B -> Double
    return valB;
  }
}

We will later explain why this is a crude simplification.

Java allows only reference types as type parameters. This is one reason why Java containers only allow storing objects with reference types. E.g. the type MyGenericClass<int, double> would be illegal due to trying to use primitive parameter types.

Below is a little bit more realistic example of a generic class: a generic version of LinkedList that takes the item type as a type parameter E.

// Top level generic class LinkedStack. Takes one type parameter: E
public class LinkedStack<E> {
  // Inner class Node that stores items if type E.
  public class Node {
    private Node next;
    private E item;  // Item type is E, that is, the concrete type that will be
    // specified when the class is referenced with a concrete type parameter.

    private Node(Node next, E item) {  // item type E.
      this.next = next;
      this.item = item;
    }

    Node getNext() {
      return this.next;
    }

    E getItem() {           // Returns an item and return type is thus E.
      return this.item;
    }
  }

  private Node top = null;
  private int n = 0;

  public Node peek() {
    return this.top;
  }

  public Node pop() {
    Node result = this.top;
    if(this.top != null) {
      this.n -= 1;
      this.top = this.top.getNext();
    }
    return result;
  }

  public void push(E item) {  // Item type E.
    this.top = new Node(this.top, item);
    this.n += 1;
  }

  public int size() {
    return this.n;
  }

  // A main function for testing. It assumes to receive command line parameters that
  // represent integers and stores them into String and Integer stacks.
  public static void main(String[] args) {
    LinkedStack<String> strStack = new LinkedStack<>();  // String stack.
    LinkedStack<Integer> intStack = new LinkedStack<>(); // Integer stack.
    for(String arg : args) {
      strStack.push("\"" + arg + "\"");      // Add to String stack, surrounding by quotes.
      intStack.push(Integer.parseInt(arg));  // Add to Integer stack, converting first to int.
    }
    for(int i = 0; i < args.length; i++) {
      System.out.println("Current stack sizes: " + strStack.size() + " and "
              + intStack.size());
      String topStr = strStack.peek().getItem();
      Integer topInt = intStack.peek().getItem();
      System.out.println("  Top items: " + topStr + " and " + topInt);
      System.out.println("Now popping the top items.");
      strStack.pop();
      intStack.pop();
    }
    System.out.println("Current stack sizes: " + strStack.size() + " "
            + intStack.size());
  }
}

running the test program e.g. as java LinkedStack 10 20 30 outputs:

Current stack sizes: 3 and 3
  Top items: "30" and 30
Now popping the top items.
Current stack sizes: 2 and 2
  Top items: "20" and 20
Now popping the top items.
Current stack sizes: 1 and 1
  Top items: "10" and 10
Now popping the top items.
Current stack sizes: 0 0

This generic class LinkedStack is already at leas somewhat realistic example of a generic class. For example Java’s own container classes are implemented in somewhat similar way, although they naturally offer much more comprehensive functionality.

Generic interfaces

An interface can be generic in more or less the same manner as a class. Below is e.g. the definition of a generic interface Comparable from the Java class library:

public interface Comparable<T> {
  public int compareTo(T o);
}

A class that implements the generic interface Comparable<T> must have a public member function int compareTo(T o). The convention behind this interface is that the compareTo function should compare the object itself with the parameter object o and return the comparison result as an int. The interface Comparable<T> is quite important in Java because it defines the “default sorting order” for objects of a class. We will return to this shortly.

Generic functions

Also functions can be generic, and this does not depend on whether the enclosing class or interface is generic. A function definiton is made generic by adding a type parameter list in front of the function parameter type. Generic functions are used especially in situations where the function receives an object of a generic type as a parameter. Below is an example of a static utility function that receives a List<E> list list and an E object query and counts how many times query occurs in the list.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ListUtils {

  // A generic function: add type parameter list in front of the return type.
  // Here we set the function "count" to take one type parameter E
  // by adding <E> in front of the return type int.
  // When the function is called, the items of "list" and the parameter
  // "query" must be of some common type E.
  public static <E> int count(List<E> list, E query) {
    int count = 0;
    if(query == null) {  // Special case: query is null.
      for(E item : list) {
        if(item == null) {  // Is also item null?
          count += 1;
        }
      }
    }
    else {  // The more conventional(?) case: query is not null.
      for(E item : list) {
        if(query.equals(item)) {  // Compare using query.equals.
          count += 1;
        }
      }
    }
    return count;
  }

  // Main function for testing.
  public static void main(String[] args) {
    // ArrayList<Integer> that contains nulls and values 1-5 randomly.
    ArrayList<Integer> is = new ArrayList<>();
    Collections.addAll(is, 2, 5, 1, null, 4, 2, 4, 4, 1, 5,
            5, null, 5, null, 4, 2, 4, 2, 3, 4, null, 3, 1, 3);

    // Count and print out the counts of all items in the Integer list "is".
    System.out.format("The list has %d values whose counts are:%n", is.size());
    for(Integer i = 1; i <= 5; i++) {
      System.out.format("  %d: %d times%n", i, count(is, i));
    }
    System.out.format("  %s: %d times%n%n", null, count(is, null));

    // ArrayList<String> that contains words "one", "two" ja "three" randomly.
    ArrayList<String> ss = new ArrayList<>();
    Collections.addAll(ss, "one", "three", "one", "two", "one", "three", "two");

    // Count and print out the counts of the items in the String list "ss".
    System.out.format("The list has %d values whose counts are:%n", ss.size());
    for(String s : List.of("one", "two", "three")) {
      System.out.format(" \"%s\": %d times%n", s, count(ss, s));
    }
  }
}

The test program outputs:

The list has 24 values whose counts are:
  1: 3 times
  2: 4 times
  3: 3 times
  4: 6 times
  5: 4 times
  null: 4 times

The list has 7 values whose counts are:
"one": 3 times
"two": 2 times
"three": 2 times

Which of the following hold in Java: