Generics

Install the App

Download the source archive
Generics.zip
Extract and install it into NetBeans as a Java Project with Existing Sources.

User-defined Generic Classes

In Java, generic means parameterized by one or more type variable. Generics appear in Java in several ways: The genericity is expressed by using a type expression something like this:
<T>
Other qualifications about T can also be expressed within this syntax.

Here is a user-defined version of an ArrayList class with some of its functionality.

myarraylist.MyArrayList
package myarraylist;
 
import java.util.Arrays;
 
public class MyArrayList<T> {
  private Object[] data;
  private int size = 0;
 
  public MyArrayList(int initialCapacity) {
    data = new Object[initialCapacity];
  }
 
  public MyArrayList() {
    this(10);
  }
 
  public int size() {
    return size;
  }
 
  public void clear() {
    size = 0;
  }
 
  public boolean isEmpty() {
    return size == 0;
  }
 
  public boolean add(T elt) {
    ensureCapacity(size+1);
    data[size++] = elt;
    return true;
  }
 
  public T get(int pos) {
    rangeCheck(pos);
    return (T) data[pos];
  }
 
  public T set(int pos, T elt) {
    rangeCheck(pos);
    T prev = (T) data[pos];
    data[pos] = elt;
    return prev;
  }
 
  public int indexOf(Object obj) {
    if (obj == null) {
      for (int i = 0; i < size; i++) {
        if (data[i] == null) {
          return i;
        }
      }
    }
    else {
      for (int i = 0; i < size; i++) {
        if (obj.equals(data[i])) {
          return i;
        }
      }
    }
    return -1;
  }
 
  public boolean contains(Object obj) {
    return indexOf(obj) >= 0;
  }
 
  @Override
  public String toString() {
    return Arrays.toString(Arrays.copyOf(data, size));
  }
 
  public void ensureCapacity(int desired_capacity) {
    if (desired_capacity > data.length) {
      throw new UnsupportedOperationException("this list cannot grow");
    }
  }
 
  private void rangeCheck(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException(index + " is out of bounds");
    }
  }
}
Points to note about the class:
  1. The actual underlying array is Object[]. You could, instead, use:
    private T[] data;
    
    However, a limitation of generics is that you cannot do:
    data = new T[initialCapacity]
    
    It must be created as Object type. We could get around this limitation by casting the created array:
    data = (T[]) new Object[initialCapacity];
    
    Our approach, as done in JDK source, is have the array be Object type and cast the return values to type T whenever it is required, e.g.:
    public T get(int pos) {
      rangeCheck(pos);
      return (T) data[pos];
    }
    
  2. The add operations must check that there is sufficient space. We use the ensureCapacity member function, which, for simplicity, ignores the issue of growing the array and throws an exception if the desired new capacity would exceed the array's length.
  3. Because the type of data[i] is Object, both of these will evaluate incorrectly
    data[i].equals(obj)  
    obj.equals(data[i])
    
    when used within the method
    int indexOf( Object obj )
    
    if the overloaded version of equals is used. You must use the overridden equals.
  4. Java lists can contain null elements!

    We have ignored this issue until now, but a correctly written indexOf(Object obj) cannot exclusively use the equals function because both
    data[i].equals(obj)    and     obj.equals(data[i])
    
    might fail since one or both of obj and data[i] could be null.

    The solution is to regard obj == null as a special case and test the data array for the presence of null.
  5. Our code does what is done in JDK source in that the data array is treated simply as an Object array:
    private Object[] data;
    
    with initialization:
    data = new Object[initialCapacity];
    
    and then cast every access which returns type T, e.g.,
      public T get(int pos) {
        rangeCheck(pos);
        return (T) data[pos];
      }
    
    Here is a consequence. The test for equality in indexOf(obj), when obj != null is:
    obj.equals(data[i])
    
    This means that data[i] is typed as Object. In particular, for our user-defined classes, the overloaded equals member function will not work; we definitely need the overriden version.
The following driver programs tests some of these features.

myarraylist.Driver
package myarraylist;
 
public class Driver {
  public static void main(String[] args) {
    MyArrayList<String> list = new MyArrayList<>(100);
    list.add("Bob");
    list.add("Carol");
    list.add("Ted");
    list.add("Alice");
    list.add(null);
    list.add("Fred");
 
    System.out.println("list = " + list);
 
    System.out.println("list.get(2) = " + list.get(2));
 
    String prev = list.set(2, "Joe");
    System.out.println("list at position 2 was " + prev);
    System.out.println("after set, list = " + list);
 
    System.out.println("list.indexOf(\"Alice\") = " + list.indexOf("Alice"));
    System.out.println("list.indexOf(\"Jill\") = " + list.indexOf("Jill"));
    System.out.println("list.indexOf(null) = " + list.indexOf(null));
    System.out.println("");
 
    MyArrayList whatever = new MyArrayList();
 
    whatever.add(55);
    whatever.add("hello");
    whatever.add(33.1);
 
    for (int i = 0; i < whatever.size(); ++i) {
      Object obj = whatever.get(i);
      System.out.format("%s:\t%s\n", obj, obj.getClass());
    }
  }
}
The list whatever is created in raw form with undeclared type. This is equivalent to
MyArrayList<Object> whatever = new MyArrayList<>();
Generic classes created in raw form are legacy, pre-1.5, and should be avoided.

Limitations of Generics

The Java compiler disallows the usage of generics in various places. The solution is usually to replace the generic type by Object and then perform casts by the generic type. Here are the exclusions:
  1. We already mentioned that only Object, not primitive types can be used for generics, e.g. this is illegal:
    ArrayList<int> list1 = new ArrayList<>();
    
  2. We noted in our example above that arrays cannot be instantiated by a generic type, e.g., this is illegal:
    T[] array = new T[100]; 
    
    you can get around this by casting:
    T[] array = (T[]) new Object[100]; 
    
  3. You cannot create an array of generic class objects per se, this is illegal:
    ArrayList<String>[] list = new ArrayList<>[10];
    
    You can do so, rather easily, by dropping the generic aspect in the object creation (right-hand side):
    ArrayList<String>[] list = new ArrayList[10];
    
  4. You cannot create an initialized array of generic class objects (even if empty)
    ArrayList<String>[] list = {  };
    
  5. You cannot instantiate via a generic type, e.g., this is illegal:
    T obj = new T();
    
  6. The instanceof operator does not work for generic types, e.g. this is illegal:
    if (obj instanceof T) { ... }
    
The following program illustrates the above errors in the commented sections. It also indicates the allowable replacements.

generics.Errors
package generics;
 
import java.util.ArrayList;
 
public class Errors<T> {
 
  public void error1() {
//    ArrayList<int> list1 = new ArrayList<>();
    ArrayList<Integer> list2 = new ArrayList<>();
  }
 
  public void error2() {
//    T[] array1 = new T[100];
    T[] array2 = (T[]) new Object[100];
  }
 
  public void error3() {
//    ArrayList<String>[] list1 = new ArrayList<String>[10];
//    ArrayList<String>[] list2 = new ArrayList<>[10];
    ArrayList<String>[] list3 = new ArrayList[10];
    list3[0] = new ArrayList<>();
    ArrayList<String>[] list4 = (ArrayList<String>[]) new Object [10];
  }
 
  public void error4() {
//    ArrayList<String>[] list1 = { };
  }
 
  public void error5() {
//    T obj1 = new T();
    T obj2 = (T) new Object();
  }
 
  public void error6(Object obj) {
//    if (obj instanceof T) {
//      System.out.println("yes");
//    }
  }
}

Generic Comparable Interface

Many computational operations depend on the ability to compare two objects, determining which is "less than" the other, or if they are equal. Perhaps the most important of such operations is sorting.

In general, Objects have no innate ability to make this comparison. The ability to do so is called comparability and in Java it means that the class must implement the Comparable interface:
public interface java.lang.Comparable<T> {
  int compareTo(T elt);
}
Comparability expresses the innate ability to be sorted in a list, and so many Java types are comparable, like Integer, String, etc. The way a class implements this interface is that T must be the class itself, for example, if you look at the String class:
public class String implements Comparable<String> ...
and so if you want your user-defined class MyClass to be comparable, write:
class MyClass implements Comparable<MyClass> { 
  ... 
  public int compareTo(MyClass elt) { ... }  
}
What the compareTo operation does is this:
int c = obj1.compareTo(obj2)
where the interpretation of the return value is:
c < 0  means  obj1 is less than obj2
c > 0  means  obj1 is greater than obj2
c = 0  means  obj1 is equal to obj2
A very simple test program segment to run is this:

comparability.StringComps
package comparability;
 
public class StringComps {
 
  public static void main(String[] args) {
 
    String s1 = "abc";
    String s2 = "abcd";
 
    System.out.println(s1.compareTo("abc"));  // 0
 
    System.out.println(s1.compareTo(s2));  // -1
    System.out.println(s2.compareTo(s1));  // 1
 
    String s3 = "abcz";
    String s4 = "abcd";
 
    System.out.println(s3.compareTo(s4));  // 22
    System.out.println(s4.compareTo(s3));  // -22
  }
}
For strings the ordering is called lexicographic, or dictionary-ordering.

Here is a demo program with a user-defined Person class where the ordering is based on the id field:

support.Person
package support;
 
public class Person implements Comparable<Person> {
  private final String name;
  private final int id;
  public Person(String name, int id) {
    this.name = name;
    this.id = id;
  }
 
  @Override
  public String toString() {
    return String.format("{%s,%s}", name, id);
  }
 
  @Override
  public boolean equals(Object obj) {
    if (obj == null) {
      return false;
    }
    if (!(obj instanceof Person)) {
      return false;
    }
    // this would make equality with objects in subclasses always be false
//    if (this.getClass() != obj.getClass()) {
//      return false;
//    }
    Person person = (Person) obj;
    return person.id == id;
  }
 
  @Override
  public int compareTo(Person p) {
    return id - p.id;
  }
}

support.Student
package support;
 
public class Student extends Person {
  private double gpa;
  public Student(String name, int id, double gpa) {
    super(name,id);
    this.gpa = gpa;
  }
}
Note how we create the comparison within compareTo by simple subtraction:
id - p.id
There are several alternatives:
  1. Use the static Integer.compare function:
    return Integer.compare(id, p.id);
    
  2. Use the compareTo method in Integer:
    return new Integer(id).compareTo(p.id);
    
  3. Do explicitly what is being done implicitly by the first two choices:
    if (id > p.id) {
      return 1;
    }
    else if (id < p.id) {
      return -1;
    }
    else {
      return 0;
    }
    
The following test program illustrates the outcomes of the usages:

comparability.PersonCompareTest
package comparability;
 
import support.Person;
import support.Student;
 
public class PersonCompareTest {
 
  public static void main(String[] args) {
    Person p1 = new Person("Mary Adams", 111);
    Person p2 = new Person("Joe Jones", 123);
    Person p3 = new Person("Mary Martin", 111);  // changed last name
 
    System.out.format("%s.compare( %s ) = %s\n", p1, p2, p1.compareTo(p2));
    System.out.format("%s.compare( %s ) = %s\n", p2, p1, p2.compareTo(p1));
    System.out.format("%s.compare( %s ) = %s\n", p1, p3, p1.compareTo(p3));
    System.out.println("");
 
    System.out.format("%s.equals( %s ) = %s\n", p1, p3, p1.equals(p3));
    System.out.println("");
 
    Student s1 = new Student("Student: Mary Adams", 111, 2.2);
    Student s2 = new Student("Student: Joe Jones", 123, 3.3);
    Student s3 = new Student("Student: Mary Martin", 111, 4.0);
 
    System.out.format("%s.compare( %s ) = %s\n", s1, s2, s1.compareTo(s2));
    System.out.format("%s.compare( %s ) = %s\n", s2, s1, s2.compareTo(s1));
    System.out.format("%s.compare( %s ) = %s\n", s1, s3, s1.compareTo(s3));
    System.out.println("");
 
    System.out.format("%s.equals( %s ) = %s\n", s1, s3, s1.equals(s3));
    System.out.println("");
 
    // Here we are comparing a Person and Student with the same id by 
    // .compareTo and .equals. The results are consistent: they're equal
    // in both cases, whether this should make sense or not is unclear.
    System.out.format("%s.compare( %s ) = %s\n", p1, s1, p1.compareTo(s1));
    System.out.format("%s.equals( %s ) = %s\n", p1, s1, p1.equals(s1));
  }
}

Two notions of equality

Comparability introduces a sense of "equals" based on the compareTo function returning 0. There is also the Object-based sense of equality based on the equals member function. The compareTo-equality and equals-equality need not be the same!

The Generic Comparator interface

Regardless of whether objects of a class are comparable or not, it is still important to be able sort them, say, on some specific field within the object. For this purpose we need the Comparator interface:
public interface java.util.Comparator<T> {
  int compare(T elt1, T elt2);
  boolean equals(Object obj);  // already defined at Object level
}

Using the compare method

A comparator is an object external to the applicable class, meant to be created though an anonymous class invocation:
Comparator<MyClass> comp = new Comparator<MyClass>() {
  @Override
  public int compare(MyClass elt1, MyClass elt2) {
    return /* some int using fields of elt1 and elt2 */;
  }
};
The intended usage is like that of a comparator. The key difference is that it is external to the class.
comp.compare(obj1,obj2) < 0    means obj1 is less than obj2
comp.compare(obj1,obj2) = 0    means obj1 equals obj2
comp.compare(obj1,obj2) > 0    means obj1 is greater than obj2

Skip the equals method

The equals method is listed as a prototype for Comparator. This method is not about the objects being compared, it's about the comparators themselves, i.e.,
Comparator<MyClass> comp1 = /* ... */;
Comparator<MyClass> comp2 = /* ... */;
 
if (comp1.equals(comp2)) ...
There is probably never any need implement it; in fact, the Java documentation says:
"Note that it is always safe not to override Object.equals(Object). However, overriding this method may, in some cases, improve performance by allowing programs to determine that two distinct comparators impose the same order."

Example Usage


support.User
package support;
 
public class User {
  private String name;
  private int id;
  public User(String name, int id) {
    this.name = name;
    this.id = id;
  }
  public int getId() { return id; }
  public String getName() { return name; }
  @Override
  public String toString() {
    return String.format("{%s,%s}", name, id);
  }
}

support.Employee
package support;
 
public class Employee extends User {
  private double salary;
  public Employee(String name, int id, double salary) {
    super(name, id);
    this.salary = salary;
  }
  public double getSalary() { return salary; }
}

comparability.UserCompareTest
package comparability;
 
import support.User;
import support.Employee;
import java.util.Comparator;
 
public class UserCompareTest {
 
  public static void main(String[] args) {
    Comparator<User> uCompId = new Comparator<User>() {
      @Override
      public int compare(User u1, User u2) {
        return u1.getId() - u2.getId();
      }
    };
 
    Comparator<User> uCompName = new Comparator<User>() {
      @Override
      public int compare(User u1, User u2) {
        return u1.getName().compareTo(u2.getName());
      }
    };
 
    Comparator<Employee> eCompSalary = new Comparator<Employee>() {
      @Override 
      public int compare(Employee u1, Employee u2) {
        return Double.compare(u1.getSalary(), u2.getSalary());
      }
    };
 
    User u1 = new User("Joe", 111);
    User u2 = new User("Bill", 222);
 
    System.out.format("uCompId.compare(%s,%s)   = %d\n", 
      u1, u2, uCompId.compare(u1,u2) );
 
    System.out.format("uCompName.compare(%s,%s) = %d\n", 
      u1, u2, uCompName.compare(u1,u2) );
    System.out.println("");
 
    Employee e1 = new Employee("John", 333, 5833.22);
    Employee e2 = new Employee("Carol", 444, 4001.45);
 
    System.out.format("(Employee) uCompId.compare(%s,%s)   = %d\n", 
      e1, e2, uCompId.compare(e1,e2) );
 
    System.out.format("(Employee) uCompName.compare(%s,%s) = %d\n", 
      e1, e2, uCompName.compare(e1,e2) );
    System.out.println("");
 
    System.out.format("eCompSalary.compare(%s,%s) = %d\n", 
      e1, e2, eCompSalary.compare(e1,e2) );
    }
}
Note how we create the salary comparator for Employees:
Comparator<Employee> eCompSalary = new Comparator<Employee>() {
  @Override 
  public int compare(Employee u1, Employee u2) {
    return Double.compare(u1.getSalary(), u2.getSalary());
  }
};
There is no way reasonable way to subtract the two salaries to get an integer return value for comparison, and so we would have to use the static Double.compare function or one of these two choices:
  1. Use the compareTo method in Double:
    return new Double(u1.getSalary()).compareTo(u2.getSalary());
    
  2. Do it explicitly:
    double sal1 = u1.getSalary(), sal2 = u2.getSalary();
    if (sal1 > sal2) {
      return 1;
    }
    else if (sal1 < sal2) {
      return -1;
    }
    else {
      return 0;
    }
    
As you see we can generate whatever sense of comparability we want. A comparator is actually necessary to easily sort an array of objects on multiple fields within the object. A comparator is a viable argument to these Java functions, all which require element comparisons.
Arrays.sort
Collections.sort
Arrays.binarySearch
Collections.binarySearch
You can also use a comparator to subvert the innate comparability of comparable class. A reasonable example is the following which sorts a list of integers in two ways, first by their natural order and second by regarding the integers as strings.

sort.SortTest
package sort;
 
import java.util.Arrays;
import java.util.Comparator;
 
public class SortTest {
 
  public static void main(String[] args) {
    Integer[] A = new Integer[] { 3333, 55, 6, 111111, 444, 22 };
    Integer[] B = (Integer[]) A.clone();
    Integer[] C = (Integer[]) A.clone();
 
    System.out.println("original:          " + Arrays.toString(A));
 
    // make a comparator which compares integers as strings
    Comparator<Integer> compReverse = new Comparator<Integer>() {
      @Override
      public int compare(Integer i1, Integer i2) {
        return i2.compareTo(i1);
      }
    };
 
    // make a comparator which compares integers as strings
    Comparator<Integer> compAsStrings = new Comparator<Integer>() {
      @Override
      public int compare(Integer i1, Integer i2) {
        return i1.toString().compareTo(i2.toString());
      }
    };
 
    Arrays.sort(A);
    Arrays.sort(B, compReverse);
    Arrays.sort(C, compAsStrings);
    System.out.println("sorted normally:   " + Arrays.toString(A));
    System.out.println("sorted in reverse: " + Arrays.toString(B));
    System.out.println("sorted as strings: " + Arrays.toString(C));
  }
}

Static generic functions

Static functions can use generic type parameters so that the types are "stated" within the declaration in a specifc way. For example
public static <T> void foo(List<T> list) {
  ...    
}
The added <T> comes before the return type. A useful static generic function might be something like this:

generics.StaticFuncs
package generics;
...
 
public class StaticFuncs {
 
  public static <T> T randChoice(List<T> list) {
    Random r = new java.util.Random();
    int size = list.size();
    if (size != 0) {
      return list.get(r.nextInt(size));
    }
    return null;
  }
  ...
}
You must have the <T> specifier after static; try removing it to validate the error.

Even more useful would be a function like this:
public static <T> T maxValue(List<T> list) {
  // return the maximum value in the list, or null if empty
}
However, we cannot easily write it because the type T would need to be comparable. We can specify precisely the requirement that we want without further generic constructs.

Generic Type Bound Expressions

The expression <T> can be expanded in two ways: upper bounds and lower bounds.
  1. Upper bound: Add the extends qualifier to create a type expression in this way:
    <T extends SomeThing>
    The usage of extends here can mean either "extends" or "implements," and so SomeThing can be class or interface. The type expression means one of:
    • SomeThing itself, if it is a class,
    • any subclass of the SomeThing class,
    • any class which implements the SomeThing /interface.
    The notion of extends is transitive and so can "accumulate" over more than one level.

  2. Upper bound using a wildcard: When a type like SomeThing is extended/implemented, it is sometimes the case that the type T need not be mentioned within the code. In that case we can replace T by the wildcard, ?:
    <? extends SomeThing>
  3. Lower bound: Apply the super qualifier in this way:
    <? super T>
    This expression means
    either T itself, or any superclass of T.
    It has very specific idiomatic usages which we'll explore.

List of numbers

The abstract class Number serves well for sample usages. If we have a List of numbers we can compute the doubleSum value. This can be expressed in two ways as static functions:

generics.StaticFuncs
package generics;
...
 
public class StaticFuncs {
  ...
  public static <T extends Number> double doubleSum_A(List<T> list) {
    double sum = 0.0;
    for (T n : list) {
      sum += n.doubleValue();
    }
    return sum;
  }
 
  public static double doubleSum_B(List<? extends Number> list) {
    double sum = 0.0;
    for (Number n : list) {
      sum += n.doubleValue();
    }
    return sum;
  }
  ...
}
In the former version, T is used in the for loop iterator:
for (T n : list)
but it gives no more information than simply using:
for (Number n : list)
and so we don't need explicit mention of the T, allowing us to employ the latter wildcard version.

Note that this syntax is not OK:
  public static <T> double doubleSum_A(List<T extends Number> list) {
    double sum = 0.0;
    for (T n : list) {
      sum += n.doubleValue();
    }
    return sum;
  }
}
We could conceivably create a subclass of ArrayList with the idea of dedicating it for Number-related functions:

myarraylist.NumList
package myarraylist;
 
public class NumList<T extends Number> extends ArrayList<T> {
  public double doubleSum() {
    double sum = 0;
    for(int i = 0; i < size(); ++i) {
      sum += get(i).doubleValue();
    }
    return sum;
  }
}
Here is a sample driver program which uses it:

myarraylist.NumListDriver
package myarraylist;
 
public class NumListDriver {
 
  public static void main(String[] args) {
    NumList<Double> numlist1 = new NumList<>();
 
    numlist1.add(3.33);
    numlist1.add(4.11);
    numlist1.add(5.0);
 
    System.out.println(numlist1.doubleSum());
 
    NumList<Number> numlist2 = new NumList<>();
 
    numlist2.add(3);
    numlist2.add(5.33);
    numlist2.add(7.1f);
 
    System.out.println(numlist2.doubleSum());
  }
}

Generic Comparability

Comparable List

Returning to the idea of computing the maximum value in a generic list, we want to say that the type T used must be comparable, leading us to the expression:
<T extends Comparable<T>>
Remember that "extends" used in this sense really means "implements." With this idea in mind we write the static function to find the maximum value in a generic array within a specific range:

comparability.ArrayFuncs
public class ArrayFuncs {
  // first attempt at an array of comparable elements
  public static <T extends Comparable<T>> T max1( T[] arr, int from, int to ) 
  {
    T max = null;
    for (int i = from; i < to; ++i) {
      if (max == null) {
        max = arr[i];
      }
      else if (arr[i].compareTo(max) > 0) {
        max = arr[i];
      }
    }
    return max;
  }
}
Recall our example above:
class Person implements Comparable<Person> { ... }
 
class Student extends Person { ... }
The class comparability.PersonMaxTest illustrates the usages of the max functions for both Person and Student objects:

comparability.PersonMaxTest
     Person P[] = new Person[] {
       new Person("Mary", 222),
       new Person("Joe", 666),
       new Person("Jill", 444),
       new Person("Laura", 333),
     };
 
     Student S[] = new Student[] {
       new Student("Mary", 222, 3.88),
       new Student("Joe", 666, 2.5),
       new Student("Jill", 444, 2.2),
       new Student("Laura", 333, 3.22),
     };
In the subsequent driver program, comparability.PersonMaxTest, the max1 function works for Person:
     Person maxPerson = ArrayFuncs.max1(P, 0, P.length);
However, if we use the derived Student class it fails to compile:
     Student maxStudent = ArrayFuncs.max1(S, 0, S.length);
Here is a driver program. The statement applying max1 to the student array is commented out.

comparability.PersonMaxTest
package comparability;
 
import support.Person;
import support.Student;
 
public class PersonMaxTest {
 
  public static void main(String[] args) {
     Integer A[] = new Integer[] { 33, 22, 45, 19, 13 };
 
     Integer maxInt = ArrayFuncs.max1(A, 0, A.length);
// this works equally:
//     Integer maxInt = ArrayFuncs.max(A, 0, A.length);
 
     System.out.println("maxInt = " + maxInt);
     System.out.println("");
 
     Person P[] = new Person[] {
       new Person("Mary", 222),
       new Person("Joe", 666),
       new Person("Jill", 444),
       new Person("Laura", 333),
     };
 
     Person maxPerson = ArrayFuncs.max1(P, 0, P.length);
// this works equally:
//     Person maxPerson = ArrayFuncs.max(P, 0, P.length);
 
     System.out.println("maxPerson = " + maxPerson);
 
     Student S[] = new Student[] {
       new Student("Mary", 222, 3.88),
       new Student("Joe", 666, 2.5),
       new Student("Jill", 444, 2.2),
       new Student("Laura", 333, 3.22),
     };
 
     // this does not compile:
     //Student maxStudent = ArrayFuncs.max1(S, 0, S.length);
 
     Student maxStudent = ArrayFuncs.max(S, 0, S.length);
 
     System.out.println("maxStudent = " + maxStudent);
     System.out.println("");
  }
}
The reason that max1 doesn't work for Student is that it is the superclass Person of Student which is comparable, not the Student per se, i.e., it is not true that:
Student implements Comparable<Student>
From a UML perspective we have:
Reading this diagram,
Student extends Person implements Comparable<Person>
Equating "implements" with "extends" and using transitivity, we have
Student extends Comparable<Person>
We need the following modification of the generic type expression:
<T extends Comparable<? super T>>
Reading it in our case, T = Student and <? super T> = Person.

This expression also works for the base class; substitute T = Person and <? super T> = Person. Therefore the function we really want is:

comparability.ArrayFuncs
public class ArrayFuncs {
  // correctly expressing an array of comparable elements
  public static <T extends Comparable<? super T>> 
                T max( T[] arr, int from, int to ) 
  {
    T max = null;
    for (int i = from; i < to; ++i) {
      if (max == null) {
        max = arr[i];
      }
      else if (arr[i].compareTo(max) > 0) {
        max = arr[i];
      }
    }
    return max;
  }
}
With the max function, we can correctly use:
     Student maxStudent = ArrayFuncs.max(S, 0, S.length);

Comparator

Fortunately, the comparator specification is simpler. If we pass a comparator into the function, the objects themselves need not be comparable. This suggests alternative, overloaded, definition of our functions max1 and max. First, max1:

comparability.ArrayFuncs
public class ArrayFuncs {            
  public static <T> T max1( T[] arr, int from, int to, Comparator<T> c) 
  {
    T max = null;
    for (int i = from; i < to; ++i) {
      if (max == null) {
        max = arr[i];
      }
      else if (c.compare(arr[i],max) > 0) {
        max = arr[i];
      }
    }
    return max;
  }
}
Here is the demo class in which it appears:

comparability.UserMaxTest
package comparability;
 
import support.User;
import support.Employee;
import java.util.Comparator;
 
public class UserMaxTest {
 
  public static void main(String[] args) {
    Comparator<User> uCompId = new Comparator<User>() {
      @Override
      public int compare(User u1, User u2) {
        return u1.getId() - u2.getId();
      }
    };
 
    Comparator<User> uCompName = new Comparator<User>() {
      @Override
      public int compare(User u1, User u2) {
        return u1.getName().compareTo(u2.getName());
      }
    };
 
    Comparator<Employee> eCompSalary = new Comparator<Employee>() {
      @Override
      public int compare(Employee u1, Employee u2) {
        return Double.compare(u1.getSalary(), u2.getSalary());
      }
    };
 
    User[] users = new User[] {
      new User("Joe", 111),
      new User("Bill", 333),
      new User("Ed", 222),
    };
 
    Employee[] emps = new Employee[] {
      new Employee("John", 333, 5833.22),
      new Employee("Carol", 444, 4001.45),
      new Employee("Ellen", 222, 6122.50),
      new Employee("Dave", 111, 3334.20),
    };
 
    User uId = ArrayFuncs.max1(users, 0, users.length, uCompId);
    User uName = ArrayFuncs.max1(users, 0, users.length, uCompName);      
    // these work equally:
//    User uId = ArrayFuncs.max(users, 0, users.length, uCompId);
//    User uName = ArrayFuncs.max(users, 0, users.length, uCompName);
 
    System.out.println("user max by name = " + uName);
    System.out.println("user max by id   = " + uId);
    System.out.println();
 
    // these two do not work with max1
//    Employee eName = ArrayFuncs.max1(emps, 0, emps.length, uCompName);
//    Employee eId = ArrayFuncs.max1(emps, 0, emps.length, uCompId);
 
    // this works with max1, because comarator is on Employee
//    Employee eSal = ArrayFuncs.max1(emps, 0, emps.length, eCompSalary);
 
    Employee eName = ArrayFuncs.max(emps, 0, emps.length, uCompName);
    Employee eId = ArrayFuncs.max(emps, 0, emps.length, uCompId);
    Employee eSal = ArrayFuncs.max(emps, 0, emps.length, eCompSalary);
 
    System.out.println("employee max by name   = " + eName);
    System.out.println("employee max by id     = " + eId);
    System.out.println("employee max by salary = " + eSal);
  }
}
For the same reasons as in the previous subsection, max1 is not quite what we want. In our example with the User and derived Employee class, the comparators defined for User objects should also work for Employee objects.

So instead of the comparator type being
Comparator<T>
we want:
Comparator<? super T>
With respect to our example,
T = Employee
and
<? super T> = User
The corrected version is this:

comparability.ArrayFuncs
public class ArrayFuncs {            
  public static <T> T max( T[] arr, int from, int to, Comparator<? super T> c) 
  {
    T max = null;
    for (int i = from; i < to; ++i) {
      if (max == null) {
        max = arr[i];
      }
      else if (c.compare(arr[i],max) > 0) {
        max = arr[i];
      }
    }
    return max;
  }
}

Java Sort Functions

Java has many functions to support array and collection usage. They are static functions within the Arrays and Collections classes. We will examine the various built-in sort functions.

Arrays.sort functions

A very simple usage example is
Integer[] A = new Integer[] { 444, 33, 222, 11 };
Arrays.sort(A);
The Arrays.sort has many overloaded possibilities:
static void sort(byte[] a)
static void sort(char[] a)
static void sort(double[] a)
static void sort(float[] a)
static void sort(int[] a)
static void sort(long[] a)
static void sort(short[] a)
 
static void sort(byte[] a, int fromIndex, int toIndex)
static void sort(char[] a, int fromIndex, int toIndex)
static void sort(double[] a, int fromIndex, int toIndex)
static void sort(float[] a, int fromIndex, int toIndex)
static void sort(int[] a, int fromIndex, int toIndex)
static void sort(long[] a, int fromIndex, int toIndex)
static void sort(short[] a, int fromIndex, int toIndex)
 
static void sort(Object[] a)
static void sort(Object[] a, int fromIndex, int toIndex)
 
static <T> void sort(T[] a, Comparator<? super T> c)
static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)
There are two overarching differentiations: Taking that into consideration, there are three categories:

Arrays.sort functions on Object arrays without comparator

The sort function for general Object types without a comparator are these:
static void Arrays.sort( Object[] a )
static void Arrays.sort( Object[] a, int fromIndex, int toIndex )
General used in this sense means "any class." What Java does is simply assume the array consists of comparable objects and makes this cast whenever it must compare two array elements:
((Comparable)a[i]).compareTo( a[j] )
In particular, the Java array sort function give a run time error when non-comparable elements are used, not a compile time error.

Arrays.sort functions with comparator

Hopefully, these now make sense:
static <T> void Arrays.sort( T[] a, Comparator<? super T> c )
static <T> void Arrays.sort(
  T[] a, int fromIndex, int toIndex, Comparator<? super T> c )

Sample program

This program illustrates the basic sort functions on the entire array applied to the Person, Student, User, and Employee classes above.

sort.ArraySortPersonsUsers
package sort;
 
import support.User;
import support.Employee;
import support.Person;
import support.Student;
import java.util.Arrays;
import java.util.Comparator;
 
public class ArraySortPersonsUsers {
 
  public static void main(String[] args) {
    Person persons[] = new Person[]{
      new Person("Mary", 222),
      new Person("Joe", 666),
      new Person("Jill", 444),
      new Person("Laura", 333),
    };
 
    Student students[] = new Student[]{
      new Student("Mary S.", 222, 3.88),
      new Student("Joe S.", 666, 2.5),
      new Student("Jill S.", 444, 2.2),
      new Student("Laura S.", 333, 3.22),
    };
 
    User[] users = new User[]{
      new User("Joe", 111),
      new User("Bill", 333),
      new User("Ed", 222),
    };
 
    Employee[] employees = new Employee[]{
      new Employee("John", 333, 5833.22),
      new Employee("Carol", 444, 4001.45),
      new Employee("Ellen", 222, 6122.50),
      new Employee("Dave", 111, 3334.20),
    };
 
    Comparator<User> uCompId = new Comparator<User>() {
      @Override
      public int compare(User u1, User u2) {
        return u1.getId() - u2.getId();
      }
    };
 
    Comparator<User> uCompName = new Comparator<User>() {
      @Override
      public int compare(User u1, User u2) {
        return u1.getName().compareTo(u2.getName());
      }
    };
 
    System.out.println("persons: " + Arrays.toString(persons));
    System.out.println("students: " + Arrays.toString(students));
    System.out.println("users: " + Arrays.toString(users));
    System.out.println("emps: " + Arrays.toString(employees));
    System.out.println("");
 
    Arrays.sort(persons);
    Arrays.sort(students);
 
    //Arrays.sort(users); // runtime error
    //Arrays.sort(employees); // runtime error
 
    Arrays.sort(users, uCompId);
    Arrays.sort(employees, uCompName);
 
    System.out.println("--- AFTER SORTING ---");
    System.out.println("persons: " + Arrays.toString(persons));
    System.out.println("students: " + Arrays.toString(students));
    System.out.println("users (by id): " + Arrays.toString(users));
    System.out.println("emps (by name): " + Arrays.toString(employees));
  }
}
In particular, we can successfully sort
Arrays.sort(persons);
Arrays.sort(employees);
because the elements are comparable. However these produce runtime (not compile-time) errors:
Arrays.sort(users);
Arrays.sort(employees);
For non-comparable elements, we need to pass in the additional comparator argument. Using the comparators created in the previous section:
Comparator<User> uCompId = new Comparator<User>() {
  @Override
  public int compare(User u1, User u2) { 
    return u1.getId() - u2.getId();
  }
};
 
Comparator<User> uCompName = new Comparator<User>() {
  @Override
  public int compare(User u1, User u2) {
    return u1.getName().compareTo(u2.getName());
  }
};
Examples of successful sort calls could be these:
Arrays.sort(users, uCompId);
Arrays.sort(employees, uCompName);

Collections.sort functions

A very simple usage example is
List<Integer> L = new ArrayList<Integer>();
L.add(444); 
L.add(33); 
L.add(222); 
L.add(11);
Collections.sort(L);
There are only two of these sort functions:
static <T extends Comparable<? super T>> void Collections.sort( List<T> ) 
static <T> void Collections.sort( List<T>, Comparator<? super T> c )
Java follows a different approach in sorting lists by Collections.sort than that used for sorting arrays. In particular, if no comparator is provided, Java requires the list elements to be comparable to be used at all. It gives a compile-time error if a Lists of non-comparable elements is given as the argument.

If we refer back to our Person, Student, User, and Employee classes, and attempt to sort lists of these, we would see:
List<Person> P = new ArrayList<Person>();
List<Student> S = new ArrayList<Student>();
 
List<User> U = new ArrayList<User>();
List<Emplooyee> E = new ArrayList<Employee>();
...
Collections.sort(P);  // OK
Collections.sort(S);  // OK
 
Collections.sort(U);  // Compile-time error
Collections.sort(E);  // Compile-time error
The following example illustrates the equivalent of the previous program, but using ArrayLists instead of arrays:

sort.CollectionsSortPersonsUsers
package sort;
 
import support.User;
import support.Employee;
import support.Person;
import support.Student;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
 
public class CollectionsSortPersonsUsers {
 
  public static void main(String[] args) {
    List<Person> P = new ArrayList<>();
    P.add(new Person("Mary", 222));
    P.add(new Person("Joe", 666));
    P.add(new Person("Jill", 444));
    P.add(new Person("Laura", 333));
 
    List<Student> S = new ArrayList<>();
    S.add(new Student("Mary S.", 222, 3.88));
    S.add(new Student("Joe S.", 666, 2.5));
    S.add(new Student("Jill S.", 444, 2.2));
    S.add(new Student("Laura S.", 333, 3.22));
 
    List<User> U = new ArrayList<>();
    U.add(new User("Joe", 111));
    U.add(new User("Bill", 333));
    U.add(new User("Ed", 222));
 
    List<Employee> E = new ArrayList<>();
    E.add(new Employee("John", 333, 5833.22));
    E.add(new Employee("Carol", 444, 4001.45));
    E.add(new Employee("Ellen", 222, 6122.50));
    E.add(new Employee("Dave", 111, 3334.20));
 
    Comparator<User> uCompId = new Comparator<User>() {
      @Override
      public int compare(User u1, User u2) {
        return u1.getId() - u2.getId();
      }
    };
 
    Comparator<User> uCompName = new Comparator<User>() {
      @Override
      public int compare(User u1, User u2) {
        return u1.getName().compareTo(u2.getName());
      }
    };
 
    System.out.println("persons: " + P);
    System.out.println("students: " + S);
    System.out.println("users: " + U);
    System.out.println("emps: " + E);
    System.out.println("");
 
    Collections.sort(P);
    Collections.sort(S);
 
    // -- compile-time errors:
    //Collections.sort(U);
    //Collections.sort(E);
 
    Collections.sort(U, uCompId);
    Collections.sort(E, uCompName);
 
    System.out.println("--- AFTER SORTING ---");
    System.out.println("persons: " + P);
    System.out.println("students: " + S);
    System.out.println("users (by id): " + U);
    System.out.println("emps (by name): " + E);
  }
}

Alternative Collections-based sort

A version of sort with a comparator can be applied as a member function on a List, instead of a call through a static support function:
list.sort(comparator_for_list_type);
Here is a simple demo program:

sort.CollectionsSortAlt
package sort;
 
import support.User;
import support.Employee;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
 
public class CollectionsSortAlt {
 
  public static void main(String[] args) {
 
    List<User> U = new ArrayList<>();
    U.add(new User("Joe", 111));
    U.add(new User("Bill", 333));
    U.add(new User("Jim", 444));
    U.add(new User("Ed", 222));
 
    List<Employee> E = new ArrayList<>();
    E.add(new Employee("John", 333, 5833.22));
    E.add(new Employee("Carol", 444, 4001.45));
    E.add(new Employee("Ellen", 222, 6122.50));
    E.add(new Employee("Dave", 111, 3334.20));
 
    Comparator<User> uCompId = new Comparator<User>() {
      @Override
      public int compare(User u1, User u2) {
        return u1.getId() - u2.getId();
      }
    };
 
    Comparator<User> uCompName = new Comparator<User>() {
      @Override
      public int compare(User u1, User u2) {
        return u1.getName().compareTo(u2.getName());
      }
    };
 
    System.out.println("users: " + U);
    System.out.println("emps:  " + E);
    System.out.println("");
 
    U.sort(uCompId);
    E.sort(uCompName);
 
    System.out.println("--- AFTER SORTING ---");
    System.out.println("users (by id):  " + U);
    System.out.println("emps (by name): " + E);
  }
 
}

Binary Search

This function has an API analogous to sort, except that the argument list requires an additional search element. Binary Search of an array or list requires that it be sorted to work. The Arrays versions referencing object types are these:
static void Arrays.binarySearch( Object[] a, Object key )
static void Arrays.binarySearch(
  Object[] a, int fromIndex, int toIndex, Object key )
 
static <T> void Arrays.binarySearch( T[] a, T key, Comparator<? super T> c )
static <T> void Arrays.binarySearch(
  T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c )
The complete Collections versions are these:
static <T extends Comparable<? super T>> void 
  Collections.binarySearch( List<T>, T key )
static <T> void 
  Collections.binarySearch( List<T>, T key, Comparator<? super T> c )
Like the sort function, binarySearch will generate a run-time error when sorting an array of non-comparable objects without a comparator. Likewise, the binarySearch will generate a compile-time error when sorting a list of non-comparable objects without a comparator.

Here is a demo program using the Student and Employee subclasses of Person and User, respectively. We're also illustrating how to create an ArrayList from an array using the Arrays.asList static function.

search.BinarySearchDemo
package search;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import support.Employee;
import support.Student;
import support.User;
 
public class BinarySearchDemo {
 
  public static void main(String[] args) {
 
    Student students1[] = new Student[]{
      new Student("Mary S.", 222, 3.88),
      new Student("Joe S.", 666, 2.5),
      new Student("Jill S.", 444, 2.2),
      new Student("Laura S.", 333, 3.22),
    };
 
    List<Student> students2 = new ArrayList<>();
    students2.addAll(Arrays.asList(students1));
 
    Employee[] employees1 = new Employee[]{
      new Employee("John", 333, 5833.22),
      new Employee("Carol", 444, 4001.45),
      new Employee("Ellen", 222, 6122.50),
      new Employee("Dave", 111, 3334.20),
    };
 
    List<Employee> employees2 = new ArrayList<>();
    employees2.addAll(Arrays.asList(employees1));
 
    Comparator<User> uCompName = new Comparator<User>() {
      @Override
      public int compare(User u1, User u2) {
        return u1.getName().compareTo(u2.getName());
      }
    };
 
    //===========================================
 
    int jill_pos, ellen_pos;
 
    System.out.println("array:  " + Arrays.toString(students1));
    Arrays.sort(students1);
    System.out.println("sorted: " + Arrays.toString(students1));
 
    Student jill = new Student("Jill S.", 444, 2.2);
 
    jill_pos = Arrays.binarySearch(students1,jill);
 
    System.out.printf("search: %s pos = %s\n", jill, jill_pos);
 
    System.out.println("-----------------------");
 
    System.out.println("array:  " + Arrays.toString(employees1));
    Arrays.sort(employees1, uCompName);
    System.out.println("sorted: " + Arrays.toString(employees1));
 
    Employee ellen = new Employee("Ellen", 222, 6122.50);
 
    ellen_pos = Arrays.binarySearch(employees1, ellen, uCompName);
 
    System.out.printf("search: %s pos = %s\n", ellen, ellen_pos);
 
    System.out.println("\n=======================\n");
 
    //===========================================
 
    System.out.println("list:   " + students2);
    Collections.sort(students2);
    System.out.println("sorted: " + students2);
 
    jill_pos = Collections.binarySearch(students2, jill);
 
    System.out.printf("search; %s pos = %s\n", jill, jill_pos);
 
    System.out.println("-----------------------");
 
    System.out.println("list:   " + employees2);
    Collections.sort(employees2, uCompName);
    System.out.println("sorted: " + employees2);
 
    ellen_pos = Collections.binarySearch(employees2, ellen, uCompName);
 
    System.out.printf("search: %s pos = %s\n", ellen, ellen_pos);
  }
}

Failed Search

To see a failed search, comment out the student/employee being searched for in the list, either "Jill S." from students1, or "Ellen" from employees1.

In either case, the returned value is negative, but not -1. What do you think is the significance of the actual value returned?


© Robert M. Kline