This course has already ended.

Java interfaces, part 2

Now that we have become more familiar with Java generics, we will next review some of the common generic interfaces of the Java class library.

Interface Comparable<T>

Let us begin from the generic interface Comparable that was already shown before:

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

The role of the function compareTo is to define a natural sorting order for objects of type T. For example Java’s sorting functions Collections.sort(List<T> list) and Arrays.sort(Object[] a) or the ordered set TreeSet<T> can be used without specifying a separate comparison function only if the item type implements the interface Comparable. Such items can be compared using the function compareTo required by the interface Comparable.

Below is a simplified version of the previously shown coordinate point class Point2D that now implements the interface Comparable<Point2D>. The class has been augmented with an implementation of the function compareTo(Point2D other) that compares an Point2D object itself with another Point2D object other. This example performs the comparison by comparing primarily the x-coordinates and secondarily the y-coordinates, and these values are compared using the comparison function Double.compare offered by the Double class.

public class Point2D implements Comparable<Point2D> { // Can compare with another Point2D object.
  private double x;
  private double y;

  public Point2D(double x, double y) {
    this.x = x;
    this.y = y;
  }

  public double getX() {
    return x;
  }

  public double getY() {
    return y;
  }

  // Implement the compareTo function required by the interface Comparable<Point2D>.
  @Override
  public int compareTo(Point2D other) {
    int cmp = Double.compare(x, other.x);  // First compare x-coordinates.
    if(cmp == 0) {
      cmp = Double.compare(y, other.y);    // If needed, compare next y-coordinates.
    }
    return cmp;
  }
}

The next code snippet illustrates how Point2D objects can now be sorted without providing a separate comparison function.

Point2D[] ps = {new Point2D(2.5, -1.5), new Point2D(-3.5, 4.5), new Point2D(0.5, 0.5)};
Arrays.sort(ps);       // No need for a separate comparison function.
for(Point2D p : ps) {
  System.out.format(" (%.1f, %.1f)", p.getX(), p.getY());
}

The code would output more or less:

(-3.5, 4.5) (0.5, 0.5) (2.5, -1.5)

Interface Comparator<T>

Another widely used Java class library interface related to comparing objects is Comparator<T>. Its definition is shown below (we have omitted default and static functions).

public interface Comparator<T> {
  int compare(T a, T b);
  boolean equals(Object obj);
}

The function of interest for us is the function int compare(T a, T b). The interface Comparator<T> in effect defines a type for comparison objects: the function compare of an object of type Comparator<T> (ie. of an implementing class) can be used for comparing two objects a and b of type T. Java’s those sorting functions and ordered containers that accept a separate comparison function actually receive the comparison function as an object of a class that implements Comparator.

Comparison object vs. a comparison function defined as a lambda function?

A comparison function that has been defined as a lambda function is not an exception to the preceding rule: the comparison function will be passed in the form of a comparison object of type Comparator even when we use a lambda function. When we pass a lambda function as a parameter to a sorting function, Java will automatically construct an object that implements Comparator and whose member function compare performs the steps defined by our lambda function. We will discuss this further later with relation to Java’s functional interfaces.

Below is an example class CmpPoint2D that implements the interface Comparator<Point2D> and has a member function compare that performs essentially the same comparison as the previously defined comparison member function compareTo.

public class CmpPoint2D implements Comparator<Point2D> { // Can compare two Point2D objects.
  // Implement the compare function required by the interface Comparator<Point2D>.
  @Override
  public int compare(Point2D a, Point2D b) {
    int cmp = Double.compare(a.getX(), b.getX());
    if(cmp == 0) {
      cmp = Double.compare(a.getY(), b.getY());
    }
    return cmp;
  }
}

The previous example about sorting Point2D objects would be transformed into the following form when we use CmpPoint2D for comparing:

Point2D[] ps = {new Point2D(2.5, -1.5), new Point2D(-3.5, 4.5), new Point2D(0.5, 0.5)};
Arrays.sort(ps, new CmpPoint2D());  // Give a new CmpPoint2d as a comparison object.
for(Point2D p : ps) {
  System.out.format(" (%.1f, %.1f)", p.getX(), p.getY());
}

A class that implements Comparator<T> is essentially still just a normal class, so we are free to e.g. define also other members in it. Below is an example where the preceding comparison type CmpPoint2D has been augmented with a constructor (and a private member variable) that allows to modify the comparison behaviour with a constructor parameter: in this example it will define whether the comparison is done in normal or reversed order.

public class CmpPoint2D implements Comparator<Point2D> { // Can compare two Point2D objects.
  // A private member variable that tells whether the comparison order should be reversed or not.
  private final boolean reversed;

  public CmpPoint2D(boolean reversed) {  // A constructor that initializes reversed.
    this.reversed = reversed;
  }

  public CmpPoint2D() {            // A constructor without parameters sets reversed = false.
    this.reversed = false;
  }

  @Override
  public int compare(Point2D a, Point2D b) {
    int cmp = Double.compare(a.getX(), b.getX());
    if(cmp == 0) {
      cmp = Double.compare(a.getY(), b.getY());
    }
    return reversed ? -cmp : cmp; // Reverse the result if reversed is true.
  }
}

This variant could be used e.g. as follows:

Point2D[] ps = {new Point2D(2.5, -1.5), new Point2D(-3.5, 4.5), new Point2D(0.5, 0.5)};
Arrays.sort(ps, new CmpPoint2D(true));  // Give true to CmpPoint2D: sort into reversed order.
for(Point2D p : ps) {
  System.out.format(" (%.1f, %.1f)", p.getX(), p.getY());
}

Interfaces Iterable<E> and Iterator<E>

Let us next consider the two Java class library interfaces Iterable<E> and Iterator<E> that have a strong connection with the much used iterating for loop of form for(V item : vals): this type of a for loop can be used if and only if vals is either a plain array or a container that implements the interface Iterable<E>, and the items must be compatible with the type V of the iterating variable item.

The definition of the interface Iterable<E> (again without default functions) is shown below. Java class library actually uses the type parameter name T instead of E, but this is just a cosmetic difference.

public interface Iterable<E> {
  Iterator<E> iterator();
}

Iterable<E> declares an abstract member function iterator that should return an iterator object of type Iterator<E> that can iterate over the items of its host container. The definition of the interface Iterator<E>, again without default functions, is as follows:

public interface Iterator<E> {
  boolean hasNext();
  E next();
}

The function boolean hasNext() of the iterator tells whether the host container still has remaining items left (or did we already iterate over all?). The function next() returns the next such remaining item (Java documentation also states that it will throw a NoSuchElementException exception if there are no remaining items). The for loop of form for(V item : vals) that iterates over a container of type Iterable<E> is implemented roughly as follows (under the hood by the Java compiler):

for(Iterator<E> iterator = vals.iterator(); iterator.hasNext(); ) {
  V item = iterator.next();
  // Now the actual steps of the for body.
}

In summary of the preceding: if you wish to use the iterating for loop to iterate over your own container, then the container class must implement the interface Iterable<E>, and you additionally need to implement an iterator class next to (or usually inside) it. In order to be able to iterate over the container, an iterator object usually needs to store some kind of a reference to the host container (could refer to a node in a linked container) and perhaps some further information about the progress of the iteration. It is thus quite natural to implement an iterator class as a non-static inner class: such an inner class can directly refer to the members of its enclosing class object (in this case the iterated container) with relation to which the inner class object (in this case the iterator) was created.

Below is a sketch of how to augment the previously shown class LinkedStack<E> to support iteration. In order to avoid redundancy, we show here only those parts that should be added to the previously shown implementation. If you want to test this code, you should copy-paste the codes into a single class. The iterator implemented here iterates over the stack without modifying its contents.

public class LinkedStack<E> implements Iterable<E> { // Now implement Iterable<E>.
  // An inner iterator class. Can be private.
  private class LSIterator implements Iterator<E> {
      // A reference to the next iterated node. Initially "top".
    private Node nextNode = top;  // Can refer directly to the enclosing class member "top".

    // Functions required by the interface Iterator<E>.
    @Override
    public boolean hasNext() {
      return nextNode != null;    // A next item exists unless nextNode is null.
    }

    @Override
    public E next() {
      if(nextNode == null) {    // Throw an exception if there is no next item.
        throw new NoSuchElementException("No more values in the stack!");
      }
      E item = nextNode.getItem();          // Record the returned item.
      nextNode = nextNode.getNext();        // Move nextNode one step forward.
      return item;
    }
  }

  // A function required by the interface Iterable<E>.
  @Override
  public Iterator<E> iterator() {
    return new LSIterator();        // Return a new LSIterator iterator object.
  }

  // Other members as before; not shown here.
}

The next code snippet tests iterating over the stack:

LinkedStack<Integer> intStack = new LinkedStack<>();
intStack.push(2022);
intStack.push(12);
intStack.push(6);
for(Integer i : intStack) {
  System.out.print(i + " ");
}

The code would output:

6 12 2022

Iterator invalidation

The preceding iterator implementation neglected the fact that usually an iterator should be invalidated if the iterated container is modified after the iterator has been created. This could occur e.g. as follows:

LinkedStack<Integer> intStack = new LinkedStack<>();
intStack.push(2022);
Iterator<Integer> iterator = intStack.iterator(); // Create a stack iterator.
intStack.pop();  // Modify the stack; the preceding iterator becomes invalid.
System.out.format("Next value: %d%n", iterator.next()); // Should not succeed!

If an iterator has been invalidated it should refuse to read next items. The idea is to prevent e.g. the situation above where an iterator would try to read items that have already been removed from the container. For example iterators of the ArrayList class throw a ConcurrentModificationException exception if we try to read a next item from an invalid iterator.

We can verify whether an iterator is valid or not by e.g. setting the container to maintain a counter that is incremented after each modification. If we store the current value of the counter into each created iterator object, then iterators can check their validity by comparing their own counter values with the container’s current counter value. If the values differ, then the container has been modified after the iterator was created and the iterator is now invalid. For example the iterator of the ArrayList class has been implemented in this manner.

Anonymous classes

Java allows to define an object, that inherits or implements a supertype, directly in conjunction with a new operation. Such an anonymous class definition is done just as if we were creating a new object of the supertype, but we in addition provide a class body after the constructor parameter list’s end parenthesis (instead of e.g. the usual semicolon). The body of such an anonymous class is defined more or less in similar manner as a normal class, but it cannot define a constructor. It is ok to define new member variables that are initialized directly at their definitions. An anonymous class usually defines at most a few member functions etc. itself, such as provides implementations for a few abstract member functions. Otherwise it might soon become better to just declare a normal class instead; otherwise the code structure might become confusing.

Anonymous classes have usually been used in settings where an object that inherits or implements a class or an interface is needed only temporarily. In earlier Java versions, that did not yet support lambda functions, anonymous classes were commonly used in defining a comparison object in conjunction with a sorting function call.

Below is an example of how Point2D objects could be sorted by defining the comparison object as an anonymous class that implements Comparator<Point2D>. You may notice that the class body is identical with the body of the first Comparator<Point2D> class on this page.

Point2D[] ps = {new Point2D(2.5, -1.5), new Point2D(-3.5, 4.5), new Point2D(0.5, 0.5)};
Arrays.sort(ps, new Comparator<Point2D>(){ // An anonymous class, implements Comparator<Double>.
  // Implement the compare function required by the interface Comparator<Point2D>.
  @Override
  public int compare(Point2D a, Point2D b) {
    int cmp = Double.compare(a.getX(), b.getX());
    if(cmp == 0) {
      cmp = Double.compare(a.getY(), b.getY());
    }
    return cmp;
  }
});  // The end parentheses of (1) the class definition and (2) the sort function call.
for(Point2D p : ps) {
  System.out.format(" (%.1f, %.1f)", p.getX(), p.getY());
}

The object created by an anonymous class definition does not need to be forgotten immediately: we may keep a reference to it and then e.g. use it several times. Below is an example that is otherwise similar as above but now a reference to the comparison object is stored into the variable comparator. Now we could use the same comparison object e.g. in several different sorting function calls.

Point2D[] ps = {new Point2D(2.5, -1.5), new Point2D(-3.5, 4.5), new Point2D(0.5, 0.5)};
Comparator<Point2D> comparator = new Comparator<>(){ // comparator holds the comparison object.
  @Override
  public int compare(Point2D a, Point2D b) {
    int cmp = Double.compare(a.getX(), b.getX());
    if(cmp == 0) {
      cmp = Double.compare(a.getY(), b.getY());
    }
    return cmp;
  }
};
Arrays.sort(ps, comparator);  // Give the comparator object "comparator" as a parameter.
for(Point2D p : ps) {
  System.out.format(" (%.1f, %.1f)", p.getX(), p.getY());
}

Although comparison functions like above would currently be usually defined as lambda functions, it is good to note that anonymous classes are more versatile than lambda functions: a lambda function can define only exactly one function (which is good enough for e.g. sorting), but an anonymous class can define several functions (and also member variables). Therefore lambda functions have not made anonymous classes completely obsolete.

The role of the interface Comparable<T> is

When we pass a lambda function as a parameter to a sorting function

If one wants to use a self-implemented container in a for(V item : vals) for loop

Posting submission...