Interface Types and Bounded Generic Types

Java Interfaces

An interface in Java is like a class which only tells us what methods may be called on it, it does not tell us how those methods work. A Java interface is written in a file like a Java class, except that the word interface is used instead of the word class, and methods are given only by their headers. Here is a simple example:

interface PricedObject
{
 public int getPrice();
}

We have already seen a class DrinksMachine where one of the methods is the zero-argument getPrice. However, for a DrinksMachine object to be considered to have type PricedObject the class not only has to have this method, but it also has to indicate that it implements the interface PricedObject. To do this, it just needs to have the words implements PricedObject added after the header to the class, so it becomes:

import java.util.ArrayList;

class DrinksMachine implements PricedObject
{
 ...

Now let's consider another class which implements PricedObject. Below is a simple example, where objects represent words whose price is determined by their Scrabble score ("Scrabble" is a game which involves putting letters togethers to make up words, with the letters that are harder to use having higher scores). Here is the code:

class ScrabbleWord implements PricedObject
{
 private String str;
 public static final int[] scores = {1,3,3,2,1,4,2,4,1,8,5,1,3,1,1,3,10,1,1,1,1,4,4,8,4,10};

 public ScrabbleWord(String s)
 {
  str = s;
 }

 public String getWord()
 {
  return str;
 }

 public int getPrice()
 {
  String str1 = str.toUpperCase();
  int score = 0;
  for(int i=0; i<str1.length(); i++)
     score+=scores[str1.charAt(i)-'A'];
  return score;
 }

 public String toString()
 {
  return str;
 }
}

The way in which Scrabble scores are calculated here is worth considering. There is an array of integers called scores in which the first item is the score of the letter 'A' (1), the second the score of the letter 'B' (3), the third the score of 'C' (3) and so on. You can use characters as if they are integers, they are equivalent to their ASCII representation. Where we have str1.charAt(i)-'A' this is the ASCII representation of the ith character of str1 less the ASCII representation of 'A'. So that gives us the position of the ith character of str1, and we use that to index the letter scores. Note that declaring the array scores as static means there is just one variable of this name shared by all ScrabbleWord objects, and declaring it as final means that its value cannot be changed.

The importance of the type PricedObject is that it enables us to write methods which take arguments where the only method we need call on them is getPrice returning an integer. This enables us to write general code which can be applied to a variety of types of object rather than write separate but near identical code for each different type of object. For example, the following method:

 public static PricedObject cheaper(PricedObject m1,PricedObject m2)
 {
  if(m1.getPrice()<m2.getPrice())
     return m1;
  else
     return m2;
 }

import java.util.Scanner;

class UseDrinksMachines7
{
 public static void main(String[] args)
 {
  Scanner input = new Scanner(System.in);
  System.out.print("Enter an identifier for a drinks machine: ");
  String id = input.next();
  System.out.print("Enter its price: ");
  int p = input.nextInt();
  DrinksMachine mach1 = new DrinksMachine(id,p);
  System.out.print("Enter an identifier for another drinks machine: ");
  id = input.next();
  System.out.print("Enter its price: ");
  p = input.nextInt();
  DrinksMachine mach2 = new DrinksMachine(id,p);
  DrinksMachine mach3 = (DrinksMachine) PricedObjectOps.cheaper(mach1,mach2);
  System.out.println("The cheaper machine is "+mach3.getIdentity());
 }

}

import java.util.Scanner;

class TestScrabble1
{
 public static void main(String[] args)
 {
  Scanner input = new Scanner(System.in);
  System.out.print("Enter a word: ");
  ScrabbleWord word1 = new ScrabbleWord(input.next());
  System.out.print("Enter another word: ");
  ScrabbleWord word2 = new ScrabbleWord(input.next());
  if(PricedObjectOps.samePrice(word1,word2))
     System.out.println("They have equal Scrabble scores");
  else
     {
      ScrabbleWord word3 = (ScrabbleWord) PricedObjectOps.cheaper(word1,word2);
      System.out.println("The word with lower Scrabble score is \""+word3+"\"");
     }
 }
}

 public static boolean samePrice(PricedObject m1,PricedObject m2)
 {
  return m1.getPrice()==m2.getPrice();
 }

 public static boolean isCheaper(PricedObject m1,PricedObject m2)
 {
  return m1.getPrice()<m2.getPrice();
 }

Bounded Types

Now suppose we want to do something similar with a method which takes an arrayList of objects and returns a reference to whichever of them has the highest price according to their getPrice method. We might suppose the following code would work:

 public static PricedObject mostExpensive(ArrayList<PricedObject> a)
 {
  PricedObject highestSoFar = a.get(0);
  for(int i=1; i<a.size(); i++)
     {
      PricedObject next = a.get(i);
      if(isCheaper(highestSoFar,next))
         highestSoFar = next;
     }
  return highestSoFar;
 }

As a simple explanation of why this is the case, an object of type ArrayList<PricedObject> may have objects of type ScrabbleWord and of type DrinksMachine (and any other type which implements PricedObject) added to it. But an object of type ArrayList<DrinksMachine> should not have objects of type ScrabbleObject added to it, and an object of type ArrayList<ScrabbleObject> should not have objects of type DrinksMachine added to it. We would not be able to protect against this if these arrayList objects were referred to by variables of type ArrayList<PricedObject>.

To get around this problem, Java introduces the idea of bounded generic types. Here is how the code for the method mostExpensive should be written using this concept:

 public static <T extends PricedObject> T mostExpensive(ArrayList<T> a)
 {
  T highestSoFar = a.get(0);
  for(int i=1; i<a.size(); i++)
     {
      T next = a.get(i);
      if(isCheaper(highestSoFar,next))
         highestSoFar = next;
     }
  return highestSoFar;
 }

The type Comparable

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

Where Comparable differs from PricedObject is that it is a parameterised type. So, just like ArrayList and LispList which we have seen earlier, it is a way of constructing a type from a base type. The type Comparable<String> has the method int compareTo(String item) in it, the type Comparable<Integer> has the method int compareTo(Integer item) in it, and so on.

If you want a type Thing to have its own version of the compareTo method, then you must give it the class header:

class Thing implements Comparable<Thing>

class ScrabbleWord implements Comparable<ScrabbleWord>
{
 private String str;
 private int score;
 public static final int[] scores = {1,3,3,2,1,4,2,4,1,8,5,1,3,1,1,3,10,1,1,1,1,4,4,8,4,10};

 public ScrabbleWord(String s)
 {
  str = s;
  String str1 = str.toUpperCase();
  score = 0;
  for(int i=0; i<str1.length(); i++)
     score+=scores[str1.charAt(i)-'A'];
 }

 public String getWord()
 {
  return str;
 }

 public int getScore()
 {
  return score;
 }

 public int compareTo(ScrabbleWord word)
 {
  return word.score-score;
 }

 public String toString()
 {
  return str+"("+score+")";
 }
}

The importance of this is that we can now write generic code where the same code can be used for any type of objects, so long as it implements the Comparable interface. Previously, we had to write separate code to sort collections of strings, collections of integers, and collections of any other type. But that is unnecessary. Here, for example, is a class which provides a static method to sort (using selection sort) any arrayList, so long as the objects in the arrayList are of a class which implements the Comparable interface:

import java.util.ArrayList;

class SelSort
{
 public static <T extends Comparable<T>> void sort(ArrayList<T> a)
 {
  for(int i=0; i<a.size()-1; i++)
     {
      int pos = findMinPos(a,i);
      swap(a,i,pos);
     }
 }

 private static <T extends Comparable<T>> int findMinPos(ArrayList<T> a,int pos)
 {
  for(int i=pos+1; i<a.size(); i++)
     if(a.get(i).compareTo(a.get(pos))<0)
        pos=i;
  return pos;
 }

 private static <T> void swap(ArrayList<T> a,int pos1,int pos2)
 {
  T temp = a.get(pos1);
  a.set(pos1,a.get(pos2));
  a.set(pos2,temp);
 }

}

Here is some code you can use to test the above class to sort an arrayList of ScrabbleWord objects:

import java.util.*;

class SortScrabble1
{
 public static void main(String[] args) throws Exception
 {
  Scanner input = new Scanner(System.in);
  System.out.println("Enter some words (all on one line):");
  String line = input.nextLine();
  String[] words = line.split(" ");
  ArrayList<ScrabbleWord> a = new ArrayList<ScrabbleWord>();
  for(int i=0; i<words.length; i++)
     a.add(new ScrabbleWord(words[i]));
  SelSort.sort(a);
  System.out.println("The words in order of their Scrabble score are:\n"+a);
 }
}

import java.util.*;

class SortIntegers1
{
 public static void main(String[] args) throws Exception
 {
  Scanner input = new Scanner(System.in);
  System.out.println("Enter some integers (all on one line):");
  String line = input.nextLine();
  String[] words = line.split(" ");
  ArrayList<Integer> a = new ArrayList<Integer>();
  for(int i=0; i<words.length; i++)
     a.add(Integer.parseInt(words[i]));
  SelSort.sort(a);
  System.out.println("Sorting the integers gives:\n"+a);
 }
}

import java.util.ArrayList;

class QuickSort
{
 public static <T extends Comparable<T>> void sort(ArrayList<T> a)
 {
  sort(a,0,a.size());
 }

 private static <T extends Comparable<T>> void sort(ArrayList<T> a,int from,int to)
 {
  if(to>from+1)
     {
      T pivot = a.get(from);
      int low=from+1,high=to-1;
      while(low<high)
         {
          while(low<high&&a.get(low).compareTo(pivot)<0)
              low++;
          while(pivot.compareTo(a.get(high))<0)
              high--;
          if(low<high)
            {
             swap(a,high,low);
             low++;
             high--;
            }
         }
      while(pivot.compareTo(a.get(high))<0)
         high--;
      swap(a,from,high);
      sort(a,from,high);
      sort(a,high+1,to);
     }
 }

 private static <T> void swap(ArrayList<T> a,int pos1,int pos2)
 {
  T temp = a.get(pos1);
  a.set(pos1,a.get(pos2));
  a.set(pos2,temp);
 }
}

Java's built-in sort code uses the same generalisation. We saw that the static method sort taking an arrayList as an argument and sorting that arrayList destructively is provided in the class Collections which is in the java.util package. So Collections.sort(a) will sort the arrayList referred to by a according to its natural ordering. It will do this even if the objects in the arrayList are ones we have defined ourselves rather than of a class which is already provided by the Java code library. All that is required, if they are of a type we have defined ourselves, is that the class for that type is indicated correctly as implementing the Comparable interface.

One further requirement is needed for the code above to be completely general. Where we have written

<T extends Comparable<T>>

<T extends Comparable<? super T>>

If all this seems rather complicated, you need not worry too much about it. The main thing you need to know is that if you are writing code for an algorithm which depends on items having some sort of ordering, you can make the code general by using a type variable such as T for the type of the items, and then put <T extends Comparable<? super T>> in the headers for the methods of the code before the return type of each method.

As an example, consider the code we used to sort Lisp lists using quick sort previously. This was written then as code to sort a Lisp list of integers. A generalised version of this code which can sort a Lisp list of any base type (so long as it is a type which implements Comparable) is given below:

class QuickSortLispLists
{

 public static <T extends Comparable<? super T>> LispList<T> sort(LispList<T> ls)
 {
  return sort(ls,LispList.<T>empty());
 }

 private static <T extends Comparable<? super T>> LispList<T> sort(LispList<T> ls1,LispList<T> ls2)
 {
  if(ls1.isEmpty())
    return ls2;
  T pivot = ls1.head();
  ls1 = ls1.tail();
  LispList<T> smaller = LispList.empty();
  LispList<T> greater = LispList.empty();
  for(; !ls1.isEmpty(); ls1=ls1.tail())
     {
      T h = ls1.head();
      if(h.compareTo(pivot)<0)
         smaller = smaller.cons(h);
      else
         greater = greater.cons(h);
     }
  greater = sort(greater,ls2);
  return sort(smaller,greater.cons(pivot));
 }

}

Below is code which gives a front end so you can test this with Scrabble words:

import java.util.Scanner;

class SortLispListScrabble
{

 public static void main(String[] args)
 {
  Scanner in = new Scanner(System.in);
  LispList ls1,ls2;
  System.out.print("Enter a list (of words): ");
  String str = in.nextLine();
  ls1 = parseScrabbleLispList(str);
  System.out.println("The list you entered (with Scrabble scores) is: ");
  System.out.println(ls1);
  ls2 = QuickSortLispLists.sort(ls1);
  System.out.println("The list sorted is: ");
  System.out.println(ls2);
 }

 public static LispList<ScrabbleWord> parseScrabbleLispList(String str)
 {
  String line = str.trim();
  String contents = line.substring(1,line.length()-1).trim();
  if(contents.length()==0)
     return LispList.empty();
  String[] words = contents.split(",");
  LispList<ScrabbleWord> list = LispList.empty();
  for(int i=words.length-1; i>=0; i--)
      list = list.cons(new ScrabbleWord(words[i]));
  return list;
 }

}

Last modified: 8 September 2005