Transcript Iterators

Today’s Agenda
 Generic
 Iterators
CS2336: Computer Science II
Parameterized Stack
 We implemented stack of Strings
 How about the stack of other type of objects!
 Do we need to implement a separate stack for each type?
 Rewriting code is error-prone
 Maintaining cut-and-paste code is error-prone

How about having a stackOfObjects and use casting
 Run-time error if the types mismatch
StackOfObj s = new StackOfObj();
Apple a = new Apple();
Orange o = new Orange();
s.push(a);
s.push(o);
a = (Apple) (s.pop());
Run-time error
CS2336: Computer Science II
Parameterized Stack : Java Generic
 No casting needed
 Discover mismatches at compile-time instead of
run-time
Stack<Apple> s = new Stack<Apple>();
Apple a = new Apple();
Orange o = new Orange();
s.push(a);
s.push(o);
compile-time error
CS2336: Computer Science II
Generic stack: linked list implementation
Pubic class Stack<Obj>{
private Node first = null;
Public void push(Obj item){
//implementation
}
Public Obj pop() {
//implementation
}
}
CS2336: Computer Science II
Generic stack: array implementation
 Generic array creation is not allowed in java
 We need to use casting ( we call it ugly cast)
Pubic class Stack<Obj>{
private Obj[] stackArray;
Public Stack(int size){
stackArray = (Obj[]) new Object[size];
}
Public void push(Obj item){
//implementation
}
Public Obj pop() {
//implementation
}
}
CS2336: Computer Science II
Iterators
 Allow the user to iterate through any collection
 Java provides Iterable interface
 Make the data structure like stack implement the
Iterable interface
CS2336: Computer Science II
Iterable interface
 It is an interface.
 Has a method that returns an Iterator.
 Iterator has methods:
 hasNext()
 next()
 Java support elegant client code if we make data
structures Iterable.

“foreach” statement that is so compact
Equivalent code
for (String s: Stack)
System.out.println(s);
Iterator<String> i = stack.iterator();
While(i.hasNext()){
String s = i.next();
System.out.println(s);
}
CS2336: Computer Science II
LinkedList Stack
import java.util.Iterator;
pubic class Stack<Obj> implements Iterable<Obj>{
….
public Iterator<obj> iterator(){
return new ListIterator();
}
//inner class
private class ListIterator implements Iterable<Obj>{
private Node current = first;
public boolean hasNext(){return current!=null;}
public Obj next(){
Obj item = current.item;
current = current.next;
return item;
}
}
}
CS2336: Computer Science II
Array Stack
import java.util.Iterator;
pubic class Stack<Obj> implements Iterable<Obj>{
….
public Iterator<obj> iterator(){
return new ReverseArrayItr();
}
//inner class
private class ReverseArrayItr implements Iterable<Obj>{
private int i = topOfArray;
public boolean hasNext(){return i > 0;
public Obj next()
{return stackArray[--i];
}
}
CS2336: Computer Science II
}
}
Java Collection Library
 List interface
 java.util.List is API for sequence of items
 List interface also extends Iterable

java.util.ArrayList uses resizable array
java.util.LinkedList uses Linked list

Why not just use the java library ??

 The problem is that a lot of operations get added, and API
become bloated. It is not a good idea to have lots of
operations to the same API
 We don’t know much about the performance!
CS2336: Computer Science II
Example
Generate random open sites in an N-by-N percolation System
1.
Use an array:
pick (i,j) at random ; if already open, repeat.
Takes linear time o(n)
2. use java.util.Linkedlist
pick an index at random and delete
takes quadratic time (n2)
•
Reason: Java LinedList implementation take linear time to find an
•
Don’t use a library until you understand its API.
item within given index. Not constant time like an array.
CS2336: Computer Science II