Lecture 22, Generics & Collections and Maps

Reading

JP chapter 21,22

Study Guide

This lecture has changed significantly since last semester; because generics (type parameters) have been added to Java, and in particular to the container classes.

The goal of this lecture is to make you familiar with the container classes in Java, and give you some hints on how to use them. And in particular to let you understand the usage of Generics in the container libraries. We will try to keep the container concepts free from the generics at first.

We assume that you are already familiar with the array-types in Java, and know how to use arrays for storing and retrieving object references and primitive types. But in many ways the functionality of arrays is too limited.

Besides arrays, Java therefore also has a library of container classes. The figure on page 92 in JP (and in the slides) gives you a graphical overview of these. The container classes have different strengths and have been designed for different purposes. So instead of just using an array every time you need a container, you now have to make a choice between different containers. The purpose of this lecture and the excercises is to give you some knowledge of what would be the best choise in different situations.

To make such a choise it is necessary to have some basic understanding of the data structures that the container classes represent, and the algorithms that work on these structures. The lecture will aim to give you a "crash course" on this subject. In section 22.10 there is a figure which illustrates the time complexity of the most common operations on different Collections - the figure might be difficult to understand at first, but hopefully the lecture will make it a bit clearer why some Collections are faster at some operations than others.

When reading the pages in JP chap 22 it is important that you get the following points:

The elements inserted into the container classes MUST be objects - primitive types can be autoboxed (see section 5.4).
What are the basic differences between a Set, a List, and a Map?
In what order are the elements in for example a LinkedList, TreeSet and TreeMap traversed when you use an Iterator?
What is the use of a Comparator? (section 22.8)
What is natural ordering of elements? (section 22.8)
Is the ordering in a TreeMap based on the order of the keys or on the order of the elements?(section 22.6)?

Excercises for lecture 12

(Hand-In)Use of Collections and Maps
For this excercise you will have to use the class Story.java, which is an example program that you can find on the homepage. The class has a method getTextAsLinkedList(), which returns a text broken into words, which have been added to a LinkedList. (If you like to you can try to run the main method of the Story class, to see how the story has been broken into words.)

Write a class CollectionTest.java with a main method where you can try out the different things you are asked to do in this excercise. Remember to use an Iterator when you have to traverse the Collections. You can use typeparameters if you wish, but that is not the point of this exercise.
1. Print out how many words the story consists of.
2. Print out the word at index 45.
3. Print out how many different words the story consists of (Hint: copy the elements into another Collection which do not allow duplicates, and then ask for the number of elements in this Collection).
4. Print out the words of the story in alphabethical order. Every word should appear exactly once (e.g. so that the String "after" and the String "she" is only printed once).
5. Print out how many there is of each kind of word in the text, in alphabetical order (Hint: use a Map, with the elements represented in this way: [after, 4] and [she, 8] - the word would be the key, and the number is represented as an Integer-object, which is incremented every time the same word appears in the story).
6. Print out the words in the story which have more than six letters.
(Hand-In) Generics
The purpose of this exercise is to let you use the generic List interface and ArrayList class of the 1.5 collection library. The exercise will have a lot of focus on which types are compatible. They can be solved without actually running the program you develop, as it only concerns compile time aspects.
Write a new class with a main method. The rest of the exercise can be done by adding code fragments to this main method. You will need access to the Person and Student classes below:
```
class Person {
	String name;
	Integer birthYear;
	Person(String name, int birth){
		this.name = name;
		birthYear = birth; // boxing
	}
	Integer age(){
		return 2004-birthYear; // unboxing & boxing
	}
}
class Student extends Person{
	String university;
	Student(String name, int birth){
		super(name, birth);
		university = "ITU";
	}
	Student(String name, int birth, String university){
		super(name, birth);
		this.university = university;
	}
}
```
1. Declare a list lp of persons and set it to an ArrayList of person types. Remember to import java.util.* to get access to the collection library. Your task is to get the type parameters right in this declaration. Use the compiler to verify your results.
2. What error message do you get if you try to insert a string into lp?
3. Make statements that insert a person object first and a student object second into lp.
4. Declare a Person p and a Student s variable.
  1. Will lp.get(1) return a Person or a Student object?
  2. Why does s = lp.get(1) give a compile time error?
  3. Why does s = (Student)lp.get(1) not give a compile time error?
  4. If the right thing is to cast, what good are generics then?
5. Declare a list ls of students.
  1. Remember, if p is a declared as Person, and s is declared as Student, one can assign as: p = s; and s = (Student)p;
  2. What error message is given if you make the assignment ls=lp?
  3. Why is it illegal to write ls = lp;
  4. Why is it also illegal to write lp = ls?
  5. Note: array assignments like this are not often used in practice, but the same rules apply when you pass lists as parameters to methods, which happens more frequently.
6. Declare a List<? extends Person> lep.
  1. How can you initialize the lep variable? Why can you not write "new ArrayList<? extends Person>()"?
  2. Can you make the assignment lpp = lp?
  3. Can you make the assignment lpp = ls?
  4. Can you insert elements into lpp? Why (not)?
  5. Can you get elements from lpp?
7. Declare a map, which can map a name to a person. Use the interface Map as type for the variable, and HashMap as the class to instantiate.
8. Make a statement that inserts a Person and one that inserts a student.
9. Make a statement that looks up a Person. Can the result be assigned to p? can it be assigned to s?
(Hand-In) Making a class with type parameters
In this exercise we will make a small class that itself has a generic parameter. It is a Store in which can store some goods. It is loosely based example 118 page 89 in JP. Considder the following 5 classes:

Without type parameters, the class Store could look like this
import java.util.*;
public class Store{
	private List goods;

	public Store()
	{
		goods = new ArrayList();
	}

	public void add(Object obj){
	    goods.add(obj);
	}
	
	public Object remove(){
	    return goods.remove(goods.size()-1);
	}
}
Add a type parameter T to Store, so that the generic class Store can be instantiated like Store<Bicycle> or Store<Goods>, but not Store<String>. Change body of the class so that appropriate fields, parameters and return types use the new parameter T. Did you have to change anything in the body of the methods?
The Goods and Bicycle classes could be defined as:
public class Goods{
    private String description;

    public Goods(String desc){
        description = desc;
    }

    public String toString(){
        return description;
    }
}
public class Bicycle extends Goods{
	public Bicycle(String s){
	    super(s);
	}
}
Test that the typeparameters you added in a) works in the following example main method:
public static void main(String[] args){
   Store<Bicycle> bStore = new Store<Bicycle>();
   Bicycle big = new Bicycle("big");
   Bicycle small = new Bicycle("Small");
   bStore.add(big);
   bStore.add(small);
   Bicycle b = bStore.remove();
   System.out.println(b);
}
Add a method public void addAll(Collection< whatToWriteHere > c) to Store. The method should add all the elements in c to the goods List. There are really two parts to this exercise, to figure out type expression should be used instead of whatToWriteHere, and the implementation of the method body. It should be so that if the store is a general Goods store, you should be able to add a collection of Bicycles. That is, the following call should be possible:
  Store<Goods> generalStore = new Store<Goods>();
  generalStore.addAll(new ArrayList());
(Hard and optional). Now, we want a method which can sell all elements from the store. Rather than returning a collection of all the elements, we pass a collection c as parameter, and the method should place all the elements in the Store in c. The method could be implemented as:
	public void sellAll(Collection<T> buyer){
	    for(T elm:goods) buyer.add(elm);
	}
But the following call should be possible.
	Store<Bicycle> bStore = new Store<Bicycle>();
	Collection<Goods> g = new ArrayList<Goods>();
	bStore.sellAll(g);
What should one write instead of T and why?
 