Transcript 12 GenericsAndIterators - Rose

CSSE221: Software Dev. Honors

Announcements




Day 12
No baby yet…
Fifteen done.
Please read Class Announcements forum. Info about
submitting IEPs there.
New “late day” policy:






You get 2 “late days” over the course of the term that each give you a
24-hour extension
The burden of turning in an assignment on a non-class day is on you.
You may earn late days for later use by turning in the assignment a
day early.
You may use only 1 late day (or earn 1 early day) per assignment
Some restrictions apply (like right before an exam)
I’ll allow this to be retroactive to any assignment you tried to submit
late or thought about doing; just resubmit it on Thursday and I’ll
enter the grade.
Research questionnaire
This week: CarsTrucksTrains

Monday:


Project workday
Tuesday:
Generics (capsule)
 Iterators


Thursday:


Lists (capsule)
Implementation of linked lists
Generics

We really want our algorithms to operate on any
type of data, without having to re-write the
whole method.

In Java, we can do this two ways:
Use inheritance (pre-Java 1.5, a bit clunky)
 Use Generics (newer, nicer)

Using Inheritance
ArrayList list = new ArrayList();
ArrayList
list
= new ArrayList();
list.add(new
Integer(3));
// 3 needs to be boxed
list.add(3);
list.add("hello");
list.add("hello");
int num = list.get(0); // doesn’t work
int
num =
list.get(0);
// doesn’t work
Integer
temp
= (Integer)list.get(0);
int num = (Integer)list.get(0);
temp.intValue(); // unboxing
Problems/concerns?



We don’t have control over what goes into the list
Typecasting is a pain (and since we don’t have control, then
we have to check for compatibility using instanceof to avoid
ClassCastExceptions
Note: in Java 1.4, it was even worse…
Using Generics
ArrayList<Integer> list =
new ArrayList<Integer>();
list.add(3);
list.add(“hello”); // invalid
int num = list.get(0); // works!
Solves both those problems!
We have control over the types of what goes into the
list
 No typecasting needed

Creating code with Generics


To use generics, use the type in a parameter.
Example showing:


The use of a type in a class
Various places where the type parameter can be used:
public class SomeClass<E> {
public E someMethod(E param) {
E retValue = 2 * param;
return retValue;
}
…
}

Unfortunately, this example doesn’t work, since we can’t multiply
2 by an unknown, possibly non-numeric type.
Demo
Going further




What if I have a method that operates on an ArrayList
of Vehicles, but I want to pass an ArrayList of Trucks?
Intuitively, this should work, but Java doesn’t allow it,
since it couldn’t catch errors until runtime.
Solution? In the method declaration, use type bounds
with wildcards:
public void
processVehicle(ArrayList<? extends Vehicle> list) {

}
for (Vehicle v : list) { … }
Yet further and messier-looking



Consider static E findMedian(E[] array)
Takes an array of type E, returns a value of that type
But we need to restrict the generics to Comparable types only
(because we need compareTo). Use type bounds:
static <E extends Comparable> E findMedian(E[] array)

But Comparable is generic:
static <E extends Comparable<E>> E findMedian(E[] array)

To enforce that E is Comparable, use
static <E extends Comparable<? super E>> E findMedian(E[] array)
If Vehicles were Comparable, then E could be Truck.
Then ? would be Vehicle
Type erasure


At compile time, the generics are replaced with
the types used
If there are bounds, it uses them and inserts the
proper casts
Some Limitations

Can’t use primitives as types


Can’t instantiate a type: E foo = new E();


No int, need to use Integer
What is E? It could even be an abstract class; this
wouldn’t make sense!
Can’t make generic arrays: E[] ar = new E[17];

Naïve solution: use typecasts:
E[] ar = (E[])(new Object[17])
 This gives a compiler warning


Better solution: use ArrayList<E>
Break

Pass in quizzes (questions 1 and 2); I’ll use a
different quiz for the second half.
Intro to Data Structures
Data Structures and the Java
Collections Framework


What is data?
What do we mean by "structure"

A data type
 But

what is a data type, really?
An interpretation of the bits
An interpretation is basically a set of operations.
 The interpretation may be provided by the hardware, as for
int and double types, or by software, as for the
java.math.BigInteger type.
 Or by software with much assistance from the hardware, as for
the java.lang.Array type.

Some basic data structures


What is "special" about
each data type?


Array (1D, 2D, …)
Stack
Queue
List


What is each used for?
What can you say about
time required for
adding an element?
removing an element?
Finding an element?



Set
MultiSet
Map (a.k.a. table, dictionary)






ArrayList
LinkedList
HashMap
TreeMap
PriorityQueue
Tree
Graph
Network
You should know these, inside and out, by the end of CSSE230.
Specifying an ADT in Java

The main Java tool for specifying an ADT is …


… an interface:
Some important methods from this interface:
Factory method
Iterators

Consider a loop to fund the sum of each
element in an array:
for (int i = 0; i < ar.length; i++) {
sum += ar[i];
}
We want to generalize this beyond arrays
What's an iterator?



More specifically, what is a java.util.Iterator?

It's an interface:

interface java.util.Iterator<E>

with the following methods:
We create a new concrete instance of an iterator, but use an
interface return type (using polymorphism). This is what a
factory method does.
The advantage is that if we change the type of collection
used in main(), then we don’t have to change the iterator type.
Example: Using an Iterator
ag is a Collection object.
Using Java 1.5’s “foreach” construct:
Note that the Java compiler essentially translates the latter code into the former.
What's an iterator?


More specifically, what is a java.util.Iterator?

It's an interface:

interface java.util.Iterator<E>

with the following methods:
Why do iterators have their own remove method, separate
from the Collections’ remove?
Sort and Binary Search

The java.util.Arrays class provides static methods
for sorting and doing binary search on arrays. Examples:
Sort and Binary Search


The java.util.Collections
class provides similar static methods for
sorting and doing binary search on
Collections. Specifically Lists.
Look up the details in the
documentation.