Transcript Iterators

Iterators
Chapter 7
Chapter Contents
What is an Iterator?
• A Basic Iterator
• Visits every item in a collection
• Knows if it has visited all items
• Doesn’t know what items it has visited.
• Iterator Methods that Modify the ADT
• Tricky if “modify” means “change location”
Implementing an Internal Iterator
• Can only be one
Implementing an Iterator as Its Own Class
• Can have many
• An External Iterator
• An Inner Class
Idea of Iteration
int listSize = nameList.getLength();
for (int position = 1; position <= listSize; position++)
System.out.println(nameList.getEntry(position));
How is it different from above?
• You don’t need to k now about “position” to use
it.
What Is an Iterator?
A program component
• Enables you to step through (traverse) a
collection of data
• Can tell whether next entry exists
Iterator may be manipulated
• Asked to advance to next entry
• Give a reference to current entry
• Modify the list as you traverse it
A Basic Iterator
import java.util.NoSuchElementException;
public interface BasicIteratorInterface<T>
{ /** Task: Determines whether the iteration has completed its traversal
* and gone beyond the last entry in the collection of data.
* @return true if the iteration has another entry to return */
Our methods throw
exceptions, must import
exception from java.util
public boolean hasCurrent();
/** Task: Advances the current position of the iteration by 1.
* @return true if the iteration has another entry to return */
public boolean advance();
/** Task: Retrieves the current entry in the iteration.
* @return a reference to the current entry in the iteration, if one exists
* @throws NoSuchElementException, if no current entry exists */
public T getCurrent() throws NoSuchElementException;
/** Task: Sets the iteration to begin with the first entry in the collection. */
public void reset();
} // end BasicIteratorInterface
A Basic Iterator
Fig. 7-1 The effect of
iterator methods on a list.
Iterator Methods That Modify the ADT
import java.util.NoSuchElementException;
public interface IteratorInterface<T> extends BasicIteratorInterface<T>
{ public boolean hasCurrent();
public boolean advance();
public T getCurrent() throws NoSuchElementException;
public void reset();
/** Task: Adds a new entry immediately after the current entry, if one exists.
* @param newEntry the object that is the new entry
* @throws NoSuchElementException, if no current entry exists */
public void addAfterCurrent(T newEntry)
throws NoSuchElementException;
/** Task: Removes the current entry, if one exists, and advances the iteration to the next entry.
* @throws NoSuchElementException, if no current entry exists */
public void removeCurrent() throws NoSuchElementException;
/** Task: Replaces the current entry with a new entry.
* @param newEntry the object that replaces the current entry
* @throws NoSuchElementException, if no current entry exists */
public void replaceCurrent(T newEntry)
throws NoSuchElementException;
} // end IteratorInterface
Iterator Methods That Modify the ADT
Fig. 7-2 The effect of
iterator methods on a list.
Iterator Methods That Modify the ADT
Fig. 7-2 (ctd.) The effect of iterator methods on a list.
Implementing an Internal Iterator
Including the methods that IteratorInterface
specifies
import java.util.NoSuchElementException;
public class LinkedListWithInternalIterator<T> implements ListInterface<T>,
IteratorInterface<T> {
private Node firstNode;
private int length;
private Node currentNode; // current node in iteration
private Node priorNode; // node before the current node in iteration
// in case you want to remove current
public LinkedListWithInternalIterator()
{ clear(); } // end default constructor
public final void clear()
{ firstNode = null;
length = 0;
currentNode = null;
priorNode = null;
} // end clear
< Other implementations go here>
} // end LinkedListWithInternalIterator
Implementing an Internal Iterator
Fig. 7-3 Before and after removing current entry
when its node is first in the chain.
Implementing an Internal Iterator
Fig. 7-4 Before and after removing current entry
when its node is not first in the chain.
Implementing an Internal Iterator
Fig. 7-5 Before and after adding an
entry after the current entry.
Implementing an Iterator as Its
Own Class
Fig. 7-6 Counting the
number of times that
Jane appears in a list
of names.
Implementing an Iterator as Its
Own Class
Internal iterator easy to understand, use
• But only one iteration of a list can occur at any
one time
• May need multiple iterators for a single list
Create an external iterator
• Allows multiple instances of an iterator for a list
An External Iterator
Fig. 7-7 An external iterator with a reference to an ADT, an
indicator of its position within the iteration, and know
knowledge of the ADT's implementation
An External Iterator
An external iterator must access an ADT's
data by using public methods of the ADT
• As a result is slower in performing its
operations
• At the same time its implementation is
straightforward
Possible to have multiple instances of
independent external iterators
An iterator for an existing implementation
of an ADT that cannot be altered must be
an external iterator
Inner Class Iterators
Have direct access to an ADT's data
• Thus is as efficient as an internal iterator
• Has similar implementation effort
Advantage
• Can have several iterator objects in existence
at same time
• Each can traverse list independently of one
another
Inner Class Iterators
Fig. 7-8 An inner class iterator with direct access to the
linked chain that implements the ADT.
java.util.Iterator
package java.util;
public interface Iterator<T>
{
/** Task: Determines whether the iteration has completed its traversal
*
and gone beyond the last entry in the collection of data.
* @return true if the iteration has another entry to return */
public boolean hasNext();
/** Task: Retrieves the current (next) entry in the collection
*
and advances the iteration by one position.
* @return a reference to the current entry in the iteration,
*
if one exists
* @throws NoSuchElementException if the iteration had reached the
*
end already, that is, if hasNext() is false */
public T next();
...
} // end Iterator
java.util.Iterator
/** Task: Removes from the collection of data the last entry
*
that next() returned. A subsequent call to next() will
*
behave as it would have before the removal.
*
Precondition: next() has been called, and remove() has not
*
been called since then. The collection has not been
*
altered during the iteration except by calls to this
*
method.
* @throws IllegalStateException if next() has not been called,
*
or if remove() was called already after the last
*
call to next().
* @throws UnsupportedOperationException if this iterator does
*
not permit a remove operation.
*
NOTE: All throws are run-time so no throws declaration required
*/
public void remove(); // Optional
} // end Iterator
Using an Iterator
import java.util.*
LinkedList<String> ll = new LinkedList();
ll.add(“Andy”); ll.add(“Olga”); ll.add(“Aiko”);
Iterator<String> i = ll.iterator();
while ( I.hasNext() ) {
String s = i.next();
// process s
}
for ( Iterator<String> i = ll.iterator(); i.hasNext();) {
s = i.next();
// process s
}
Inner Iterator Class
private class IteratorForLinkedList implements Iterator<T> {
private Node curr, prev, preprev;
private IteratorForLinkedList() {
curr = firstNode; prev = preprev = null;
}
// returns value of curr and then advances curr
public T next() {
if ( hasNext()) {
Node returnNode = curr;
if ( curr != firstNode) preprev = prev;
prev = curr;
curr = curr.next;
return returnNode.data;
} else {
throw new NoSuchElementException("Illegal call to next()");
}
}
Inner Iterator Class (2)
public boolean hasNext() {
return curr != null;
}
// Removes from the underlying collection the last element
// returned by the iterator; must call next() first. For example,
// you can't call next(); remove(); remove();
public void remove() {
if ( preprev == prev)
return; // next() must be called first
else {
if ( preprev == null ) {
firstNode = curr; length--;
prev = null;
} else {
preprev.next = curr;
prev = preprev; length--;
}
}
}
Inner Iterator Class (3)
// Now how do we deliver an inner class Iterator to the
// rest of the world without exposing its class type (which,
// by the way, is unknown to the outside world?
// In the ListInterface<T> interface we declare
public Iterator<T> getIterator() {
return new IteratorForLinkedList();
}