Type variance and compatibility

Both class subtyping and interfaces allow an object to be treated as a member of different classes. For example a CreditAccount instance is acceptable as an instance of BankAccount or Object. Similarly a Sphere is acceptable as a Shape or Shape3D.

Although it changes from one programming language to the other, in principle variance rules are as follows:

For example:

    class A {...}
    interface I1 {...}
    interface I2 {...}
    interface I3 { ...}
    class B extends A implements I1 {...}
    class C extends A implements I2, I3 {...}
    class BB extends B implements I3 { ... }
    ...
    A x = new A(); // VALID, Obviously
    A x = new B(); // VALID
    A x = new C(); // VALID
    A x = new BB(); // VALID
    B x = new A(); // NOT VALID !!!!!
    I1 x = new B(); // VALID
    I1 x = new BB(); //VALID
    I3 x = new B(); // NOT VALID !!!
    I3 x = new BB(); //VALID
    I3 x = new C(); //VALID

The need for generics

Consider the linked list and stack example we have studied last week. We have created a nice, mutable list to store an unknown amount of data. But the list can store only one kind of data: integers. To make similarly flexible lists of other kinds of data, we would need to write a type specific version of LinkedList class!

Object oriented programming languages provide some mechanisms, which are commonly named as generics. Before we see how generics work, let's consider one possible solution to our problem. What if we write a LinkedList class to store Object type as data? Since all Java types derive from Object, it seems like we can store anything in such a linked list. To implement this proposal, we'd have to change our Item class as well as other classes as follows, changing all int with Object:

    interface ObjectStack { 
     void push(int item); 
     Object pop() throws Exception; 
    } 

    class ObjectLinkedList implements ObjectStack { 
     Item head; 

     public void push(int data) { 
      if (head==null) 
       head=new Item(data); 
      else 
       head=new Item(data,head); 
     } 

     public Object pop() throws Exception { 
      if (head==null) 
       throw new Exception("List is empty"); 
      else { 
       int retval=head.data; 
       head=head.next; 
       return retval;
      } 
     } 
    } 

    class Item { 
     Item next; 
     Object data; 
     Item(Object data) { this.data=data; } 
     Item(Object data, Item next) { this.data=data; this.next=next;} 
    }

The need for generics (contd.)

The above code will work, in the sense that we can store instances of any type in this linked list (except primitive types). Now consider a stiuation where we store Shapes in the list:

    ObjectLinkedList list=new ObjectLinkedList();
    list.push(new Circle());
    list.push(new Square());
    list.pop().area(); // WILL GIVE AN ERROR
    ((Shape)(list.pop())).area(); // WILL NOT GOVE AN ERROR BUT WILL GOVE A WARNING

Thus we can only make the code work by using typecasting, a nasty method which bypasses all type safety the Java language provides us, and thus making our program very error prone.

Meet generics

Generic typing is a mechanism provided by the programming language which allows us to make types parametric. http://docs.oracle.com/javase/tutorial/java/generics/index.html

It does not mean using dynamic types, which some programming languages do but with huge risks related to type safety, and hence not accepted in industrial grade software.

Instead generic typing allows us to write classes which make some assumptions about a type, but otherwise let the programmer decide the type later when they make use of this class. Therefore the actual type is decided when our class (which uses generics) is used (i.e. instantiated). Therefore, unlike dynamic typing (as in Racket or Python) the type is certainly decided when an object is constructed, but not when class is written!

The type parameters are expressed as <T>, or with assumptions as <T extends BankAccount>, <T implements Shape, Shape3D>, etc.

Type binding in generics

Note that generic typing is different from what we have done when we used Object as data type, which was valid, but very under-informative. Instead generic typing allows more precise information about a data type, it only portpones its declaration:

    class Item<T> { 
     Item<T> next; 
     T data; 
     Item(T data) { this.data=data; } 
     Item(T data, Item<T> next) { this.data=data; this.next=next;} 
    }

In the above code, the type is parameterized as T, and that type is used throughout the class definition in places where you would use a type, e.g. as the data type of data field named data.

Now we can use this class as follows. Note that we are binding the type parameter T to a concrete type when we use it. And we do that in compile time!:

    Item<Shape> item=new Item<Shape>(new Circle(5));
    item.data.area(); // VALID

In the above example since it is known that data is of type Shape, the call is valid.

A complete example could be as follows:

    interface Shape {
        double area();
    }
    class Circle implements Shape {
        double radius;
        Circle(double radius) {this.radius=radius;}
        public double area() {return Math.PI*radius*radius;}
    }

    class Square implements Shape{
        double side;
        Square(double side) {this.side=side;}
        public double area() {return side*side;} 
    }

    class Item<T> { 
        Item<T> next; 
        T data; 
        Item(T data) { this.data=data; } 
        Item(T data, Item<T> next) { this.data=data; this.next=next;} 
    }

    class Tester {
      public static void main(String[] args) {
        Item<Shape> item=new Item<Shape>(new Circle(10));
        System.out.println(item.data.area());
        item.data=new Square(10);
        System.out.println(item.data.area());
      }
    }

Example: A versatile linked list implementation of stack

    interface Stack<T> { 
     void push(T item); 
     T pop() throws Exception; 
    } 

    class LinkedList<T> implements Stack<T> { 
     Item<T> head; 

     public void push(T data) { 
      if (head==null) 
       head=new Item<T>(data); 
      else 
       head=new Item<T>(data,head); 
     } 

     public T pop() throws Exception { 
      if (head==null) 
       throw new Exception("List is empty"); 
      else { 
       T retval=head.data; 
       head=head.next; 
       return retval;
      } 
     } 
    } 

    class Item<T> { 
     Item<T> next; 
     T data; 
     Item(T data) { this.data=data; } 
     Item(T data, Item<T> next) { this.data=data; this.next=next;} 
    }

    class Tester {
      public static void main(String[] args) {
        Stack<Shape> shapes=new LinkedList<Shape>();
        shapes.push(new Circle(10));
        shapes.push(new Square(10));
        try {
          System.out.println(shapes.pop().area());
          System.out.println(shapes.pop().area());
        } catch (Exception e) {
          System.out.println(e);
        }
      }
    }

Inheritence and type compatibility with interfaces

Just as with classes, interfaces can extend other interfaces, hence becoming type compatible with its super-interface:

    interface B {
        ...
    }

    interface A extends B {
        ...
    }

    class C implements A {
        ...
    }

    B x=new C(); //VALID since C implemens A which extends B

Thus, an object is type compatible with its class, all super-classes of it, all interfaces implemented by those classes, and all super-interfaces of those interfaces. This feature becomes important when using generics.

Exercise: Queue interface

Consider a linked list which is intended to be used, not as a stack, but as a queue which allows accessing elements from tail (first-in-first-out) or head (last-in-first-out, as in stack) of the queue. Such an interface must describe methods to:

Design the interface for such a queue.

Exercise solution

A queue is a more general interface than Stack, so it naturally extends Stack:

    interface Queue<T> extends Stack<T> {
        void push(T element);
        T pop();
        T popTail();
        boolean isEmpty();
        int length();
    }

With the above definitions not how type compatibility works, for example:

    class C<T> implements Queue<T> {
      ...
    }

    C<Shape> x=new C<Shape>(); //VALID
    Queue<Shape> x=new C<Shape>(); //VALID
    Stack<Shape> x=new C<Shape>(); //VALID

The Java Lang and Collections framework interfaces

Java language environment comes with a bunch of packages containing many classes. One of these is java.util's group of interfaces and classes called as Collections framework, for use in situations when one needs a mutable data structure.

This framework consists of several interfaces, and classes implementing these interfaces, inside the java.util package http://docs.oracle.com/javase/7/docs/api/java/util/package-summary.html .

The interfaces in this framework can be used to manipulate and use either mutable lists (such as list, set, etc.) or dictionaries (called maps).

In some cases, the interfaces in this framework are deeply integrated into some Java constructs (such as for-each statement).

Iterable and Iterator in for-each loops

Iterable and Iterator are interfaces defined in Collections to iterate over elements of lists/collections, usually inside a special for statement, see http://docs.oracle.com/javase/7/docs/api/java/lang/Iterable.html and http://docs.oracle.com/javase/7/docs/api/java/util/Iterator.html

Here we illustrate the use of this interface with our linked list implementation:

    import java.lang.Iterable;
    import java.util.Iterator;

    interface Stack<T> { 
     void push(T item); 
     T pop() throws Exception; 
    } 

    class Item<T> { 
     Item<T> next; 
     T data; 
     Item(T data) { this.data=data; } 
     Item(T data, Item<T> next) { this.data=data; this.next=next;} 
    }

    class LinkedList<T> implements Stack<T>, Iterable<T> { 
     Item<T> head; 

     public void push(T data) { 
      if (head==null) 
       head=new Item<T>(data); 
      else 
       head=new Item<T>(data,head); 
     } 

     public T pop() throws Exception { 
      if (head==null) 
       throw new Exception("List is empty"); 
      else { 
       T retval=head.data; 
       head=head.next; 
       return retval;
      } 
     } 

     public Iterator<T> iterator() {
       return new LinkedListIterator<T>(this);
     }
    } 

    class LinkedListIterator<T> implements Iterator<T> {
      LinkedList<T> list;
      Item<T> current;
      LinkedListIterator(LinkedList<T> list) {
        this.list=list;
        current=list.head;
      }
      public boolean hasNext(){ return !(current==null); }
      public T next() { 
        T retval=current.data;
        current=current.next;
        return retval;
      }
      public void remove(){
        //skipped
      }
    }

    class Tester {
      public static void main(String[] args) {
        LinkedList<Integer> values=new LinkedList<Integer>();
        values.push(10);
        values.push(5);
        for(Integer val:values)
          System.out.println(val);
      }
    }

Collections framework mutable lists

Collectionss framework provide several classes to be used as mutable lists (see http://java.sun.com/docs/books/tutorial/collections/index.html). Here we will see one example: ArrayList http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html.

All these classes use generic types so can be used to stored objects of your choosing.

ArrayList implements some interfaces in the Collections framework, which are sufficient for us to use it to store items of any type, for example:

    import java.util.ArrayList;
    ...
    ArrayList<Shape> shapes=new ArrayList<Shape>();
    shapes.add(new Circle());
    for (Shape shape: shapes)
        System.out.println(shape);

Exercise: Book with multiple authors

Revisit the library exercise. Assume that an Author class is already written. Write a Book class which can represent a book with as many authors as desired, using an ArrayList.

Exercise solution

The solution below allows an author to know about its books as well

    import java.util.ArrayList;

    class Book {
      String title;
      ArrayList<Author> authors;
      Book(String title) {
        this.title=title;
        this.authors=new ArrayList<Author>();
      }
      void addAuthor(Author author) {
        this.authors.add(author);
      }
      public String toString() {
        String retval=String.format("title: %s",title);
        for(Author author:authors)
          retval+=String.format("\n   author:%s",author.name);
        return retval;
      }
    }

    class Author {
      String name;
      ArrayList<Book> books;
      Author(String name) {
        this.name=name;
        this.books=new ArrayList<Book>();
      }
      void addBook(Book book) {
        this.books.add(book);
      }
    }

    class Tester {
        public static void main(String[] args) {
            Book b=new Book("Empire");
            b.addAuthor(new Author("Negri"));
            b.addAuthor(new Author("Hardt"));
            System.out.println(b);
        }
    }

Ordering of objects

There's a natural ordering of most objects such as numbers, books (according to title), etc. In some cases we may use more than one ordering method to orders objects: e.g. students can be ordered with respect to student-id or lastnames, products in an e-shop can be ordered with respect to price or type, etc.

Java's Comparable and Comparator interfaces play an essential role in ordering of objects, together with the Collections framework.

Comparable is a base class from java.lang package, and implementing Comparable (see http://docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html) interface changes the was your objects are compared. For example:

    class Book implements Comparable<Book> {
        ...
        int compareTo(Book other){
            return title.compareTo(other.title);
        }
    }

With the above modification we can use static utility methods of the Collections class to sort lists of books:

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

    class Book implements Comparable<Book> {
      String title;
      int year;
      ArrayList<Author> authors;
      Book(String title, int year) {
        this.title=title;
        this.year=year;
        this.authors=new ArrayList<Author>();
      }
      void addAuthor(Author author) {
        this.authors.add(author);
      }
      public int compareTo(Book other){
            return title.compareTo(other.title);
      }
      public String toString() {
        String retval=String.format("title: %s, year: %d",title,year);
        for(Author author:authors)
          retval+=String.format("\n   author:%s",author.name);
        return retval;
      }
    }

    class Author {
      String name;
      ArrayList<Book> books;
      Author(String name) {
        this.name=name;
        this.books=new ArrayList<Book>();
      }
      void addBook(Book book) {
        this.books.add(book);
      }
    }

    class Tester {
        public static void main(String[] args) {
          ArrayList<Book> books=new ArrayList<Book>();
          books.add(new Book("b2",1996));
          books.add(new Book("b1",1997));
          books.add(new Book("b3",1998));
          for(Book b:books)
            System.out.println(b);
          Collections.sort(books);
          for(Book b:books)
            System.out.println(b);
        }
    }

Comparator ordering

What if you want to use more than one criteria for sorting a list of objects, at different times, usually depending on user preferences. e.g. students can be ordered with respect to student-id or lastnames.

A comparator is an instance of a class which implements the Comparator interface http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html. The example below allows us to sort books with respect to publication year, using BookComparatorYear class which implements this interface:

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;

    class Book implements Comparable<Book> {
      String title;
      int year;
      ArrayList<Author> authors;
      Book(String title, int year) {
        this.title=title;
        this.year=year;
        this.authors=new ArrayList<Author>();
      }
      void addAuthor(Author author) {
        this.authors.add(author);
      }
      public int compareTo(Book other){
            return title.compareTo(other.title);
      }
      public String toString() {
        String retval=String.format("title: %s, year: %d",title,year);
        for(Author author:authors)
          retval+=String.format("\n   author:%s",author.name);
        return retval;
      }
    }

    class Author {
      String name;
      ArrayList<Book> books;
      Author(String name) {
        this.name=name;
        this.books=new ArrayList<Book>();
      }
      void addBook(Book book) {
        this.books.add(book);
      }
    }

    class BookComparatorYear implements Comparator<Book>{
      public int compare (Book b1, Book b2) {
        if (b1.year<b2.year)
          return -1;
        else if (b1.year==b2.year)
          return 0;
        else return 1;
      }
    }
    class Tester {
        public static void main(String[] args) {
          ArrayList<Book> books=new ArrayList<Book>();
          books.add(new Book("b2",1996));
          books.add(new Book("b1",1997));
          books.add(new Book("b3",1998));
          for(Book b:books)
            System.out.println(b);
          Collections.sort(books, new BookComparatorYear());
          for(Book b:books)
            System.out.println(b);
        }
    }

ADVANCED USAGE NOTE: Since writing a class for each comparison scenario is cumbersome, developers often use inline, anonymous classes as comparators:

    class Tester {
        public static void main(String[] args) {
          ArrayList<Book> books=new ArrayList<Book>();
          books.add(new Book("b2",1996));
          books.add(new Book("b1",1997));
          books.add(new Book("b3",1998));
          for(Book b:books)
            System.out.println(b);
          Comparator<Book> comparator=new Comparator<Book>() {
            public int compare (Book b1, Book b2) {
              if (b1.year<b2.year)
                return -1;
              else if (b1.year==b2.year)
                return 0;
              else return 1;
            }
          };
          Collections.sort(books, comparator);
          for(Book b:books)
            System.out.println(b);
        }
    }

Imposing assumptions on generic types

Consider a scenario in which we would like to implement a sorted list, i.e. a list which stores elements in sorted order. As with our linked list before, this sorted list should be able to store anything, provided that some ordering is defined, so that we can sort the items.

The following example demonstrates how we can impose conditions on a generic type definition:

    class SortedList<T extends Comparable<T>> implements Stack<T>, Iterable<T>{
        ...
    }

This declaration ensures that T is not just any type, but one which is limited to those that extend Comparable (to itself).

Full blown example would look like below. Note that Sorted list just needs to override how new elements are inserted:

    class SortedList<T extends Comparable<T>> extends LinkedList<T>  {

      public void push(T data) {
        if (head==null||head.data.compareTo(data)>0) {
          head=new Item<T>(data,head);
          return;
        }
        Item<T> current=head;
        while (current.next!=null&&current.data.compareTo(data)<0) {
          current=current.next;
        }
        current.next=new Item<T>(data, current.next);
      }
    }



    class Tester {
      public static void main(String[] args) {
        SortedList<Integer> values=new SortedList<Integer>();
        values.push(10);
        values.push(5);
        values.push(15);
        for(Integer val:values)
          System.out.println(val);
      }
    }

Exercise: Graphs

A graph is a set of vertices and a set of edges linking some vertices, \(G=(V,E)\). An example is the friendship relations in Facebook. In most cases edges in the graph has a weight parameter which measures the strength of the relation.

Write Graph and Edge classes which can represent a graph whose vertices can be of any type.

OPTIONAL: Append your code to allow sorting edges with respect to edge strength.

Exercise solution

    import java.util.ArrayList;

    class GenericGraph<T> {
      ArrayList<T> vertices;
      ArrayList<GenericEdge<T>> edges;
      GenericGraph() {
        vertices=new ArrayList<T>();
        edges=new ArrayList<GenericEdge<T>>();
      }
    }

    class GenericEdge<T>{
      T from,to;
      GenericEdge(T from, T to) {
        this.from=from;
        this.to=to;
      }
    }

To implement the optional features, one can use wildcard generics, using ? to mean any type:

    import java.util.ArrayList;

    class GenericGraph<T> {
      ArrayList<T> vertices;
      ArrayList<GenericEdge<T>> edges;
      GenericGraph() {
        vertices=new ArrayList<T>();
        edges=new ArrayList<GenericEdge<T>>();
      }
    }

    class GenericEdge<T> implements Comparable<GenericEdge<?>>{
      T from,to;
      double weight;
      GenericEdge(T from, T to, double weight) {
        this.from=from;
        this.to=to;
        this.weight=weight;
      }
      public int compareTo(GenericEdge<?> other) {
        if (weight<other.weight) return -1;
        else if (weight==other.weight) return 0;
        else return 1;
      }
    }

HOME EXERCISE

Design a Log class which can keep a timestamped log of values of given type, ie. uses generic typing. These log entries can be anything like strings, bank account operations, library resource borrowals, etc., its up to the class user. Assuming that the entries to be logged are of type T your class must implement the following interface:

    import java.util.Iterator;

    interface Logger<T> extends Iterable<T> {
        /** Adds a new log item to this logger */
        void addLog(T newLogItem);

        Iterator<T> iterator();
    }