More Generics

Generics
> Click or hit Control-Enter to run Example.main above

Lists and maps are the two data structures you meet in heaven. Together you can use them to solve almost any problem.

But you’ll usually use Java`s built-in implementations.

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

import java.util.Map;
import java.util.HashMap;
import java.util.TreeMap;

List list = new ArrayList();
List anotherList = new LinkedList();
Map map = new HashMap();
Map anotherMap = new TreeMap();

> Click or hit Control-Enter to run Example.main above

Java and many languages that followed it have tried to transform runtime errors into compiler errors. Why?

You compile your code before it runs: and so before you have to demo it to a client, or before you deploy it to hundreds of users.
Catching errors at this stage is critical.

Java generics allow us to create reusable classes while allowing the compiler to check our code for correctness.

Type parameters tell the compiler what we are going to do with each data structure.

import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;

List<Integer> integerlist = new ArrayList<>(); // This is list of Integers
Map<Integer, String> = new HashMap<>(); // This maps Integers to Strings

Java generics allow to combine two desirable features of the language:

Polymorphism: because every object inherits from Object it is easy to build general purpose data structures that can operate on every Java object
Type Checking: however, upcasting everything to Object makes it impossible for the compiler to perform compile-time type checking
Generics are intended to allow us to have the best of both worlds

> Click or hit Control-Enter to run Example.main above

So we know how to use existing generic class. But how do we provide our own?

First, we have to declare our class to accept type parameters:

// T is a type parameter that can be used throughout our class
public class SimpleLinkedList<E> {
  // get returns a reference of type E
  public E get(int index) {
  }
  // set takes a reference of type T as its second argument
  public void set(int index, E value) {
  }
}

Class parameters are not variables.

I can use them where I would normally provide a type, but I can’t get or set their values.

public class SimpleLinkedList<E> {
  // I can use the parameter here as a return type...
  public E get(int index) {
    E = String; // But I can't do something like this
  }
}

To help understand how generics work you can imagine the compiler rewriting them when it compiles your code.

public class List<E> {
  public E get(int i) {
  }
  public void set(int i, E value) {
  }
}
List<String> list = new List<>();

public class List {
  public String get(int i) {
  }
  public void set(int i, String value) {
  }
}
List list = new List<>();

public class List<E> {
  public E get(int i) {
  }
  public void set(int i, E value) {
  }
}
List<Integer> list = new List<>();

public class List {
  public Integer get(int i) {
  }
  public void set(int i, Integer value) {
  }
}
List list = new List<>();

Note that this is not actually what happens.

The compiler only creates one instance of each generic class
Type information is used during compilation to check access but then erased
But this isn’t a bad mental model of how generics work in practice

Classes can use one or several type parameters:

// This is a generic list storing elements of type T
public class SimpleLinkedList<T> { }

// This is a generic map mapping elements of type K to type V
public class SimpleMap<K,V> { }

To avoid confusing type parameters with variable names or other keywords, Java has established conventions for naming them.

By convention type names are single uppercase letters: T, K, V, E, etc.
Note that this is just a convention: it’s not enforced by the compiler
Certain type parameters have conventional meanings:
- E for element (which we’ll use for our lists)
- K for key and V for value, (which we’ll use for our maps)
- N for a number

public class Map<K, V> {
  public V get(K key) {
  }
  public void put(K key, V val) {
  }
}
Map<String, Double> map = new Map<>();

public class Map {
  public Double get(String key) {
  }
  public void put(String key, Double val) {
  }
}
Map map = new Map();

public class Map<K, V> {
  public V get(K key) {
  }
  public void put(K key, V val) {
  }
}
Map<Integer, String> map = new Map<>();

public class Map {
  public String get(Integer key) {
  }
  public void put(Integer key, String val) {
  }
}
Map map = new Map();

public class SimpleLinkedList {
  class Item {
    Object value;
    Item next;
    Item(Object setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
  private Item start;
  private int currentSize;

public SimpleLinkedList() { }

public SimpleLinkedList(Object[] array) {
    for (int i = array.length - 1; i >= 0; i--) {
      this.add(0, array[i]);
    }
  }

public void add(int index, Object toAdd) {
    if (index == 0) {
      start = new Item(toAdd, start);
      currentSize++;
      return;
    }
    Item previousItem = getItem(index - 1);
    if (previousItem == null) {
      return;
    }
    Item newItem = new Item(toAdd, previousItem.next);
    previousItem.next = newItem;
    currentSize++;
  }

public Object remove(int index) {
    Object toReturn;
    if (index == 0) {
      toReturn = start;
      start = start.next;
      return toReturn;
    }
    Item previousItem = getItem(index - 1);
    toReturn = previousItem.next;
    previousItem.next = previousItem.next.next;
    return toReturn;
  }

public Object get(int index) {
    Item item = getItem(index);
    if (item == null) {
      return null;
    } else {
      return item.value;
    }
  }

public void set(int index, Object toSet) {
    Item item = getItem(index);
    if (item != null) {
      item.value = toSet;
    }
  }

public int size() {
    return currentSize;
  }

protected Item getItem(int index) {
    if (index < 0 || index >= currentSize) {
      return null;
    }
    int currentIndex = 0;
    for (Item current = start; current != null; current = current.next) {
      if (currentIndex == index) {
        return current;
      }
      currentIndex++;
    }
    return null;
  }
}
public class Example {
  public static void main(String[] unused) {
    SimpleLinkedList simpleList = new SimpleLinkedList();
    for (int i = 0; i < 10; i++) {
      simpleList.add(0, i);
    }
    System.out.println(simpleList.size());
    for (int i = 0; i < 5; i++) {
      simpleList.remove(i);
    }
    System.out.println(simpleList.get(0));
  }
}

> Click or hit Control-Enter to run Example.main above

Because it’s about to get more interesting…

> Click or hit Control-Enter to run Example.main above

The compiler knows all about the relationship between different types, and so it can help us ensure that our generic classes receive appropriate type parameters.

<T extends S>: type T extends class S or implements interface S
<T extends S & U & V>: type T extends or implements S, U, and V

> Click or hit Control-Enter to run Example.main above

Just like classes, interface definitions can use type parameters:

public interface SimpleList<E> {
  public E get(int index);
  public void set(int index, E element);
  public void add(int index, E element);
  public E remove(int index);
  public int size();
}

I’ve elided many of the details of working with generics. Review the official documentation to learn more.

But here’s one of the more obvious things that doesn’t work the way you’d want:

public class LastTen<T> {
  private T[] values;
  private List<T> listOfValues;
  LastTen() {
    value = new T[10]; // You can't create an array of a generic type
    // As a solution you can use a collection type like a list
    listOfValues = new ArrayList<T>(); // This works
  }
}

Monday: streams and functional Java
Wednesday: wrap up and ICES forms

The third and final midterm starts Sunday. Good luck!
Lab next week will be final project evaluations and choosing the best projects to feature at the fair next week. Good luck wrapping up your cool projects! I’m very excited to see what you all built…
I have today from 1–3PM in Siebel 2227. Please stop by!

Java Generics

Compiler Errors v. Runtime Errors

Generics

Generic Rationale

Generifying Your Classes

Class Type Parameters

Parameters Are Not Variables

Compiling Generic Classes

Original and Rewritten List

Original and Rewritten List

Type Erasure

Multiple Type Parameters

Parameter Naming Conventions

Original and Rewritten Map

Original and Rewritten Map

Questions So Far?

Bounded Type Parameters

Generic Interfaces

Generic Gotchas

Questions About Generics?

Next Few Classes

Announcements