Generic Types and theJava CollectionsFrameworkLecture 17CS211 – Summer 20072Announcements A4 posted, due Friday 11:59PM As with A2 and A3, you may work with a partner A3 grades posted Regrade requests due Thursday, 11:59PM3Java Collections Framework Collections: holders that let you store and organize objects in usefulways for efficient access Since Java 1.2, the package java.util includes interfaces andclasses for a general collection framework Goal: conciseness A few concepts that are broadly useful Not an exhaustive set of useful concepts Two types of concepts are provided Interfaces (i.e., ADTs) Implementations4JCF Interfaces and Classes Interfaces Collection Set (no duplicates) SortedSet List (duplicates OK) Map (i.e., Dictionary) SortedMap Iterator Iterable ListIterator Classes HashSet TreeSet ArrayList LinkedList HashMap TreeMap5Collections in Java <5 Before Java 1.5, collections had to be implemented ascollections of type Object So when extracting an element, had to downcast it to Tbefore we could invoke T's methods Compiler could not check that the cast was correct atcompile-time, since it didn't know what T was This was inconvenient and unsafe, could fail at runtime6Collections in Java <5class ArrayStack implements Stack { private Object[] array; //Array that holds the Stack private int index = 0; //First empty slot in Stack public ArrayStack (int maxSize) { array = new Object[maxSize]; } public void push(Object x) { array[index++] = x; } public Object pop() { return array[--index]; } public Object peek() { return array[index-1]; } public boolean isEmpty() { return index == 0; } public void makeEmpty() { index = 0; }}class TestArrayStack { public static void main( String [] args ) { ArrayStack stack = new ArrayStack(100); stack.push( “yes” ); stack.push( “no” ); String str = (String) stack.pop(); // downcast works Integer bad = (Integer) stack.pop(); // runtime error!}7Generic Types in Java 5 When using a collection we generally have a single type T ofelements that we store in it e.g. LinkedList of Integers, HashSet of Strings, etc. Generics in Java 1.5 provide a way to communicate T, the typeof elements in a collection, to the compiler Compiler can check that you have used the collection consistently Result: safer and more efficient code Underlying motivation: we want to detect as many bugs aspossible at compile-time8Example//removes 4-letter words from c//elements must be Stringsstatic void purge(Collection c) { Iterator i = c.iterator(); while (i.hasNext()) { if (((String)i.next()).length() == 4) i.remove();}}//removes 4-letter words from cstatic void purge(Collection<String> c) { Iterator<String> i = c.iterator(); while (i.hasNext()) { if (i.next().length() == 4) i.remove();}}oldnew9Another ExampleMap grades = new HashMap();grades.put("John",new Integer(67));grades.put("Jane",new Integer(88));grades.put("Fred",new Integer(72));Integer x = (Integer)grades.get("John");sum = sum + x.intValue();Map<String,Integer> grades = new HashMap<String,Integer>();grades.put("John",new Integer(67));grades.put("Jane",new Integer(88));grades.put("Fred",new Integer(72));Integer x = grades.get("John");sum = sum + x.intValue();oldnew10Type Casting In effect, Java inserts the correct cast automatically, based onthe declared type In this example, grades.get("John") is automatically cast toIntegerMap<String,Integer> grades = new HashMap<String,Integer>();grades.put("John",new Integer(67));grades.put("Jane",new Integer(88));grades.put("Fred",new Integer(72));Integer x = grades.get("John");sum = sum + x.intValue();11An Aside: Autoboxing Java 5 also has autoboxing and auto-unboxing of primitive types,so the example can be further simplifiedMap<String,Integer> grades = new HashMap<String,Integer>();grades.put("John",new Integer(67));grades.put("Jane",new Integer(88));grades.put("Fred",new Integer(72));Integer x = grades.get("John");sum = sum + x.intValue());Map<String,Integer> grades = new HashMap<String,Integer>();grades.put("John", 67);grades.put("Jane", 88);grades.put("Fred", 72);sum = sum + grades.get("John");12Using Generic Types <T> is read, “of T” For example: Stack<Integer> is read, “Stack of Integer” The type annotation <T> informs the compiler that allextractions from this collection should be automaticallycast to T Specify type in declaration, can be checked at compiletime Can eliminate explicit casts13Advantage of Generics Declaring Collection<String> c tells us somethingabout the variable c (i.e., c holds only Strings) This is true wherever c is used This is enforced at compile-time by the compiler Without use of generic types, explicit downcastingmust be used A cast tells us something the programmer thinks is true at asingle point in the code The Java virtual machine checks whether the programmer isright only at runtime Generics also produce very efficient code14Programming with Generic Types To use the interface List<E>, supply an actual typeargument, e.g., List<Integer> All occurrences of the formal type parameter (E in thiscase) are replaced by the actual type argument(Integer in this case)public interface List<E> { // E is a type variable void add(E x); Iterator<E> iterator();}public interface Iterator<E> { E next(); boolean hasNext();}15SubtypesStack<Integer> s = new Stack<Integer>();s.push(new Integer(7));Stack<Object> t = s; // Gives compiler errort.push("bad idea");System.out.println(s.pop().intValue());Stack<Integer> is not a subtype of Stack<Object>Stack<Integer> s = new Stack<Integer>();s.push(new Integer(7));Stack t = s; // Compiler allows thist.push("bad idea"); // Produces a warningSystem.out.println(s.pop().intValue()); //Runtime error!However, Stack<Integer> is a subtype of Stack (forbackward compatibility with previous Java versions)16Wildcardsvoid printCollection(Collection c) { Iterator i = c.iterator(); while (i.hasNext()) { System.out.println(i.next());}}void printCollection(Collection<Object> c) { for (Object e : c) { System.out.println(e);}}oldgoodvoid printCollection(Collection<?> c) { for (Object e : c) { System.out.println(e);}}bad17Bounded Wildcards Note that if we declared the parameter c to be of typeList<Comparable> then we could not sort an object of typeList<String> (even though String is a subtype
View Full Document
Unlocking...